[Bf-blender-cvs] [0f769af] master: Fix T46692: Triangulate creates duplicate faces
Campbell Barton
noreply at git.blender.org
Thu Nov 5 15:22:08 CET 2015
Commit: 0f769afe07f96efa7ec6325453c4f04ea391f112
Author: Campbell Barton
Date: Fri Nov 6 01:05:38 2015 +1100
Branches: master
https://developer.blender.org/rB0f769afe07f96efa7ec6325453c4f04ea391f112
Fix T46692: Triangulate creates duplicate faces
Caused a crash in dyntopo.
===================================================================
M source/blender/bmesh/intern/bmesh_opdefines.c
M source/blender/bmesh/intern/bmesh_polygon.c
M source/blender/bmesh/intern/bmesh_polygon.h
M source/blender/bmesh/operators/bmo_connect_concave.c
M source/blender/bmesh/operators/bmo_triangulate.c
M source/blender/bmesh/tools/bmesh_triangulate.c
M source/blender/bmesh/tools/bmesh_triangulate.h
M source/blender/editors/sculpt_paint/sculpt.c
M source/blender/modifiers/intern/MOD_triangulate.c
===================================================================
diff --git a/source/blender/bmesh/intern/bmesh_opdefines.c b/source/blender/bmesh/intern/bmesh_opdefines.c
index f3496b3..d92bdc6 100644
--- a/source/blender/bmesh/intern/bmesh_opdefines.c
+++ b/source/blender/bmesh/intern/bmesh_opdefines.c
@@ -1171,6 +1171,7 @@ static BMOpDefine bmo_triangulate_def = {
{{"edges.out", BMO_OP_SLOT_ELEMENT_BUF, {BM_EDGE}},
{"faces.out", BMO_OP_SLOT_ELEMENT_BUF, {BM_FACE}},
{"face_map.out", BMO_OP_SLOT_MAPPING, {(int)BMO_OP_SLOT_SUBTYPE_MAP_ELEM}},
+ {"face_map_double.out", BMO_OP_SLOT_MAPPING, {(int)BMO_OP_SLOT_SUBTYPE_MAP_ELEM}}, /* duplicate faces */
{{'\0'}},
},
bmo_triangulate_exec,
diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c
index 5bbade2..56d109f 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.c
+++ b/source/blender/bmesh/intern/bmesh_polygon.c
@@ -38,6 +38,7 @@
#include "BLI_memarena.h"
#include "BLI_polyfill2d.h"
#include "BLI_polyfill2d_beautify.h"
+#include "BLI_linklist.h"
#include "bmesh.h"
#include "bmesh_tools.h"
@@ -767,6 +768,12 @@ bool BM_face_point_inside_test(const BMFace *f, const float co[3])
* with a length equal to (f->len - 3). It will be filled with the new
* triangles (not including the original triangle).
*
+ * \param r_faces_double: When newly created faces are duplicates of existing faces, they're added to this list.
+ * Caller must handle de-duplication.
+ * This is done because its possible _all_ faces exist already,
+ * and in that case we would have to remove all faces including the one passed,
+ * which causes complications adding/removing faces while looking over them.
+ *
* \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.
@@ -779,6 +786,7 @@ void BM_face_triangulate(
int *r_faces_new_tot,
BMEdge **r_edges_new,
int *r_edges_new_tot,
+ LinkNode **r_faces_double,
const int quad_method,
const int ngon_method,
const bool use_tag,
@@ -789,12 +797,11 @@ void BM_face_triangulate(
{
const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS);
const bool use_beauty = (ngon_method == MOD_TRIANGULATE_NGON_BEAUTY);
- BMLoop *l_iter, *l_first, *l_new;
+ BMLoop *l_first, *l_new;
BMFace *f_new;
int nf_i = 0;
int ne_i = 0;
-
BLI_assert(BM_face_is_normal_valid(f));
/* ensure both are valid or NULL */
@@ -885,6 +892,7 @@ void BM_face_triangulate(
ARRAY_SET_ITEMS(tris[1], 0, 2, 3);
}
else {
+ BMLoop *l_iter;
float axis_mat[3][3];
float (*projverts)[2] = BLI_array_alloca(projverts, f->len);
@@ -929,6 +937,16 @@ void BM_face_triangulate(
BLI_assert(v_tri[0] == l_new->v);
+ /* check for duplicate */
+ if (l_new->radial_next != l_new) {
+ BMLoop *l_iter = l_new->radial_next;
+ do {
+ if (UNLIKELY(l_new->prev->v == l_iter->prev->v)) {
+ BLI_linklist_prepend(r_faces_double, l_new->f);
+ }
+ } while ((l_iter = l_iter->radial_next) != l_new);
+ }
+
/* copy CD data */
BM_elem_attrs_copy(bm, bm, l_tri[0], l_new);
BM_elem_attrs_copy(bm, bm, l_tri[1], l_new->next);
@@ -946,6 +964,8 @@ void BM_face_triangulate(
if (use_tag || r_edges_new) {
/* new faces loops */
+ BMLoop *l_iter;
+
l_iter = l_first = l_new;
do {
BMEdge *e = l_iter->e;
diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h
index ff0938e..a1866bb 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.h
+++ b/source/blender/bmesh/intern/bmesh_polygon.h
@@ -68,6 +68,7 @@ void BM_face_triangulate(
int *r_faces_new_tot,
BMEdge **r_edges_new,
int *r_edges_new_tot,
+ struct LinkNode **r_faces_double,
const int quad_method, const int ngon_method,
const bool use_tag,
struct MemArena *pf_arena,
diff --git a/source/blender/bmesh/operators/bmo_connect_concave.c b/source/blender/bmesh/operators/bmo_connect_concave.c
index 107aead..34f59aa 100644
--- a/source/blender/bmesh/operators/bmo_connect_concave.c
+++ b/source/blender/bmesh/operators/bmo_connect_concave.c
@@ -42,6 +42,7 @@
#include "BLI_polyfill2d.h"
#include "BLI_polyfill2d_beautify.h"
#include "BLI_edgehash.h"
+#include "BLI_linklist.h"
#include "bmesh.h"
@@ -84,6 +85,7 @@ static bool bm_face_split_by_concave(
BMFace **faces_array = BLI_array_alloca(faces_array, faces_array_tot);
BMEdge **edges_array = BLI_array_alloca(edges_array, edges_array_tot);
const int quad_method = 0, ngon_method = 0; /* beauty */
+ LinkNode *r_faces_double = NULL;
float normal[3];
BLI_assert(f_base->len > 3);
@@ -94,6 +96,7 @@ static bool bm_face_split_by_concave(
bm, f_base,
faces_array, &faces_array_tot,
edges_array, &edges_array_tot,
+ &r_faces_double,
quad_method, ngon_method, false,
pf_arena,
pf_heap, pf_ehash);
diff --git a/source/blender/bmesh/operators/bmo_triangulate.c b/source/blender/bmesh/operators/bmo_triangulate.c
index cb9ba5e..94658f1 100644
--- a/source/blender/bmesh/operators/bmo_triangulate.c
+++ b/source/blender/bmesh/operators/bmo_triangulate.c
@@ -48,14 +48,16 @@ void bmo_triangulate_exec(BMesh *bm, BMOperator *op)
const int ngon_method = BMO_slot_int_get(op->slots_in, "ngon_method");
BMOpSlot *slot_facemap_out = BMO_slot_get(op->slots_out, "face_map.out");
+ BMOpSlot *slot_facemap_double_out = BMO_slot_get(op->slots_out, "face_map_double.out");
BM_mesh_elem_hflag_disable_all(bm, BM_FACE | BM_EDGE, BM_ELEM_TAG, false);
BMO_slot_buffer_hflag_enable(bm, op->slots_in, "faces", BM_FACE, BM_ELEM_TAG, false);
- BM_mesh_triangulate(bm, quad_method, ngon_method, true, op, slot_facemap_out);
+ BM_mesh_triangulate(bm, quad_method, ngon_method, true, op, slot_facemap_out, slot_facemap_double_out);
BMO_slot_buffer_from_enabled_hflag(bm, op, op->slots_out, "edges.out", BM_EDGE, BM_ELEM_TAG);
BMO_slot_buffer_from_enabled_hflag(bm, op, op->slots_out, "faces.out", BM_FACE, BM_ELEM_TAG);
+
}
struct SortNormal {
diff --git a/source/blender/bmesh/tools/bmesh_triangulate.c b/source/blender/bmesh/tools/bmesh_triangulate.c
index 6f2aaf2..ce1bc46 100644
--- a/source/blender/bmesh/tools/bmesh_triangulate.c
+++ b/source/blender/bmesh/tools/bmesh_triangulate.c
@@ -36,6 +36,7 @@
#include "BLI_memarena.h"
#include "BLI_heap.h"
#include "BLI_edgehash.h"
+#include "BLI_linklist.h"
/* only for defines */
#include "BLI_polyfill2d.h"
@@ -52,7 +53,7 @@ static void bm_face_triangulate_mapping(
BMesh *bm, BMFace *face,
const int quad_method, const int ngon_method,
const bool use_tag,
- BMOperator *op, BMOpSlot *slot_facemap_out,
+ BMOperator *op, BMOpSlot *slot_facemap_out, BMOpSlot *slot_facemap_double_out,
MemArena *pf_arena,
/* use for MOD_TRIANGULATE_NGON_BEAUTY only! */
@@ -60,12 +61,14 @@ static void bm_face_triangulate_mapping(
{
int faces_array_tot = face->len - 3;
BMFace **faces_array = BLI_array_alloca(faces_array, faces_array_tot);
+ LinkNode *faces_double = NULL;
BLI_assert(face->len > 3);
BM_face_triangulate(
bm, face,
faces_array, &faces_array_tot,
NULL, NULL,
+ &faces_double,
quad_method, ngon_method, use_tag,
pf_arena,
pf_heap, pf_ehash);
@@ -76,13 +79,20 @@ static void bm_face_triangulate_mapping(
for (i = 0; i < faces_array_tot; i++) {
BMO_slot_map_elem_insert(op, slot_facemap_out, faces_array[i], face);
}
+
+ while (faces_double) {
+ LinkNode *next = faces_double->next;
+ BMO_slot_map_elem_insert(op, slot_facemap_double_out, faces_double->link, face);
+ MEM_freeN(faces_double);
+ faces_double = next;
+ }
}
}
void BM_mesh_triangulate(
BMesh *bm, const int quad_method, const int ngon_method, const bool tag_only,
- BMOperator *op, BMOpSlot *slot_facemap_out)
+ BMOperator *op, BMOpSlot *slot_facemap_out, BMOpSlot *slot_facemap_double_out)
{
BMIter iter;
BMFace *face;
@@ -107,10 +117,9 @@ void BM_mesh_triangulate(
if (face->len > 3) {
if (tag_only == false || BM_elem_flag_test(face, BM_ELEM_TAG)) {
bm_face_triangulate_mapping(
- bm, face, quad_method,
- ngon_method, tag_only,
- op, slot_facemap_out,
-
+ bm, face,
+ quad_method, ngon_method, tag_only,
+ op, slot_facemap_out, slot_facemap_double_out,
pf_arena,
pf_heap, pf_ehash);
}
@@ -118,6 +127,8 @@ void BM_mesh_triangulate(
}
}
else {
+ LinkNode *faces_double = NULL;
+
BM_ITER_MESH (face, &iter, bm, BM_FACES_OF_MESH) {
if (face->len > 3) {
if (tag_only == false || BM_elem_flag_test(face, BM_ELEM_TAG)) {
@@ -125,12 +136,20 @@ void BM_mesh_triangulate(
bm, face,
NULL, NULL,
NULL, NULL,
+ &faces_double,
quad_method, ngon_method, tag_only,
pf_arena,
pf_heap, pf_ehash);
}
}
}
+
+ while (faces_double) {
+ LinkNode *next = faces_double->next;
+ BM_face_kill(bm, faces_double->link);
+ MEM_freeN(faces_double);
+ faces_double = next;
+ }
}
BLI_memarena_free(pf_arena);
diff --git a/source/blender/bmesh/tools/bmesh_triangulate.h b/source/blender/bmesh/tools/bmesh_triangulate.h
index c6a5e04..644d788 100644
--- a/source/blender/bmesh/tools/bmesh_triangulate.h
+++ b/source/blender/bmesh/tools/bmesh_triangulate.h
@@ -32,6 +32,6 @@
void BM_mesh_triangulate(
BMesh *bm, const int quad_method, const int ngon_method, const bool tag_only,
- BMOperator *op, BMOpSlot *slot_facemap_out);
+ BMOperator *op, BMOpSlot *slot_facemap_out, BMOpSlot *slot_doubles_out);
#endif /* __BMESH_TRIANGULATE_H__ */
diff --git a/source/blender/editors/sculpt_paint/sculpt.c b/source/blender/editors/sculpt_paint/sculpt.c
index 81c158a..5f0295e 100644
--- a/source/blender/editors/sculpt_paint/sculpt.c
+++ b/source/blender/editors/sculpt_paint/sculpt.c
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list