1 /*---------------------------------------------------------------------------*
2 Project: TwlSDK - PRC -
3 File: prc_algo_common.c
4
5 Copyright 2003-2008 Nintendo. All rights reserved.
6
7 These coded instructions, statements, and computer programs contain
8 proprietary information of Nintendo of America Inc. and/or Nintendo
9 Company Ltd., and are protected by Federal copyright law. They may
10 not be disclosed to third parties or copied or duplicated in any form,
11 in whole or in part, without the prior written consent of Nintendo.
12
13 $Date:: 2008-09-18#$
14 $Rev: 8573 $
15 $Author: okubata_ryoma $
16 *---------------------------------------------------------------------------*/
17
18 #include <nitro.h>
19 #include <nitro/prc/resample.h>
20
21 /*===========================================================================*
22 Prototype Declarations
23 *===========================================================================*/
24
25
26 /*===========================================================================*
27 Variable Definitions
28 *===========================================================================*/
29
30 /*===========================================================================*
31 Functions
32 *===========================================================================*/
33
34 static BOOL
PRCi_TerminateStrokes(u16 * selectedPoints,int * pSelectedPointNum,int maxPointCount,const PRCStrokes * strokes)35 PRCi_TerminateStrokes(u16 *selectedPoints,
36 int *pSelectedPointNum, int maxPointCount, const PRCStrokes *strokes)
37 {
38 int selectedPointNum = *pSelectedPointNum;
39 const PRCPoint *inputPoints;
40
41 inputPoints = strokes->points;
42 if (selectedPointNum < 2)
43 {
44 // If length of dot series is 0 or 1, ignore
45 *pSelectedPointNum = 0;
46 return FALSE;
47 }
48 if (!PRC_IsPenUpMarker(&inputPoints[selectedPoints[selectedPointNum - 1]]))
49 {
50 // Doesn't finish with Pen Up Marker
51 if (!PRC_IsPenUpMarker(&inputPoints[selectedPoints[selectedPointNum - 2]]))
52 {
53 // Next to last is not Pen Up Marker either
54 if (selectedPointNum < maxPointCount)
55 {
56 // If there is room at the end, append Pen Up Marker
57 selectedPoints[selectedPointNum] = (u16)-1;
58 selectedPointNum++;
59 }
60 else
61 {
62 // If no space at the end
63 if (selectedPointNum >= 3
64 && !PRC_IsPenUpMarker(&inputPoints[selectedPoints[selectedPointNum - 3]]))
65 {
66 // If the third from last is also not a Pen Up Marker, overwrite the last one with Pen Up
67 selectedPoints[selectedPointNum - 1] = (u16)-1;
68 }
69 else
70 {
71 // Otherwise delete two
72 selectedPointNum -= 2;
73 }
74 }
75 }
76 else
77 {
78 // If the next to last is a Pen Up Marker, reduce by one without any pause to think
79 selectedPointNum--;
80 }
81 }
82
83 *pSelectedPointNum = selectedPointNum;
84 return TRUE;
85 }
86
87
88 /*---------------------------------------------------------------------------*
89 Name: PRC_ResampleStrokes_None
90
91 Description: Does not resample.
92
93 Arguments: selectedPoints, pSelectedPointNum: Pointers which return results
94 maxPointCount: Upper limit of number of input points (includes pen up marker)
95 maxStrokeCount: Upper limit of stroke count
96 strokes: Raw input coordinate values before sorting
97 threshold: Resampling threshold
98 buffer: Work area ([sizeof(int)*maxPointCount] required)
99
100 Returns: TRUE if resampling succeeded.
101 *---------------------------------------------------------------------------*/
102 BOOL
PRC_ResampleStrokes_None(u16 * selectedPoints,int * pSelectedPointNum,int maxPointCount,int maxStrokeCount,const PRCStrokes * strokes,int threshold,void * buffer)103 PRC_ResampleStrokes_None(u16 *selectedPoints,
104 int *pSelectedPointNum,
105 int maxPointCount,
106 int maxStrokeCount, const PRCStrokes *strokes, int threshold, void *buffer)
107 {
108 // Use the raw dot sequence data without resampling
109 u16 iPoint;
110 int size = strokes->size;
111
112 (void)maxStrokeCount;
113 (void)threshold;
114 (void)buffer;
115
116 if (size > maxPointCount)
117 {
118 size = maxPointCount;
119 }
120 if (size < 2)
121 {
122 // If length of dot series is 0 or 1, ignore
123 *pSelectedPointNum = 0;
124 }
125 else
126 {
127 // Select point automatically
128 for (iPoint = 0; iPoint < size; iPoint++)
129 {
130 selectedPoints[iPoint] = iPoint;
131 }
132 *pSelectedPointNum = iPoint;
133
134 if (!PRC_IsPenUpMarker(&strokes->points[size - 1]))
135 {
136 // Not terminated with Pen Up Marker
137 (void)PRCi_TerminateStrokes(selectedPoints, pSelectedPointNum, maxPointCount, strokes);
138 }
139 }
140
141 return (*pSelectedPointNum > 0);
142 }
143
144 #define PRCi_ABS(x) (((x)>=0)?(x):-(x))
145
146 /*---------------------------------------------------------------------------*
147 Name: PRC_ResampleStrokes_Distance
148
149 Description: Resamples based on city block distance.
150
151 Arguments: selectedPoints, pSelectedPointNum: Pointers which return results
152 maxPointCount: Upper limit of number of input points (includes pen up marker)
153 maxStrokeCount: Upper limit of stroke count
154 strokes: Raw input coordinate values before sorting
155 threshold: Resampling threshold
156 buffer: Work area ([sizeof(int)*maxPointCount] required)
157
158 Returns: TRUE if resampling succeeded.
159 *---------------------------------------------------------------------------*/
160 BOOL
PRC_ResampleStrokes_Distance(u16 * selectedPoints,int * pSelectedPointNum,int maxPointCount,int maxStrokeCount,const PRCStrokes * strokes,int threshold,void * buffer)161 PRC_ResampleStrokes_Distance(u16 *selectedPoints,
162 int *pSelectedPointNum,
163 int maxPointCount,
164 int maxStrokeCount,
165 const PRCStrokes *strokes, int threshold, void *buffer)
166 {
167 int selectedPointNum;
168 int strokeCount;
169 int iPoint;
170 int size;
171 PRCPoint prevPoint;
172 PRCPoint *point;
173 BOOL newFlag;
174 int length;
175
176 SDK_ASSERT(maxPointCount > 0);
177 SDK_ASSERT(maxStrokeCount > 0);
178
179 (void)buffer;
180
181 selectedPointNum = 0;
182 strokeCount = 0;
183
184 size = strokes->size;
185 point = strokes->points;
186
187 newFlag = TRUE;
188 for (iPoint = 0; iPoint < size && selectedPointNum < maxPointCount; iPoint++, point++)
189 {
190 if (!PRC_IsPenUpMarker(point))
191 {
192 if (newFlag)
193 {
194 // The starting point is always selected
195 selectedPoints[selectedPointNum] = (u16)iPoint;
196 selectedPointNum++;
197 length = 0;
198 newFlag = FALSE;
199 }
200 else
201 {
202 length += PRCi_ABS(point->x - prevPoint.x) + PRCi_ABS(point->y - prevPoint.y);
203 if (length >= threshold)
204 {
205 selectedPoints[selectedPointNum] = (u16)iPoint;
206 selectedPointNum++;
207 length = 0;
208 }
209 }
210 prevPoint = *point;
211 }
212 else
213 {
214 if (newFlag)
215 {
216 // Ignore several Pen Up Markers in a row
217 continue;
218 }
219 else
220 {
221 if (selectedPoints[selectedPointNum - 1] != iPoint - 1) // When execution comes here, [selectedPointNum>0] is always true
222 {
223 // End point is always selected
224 selectedPoints[selectedPointNum] = (u16)(iPoint - 1);
225 selectedPointNum++;
226 if (selectedPointNum >= maxPointCount)
227 {
228 break;
229 }
230 }
231 selectedPoints[selectedPointNum] = (u16)iPoint;
232 selectedPointNum++;
233 newFlag = TRUE;
234
235 strokeCount++;
236 if (strokeCount >= maxStrokeCount)
237 {
238 // Max number of strokes exceeded
239 iPoint++; // For the processing after the loop. // At the present time, has no meaning because newFlag == TRUE
240 break;
241 }
242 }
243 }
244 }
245
246 *pSelectedPointNum = selectedPointNum;
247
248 if (!newFlag)
249 {
250 // Not terminated with Pen Up Marker
251
252 // First, confirm that end point is selected
253 if (selectedPointNum > 0 && selectedPoints[selectedPointNum - 1] != iPoint - 1
254 && selectedPointNum < maxPointCount)
255 {
256 // End point is always selected
257 selectedPoints[*pSelectedPointNum] = (u16)(iPoint - 1);
258 (*pSelectedPointNum)++;
259 }
260
261 (void)PRCi_TerminateStrokes(selectedPoints, pSelectedPointNum, maxPointCount, strokes);
262 }
263
264 return (*pSelectedPointNum > 0);
265 }
266
267 /*---------------------------------------------------------------------------*
268 Name: PRC_ResampleStrokes_Angle
269
270 Description: Resamples, based on the angle difference.
271
272 Arguments: selectedPoints, pSelectedPointNum: Pointers which return results
273 maxPointCount: Upper limit of number of input points (includes pen up marker)
274 maxStrokeCount: Upper limit of stroke count
275 strokes: Raw input coordinate values before sorting
276 threshold: Resampling threshold
277 buffer: Work area ([sizeof(int)*maxPointCount] required)
278
279 Returns: TRUE if resampling succeeded.
280 *---------------------------------------------------------------------------*/
281 BOOL
PRC_ResampleStrokes_Angle(u16 * selectedPoints,int * pSelectedPointNum,int maxPointCount,int maxStrokeCount,const PRCStrokes * strokes,int threshold,void * buffer)282 PRC_ResampleStrokes_Angle(u16 *selectedPoints,
283 int *pSelectedPointNum,
284 int maxPointCount,
285 int maxStrokeCount,
286 const PRCStrokes *strokes, int threshold, void *buffer)
287 {
288 #define PRC_RESAMPLE_ANGLE_LENGTH_THRESHOLD 6 // A valid angle cannot be obtained unless one moves about 6 city block lengths away
289 int selectedPointNum;
290 int strokeCount;
291 int iPoint;
292 int size;
293 PRCPoint *point;
294 BOOL newFlag;
295 u16 prevAngle;
296 PRCPoint prevPoint;
297 BOOL firstFlag;
298
299 SDK_ASSERT(maxPointCount > 0);
300 SDK_ASSERT(maxStrokeCount > 0);
301
302 (void)buffer;
303
304 selectedPointNum = 0;
305 strokeCount = 0;
306
307 size = strokes->size;
308 point = strokes->points;
309
310 newFlag = TRUE;
311 for (iPoint = 0; iPoint < size && selectedPointNum < maxPointCount; iPoint++, point++)
312 {
313 if (!PRC_IsPenUpMarker(point))
314 {
315 if (newFlag)
316 {
317 // The starting point is always selected
318 selectedPoints[selectedPointNum] = (u16)iPoint;
319 selectedPointNum++;
320 prevPoint = *point;
321 newFlag = FALSE;
322 firstFlag = TRUE;
323 if (iPoint + 1 < size)
324 {
325 prevAngle =
326 FX_Atan2Idx(((point + 1)->y - point->y) << FX32_SHIFT,
327 ((point + 1)->x - point->x) << FX32_SHIFT);
328 }
329 }
330 else
331 {
332 int length;
333 length = PRCi_ABS(point->x - prevPoint.x) + PRCi_ABS(point->y - prevPoint.y);
334 if (length >= PRC_RESAMPLE_ANGLE_LENGTH_THRESHOLD)
335 {
336 if (firstFlag)
337 {
338 // Watch the angle formed with the next point until the second point is selected.
339 // Otherwise, the direction of the initial segment will be lost.
340 if (iPoint + 1 < size && !PRC_IsPenUpMarker(point + 1))
341 // If [point+1] is the Pen Up Marker, then it is always selected as the endpoint and the following conditions are not needed, but...
342 //
343 {
344 u16 currAngle, nextAngle;
345 nextAngle =
346 FX_Atan2Idx(((point + 1)->y - point->y) << FX32_SHIFT,
347 ((point + 1)->x - point->x) << FX32_SHIFT);
348 if (PRCi_ABS((s16)(prevAngle - nextAngle)) >= threshold)
349 {
350 currAngle =
351 FX_Atan2Idx((point->y - prevPoint.y) << FX32_SHIFT,
352 (point->x - prevPoint.x) << FX32_SHIFT);
353 selectedPoints[selectedPointNum] = (u16)iPoint;
354 selectedPointNum++;
355 prevAngle = currAngle;
356 }
357 }
358 firstFlag = FALSE;
359 }
360 else
361 {
362 u16 currAngle;
363 currAngle =
364 FX_Atan2Idx((point->y - prevPoint.y) << FX32_SHIFT,
365 (point->x - prevPoint.x) << FX32_SHIFT);
366 if (PRCi_ABS((s16)(prevAngle - currAngle)) >= threshold)
367 {
368 selectedPoints[selectedPointNum] = (u16)iPoint;
369 selectedPointNum++;
370 prevAngle = currAngle;
371 }
372 }
373 prevPoint = *point;
374 }
375 }
376 }
377 else
378 {
379 if (newFlag)
380 {
381 // Ignore several Pen Up Markers in a row
382 continue;
383 }
384 else
385 {
386 if (selectedPoints[selectedPointNum - 1] != iPoint - 1) // Always selectedPointNum>0 when comes to here
387 {
388 // End point is always selected
389 selectedPoints[selectedPointNum] = (u16)(iPoint - 1);
390 selectedPointNum++;
391 if (selectedPointNum >= maxPointCount)
392 {
393 break;
394 }
395 }
396 selectedPoints[selectedPointNum] = (u16)iPoint;
397 selectedPointNum++;
398 newFlag = TRUE;
399
400 strokeCount++;
401 if (strokeCount >= maxStrokeCount)
402 {
403 // Max number of strokes exceeded
404 iPoint++; // For the processing after the loop. // At the present time, has no meaning because newFlag == TRUE
405 break;
406 }
407 }
408 }
409 }
410
411 *pSelectedPointNum = selectedPointNum;
412
413 if (!newFlag)
414 {
415 // Not terminated with Pen Up Marker
416
417 // First, confirm that end point is selected
418 if (selectedPointNum > 0 && selectedPoints[selectedPointNum - 1] != iPoint - 1
419 && selectedPointNum < maxPointCount)
420 {
421 // End point is always selected
422 selectedPoints[*pSelectedPointNum] = (u16)(iPoint - 1);
423 (*pSelectedPointNum)++;
424 }
425
426 (void)PRCi_TerminateStrokes(selectedPoints, pSelectedPointNum, maxPointCount, strokes);
427 }
428
429 return (*pSelectedPointNum > 0);
430 }
431
432 /*---------------------------------------------------------------------------*
433 Name: PRC_ResampleStrokes_Recursive
434
435 Description: Resamples with recursive method.
436
437 Arguments: selectedPoints, pSelectedPointNum: Pointers which return results
438 maxPointCount: Upper limit of number of input points (includes pen up marker)
439 maxStrokeCount: Upper limit of stroke count
440 strokes: Raw input coordinate values before sorting
441 threshold: Resampling threshold
442 buffer: Work area ([sizeof(int)*maxPointCount] required)
443
444 Returns: TRUE if resampling succeeded.
445 *---------------------------------------------------------------------------*/
446 BOOL
PRC_ResampleStrokes_Recursive(u16 * selectedPoints,int * pSelectedPointNum,int maxPointCount,int maxStrokeCount,const PRCStrokes * strokes,int threshold,void * buffer)447 PRC_ResampleStrokes_Recursive(u16 *selectedPoints,
448 int *pSelectedPointNum,
449 int maxPointCount,
450 int maxStrokeCount,
451 const PRCStrokes *strokes, int threshold, void *buffer)
452 {
453 u16 beginIndex, endIndex;
454 int stackSize;
455 int stackTop, stackTail;
456 int strokeCount;
457 int selectedPointNum;
458 int size;
459 PRCPoint *inputPoints;
460 u16 *stackP1;
461 u16 *stackP2;
462 int squaredThreshold;
463
464 stackP1 = (u16 *)buffer;
465 stackP2 = (u16 *)buffer + maxPointCount;
466
467 squaredThreshold = threshold * threshold;
468
469 beginIndex = 0;
470 endIndex = 0;
471 strokeCount = 0;
472 selectedPointNum = 0;
473
474 inputPoints = strokes->points;
475 size = strokes->size;
476
477 while (1)
478 {
479 if (selectedPointNum + 3 > maxPointCount || strokeCount > maxStrokeCount)
480 {
481 // No space to store the next stroke
482 // To store a single 'stroke' you must have at least three available spaces: starting point, end point, and PenUpMarker.
483 //
484 break;
485 }
486
487 // Skip over PenUpMarker
488 while (endIndex < size && PRC_IsPenUpMarker(&inputPoints[endIndex]))
489 {
490 endIndex++;
491 }
492
493 beginIndex = endIndex;
494 if (beginIndex >= size)
495 {
496 // Quit
497 break;
498 }
499
500 // Search for next PenUpMarker
501 while (endIndex < size && !PRC_IsPenUpMarker(&inputPoints[endIndex]))
502 {
503 endIndex++;
504 }
505 if (endIndex < size)
506 {
507 selectedPoints[selectedPointNum] = endIndex;
508 selectedPointNum++; // Select required PenUpMarker
509 }
510 else
511 {
512 selectedPoints[selectedPointNum] = (u16)-1;
513 selectedPointNum++; // -1 is specially reserved to indicate the final PenUpMarker
514 }
515
516 SDK_ASSERT(endIndex > 0);
517 selectedPoints[selectedPointNum] = beginIndex;
518 selectedPointNum++;
519 selectedPoints[selectedPointNum] = (u16)(endIndex - 1);
520 selectedPointNum++;
521
522 strokeCount++; // strokeCount is only counted for the sake of limiting it with maxStrokeCount
523
524 if (selectedPointNum >= maxPointCount)
525 {
526 // Number of vertices is at the limit
527 break;
528 }
529
530 if (endIndex - beginIndex <= 2)
531 continue;
532
533 // Using the stack, recursively extract characteristic points
534 stackP1[0] = beginIndex;
535 stackP2[0] = (u16)(endIndex - 1);
536 stackSize = 1;
537 stackTop = 0;
538 stackTail = 1;
539 while (stackSize > 0)
540 {
541 u16 p1, p2;
542 int x1, y1, x2, y2, xDir, yDir, offs;
543 int lastX, lastY;
544 int i;
545 int maxDist;
546 u16 maxP;
547
548 p1 = stackP1[stackTop];
549 p2 = stackP2[stackTop];
550 stackTop++;
551 if (stackTop >= maxPointCount)
552 {
553 stackTop = 0;
554 }
555 stackSize--; // pop
556
557 if (p2 - p1 <= 1)
558 continue;
559
560 x1 = inputPoints[p1].x; // Starting point
561 y1 = inputPoints[p1].y;
562 x2 = inputPoints[p2].x; // End point
563 y2 = inputPoints[p2].y;
564 xDir = x2 - x1; // Direction vector
565 yDir = y2 - y1;
566 offs = -(x1 * y2 - x2 * y1); // Items bundled together in order to reduce the amount of calculation.
567
568 maxDist = -1;
569 maxP = (u16)-1;
570 lastX = -1;
571 lastY = -1;
572 for (i = p1 + 1; i < p2; i++)
573 {
574 int dist;
575 int x, y;
576 x = inputPoints[i].x;
577 y = inputPoints[i].y;
578
579 if (lastX == x && lastY == y)
580 continue;
581 lastX = x;
582 lastY = y;
583
584 // Calculate the distance between the straight line and the point
585 // The actual value is the original distance multiplied by the distance from the start point to end point
586 dist = x * yDir - y * xDir + offs;
587 if (dist < 0)
588 {
589 dist = -dist;
590 }
591
592 if (maxDist < dist)
593 {
594 maxP = (u16)i;
595 maxDist = dist;
596 }
597 }
598
599 // Because [maxDist == 0] in cases where the start coordinates and end coordinates exactly match, it would be preferable if the 'dist' calculation separately found the Euclidean distance between (x, y) and the start point, but because we don't want to introduce special processing for rare cases, try coding so that [p1+1] is always used when [maxDist==0] and [maxP==p1+1]. (Note that [xDir*xDir+yDir*yDir == 0] at such times.)
600 //
601 //
602 //
603 if (maxDist * maxDist >= (xDir * xDir + yDir * yDir) * squaredThreshold)
604 {
605 // Adopt points located at or outside the threshold as characteristic points
606 // Note that maxDist was the original distance multiplied by the distance from the start point to end point.
607 selectedPoints[selectedPointNum] = maxP;
608 selectedPointNum++;
609 stackP1[stackTail] = maxP;
610 stackP2[stackTail] = p2;
611 stackTail++;
612 if (stackTail >= maxPointCount)
613 {
614 stackTail = 0;
615 }
616 stackSize++; // push
617 stackP1[stackTail] = p1;
618 stackP2[stackTail] = maxP;
619 stackTail++;
620 if (stackTail >= maxPointCount)
621 {
622 stackTail = 0;
623 }
624 stackSize++; // push
625 SDK_ASSERT(stackSize <= maxPointCount);
626 if (selectedPointNum >= maxPointCount)
627 {
628 // Number of vertices is at the limit
629 break;
630 }
631 }
632 }
633 }
634
635 *pSelectedPointNum = selectedPointNum;
636
637 //{OSTick start, end; start = OS_GetTick();
638 // Sort in ascending order before returning
639 // To Do: Examine to what degree it is sped up by quick sort
640 {
641 int i, j;
642 for (i = 0; i < selectedPointNum - 1; i++)
643 {
644 for (j = i + 1; j < selectedPointNum; j++)
645 {
646 if (selectedPoints[i] > selectedPoints[j])
647 {
648 u16 tmp;
649 tmp = selectedPoints[i];
650 selectedPoints[i] = selectedPoints[j];
651 selectedPoints[j] = tmp;
652 }
653 }
654 }
655 }
656 //end = OS_GetTick(); OS_Printf("// sort in resample: %lld��s selectedPointNum=%d\n", OS_TicksToMicroSeconds(end-start), selectedPointNum); }
657 return (*pSelectedPointNum > 0);
658 }
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682 /*===========================================================================*
683 Static Functions
684 *===========================================================================*/
685
686
687 /*---------------------------------------------------------------------------*
688 End of file
689 *---------------------------------------------------------------------------*/
690