Commit 1a9c3d14fbc068671480eb4b4d4e66620b366d8f
2013-08-15T22:51:42
[base] Finish experimental (disabled) BBox_Cubic_Check implementation. * src/base/ftbbox.c (BBox_Cubic_Check): Scale arguments to improve accuracy and avoid overflows.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104
diff --git a/ChangeLog b/ChangeLog
index dc12dd1..0098354 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,9 +1,17 @@
+2013-08-15 Alexei Podtelezhnikov <apodtele@gmail.com>
+
+ [base] Finish experimental (disabled) BBox_Cubic_Check implementation.
+
+ * src/base/ftbbox.c (BBox_Cubic_Check): Scale arguments to improve
+ accuracy and avoid overflows.
+
2013-08-13 Alexei Podtelezhnikov <apodtele@gmail.com>
[base] Refactor experimental (disabled) BBox_Cubic_Check.
* src/base/ftbbox.c (BBox_Cubic_Check): Implement the minimum search
- as the mirror image of the maximum search.
+ as the mirror image of the maximum search implemented here...
+ (update_max): New function.
2013-08-06 John Tytgat <John.Tytgat@esko.com>
diff --git a/src/base/ftbbox.c b/src/base/ftbbox.c
index ca53dd8..3fe0a7d 100644
--- a/src/base/ftbbox.c
+++ b/src/base/ftbbox.c
@@ -275,10 +275,62 @@
FT_Pos* min,
FT_Pos* max )
{
- *max = update_max( p1, p2, p3, p4, *max );
+ FT_Pos nmin, nmax;
+ FT_Int shift;
+
+ /* This implementation relies on iterative bisection of the segment. */
+ /* The fixed-point arithmentic of bisection is inherently stable but */
+ /* may loose accuracy in the two lowest bits. To compensate, we */
+ /* upscale the segment if there is room. Large values may need to be */
+ /* downscaled to avoid overflows during bisection bisection. This */
+ /* function is only called when a control off-point is outside the */
+ /* the bbox and, thus, has the top absolute value among arguments. */
+
+ shift = 27 - FT_MSB( FT_ABS( p2 ) | FT_ABS( p3 ) );
+
+ if ( shift > 0 )
+ {
+ /* upscaling too much just wastes time */
+ if ( shift > 2 )
+ shift = 2;
+
+ p1 <<= shift;
+ p2 <<= shift;
+ p3 <<= shift;
+ p4 <<= shift;
+ nmin = *min << shift;
+ nmax = *max << shift;
+ }
+ else
+ {
+ p1 >>= -shift;
+ p2 >>= -shift;
+ p3 >>= -shift;
+ p4 >>= -shift;
+ nmin = *min >> -shift;
+ nmax = *max >> -shift;
+ }
+
+ nmax = update_max( p1, p2, p3, p4, nmax );
/* now flip the signs to update the minimum */
- *min = -update_max( -p1, -p2, -p3, -p4, -*min );
+ nmin = -update_max( -p1, -p2, -p3, -p4, -nmin );
+
+ if ( shift > 0 )
+ {
+ nmin >>= shift;
+ nmax >>= shift;
+ }
+ else
+ {
+ nmin <<= -shift;
+ nmax <<= -shift;
+ }
+
+ if ( nmin < *min )
+ *min = nmin;
+ if ( nmax > *max )
+ *max = nmax;
}
#else
@@ -482,8 +534,9 @@
FT_Vector* to,
TBBox_Rec* user )
{
- /* we don't need to check `to' since it is always an `on' point, thus */
- /* within the bbox */
+ /* We don't need to check `to' since it is always an on-point, */
+ /* thus within the bbox. Only segments with an off-point outside */
+ /* the bbox can possibly reach new extreme values. */
if ( CHECK_X( control1, user->bbox ) ||
CHECK_X( control2, user->bbox ) )