blender
/
blender
136
404
Fork 586
Code Issues 6.2k Pull Requests 753 Projects 19 Wiki Activity

BMesh/Mesh: replace scanfill with polyfill

This commit is contained in:
Campbell Barton 2013-11-30 22:05:58 +11:00
parent b9445106b2
commit 5da703e915
Notes: blender-bot 2023-02-14 11:32:13 +01:00 
Referenced by issue #37670, Paint mode + procedural map colours error
5 changed files with 150 additions and 232 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

97
source/blender/blenkernel/intern/mesh_evaluate.c
View File

@ -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];
float axis_mat[3][3];
float (*projverts)[2];
unsigned int (*tris)[3];
const unsigned int loopstart = (unsigned int)mp->loopstart;
const int totfilltri = mp->totloop - 2;
if (UNLIKELY(arena == NULL)) {
arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
}
tris = BLI_memarena_alloc(arena, (int)sizeof(*tris) * totfilltri);
projverts = BLI_memarena_alloc(arena, (int)sizeof(*projverts) * mp->totloop);
zero_v3(normal);
#endif
ml = mloop + mp->loopstart;
if (UNLIKELY(sf_arena == NULL)) {
sf_arena = BLI_memarena_new(BLI_SCANFILL_ARENA_SIZE, __func__);
}
BLI_scanfill_begin_arena(&sf_ctx, sf_arena);
sf_vert_first = NULL;
sf_vert_last = NULL;
/* calc normal */
ml = mloop + loopstart;
co_prev = mvert[ml[mp->totloop - 1].v].co;
for (j = 0; j < mp->totloop; j++, ml++) {
sf_vert = BLI_scanfill_vert_add(&sf_ctx, mvert[ml->v].co);
sf_vert->keyindex = (unsigned int)(mp->loopstart + j);
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
}
if (!sf_vert_first)
sf_vert_first = sf_vert;
sf_vert_last = sf_vert;
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);

265
source/blender/bmesh/intern/bmesh_polygon.c
View File

@ -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);
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;
/* 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;
//BLI_assert(BM_face_is_normal_valid(f));
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;
axis_dominant_v3_to_m3(axis_mat, f->no);
sf_vert->tmp.p = l_iter;
sf_vert_prev = sf_vert;
} while ((l_iter = l_iter->next) != l_first);
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);
}
sf_edge = BLI_scanfill_edge_add(&sf_ctx, sf_vert_prev, sf_ctx.fillvertbase.first);
sf_edge->tmp.c = SF_EDGE_IS_BOUNDARY;
/* calculate filled triangles */
totfilltri = BLI_scanfill_calc_ex(&sf_ctx, 0, f->no);
BLI_assert(totfilltri <= f->len - 2);
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 and create new geometry */
for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) {
for (i = 0; i < totfilltri; i++) {
/* 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};
loops[tris[i][2]],
loops[tris[i][1]],
loops[tris[i][0]]};
BMVert *v_tri[3] = {
l_tri[0]->v,
@ -969,7 +914,7 @@ void BM_face_triangulate(BMesh *bm, BMFace *f,
BM_elem_attrs_copy(bm, bm, l_tri[2], l_new->prev);
/* add all but the last face which is swapped and removed (below) */
if (sf_tri->next) {
if (i != last_tri) {
if (use_tag) {
BM_elem_flag_enable(f_new, BM_ELEM_TAG);
}
@ -977,35 +922,36 @@ void BM_face_triangulate(BMesh *bm, BMFace *f,
r_faces_new[nf_i++] = f_new;
}
}
}
if (use_beauty || use_tag) {
ScanFillEdge *sf_edge;
edge_array = BLI_array_alloca(edge_array, orig_f_len - 3);
edge_array_len = 0;
/* we know any edge that we create and _isnt_ */
if (use_beauty || use_tag) {
/* new faces loops */
l_iter = l_first = l_new;
do {
BMEdge *e = l_iter->e;
/* confusing! if its not a boundary now, we know it will be later
* since this will be an edge of one of the new faces which we're in the middle of creating */
bool is_new_edge = (l_iter == l_iter->radial_next);
for (sf_edge = sf_ctx.filledgebase.first; sf_edge; sf_edge = sf_edge->next) {
BMLoop *l1 = sf_edge->v1->tmp.p;
BMLoop *l2 = sf_edge->v2->tmp.p;
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++;
}
BMEdge *e = BM_edge_exists(l1->v, l2->v);
if (sf_edge->tmp.c != SF_EDGE_IS_BOUNDARY) {
if (use_tag) {
BM_elem_flag_enable(e, BM_ELEM_TAG);
if (use_beauty) {
BM_elem_index_set(e, edge_array_len); /* set_dirty */
edge_array[edge_array_len] = e;
edge_array_len++;
}
}
if (use_tag) {
BM_elem_flag_enable(e, BM_ELEM_TAG);
else {
if (use_tag) {
BM_elem_flag_disable(e, BM_ELEM_TAG);
}
}
}
else if (use_tag) {
BM_elem_flag_disable(e, BM_ELEM_TAG);
}
} while ((l_iter = l_iter->next) != l_first);
}
}
if ((!use_beauty) || (!r_faces_new)) {
@ -1016,6 +962,8 @@ 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);
@ -1075,13 +1023,7 @@ void BM_face_triangulate(BMesh *bm, BMFace *f,
BM_face_kill(bm, f_new);
}
}
/* garbage collection */
BLI_scanfill_end_arena(&sf_ctx, sf_arena);
}
#undef SF_EDGE_IS_BOUNDARY
}
/**
@ -1290,11 +1232,9 @@ void BM_bmesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptr
BMIter iter;
BMFace *efa;
BMLoop *l;
int i = 0;
ScanFillContext sf_ctx;
MemArena *sf_arena = NULL;
MemArena *arena = NULL;
BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) {
/* don't consider two-edged faces */
@ -1315,6 +1255,7 @@ void BM_bmesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptr
i += 1;
#else
/* more cryptic but faster */
BMLoop *l;
BMLoop **l_ptr = looptris[i++];
l_ptr[0] = l = BM_FACE_FIRST_LOOP(efa);
l_ptr[1] = l = l->next;
@ -1341,6 +1282,7 @@ void BM_bmesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptr
i += 1;
#else
/* more cryptic but faster */
BMLoop *l;
BMLoop **l_ptr_a = looptris[i++];
BMLoop **l_ptr_b = looptris[i++];
(l_ptr_a[0] = l_ptr_b[0] = l = BM_FACE_FIRST_LOOP(efa));
@ -1354,70 +1296,53 @@ void BM_bmesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptr
else {
int j;
BMLoop *l_iter;
BMLoop *l_first;
BMLoop **l_arr;
ScanFillVert *sf_vert, *sf_vert_last = NULL, *sf_vert_first = NULL;
/* ScanFillEdge *e; */ /* UNUSED */
ScanFillFace *sf_tri;
int totfilltri;
float axis_mat[3][3];
float (*projverts)[2];
unsigned int (*tris)[3];
if (UNLIKELY(sf_arena == NULL)) {
sf_arena = BLI_memarena_new(BLI_SCANFILL_ARENA_SIZE, __func__);
const int totfilltri = efa->len - 2;
if (UNLIKELY(arena == NULL)) {
arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
}
BLI_scanfill_begin_arena(&sf_ctx, sf_arena);
tris = BLI_memarena_alloc(arena, sizeof(*tris) * totfilltri);
l_arr = BLI_memarena_alloc(arena, sizeof(*l_arr) * efa->len);
projverts = BLI_memarena_alloc(arena, sizeof(*projverts) * efa->len);
axis_dominant_v3_to_m3(axis_mat, efa->no);
/* scanfill time */
j = 0;
l_iter = l_first = BM_FACE_FIRST_LOOP(efa);
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;
}
/*mark order */
BM_elem_index_set(l_iter, j++); /* set_loop */
l_arr[j] = l_iter;
mul_v2_m3v3(projverts[j], axis_mat, l_iter->v->co);
j++;
} while ((l_iter = l_iter->next) != l_first);
/* complete the loop */
BLI_scanfill_edge_add(&sf_ctx, sf_vert_first, sf_vert);
BLI_polyfill_calc_arena((const float (*)[2])projverts, efa->len, tris, arena);
totfilltri = BLI_scanfill_calc_ex(&sf_ctx, 0, efa->no);
BLI_assert(totfilltri <= efa->len - 2);
(void)totfilltri;
for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) {
for (j = 0; j < totfilltri; j++) {
BMLoop **l_ptr = looptris[i++];
BMLoop *l1 = sf_tri->v1->tmp.p;
BMLoop *l2 = sf_tri->v2->tmp.p;
BMLoop *l3 = sf_tri->v3->tmp.p;
unsigned int *tri = tris[j];
if (BM_elem_index_get(l1) > BM_elem_index_get(l2)) { SWAP(BMLoop *, l1, l2); }
if (BM_elem_index_get(l2) > BM_elem_index_get(l3)) { SWAP(BMLoop *, l2, l3); }
if (BM_elem_index_get(l1) > BM_elem_index_get(l2)) { SWAP(BMLoop *, l1, l2); }
l_ptr[0] = l1;
l_ptr[1] = l2;
l_ptr[2] = l3;
l_ptr[0] = l_arr[tri[2]];
l_ptr[1] = l_arr[tri[1]];
l_ptr[2] = l_arr[tri[0]];
}
BLI_scanfill_end_arena(&sf_ctx, sf_arena);
BLI_memarena_clear(arena);
}
}
if (sf_arena) {
BLI_memarena_free(sf_arena);
sf_arena = NULL;
if (arena) {
BLI_memarena_free(arena);
arena = NULL;
}
*r_looptris_tot = i;

2
source/blender/bmesh/intern/bmesh_polygon.h
View File

@ -31,7 +31,7 @@
void BM_bmesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptris_tot);
int BM_face_calc_tessellation(const BMFace *f, BMLoop **r_loops, int (*r_index)[3]) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();
void BM_face_calc_tessellation(const BMFace *f, BMLoop **r_loops, unsigned int (*r_index)[3]);
void BM_face_calc_normal(const BMFace *f, float r_no[3]) ATTR_NONNULL();
void BM_face_calc_normal_vcos(BMesh *bm, BMFace *f, float r_no[3],
float const (*vertexCos)[3]) ATTR_NONNULL();

9
source/blender/bmesh/intern/bmesh_queries.c
View File

@ -1886,13 +1886,12 @@ bool BM_face_is_normal_valid(const BMFace *f)
static void bm_mesh_calc_volume_face(const BMFace *f, float *r_vol)
{
int tottri = f->len - 2;
BMLoop **loops = BLI_array_alloca(loops, f->len);
int (*index)[3] = BLI_array_alloca(index, tottri);
const int tottri = f->len - 2;
BMLoop **loops = BLI_array_alloca(loops, f->len);
unsigned int (*index)[3] = BLI_array_alloca(index, tottri);
int j;
tottri = BM_face_calc_tessellation(f, loops, index);
BLI_assert(tottri <= f->len - 2);
BM_face_calc_tessellation(f, loops, index);
for (j = 0; j < tottri; j++) {
const float *p1 = loops[index[j][0]]->v->co;

9
source/blender/editors/mesh/editmesh_knife.c
View File

@ -2913,17 +2913,16 @@ void MESH_OT_knife_tool(wmOperatorType *ot)
*/
static void edvm_mesh_knife_face_point(BMFace *f, float r_cent[3])
{
int tottri = f->len - 2;
BMLoop **loops = BLI_array_alloca(loops, f->len);
int (*index)[3] = BLI_array_alloca(index, tottri);
const int tottri = f->len - 2;
BMLoop **loops = BLI_array_alloca(loops, f->len);
unsigned int (*index)[3] = BLI_array_alloca(index, tottri);
int j;
float const *best_co[3] = {NULL};
float best_area = -1.0f;
bool ok = false;
tottri = BM_face_calc_tessellation(f, loops, index);
BLI_assert(tottri <= f->len - 2);
BM_face_calc_tessellation(f, loops, index);
for (j = 0; j < tottri; j++) {
const float *p1 = loops[index[j][0]]->v->co;