[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [42788] branches/carve_booleans: Carve booleans: triangulate non-planar faces before sending to Carve

Sergey Sharybin sergey.vfx at gmail.com
Wed Dec 21 10:27:33 CET 2011


Revision: 42788
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=42788
Author:   nazgul
Date:     2011-12-21 09:27:17 +0000 (Wed, 21 Dec 2011)
Log Message:
-----------
Carve booleans: triangulate non-planar faces before sending to Carve

Carve's intersection stuff doesn't currently deal with non-planar quad
faces, so temporary added workaround to splitting non-planar faces
into two triangles before sending mesh to Carve library.

Now workaround with epsilon doesn't need at all.

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	2011-12-21 08:41:13 UTC (rev 42787)
+++ branches/carve_booleans/intern/boolop/intern/BOP_CarveInterface.cpp	2011-12-21 09:27:17 UTC (rev 42788)
@@ -273,10 +273,6 @@
 	carve::interpolate::FaceAttr<uint> oface_num;
 	uint num_origfaces = 0;
 
-	/* TODO: with this magic value of epsilon carve doesn't fail in special cases,
-	         but is it our failure, filure of Carve or something else? */
-	carve::setEpsilon(1e-3);
-
 	switch (opType) {
 	case BOP_UNION:
 		op = carve::csg::CSG::UNION;

Modified: branches/carve_booleans/source/blender/modifiers/intern/MOD_boolean.c
===================================================================
--- branches/carve_booleans/source/blender/modifiers/intern/MOD_boolean.c	2011-12-21 08:41:13 UTC (rev 42787)
+++ branches/carve_booleans/source/blender/modifiers/intern/MOD_boolean.c	2011-12-21 09:27:17 UTC (rev 42788)
@@ -33,13 +33,17 @@
  */
 
 #include <stdio.h>
+#include <memory.h>
 
+#include "DNA_meshdata_types.h"
 #include "DNA_object_types.h"
 
 #include "BLI_utildefines.h"
+#include "BLI_math.h"
 
 
 #include "BKE_cdderivedmesh.h"
+#include "BKE_mesh.h"
 #include "BKE_modifier.h"
 
 #include "depsgraph_private.h"
@@ -47,6 +51,7 @@
 #include "MOD_boolean_util.h"
 #include "MOD_util.h"
 
+#define TRIANGULATE_WORKAROUND
 
 static void copyData(ModifierData *md, ModifierData *target)
 {
@@ -115,6 +120,134 @@
 	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 dot_v3v3(cross, v3) < 1e-4 * 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),
@@ -137,12 +270,23 @@
 		result = get_quick_derivedMesh(derivedData, dm, bmd->operation);
 
 		if(result == NULL) {
-			result = NewBooleanDerivedMesh(dm, bmd->object, derivedData, ob,
+			DerivedMesh *dm_tri, *derivedData_tri;
+
+			dm_tri = triangulateNonplanarFaces(dm);
+			derivedData_tri = triangulateNonplanarFaces(derivedData);
+
+			result = NewBooleanDerivedMesh(dm_tri, bmd->object, derivedData_tri, 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
-		* an error, so delete the modifier object */
+		   an error, so delete the modifier object */
 		if(result)
 			return result;
 		else




More information about the Bf-blender-cvs mailing list