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

ui/gfx/transform.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 // MSVC++ requires this to be set before any other includes to get M_PI.
 #define _USE_MATH_DEFINES
 
 #include "ui/gfx/transform.h"
 
 #include <cmath>
@@ skipping 240 matching lines @@
       static_cast<int>(matrix_.get(0, 3)) == matrix_.get(0, 3) &&
       static_cast<int>(matrix_.get(1, 3)) == matrix_.get(1, 3) &&
       static_cast<int>(matrix_.get(2, 3)) == matrix_.get(2, 3);
 
   return no_fractional_translation;
 }
 
 bool Transform::IsBackFaceVisible() const {
   // Compute whether a layer with a forward-facing normal of (0, 0, 1, 0)
   // would have its back face visible after applying the transform.
-  if (matrix_.isIdentity())
+
+  // Case 1: Shortcut if simple translate and scale.
+  if (!(matrix_.getType() & SkMatrix44::kAffine_Mask))
+    return matrix_.get(2, 2) < 0;
+
+  // Case 2: Determine back face in the projected space.
+  //
+  // This is done by projecting an arbitrary vector that points to the
+  // front side of the plane. For simplicity we can use (0, 0, 1, 0).
+  // Note that this projected vector will no longer be the normal vector
+  // of the projected plane. To avoid confusion, it will be referred as
+  // the front-face indicator.
+  //
+  // Then we find the normal vector of the projected plane. This vector
+  // is not normalized and does not indicate the face direction. Compute
+  // the dot product of the front-face indicator by the normal vector to
+  // determine which face is the front face.
+  //
+  // The face that faces the half-space where the origin resides is visible.
+
+  // Compute the normal vector of the projected plane.
+  double normal_x = matrix_.get(1, 0) * matrix_.get(3, 1) -
+                    matrix_.get(3, 0) * matrix_.get(1, 1);
+  double normal_y = matrix_.get(3, 0) * matrix_.get(0, 1) -
+                    matrix_.get(0, 0) * matrix_.get(3, 1);
+  double normal_w = matrix_.get(0, 0) * matrix_.get(1, 1) -
+                    matrix_.get(1, 0) * matrix_.get(0, 1);
+
+  // Compute the determinant to determine which half-space the origin resides.
+  // Note that the origin resides in the half-space of the opposite sign.
+  double determinant = normal_x * matrix_.get(0, 3) +
+                       normal_y * matrix_.get(1, 3) +
+                       normal_w * matrix_.get(3, 3);
+
+  // The origin coplanes the projected plane or the plane is degenerate.
+  if (!determinant)
     return false;
 
-  // This is done by transforming the normal and seeing if the resulting z
-  // value is positive or negative. However, note that transforming a normal
-  // actually requires using the inverse-transpose of the original transform.
+  // Compute the dot product of the normal vector by the front-face indicator.
+  double face_direction = normal_x * matrix_.get(0, 2) +
+                          normal_y * matrix_.get(1, 2) +
+                          normal_w * matrix_.get(3, 2);
+
+  // We are seeing the back face if the front face faces the opposite
+  // half-space the origin resides.
+  if (face_direction)
+      return determinant * face_direction > 0;
+
+  // Case 3: Front-face indicator is 0.
   //
-  // We can avoid inverting and transposing the matrix since we know we want
-  // to transform only the specific normal vector (0, 0, 1, 0). In this case,
-  // we only need the 3rd row, 3rd column of the inverse-transpose. We can
-  // calculate only the 3rd row 3rd column element of the inverse, skipping
-  // everything else.
+  // This can happen if the z component does not participate the projection,
+  // which means the original space gets flattened there is no front or back.
+  // A notable example is no perspective (= infinite perspective).
   //
-  // For more information, refer to:
-  //   http://en.wikipedia.org/wiki/Invertible_matrix#Analytic_solution
-  //
+  // Try again as if a perspective that approaches infinite is applied.
+  //       | 1  0  0  0 |
+  //  lim  | 0  1  0  0 |
+  // e->+0 | 0  0  1  0 |
+  //       | 0  0 -e  1 |
 
-  double determinant = matrix_.determinant();
+  double normal_x_epsilon =  matrix_.get(1, 0) * -matrix_.get(2, 1) -
+                            -matrix_.get(2, 0) *  matrix_.get(1, 1);
+  double normal_y_epsilon = -matrix_.get(2, 0) *  matrix_.get(0, 1) -
+                             matrix_.get(0, 0) * -matrix_.get(2, 1);
 
-  // If matrix was not invertible, then just assume back face is not visible.
-  if (std::abs(determinant) <= kEpsilon)
-    return false;
+  face_direction = normal_x_epsilon *  matrix_.get(0, 2) +
+                   normal_y_epsilon *  matrix_.get(1, 2) +
+                   normal_w         * -matrix_.get(2, 2);
 
-  // Compute the cofactor of the 3rd row, 3rd column.
-  double cofactor_part_1 =
-      matrix_.get(0, 0) * matrix_.get(1, 1) * matrix_.get(3, 3);
-
-  double cofactor_part_2 =
-      matrix_.get(0, 1) * matrix_.get(1, 3) * matrix_.get(3, 0);
-
-  double cofactor_part_3 =
-      matrix_.get(0, 3) * matrix_.get(1, 0) * matrix_.get(3, 1);
-
-  double cofactor_part_4 =
-      matrix_.get(0, 0) * matrix_.get(1, 3) * matrix_.get(3, 1);
-
-  double cofactor_part_5 =
-      matrix_.get(0, 1) * matrix_.get(1, 0) * matrix_.get(3, 3);
-
-  double cofactor_part_6 =
-      matrix_.get(0, 3) * matrix_.get(1, 1) * matrix_.get(3, 0);
-
-  double cofactor33 =
-      cofactor_part_1 +
-      cofactor_part_2 +
-      cofactor_part_3 -
-      cofactor_part_4 -
-      cofactor_part_5 -
-      cofactor_part_6;
-
-  // Technically the transformed z component is cofactor33 / determinant.  But
-  // we can avoid the costly division because we only care about the resulting
-  // +/- sign; we can check this equivalently by multiplication.
-  return cofactor33 * determinant < 0;
+  return determinant * face_direction > 0;
 }
 
 bool Transform::GetInverse(Transform* transform) const {
   if (!matrix_.invert(&transform->matrix_)) {
     // Initialize the return value to identity if this matrix turned
     // out to be un-invertible.
     transform->MakeIdentity();
     return false;
   }
 
@@ skipping 235 matching lines @@
       matrix_.get(2, 1),
       matrix_.get(2, 2),
       matrix_.get(2, 3),
       matrix_.get(3, 0),
       matrix_.get(3, 1),
       matrix_.get(3, 2),
       matrix_.get(3, 3));
 }
 
 }  // namespace gfx