Perform BSP polygon splitting and orientation selection in a single step.

Perform BSP polygon splitting and orientation selection in a single step.

This eliminates redundant testing of vertices for orientation with
respect to the splitting polygon. Previously, up to 3 sets of tests
were made (once to determine whether the polygon was split, then once
during the split, and then finally to determine the orientation of the
split polygons.

Merging these steps in order to reuse calculated values also eliminates
the possibility that different calculations in testing and splitting
could be inconsistent.

BUG=606984
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel

Committed: https://crrev.com/89c62c8f69d76471e866f21ee4f1ae5e0c5bca48
Committed: https://crrev.com/3e9082bfc63be6b304543ee499354fd71ea063ae
Cr-Original-Commit-Position: refs/heads/master@{#399459}
Cr-Commit-Position: refs/heads/master@{#403559}

[Tobias Sargeant, 2016-06-08 08:50:02]

Description was changed from

==========
Perform BSP polygon splitting and orientation selection in a single step.

This eliminates redundant testing of vertices for orientation with
respect to the splitting polygon. Previously, up to 3 sets of tests
were made (once to determine whether the polygon was split, then once
during the split, and then finally to determine the orientation of the
split polygons.

Merging these steps in order to reuse calculated values also eliminates
the possibility that different calculations in testing and splitting
could be inconsistent.

BUG=606984
==========

to

==========
Perform BSP polygon splitting and orientation selection in a single step.

This eliminates redundant testing of vertices for orientation with
respect to the splitting polygon. Previously, up to 3 sets of tests
were made (once to determine whether the polygon was split, then once
during the split, and then finally to determine the orientation of the
split polygons.

Merging these steps in order to reuse calculated values also eliminates
the possibility that different calculations in testing and splitting
could be inconsistent.

BUG=606984
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
==========

[Tobias Sargeant, 2016-06-08 17:27:44]

tobiasjs@chromium.org changed reviewers:
+ enne@chromium.org

[Tobias Sargeant, 2016-06-08 17:27:45]

Hi Enne,

Delving into this a bit deeper, I think it is actually a bit of a potential (and
actual, after my previous change) pitfall to have the process of decising
whether to split be independent from the actual splitting.

It's also a performance loss, given you end up computing the same set of dot
products 3 times currently.

As it stands, I'd like to get rid of DrawPolygon::SideCompare, as it's only used
in tests. The DrawPolygon unittests could be modified to not need it (by just
splitting the polygon, and checking where the result ends up) but I'm not so
sure that the BSP tests can be dealt with the same way.

Anyway, WDYT?

[enne (OOO), 2016-06-08 22:02:52]

Can you also put up a patch without the test expectations so I can look at the
try bots and see what the results look like?

https://codereview.chromium.org/2043283002/diff/20001/cc/quads/draw_polygon.cc
File cc/quads/draw_polygon.cc (right):

https://codereview.chromium.org/2043283002/diff/20001/cc/quads/draw_polygon.c...
cc/quads/draw_polygon.cc:149: BspCompareResult DrawPolygon::SideCompare(const
DrawPolygon& a,
Is this function used anymore?

https://codereview.chromium.org/2043283002/diff/20001/cc/quads/draw_polygon.c...
cc/quads/draw_polygon.cc:250: const size_t N_points = polygon->points_.size();
N_points isn't valid chromium style.

I think you're looking for n_points or maybe num_points?

https://codereview.chromium.org/2043283002/diff/20001/cc/quads/draw_polygon.c...
cc/quads/draw_polygon.cc:363: return false;
Can you add some dchecks that out_points in both cases have at least three
points and that the sum total of points - 4 = original number of points?  This
is less clear than in the original version.

https://codereview.chromium.org/2043283002/diff/20001/cc/quads/draw_polygon.c...
cc/quads/draw_polygon.cc:363: return false;
Can you add some dchecks that out_points in both cases have at least three
points and that the sum total of points - 4 = original number of points?  This
is less clear than in the original version.

https://codereview.chromium.org/2043283002/diff/20001/cc/quads/draw_polygon.h
File cc/quads/draw_polygon.h (right):

https://codereview.chromium.org/2043283002/diff/20001/cc/quads/draw_polygon.h...
cc/quads/draw_polygon.h:43: bool SplitPolygon(std::unique_ptr<DrawPolygon>
polygon,
Style nit: if you have more than one out parameter, then make them all
parameters and not some as out parameters and one as a return value.

I see you're using it for EXPECT calls, but it looks like you could write a test
helper that says bool IsCoplanar() and hides the front and back parameters
inside it, and checks that front and back are not null when a split occurs.

https://codereview.chromium.org/2043283002/diff/20001/cc/quads/draw_polygon.h...
cc/quads/draw_polygon.h:46: bool SplitPolygon(const DrawPolygon& polygon,
This is a bit awkward.  How many test locations use this? Can you just make the
test call WrapUnique or move this function into tests?

[Tobias Sargeant, 2016-06-09 16:48:44]

https://codereview.chromium.org/2043283002/diff/20001/cc/quads/draw_polygon.cc
File cc/quads/draw_polygon.cc (right):

https://codereview.chromium.org/2043283002/diff/20001/cc/quads/draw_polygon.c...
cc/quads/draw_polygon.cc:149: BspCompareResult DrawPolygon::SideCompare(const
DrawPolygon& a,
On 2016/06/08 22:02:51, enne wrote:
> Is this function used anymore?

Only in tests.

https://codereview.chromium.org/2043283002/diff/20001/cc/quads/draw_polygon.c...
cc/quads/draw_polygon.cc:250: const size_t N_points = polygon->points_.size();
On 2016/06/08 22:02:51, enne wrote:
> N_points isn't valid chromium style.
> 
> I think you're looking for n_points or maybe num_points?

Done.

https://codereview.chromium.org/2043283002/diff/20001/cc/quads/draw_polygon.c...
cc/quads/draw_polygon.cc:363: return false;
On 2016/06/08 22:02:51, enne wrote:
> Can you add some dchecks that out_points in both cases have at least three
> points and that the sum total of points - 4 = original number of points?  This
> is less clear than in the original version.

Yes, but that latter condition is actually wrong in the case where there are
some points that are on the thick plane. Looking at the code as it stood, I
think this wasn't handled correctly previously. e.g.

     |
    /|\
   / | \
  /  |  \
  \  |  /
   \ | /
    \|/
     |

Then splitting that quad should result in 2 triangles. Previously it looks like
this would result in 2 degenerate quads with two vertices at the same
coordinate.

I've DCHECKed that there are at most two vertices that lie on the thick plane,
which is equivalent to catching (some) non-convex cases, and also ensures that
the vertex loop is divisible into two halves such that no vertices are lost.

https://codereview.chromium.org/2043283002/diff/20001/cc/quads/draw_polygon.h
File cc/quads/draw_polygon.h (right):

https://codereview.chromium.org/2043283002/diff/20001/cc/quads/draw_polygon.h...
cc/quads/draw_polygon.h:43: bool SplitPolygon(std::unique_ptr<DrawPolygon>
polygon,
On 2016/06/08 22:02:51, enne wrote:
> Style nit: if you have more than one out parameter, then make them all
> parameters and not some as out parameters and one as a return value.
> 
> I see you're using it for EXPECT calls, but it looks like you could write a
test
> helper that says bool IsCoplanar() and hides the front and back parameters
> inside it, and checks that front and back are not null when a split occurs.

Done.

https://codereview.chromium.org/2043283002/diff/20001/cc/quads/draw_polygon.h...
cc/quads/draw_polygon.h:46: bool SplitPolygon(const DrawPolygon& polygon,
On 2016/06/08 22:02:51, enne wrote:
> This is a bit awkward.  How many test locations use this? Can you just make
the
> test call WrapUnique or move this function into tests?

Moved this into the tests.

[enne (OOO), 2016-06-09 17:11:26]

lgtm

https://codereview.chromium.org/2043283002/diff/20001/cc/quads/draw_polygon.cc
File cc/quads/draw_polygon.cc (right):

https://codereview.chromium.org/2043283002/diff/20001/cc/quads/draw_polygon.c...
cc/quads/draw_polygon.cc:363: return false;
On 2016/06/09 at 16:48:44, Tobias Sargeant wrote:
> Then splitting that quad should result in 2 triangles. Previously it looks
like this would result in 2 degenerate quads with two vertices at the same
coordinate.
> 
> I've DCHECKed that there are at most two vertices that lie on the thick plane,
which is equivalent to catching (some) non-convex cases, and also ensures that
the vertex loop is divisible into two halves such that no vertices are lost.

Yeah, that was my concern--I didn't want to lose vertices.  Thanks for the
clarification about the total number of points in those cases.

[Tobias Sargeant, 2016-06-09 18:20:53]

Thanks. Can I assume that as all the try jobs are green, there's no need to
rebaseline any extra tests? It would be nice to try and re-enable the tests that
are currently marked as failures, but that didn't go so well last time.

[enne (OOO), 2016-06-09 18:22:54]

I added the *blink_rel trybots.  If those are green, then you're good to go.

[Tobias Sargeant, 2016-06-10 13:12:53]

On 2016/06/09 18:22:54, enne wrote:
> I added the *blink_rel trybots.  If those are green, then you're good to go.

Ok. Not fine, as I suspected from local testing. I guess the best thing to do is
to land with rebaselines and watch to see if the error expectations need to be
put back in?

[Tobias Sargeant, 2016-06-13 13:25:18]

The CQ bit was checked by tobiasjs@chromium.org

[Tobias Sargeant, 2016-06-13 13:25:19]

The patchset sent to the CQ was uploaded after l-g-t-m from enne@chromium.org
Link to the patchset: https://codereview.chromium.org/2043283002/#ps60001
(title: "Re-add rebaselines")

[commit-bot: I haz the power, 2016-06-13 13:25:36]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/2043283002/60001

[commit-bot: I haz the power, 2016-06-13 15:48:08]

Committed patchset #4 (id:60001)

[commit-bot: I haz the power, 2016-06-13 15:48:11]

CQ bit was unchecked

[commit-bot: I haz the power, 2016-06-13 15:49:36]

Description was changed from

==========
Perform BSP polygon splitting and orientation selection in a single step.

This eliminates redundant testing of vertices for orientation with
respect to the splitting polygon. Previously, up to 3 sets of tests
were made (once to determine whether the polygon was split, then once
during the split, and then finally to determine the orientation of the
split polygons.

Merging these steps in order to reuse calculated values also eliminates
the possibility that different calculations in testing and splitting
could be inconsistent.

BUG=606984
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
==========

to

==========
Perform BSP polygon splitting and orientation selection in a single step.

This eliminates redundant testing of vertices for orientation with
respect to the splitting polygon. Previously, up to 3 sets of tests
were made (once to determine whether the polygon was split, then once
during the split, and then finally to determine the orientation of the
split polygons.

Merging these steps in order to reuse calculated values also eliminates
the possibility that different calculations in testing and splitting
could be inconsistent.

BUG=606984
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel

Committed: https://crrev.com/89c62c8f69d76471e866f21ee4f1ae5e0c5bca48
Cr-Commit-Position: refs/heads/master@{#399459}
==========

[commit-bot: I haz the power, 2016-06-13 15:49:37]

Patchset 4 (id:??) landed as
https://crrev.com/89c62c8f69d76471e866f21ee4f1ae5e0c5bca48
Cr-Commit-Position: refs/heads/master@{#399459}

[enne (OOO), 2016-06-13 16:58:41]

Yeah, landing with rebaseline expectations was the right thing to do.

[Fady Samuel, 2016-06-13 17:21:55]

A revert of this CL (patchset #4 id:60001) has been created in
https://codereview.chromium.org/2060183003/ by fsamuel@chromium.org.

The reason for reverting is: Broke Windows 7 cc_unittests:
DrawPolygonSplitTest.AngledSplit
https://build.chromium.org/p/chromium.win/builders/Win7%20Tests%20%281%29/bui....

[Tobias Sargeant, 2016-06-13 17:32:44]

Description was changed from

==========
Perform BSP polygon splitting and orientation selection in a single step.

This eliminates redundant testing of vertices for orientation with
respect to the splitting polygon. Previously, up to 3 sets of tests
were made (once to determine whether the polygon was split, then once
during the split, and then finally to determine the orientation of the
split polygons.

Merging these steps in order to reuse calculated values also eliminates
the possibility that different calculations in testing and splitting
could be inconsistent.

BUG=606984
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel

Committed: https://crrev.com/89c62c8f69d76471e866f21ee4f1ae5e0c5bca48
Cr-Commit-Position: refs/heads/master@{#399459}
==========

to

==========
Perform BSP polygon splitting and orientation selection in a single step.

This eliminates redundant testing of vertices for orientation with
respect to the splitting polygon. Previously, up to 3 sets of tests
were made (once to determine whether the polygon was split, then once
during the split, and then finally to determine the orientation of the
split polygons.

Merging these steps in order to reuse calculated values also eliminates
the possibility that different calculations in testing and splitting
could be inconsistent.

BUG=606984
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel

Committed: https://crrev.com/89c62c8f69d76471e866f21ee4f1ae5e0c5bca48
Cr-Commit-Position: refs/heads/master@{#399459}
==========

[Tobias Sargeant, 2016-06-28 12:13:45]

Patchset #6 (id:100001) has been deleted

[enne (OOO), 2016-07-01 18:40:51]

lgtm to reland with some tolerance in the AngledSplit test.

[Tobias Sargeant, 2016-07-01 22:37:03]

The CQ bit was checked by tobiasjs@chromium.org

[Tobias Sargeant, 2016-07-01 22:37:03]

The patchset sent to the CQ was uploaded after l-g-t-m from enne@chromium.org
Link to the patchset: https://codereview.chromium.org/2043283002/#ps160001
(title: "Make AngledSplit test sufficiently inexact; revert speculative change")

[commit-bot: I haz the power, 2016-07-01 22:37:23]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-07-01 23:18:57]

Description was changed from

==========
Perform BSP polygon splitting and orientation selection in a single step.

This eliminates redundant testing of vertices for orientation with
respect to the splitting polygon. Previously, up to 3 sets of tests
were made (once to determine whether the polygon was split, then once
during the split, and then finally to determine the orientation of the
split polygons.

Merging these steps in order to reuse calculated values also eliminates
the possibility that different calculations in testing and splitting
could be inconsistent.

BUG=606984
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel

Committed: https://crrev.com/89c62c8f69d76471e866f21ee4f1ae5e0c5bca48
Cr-Commit-Position: refs/heads/master@{#399459}
==========

to

==========
Perform BSP polygon splitting and orientation selection in a single step.

This eliminates redundant testing of vertices for orientation with
respect to the splitting polygon. Previously, up to 3 sets of tests
were made (once to determine whether the polygon was split, then once
during the split, and then finally to determine the orientation of the
split polygons.

Merging these steps in order to reuse calculated values also eliminates
the possibility that different calculations in testing and splitting
could be inconsistent.

BUG=606984
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel

Committed: https://crrev.com/89c62c8f69d76471e866f21ee4f1ae5e0c5bca48
Cr-Commit-Position: refs/heads/master@{#399459}
==========

[commit-bot: I haz the power, 2016-07-01 23:18:58]

Committed patchset #8 (id:160001)

[commit-bot: I haz the power, 2016-07-01 23:19:00]

CQ bit was unchecked.

[commit-bot: I haz the power, 2016-07-01 23:20:40]

Description was changed from

==========
Perform BSP polygon splitting and orientation selection in a single step.

This eliminates redundant testing of vertices for orientation with
respect to the splitting polygon. Previously, up to 3 sets of tests
were made (once to determine whether the polygon was split, then once
during the split, and then finally to determine the orientation of the
split polygons.

Merging these steps in order to reuse calculated values also eliminates
the possibility that different calculations in testing and splitting
could be inconsistent.

BUG=606984
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel

Committed: https://crrev.com/89c62c8f69d76471e866f21ee4f1ae5e0c5bca48
Cr-Commit-Position: refs/heads/master@{#399459}
==========

to

==========
Perform BSP polygon splitting and orientation selection in a single step.

This eliminates redundant testing of vertices for orientation with
respect to the splitting polygon. Previously, up to 3 sets of tests
were made (once to determine whether the polygon was split, then once
during the split, and then finally to determine the orientation of the
split polygons.

Merging these steps in order to reuse calculated values also eliminates
the possibility that different calculations in testing and splitting
could be inconsistent.

BUG=606984
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel

Committed: https://crrev.com/89c62c8f69d76471e866f21ee4f1ae5e0c5bca48
Committed: https://crrev.com/3e9082bfc63be6b304543ee499354fd71ea063ae
Cr-Original-Commit-Position: refs/heads/master@{#399459}
Cr-Commit-Position: refs/heads/master@{#403559}
==========

[commit-bot: I haz the power, 2016-07-01 23:20:42]

Patchset 8 (id:??) landed as
https://crrev.com/3e9082bfc63be6b304543ee499354fd71ea063ae
Cr-Commit-Position: refs/heads/master@{#403559}