Optimize QuadF's PointIsInTriangle function

Optimize QuadF's PointIsInTriangle function

The original version required 34 float ops (16mul + 11sub + 5add + 2div).
This version removes some of the intermediate dot products, reducing the
max number of operations to 19 (6mul + 2div + 11sub).  It also avoids using
doubles, warranted by the removal of several intermediate operations that might
otherwise incur significance loss.

In local (release build) benchmarks, this reduced the typical CPU cost of a call to
QuadF::Contains(...) by 2/3, both with GCC and Clang on an ARM v7 device.

Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=271088

[jdduke (slow), 2014-05-15 20:04:07]

danakj@: PTAL.  I'm hoping the elimination of the intermediate operations
lessens the need for double precision, but let me know if you think otherwise.

[danakj, 2014-05-16 15:43:43]

https://codereview.chromium.org/291493003/diff/20001/ui/gfx/geometry/quad_f.cc
File ui/gfx/geometry/quad_f.cc (right):

https://codereview.chromium.org/291493003/diff/20001/ui/gfx/geometry/quad_f.c...
ui/gfx/geometry/quad_f.cc:66: // (r1, r2, r3). This algorithm comes from
Christer Ericson's Real-Time
Can you update this comment with a citation on the algorithm?

[jdduke (slow), 2014-05-16 16:49:46]

https://codereview.chromium.org/291493003/diff/20001/ui/gfx/geometry/quad_f.cc
File ui/gfx/geometry/quad_f.cc (right):

https://codereview.chromium.org/291493003/diff/20001/ui/gfx/geometry/quad_f.c...
ui/gfx/geometry/quad_f.cc:66: // (r1, r2, r3). This algorithm comes from
Christer Ericson's Real-Time
On 2014/05/16 15:43:44, danakj wrote:
> Can you update this comment with a citation on the algorithm?

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]

LGTM

https://codereview.chromium.org/291493003/diff/20001/ui/gfx/geometry/quad_f.cc
File ui/gfx/geometry/quad_f.cc (right):

https://codereview.chromium.org/291493003/diff/20001/ui/gfx/geometry/quad_f.c...
ui/gfx/geometry/quad_f.cc:66: // (r1, r2, r3). This algorithm comes from
Christer Ericson's Real-Time
On 2014/05/16 16:49:47, jdduke wrote:
> On 2014/05/16 15:43:44, danakj wrote:
> > Can you update this comment with a citation on the algorithm?
> 
> 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?

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

[danakj, 2014-05-16 17:02:53]

Previously we were multiplying 2 floats as doubles to find the DotProduct, then
multiplying the dot products, causing us to lose up to half the bits of the
doubles.

Now we just multiply two floats as floats, also causing us to lose up to half
the bits, which puts us in a similar place, I believe.

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

https://codereview.chromium.org/291493003/diff/20001/ui/gfx/geometry/quad_f.cc
File ui/gfx/geometry/quad_f.cc (right):

https://codereview.chromium.org/291493003/diff/20001/ui/gfx/geometry/quad_f.c...
ui/gfx/geometry/quad_f.cc:66: // (r1, r2, r3). This algorithm comes from
Christer Ericson's Real-Time
On 2014/05/16 17:01:48, danakj wrote:
> On 2014/05/16 16:49:47, jdduke wrote:
> > On 2014/05/16 15:43:44, danakj wrote:
> > > Can you update this comment with a citation on the algorithm?
> > 
> > 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?
> 
> Ahhh yeh ok, showing the equation we're solving sounds nice :)

Done.

[jdduke (slow), 2014-05-16 17:30:35]

The CQ bit was checked by jdduke@chromium.org

[commit-bot: I haz the power, 2014-05-16 17:31:09]

CQ is trying da patch. Follow status at
 https://chromium-status.appspot.com/cq/jdduke@chromium.org/291493003/40001

[commit-bot: I haz the power, 2014-05-16 20:13:57]

Change committed as 271088