Determine face orientation in (x, y: w) projected space

Determine face orientation in (x, y: w) projected space

The current Transform::IsBackFaceVisible() implementation only works for
matrix without perspective. This CL extends the function to work on
general 4x4 matrix.

This CL also corrects the transform used in cc for determining face
orientation.

[trchen, 2015-03-28 01:49:46]

trchen@chromium.org changed reviewers:
+ enne@chromium.org, vollick@chromium.org

[trchen, 2015-03-28 01:49:47]

Hello reviewers, this CL is an attempt to make backface visibility saner. PTAL,
thanks!

It is WIP. Tests need to be added and probably need to update the property tree
counterpart.

[Ian Vollick, 2015-03-31 16:02:16]

On 2015/03/28 01:49:47, trchen wrote:
> Hello reviewers, this CL is an attempt to make backface visibility saner.
PTAL,
> thanks!
> 
> It is WIP. Tests need to be added and probably need to update the property
tree
> counterpart.

Please include an example that fails with the old IsBackFaceVisible and passes
with the new.

I believe the logic in LTHC was designed to match up with bullet #1 from
http://www.w3.org/TR/css3-transforms/#backface-visibility-property. Can you
explain how the Is3dSorted value will capture the right concepts? (Does this
pass our tests?).

[trchen, 2015-03-31 23:32:52]

Closing this CL for now. What really matters are the two TODOs I added in the
CL. This CL itself doesn't add much value.

I replied a summarized analysis to vollick in chat. Here is the detailed
analysis for note.
(Feel free to TLDR.)

On 2015/03/31 16:02:16, vollick wrote:
> On 2015/03/28 01:49:47, trchen wrote:
> > Hello reviewers, this CL is an attempt to make backface visibility saner.
> PTAL,
> > thanks!
> > 
> > It is WIP. Tests need to be added and probably need to update the property
> tree
> > counterpart.
> 
> Please include an example that fails with the old IsBackFaceVisible and passes
> with the new.

I originally thought the original formula was wrong and came up with the new
formula and added some fix-up in cc. It turns out it is the cc part that fixes
bugs. The two formulas are equivalent for regular matrices. (i.e. Only xyz
operations in the begging and end with a positive perspective.)

Basically the original formula calculates det|M33| * det|M|, where as the new
formula calculates det|M33| * det|M34|.

It is known that for only xyz operations the resulting matrix have the form of
| a b c d |
| e f g h | = M'
| i j k l |
| 0 0 0 1 |
i.e. I doesn't change the w row. Applying a positive perspective at last doesn't
change the determinant. Therefore det|M| = det|Mpers * M'| = det|M'| = det|M'44|
= det|M44|

Also after applying perspective we have
|   a    b    c    d   |
|   e    f    g    h   | = Mpers * M' = M
|   i    j    k    l   |
| -i/p -j/p -k/p 1-l/p |
We can see det|M34| = -det|M44|/p. It is proved that the two formula works
identically for such matrices.

So where the two formulas differ is how they handle negative perspective. i.e.
The farther in z, the bigger the object seems. The old formula prefers xyz
space, where the new formula prefers xyw space.

Since CSS allows specifying raw matrices, the two formulas will actually behave
differently. However it is a known issue that CSS spec is unclear about how to
calculate this: https://www.w3.org/Bugs/Public/show_bug.cgi?id=23014

I think unless we found some legit use case for negative perspective, both
formulas are are acceptable. Thought the new formula will be about 3x as fast
when a finite perspective is applied, and 2x as fast with infinite perspective,
due to avoiding to calculate det4.

Arithmetic complexity: 
det4                    30M 17A
backface(old)           43M 22A
backface(new, finite)   13M  7A
backface(new, infinite) 21M 11A

> I believe the logic in LTHC was designed to match up with bullet #1 from
> http://www.w3.org/TR/css3-transforms/#backface-visibility-property. Can you
> explain how the Is3dSorted value will capture the right concepts? (Does this
> pass our tests?).

LayerIsInExisting3DRenderingContext() determines whether a layer inherits its
parent's 3D context. However a layer that establishes a new 3D context should be
considered to be in a 3D context that is created by itself. The use of
Is3dSorted is legit here. (Actually either way works, since for the root layer
of a 3D context its transform to the flattening layer is equal to its layer
transform.)

For layer that is not 3D-sorted (i.e. not in a 3D context), conceptually they
are creating a 3D context that consists only one layer, so using its layer
transform is equivalent to the transform between layer and its flattening layer.

Now here is the ugly thing: Blink supplies the perspective matrix through the
child transform layer of the element which has perspective property, which
element not necessarily participates in a 3D context, and is not affected by the
perspective. However the perspective should be applied to every child elements
that establishes a 3D context, before flattening.