diff options
author | Bastien Montagne <montagne29@wanadoo.fr> | 2014-01-21 19:32:36 +0400 |
---|---|---|
committer | Bastien Montagne <montagne29@wanadoo.fr> | 2014-01-21 19:32:47 +0400 |
commit | c691551249f3fe3982c43e4c75be40a19503dd26 (patch) | |
tree | 3332a4f50ff5e6df3884a44334b07e578d619840 /source/blender | |
parent | cda894fcfd6a19f48eeb745af49800b5165f936c (diff) |
Optimize tessellation code (min 20% better, up to 300% with some CD layers to tessellate).
The main idea is to store (during tessellation) or recreate (during tessdata update) a tessfaceverts-to-loops mapping, and then update all tessdata
in one pass, instead of calling `BKE_mesh_loops_to_mface_corners` repeatedly for all tfaces!
Differential Revision: https://developer.blender.org/D226
Reviewed by Campbell, thanks a lot!
Diffstat (limited to 'source/blender')
-rw-r--r-- | source/blender/blenkernel/BKE_mesh.h | 3 | ||||
-rw-r--r-- | source/blender/blenkernel/BKE_mesh_mapping.h | 9 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/DerivedMesh.c | 65 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/mesh_evaluate.c | 240 | ||||
-rw-r--r-- | source/blender/editors/sculpt_paint/paint_vertex.c | 11 |
5 files changed, 187 insertions, 141 deletions
diff --git a/source/blender/blenkernel/BKE_mesh.h b/source/blender/blenkernel/BKE_mesh.h index e82689ec339..302f71e61bf 100644 --- a/source/blender/blenkernel/BKE_mesh.h +++ b/source/blender/blenkernel/BKE_mesh.h @@ -215,6 +215,9 @@ void BKE_mesh_loops_to_mface_corners( const int polyindex, const int mf_len, const int numTex, const int numCol, const bool hasPCol, const bool hasOrigSpace); +void BKE_mesh_loops_to_tessdata( + struct CustomData *fdata, struct CustomData *ldata, struct CustomData *pdata, + int *polyindices, unsigned int (*loopindices)[4], const int num_faces); int BKE_mesh_recalc_tessellation( struct CustomData *fdata, struct CustomData *ldata, struct CustomData *pdata, struct MVert *mvert, diff --git a/source/blender/blenkernel/BKE_mesh_mapping.h b/source/blender/blenkernel/BKE_mesh_mapping.h index ee9e63e6975..f3f6b556a07 100644 --- a/source/blender/blenkernel/BKE_mesh_mapping.h +++ b/source/blender/blenkernel/BKE_mesh_mapping.h @@ -129,4 +129,13 @@ int *BKE_mesh_calc_smoothgroups( const struct MLoop *mloop, const int totloop, int *r_totgroup, const bool use_bitflags); +/* No good (portable) way to have exported inlined functions... */ +#define BKE_MESH_TESSFACE_VINDEX_ORDER(_mf, _v) ( \ + (CHECK_TYPE_INLINE(_mf, MFace *), CHECK_TYPE_INLINE(_v, unsigned int)), \ + ((_mf->v1 == _v) ? 0 : \ + (_mf->v2 == _v) ? 1 : \ + (_mf->v3 == _v) ? 2 : \ + (_mf->v4 && _mf->v4 == _v) ? 3 : -1) \ + ) + #endif /* __BKE_MESH_MAPPING_H__ */ diff --git a/source/blender/blenkernel/intern/DerivedMesh.c b/source/blender/blenkernel/intern/DerivedMesh.c index ee7d89071d3..c1424381ce6 100644 --- a/source/blender/blenkernel/intern/DerivedMesh.c +++ b/source/blender/blenkernel/intern/DerivedMesh.c @@ -56,6 +56,7 @@ #include "BKE_key.h" #include "BKE_modifier.h" #include "BKE_mesh.h" +#include "BKE_mesh_mapping.h" #include "BKE_object.h" #include "BKE_object_deform.h" #include "BKE_paint.h" @@ -431,16 +432,11 @@ void DM_update_tessface_data(DerivedMesh *dm) CustomData *pdata = dm->getPolyDataLayout(dm); CustomData *ldata = dm->getLoopDataLayout(dm); - const int numTex = CustomData_number_of_layers(pdata, CD_MTEXPOLY); - const int numCol = CustomData_number_of_layers(ldata, CD_MLOOPCOL); - const int hasPCol = CustomData_has_layer(ldata, CD_PREVIEW_MLOOPCOL); - const int hasOrigSpace = CustomData_has_layer(ldata, CD_ORIGSPACE_MLOOP); - - int *polyindex = CustomData_get_layer(fdata, CD_ORIGINDEX); - const int totface = dm->getNumTessFaces(dm); int mf_idx; - int ml_idx[4]; + + int *polyindex = CustomData_get_layer(fdata, CD_ORIGINDEX); + unsigned int (*loopindex)[4]; /* Should never occure, but better abort than segfault! */ if (!polyindex) @@ -448,36 +444,35 @@ void DM_update_tessface_data(DerivedMesh *dm) CustomData_from_bmeshpoly(fdata, pdata, ldata, totface); - for (mf_idx = 0; mf_idx < totface; mf_idx++, mf++) { - const int mf_len = mf->v4 ? 4 : 3; - int i, not_done; - - /* Find out loop indices. */ - /* XXX Is there a better way to do this? */ - /* NOTE: This assumes tessface are valid and in sync with loop/poly... Else, most likely, segfault! */ - for (i = mp[polyindex[mf_idx]].loopstart, not_done = mf_len; not_done; i++) { - MLoop *tml = &ml[i]; - if (tml->v == mf->v1) { - ml_idx[0] = i; - not_done--; - } - else if (tml->v == mf->v2) { - ml_idx[1] = i; - not_done--; - } - else if (tml->v == mf->v3) { - ml_idx[2] = i; - not_done--; + if (CustomData_has_layer(fdata, CD_MTFACE) || + CustomData_has_layer(fdata, CD_MCOL) || + CustomData_has_layer(fdata, CD_PREVIEW_MCOL) || + CustomData_has_layer(fdata, CD_ORIGSPACE)) + { + loopindex = MEM_mallocN(sizeof(*loopindex) * totface, __func__); + + for (mf_idx = 0; mf_idx < totface; mf_idx++, mf++) { + const int mf_len = mf->v4 ? 4 : 3; + unsigned int *ml_idx = loopindex[mf_idx]; + int i, not_done; + + /* Find out loop indices. */ + /* NOTE: This assumes tessface are valid and in sync with loop/poly... Else, most likely, segfault! */ + for (i = mp[polyindex[mf_idx]].loopstart, not_done = mf_len; not_done; i++) { + const int tf_v = BKE_MESH_TESSFACE_VINDEX_ORDER(mf, ml[i].v); + if (tf_v != -1) { + ml_idx[tf_v] = i; + not_done--; + } } - else if (mf_len == 4 && tml->v == mf->v4) { - ml_idx[3] = i; - not_done--; + if (mf_len == 3) { + ml_idx[3] = 0; } } - BKE_mesh_loops_to_mface_corners(fdata, ldata, pdata, - ml_idx, mf_idx, polyindex[mf_idx], - mf_len, - numTex, numCol, hasPCol, hasOrigSpace); + + BKE_mesh_loops_to_tessdata(fdata, ldata, pdata, polyindex, loopindex, totface); + + MEM_freeN(loopindex); } if (G.debug & G_DEBUG) diff --git a/source/blender/blenkernel/intern/mesh_evaluate.c b/source/blender/blenkernel/intern/mesh_evaluate.c index 7759e53473a..d1b1c5c1fb0 100644 --- a/source/blender/blenkernel/intern/mesh_evaluate.c +++ b/source/blender/blenkernel/intern/mesh_evaluate.c @@ -1155,6 +1155,72 @@ void BKE_mesh_loops_to_mface_corners( } /** + * Convert all CD layers from loop/poly to tessface data. + * @loopindices is an array of an int[4] per tessface, mapping tessface's verts to loops indices. + */ +void BKE_mesh_loops_to_tessdata(CustomData *fdata, CustomData *ldata, CustomData *pdata, + int *polyindices, unsigned int (*loopindices)[4], const int num_faces) +{ + const int numTex = CustomData_number_of_layers(pdata, CD_MTEXPOLY); + const int numCol = CustomData_number_of_layers(ldata, CD_MLOOPCOL); + const bool hasPCol = CustomData_has_layer(ldata, CD_PREVIEW_MLOOPCOL); + const bool hasOrigSpace = CustomData_has_layer(ldata, CD_ORIGSPACE_MLOOP); + int findex, i, j; + int *pidx; + unsigned int (*lidx)[4]; + + for (i = 0; i < numTex; i++) { + MTFace *texface = CustomData_get_layer_n(fdata, CD_MTFACE, i); + MTexPoly *texpoly = CustomData_get_layer_n(pdata, CD_MTEXPOLY, i); + MLoopUV *mloopuv = CustomData_get_layer_n(ldata, CD_MLOOPUV, i); + + for (findex = 0, pidx = polyindices, lidx = loopindices; + findex < num_faces; + pidx++, lidx++, findex++, texface++) + { + ME_MTEXFACE_CPY(texface, &texpoly[*pidx]); + + for (j = (*lidx)[3] ? 4 : 3; j--;) { + copy_v2_v2(texface->uv[j], mloopuv[(*lidx)[j]].uv); + } + } + } + + for (i = 0; i < numCol; i++) { + MCol (*mcol)[4] = CustomData_get_layer_n(fdata, CD_MCOL, i); + MLoopCol *mloopcol = CustomData_get_layer_n(ldata, CD_MLOOPCOL, i); + + for (findex = 0, lidx = loopindices; findex < num_faces; lidx++, findex++, mcol++) { + for (j = (*lidx)[3] ? 4 : 3; j--;) { + MESH_MLOOPCOL_TO_MCOL(&mloopcol[(*lidx)[j]], &(*mcol)[j]); + } + } + } + + if (hasPCol) { + MCol (*mcol)[4] = CustomData_get_layer(fdata, CD_PREVIEW_MCOL); + MLoopCol *mloopcol = CustomData_get_layer(ldata, CD_PREVIEW_MLOOPCOL); + + for (findex = 0, lidx = loopindices; findex < num_faces; lidx++, findex++, mcol++) { + for (j = (*lidx)[3] ? 4 : 3; j--;) { + MESH_MLOOPCOL_TO_MCOL(&mloopcol[(*lidx)[j]], &(*mcol)[j]); + } + } + } + + if (hasOrigSpace) { + OrigSpaceFace *of = CustomData_get_layer(fdata, CD_ORIGSPACE); + OrigSpaceLoop *lof = CustomData_get_layer(ldata, CD_ORIGSPACE_MLOOP); + + for (findex = 0, lidx = loopindices; findex < num_faces; lidx++, findex++, of++) { + for (j = (*lidx)[3] ? 4 : 3; j--;) { + copy_v2_v2(of->uv[j], lof[(*lidx)[j]].uv); + } + } + } +} + +/** * Recreate tessellation. * * use_poly_origindex sets whether or not the tessellation faces' origindex @@ -1168,10 +1234,8 @@ void BKE_mesh_loops_to_mface_corners( * * \return number of tessellation faces. */ -int BKE_mesh_recalc_tessellation(CustomData *fdata, - CustomData *ldata, CustomData *pdata, - MVert *mvert, int totface, int totloop, - int totpoly, +int BKE_mesh_recalc_tessellation(CustomData *fdata, CustomData *ldata, CustomData *pdata, + MVert *mvert, int totface, int totloop, int totpoly, /* when tessellating to recalculate normals after * we can skip copying here */ const bool do_face_nor_cpy) @@ -1182,9 +1246,6 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata, #define USE_TESSFACE_SPEEDUP #define USE_TESSFACE_QUADS // NEEDS FURTHER TESTING -#define TESSFACE_SCANFILL (1 << 0) -#define TESSFACE_IS_QUAD (1 << 1) - const int looptris_tot = poly_to_tri_count(totpoly, totloop); MPoly *mp, *mpoly; @@ -1192,13 +1253,9 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata, MFace *mface, *mf; MemArena *arena = NULL; int *mface_to_poly_map; - int lindex[4]; /* only ever use 3 in this case */ - int poly_index, j, mface_index; - - const int numTex = CustomData_number_of_layers(pdata, CD_MTEXPOLY); - const int numCol = CustomData_number_of_layers(ldata, CD_MLOOPCOL); - const bool hasPCol = CustomData_has_layer(ldata, CD_PREVIEW_MLOOPCOL); - const bool hasOrigSpace = CustomData_has_layer(ldata, CD_ORIGSPACE_MLOOP); + unsigned int (*lindices)[4]; + int poly_index, mface_index; + unsigned int j; mpoly = CustomData_get_layer(pdata, CD_MPOLY); mloop = CustomData_get_layer(ldata, CD_MLOOP); @@ -1208,12 +1265,16 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata, /* take care. we are _not_ calloc'ing so be sure to initialize each field */ mface_to_poly_map = MEM_mallocN(sizeof(*mface_to_poly_map) * (size_t)looptris_tot, __func__); mface = MEM_mallocN(sizeof(*mface) * (size_t)looptris_tot, __func__); + lindices = MEM_mallocN(sizeof(*lindices) * (size_t)looptris_tot, __func__); mface_index = 0; mp = mpoly; for (poly_index = 0; poly_index < totpoly; poly_index++, mp++) { const unsigned int mp_loopstart = (unsigned int)mp->loopstart; - if (mp->totloop < 3) { + const unsigned int mp_totloop = (unsigned int)mp->totloop; + unsigned int l1, l2, l3, l4; + unsigned int *lidx; + if (mp_totloop < 3) { /* do nothing */ } @@ -1222,36 +1283,51 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata, #define ML_TO_MF(i1, i2, i3) \ mface_to_poly_map[mface_index] = poly_index; \ mf = &mface[mface_index]; \ + lidx = lindices[mface_index]; \ /* set loop indices, transformed to vert indices later */ \ - mf->v1 = mp_loopstart + i1; \ - mf->v2 = mp_loopstart + i2; \ - mf->v3 = mp_loopstart + i3; \ + l1 = mp_loopstart + i1; \ + l2 = mp_loopstart + i2; \ + l3 = mp_loopstart + i3; \ + mf->v1 = mloop[l1].v; \ + mf->v2 = mloop[l2].v; \ + mf->v3 = mloop[l3].v; \ mf->v4 = 0; \ + lidx[0] = l1; \ + lidx[1] = l2; \ + lidx[2] = l3; \ + lidx[3] = 0; \ mf->mat_nr = mp->mat_nr; \ mf->flag = mp->flag; \ - mf->edcode = 0; \ (void)0 /* ALMOST IDENTICAL TO DEFINE ABOVE (see EXCEPTION) */ #define ML_TO_MF_QUAD() \ mface_to_poly_map[mface_index] = poly_index; \ mf = &mface[mface_index]; \ + lidx = lindices[mface_index]; \ /* set loop indices, transformed to vert indices later */ \ - mf->v1 = mp_loopstart + 0; /* EXCEPTION */ \ - mf->v2 = mp_loopstart + 1; /* EXCEPTION */ \ - mf->v3 = mp_loopstart + 2; /* EXCEPTION */ \ - mf->v4 = mp_loopstart + 3; /* EXCEPTION */ \ + l1 = mp_loopstart + 0; /* EXCEPTION */ \ + l2 = mp_loopstart + 1; /* EXCEPTION */ \ + l3 = mp_loopstart + 2; /* EXCEPTION */ \ + l4 = mp_loopstart + 3; /* EXCEPTION */ \ + mf->v1 = mloop[l1].v; \ + mf->v2 = mloop[l2].v; \ + mf->v3 = mloop[l3].v; \ + mf->v4 = mloop[l4].v; \ + lidx[0] = l1; \ + lidx[1] = l2; \ + lidx[2] = l3; \ + lidx[3] = l4; \ mf->mat_nr = mp->mat_nr; \ mf->flag = mp->flag; \ - mf->edcode = TESSFACE_IS_QUAD; /* EXCEPTION */ \ (void)0 - else if (mp->totloop == 3) { + else if (mp_totloop == 3) { ML_TO_MF(0, 1, 2); mface_index++; } - else if (mp->totloop == 4) { + else if (mp_totloop == 4) { #ifdef USE_TESSFACE_QUADS ML_TO_MF_QUAD(); mface_index++; @@ -1272,22 +1348,21 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata, float (*projverts)[2]; unsigned int (*tris)[3]; - const unsigned int loopstart = (unsigned int)mp->loopstart; - const int totfilltri = mp->totloop - 2; + const unsigned int totfilltri = mp_totloop - 2; if (UNLIKELY(arena == NULL)) { arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__); } tris = BLI_memarena_alloc(arena, sizeof(*tris) * (size_t)totfilltri); - projverts = BLI_memarena_alloc(arena, sizeof(*projverts) * (size_t)mp->totloop); + projverts = BLI_memarena_alloc(arena, sizeof(*projverts) * (size_t)mp_totloop); zero_v3(normal); /* calc normal */ - ml = mloop + loopstart; - co_prev = mvert[ml[mp->totloop - 1].v].co; - for (j = 0; j < mp->totloop; j++, ml++) { + ml = mloop + mp_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; @@ -1299,34 +1374,44 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata, /* project verts to 2d */ axis_dominant_v3_to_m3(axis_mat, normal); - ml = mloop + loopstart; - for (j = 0; j < mp->totloop; j++, ml++) { + ml = mloop + mp_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); + BLI_polyfill_calc_arena((const float (*)[2])projverts, mp_totloop, tris, arena); /* apply fill */ - ml = mloop + loopstart; for (j = 0; j < totfilltri; j++) { unsigned int *tri = tris[j]; + lidx = lindices[mface_index]; mface_to_poly_map[mface_index] = poly_index; mf = &mface[mface_index]; /* set loop indices, transformed to vert indices later */ - mf->v1 = loopstart + tri[0]; - mf->v2 = loopstart + tri[1]; - mf->v3 = loopstart + tri[2]; + l1 = mp_loopstart + tri[0]; + l2 = mp_loopstart + tri[1]; + l3 = mp_loopstart + tri[2]; + + /* sort loop indices to ensure winding is correct */ + if (l1 > l2) SWAP(unsigned int, l1, l2); + if (l2 > l3) SWAP(unsigned int, l2, l3); + if (l1 > l2) SWAP(unsigned int, l1, l2); + + mf->v1 = mloop[l1].v; + mf->v2 = mloop[l2].v; + mf->v3 = mloop[l3].v; mf->v4 = 0; + lidx[0] = l1; + lidx[1] = l2; + lidx[2] = l3; + lidx[3] = 0; + mf->mat_nr = mp->mat_nr; mf->flag = mp->flag; -#ifdef USE_TESSFACE_SPEEDUP - mf->edcode = TESSFACE_SCANFILL; /* tag for sorting loop indices */ -#endif - mface_index++; } @@ -1369,71 +1454,34 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata, } } - mf = mface; - for (mface_index = 0; mface_index < totface; mface_index++, mf++) { - -#ifdef USE_TESSFACE_QUADS - const int mf_len = mf->edcode & TESSFACE_IS_QUAD ? 4 : 3; -#endif - -#ifdef USE_TESSFACE_SPEEDUP - /* skip sorting when not using ngons */ - if (UNLIKELY(mf->edcode & TESSFACE_SCANFILL)) -#endif - { - /* sort loop indices to ensure winding is correct */ - if (mf->v1 > mf->v2) SWAP(unsigned int, mf->v1, mf->v2); - if (mf->v2 > mf->v3) SWAP(unsigned int, mf->v2, mf->v3); - if (mf->v1 > mf->v2) SWAP(unsigned int, mf->v1, mf->v2); - - if (mf->v1 > mf->v2) SWAP(unsigned int, mf->v1, mf->v2); - if (mf->v2 > mf->v3) SWAP(unsigned int, mf->v2, mf->v3); - if (mf->v1 > mf->v2) SWAP(unsigned int, mf->v1, mf->v2); - } - - /* end abusing the edcode */ -#if defined(USE_TESSFACE_QUADS) || defined(USE_TESSFACE_SPEEDUP) - mf->edcode = 0; -#endif - - - lindex[0] = (int)mf->v1; - lindex[1] = (int)mf->v2; - lindex[2] = (int)mf->v3; -#ifdef USE_TESSFACE_QUADS - if (mf_len == 4) lindex[3] = (int)mf->v4; -#endif + BKE_mesh_loops_to_tessdata(fdata, ldata, pdata, mface_to_poly_map, lindices, totface); - /*transform loop indices to vert indices*/ - mf->v1 = mloop[mf->v1].v; - mf->v2 = mloop[mf->v2].v; - mf->v3 = mloop[mf->v3].v; + /* XXX Is it really needed to call test_index_face here??? Since we reuse tris/quads as-is, and sort tris generated + * by scanfill, our indices should always be OK? + */ +#if 0 #ifdef USE_TESSFACE_QUADS - if (mf_len == 4) mf->v4 = mloop[mf->v4].v; -#endif + mf = mface; + for (mface_index = 0; mface_index < totface; mface_index++, mf++) { + const int mf_len = mf->v4 ? 4 : 3; - BKE_mesh_loops_to_mface_corners(fdata, ldata, pdata, - lindex, mface_index, mface_to_poly_map[mface_index], -#ifdef USE_TESSFACE_QUADS - mf_len, -#else - 3, + if (test_index_face(mf, fdata, mface_index, mf_len) != mf_len) + printf("%s: test_index_face had to make changes!!!\n", __func__); + } #endif - numTex, numCol, hasPCol, hasOrigSpace); - - -#ifdef USE_TESSFACE_QUADS - test_index_face(mf, fdata, mface_index, mf_len); #endif - } + MEM_freeN(lindices); return totface; #undef USE_TESSFACE_SPEEDUP +#undef USE_TESSFACE_QUADS -} +#undef ML_TO_MF +#undef ML_TO_MF_QUAD +} #ifdef USE_BMESH_SAVE_AS_COMPAT diff --git a/source/blender/editors/sculpt_paint/paint_vertex.c b/source/blender/editors/sculpt_paint/paint_vertex.c index e03c5b5600c..9c9b8d84a21 100644 --- a/source/blender/editors/sculpt_paint/paint_vertex.c +++ b/source/blender/editors/sculpt_paint/paint_vertex.c @@ -2847,15 +2847,6 @@ static int vpaint_stroke_test_start(bContext *C, struct wmOperator *op, const fl return 1; } -BLI_INLINE int mesh_tessface_vertex_index(MFace *tessface, unsigned int v) -{ - if (tessface->v1 == v) return 0; - if (tessface->v2 == v) return 1; - if (tessface->v3 == v) return 2; - if (v && (tessface->v4 == v)) return 3; - return -1; -} - static void vpaint_paint_poly(VPaint *vp, VPaintData *vpd, Mesh *me, const unsigned int index, const float mval[2], const float brush_size_pressure, const float brush_alpha_pressure) @@ -2945,7 +2936,7 @@ static void vpaint_paint_poly(VPaint *vp, VPaintData *vpd, Mesh *me, for (j = 0; j < totloop; j++, ml++, mlc++) { /* search for the loop vertex within the tessface */ - const int fidx = mesh_tessface_vertex_index(mf, ml->v); + const int fidx = BKE_MESH_TESSFACE_VINDEX_ORDER(mf, ml->v); if (fidx != -1) { MESH_MLOOPCOL_TO_MCOL(mlc, mc + fidx); if (mlooptag) { |