Commit f9434dba81a08ee20822c68133b463209db5c65b
2013-02-19T21:27:18
[base] New bisecting BBox_Cubic_Check (disabled). * src/base/ftbbox.c (BBox_Cubic_Check): New bisecting algorithm for extremum search built around simple condition that defines which half contains the extremum.
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 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167
diff --git a/ChangeLog b/ChangeLog
index fa62a29..8403ab9 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,11 @@
+2013-02-19 Alexei Podtelezhnikov <apodtele@gmail.com>
+
+ [base] New bisecting BBox_Cubic_Check (disabled).
+
+ * src/base/ftbbox.c (BBox_Cubic_Check): New bisecting algorithm
+ for extremum search built around simple condition that defines
+ which half contains the extremum.
+
2013-02-18 Alexei Podtelezhnikov <apodtele@gmail.com>
[tools] Update BBox testing tool.
diff --git a/src/base/ftbbox.c b/src/base/ftbbox.c
index 7d44023..8a240ef 100644
--- a/src/base/ftbbox.c
+++ b/src/base/ftbbox.c
@@ -222,65 +222,100 @@
FT_Pos* min,
FT_Pos* max )
{
- FT_Pos stack[32*3 + 1], *arc;
+ FT_Pos q1, q2, q3, q4;
- arc = stack;
+ q1 = p1;
+ q2 = p2;
+ q3 = p3;
+ q4 = p4;
- arc[0] = p1;
- arc[1] = p2;
- arc[2] = p3;
- arc[3] = p4;
-
- do
+ /* for a conic segment to possibly reach new maximum */
+ /* one of its off-points must be above the current value */
+ while ( q2 > *max || q3 > *max )
{
- FT_Pos y1 = arc[0];
- FT_Pos y2 = arc[1];
- FT_Pos y3 = arc[2];
- FT_Pos y4 = arc[3];
-
-
- if ( y1 == y4 )
+ /* determine which half contains the maximum and split */
+ if ( q1 + q2 > q3 + q4 ) /* first half */
{
- if ( y1 == y2 && y1 == y3 ) /* flat */
- goto Test;
+ q4 = q4 + q3;
+ q3 = q3 + q2;
+ q2 = q2 + q1;
+ q4 = q4 + q3;
+ q3 = q3 + q2;
+ q4 = ( q4 + q3 ) / 8;
+ q3 = q3 / 4;
+ q2 = q2 / 2;
}
- else if ( y1 < y4 )
+ else /* second half */
{
- if ( y2 >= y1 && y2 <= y4 && y3 >= y1 && y3 <= y4 ) /* ascending */
- goto Test;
+ q1 = q1 + q2;
+ q2 = q2 + q3;
+ q3 = q3 + q4;
+ q1 = q1 + q2;
+ q2 = q2 + q3;
+ q1 = ( q1 + q2 ) / 8;
+ q2 = q2 / 4;
+ q3 = q3 / 2;
}
- else
+
+ /* check if either end reached the maximum */
+ if ( q1 == q2 && q1 >= q3 )
{
- if ( y2 >= y4 && y2 <= y1 && y3 >= y4 && y3 <= y1 ) /* descending */
- {
- y2 = y1;
- y1 = y4;
- y4 = y2;
- goto Test;
- }
+ *max = q1;
+ break;
}
+ if ( q3 == q4 && q2 <= q4 )
+ {
+ *max = q4;
+ break;
+ }
+ }
- /* unknown direction -- split the arc in two */
- arc[6] = y4;
- arc[1] = y1 = ( y1 + y2 ) / 2;
- arc[5] = y4 = ( y4 + y3 ) / 2;
- y2 = ( y2 + y3 ) / 2;
- arc[2] = y1 = ( y1 + y2 ) / 2;
- arc[4] = y4 = ( y4 + y2 ) / 2;
- arc[3] = ( y1 + y4 ) / 2;
-
- arc += 3;
- goto Suite;
+ q1 = p1;
+ q2 = p2;
+ q3 = p3;
+ q4 = p4;
- Test:
- if ( y1 < *min ) *min = y1;
- if ( y4 > *max ) *max = y4;
- arc -= 3;
+ /* for a conic segment to possibly reach new minimum */
+ /* one of its off-points must be below the current value */
+ while ( q2 < *min || q3 < *min )
+ {
+ /* determine which half contains the minimum and split */
+ if ( q1 + q2 < q3 + q4 ) /* first half */
+ {
+ q4 = q4 + q3;
+ q3 = q3 + q2;
+ q2 = q2 + q1;
+ q4 = q4 + q3;
+ q3 = q3 + q2;
+ q4 = ( q4 + q3 ) / 8;
+ q3 = q3 / 4;
+ q2 = q2 / 2;
+ }
+ else /* second half */
+ {
+ q1 = q1 + q2;
+ q2 = q2 + q3;
+ q3 = q3 + q4;
+ q1 = q1 + q2;
+ q2 = q2 + q3;
+ q1 = ( q1 + q2 ) / 8;
+ q2 = q2 / 4;
+ q3 = q3 / 2;
+ }
- Suite:
- ;
- } while ( arc >= stack );
+ /* check if either end reached the minimum */
+ if ( q1 == q2 && q1 <= q3 )
+ {
+ *min = q1;
+ break;
+ }
+ if ( q3 == q4 && q2 >= q4 )
+ {
+ *min = q4;
+ break;
+ }
+ }
}
#else