[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [44089] trunk/blender/intern/boolop/intern /BOP_CarveInterface.cpp: Fix #30159: Boolean modifier creating non-concave faces

Sergey Sharybin sergey.vfx at gmail.com
Mon Feb 13 14:23:24 CET 2012


Revision: 44089
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=44089
Author:   nazgul
Date:     2012-02-13 13:23:23 +0000 (Mon, 13 Feb 2012)
Log Message:
-----------
Fix #30159: Boolean modifier creating non-concave faces

Issue was caused by merging triangles into quads policy which used to think
triangulation of non-planar/non-concave quads happens by 1-3 diagonal which
isn't actually correct in some OpenGL implementations.

Added check for non-concave faces when merging triangles. It will work fine if
original faces are flat. In case if original faces aren't flat this check might
fail and triangulate face when it's not actually needed or merge triangles in
a way which leads to OpenGL artifacts.

Modified Paths:
--------------
    trunk/blender/intern/boolop/intern/BOP_CarveInterface.cpp

Modified: trunk/blender/intern/boolop/intern/BOP_CarveInterface.cpp
===================================================================
--- trunk/blender/intern/boolop/intern/BOP_CarveInterface.cpp	2012-02-13 12:57:46 UTC (rev 44088)
+++ trunk/blender/intern/boolop/intern/BOP_CarveInterface.cpp	2012-02-13 13:23:23 UTC (rev 44089)
@@ -46,24 +46,31 @@
 #define MAX(x,y) ((x)>(y)?(x):(y))
 #define MIN(x,y) ((x)<(y)?(x):(y))
 
-static int isFacePlanar(CSG_IFace &face, std::vector<carve::geom3d::Vector> &vertices)
+static bool isQuadPlanar(carve::geom3d::Vector &v1, carve::geom3d::Vector &v2,
+                         carve::geom3d::Vector &v3, carve::geom3d::Vector &v4)
 {
-	carve::geom3d::Vector v1, v2, v3, cross;
+	carve::geom3d::Vector vec1, vec2, vec3, cross;
 
-	if (face.vertex_number == 4) {
-		v1 = vertices[face.vertex_index[1]] - vertices[face.vertex_index[0]];
-		v2 = vertices[face.vertex_index[3]] - vertices[face.vertex_index[0]];
-		v3 = vertices[face.vertex_index[2]] - vertices[face.vertex_index[0]];
+	vec1 = v2 - v1;
+	vec2 = v4 - v1;
+	vec3 = v3 - v1;
 
-		cross = carve::geom::cross(v1, v2);
+	cross = carve::geom::cross(vec1, vec2);
 
-		float production = carve::geom::dot(cross, v3);
-		float magnitude = 1e-6 * cross.length();
+	float production = carve::geom::dot(cross, vec3);
+	float magnitude = 1e-6 * cross.length();
 
-		return fabs(production) < magnitude;
+	return fabs(production) < magnitude;
+}
+
+static bool isFacePlanar(CSG_IFace &face, std::vector<carve::geom3d::Vector> &vertices)
+{
+	if (face.vertex_number == 4) {
+		return isQuadPlanar(vertices[face.vertex_index[0]], vertices[face.vertex_index[1]],
+		                    vertices[face.vertex_index[2]], vertices[face.vertex_index[3]]);
 	}
 
-	return 1;
+	return true;
 }
 
 static void Carve_copyMeshes(std::vector<MeshSet<3>::mesh_t*> &meshes, std::vector<MeshSet<3>::mesh_t*> &new_meshes)
@@ -396,8 +403,63 @@
 	return poly;
 }
 
+static bool checkValidQuad(std::vector<MeshSet<3>::vertex_t> &vertex_storage, uint quad[4])
+{
+	carve::geom3d::Vector &v1 = vertex_storage[quad[0]].v;
+	carve::geom3d::Vector &v2 = vertex_storage[quad[1]].v;
+	carve::geom3d::Vector &v3 = vertex_storage[quad[2]].v;
+	carve::geom3d::Vector &v4 = vertex_storage[quad[3]].v;
+
+#if 0
+	/* disabled for now to prevent initially non-planar be triangulated
+	 * in theory this might cause some artifacts if intersections happens by non-planar
+	 * non-concave quad, but in practice it's acceptable */
+	if (!isQuadPlanar(v1, v2, v3, v4)) {
+		/* non-planar faces better not be merged because of possible differences in triangulation
+		 * of non-planar faces in opengl and renderer */
+		return false;
+	}
+#endif
+
+	carve::geom3d::Vector edges[4];
+	carve::geom3d::Vector normal;
+	bool normal_set = false;
+
+	edges[0] = v2 - v1;
+	edges[1] = v3 - v2;
+	edges[2] = v4 - v3;
+	edges[3] = v1 - v4;
+
+	for (int i = 0; i < 4; i++) {
+		int n = i + 1;
+
+		if (n == 4)
+			n = 0;
+
+		carve::geom3d::Vector current_normal = carve::geom::cross(edges[i], edges[n]);
+
+		if (current_normal.length() > 1e-6) {
+			if (!normal_set) {
+				normal = current_normal;
+				normal_set = true;
+			}
+			else if (carve::geom::dot(normal, current_normal) < -1e-6) {
+				return false;
+			}
+		}
+	}
+
+	if (!normal_set) {
+		/* normal wasn't set means face is degraded and better merge it in such way */
+		return false;
+	}
+
+	return true;
+}
+
 // check whether two faces share an edge, and if so merge them
 static uint quadMerge(std::map<MeshSet<3>::vertex_t*, uint> *vertexToIndex_map,
+					  std::vector<MeshSet<3>::vertex_t> &vertex_storage,
                       MeshSet<3>::face_t *f1, MeshSet<3>::face_t *f2,
                       uint v, uint quad[4])
 {
@@ -432,7 +494,7 @@
 		quad[2] = v1[p1];
 		quad[3] = v2[p2];
 
-		return 1;
+		return checkValidQuad(vertex_storage, quad);
 	}
 	else if (v1[n1] == v2[p2]) {
 		quad[0] = v1[current];
@@ -440,7 +502,7 @@
 		quad[2] = v1[n1];
 		quad[3] = v1[p1];
 
-		return 1;
+		return checkValidQuad(vertex_storage, quad);
 	}
 
 	return 0;
@@ -539,7 +601,7 @@
 					if (other_index == fl.size()) continue;
 
 					// see if the faces share an edge
-					result = quadMerge(&vertexToIndex_map, f, f2, v, quadverts);
+					result = quadMerge(&vertexToIndex_map, poly->vertex_storage, f, f2, v, quadverts);
 					// if faces can be merged, then remove the other face
 					// from the current set
 					if (result) {




More information about the Bf-blender-cvs mailing list