[truetype] Cheaper way to threshold angles between vectors. * src/truetype/ttinterp.c (Ins_ISECT): Thresholding tangent is a lot cheaper than thresholding sine.
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
diff --git a/ChangeLog b/ChangeLog
index c7d401e..3e92e6f 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,10 @@
+2012-10-20 Alexei Podtelezhnikov <apodtele@gmail.com>
+
+ [truetype] Cheaper way to threshold angles between vectors.
+
+ * src/truetype/ttinterp.c (Ins_ISECT): Thresholding tangent is a lot
+ cheaper than thresholding sine.
+
2012-10-20 Werner Lemberg <wl@gnu.org>
[cff] Improve parsing of invalid real numbers.
diff --git a/src/truetype/ttinterp.c b/src/truetype/ttinterp.c
index 41f77cd..765d323 100644
--- a/src/truetype/ttinterp.c
+++ b/src/truetype/ttinterp.c
@@ -6835,15 +6835,12 @@
a0, a1,
b0, b1;
- FT_F26Dot6 discriminant;
+ FT_F26Dot6 discriminant, dotproduct;
FT_F26Dot6 dx, dy,
dax, day,
dbx, dby;
- FT_F26Dot6 len_a, len_b;
- FT_Long sine;
-
FT_F26Dot6 val;
FT_Vector R;
@@ -6882,34 +6879,18 @@
discriminant = TT_MULDIV( dax, -dby, 0x40 ) +
TT_MULDIV( day, dbx, 0x40 );
-
- /* Let */
- /* */
- /* a = vector(a0, a1) */
- /* b = vector(b0, b1) . */
- /* */
- /* Then */
- /* */
- /* dot_product(normal_vector(a), b) */
- /* = discriminant */
- /* = |a| * |b| * sin(alpha) . */
-
- len_a = TT_VecLen( dax, day );
- len_b = TT_VecLen( dbx, dby );
-
- if ( len_a && len_b )
- {
- /* precision: (F.6 * F.16) / F.6 = F.16 */
- sine = FT_DivFix( discriminant, len_a );
- /* precision: (F.16 * F.16) / F.6 = F.26 */
- sine = FT_DivFix( sine, len_b );
- }
- else
- sine = 0;
-
- /* We reject grazing intersections; heuristic value 2342066 */
- /* corresponds to arcsin(2342066/2^26), this is approx 2 degrees. */
- if ( FT_ABS( sine ) >= 2342066 )
+ dotproduct = TT_MULDIV( dax, dbx, 0x40 ) +
+ TT_MULDIV( day, dby, 0x40 );
+
+ /* The discriminant above is actually a cross product of vectors */
+ /* da and db. Together with the dot product, they can be used as */
+ /* surrogates for sine and cosine of the angle between the vectors. */
+ /* Indeed, */
+ /* dotproduct = |da||db|cos(angle) */
+ /* discriminant = |da||db|sin(angle) . */
+ /* We use these equations to reject grazing intersections by */
+ /* thresholding abs(tan(angle)) at 1/19, corresponding to 3 degrees. */
+ if ( 19 * FT_ABS( discriminant ) > FT_ABS( dotproduct ) )
{
val = TT_MULDIV( dx, -dby, 0x40 ) + TT_MULDIV( dy, dbx, 0x40 );