Fix precision issue for bmo_hull.interior_geom output slot.

Keep track of interior verts during the hull build to avoid
imprecise floating-point test afterward.

1 files changed, 25 insertions, 36 deletions

diff --git a/source/blender/bmesh/operators/bmo_hull.c b/source/blender/bmesh/operators/bmo_hull.c
index 1cd095f72e4..0b5a06e471e 100644
--- a/source/blender/bmesh/operators/bmo_hull.c
+++ b/source/blender/bmesh/operators/bmo_hull.c
@@ -119,16 +119,21 @@ static void expand_boundary_edges(ListBase *edges, BLI_mempool *edge_pool,
 
 /*************************** Hull Triangles ***************************/
 
-static void hull_add_triangle(GHash *hull_triangles, BLI_mempool *pool,
+static void hull_add_triangle(BMesh *bm, GHash *hull_triangles, BLI_mempool *pool,
                               BMVert *v1, BMVert *v2, BMVert *v3)
 {
 	HullTriangle *t;
+	int i;
 
 	t = BLI_mempool_calloc(pool);
 	t->v[0] = v1;
 	t->v[1] = v2;
 	t->v[2] = v3;
 
+	/* Mark triangles vertices as not interior */
+	for (i = 0; i < 3; i++)
+		BMO_elem_flag_disable(bm, t->v[i], HULL_FLAG_INTERIOR_ELE);
+
 	BLI_ghash_insert(hull_triangles, t, NULL);
 	normal_tri_v3(t->no, v1->co, v2->co, v3->co);
 }
@@ -163,27 +168,11 @@ static GHash *hull_triangles_v_outside(GHash *hull_triangles, const BMVert *v)
 	return outside;
 }
 
-/* Similar to above, but just get true/false rather than triangles */
-static int hull_test_v_outside(GHash *hull_triangles, const BMVert *v)
-{
-	GHashIterator iter;
-
-	GHASH_ITER (iter, hull_triangles) {
-		HullTriangle *t = BLI_ghashIterator_getKey(&iter);
-		
-		if (hull_point_tri_side(t, v->co) >= 0)
-			return TRUE;
-	}
-
-	return FALSE;
-}
-
-
 /* For vertex 'v', find which triangles must be deleted to extend the
  * hull; find the boundary edges of that hole so that it can be filled
  * with connections to the new vertex, and update the hull_triangles
  * to delete the marked triangles */
-static void add_point(GHash *hull_triangles, BLI_mempool *hull_pool,
+static void add_point(BMesh *bm, GHash *hull_triangles, BLI_mempool *hull_pool,
                       BLI_mempool *edge_pool, GHash *outside, BMVert *v)
 {
 	ListBase edges = {NULL, NULL};
@@ -192,7 +181,13 @@ static void add_point(GHash *hull_triangles, BLI_mempool *hull_pool,
 
 	GHASH_ITER (iter, outside) {
 		HullTriangle *t = BLI_ghashIterator_getKey(&iter);
+		int i;
+		
 		expand_boundary_edges(&edges, edge_pool, t);
+
+		/* Mark triangle's vertices as interior */
+		for (i = 0; i < 3; i++)
+			BMO_elem_flag_enable(bm, t->v[i], HULL_FLAG_INTERIOR_ELE);
 		
 		/* Delete the triangle */
 		BLI_ghash_remove(hull_triangles, t, NULL, NULL);
@@ -202,7 +197,7 @@ static void add_point(GHash *hull_triangles, BLI_mempool *hull_pool,
 	/* Fill hole boundary with triangles to new point */
 	for (e = edges.first; e; e = next) {
 		next = e->next;
-		hull_add_triangle(hull_triangles, hull_pool, e->v[0], e->v[1], v);
+		hull_add_triangle(bm, hull_triangles, hull_pool, e->v[0], e->v[1], v);
 		BLI_mempool_free(edge_pool, e);
 	}
 }
@@ -352,7 +347,7 @@ static void hull_final_edges_free(HullFinalEdges *final_edges)
 
 /************************* Initial Tetrahedron ************************/
 
-static void hull_add_tetrahedron(GHash *hull_triangles, BLI_mempool *pool,
+static void hull_add_tetrahedron(BMesh *bm, GHash *hull_triangles, BLI_mempool *pool,
                                  BMVert *tetra[4])
 {
 	float center[3];
@@ -379,7 +374,7 @@ static void hull_add_tetrahedron(GHash *hull_triangles, BLI_mempool *pool,
 		if (dot_v3v3(no, d) > 0)
 			SWAP(BMVert *, v1, v3);
 
-		hull_add_triangle(hull_triangles, pool, v1, v2, v3);
+		hull_add_triangle(bm, hull_triangles, pool, v1, v2, v3);
 	}
 }
 
@@ -540,23 +535,12 @@ static void hull_remove_overlapping(BMesh *bm, GHash *hull_triangles,
 }
 
 static void hull_mark_interior_elements(BMesh *bm, BMOperator *op,
-                                        GHash *hull_triangles,
                                         HullFinalEdges *final_edges)
 {
-	BMVert *v;
 	BMEdge *e;
 	BMFace *f;
 	BMOIter oiter;
 
-	/* Check all input vertices again to see if they are actually part
-	   of the hull */
-	BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
-		if (!hull_test_v_outside(hull_triangles, v)) {
-			/* Mark for 'interior_verts' slot */
-			BMO_elem_flag_enable(bm, v, HULL_FLAG_INTERIOR_ELE);
-		}
-	}
-
 	/* Check for interior edges too */
 	BMO_ITER (e, &oiter, bm, op, "input", BM_EDGE) {
 		if (!hull_final_edges_lookup(final_edges, e->v1, e->v2))
@@ -689,8 +673,13 @@ void bmo_convex_hull_exec(BMesh *bm, BMOperator *op)
 	}
 
 	/* Tag input elements */
-	BMO_ITER (ele, &oiter, bm, op, "input", BM_ALL)
+	BMO_ITER (ele, &oiter, bm, op, "input", BM_ALL) {
 		BMO_elem_flag_enable(bm, ele, HULL_FLAG_INPUT);
+		
+		/* Mark all vertices as interior to begin with */
+		if (ele->head.htype == BM_VERT)
+			BMO_elem_flag_enable(bm, ele, HULL_FLAG_INTERIOR_ELE);
+	}
 
 	edge_pool = BLI_mempool_create(sizeof(HullBoundaryEdge), 128, 128, 0);
 	hull_pool = BLI_mempool_create(sizeof(HullTriangle), 128, 128, 0);
@@ -699,7 +688,7 @@ void bmo_convex_hull_exec(BMesh *bm, BMOperator *op)
 	                               "hull_triangles");
 
 	/* Add tetrahedron triangles */
-	hull_add_tetrahedron(hull_triangles, hull_pool, tetra);
+	hull_add_tetrahedron(bm, hull_triangles, hull_pool, tetra);
 
 	/* Expand hull to cover new vertices outside the existing hull */
 	BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
@@ -707,7 +696,7 @@ void bmo_convex_hull_exec(BMesh *bm, BMOperator *op)
 			GHash *outside = hull_triangles_v_outside(hull_triangles, v);
 			if (BLI_ghash_size(outside)) {
 				/* Expand hull and delete interior triangles */
-				add_point(hull_triangles, hull_pool, edge_pool, outside, v);
+				add_point(bm, hull_triangles, hull_pool, edge_pool, outside, v);
 			}
 			BLI_ghash_free(outside, NULL, NULL);
 		}
@@ -716,7 +705,7 @@ void bmo_convex_hull_exec(BMesh *bm, BMOperator *op)
 	BLI_mempool_destroy(edge_pool);
 	final_edges = hull_final_edges(hull_triangles);
 	
-	hull_mark_interior_elements(bm, op, hull_triangles, final_edges);
+	hull_mark_interior_elements(bm, op, final_edges);
 
 	/* Remove hull triangles covered by an existing face */
 	if (BMO_slot_bool_get(op, "use_existing_faces")) {