Optimize QuadF's PointIsInTriangle function

ui/gfx/geometry/quad_f.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "ui/gfx/geometry/quad_f.h"
 
 #include <limits>
 
 #include "base/strings/stringprintf.h"
 
@@ skipping 44 matching lines @@
   double determinant4 = static_cast<double>(p4_.x()) * p1_.y()
       - static_cast<double>(p1_.x()) * p4_.y();
 
   return determinant1 + determinant2 + determinant3 + determinant4 < 0;
 }
 
 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.
+  // 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 r31 = r1 - r3;
-  Vector2dF r32 = r2 - r3;
-  Vector2dF r3p = point - r3;
+  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)
 
-  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;
+  // 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;
 
-  // Use the barycentric coordinates to test if |point| is inside the
-  // triangle (r1, r2, r2).
-  return (u >= 0) && (v >= 0) && (w >= 0);
+  return true;
 }
 
 bool QuadF::Contains(const PointF& point) const {
   return PointIsInTriangle(point, p1_, p2_, p3_)
       || PointIsInTriangle(point, p1_, p3_, p4_);
 }
 
 void QuadF::Scale(float x_scale, float y_scale) {
   p1_.Scale(x_scale, y_scale);
   p2_.Scale(x_scale, y_scale);
@@ skipping 21 matching lines @@
   return result;
 }
 
 QuadF operator-(const QuadF& lhs, const Vector2dF& rhs) {
   QuadF result = lhs;
   result -= rhs;
   return result;
 }
 
 }  // namespace gfx