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 45 matching lines @@
       - 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 of |point| relative to the triangle
   // (r1, r2, r3). This algorithm comes from Christer Ericson's Real-Time

[danakj, 2014/05/16 15:43:44]

Can you update this comment with a citation on the algorithm?

[jdduke (slow), 2014/05/16 16:49:47]

Hmm, the algorithm is the same (barycentric coords), just with a streamlined
computation. I could write the formula for which this is the solution, e.g.,:

px = u * r1x + v * r2x + w * r3x
py = u * r1y + v * r2y + w * r3y
u + v + w = 1

or I could link to a resource that shows a similar computation:
http://totologic.blogspot.fr/2014/01/accurate-point-in-triangle-test.html ?
Preference?

[danakj, 2014/05/16 17:01:48]

Ahhh yeh ok, showing the equation we're solving sounds nice :)

[jdduke (slow), 2014/05/16 17:30:32]

Done.

   // Collision Detection.
-  Vector2dF v0 = r2 - r1;
-  Vector2dF v1 = r3 - r1;
-  Vector2dF v2 = point - r1;
+  Vector2dF r31 = r1 - r3;
+  Vector2dF r32 = r2 - r3;
+  Vector2dF r3p = point - r3;
 
-  double dot00 = DotProduct(v0, v0);
-  double dot01 = DotProduct(v0, v1);
-  double dot11 = DotProduct(v1, v1);
-  double dot20 = DotProduct(v2, v0);
-  double dot21 = DotProduct(v2, v1);
-
-  double denom = dot00 * dot11 - dot01 * dot01;
-
-  double v = (dot11 * dot20 - dot01 * dot21) / denom;
-  double w = (dot00 * dot21 - dot01 * dot20) / denom;
-  double u = 1 - v - w;
+  float denom = r32.y() * r31.x() - r32.x() * r31.y();
+  float v = (r32.y() * r3p.x() - r32.x() * r3p.y()) / denom;
+  float w = (r31.x() * r3p.y() - r31.y() * r3p.x()) / denom;
+  float u = 1.f - v - w;
 
   // Use the barycentric coordinates to test if |point| is inside the
   // triangle (r1, r2, r2).
   return (v >= 0) && (w >= 0) && (u >= 0);
 }
 
 bool QuadF::Contains(const PointF& point) const {
   return PointIsInTriangle(point, p1_, p2_, p3_)
       || PointIsInTriangle(point, p1_, p3_, p4_);
 }
@@ skipping 25 matching lines @@
   return result;
 }
 
 QuadF operator-(const QuadF& lhs, const Vector2dF& rhs) {
   QuadF result = lhs;
   result -= rhs;
   return result;
 }
 
 }  // namespace gfx