[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [44548] trunk/blender/intern/boolop/intern /BOP_CarveInterface.cpp: Boolean modifier:

[Sergey Sharybin]

Revision: 44548
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=44548
Author:   nazgul
Date:     2012-02-29 13:48:19 +0000 (Wed, 29 Feb 2012)
Log Message:
-----------
Boolean modifier:

- Fixed convex quad detection (in some special cases non-convex quad was detecting as convex)
- Do not add faces with zero area to the output object.

This should resolve #30395: Degenerated triangles from BMesh + Difference

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-29 13:17:11 UTC (rev 44547)
+++ trunk/blender/intern/boolop/intern/BOP_CarveInterface.cpp	2012-02-29 13:48:19 UTC (rev 44548)
@@ -430,6 +430,14 @@
 	return poly;
 }
 
+static double triangleArea(carve::geom3d::Vector &v1, carve::geom3d::Vector &v2, carve::geom3d::Vector &v3)
+{
+	carve::geom3d::Vector a = v2 - v1;
+	carve::geom3d::Vector b = v3 - v1;
+
+	return carve::geom::cross(a, b).length();
+}
+
 static bool checkValidQuad(std::vector<MeshSet<3>::vertex_t> &vertex_storage, uint quad[4])
 {
 	carve::geom3d::Vector &v1 = vertex_storage[quad[0]].v;
@@ -465,12 +473,12 @@
 
 		carve::geom3d::Vector current_normal = carve::geom::cross(edges[i], edges[n]);
 
-		if (current_normal.length() > 1e-6) {
+		if (current_normal.length() > DBL_EPSILON) {
 			if (!normal_set) {
 				normal = current_normal;
 				normal_set = true;
 			}
-			else if (carve::geom::dot(normal, current_normal) < -1e-6) {
+			else if (carve::geom::dot(normal, current_normal) < 0) {
 				return false;
 			}
 		}
@@ -481,6 +489,10 @@
 		return false;
 	}
 
+	double area = triangleArea(v1, v2, v3) + triangleArea(v1, v3, v4);
+	if (area <= DBL_EPSILON)
+		return false;
+
 	return true;
 }
 
@@ -535,6 +547,20 @@
 	return 0;
 }
 
+static bool Carve_checkDegeneratedFace(MeshSet<3>::face_t *face)
+{
+	/* only tris and quads for now */
+	if (face->n_edges == 3) {
+		return triangleArea(face->edge->prev->vert->v, face->edge->vert->v, face->edge->next->vert->v) < DBL_EPSILON;
+	}
+	else if (face->n_edges == 4) {
+		return triangleArea(face->edge->vert->v, face->edge->next->vert->v, face->edge->next->next->vert->v) +
+		       triangleArea(face->edge->prev->vert->v, face->edge->vert->v, face->edge->next->next->vert->v) < DBL_EPSILON;
+	}
+
+	return false;
+}
+
 static BSP_CSGMesh *Carve_exportMesh(MeshSet<3>* &poly, carve::interpolate::FaceAttr<uint> &oface_num,
                                      uint num_origfaces)
 {
@@ -591,13 +617,6 @@
 
 			MeshSet<3>::face_t *f = *(poly->faceBegin() + findex);
 
-			// add all information except vertices to the output mesh
-			outputMesh->FaceSet().push_back(BSP_MFace());
-			BSP_MFace& outFace = outputMesh->FaceSet().back();
-			outFace.m_verts.clear();
-			outFace.m_plane.setValue(f->plane.N.v);
-			outFace.m_orig_face = orig;
-
 			// for each vertex of this face, check other faces containing
 			// that vertex to see if there is a neighbor also belonging to
 			// the original face
@@ -640,20 +659,36 @@
 				}
 			}
 
-			// if we merged faces, use the list of common vertices; otherwise
-			// use the faces's vertices
-			if (result) {
-				// make quat using verts stored in result
-				outFace.m_verts.push_back(quadverts[0]);
-				outFace.m_verts.push_back(quadverts[1]);
-				outFace.m_verts.push_back(quadverts[2]);
-				outFace.m_verts.push_back(quadverts[3]);
-			} else {
-				MeshSet<3>::face_t::edge_iter_t edge_iter = f->begin();
-				for (; edge_iter != f->end(); ++edge_iter) {
-					//int index = ofacevert_num.getAttribute(f, edge_iter.idx());
-					int index = vertexToIndex_map[edge_iter->vert];
-					outFace.m_verts.push_back( index );
+			bool degenerativeFace = false;
+
+			if (!result) {
+				/* merged triangles are already checked for degenerative quad */
+				degenerativeFace = Carve_checkDegeneratedFace(f);
+			}
+
+			if (!degenerativeFace) {
+				// add all information except vertices to the output mesh
+				outputMesh->FaceSet().push_back(BSP_MFace());
+				BSP_MFace& outFace = outputMesh->FaceSet().back();
+				outFace.m_verts.clear();
+				outFace.m_plane.setValue(f->plane.N.v);
+				outFace.m_orig_face = orig;
+
+				// if we merged faces, use the list of common vertices; otherwise
+				// use the faces's vertices
+				if (result) {
+					// make quat using verts stored in result
+					outFace.m_verts.push_back(quadverts[0]);
+					outFace.m_verts.push_back(quadverts[1]);
+					outFace.m_verts.push_back(quadverts[2]);
+					outFace.m_verts.push_back(quadverts[3]);
+				} else {
+					MeshSet<3>::face_t::edge_iter_t edge_iter = f->begin();
+					for (; edge_iter != f->end(); ++edge_iter) {
+						//int index = ofacevert_num.getAttribute(f, edge_iter.idx());
+						int index = vertexToIndex_map[edge_iter->vert];
+						outFace.m_verts.push_back( index );
+					}
 				}
 			}
 		}