[Bf-blender-cvs] [c33fb00] master: Fix for triangulate and beauty-fill
Campbell Barton
noreply at git.blender.org
Mon Dec 2 01:53:12 CET 2013
Commit: c33fb00c287a05424bd7f99051ab02fa322aeb02
Author: Campbell Barton
Date: Mon Dec 2 11:49:18 2013 +1100
http://developer.blender.org/rBc33fb00c287a05424bd7f99051ab02fa322aeb02
Fix for triangulate and beauty-fill
- could crash if triangulate attempted to create an existing face.
- tagging edges to rotate was unreliable, don't do this anymore.
now check if edge is in the array passed to the beauty function.
===================================================================
M source/blender/bmesh/intern/bmesh_polygon.c
M source/blender/bmesh/intern/bmesh_polygon.h
M source/blender/bmesh/operators/bmo_beautify.c
M source/blender/bmesh/tools/bmesh_beautify.c
M source/blender/bmesh/tools/bmesh_triangulate.c
===================================================================
diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c
index 2a7b32d..5708c77 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.c
+++ b/source/blender/bmesh/intern/bmesh_polygon.c
@@ -764,17 +764,22 @@ bool BM_face_point_inside_test(BMFace *f, const float co[3])
* \brief BMESH TRIANGULATE FACE
*
* Breaks all quads and ngons down to triangles.
- * It uses scanfill for the ngons splitting, and
+ * It uses polyfill for the ngons splitting, and
* the beautify operator when use_beauty is true.
*
* \param r_faces_new if non-null, must be an array of BMFace pointers,
* with a length equal to (f->len - 3). It will be filled with the new
* triangles (not including the original triangle).
*
+ * \note The number of faces is _almost_ always (f->len - 3),
+ * However there may be faces that already occupying the
+ * triangles we would make, so the caller must check \a r_faces_new_tot.
+ *
* \note use_tag tags new flags and edges.
*/
void BM_face_triangulate(BMesh *bm, BMFace *f,
BMFace **r_faces_new,
+ int *r_faces_new_tot,
MemArena *sf_arena,
const int quad_method,
const int ngon_method,
@@ -790,6 +795,9 @@ void BM_face_triangulate(BMesh *bm, BMFace *f,
BLI_assert(BM_face_is_normal_valid(f));
+ /* ensure both are valid or NULL */
+ BLI_assert((r_faces_new == NULL) == (r_faces_new_tot == NULL));
+
if (f->len == 4) {
BMVert *v1, *v2;
l_first = BM_FACE_FIRST_LOOP(f);
@@ -873,8 +881,6 @@ void BM_face_triangulate(BMesh *bm, BMFace *f,
const int last_tri = f->len - 3;
int i;
- //BLI_assert(BM_face_is_normal_valid(f));
-
axis_dominant_v3_to_m3(axis_mat, f->no);
for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f); i < f->len; i++, l_iter = l_iter->next) {
@@ -935,10 +941,8 @@ void BM_face_triangulate(BMesh *bm, BMFace *f,
if (is_new_edge) {
if (use_beauty) {
- BM_elem_index_set(e, edge_array_len); /* set_dirty */
edge_array[edge_array_len] = e;
edge_array_len++;
- BM_elem_flag_enable(e, BM_ELEM_TAG);
}
if (use_tag) {
@@ -961,7 +965,6 @@ void BM_face_triangulate(BMesh *bm, BMFace *f,
if (use_beauty) {
BLI_assert(edge_array_len <= orig_f_len - 3);
- bm->elem_index_dirty |= BM_EDGE;
BM_mesh_beautify_fill(bm, edge_array, edge_array_len, 0, 0, 0, 0);
if (r_faces_new) {
@@ -1012,7 +1015,7 @@ void BM_face_triangulate(BMesh *bm, BMFace *f,
#undef FACE_USED_SET
/* nf_i doesn't include the last face */
- BLI_assert(nf_i == orig_f_len - 3);
+ BLI_assert(nf_i <= orig_f_len - 3);
/* we can't delete the real face, because some of the callers expect it to remain valid.
* so swap data and delete the last created tri */
@@ -1021,6 +1024,10 @@ void BM_face_triangulate(BMesh *bm, BMFace *f,
}
}
}
+
+ if (r_faces_new_tot) {
+ *r_faces_new_tot = nf_i;
+ }
}
/**
diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h
index f620350..f408947 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.h
+++ b/source/blender/bmesh/intern/bmesh_polygon.h
@@ -54,7 +54,9 @@ void BM_vert_normal_update_all(BMVert *v) ATTR_NONNULL();
void BM_face_normal_flip(BMesh *bm, BMFace *f) ATTR_NONNULL();
bool BM_face_point_inside_test(BMFace *f, const float co[3]) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();
-void BM_face_triangulate(BMesh *bm, BMFace *f, BMFace **newfaces,
+void BM_face_triangulate(BMesh *bm, BMFace *f,
+ BMFace **r_faces_new,
+ int *r_faces_new_tot,
struct MemArena *sf_arena,
const int quad_method, const int ngon_method,
const bool use_tag) ATTR_NONNULL(1, 2);
diff --git a/source/blender/bmesh/operators/bmo_beautify.c b/source/blender/bmesh/operators/bmo_beautify.c
index d9ab30b..4a292c3 100644
--- a/source/blender/bmesh/operators/bmo_beautify.c
+++ b/source/blender/bmesh/operators/bmo_beautify.c
@@ -71,13 +71,10 @@ void bmo_beautify_fill_exec(BMesh *bm, BMOperator *op)
BMO_elem_flag_test(bm, e->l->f, FACE_MARK) &&
BMO_elem_flag_test(bm, e->l->radial_next->f, FACE_MARK))
{
- BM_elem_index_set(e, edge_array_len); /* set_dirty */
- BM_elem_flag_enable(e, BM_ELEM_TAG);
edge_array[edge_array_len] = e;
edge_array_len++;
}
}
- bm->elem_index_dirty |= BM_EDGE;
BM_mesh_beautify_fill(bm, edge_array, edge_array_len, flag, method, ELE_NEW, FACE_MARK | ELE_NEW);
diff --git a/source/blender/bmesh/tools/bmesh_beautify.c b/source/blender/bmesh/tools/bmesh_beautify.c
index cad5e1b..26d02cf 100644
--- a/source/blender/bmesh/tools/bmesh_beautify.c
+++ b/source/blender/bmesh/tools/bmesh_beautify.c
@@ -294,11 +294,22 @@ static float bm_edge_calc_rotate_beauty(const BMEdge *e, const short flag, const
/* -------------------------------------------------------------------- */
/* Update the edge cost of rotation in the heap */
+BLI_INLINE bool edge_in_array(const BMEdge *e, const BMEdge **edge_array, const int edge_array_len)
+{
+ const int index = BM_elem_index_get(e);
+ return ((index >= 0) &&
+ (index < edge_array_len) &&
+ (e == edge_array[index]));
+}
+
/* recalc an edge in the heap (surrounding geometry has changed) */
static void bm_edge_update_beauty_cost_single(BMEdge *e, Heap *eheap, HeapNode **eheap_table, GSet **edge_state_arr,
+ /* only for testing the edge is in the array */
+ const BMEdge **edge_array, const int edge_array_len,
+
const short flag, const short method)
{
- if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
+ if (edge_in_array(e, edge_array, edge_array_len)) {
const int i = BM_elem_index_get(e);
GSet *e_state_set = edge_state_arr[i];
@@ -335,26 +346,38 @@ static void bm_edge_update_beauty_cost_single(BMEdge *e, Heap *eheap, HeapNode *
/* we have rotated an edge, tag other edges and clear this one */
static void bm_edge_update_beauty_cost(BMEdge *e, Heap *eheap, HeapNode **eheap_table, GSet **edge_state_arr,
+ const BMEdge **edge_array, const int edge_array_len,
+ /* only for testing the edge is in the array */
const short flag, const short method)
{
- BMLoop *l;
+ int i;
+
+ BMEdge *e_arr[4] = {
+ e->l->next->e,
+ e->l->prev->e,
+ e->l->radial_next->next->e,
+ e->l->radial_next->prev->e,
+ };
+
BLI_assert(e->l->f->len == 3 &&
e->l->radial_next->f->len == 3);
- l = e->l;
- bm_edge_update_beauty_cost_single(l->next->e, eheap, eheap_table, edge_state_arr, flag, method);
- bm_edge_update_beauty_cost_single(l->prev->e, eheap, eheap_table, edge_state_arr, flag, method);
- l = l->radial_next;
- bm_edge_update_beauty_cost_single(l->next->e, eheap, eheap_table, edge_state_arr, flag, method);
- bm_edge_update_beauty_cost_single(l->prev->e, eheap, eheap_table, edge_state_arr, flag, method);
+ BLI_assert(BM_edge_face_count(e) == 2);
+
+ for (i = 0; i < 4; i++) {
+ bm_edge_update_beauty_cost_single(
+ e_arr[i],
+ eheap, eheap_table, edge_state_arr,
+ edge_array, edge_array_len,
+ flag, method);
+ }
}
/* -------------------------------------------------------------------- */
/* Beautify Fill */
/**
- * \note All edges in \a edge_array must be tagged and
- * have their index values set according to their position in the array.
+ * \note This function sets the edge indicies to invalid values.
*/
void BM_mesh_beautify_fill(BMesh *bm, BMEdge **edge_array, const int edge_array_len,
const short flag, const short method,
@@ -384,14 +407,22 @@ void BM_mesh_beautify_fill(BMesh *bm, BMEdge **edge_array, const int edge_array_
else {
eheap_table[i] = NULL;
}
+
+ BM_elem_index_set(e, i); /* set_dirty */
}
+ bm->elem_index_dirty |= BM_EDGE;
while (BLI_heap_is_empty(eheap) == false) {
BMEdge *e = BLI_heap_popmin(eheap);
i = BM_elem_index_get(e);
eheap_table[i] = NULL;
+ BLI_assert(BM_edge_face_count(e) == 2);
+
e = BM_edge_rotate(bm, e, false, BM_EDGEROT_CHECK_EXISTS);
+
+ BLI_assert(e == NULL || BM_edge_face_count(e) == 2);
+
if (LIKELY(e)) {
GSet *e_state_set = edge_state_arr[i];
@@ -414,7 +445,9 @@ void BM_mesh_beautify_fill(BMesh *bm, BMEdge **edge_array, const int edge_array_
BM_elem_index_set(e, i);
/* recalculate faces connected on the heap */
- bm_edge_update_beauty_cost(e, eheap, eheap_table, edge_state_arr, flag, method);
+ bm_edge_update_beauty_cost(e, eheap, eheap_table, edge_state_arr,
+ (const BMEdge **)edge_array, edge_array_len,
+ flag, method);
/* update flags */
if (oflag_edge)
diff --git a/source/blender/bmesh/tools/bmesh_triangulate.c b/source/blender/bmesh/tools/bmesh_triangulate.c
index 59c2aa4..446c03a 100644
--- a/source/blender/bmesh/tools/bmesh_triangulate.c
+++ b/source/blender/bmesh/tools/bmesh_triangulate.c
@@ -47,13 +47,13 @@ static void bm_face_triangulate_mapping(BMesh *bm, BMFace *face, MemArena *sf_ar
const bool use_tag,
BMOperator *op, BMOpSlot *slot_facemap_out)
{
- const int faces_array_tot = face->len - 3;
+ int faces_array_tot = face->len - 3;
BMFace **faces_array = BLI_array_alloca(faces_array, faces_array_tot);
BLI_assert(face->len > 3);
- BM_face_triangulate(bm, face, faces_array, sf_arena, quad_method, ngon_method, use_tag);
+ BM_face_triangulate(bm, face, faces_array, &faces_array_tot, sf_arena, quad_method, ngon_method, use_tag);
- if (faces_array) {
+ if (faces_array_tot) {
int i;
BMO_slot_map_elem_insert(op, slot_facemap_out, face, face);
for (i = 0; i < faces_array_tot; i++) {
@@ -87,7 +87,7 @@ void BM_mesh_triangulate(BMesh *bm, const int quad_method, const int ngon_method
BM_IT
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list