Tighten bounds on 3d clipping.

Tighten bounds on 3d clipping.

We can only generate 6 points for even non-convex quads.
It falls from the w component crossing 0 implies we have to remove
at least one corner for each 2 we add. We can only do that twice.
4 -> 3+2 -> 2+4 -> 1+2.

BUG=None
CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel

Review-Url: https://codereview.chromium.org/2627213002
Cr-Commit-Position: refs/heads/master@{#443350}
Committed: https://chromium.googlesource.com/chromium/src/+/61b5a492fc55a674d0df5d1eb65695118f39a2c3

[Peter Mayo, 2017-01-12 01:55:34]

Description was changed from

==========
Tighten bounds on 3d clipping.

We can only generate 6 points for even non-convex quads.
It falls from the w component crossing 0 implies we get have to remove
at least one corner for each 2 we add. We can only do that twice.

BUG=
==========

to

==========
Tighten bounds on 3d clipping.

We can only generate 6 points for even non-convex quads.
It falls from the w component crossing 0 implies we get have to remove
at least one corner for each 2 we add. We can only do that twice.

BUG=
CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel
==========

[Peter Mayo, 2017-01-12 01:56:46]

petermayo@chromium.org changed reviewers:
+ danakj@chromium.org, flackr@chromium.org

[Peter Mayo, 2017-01-12 01:56:46]

Another observation from staring at this code for too long.

[Peter Mayo, 2017-01-12 01:56:57]

Description was changed from

==========
Tighten bounds on 3d clipping.

We can only generate 6 points for even non-convex quads.
It falls from the w component crossing 0 implies we get have to remove
at least one corner for each 2 we add. We can only do that twice.

BUG=
CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel
==========

to

==========
Tighten bounds on 3d clipping.

We can only generate 6 points for even non-convex quads.
It falls from the w component crossing 0 implies we get have to remove
at least one corner for each 2 we add. We can only do that twice.

BUG=None
CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel
==========

[flackr, 2017-01-12 16:59:11]

Also could probably work this out by the maximum number of branches hit by
if (h1) ...
if (h1 ^ h2) ...
if (h2) ...
...
if (h4)
if (h4 ^ h1)

https://codereview.chromium.org/2627213002/diff/20001/cc/base/math_util.cc
File cc/base/math_util.cc (right):

https://codereview.chromium.org/2627213002/diff/20001/cc/base/math_util.cc#ne...
cc/base/math_util.cc:373: DCHECK_LE(*num_vertices_in_clipped_quad, 6);
I'm concerned with the DCHECK that if we got this maximum amount wrong for some
reason we might not find out if it's a rare case (i.e. only hit on release where
it may crash later). Can we make this a release check?

[danakj, 2017-01-12 17:01:20]

https://codereview.chromium.org/2627213002/diff/20001/cc/base/math_util.cc
File cc/base/math_util.cc (right):

https://codereview.chromium.org/2627213002/diff/20001/cc/base/math_util.cc#ne...
cc/base/math_util.cc:373: DCHECK_LE(*num_vertices_in_clipped_quad, 6);
On 2017/01/12 16:59:11, flackr wrote:
> I'm concerned with the DCHECK that if we got this maximum amount wrong for
some
> reason we might not find out if it's a rare case (i.e. only hit on release
where
> it may crash later). Can we make this a release check?

Can we not just find a provably correct number?

[Peter Mayo, 2017-01-12 17:24:16]

On 2017/01/12 17:01:20, danakj (slow) wrote:
> https://codereview.chromium.org/2627213002/diff/20001/cc/base/math_util.cc
> File cc/base/math_util.cc (right):
> 
>
https://codereview.chromium.org/2627213002/diff/20001/cc/base/math_util.cc#ne...
> cc/base/math_util.cc:373: DCHECK_LE(*num_vertices_in_clipped_quad, 6);
> On 2017/01/12 16:59:11, flackr wrote:
> > I'm concerned with the DCHECK that if we got this maximum amount wrong for
> some
> > reason we might not find out if it's a rare case (i.e. only hit on release
> where
> > it may crash later). Can we make this a release check?
> 
> Can we not just find a provably correct number?

6 is necessary and sufficient for 4 general vertices (a quad).

5 is sufficient if we require the source quad to be numerically stably convex. 
Mostly they
come from rectangles, which theoretically meet the constraint after mapping, but
I don't want
to DCHECK something that could be a flaky numeric corner.

If I knew how to put a stat counter (UMA, tracing, logging, ???) in I might add
one for hitting the 6 output points case.

6 comes from the branches:
  every mid point we include implies there is a vertex that is excluded.
  therefore we have at most 4 midpoints and 2 vertices.

in ascii it happens like this:

      | .1
      |
 2. 4.|
      |
      | .3 

the result is (1) (1-2) (2-3) (3) (3-4) (4-1)


also if you output 2 vertices you will not output the half-way point  (h1 && h2
=> ! h1 ^ h2)  and (h1 ^ h2 => !h1 or ! h2)

starting from how many vertices we include:

4 + 0 (no ex-ors can be true)
3 + 2  (only two ex-ors can be true)
2 + 4    (there are only 4 ex-ors)
1 + 2  (only one ex-or can be true)
0 + 0 (no ex-ors can be true)


This is the logic I went through before I proposed the change, FWIW.

I thought the CL comment was clear on that.  Do you have a proposal to improve
it without making it this long?

[flackr, 2017-01-12 18:29:43]

On 2017/01/12 17:24:16, Peter Mayo wrote:
> On 2017/01/12 17:01:20, danakj (slow) wrote:
> > https://codereview.chromium.org/2627213002/diff/20001/cc/base/math_util.cc
> > File cc/base/math_util.cc (right):
> > 
> >
>
https://codereview.chromium.org/2627213002/diff/20001/cc/base/math_util.cc#ne...
> > cc/base/math_util.cc:373: DCHECK_LE(*num_vertices_in_clipped_quad, 6);
> > On 2017/01/12 16:59:11, flackr wrote:
> > > I'm concerned with the DCHECK that if we got this maximum amount wrong for
> > some
> > > reason we might not find out if it's a rare case (i.e. only hit on release
> > where
> > > it may crash later). Can we make this a release check?
> > 
> > Can we not just find a provably correct number?
> 
> 6 is necessary and sufficient for 4 general vertices (a quad).
> 
> 5 is sufficient if we require the source quad to be numerically stably convex.

> Mostly they
> come from rectangles, which theoretically meet the constraint after mapping,
but
> I don't want
> to DCHECK something that could be a flaky numeric corner.
> 
> If I knew how to put a stat counter (UMA, tracing, logging, ???) in I might
add
> one for hitting the 6 output points case.
> 
> 6 comes from the branches:
>   every mid point we include implies there is a vertex that is excluded.
>   therefore we have at most 4 midpoints and 2 vertices.
> 
> in ascii it happens like this:
> 
>       | .1
>       |
>  2. 4.|
>       |
>       | .3 
> 
> the result is (1) (1-2) (2-3) (3) (3-4) (4-1)
> 
> 
> also if you output 2 vertices you will not output the half-way point  (h1 &&
h2
> => ! h1 ^ h2)  and (h1 ^ h2 => !h1 or ! h2)
> 
> starting from how many vertices we include:
> 
> 4 + 0 (no ex-ors can be true)
> 3 + 2  (only two ex-ors can be true)
> 2 + 4    (there are only 4 ex-ors)
> 1 + 2  (only one ex-or can be true)
> 0 + 0 (no ex-ors can be true)
> 
> 
> This is the logic I went through before I proposed the change, FWIW.
> 
> I thought the CL comment was clear on that.  Do you have a proposal to improve
> it without making it this long?

Sorry, I just didn't follow it initially. Thanks for the breakdown, it makes
perfect sense to me now. LGTM.

[danakj, 2017-01-12 18:46:44]

rs LGTM

[Peter Mayo, 2017-01-12 19:36:29]

Description was changed from

==========
Tighten bounds on 3d clipping.

We can only generate 6 points for even non-convex quads.
It falls from the w component crossing 0 implies we get have to remove
at least one corner for each 2 we add. We can only do that twice.

BUG=None
CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel
==========

to

==========
Tighten bounds on 3d clipping.

We can only generate 6 points for even non-convex quads.
It falls from the w component crossing 0 implies we have to remove
at least one corner for each 2 we add. We can only do that twice.
4 -> 3+2 -> 2+4 -> 1+2.

BUG=None
CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel
==========

[Peter Mayo, 2017-01-12 19:36:41]

The CQ bit was checked by petermayo@chromium.org

[commit-bot: I haz the power, 2017-01-12 19:37:17]

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, 2017-01-12 20:45:27]

CQ is committing da patch.

Bot data: {"patchset_id": 20001, "attempt_start_ts": 1484249801289740,
"parent_rev": "5a7ffae71d0dcf646d26ef202f8d1882587724c7", "commit_rev":
"61b5a492fc55a674d0df5d1eb65695118f39a2c3"}

[commit-bot: I haz the power, 2017-01-12 20:45:55]

Description was changed from

==========
Tighten bounds on 3d clipping.

We can only generate 6 points for even non-convex quads.
It falls from the w component crossing 0 implies we have to remove
at least one corner for each 2 we add. We can only do that twice.
4 -> 3+2 -> 2+4 -> 1+2.

BUG=None
CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel
==========

to

==========
Tighten bounds on 3d clipping.

We can only generate 6 points for even non-convex quads.
It falls from the w component crossing 0 implies we have to remove
at least one corner for each 2 we add. We can only do that twice.
4 -> 3+2 -> 2+4 -> 1+2.

BUG=None
CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel

Review-Url: https://codereview.chromium.org/2627213002
Cr-Commit-Position: refs/heads/master@{#443350}
Committed:
https://chromium.googlesource.com/chromium/src/+/61b5a492fc55a674d0df5d1eb656...
==========

[commit-bot: I haz the power, 2017-01-12 20:45:56]

Committed patchset #2 (id:20001) as
https://chromium.googlesource.com/chromium/src/+/61b5a492fc55a674d0df5d1eb656...