[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [43268] branches/carve_booleans: Carve booleans: merge faces which where split on triangulation

Sergey Sharybin sergey.vfx at gmail.com
Tue Jan 10 22:38:52 CET 2012


Revision: 43268
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=43268
Author:   nazgul
Date:     2012-01-10 21:38:51 +0000 (Tue, 10 Jan 2012)
Log Message:
-----------
Carve booleans: merge faces which where split on triangulation

- Removed triangulation code from modifier side.
  CSG stuff is already interpolating customdata layers for boolean operation
  result properly and adding extra interpolation stuff just adds some unwatnted
  noise to customdata layers. Much better to do triangulation on geometry level
  and interpolate needed faces only.
  This will improve speed a bit because of avoiding extra per-face cycle and
  avoiding extra interpolation stuff.
- Triangulation now happens on CarveInterface level.
  Doing triangulation on this level allows to merge triangles back into
  quads if they weren't split by boolean operation, so artists will have
  result mesh with the same topology on faces which aren't intersecting.
- Fixed order of vertices when merging triangles into quad after performing
  boolean operation.

Modified Paths:
--------------
    branches/carve_booleans/intern/boolop/intern/BOP_CarveInterface.cpp
    branches/carve_booleans/source/blender/modifiers/intern/MOD_boolean.c

Modified: branches/carve_booleans/intern/boolop/intern/BOP_CarveInterface.cpp
===================================================================
--- branches/carve_booleans/intern/boolop/intern/BOP_CarveInterface.cpp	2012-01-10 21:35:24 UTC (rev 43267)
+++ branches/carve_booleans/intern/boolop/intern/BOP_CarveInterface.cpp	2012-01-10 21:38:51 UTC (rev 43268)
@@ -41,7 +41,27 @@
 #define MAX(x,y) ((x)>(y)?(x):(y))
 #define MIN(x,y) ((x)<(y)?(x):(y))
 
-carve::poly::Polyhedron *Carve_addMesh(
+static int isFacePlanar(CSG_IFace &face, std::vector<carve::geom3d::Vector> &vertices)
+{
+	carve::geom3d::Vector v1, v2, v3, 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]];
+
+		cross = carve::geom::cross(v1, v2);
+
+		float production = carve::geom::dot(cross, v3);
+		float magnitude = 1e-6 * cross.length();
+
+		return fabs(production) < magnitude;
+	}
+
+	return 1;
+}
+
+static carve::poly::Polyhedron *Carve_addMesh(
 				 CSG_FaceIteratorDescriptor&   face_it,
 				 CSG_VertexIteratorDescriptor& vertex_it,
 				 carve::interpolate::FaceAttr<uint> &oface_num,
@@ -66,18 +86,43 @@
     std::vector<int> forig;
 	while (!face_it.Done(face_it.it)) {
 		face_it.Fill(face_it.it,&face);
-		f.push_back(face.vertex_number);
-		f.push_back(face.vertex_index[0]);
-		f.push_back(face.vertex_index[1]);
-		f.push_back(face.vertex_index[2]);
 
-		if (face.vertex_number == 4)
-			f.push_back(face.vertex_index[3]);
+		if (isFacePlanar(face, vertices)) {
+			f.push_back(face.vertex_number);
+			f.push_back(face.vertex_index[0]);
+			f.push_back(face.vertex_index[1]);
+			f.push_back(face.vertex_index[2]);
 
-		forig.push_back(face.orig_face);
-		++numfaces;
-		face_it.Step(face_it.it);
-		++num_origfaces;
+			if (face.vertex_number == 4)
+				f.push_back(face.vertex_index[3]);
+
+			forig.push_back(face.orig_face);
+			++numfaces;
+			face_it.Step(face_it.it);
+			++num_origfaces;
+		}
+		else {
+			f.push_back(3);
+			f.push_back(face.vertex_index[0]);
+			f.push_back(face.vertex_index[1]);
+			f.push_back(face.vertex_index[2]);
+
+			forig.push_back(face.orig_face);
+			++numfaces;
+
+			if (face.vertex_number == 4) {
+				f.push_back(3);
+				f.push_back(face.vertex_index[0]);
+				f.push_back(face.vertex_index[2]);
+				f.push_back(face.vertex_index[3]);
+
+				forig.push_back(face.orig_face);
+				++numfaces;
+			}
+
+			face_it.Step(face_it.it);
+			++num_origfaces;
+		}
 	}
 
     carve::poly::Polyhedron *poly = new carve::poly::Polyhedron (vertices, numfaces, f);
@@ -109,7 +154,7 @@
 
 	// locate the current vertex we're examining, and find the next and
 	// previous vertices based on the face windings
-	if( v1[0] == v ) { current = 0; p1 = 2; n1 = 1; }
+	if( v1[0] == v ) { current = 0; p1 = 1; n1 = 2; }
 	else if( v1[1] == v ) { current = 1; p1 = 0; n1 = 2; }
 	else { current = 2; p1 = 1; n1 = 0; }
 
@@ -138,7 +183,7 @@
 	return 0;
 }
 
-BSP_CSGMesh* Carve_exportMesh(carve::poly::Polyhedron* &poly,
+static BSP_CSGMesh* Carve_exportMesh(carve::poly::Polyhedron* &poly,
 				 carve::interpolate::FaceAttr<uint> &oface_num,
 				 uint num_origfaces )
 {

Modified: branches/carve_booleans/source/blender/modifiers/intern/MOD_boolean.c
===================================================================
--- branches/carve_booleans/source/blender/modifiers/intern/MOD_boolean.c	2012-01-10 21:35:24 UTC (rev 43267)
+++ branches/carve_booleans/source/blender/modifiers/intern/MOD_boolean.c	2012-01-10 21:38:51 UTC (rev 43268)
@@ -51,8 +51,6 @@
 #include "MOD_boolean_util.h"
 #include "MOD_util.h"
 
-#define TRIANGULATE_WORKAROUND
-
 static void copyData(ModifierData *md, ModifierData *target)
 {
 	BooleanModifierData *bmd = (BooleanModifierData*) md;
@@ -120,134 +118,6 @@
 	return result;
 }
 
-#ifdef TRIANGULATE_WORKAROUND
-static int isFacePlanar(MFace *face, MVert *mvert)
-{
-	float v1[3], v2[3], v3[3], cross[3];
-
-	if(face->v4) {
-		sub_v3_v3v3(v1, mvert[face->v2].co, mvert[face->v1].co);
-		sub_v3_v3v3(v2, mvert[face->v4].co, mvert[face->v1].co);
-		sub_v3_v3v3(v3, mvert[face->v3].co, mvert[face->v1].co);
-
-		cross_v3_v3v3(cross, v1, v2);
-		return fabsf(dot_v3v3(cross, v3)) < 1e-6 * len_v3(cross);
-	}
-
-	return 1;
-}
-
-static void interpFaceDate(DerivedMesh *dm, DerivedMesh *result, int src_index, int dst_index,
-                           int i1, int i2, int i3, int i4)
-{
-	float w[2][4][4];
-
-	memset(w, 0, sizeof(w));
-
-	w[i1/4][0][i1%4]= 1.0f;
-	w[i2/4][1][i2%4]= 1.0f;
-	w[i3/4][2][i3%4]= 1.0f;
-	if (i4 != -1)
-		w[i4/4][3][i4%4]= 1.0f;
-
-	DM_interp_face_data(dm, result, &src_index, NULL, w, 1, dst_index);
-}
-#endif
-
-static DerivedMesh *triangulateNonplanarFaces(DerivedMesh *dm)
-{
-#ifdef TRIANGULATE_WORKAROUND
-	DerivedMesh *result;
-	MVert *mvert;
-	MEdge *medge;
-	MFace *mface;
-	int i, numVerts, numEdges, numFaces;
-	int count = 0, triangulated = 0;
-
-	mvert = dm->getVertArray(dm);
-	medge = dm->getEdgeArray(dm);
-	mface = dm->getFaceArray(dm);
-
-	numVerts = dm->getNumVerts(dm);
-	numEdges = dm->getNumEdges(dm);
-	numFaces = dm->getNumFaces(dm);
-
-	for(i = 0; i < numFaces; i++) {
-		MFace *face = &mface[i];
-
-		if(!isFacePlanar(face, mvert))
-			count++;
-	}
-
-	if(!count)
-		return dm;
-
-	result = CDDM_from_template(dm, numVerts, numEdges + count, numFaces + count);
-
-	/* copy vertices */
-	for(i = 0; i < numVerts; i++) {
-		MVert *dest;
-
-		dest = CDDM_get_vert(result, i);
-
-		DM_copy_vert_data(dm, result, i, i, 1);
-		*dest = mvert[i];
-	}
-
-	/* copy edges */
-	for(i = 0; i < numEdges; i++) {
-		MEdge *dest;
-
-		dest = CDDM_get_edge(result, i);
-
-		DM_copy_edge_data(dm, result, i, i, 1);
-		*dest = medge[i];
-	}
-
-	/* copy faces */
-	for(i = 0; i < numFaces; i++) {
-		MFace *source = &mface[i];
-
-		if(!isFacePlanar(source, mvert)) {
-			MFace *dest;
-			MEdge *edge;
-
-			dest = CDDM_get_face(result, i);
-			interpFaceDate(dm, result, i, i, 0, 1, 2, 0);
-			*dest = *source;
-			dest->v4 = 0;
-			test_index_face(dest, &result->faceData, i, 3);
-
-			dest = CDDM_get_face(result, numFaces + triangulated);
-			interpFaceDate(dm, result, i, numFaces + triangulated, 0, 2, 3, 0);
-			*dest = *source;
-			dest->v2 = dest->v3;
-			dest->v3 = dest->v4;
-			dest->v4 = 0;
-			test_index_face(dest, &result->faceData, i, 3);
-
-			/* create diagonal edges */
-			edge = CDDM_get_edge(result, numEdges + triangulated);
-			edge->v1 = source->v3;
-			edge->v2 = source->v1;
-
-			triangulated++;
-		}
-		else {
-			MFace *dest;
-			dest = CDDM_get_face(result, i);
-
-			DM_copy_face_data(dm, result, i, i, 1);
-			*dest = *source;
-		}
-	}
-
-	return result;
-#else
-	return dm;
-#endif
-}
-
 static DerivedMesh *applyModifier(ModifierData *md, Object *ob,
 						DerivedMesh *derivedData,
 						int UNUSED(useRenderParams),
@@ -270,19 +140,8 @@
 		result = get_quick_derivedMesh(derivedData, dm, bmd->operation);
 
 		if(result == NULL) {
-			DerivedMesh *dm_tri, *derivedData_tri;
-
-			dm_tri = triangulateNonplanarFaces(dm);
-			derivedData_tri = triangulateNonplanarFaces(derivedData);
-
-			result = NewBooleanDerivedMesh(dm_tri, bmd->object, derivedData_tri, ob,
+			result = NewBooleanDerivedMesh(dm, bmd->object, derivedData, ob,
 					1 + bmd->operation);
-
-			if(dm_tri != dm)
-				dm_tri->release(dm_tri);
-
-			if(derivedData_tri != derivedData)
-				derivedData_tri->release(derivedData_tri);
 		}
 
 		/* if new mesh returned, return it; otherwise there was



More information about the Bf-blender-cvs mailing list