Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--source/blender/bmesh/intern/bmesh_core.c24
-rw-r--r--source/blender/bmesh/intern/bmesh_core.h2
-rw-r--r--source/blender/bmesh/intern/bmesh_polygon.c308
-rw-r--r--source/blender/bmesh/intern/bmesh_polygon.h1
-rw-r--r--source/blender/bmesh/tools/bmesh_triangulate.c16
5 files changed, 125 insertions, 226 deletions
diff --git a/source/blender/bmesh/intern/bmesh_core.c b/source/blender/bmesh/intern/bmesh_core.c
index 164a92125cd..0b14cf22276 100644
--- a/source/blender/bmesh/intern/bmesh_core.c
+++ b/source/blender/bmesh/intern/bmesh_core.c
@@ -2279,3 +2279,27 @@ BMVert *bmesh_urmv(BMesh *bm, BMFace *f_sep, BMVert *v_sep)
BMLoop *l = BM_face_vert_share_loop(f_sep, v_sep);
return bmesh_urmv_loop(bm, l);
}
+
+/**
+ * Avoid calling this where possible,
+ * low level function for swapping faces.
+ */
+void bmesh_face_swap_data(BMesh *bm, BMFace *f_a, BMFace *f_b)
+{
+ BMLoop *l_iter, *l_first;
+
+ BLI_assert(f_a != f_b);
+
+ l_iter = l_first = BM_FACE_FIRST_LOOP(f_a);
+ do {
+ l_iter->f = f_b;
+ } while ((l_iter = l_iter->next) != l_first);
+
+ l_iter = l_first = BM_FACE_FIRST_LOOP(f_b);
+ do {
+ l_iter->f = f_a;
+ } while ((l_iter = l_iter->next) != l_first);
+
+ SWAP(BMFace, (*f_a), (*f_b));
+ bm->elem_index_dirty |= BM_FACE;
+}
diff --git a/source/blender/bmesh/intern/bmesh_core.h b/source/blender/bmesh/intern/bmesh_core.h
index a18c2ebd32c..9e33509c2c8 100644
--- a/source/blender/bmesh/intern/bmesh_core.h
+++ b/source/blender/bmesh/intern/bmesh_core.h
@@ -87,4 +87,6 @@ BMFace *bmesh_jfke(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e);
BMVert *bmesh_urmv(BMesh *bm, BMFace *f_sep, BMVert *v_sep);
BMVert *bmesh_urmv_loop(BMesh *bm, BMLoop *l_sep);
+void bmesh_face_swap_data(BMesh *bm, BMFace *f_a, BMFace *f_b);
+
#endif /* __BMESH_CORE_H__ */
diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c
index 0978faee9e4..d11ae82b3d2 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.c
+++ b/source/blender/bmesh/intern/bmesh_polygon.c
@@ -34,6 +34,7 @@
#include "BLI_alloca.h"
#include "BLI_math.h"
+#include "BLI_memarena.h"
#include "BLI_scanfill.h"
#include "BLI_listbase.h"
@@ -801,264 +802,127 @@ bool BM_face_point_inside_test(BMFace *f, const float co[3])
return crosses % 2 != 0;
}
-static bool bm_face_goodline(float const (*projectverts)[2], BMFace *f, int v1i, int v2i, int v3i)
-{
- BMLoop *l_iter;
- BMLoop *l_first;
-
- float pv1[2];
- const float *v1 = projectverts[v1i];
- const float *v2 = projectverts[v2i];
- const float *v3 = projectverts[v3i];
- int i;
-
- /* v3 must be on the left side of [v1, v2] line, else we know [v1, v3] is outside of f! */
- if (testedgesidef(v1, v2, v3)) {
- return false;
- }
-
- l_iter = l_first = BM_FACE_FIRST_LOOP(f);
- do {
- i = BM_elem_index_get(l_iter->v);
- copy_v2_v2(pv1, projectverts[i]);
-
- if (ELEM3(i, v1i, v2i, v3i)) {
-#if 0
- printf("%d in (%d, %d, %d) tri (from indices!), continuing\n", i, v1i, v2i, v3i);
-#endif
- continue;
- }
-
- if (isect_point_tri_v2(pv1, v1, v2, v3) ||
- isect_point_tri_v2(pv1, v3, v2, v1))
- {
-#if 0
- if (isect_point_tri_v2(pv1, v1, v2, v3))
- printf("%d in (%d, %d, %d)\n", v3i, i, v1i, v2i);
- else
- printf("%d in (%d, %d, %d)\n", v1i, i, v3i, v2i);
-#endif
- return false;
- }
- } while ((l_iter = l_iter->next) != l_first);
- return true;
-}
-
/**
- * \brief Find Ear
+ * \brief BMESH TRIANGULATE FACE
*
- * Used by tessellator to find the next triangle to 'clip off' of a polygon while tessellating.
+ * Currently repeatedly find the best triangle (i.e. the most "open" one), provided it does not
+ * produces a "remaining" face with too much wide/narrow angles
+ * (using cos (i.e. dot product of normalized vectors) of angles).
*
- * \param f The face to search.
- * \param projectverts an array of face vert coords.
- * \param use_beauty Currently only applies to quads, can be extended later on.
- * \param abscoss Must be allocated by caller, and at least f->len length
- * (allow to avoid allocating a new one for each tri!).
+ * \param r_faces_new if non-null, must be an array of BMFace pointers,
+ * with a length equal to (f->len - 2). It will be filled with the new
+ * triangles.
+ *
+ * \note use_tag tags new flags and edges.
*/
-static BMLoop *poly_find_ear(BMFace *f, float (*projectverts)[2], const bool use_beauty, float *abscoss)
+void BM_face_triangulate(BMesh *bm, BMFace *f,
+ BMFace **r_faces_new,
+ MemArena *sf_arena,
+ const bool UNUSED(use_beauty), const bool use_tag)
{
- BMLoop *bestear = NULL;
+ int nf_i = 0;
+ BMLoop *l_iter, *l_first, *l_new;
+ BMFace *f_new;
- BMLoop *l_iter;
- BMLoop *l_first;
+ BLI_assert(BM_face_is_normal_valid(f));
- const float cos_threshold = 0.9f;
- const float bias = 1.0f + 1e-6f;
-
- /* just triangulate degenerate faces */
- if (UNLIKELY(is_zero_v3(f->no))) {
- return BM_FACE_FIRST_LOOP(f);
- }
if (f->len == 4) {
- BMLoop *larr[4];
- int i = 0, i4;
- float cos1, cos2;
- l_iter = l_first = BM_FACE_FIRST_LOOP(f);
- do {
- larr[i] = l_iter;
- i++;
- } while ((l_iter = l_iter->next) != l_first);
+ l_first = BM_FACE_FIRST_LOOP(f);
- /* pick 0/1 based on best length */
- /* XXX Can't only rely on such test, also must check we do not get (too much) degenerated triangles!!! */
- i = (((len_squared_v3v3(larr[0]->v->co, larr[2]->v->co) >
- len_squared_v3v3(larr[1]->v->co, larr[3]->v->co) * bias)) != use_beauty);
- i4 = (i + 3) % 4;
- /* Check produced tris aren't too flat/narrow...
- * Probably not the best test, but is quite efficient and should at least avoid null-area faces! */
- cos1 = fabsf(cos_v3v3v3(larr[i4]->v->co, larr[i]->v->co, larr[i + 1]->v->co));
- cos2 = fabsf(cos_v3v3v3(larr[i4]->v->co, larr[i + 2]->v->co, larr[i + 1]->v->co));
-#if 0
- printf("%d, (%f, %f), (%f, %f)\n", i, cos1, cos2,
- fabsf(cos_v3v3v3(larr[i]->v->co, larr[i4]->v->co, larr[i + 2]->v->co)),
- fabsf(cos_v3v3v3(larr[i]->v->co, larr[i + 1]->v->co, larr[i + 2]->v->co)));
-#endif
- if (cos1 < cos2)
- cos1 = cos2;
-
- if (cos1 > cos_threshold) {
- if (cos1 > fabsf(cos_v3v3v3(larr[i]->v->co, larr[i4]->v->co, larr[i + 2]->v->co)) &&
- cos1 > fabsf(cos_v3v3v3(larr[i]->v->co, larr[i + 1]->v->co, larr[i + 2]->v->co)))
- {
- i = !i;
- }
+ f_new = BM_face_split(bm, f, l_first->v, l_first->next->next->v, &l_new, NULL, false);
+ copy_v3_v3(f_new->no, f->no);
+
+ if (UNLIKELY(!l_new || !f_new)) {
+ fprintf(stderr, "%s: triangulator failed to split face! (bmesh internal error)\n", __func__);
}
- /* Last check we do not get overlapping triangles
- * (as much as possible, there are some cases with no good solution!) */
- i4 = (i + 3) % 4;
- if (!bm_face_goodline((float const (*)[2])projectverts, f,
- BM_elem_index_get(larr[i4]->v),
- BM_elem_index_get(larr[i]->v),
- BM_elem_index_get(larr[i + 1]->v)))
- {
- i = !i;
+
+ if (use_tag) {
+ BM_elem_flag_enable(l_new->e, BM_ELEM_TAG);
+ BM_elem_flag_enable(f, BM_ELEM_TAG);
}
-/* printf("%d\n", i);*/
- bestear = larr[i];
+ if (r_faces_new) {
+ r_faces_new[nf_i++] = f_new;
+ }
}
- else {
- /* float angle, bestangle = 180.0f; */
- const int len = f->len;
- float cos, cos_best = 1.0f;
- int i, j;
+ else if (f->len > 4) {
+ /* scanfill */
+ ScanFillContext sf_ctx;
+ ScanFillVert *sf_vert, *sf_vert_prev = NULL;
+ ScanFillFace *sf_tri;
+ int totfilltri;
- /* Compute cos of all corners! */
- i = 0;
+ /* populate scanfill */
+ BLI_scanfill_begin_arena(&sf_ctx, sf_arena);
l_iter = l_first = BM_FACE_FIRST_LOOP(f);
- do {
- const BMVert *v1 = l_iter->prev->v;
- const BMVert *v2 = l_iter->v;
- const BMVert *v3 = l_iter->next->v;
- abscoss[i] = fabsf(cos_v3v3v3(v1->co, v2->co, v3->co));
-/* printf("tcoss: %f\n", *tcoss);*/
- i++;
- } while ((l_iter = l_iter->next) != l_first);
+ /* step once before entering the loop */
+ sf_vert = BLI_scanfill_vert_add(&sf_ctx, l_iter->v->co);
+ sf_vert->tmp.p = l_iter;
+ sf_vert_prev = sf_vert;
+ l_iter = l_iter->next;
- i = 0;
- l_iter = l_first;
do {
- const BMVert *v1 = l_iter->prev->v;
- const BMVert *v2 = l_iter->v;
- const BMVert *v3 = l_iter->next->v;
-
- /* Compute highest cos (i.e. narrowest angle) of this tri. */
- cos = max_fff(abscoss[i],
- fabsf(cos_v3v3v3(v2->co, v3->co, v1->co)),
- fabsf(cos_v3v3v3(v3->co, v1->co, v2->co)));
-
- /* Compare to prev best (i.e. lowest) cos. */
- if (cos < cos_best) {
- if (bm_face_goodline((float const (*)[2])projectverts, f,
- BM_elem_index_get(v1),
- BM_elem_index_get(v2),
- BM_elem_index_get(v3)))
- {
- /* We must check this tri would not leave a (too much) degenerated remaining face! */
- /* For now just assume if the average of cos of all
- * "remaining face"'s corners is below a given threshold, it's OK. */
- float cos_mean = fabsf(cos_v3v3v3(v1->co, v3->co, l_iter->next->next->v->co));
- const int i_limit = (i - 1 + len) % len;
- cos_mean += fabsf(cos_v3v3v3(l_iter->prev->prev->v->co, v1->co, v3->co));
- j = (i + 2) % len;
- do {
- cos_mean += abscoss[j];
- } while ((j = (j + 1) % len) != i_limit);
- cos_mean /= len - 1;
-
- /* We need a best ear in any case... */
- if (cos_mean < cos_threshold || (!bestear && cos_mean < 1.0f)) {
- /* OKI, keep this ear (corner...) as a potential best one! */
- bestear = l_iter;
- cos_best = cos;
- }
-#if 0
- else
- printf("Had a nice tri (higest cos of %f, current cos_best is %f), "
- "but average cos of all \"remaining face\"'s corners is too high (%f)!\n",
- cos, cos_best, cos_mean);
-#endif
- }
- }
- i++;
+ sf_vert = BLI_scanfill_vert_add(&sf_ctx, l_iter->v->co);
+ BLI_scanfill_edge_add(&sf_ctx, sf_vert_prev, sf_vert);
+
+ sf_vert->tmp.p = l_iter;
+ sf_vert_prev = sf_vert;
} while ((l_iter = l_iter->next) != l_first);
- }
- return bestear;
-}
+ BLI_scanfill_edge_add(&sf_ctx, sf_vert_prev, sf_ctx.fillvertbase.first);
-/**
- * \brief BMESH TRIANGULATE FACE
- *
- * Currently repeatedly find the best triangle (i.e. the most "open" one), provided it does not
- * produces a "remaining" face with too much wide/narrow angles
- * (using cos (i.e. dot product of normalized vectors) of angles).
- *
- * \param r_faces_new if non-null, must be an array of BMFace pointers,
- * with a length equal to (f->len - 2). It will be filled with the new
- * triangles.
- *
- * \note use_tag tags new flags and edges.
- */
-void BM_face_triangulate(BMesh *bm, BMFace *f,
- BMFace **r_faces_new,
- const bool use_beauty, const bool use_tag)
-{
- const float f_len_orig = f->len;
- int i, nf_i = 0;
- BMLoop *l_new;
- BMLoop *l_iter;
- BMLoop *l_first;
- /* BM_face_triangulate: temp absolute cosines of face corners */
- float (*projectverts)[2] = BLI_array_alloca(projectverts, f_len_orig);
- float *abscoss = BLI_array_alloca(abscoss, f_len_orig);
- float mat[3][3];
+ /* calculate filled triangles */
+ totfilltri = BLI_scanfill_calc_ex(&sf_ctx, 0, f->no);
+ BLI_assert(totfilltri <= f->len - 2);
- BLI_assert(BM_face_is_normal_valid(f));
- axis_dominant_v3_to_m3(mat, f->no);
+ /* loop over calculated triangles and create new geometry */
+ for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) {
+ /* the order is reverse, otherwise the normal is flipped */
+ BMLoop *l_tri[3] = {
+ sf_tri->v3->tmp.p,
+ sf_tri->v2->tmp.p,
+ sf_tri->v1->tmp.p};
- /* copy vertex coordinates to vertspace area */
- i = 0;
- l_iter = l_first = BM_FACE_FIRST_LOOP(f);
- do {
- mul_v2_m3v3(projectverts[i], mat, l_iter->v->co);
- BM_elem_index_set(l_iter->v, i++); /* set dirty! */
- } while ((l_iter = l_iter->next) != l_first);
+ BMVert *v_tri[3] = {
+ l_tri[0]->v,
+ l_tri[1]->v,
+ l_tri[2]->v};
- bm->elem_index_dirty |= BM_VERT; /* see above */
+ f_new = BM_face_create_verts(bm, v_tri, 3, f, false, true);
+ l_new = BM_FACE_FIRST_LOOP(f_new);
- while (f->len > 3) {
- l_iter = poly_find_ear(f, projectverts, use_beauty, abscoss);
+ BLI_assert(v_tri[0] == l_new->v);
- /* force triangulation - if we can't find an ear the face is degenerate */
- if (l_iter == NULL) {
- l_iter = BM_FACE_FIRST_LOOP(f);
- }
+ /* 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);
+ BM_elem_attrs_copy(bm, bm, l_tri[2], l_new->prev);
-/* printf("Subdividing face...\n");*/
- f = BM_face_split(bm, l_iter->f, l_iter->prev->v, l_iter->next->v, &l_new, NULL, true);
+ if (use_tag) {
+ BM_elem_flag_enable(l_new->e, BM_ELEM_TAG);
+ }
- if (UNLIKELY(!f)) {
- fprintf(stderr, "%s: triangulator failed to split face! (bmesh internal error)\n", __func__);
- break;
+ if (r_faces_new && sf_tri->prev) {
+ r_faces_new[nf_i++] = f_new;
+ }
}
- copy_v3_v3(f->no, l_iter->f->no);
+ if (sf_ctx.fillfacebase.first) {
+ /* we can't delete the real face, so swap data and delete */
+ bmesh_face_swap_data(bm, f, f_new);
+ BM_face_kill(bm, f_new);
- if (use_tag) {
- BM_elem_flag_enable(l_new->e, BM_ELEM_TAG);
- BM_elem_flag_enable(f, BM_ELEM_TAG);
+ if (use_tag) {
+ BM_elem_flag_enable(f, BM_ELEM_TAG);
+ }
}
- if (r_faces_new) {
- r_faces_new[nf_i++] = f;
- }
+ /* garbage collection */
+ BLI_scanfill_end_arena(&sf_ctx, sf_arena);
}
-
- BLI_assert(f->len == 3);
}
/**
diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h
index 14fe1e76360..b7117621273 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.h
+++ b/source/blender/bmesh/intern/bmesh_polygon.h
@@ -53,6 +53,7 @@ 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,
+ struct MemArena *sf_arena,
const bool use_beauty, const bool use_tag) ATTR_NONNULL(1, 2);
void BM_face_legal_splits(BMFace *f, BMLoop *(*loops)[2], int len) ATTR_NONNULL();
diff --git a/source/blender/bmesh/tools/bmesh_triangulate.c b/source/blender/bmesh/tools/bmesh_triangulate.c
index 2eacf62d68a..34ff493a026 100644
--- a/source/blender/bmesh/tools/bmesh_triangulate.c
+++ b/source/blender/bmesh/tools/bmesh_triangulate.c
@@ -31,6 +31,9 @@
#include "BLI_utildefines.h"
#include "BLI_alloca.h"
+#include "BLI_memarena.h"
+#include "BLI_listbase.h"
+#include "BLI_scanfill.h"
#include "bmesh.h"
@@ -39,14 +42,14 @@
/**
* a version of #BM_face_triangulate that maps to #BMOpSlot
*/
-static void bm_face_triangulate_mapping(BMesh *bm, BMFace *face, const bool use_beauty, const bool use_tag,
+static void bm_face_triangulate_mapping(BMesh *bm, BMFace *face, MemArena *sf_arena, const bool use_beauty, const bool use_tag,
BMOperator *op, BMOpSlot *slot_facemap_out)
{
const 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, use_beauty, use_tag);
+ BM_face_triangulate(bm, face, faces_array, sf_arena, use_beauty, use_tag);
if (faces_array) {
int i;
@@ -63,13 +66,16 @@ void BM_mesh_triangulate(BMesh *bm, const bool use_beauty, const bool tag_only,
{
BMIter iter;
BMFace *face;
+ MemArena *sf_arena;
+
+ sf_arena = BLI_memarena_new(BLI_SCANFILL_ARENA_SIZE, __func__);
if (slot_facemap_out) {
/* same as below but call: bm_face_triangulate_mapping() */
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)) {
- bm_face_triangulate_mapping(bm, face, use_beauty, tag_only,
+ bm_face_triangulate_mapping(bm, face, sf_arena, use_beauty, tag_only,
op, slot_facemap_out);
}
}
@@ -79,9 +85,11 @@ void BM_mesh_triangulate(BMesh *bm, const bool use_beauty, const bool tag_only,
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)) {
- BM_face_triangulate(bm, face, NULL, use_beauty, tag_only);
+ BM_face_triangulate(bm, face, NULL, sf_arena, use_beauty, tag_only);
}
}
}
}
+
+ BLI_memarena_free(sf_arena);
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-08-12 01:10:45 +0300