[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [51966] trunk/blender/source/blender: fix [#33106] Decimate modifier/collapse give bad result

[Campbell Barton]

Revision: 51966
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=51966
Author:   campbellbarton
Date:     2012-11-07 09:28:59 +0000 (Wed, 07 Nov 2012)
Log Message:
-----------
fix [#33106] Decimate modifier/collapse give bad result
FLT_EPSILON was too small to use when checking if the edge collapse result is an error.

add invert_m3_m3_ex(), invert_m3_ex() functiosn which take an epsilon to check the determinant, saves calculating it twice per edge collapse.

Modified Paths:
--------------
    trunk/blender/source/blender/blenlib/BLI_math_matrix.h
    trunk/blender/source/blender/blenlib/BLI_quadric.h
    trunk/blender/source/blender/blenlib/intern/math_matrix.c
    trunk/blender/source/blender/blenlib/intern/quadric.c
    trunk/blender/source/blender/bmesh/intern/bmesh_decimate_collapse.c

Modified: trunk/blender/source/blender/blenlib/BLI_math_matrix.h
===================================================================
--- trunk/blender/source/blender/blenlib/BLI_math_matrix.h	2012-11-07 07:16:28 UTC (rev 51965)
+++ trunk/blender/source/blender/blenlib/BLI_math_matrix.h	2012-11-07 09:28:59 UTC (rev 51966)
@@ -98,6 +98,9 @@
 void mul_m4_fl(float R[4][4], float f);
 void mul_mat3_m4_fl(float R[4][4], float f);
 
+int invert_m3_ex(float m[3][3], const float epsilon);
+int invert_m3_m3_ex(float m1[3][3], float m2[3][3], const float epsilon);
+
 int invert_m3(float R[3][3]);
 int invert_m3_m3(float R[3][3], float A[3][3]);
 int invert_m4(float R[4][4]);

Modified: trunk/blender/source/blender/blenlib/BLI_quadric.h
===================================================================
--- trunk/blender/source/blender/blenlib/BLI_quadric.h	2012-11-07 07:16:28 UTC (rev 51965)
+++ trunk/blender/source/blender/blenlib/BLI_quadric.h	2012-11-07 09:28:59 UTC (rev 51966)
@@ -51,6 +51,6 @@
 
 /* solve */
 float BLI_quadric_evaluate(const Quadric *q, const float v[3]);
-int   BLI_quadric_optimize(const Quadric *q, float v[3]);
+int   BLI_quadric_optimize(const Quadric *q, float v[3], const float epsilon);
 
 #endif /* __BLI_QUADRIC_H__ */

Modified: trunk/blender/source/blender/blenlib/intern/math_matrix.c
===================================================================
--- trunk/blender/source/blender/blenlib/intern/math_matrix.c	2012-11-07 07:16:28 UTC (rev 51965)
+++ trunk/blender/source/blender/blenlib/intern/math_matrix.c	2012-11-07 09:28:59 UTC (rev 51966)
@@ -504,6 +504,51 @@
 			m1[i][j] = m2[i][j] - m3[i][j];
 }
 
+/* why not make this a standard part of the API? */
+static float determinant_m3_local(float m[3][3])
+{
+	return (m[0][0] * (m[1][1] * m[2][2] - m[1][2] * m[2][1]) -
+	        m[1][0] * (m[0][1] * m[2][2] - m[0][2] * m[2][1]) +
+	        m[2][0] * (m[0][1] * m[1][2] - m[0][2] * m[1][1]));
+}
+
+int invert_m3_ex(float m[3][3], const float epsilon)
+{
+	float tmp[3][3];
+	int success;
+
+	success = invert_m3_m3_ex(tmp, m, epsilon);
+	copy_m3_m3(m, tmp);
+
+	return success;
+}
+
+int invert_m3_m3_ex(float m1[3][3], float m2[3][3], const float epsilon)
+{
+	float det;
+	int a, b, success;
+
+	BLI_assert(epsilon >= 0.0f);
+
+	/* calc adjoint */
+	adjoint_m3_m3(m1, m2);
+
+	/* then determinant old matrix! */
+	det = determinant_m3_local(m2);
+
+	success = (fabsf(det) > epsilon);
+
+	if (LIKELY(det != 0.0f)) {
+		det = 1.0f / det;
+		for (a = 0; a < 3; a++) {
+			for (b = 0; b < 3; b++) {
+				m1[a][b] *= det;
+			}
+		}
+	}
+	return success;
+}
+
 int invert_m3(float m[3][3])
 {
 	float tmp[3][3];
@@ -524,17 +569,16 @@
 	adjoint_m3_m3(m1, m2);
 
 	/* then determinant old matrix! */
-	det = (m2[0][0] * (m2[1][1] * m2[2][2] - m2[1][2] * m2[2][1]) -
-	       m2[1][0] * (m2[0][1] * m2[2][2] - m2[0][2] * m2[2][1]) +
-	       m2[2][0] * (m2[0][1] * m2[1][2] - m2[0][2] * m2[1][1]));
+	det = determinant_m3_local(m2);
 
-	success = (det != 0);
+	success = (det != 0.0f);
 
-	if (det == 0) det = 1;
-	det = 1 / det;
-	for (a = 0; a < 3; a++) {
-		for (b = 0; b < 3; b++) {
-			m1[a][b] *= det;
+	if (LIKELY(det != 0.0f)) {
+		det = 1.0f / det;
+		for (a = 0; a < 3; a++) {
+			for (b = 0; b < 3; b++) {
+				m1[a][b] *= det;
+			}
 		}
 	}
 

Modified: trunk/blender/source/blender/blenlib/intern/quadric.c
===================================================================
--- trunk/blender/source/blender/blenlib/intern/quadric.c	2012-11-07 07:16:28 UTC (rev 51965)
+++ trunk/blender/source/blender/blenlib/intern/quadric.c	2012-11-07 09:28:59 UTC (rev 51966)
@@ -107,18 +107,13 @@
 	         q->d2);
 }
 
-int BLI_quadric_optimize(const Quadric *q, float v[3])
+int BLI_quadric_optimize(const Quadric *q, float v[3], const float epsilon)
 {
 	float m[3][3];
-	float det;
 
 	BLI_quadric_to_tensor_m3(q, m);
-	det = determinant_m3(m[0][0], m[0][1], m[0][2],
-	                     m[1][0], m[1][1], m[1][2],
-	                     m[2][0], m[2][1], m[2][2]);
 
-	if (fabsf(det) > FLT_EPSILON) {
-		invert_m3(m);
+	if (invert_m3_ex(m, epsilon)) {
 		BLI_quadric_to_vector_v3(q, v);
 		mul_m3_v3(m, v);
 		negate_v3(v);

Modified: trunk/blender/source/blender/bmesh/intern/bmesh_decimate_collapse.c
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_decimate_collapse.c	2012-11-07 07:16:28 UTC (rev 51965)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_decimate_collapse.c	2012-11-07 09:28:59 UTC (rev 51966)
@@ -51,6 +51,7 @@
 #define USE_SAFETY_CHECKS
 
 #define BOUNDARY_PRESERVE_WEIGHT 100.0f
+#define OPTIMIZE_EPS 0.01f  /* FLT_EPSILON is too small, see [#33106] */
 
 typedef enum CD_UseFlag {
 	CD_DO_VERT = (1 << 0),
@@ -123,7 +124,7 @@
 	                        &vquadrics[BM_elem_index_get(e->v2)]);
 
 
-	if (BLI_quadric_optimize(&q, optimize_co)) {
+	if (BLI_quadric_optimize(&q, optimize_co, OPTIMIZE_EPS)) {
 		return;  /* all is good */
 	}
 	else {