Add base types for path ops

Add base types for path ops

Paths contain lines, quads, and cubics, which are
collectively curves.

To work with path intersections, intermediary curves
are constructed. For now, those intermediates use
doubles to guarantee sufficient precision.

The DVector, DPoint, DLine, DQuad, and DCubic
structs encapsulate these intermediate curves.

The DRect and DTriangle structs are created to
describe intersectable areas of interest.

The Bounds struct inherits from SkRect to create
a SkScalar-based rectangle that intersects shared
edges.

This also includes common math equalities and
debugging that the remainder of path ops builds on,
as well as a temporary top-level interface in
include/pathops/SkPathOps.h.
Committed: https://code.google.com/p/skia/source/detail?r=8551

[caryclark, 2013-03-22 15:44:25]

First cut at base types for path ops. If this is too onerous, I can split this
into smaller reviews.

[reed1, 2013-03-22 15:58:04]

If you have any headers that are destined for the public, lets add those to
include/pathops/ for now, just to make it clear to reviewers.

some initial comments/questions.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
File src/pathops/SkPathOpsBounds.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:35: void add(const SkPathOpsBounds& toAdd) {
this, and add(point), could likely be added to SkRect, since they look generic.
Perhaps a comment to that effect for now?

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:46: bool isEmpty() {
const?

Can we find a different name, since this one directly matches/hides one on
SkRect with diff semantics?

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:49: || sk_double_isnan(fLeft) ||
sk_double_isnan(fRight)
fLeft is SkScalar, not double. Should we use SkScalarIsNaN?

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:57: void setPoint(const SkPoint& pt) {
Crazy suggestion: setPointBounds (like the above methods)?

[whunt, 2013-03-22 18:16:06]

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
File src/pathops/SkPathOpsBounds.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:20: void add(SkScalar left, SkScalar top, SkScalar
right, SkScalar bottom) {
add is a very overloaded word.  I'd recommend "Union" in this case as you are
unioning a new point into a point set.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:21: if (left < fLeft) {
Use std::min and std::max. In 64 bit mode and any platform that assumes SSE
you'll get the scalar SSE min/max operations witch are *way* faster than
branches.
https://uma.googleplex.com/histograms/?dayCount=28&endDate=03-21-2013&version...

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:47: return fLeft > fRight || fTop > fBottom
the implementation should be:
!(fLeft < fRight && fTop < fBottom)
this will catch all cases you have here

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsCubi...
File src/pathops/SkPathOpsCubic.cpp (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsCubi...
src/pathops/SkPathOpsCubic.cpp:113: static const double PI = 4 * atan(1);
Is this allowed in skia?  In chromium statics be initialized with functions. 
You may just want to drop in the constant.
3.14159265359

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsCubic.h
File src/pathops/SkPathOpsCubic.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsCubi...
src/pathops/SkPathOpsCubic.h:32: const SkDPoint& operator[](int n) const {
return fPts[n]; }
DCHECK/assert n < 4

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsCubi...
src/pathops/SkPathOpsCubic.h:33: SkDPoint& operator[](int n) { return fPts[n]; }
DCHECK/assert n < 4

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
File src/pathops/SkPathOpsPoint.cpp (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
src/pathops/SkPathOpsPoint.cpp:9: SkDVector operator-(const SkDPoint& a, const
SkDPoint& b) {
This function should be inlined.  If the rational for not inlining it is code
size you'll find that pushing the operators and making the function call are
actually more code bytes than the subtracts.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
src/pathops/SkPathOpsPoint.cpp:10: SkDVector v = {a.fX - b.fX, a.fY - b.fY};
you'll bet better code with a constructor

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
src/pathops/SkPathOpsPoint.cpp:14: SkDPoint operator+(const SkDPoint& a, const
SkDVector& b) {
This function should be inlined.  If the rational for not inlining it is code
size you'll find that pushing the operators and making the function call are
actually more code bytes than the adds.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
src/pathops/SkPathOpsPoint.cpp:15: SkDPoint v = {a.fX + b.fX, a.fY + b.fY};
you'll bet better code with a constructor

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoint.h
File src/pathops/SkPathOpsPoint.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
src/pathops/SkPathOpsPoint.h:38: SkVector asSkVector() const {
for reasons I'm not entirely clear on, many compilers I've tested do not
generate optimal code when using this pattern.  For optimal performance having a
constructor for SkVector and implement the function as:
return SkVector(SkDoubleToScalar(fX), SkDoubleToScalar(fY));

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
src/pathops/SkPathOpsPoint.h:79: void operator=(const SkPoint& pt) {
don't implement this, the compiler will do at least as well

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
src/pathops/SkPathOpsPoint.h:133: SkPoint pt = {SkDoubleToScalar(fX),
SkDoubleToScalar(fY)};
Again, the compiler will produce better code with a constructor.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsRect.h
File src/pathops/SkPathOpsRect.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsRect...
src/pathops/SkPathOpsRect.h:15: void add(const SkDPoint& pt) {
add is a very overloaded name, I'd recommend "Union" (this is essentially a set
operation)

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsRect...
src/pathops/SkPathOpsRect.h:16: if (fLeft > pt.fX) {
Use std::min and std::max. In 64 bit mode and any platform that assumes SSE
you'll get the scalar SSE min/max operations witch are *way* faster than
branches.
https://uma.googleplex.com/histograms/?dayCount=28&endDate=03-21-2013&version...

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsTria...
File src/pathops/SkPathOpsTriangle.cpp (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsTria...
src/pathops/SkPathOpsTriangle.cpp:30: return (u >= 0) && (v >= 0) && (u + v <
1);
should be u + v <= 1 if you want to include all three edges. (It's perfectly
reasonable for the 3rd bary to be 0)

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsType...
File src/pathops/SkPathOpsTypes.cpp (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsType...
src/pathops/SkPathOpsTypes.cpp:17: bool negative() const { return (fInt >> 31)
!= 0; }
why not just compute (fInt < 0)?

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsType...
src/pathops/SkPathOpsTypes.cpp:26: // Check for equality to make sure +0==-0
0 ==

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsType...
src/pathops/SkPathOpsTypes.cpp:41: pt[1]=px[1]/3+B1;
spaces around the ops?

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsType...
src/pathops/SkPathOpsTypes.cpp:48: const double b= a * (a3 + R + R) / (a3 + a3 +
R);
b =

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsTypes.h
File src/pathops/SkPathOpsTypes.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsType...
src/pathops/SkPathOpsTypes.h:19: if (a < b)
min and max can be performance critical operations.  I'd really recommend using
std::min and std::max in the general case if you can help it as that compiler is
mostly likely to recognize those and produce optimal code.  If SSE is enabled
you really want something like (for double):
_mm_cvtsd_f64(_mm_max_sd(_mm_set_sd(a), _mm_set_sd(b)))
although to be honest this sequence is not as efficient as it could be because
_mm_set_sd has the semantic of clearing the high bits of the SSE register even
though we don't actually need it to.  Because the double registers and SSE
registers are are the same the conversations are noops.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsType...
src/pathops/SkPathOpsTypes.h:251: return 1 >> 3 - (one ^ two) ^ 3;
I believe:
((one ^ two) & 1) + 1
will yield you the same result in fewer ops.  The existing solution should be 5
ops: two xor, one sub, one shift and one mov (to set the 1 that gets shifted). 
This solution should be 3: xor, and and inc

requirements (by my understanding):
[0,1] = 2
[0,2] = 1
[0,3] = 1 or 2
[1,2] = 1 or 2
[1,3] = 1
[2,3] = 2

a ^ b:
[0,1] = 1
[0,2] = 2
[0,3] = 3
[1,2] = 3
[1,3] = 2
[2,3] = 1

(a ^ b) & 1:
[0,1] = 1
[0,2] = 0
[0,3] = 1
[1,2] = 1
[1,3] = 0
[2,3] = 1

((a ^ b) & 1) + 1:
[0,1] = 2
[0,2] = 1
[0,3] = 2
[1,2] = 2
[1,3] = 1
[2,3] = 2

[reed1, 2013-03-22 19:00:37]

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsCubic.h
File src/pathops/SkPathOpsCubic.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsCubi...
src/pathops/SkPathOpsCubic.h:32: const SkDPoint& operator[](int n) const {
return fPts[n]; }
On 2013/03/22 18:16:06, whunt wrote:
> DCHECK/assert n < 4

whunt: good catch. fyi -- in skia we use SkASSERT()

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoint.h
File src/pathops/SkPathOpsPoint.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
src/pathops/SkPathOpsPoint.h:38: SkVector asSkVector() const {
On 2013/03/22 18:16:06, whunt wrote:
> for reasons I'm not entirely clear on, many compilers I've tested do not
> generate optimal code when using this pattern.  For optimal performance having
a
> constructor for SkVector and implement the function as:
> return SkVector(SkDoubleToScalar(fX), SkDoubleToScalar(fY)); 

We should disassemble and check, as SkVector (and SkPoint, SkRect) do not have
constructors. We do have statics like SkPoint::Make(...)

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
src/pathops/SkPathOpsPoint.h:133: SkPoint pt = {SkDoubleToScalar(fX),
SkDoubleToScalar(fY)};
On 2013/03/22 18:16:06, whunt wrote:
> Again, the compiler will produce better code with a constructor.

Lets measure.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsRect.h
File src/pathops/SkPathOpsRect.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsRect...
src/pathops/SkPathOpsRect.h:15: void add(const SkDPoint& pt) {
On 2013/03/22 18:16:06, whunt wrote:
> add is a very overloaded name, I'd recommend "Union" (this is essentially a
set
> operation)

whunt: skia uses lower-case for method names, and 'union' would be illegal.

For better or worse, SkRect has growToInclude(x, y) ... just saying.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsTria...
File src/pathops/SkPathOpsTriangle.cpp (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsTria...
src/pathops/SkPathOpsTriangle.cpp:30: return (u >= 0) && (v >= 0) && (u + v <
1);
On 2013/03/22 18:16:06, whunt wrote:
> should be u + v <= 1 if you want to include all three edges. (It's perfectly
> reasonable for the 3rd bary to be 0)

u + v <= 1

This doesn't catch if u or v are negative. Are those still considered in the
triangle?

https://codereview.chromium.org/12827020/diff/14006/tests/PathOpsDLineTest.cpp
File tests/PathOpsDLineTest.cpp (right):

https://codereview.chromium.org/12827020/diff/14006/tests/PathOpsDLineTest.cp...
tests/PathOpsDLineTest.cpp:10: const SkDLine tests[] = {
'static' const SkDLine tests[] = {     ?

[danakj, 2013-03-22 19:11:42]

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
File src/pathops/SkPathOpsBounds.cpp (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.cpp:2: * Copyright 2012 Google Inc.
2013 everywhere

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
File src/pathops/SkPathOpsBounds.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:46: bool isEmpty() {
it seems interesting that a 0x0 area is empty but a 0x10 area is not? that
certainly is not how other geometry types in our code base work, is that going
to cause a problem?

[whunt, 2013-03-22 19:37:28]

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
File src/pathops/SkPathOpsBounds.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:46: bool isEmpty() {
On 2013/03/22 19:11:42, danakj wrote:
> it seems interesting that a 0x0 area is empty but a 0x10 area is not? that
> certainly is not how other geometry types in our code base work, is that going
> to cause a problem?

0x0 should not be empty, it should contain a point (e.g. the result of an
setPoint() call)

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:47: return fLeft > fRight || fTop > fBottom
On 2013/03/22 18:16:06, whunt wrote:
> the implementation should be:
> !(fLeft < fRight && fTop < fBottom)
> this will catch all cases you have here

revised to to account for zero area, non-empty bounds
!(fLeft <= fRight && fTop <= fBottom)

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:48: || (fLeft == fRight && fTop == fBottom)
I think this check (for single point) is wrong, see Dana's comment.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsTria...
File src/pathops/SkPathOpsTriangle.cpp (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsTria...
src/pathops/SkPathOpsTriangle.cpp:30: return (u >= 0) && (v >= 0) && (u + v <
1);
On 2013/03/22 19:00:37, reed1 wrote:
> On 2013/03/22 18:16:06, whunt wrote:
> > should be u + v <= 1 if you want to include all three edges. (It's perfectly
> > reasonable for the 3rd bary to be 0)
> 
> u + v <= 1
> 
> This doesn't catch if u or v are negative. Are those still considered in the
> triangle?

u and v can't be negative... you check for that

[caryclark, 2013-03-22 19:38:51]

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
File src/pathops/SkPathOpsBounds.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:20: void add(SkScalar left, SkScalar top, SkScalar
right, SkScalar bottom) {
On 2013/03/22 18:16:06, whunt wrote:
> add is a very overloaded word.  I'd recommend "Union" in this case as you are
> unioning a new point into a point set.

Point taken. However, union is unavailable -- Skia coding standards requires
that members are lowercase.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:21: if (left < fLeft) {
On 2013/03/22 18:16:06, whunt wrote:
> Use std::min and std::max. In 64 bit mode and any platform that assumes SSE
> you'll get the scalar SSE min/max operations witch are *way* faster than
> branches.
>
https://uma.googleplex.com/histograms/?dayCount=28&endDate=03-21-2013&version...

Certainly worth investigating. Skia uses the  'if (a op b) a = b' pattern in
some  places and 'a = max(b, c)'  in others, so it's worth making consistent.
I'd be interested to see for which compilers and platforms this is appropriate.

In any case, it's worth noting that Skia does not use std:: as a rule, but that
SkTMin and SkTMax are part of this CL.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:35: void add(const SkPathOpsBounds& toAdd) {
On 2013/03/22 15:58:04, reed1 wrote:
> this, and add(point), could likely be added to SkRect, since they look
generic.
> Perhaps a comment to that effect for now?

Done.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:46: bool isEmpty() {
On 2013/03/22 15:58:04, reed1 wrote:
> const?
> 
> Can we find a different name, since this one directly matches/hides one on
> SkRect with diff semantics?

Done. isReallyEmpty() ? (BTW, this function turns out to be unused for now.)

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:47: return fLeft > fRight || fTop > fBottom
On 2013/03/22 18:16:06, whunt wrote:
> the implementation should be:
> !(fLeft < fRight && fTop < fBottom)
> this will catch all cases you have here

Done.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:49: || sk_double_isnan(fLeft) ||
sk_double_isnan(fRight)
On 2013/03/22 15:58:04, reed1 wrote:
> fLeft is SkScalar, not double. Should we use SkScalarIsNaN?

Done.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:57: void setPoint(const SkPoint& pt) {
On 2013/03/22 15:58:04, reed1 wrote:
> Crazy suggestion: setPointBounds (like the above methods)?

Done.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsCubic.h
File src/pathops/SkPathOpsCubic.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsCubi...
src/pathops/SkPathOpsCubic.h:32: const SkDPoint& operator[](int n) const {
return fPts[n]; }
On 2013/03/22 18:16:06, whunt wrote:
> DCHECK/assert n < 4

Done.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsCubi...
src/pathops/SkPathOpsCubic.h:33: SkDPoint& operator[](int n) { return fPts[n]; }
On 2013/03/22 18:16:06, whunt wrote:
> DCHECK/assert n < 4

Done.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
File src/pathops/SkPathOpsPoint.cpp (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
src/pathops/SkPathOpsPoint.cpp:9: SkDVector operator-(const SkDPoint& a, const
SkDPoint& b) {
On 2013/03/22 18:16:06, whunt wrote:
> This function should be inlined.  If the rational for not inlining it is code
> size you'll find that pushing the operators and making the function call are
> actually more code bytes than the subtracts.

Again, I think measurement is the key. The compiler (or, more precisely, the
linker) can inline this code by itself.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
src/pathops/SkPathOpsPoint.cpp:10: SkDVector v = {a.fX - b.fX, a.fY - b.fY};
On 2013/03/22 18:16:06, whunt wrote:
> you'll bet better code with a constructor

As Mike has pointed out, Skia intentionally does not use constructors for
structs.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoint.h
File src/pathops/SkPathOpsPoint.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
src/pathops/SkPathOpsPoint.h:38: SkVector asSkVector() const {
On 2013/03/22 19:00:37, reed1 wrote:
> On 2013/03/22 18:16:06, whunt wrote:
> > for reasons I'm not entirely clear on, many compilers I've tested do not
> > generate optimal code when using this pattern.  For optimal performance
having
> a
> > constructor for SkVector and implement the function as:
> > return SkVector(SkDoubleToScalar(fX), SkDoubleToScalar(fY)); 
> 
> We should disassemble and check, as SkVector (and SkPoint, SkRect) do not have
> constructors. We do have statics like SkPoint::Make(...)

Will test and verify that this is or is not a problem.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
src/pathops/SkPathOpsPoint.h:79: void operator=(const SkPoint& pt) {
On 2013/03/22 18:16:06, whunt wrote:
> don't implement this, the compiler will do at least as well

Read it more carefully -- the types are not the same.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
src/pathops/SkPathOpsPoint.h:133: SkPoint pt = {SkDoubleToScalar(fX),
SkDoubleToScalar(fY)};
On 2013/03/22 19:00:37, reed1 wrote:
> On 2013/03/22 18:16:06, whunt wrote:
> > Again, the compiler will produce better code with a constructor.
> 
> Lets measure.

Agreed.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsRect.h
File src/pathops/SkPathOpsRect.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsRect...
src/pathops/SkPathOpsRect.h:16: if (fLeft > pt.fX) {
On 2013/03/22 18:16:06, whunt wrote:
> Use std::min and std::max. In 64 bit mode and any platform that assumes SSE
> you'll get the scalar SSE min/max operations witch are *way* faster than
> branches.

Noted. In general, it's not necessary to flag and repeat your arguments for each
additional instance of coding style choices.
>
https://uma.googleplex.com/histograms/?dayCount=28&endDate=03-21-2013&version...

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsTria...
File src/pathops/SkPathOpsTriangle.cpp (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsTria...
src/pathops/SkPathOpsTriangle.cpp:30: return (u >= 0) && (v >= 0) && (u + v <
1);
On 2013/03/22 19:00:37, reed1 wrote:
> On 2013/03/22 18:16:06, whunt wrote:
> > should be u + v <= 1 if you want to include all three edges. (It's perfectly
> > reasonable for the 3rd bary to be 0)
> 
> u + v <= 1
> 
> This doesn't catch if u or v are negative. Are those still considered in the
> triangle?

Hmm. I am only concerned with rejecting edges that are outside the triangle.
That said, this is part of a quick reject so it's hard to see when <= vs. < is
really relevant. I'll create some test cases and investigate further.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsType...
File src/pathops/SkPathOpsTypes.cpp (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsType...
src/pathops/SkPathOpsTypes.cpp:17: bool negative() const { return (fInt >> 31)
!= 0; }
On 2013/03/22 18:16:06, whunt wrote:
> why not just compute (fInt < 0)?

No reason. It's copied/pasted code. In general, I've done no performance
analysis on this code -- I've been concentrating only on completeness and
correctness.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsType...
src/pathops/SkPathOpsTypes.cpp:26: // Check for equality to make sure +0==-0
On 2013/03/22 18:16:06, whunt wrote:
> 0 ==

Done.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsType...
src/pathops/SkPathOpsTypes.cpp:41: pt[1]=px[1]/3+B1;
On 2013/03/22 18:16:06, whunt wrote:
> spaces around the ops?

Done.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsType...
src/pathops/SkPathOpsTypes.cpp:48: const double b= a * (a3 + R + R) / (a3 + a3 +
R);
On 2013/03/22 18:16:06, whunt wrote:
> b =

Done.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsTypes.h
File src/pathops/SkPathOpsTypes.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsType...
src/pathops/SkPathOpsTypes.h:19: if (a < b)
On 2013/03/22 18:16:06, whunt wrote:
> min and max can be performance critical operations.  I'd really recommend
using
> std::min and std::max in the general case if you can help it as that compiler
is
> mostly likely to recognize those and produce optimal code.  If SSE is enabled
> you really want something like (for double):
> _mm_cvtsd_f64(_mm_max_sd(_mm_set_sd(a), _mm_set_sd(b)))
> although to be honest this sequence is not as efficient as it could be because
> _mm_set_sd has the semantic of clearing the high bits of the SSE register even
> though we don't actually need it to.  Because the double registers and SSE
> registers are are the same the conversations are noops.

Noted.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsType...
src/pathops/SkPathOpsTypes.h:251: return 1 >> 3 - (one ^ two) ^ 3;
On 2013/03/22 18:16:06, whunt wrote:
> I believe:
> ((one ^ two) & 1) + 1
> will yield you the same result in fewer ops.  The existing solution should be
5
> ops: two xor, one sub, one shift and one mov (to set the 1 that gets shifted).

> This solution should be 3: xor, and and inc
> 
> requirements (by my understanding):
> [0,1] = 2
> [0,2] = 1
> [0,3] = 1 or 2
> [1,2] = 1 or 2
> [1,3] = 1
> [2,3] = 2
> 
> a ^ b:
> [0,1] = 1
> [0,2] = 2
> [0,3] = 3
> [1,2] = 3
> [1,3] = 2
> [2,3] = 1
> 
> (a ^ b) & 1:
> [0,1] = 1
> [0,2] = 0
> [0,3] = 1
> [1,2] = 1
> [1,3] = 0
> [2,3] = 1
> 
> ((a ^ b) & 1) + 1:
> [0,1] = 2
> [0,2] = 1
> [0,3] = 2
> [1,2] = 2
> [1,3] = 1
> [2,3] = 2

This function is no longer used. It's been removed.

https://codereview.chromium.org/12827020/diff/14006/tests/PathOpsDLineTest.cpp
File tests/PathOpsDLineTest.cpp (right):

https://codereview.chromium.org/12827020/diff/14006/tests/PathOpsDLineTest.cp...
tests/PathOpsDLineTest.cpp:10: const SkDLine tests[] = {
On 2013/03/22 19:00:37, reed1 wrote:
> 'static' const SkDLine tests[] = {     ?

Done.

[whunt, 2013-03-22 19:50:09]

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoint.h
File src/pathops/SkPathOpsPoint.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
src/pathops/SkPathOpsPoint.h:79: void operator=(const SkPoint& pt) {
On 2013/03/22 19:38:51, caryclark wrote:
> On 2013/03/22 18:16:06, whunt wrote:
> > don't implement this, the compiler will do at least as well
> 
> Read it more carefully -- the types are not the same.

Ahh, I see that and w/o constructors I see the necessity.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsTypes.h
File src/pathops/SkPathOpsTypes.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsType...
src/pathops/SkPathOpsTypes.h:251: return 1 >> 3 - (one ^ two) ^ 3;
On 2013/03/22 19:38:51, caryclark wrote:
> On 2013/03/22 18:16:06, whunt wrote:
> > I believe:
> > ((one ^ two) & 1) + 1
> > will yield you the same result in fewer ops.  The existing solution should
be
> 5
> > ops: two xor, one sub, one shift and one mov (to set the 1 that gets
shifted).
> 
> > This solution should be 3: xor, and and inc
> > 
> > requirements (by my understanding):
> > [0,1] = 2
> > [0,2] = 1
> > [0,3] = 1 or 2
> > [1,2] = 1 or 2
> > [1,3] = 1
> > [2,3] = 2
> > 
> > a ^ b:
> > [0,1] = 1
> > [0,2] = 2
> > [0,3] = 3
> > [1,2] = 3
> > [1,3] = 2
> > [2,3] = 1
> > 
> > (a ^ b) & 1:
> > [0,1] = 1
> > [0,2] = 0
> > [0,3] = 1
> > [1,2] = 1
> > [1,3] = 0
> > [2,3] = 1
> > 
> > ((a ^ b) & 1) + 1:
> > [0,1] = 2
> > [0,2] = 1
> > [0,3] = 2
> > [1,2] = 2
> > [1,3] = 1
> > [2,3] = 2
> 
> This function is no longer used. It's been removed.

Sad =(, it was an interesting bit-twiddling problem.

[whunt, 2013-03-22 19:52:03]

In general, what's the rational for not using constructors for these types in
Skia?  I'm happy to produce code demonstrating code improvements of using
constructors over "= {}" initialization syntax, but if efficiency wasn't the
concern it may not matter.


On 2013/03/22 19:50:09, whunt wrote:
>
https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoint.h
> File src/pathops/SkPathOpsPoint.h (right):
> 
>
https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
> src/pathops/SkPathOpsPoint.h:79: void operator=(const SkPoint& pt) {
> On 2013/03/22 19:38:51, caryclark wrote:
> > On 2013/03/22 18:16:06, whunt wrote:
> > > don't implement this, the compiler will do at least as well
> > 
> > Read it more carefully -- the types are not the same.
> 
> Ahh, I see that and w/o constructors I see the necessity.
> 
>
https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsTypes.h
> File src/pathops/SkPathOpsTypes.h (right):
> 
>
https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsType...
> src/pathops/SkPathOpsTypes.h:251: return 1 >> 3 - (one ^ two) ^ 3;
> On 2013/03/22 19:38:51, caryclark wrote:
> > On 2013/03/22 18:16:06, whunt wrote:
> > > I believe:
> > > ((one ^ two) & 1) + 1
> > > will yield you the same result in fewer ops.  The existing solution should
> be
> > 5
> > > ops: two xor, one sub, one shift and one mov (to set the 1 that gets
> shifted).
> > 
> > > This solution should be 3: xor, and and inc
> > > 
> > > requirements (by my understanding):
> > > [0,1] = 2
> > > [0,2] = 1
> > > [0,3] = 1 or 2
> > > [1,2] = 1 or 2
> > > [1,3] = 1
> > > [2,3] = 2
> > > 
> > > a ^ b:
> > > [0,1] = 1
> > > [0,2] = 2
> > > [0,3] = 3
> > > [1,2] = 3
> > > [1,3] = 2
> > > [2,3] = 1
> > > 
> > > (a ^ b) & 1:
> > > [0,1] = 1
> > > [0,2] = 0
> > > [0,3] = 1
> > > [1,2] = 1
> > > [1,3] = 0
> > > [2,3] = 1
> > > 
> > > ((a ^ b) & 1) + 1:
> > > [0,1] = 2
> > > [0,2] = 1
> > > [0,3] = 2
> > > [1,2] = 2
> > > [1,3] = 1
> > > [2,3] = 2
> > 
> > This function is no longer used. It's been removed.
> 
> Sad =(, it was an interesting bit-twiddling problem.

[danakj, 2013-03-22 19:52:18]

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
File src/pathops/SkPathOpsBounds.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:20: void add(SkScalar left, SkScalar top, SkScalar
right, SkScalar bottom) {
On 2013/03/22 19:38:51, caryclark wrote:
> On 2013/03/22 18:16:06, whunt wrote:
> > add is a very overloaded word.  I'd recommend "Union" in this case as you
are
> > unioning a new point into a point set.
> 
> Point taken. However, union is unavailable -- Skia coding standards requires
> that members are lowercase. 

We've used "unite" in the past instead

[caryclark, 2013-03-22 20:05:00]

Thanks for your review contents. I apologize if some of my replies are cryptic,
but I tried to make sure that I read and responded to each comment.

In general, if you see specific problems or suspect there are bugs in the code,
please continue to add comments.

If you think Skia should adapt a different coding style or have different
approaches to implementing algorithms in general, this may not be the best forum
to hash that out.

I'll re-upload the code so that you may iterate afresh.

Thanks again

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
File src/pathops/SkPathOpsBounds.cpp (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.cpp:2: * Copyright 2012 Google Inc.
On 2013/03/22 19:11:42, danakj wrote:
> 2013 everywhere

This code was written and published in 2012.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
File src/pathops/SkPathOpsBounds.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:46: bool isEmpty() {
On 2013/03/22 19:11:42, danakj wrote:
> it seems interesting that a 0x0 area is empty but a 0x10 area is not? that
> certainly is not how other geometry types in our code base work, is that going
> to cause a problem?

In this use case, that is the correct behavior. Note that all code here solely
exists to perform path ops, and is private to that purpose.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:46: bool isEmpty() {
On 2013/03/22 19:37:28, whunt wrote:
> On 2013/03/22 19:11:42, danakj wrote:
> > it seems interesting that a 0x0 area is empty but a 0x10 area is not? that
> > certainly is not how other geometry types in our code base work, is that
going
> > to cause a problem?
> 
> 0x0 should not be empty, it should contain a point (e.g. the result of an
> setPoint() call)

Not for this application.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:47: return fLeft > fRight || fTop > fBottom
On 2013/03/22 18:16:06, whunt wrote:
> the implementation should be:
> !(fLeft < fRight && fTop < fBottom)
> this will catch all cases you have here

Noted.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsBoun...
src/pathops/SkPathOpsBounds.h:48: || (fLeft == fRight && fTop == fBottom)
On 2013/03/22 19:37:28, whunt wrote:
> I think this check (for single point) is wrong, see Dana's comment.

For this use case, it is not wrong.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsCubi...
File src/pathops/SkPathOpsCubic.cpp (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsCubi...
src/pathops/SkPathOpsCubic.cpp:113: static const double PI = 4 * atan(1);
On 2013/03/22 18:16:06, whunt wrote:
> Is this allowed in skia?  In chromium statics be initialized with functions. 
> You may just want to drop in the constant.
> 3.14159265359

Done.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsCubic.h
File src/pathops/SkPathOpsCubic.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsCubi...
src/pathops/SkPathOpsCubic.h:32: const SkDPoint& operator[](int n) const {
return fPts[n]; }
On 2013/03/22 18:16:06, whunt wrote:
> DCHECK/assert n < 4

Done.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
File src/pathops/SkPathOpsPoint.cpp (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
src/pathops/SkPathOpsPoint.cpp:14: SkDPoint operator+(const SkDPoint& a, const
SkDVector& b) {
On 2013/03/22 18:16:06, whunt wrote:
> This function should be inlined.  If the rational for not inlining it is code
> size you'll find that pushing the operators and making the function call are
> actually more code bytes than the adds.
Noted.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
src/pathops/SkPathOpsPoint.cpp:15: SkDPoint v = {a.fX + b.fX, a.fY + b.fY};
On 2013/03/22 18:16:06, whunt wrote:
> you'll bet better code with a constructor

Noted.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoint.h
File src/pathops/SkPathOpsPoint.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
src/pathops/SkPathOpsPoint.h:38: SkVector asSkVector() const {
On 2013/03/22 18:16:06, whunt wrote:
> for reasons I'm not entirely clear on, many compilers I've tested do not
> generate optimal code when using this pattern.  For optimal performance having
a
> constructor for SkVector and implement the function as:
> return SkVector(SkDoubleToScalar(fX), SkDoubleToScalar(fY)); 

Noted.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
src/pathops/SkPathOpsPoint.h:79: void operator=(const SkPoint& pt) {
On 2013/03/22 19:50:10, whunt wrote:
> On 2013/03/22 19:38:51, caryclark wrote:
> > On 2013/03/22 18:16:06, whunt wrote:
> > > don't implement this, the compiler will do at least as well
> > 
> > Read it more carefully -- the types are not the same.
> 
> Ahh, I see that and w/o constructors I see the necessity.

Done.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsPoin...
src/pathops/SkPathOpsPoint.h:133: SkPoint pt = {SkDoubleToScalar(fX),
SkDoubleToScalar(fY)};
On 2013/03/22 18:16:06, whunt wrote:
> Again, the compiler will produce better code with a constructor.

Noted.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsRect.h
File src/pathops/SkPathOpsRect.h (right):

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsRect...
src/pathops/SkPathOpsRect.h:15: void add(const SkDPoint& pt) {
On 2013/03/22 18:16:06, whunt wrote:
> add is a very overloaded name, I'd recommend "Union" (this is essentially a
set
> operation)

Noted.

https://codereview.chromium.org/12827020/diff/14006/src/pathops/SkPathOpsRect...
src/pathops/SkPathOpsRect.h:15: void add(const SkDPoint& pt) {
On 2013/03/22 19:00:37, reed1 wrote:
> On 2013/03/22 18:16:06, whunt wrote:
> > add is a very overloaded name, I'd recommend "Union" (this is essentially a
> set
> > operation)
> 
> whunt: skia uses lower-case for method names, and 'union' would be illegal.
> 
> For better or worse, SkRect has growToInclude(x, y) ... just saying.

Noted.

[caryclark, 2013-03-25 13:44:59]

I looked at the code generated by auto initialization, and determined that it is
efficient. Should this pop up again during profiling, I'm happy to spend more
time finding an alternative.

This update includes public headers in the include directory. These headers are
sufficient to write tests, but can be tweaked as needed to fit into the SkPath
class and to provide better functionality (e.g., a bool return if the result is
empty to match the SkRegion equivalent).

[caryclark, 2013-04-08 11:49:40]

Committed manually as r8551 (presubmit successful).