Commit: a56e31c89c8a539e8726f5060eff3445064114a8
Author: Campbell Barton
Date: Wed Dec 17 11:31:33 2014 +0100
Branches: master
https://developer.blender.org/rBa56e31c89c8a539e8726f5060eff3445064114a8
Fix triangulating concave quads
Resulting triangles could be pointing in opposing directions.
===================================================================
M source/blender/blenlib/BLI_math_geom.h
M source/blender/blenlib/intern/math_geom.c
M source/blender/bmesh/intern/bmesh_polygon.c
===================================================================
diff --git a/source/blender/blenlib/BLI_math_geom.h
b/source/blender/blenlib/BLI_math_geom.h
index ba32b29..32678bd 100644
--- a/source/blender/blenlib/BLI_math_geom.h
+++ b/source/blender/blenlib/BLI_math_geom.h
@@ -77,6 +77,7 @@ float volume_tetrahedron_signed_v3(const float v1[3], const
float v2[3], const f
bool is_quad_convex_v3(const float v1[3], const float v2[3], const float
v3[3], const float v4[3]);
bool is_quad_convex_v2(const float v1[2], const float v2[2], const float
v3[2], const float v4[2]);
bool is_poly_convex_v2(const float verts[][2], unsigned int nr);
+int is_quad_flip_v3(const float v1[3], const float v2[3], const float v3[3],
const float v4[3]);
/********************************* Distance **********************************/
diff --git a/source/blender/blenlib/intern/math_geom.c
b/source/blender/blenlib/intern/math_geom.c
index 1c75a90..42aa24d 100644
--- a/source/blender/blenlib/intern/math_geom.c
+++ b/source/blender/blenlib/intern/math_geom.c
@@ -4016,3 +4016,31 @@ bool is_poly_convex_v2(const float verts[][2], unsigned
int nr)
return true;
}
+
+/**
+ * Check if either of the diagonals along this quad create flipped triangles
+ * (normals pointing away from eachother).
+ * - (1 << 0): (v1-v3) is flipped.
+ * - (1 << 1): (v2-v4) is flipped.
+ */
+int is_quad_flip_v3(const float v1[3], const float v2[3], const float v3[3],
const float v4[3])
+{
+ float d_12[3], d_23[3], d_34[3], d_41[3];
+ float cross_a[3], cross_b[3];
+ int ret = 0;
+
+ sub_v3_v3v3(d_12, v1, v2);
+ sub_v3_v3v3(d_23, v2, v3);
+ sub_v3_v3v3(d_34, v3, v4);
+ sub_v3_v3v3(d_41, v4, v1);
+
+ cross_v3_v3v3(cross_a, d_12, d_23);
+ cross_v3_v3v3(cross_b, d_34, d_41);
+ ret |= ((dot_v3v3(cross_a, cross_b) < 0.0f) << 0);
+
+ cross_v3_v3v3(cross_a, d_23, d_34);
+ cross_v3_v3v3(cross_b, d_41, d_12);
+ ret |= ((dot_v3v3(cross_a, cross_b) < 0.0f) << 1);
+
+ return ret;
+}
diff --git a/source/blender/bmesh/intern/bmesh_polygon.c
b/source/blender/bmesh/intern/bmesh_polygon.c
index a0f2f8c..f2c4261 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.c
+++ b/source/blender/bmesh/intern/bmesh_polygon.c
@@ -783,38 +783,39 @@ void BM_face_triangulate(
break;
}
case MOD_TRIANGULATE_QUAD_SHORTEDGE:
- {
- BMLoop *l_v3, *l_v4;
- float d1, d2;
-
- l_v1 = l_first;
- l_v2 = l_first->next->next;
- l_v3 = l_first->next;
- l_v4 = l_first->prev;
-
- d1 = len_squared_v3v3(l_v1->v->co, l_v2->v->co);
- d2 = len_squared_v3v3(l_v3->v->co, l_v4->v->co);
-
- if (d2 < d1) {
- l_v1 = l_v3;
- l_v2 = l_v4;
- }
- break;
- }
case MOD_TRIANGULATE_QUAD_BEAUTY:
default:
{
BMLoop *l_v3, *l_v4;
- float cost;
+ bool split_24;
l_v1 = l_first->next;
l_v2 = l_first->next->next;
l_v3 = l_first->prev;
l_v4 = l_first;
- cost = BM_verts_calc_rotate_beauty(l_v1->v,
l_v2->v, l_v3->v, l_v4->v, 0, 0);
+ if (quad_method ==
MOD_TRIANGULATE_QUAD_SHORTEDGE) {
+ float d1, d2;
+ d1 = len_squared_v3v3(l_v4->v->co,
l_v2->v->co);
+ d2 = len_squared_v3v3(l_v1->v->co,
l_v3->v->co);
+ split_24 = ((d2 - d1) > 0.0f);
+ }
+ else {
+ /* first check if the quad is concave
on either diagonal */
+ const int flip_flag =
is_quad_flip_v3(l_v1->v->co, l_v2->v->co, l_v3->v->co, l_v4->v->co);
+ if (UNLIKELY(flip_flag & (1 << 0))) {
+ split_24 = true;
+ }
+ else if (UNLIKELY(flip_flag & (1 <<
1))) {
+ split_24 = false;
+ }
+ else {
+ split_24 =
(BM_verts_calc_rotate_beauty(l_v1->v, l_v2->v, l_v3->v, l_v4->v, 0, 0) > 0.0f);
+ }
+ }
- if (cost > 0.0f) {
+ /* named confusingly, l_v1 is in fact the
second vertex */
+ if (split_24) {
l_v1 = l_v4;
//l_v2 = l_v2;
}
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
