diff options
author | Nicholas Bishop <nicholasbishop@gmail.com> | 2012-05-15 00:58:59 +0400 |
---|---|---|
committer | Nicholas Bishop <nicholasbishop@gmail.com> | 2012-05-15 00:58:59 +0400 |
commit | f87fda5864df88786b8afea9f66babd220bf2c03 (patch) | |
tree | 98880a75fbc726e04f0397ad3ceee2817a25592c /source/blender/bmesh | |
parent | d8ae4b35f2c3503dfec548a028c354619b5a388c (diff) |
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.
Diffstat (limited to 'source/blender/bmesh')
-rw-r--r-- | source/blender/bmesh/operators/bmo_hull.c | 61 |
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")) { |