Optimize QuadF's PointIsInTriangle function

ui/gfx/geometry/quad_f.cc

Index: ui/gfx/geometry/quad_f.cc
diff --git a/ui/gfx/geometry/quad_f.cc b/ui/gfx/geometry/quad_f.cc
index dbc50458b3fa1e04aedfdee3c51d5ae00351b46a..0c8473c3e3eb262c98cd53fe0aa184e8b670534b 100644
--- a/ui/gfx/geometry/quad_f.cc
+++ b/ui/gfx/geometry/quad_f.cc
@@ -62,24 +62,31 @@ static inline bool PointIsInTriangle(const PointF& point,
                                      const PointF& r1,
                                      const PointF& r2,
                                      const PointF& r3) {
-  // Compute the barycentric coordinates (u, v, w) of |point| relative to the
-  // triangle (r1, r2, r3) by the solving the system of equations:
-  //   1) point = u * r1 + v * r2 + w * r3
-  //   2) u + v + w = 1
-  // This algorithm comes from Christer Ericson's Real-Time Collision Detection.
-
-  Vector2dF r31 = r1 - r3;
-  Vector2dF r32 = r2 - r3;
-  Vector2dF r3p = point - r3;
-
-  float denom = r32.y() * r31.x() - r32.x() * r31.y();
-  float u = (r32.y() * r3p.x() - r32.x() * r3p.y()) / denom;
-  float v = (r31.x() * r3p.y() - r31.y() * r3p.x()) / denom;
-  float w = 1.f - u - v;
-
-  // Use the barycentric coordinates to test if |point| is inside the
-  // triangle (r1, r2, r2).
-  return (u >= 0) && (v >= 0) && (w >= 0);
+  // Translate point and triangle so that point lies at origin.
+  // Then checking if the origin is contained in the translated triangle.
+  // The origin O lies inside ABC if and only if the triangles OAB, OBC,
+  // and OCA are all either clockwise or counterclockwise.
+  // This algorithm is from Christer Ericson's Real-Time Collision Detection.
+
+  Vector2dF a = r1 - point;
+  Vector2dF b = r2 - point;
+  Vector2dF c = r3 - point;
+  // Quick test doubles have same sign

[danakj, 2014/08/11 14:09:26]

style nit: comments should be full sentences including periods, here and below.

[kui.zheng, 2014/08/14 06:44:17]

Remove comments due to algorithm is updated

+  #define DOUBLE_SIGN_MASK UINT64_C(0x8000000000000000)

[danakj, 2014/08/11 14:09:26]

Can you use "static const uint64 kDoubleSignMask" instead?

[kui.zheng, 2014/08/14 06:44:16]

Remove "Mask" due to algorithm is updated

+  #define DOUBLE_SAME_SIGN(d1, d2) \

[danakj, 2014/08/11 14:09:26]

Is the performance changed if you use a static method to do this? With some
temporary uint64 vars to make it easier to read?

[kui.zheng, 2014/08/14 06:44:16]

Compiler should help inlining *short* static method, So, I don't think
performance would be changed. 
For this case, Remove "Micro" due to algorithm is updated.

+      (((reinterpret_cast<__uint64_t&>(d1)) ^ \

[danakj, 2014/08/11 14:09:26]

i think the extra () around the reinterpret_cast makes this harder to read/count
braces.

[kui.zheng, 2014/08/14 06:44:17]

Same as above.

+      (reinterpret_cast<__uint64_t&>(d2))) & \

[danakj, 2014/08/11 14:09:26]

Is doing XOR and AND really all that better than doing >= 0? I don't see either
of these operations listed in your analysis of changes to the method.

[kui.zheng, 2014/08/14 06:44:16]

The micro-bench(on armv7) result shows manual "XOR and AND MASK" is ~30% faster
than this method - "if (u>0 && v<0) || (u<0 && v>0)" for this case. But, Manual
"XOR and AND MASK" is not a good way because there is a standard function -
"std::signbit()".

For the algorithm about testing PointIsInTriangle, Testing Sign bit is
insufficient Sometimes. Considering one point is on the edge of triangle, we may
get Positive zero or Negative Zero after CrossProduct. In this case, the sign
bit doesn't make sense. I had updated algorithm.

+      DOUBLE_SIGN_MASK)
+
+  // Normal vectors of triangles obc and oca
+  double u = CrossProduct(b, c);
+  double v = CrossProduct(c, a);
+  if(DOUBLE_SAME_SIGN(u, v)) return false;

[danakj, 2014/08/11 14:09:26]

This is checking if they have different signs not the same sign right? It
returns true if they are different signs. Can the name reflect that?

[kui.zheng, 2014/08/14 06:44:16]

Oh yes, it's really a bad name.
The Macro would be removed due to updated algorithm.

+  // Normal vector of triangle oab
+  double w = CrossProduct(a, b);
+  if(DOUBLE_SAME_SIGN(u, w)) return false;
+
+  return true;
 }
 
 bool QuadF::Contains(const PointF& point) const {