[Bf-blender-cvs] [5da703e] master: BMesh/Mesh: replace scanfill with polyfill
Campbell Barton
noreply at git.blender.org
Sat Nov 30 12:16:21 CET 2013
Commit: 5da703e9158adb67d23209c3cff2972683642f7f
Author: Campbell Barton
Date: Sat Nov 30 22:05:58 2013 +1100
http://developer.blender.org/rB5da703e9158adb67d23209c3cff2972683642f7f
BMesh/Mesh: replace scanfill with polyfill
===================================================================
M source/blender/blenkernel/intern/mesh_evaluate.c
M source/blender/bmesh/intern/bmesh_polygon.c
M source/blender/bmesh/intern/bmesh_polygon.h
M source/blender/bmesh/intern/bmesh_queries.c
M source/blender/editors/mesh/editmesh_knife.c
===================================================================
diff --git a/source/blender/blenkernel/intern/mesh_evaluate.c b/source/blender/blenkernel/intern/mesh_evaluate.c
index 1e74ce2..adc71e7 100644
--- a/source/blender/blenkernel/intern/mesh_evaluate.c
+++ b/source/blender/blenkernel/intern/mesh_evaluate.c
@@ -42,7 +42,7 @@
#include "BLI_math.h"
#include "BLI_edgehash.h"
#include "BLI_bitmap.h"
-#include "BLI_scanfill.h"
+#include "BLI_polyfill2d.h"
#include "BLI_linklist.h"
#include "BLI_linklist_stack.h"
#include "BLI_alloca.h"
@@ -1298,10 +1298,7 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata,
MPoly *mp, *mpoly;
MLoop *ml, *mloop;
MFace *mface, *mf;
- ScanFillContext sf_ctx;
- ScanFillVert *sf_vert, *sf_vert_last, *sf_vert_first;
- ScanFillFace *sf_tri;
- MemArena *sf_arena = NULL;
+ MemArena *arena = NULL;
int *mface_to_poly_map;
int lindex[4]; /* only ever use 3 in this case */
int poly_index, j, mface_index;
@@ -1375,60 +1372,60 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata,
}
#endif /* USE_TESSFACE_SPEEDUP */
else {
-#define USE_TESSFACE_CALCNORMAL
+ const float *co_curr, *co_prev;
- unsigned int totfilltri;
-
-#ifdef USE_TESSFACE_CALCNORMAL
float normal[3];
- zero_v3(normal);
-#endif
- ml = mloop + mp->loopstart;
- if (UNLIKELY(sf_arena == NULL)) {
- sf_arena = BLI_memarena_new(BLI_SCANFILL_ARENA_SIZE, __func__);
- }
+ float axis_mat[3][3];
+ float (*projverts)[2];
+ unsigned int (*tris)[3];
- BLI_scanfill_begin_arena(&sf_ctx, sf_arena);
- sf_vert_first = NULL;
- sf_vert_last = NULL;
- for (j = 0; j < mp->totloop; j++, ml++) {
- sf_vert = BLI_scanfill_vert_add(&sf_ctx, mvert[ml->v].co);
+ const unsigned int loopstart = (unsigned int)mp->loopstart;
+ const int totfilltri = mp->totloop - 2;
- sf_vert->keyindex = (unsigned int)(mp->loopstart + j);
+ if (UNLIKELY(arena == NULL)) {
+ arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
+ }
- if (sf_vert_last) {
- BLI_scanfill_edge_add(&sf_ctx, sf_vert_last, sf_vert);
-#ifdef USE_TESSFACE_CALCNORMAL
- add_newell_cross_v3_v3v3(normal, sf_vert_last->co, sf_vert->co);
-#endif
- }
+ tris = BLI_memarena_alloc(arena, (int)sizeof(*tris) * totfilltri);
+ projverts = BLI_memarena_alloc(arena, (int)sizeof(*projverts) * mp->totloop);
+
+ zero_v3(normal);
- if (!sf_vert_first)
- sf_vert_first = sf_vert;
- sf_vert_last = sf_vert;
+ /* calc normal */
+ ml = mloop + loopstart;
+ co_prev = mvert[ml[mp->totloop - 1].v].co;
+ for (j = 0; j < mp->totloop; j++, ml++) {
+ co_curr = mvert[ml->v].co;
+ add_newell_cross_v3_v3v3(normal, co_prev, co_curr);
+ co_prev = co_curr;
}
- BLI_scanfill_edge_add(&sf_ctx, sf_vert_last, sf_vert_first);
-#ifdef USE_TESSFACE_CALCNORMAL
- add_newell_cross_v3_v3v3(normal, sf_vert_last->co, sf_vert_first->co);
if (UNLIKELY(normalize_v3(normal) == 0.0f)) {
normal[2] = 1.0f;
}
- totfilltri = BLI_scanfill_calc_ex(&sf_ctx, 0, normal);
-#else
- totfilltri = BLI_scanfill_calc(&sf_ctx, 0);
-#endif
- BLI_assert(totfilltri <= (unsigned int)(mp->totloop - 2));
- (void)totfilltri;
- for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next, mf++) {
+ /* project verts to 2d */
+ axis_dominant_v3_to_m3(axis_mat, normal);
+
+ ml = mloop + loopstart;
+ for (j = 0; j < mp->totloop; j++, ml++) {
+ mul_v2_m3v3(projverts[j], axis_mat, mvert[ml->v].co);
+ }
+
+ BLI_polyfill_calc_arena((const float (*)[2])projverts, (unsigned int)mp->totloop, tris, arena);
+
+ /* apply fill */
+ ml = mloop + loopstart;
+ for (j = 0; j < totfilltri; j++) {
+ unsigned int *tri = tris[j];
+
mface_to_poly_map[mface_index] = poly_index;
mf = &mface[mface_index];
/* set loop indices, transformed to vert indices later */
- mf->v1 = sf_tri->v1->keyindex;
- mf->v2 = sf_tri->v2->keyindex;
- mf->v3 = sf_tri->v3->keyindex;
+ mf->v1 = loopstart + tri[0];
+ mf->v2 = loopstart + tri[1];
+ mf->v3 = loopstart + tri[2];
mf->v4 = 0;
mf->mat_nr = mp->mat_nr;
@@ -1441,15 +1438,13 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata,
mface_index++;
}
- BLI_scanfill_end_arena(&sf_ctx, sf_arena);
-
-#undef USE_TESSFACE_CALCNORMAL
+ BLI_memarena_clear(arena);
}
}
- if (sf_arena) {
- BLI_memarena_free(sf_arena);
- sf_arena = NULL;
+ if (arena) {
+ BLI_memarena_free(arena);
+ arena = NULL;
}
CustomData_free(fdata, totface);
diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c
index 36d7e16..c09fb6d 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.c
+++ b/source/blender/bmesh/intern/bmesh_polygon.c
@@ -36,7 +36,7 @@
#include "BLI_alloca.h"
#include "BLI_math.h"
#include "BLI_memarena.h"
-#include "BLI_scanfill.h"
+#include "BLI_polyfill2d.h"
#include "BLI_listbase.h"
#include "bmesh.h"
@@ -176,22 +176,19 @@ static void bm_face_calc_poly_center_mean_vertex_cos(BMFace *f, float r_cent[3],
* \param r_loops Store face loop pointers, (f->len)
* \param r_index Store triangle triples, indicies into \a r_loops, ((f->len - 2) * 3)
*/
-int BM_face_calc_tessellation(const BMFace *f, BMLoop **r_loops, int (*_r_index)[3])
+void BM_face_calc_tessellation(const BMFace *f, BMLoop **r_loops, unsigned int (*r_index)[3])
{
- int *r_index = (int *)_r_index;
BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
BMLoop *l_iter;
- int totfilltri;
if (f->len == 3) {
*r_loops++ = (l_iter = l_first);
*r_loops++ = (l_iter = l_iter->next);
*r_loops++ = ( l_iter->next);
- r_index[0] = 0;
- r_index[1] = 1;
- r_index[2] = 2;
- totfilltri = 1;
+ r_index[0][0] = 0;
+ r_index[0][1] = 1;
+ r_index[0][2] = 2;
}
else if (f->len == 4) {
*r_loops++ = (l_iter = l_first);
@@ -199,72 +196,31 @@ int BM_face_calc_tessellation(const BMFace *f, BMLoop **r_loops, int (*_r_index)
*r_loops++ = (l_iter = l_iter->next);
*r_loops++ = ( l_iter->next);
- r_index[0] = 0;
- r_index[1] = 1;
- r_index[2] = 2;
+ r_index[0][0] = 0;
+ r_index[0][1] = 1;
+ r_index[0][2] = 2;
- r_index[3] = 0;
- r_index[4] = 2;
- r_index[5] = 3;
- totfilltri = 2;
+ r_index[1][0] = 0;
+ r_index[1][1] = 2;
+ r_index[1][2] = 3;
}
else {
+ float axis_mat[3][3];
+ float (*projverts)[2] = BLI_array_alloca(projverts, f->len);
int j;
- ScanFillContext sf_ctx;
- ScanFillVert *sf_vert, *sf_vert_last = NULL, *sf_vert_first = NULL;
- /* ScanFillEdge *e; */ /* UNUSED */
- ScanFillFace *sf_tri;
-
- BLI_scanfill_begin(&sf_ctx);
+ axis_dominant_v3_to_m3(axis_mat, f->no);
j = 0;
l_iter = l_first;
do {
- sf_vert = BLI_scanfill_vert_add(&sf_ctx, l_iter->v->co);
- sf_vert->tmp.p = l_iter;
-
- if (sf_vert_last) {
- /* e = */ BLI_scanfill_edge_add(&sf_ctx, sf_vert_last, sf_vert);
- }
-
- sf_vert_last = sf_vert;
- if (sf_vert_first == NULL) {
- sf_vert_first = sf_vert;
- }
-
+ mul_v2_m3v3(projverts[j], axis_mat, l_iter->v->co);
r_loops[j] = l_iter;
-
- /* mark order */
- BM_elem_index_set(l_iter, j++); /* set_loop */
-
} while ((l_iter = l_iter->next) != l_first);
/* complete the loop */
- BLI_scanfill_edge_add(&sf_ctx, sf_vert_first, sf_vert);
-
- totfilltri = BLI_scanfill_calc_ex(&sf_ctx, 0, f->no);
- BLI_assert(totfilltri <= f->len - 2);
- BLI_assert(totfilltri == BLI_countlist(&sf_ctx.fillfacebase));
-
- for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) {
- int i1 = BM_elem_index_get((BMLoop *)sf_tri->v1->tmp.p);
- int i2 = BM_elem_index_get((BMLoop *)sf_tri->v2->tmp.p);
- int i3 = BM_elem_index_get((BMLoop *)sf_tri->v3->tmp.p);
-
- if (i1 > i2) { SWAP(int, i1, i2); }
- if (i2 > i3) { SWAP(int, i2, i3); }
- if (i1 > i2) { SWAP(int, i1, i2); }
-
- *r_index++ = i1;
- *r_index++ = i2;
- *r_index++ = i3;
- }
-
- BLI_scanfill_end(&sf_ctx);
+ BLI_polyfill_calc((const float (*)[2])projverts, f->len, r_index);
}
-
- return totfilltri;
}
/**
@@ -832,11 +788,8 @@ void BM_face_triangulate(BMesh *bm, BMFace *f,
int edge_array_len;
bool use_beauty = (ngon_method == MOD_TRIANGULATE_NGON_BEAUTY);
-#define SF_EDGE_IS_BOUNDARY 0xff
-
BLI_assert(BM_face_is_normal_valid(f));
-
if (f->len == 4) {
BMVert *v1, *v2;
l_first = BM_FACE_FIRST_LOOP(f);
@@ -911,47 +864,39 @@ void BM_face_triangulate(BMesh *bm, BMFace *f,
}
}
else if (f->len > 4) {
- /* scanfill */
- ScanFillContext sf_ctx;
- ScanFillVert *sf_vert, *sf_vert_prev = NULL;
- ScanFillEdge *sf_edge;
- ScanFillFace *sf_tri;
- int totfilltri;
-
- /* populate scanfill */
- BLI_scanfill_begin_arena(&sf_ctx, sf_arena);
- l_iter = l_first = BM_FACE_FIRST_LOOP(f);
-
- /* 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;
- do {
- sf_vert = BLI_scanfill_vert_add(&sf_ctx, l_iter->v->co);
- sf_edge = BLI_scanfill_edge_add(&sf_ctx, sf_vert_prev, sf_vert);
- sf_edge->tmp.c = SF_EDGE_IS_BOUNDARY;
+ float axis_mat[3][3];
+ float (*projverts)[2] = BLI_array_alloca(projverts, f->len);
+ BMLoop **loops = BLI_array_alloca(loops, f->len);
+ unsigned int (*tris)[3] = BLI_array_alloca(tris, f->len);
+ const int totfilltri = f->len - 2;
+ const int last_tri = f->len - 3;
+ int i;
- sf_vert->tmp.p = l_iter;
- sf_vert_prev = sf_vert;
- } while ((l_iter = l_iter->next) != l_first);
+ //BLI_assert(BM_face_is_normal_valid(f));
- sf_edge = BLI_scanfill_edge_add(&sf_ctx, sf_vert_prev, sf_ctx.fillvertbase.first);
- sf_edge->tmp.c = SF_EDGE_IS_BOUNDARY;
+ axis_dominant_v3_to_m3(axis_mat, f->no);
- /* calculate filled triangles */
- totfilltri = BLI_scanfill_calc_ex(&sf_ctx, 0, f->no);
- BLI_assert(totfilltri <= f->len - 2);
+ for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f); i < f->len; i++, l_iter = l_iter->next) {
+ loops[i] = l_iter;
+ mul_v2_m3v3(projverts[i], axis_mat, l_iter->v->co);
+ }
+
+ BLI_polyfill_calc_arena((const float (*)[2])projverts, f->len, tris,
+ sf_arena);
+ if (use_beauty) {
+ edge_array = BLI_array_alloca(edge_array, orig_f_len - 3);
+ edge_array_len = 0;
+ }
/* loop over calculated triangles
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list