[Bf-blender-cvs] [2d60c496a20] master: Mesh: minor optimization to concave quad check for tessellation

[Campbell Barton]

Commit: 2d60c496a200288f100c11845ccb196f04e45ba3
Author: Campbell Barton
Date:   Sun Jun 20 13:47:53 2021 +1000
Branches: master
https://developer.blender.org/rB2d60c496a200288f100c11845ccb196f04e45ba3

Mesh: minor optimization to concave quad check for tessellation

Use the face normal (when available) for a faster concave quad test.

===================================================================

M	source/blender/blenkernel/intern/mesh_tessellate.c
M	source/blender/blenlib/BLI_math_geom.h
M	source/blender/blenlib/intern/math_geom.c
M	source/blender/bmesh/intern/bmesh_mesh_tessellate.c

===================================================================

diff --git a/source/blender/blenkernel/intern/mesh_tessellate.c b/source/blender/blenkernel/intern/mesh_tessellate.c
index 98a93dbc4b5..0cd1b211e4d 100644
--- a/source/blender/blenkernel/intern/mesh_tessellate.c
+++ b/source/blender/blenkernel/intern/mesh_tessellate.c
@@ -476,10 +476,19 @@ BLI_INLINE void mesh_calc_tessellation_for_face_impl(const MLoop *mloop,
       ML_TO_MLT(0, 2, 3);
       MLoopTri *mlt_b = mlt;
 
-      if (UNLIKELY(is_quad_flip_v3_first_third_fast(mvert[mloop[mlt_a->tri[0]].v].co,
-                                                    mvert[mloop[mlt_a->tri[1]].v].co,
-                                                    mvert[mloop[mlt_a->tri[2]].v].co,
-                                                    mvert[mloop[mlt_b->tri[2]].v].co))) {
+      if (UNLIKELY(face_normal ? is_quad_flip_v3_first_third_fast_with_normal(
+                                     /* Simpler calculation (using the normal). */
+                                     mvert[mloop[mlt_a->tri[0]].v].co,
+                                     mvert[mloop[mlt_a->tri[1]].v].co,
+                                     mvert[mloop[mlt_a->tri[2]].v].co,
+                                     mvert[mloop[mlt_b->tri[2]].v].co,
+                                     normal_precalc) :
+                                 is_quad_flip_v3_first_third_fast(
+                                     /* Expensive calculation (no normal). */
+                                     mvert[mloop[mlt_a->tri[0]].v].co,
+                                     mvert[mloop[mlt_a->tri[1]].v].co,
+                                     mvert[mloop[mlt_a->tri[2]].v].co,
+                                     mvert[mloop[mlt_b->tri[2]].v].co))) {
         /* Flip out of degenerate 0-2 state. */
         mlt_a->tri[2] = mlt_b->tri[2];
         mlt_b->tri[0] = mlt_a->tri[1];
diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h
index c744c5d13d3..49188964f3b 100644
--- a/source/blender/blenlib/BLI_math_geom.h
+++ b/source/blender/blenlib/BLI_math_geom.h
@@ -105,6 +105,11 @@ bool is_quad_flip_v3_first_third_fast(const float v1[3],
                                       const float v2[3],
                                       const float v3[3],
                                       const float v4[3]);
+bool is_quad_flip_v3_first_third_fast_with_normal(const float v1[3],
+                                                  const float v2[3],
+                                                  const float v3[3],
+                                                  const float v4[3],
+                                                  const float normal[3]);
 
 /********************************* Distance **********************************/
 
diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c
index 6b1730f8ee8..0a5dc8517d8 100644
--- a/source/blender/blenlib/intern/math_geom.c
+++ b/source/blender/blenlib/intern/math_geom.c
@@ -6218,6 +6218,19 @@ bool is_quad_flip_v3_first_third_fast(const float v1[3],
   return dot_v3v3(cross_a, cross_b) > 0.0f;
 }
 
+bool is_quad_flip_v3_first_third_fast_with_normal(const float v1[3],
+                                                  const float v2[3],
+                                                  const float v3[3],
+                                                  const float v4[3],
+                                                  const float normal[3])
+{
+  float dir_v3v1[3], tangent[3];
+  sub_v3_v3v3(dir_v3v1, v3, v1);
+  cross_v3_v3v3(tangent, dir_v3v1, normal);
+  const float dot = dot_v3v3(v1, tangent);
+  return (dot_v3v3(v4, tangent) >= dot) || (dot_v3v3(v2, tangent) <= dot);
+}
+
 /**
  * Return the value which the distance between points will need to be scaled by,
  * to define a handle, given both points are on a perfect circle.
diff --git a/source/blender/bmesh/intern/bmesh_mesh_tessellate.c b/source/blender/bmesh/intern/bmesh_mesh_tessellate.c
index 18ec83057e2..c9b027474e1 100644
--- a/source/blender/bmesh/intern/bmesh_mesh_tessellate.c
+++ b/source/blender/bmesh/intern/bmesh_mesh_tessellate.c
@@ -95,8 +95,11 @@ BLI_INLINE void bmesh_calc_tessellation_for_face_impl(BMLoop *(*looptris)[3],
             efa->no, l_ptr_a[0]->v->co, l_ptr_a[1]->v->co, l_ptr_a[2]->v->co, l_ptr_b[2]->v->co);
       }
 
-      if (UNLIKELY(is_quad_flip_v3_first_third_fast(
-              l_ptr_a[0]->v->co, l_ptr_a[1]->v->co, l_ptr_a[2]->v->co, l_ptr_b[2]->v->co))) {
+      if (UNLIKELY(is_quad_flip_v3_first_third_fast_with_normal(l_ptr_a[0]->v->co,
+                                                                l_ptr_a[1]->v->co,
+                                                                l_ptr_a[2]->v->co,
+                                                                l_ptr_b[2]->v->co,
+                                                                efa->no))) {
         /* Flip out of degenerate 0-2 state. */
         l_ptr_a[2] = l_ptr_b[2];
         l_ptr_b[0] = l_ptr_a[1];