diff options
| -rw-r--r-- | source/blender/blenkernel/BKE_mesh.h | 47 | ||||
| -rw-r--r-- | source/blender/blenkernel/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | source/blender/blenkernel/intern/mesh.c | 16 | ||||
| -rw-r--r-- | source/blender/blenkernel/intern/mesh_evaluate.c | 513 | ||||
| -rw-r--r-- | source/blender/blenkernel/intern/mesh_tessellate.c | 584 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_mesh_tessellate.c | 2 |
6 files changed, 613 insertions, 550 deletions
diff --git a/source/blender/blenkernel/BKE_mesh.h b/source/blender/blenkernel/BKE_mesh.h index c24e87b3788..2a1fbc8273b 100644 --- a/source/blender/blenkernel/BKE_mesh.h +++ b/source/blender/blenkernel/BKE_mesh.h @@ -247,7 +247,6 @@ bool BKE_mesh_minmax(const struct Mesh *me, float r_min[3], float r_max[3]); void BKE_mesh_transform(struct Mesh *me, const float mat[4][4], bool do_keys); void BKE_mesh_translate(struct Mesh *me, const float offset[3], const bool do_keys); -void BKE_mesh_tessface_calc(struct Mesh *mesh); void BKE_mesh_tessface_ensure(struct Mesh *mesh); void BKE_mesh_tessface_clear(struct Mesh *mesh); @@ -270,6 +269,32 @@ void BKE_mesh_vert_coords_apply_with_mat4(struct Mesh *mesh, void BKE_mesh_vert_coords_apply(struct Mesh *mesh, const float (*vert_coords)[3]); void BKE_mesh_vert_normals_apply(struct Mesh *mesh, const short (*vert_normals)[3]); +/* *** mesh_tessellate.c *** */ + +void BKE_mesh_loops_to_tessdata(struct CustomData *fdata, + struct CustomData *ldata, + struct MFace *mface, + const int *polyindices, + unsigned int (*loopindices)[4], + const int num_faces); + +int BKE_mesh_tessface_calc_ex(struct CustomData *fdata, + struct CustomData *ldata, + struct CustomData *pdata, + struct MVert *mvert, + int totface, + int totloop, + int totpoly, + const bool do_face_nor_copy); +void BKE_mesh_tessface_calc(struct Mesh *mesh); + +void BKE_mesh_recalc_looptri(const struct MLoop *mloop, + const struct MPoly *mpoly, + const struct MVert *mvert, + int totloop, + int totpoly, + struct MLoopTri *mlooptri); + /* *** mesh_evaluate.c *** */ void BKE_mesh_calc_normals_mapping_simple(struct Mesh *me); @@ -521,12 +546,6 @@ void BKE_mesh_loops_to_mface_corners(struct CustomData *fdata, const bool hasPCol, const bool hasOrigSpace, const bool hasLNor); -void BKE_mesh_loops_to_tessdata(struct CustomData *fdata, - struct CustomData *ldata, - struct MFace *mface, - const int *polyindices, - unsigned int (*loopindices)[4], - const int num_faces); void BKE_mesh_tangent_loops_to_tessdata(struct CustomData *fdata, struct CustomData *ldata, struct MFace *mface, @@ -534,20 +553,6 @@ void BKE_mesh_tangent_loops_to_tessdata(struct CustomData *fdata, unsigned int (*loopindices)[4], const int num_faces, const char *layer_name); -int BKE_mesh_tessface_calc_ex(struct CustomData *fdata, - struct CustomData *ldata, - struct CustomData *pdata, - struct MVert *mvert, - int totface, - int totloop, - int totpoly, - const bool do_face_nor_copy); -void BKE_mesh_recalc_looptri(const struct MLoop *mloop, - const struct MPoly *mpoly, - const struct MVert *mvert, - int totloop, - int totpoly, - struct MLoopTri *mlooptri); void BKE_mesh_convert_mfaces_to_mpolys(struct Mesh *mesh); void BKE_mesh_do_versions_convert_mfaces_to_mpolys(struct Mesh *mesh); void BKE_mesh_convert_mfaces_to_mpolys_ex(struct ID *id, diff --git a/source/blender/blenkernel/CMakeLists.txt b/source/blender/blenkernel/CMakeLists.txt index 021d7e15814..0f36887b234 100644 --- a/source/blender/blenkernel/CMakeLists.txt +++ b/source/blender/blenkernel/CMakeLists.txt @@ -194,6 +194,7 @@ set(SRC intern/mesh_runtime.c intern/mesh_sample.cc intern/mesh_tangent.c + intern/mesh_tessellate.c intern/mesh_validate.c intern/mesh_validate.cc intern/mesh_wrapper.c diff --git a/source/blender/blenkernel/intern/mesh.c b/source/blender/blenkernel/intern/mesh.c index 0068821bab0..b70fea459f6 100644 --- a/source/blender/blenkernel/intern/mesh.c +++ b/source/blender/blenkernel/intern/mesh.c @@ -1554,22 +1554,6 @@ void BKE_mesh_translate(Mesh *me, const float offset[3], const bool do_keys) } } -void BKE_mesh_tessface_calc(Mesh *mesh) -{ - mesh->totface = BKE_mesh_tessface_calc_ex( - &mesh->fdata, - &mesh->ldata, - &mesh->pdata, - mesh->mvert, - mesh->totface, - mesh->totloop, - mesh->totpoly, - /* calc normals right after, don't copy from polys here */ - false); - - BKE_mesh_update_customdata_pointers(mesh, true); -} - void BKE_mesh_tessface_ensure(Mesh *mesh) { if (mesh->totpoly && mesh->totface == 0) { diff --git a/source/blender/blenkernel/intern/mesh_evaluate.c b/source/blender/blenkernel/intern/mesh_evaluate.c index 2ce6e1f15f0..56f820848cb 100644 --- a/source/blender/blenkernel/intern/mesh_evaluate.c +++ b/source/blender/blenkernel/intern/mesh_evaluate.c @@ -40,7 +40,6 @@ #include "BLI_linklist_stack.h" #include "BLI_math.h" #include "BLI_memarena.h" -#include "BLI_polyfill_2d.h" #include "BLI_stack.h" #include "BLI_task.h" #include "BLI_utildefines.h" @@ -2858,108 +2857,6 @@ void BKE_mesh_loops_to_mface_corners( } } -/** - * Convert all CD layers from loop/poly to tessface data. - * - * \param loopindices: is an array of an int[4] per tessface, - * mapping tessface's verts to loops indices. - * - * \note when mface is not NULL, mface[face_index].v4 - * is used to test quads, else, loopindices[face_index][3] is used. - */ -void BKE_mesh_loops_to_tessdata(CustomData *fdata, - CustomData *ldata, - MFace *mface, - const int *polyindices, - uint (*loopindices)[4], - const int num_faces) -{ - /* Note: performances are sub-optimal when we get a NULL mface, - * we could be ~25% quicker with dedicated code... - * Issue is, unless having two different functions with nearly the same code, - * there's not much ways to solve this. Better imho to live with it for now. :/ --mont29 - */ - const int numUV = CustomData_number_of_layers(ldata, CD_MLOOPUV); - 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); - const bool hasLoopNormal = CustomData_has_layer(ldata, CD_NORMAL); - const bool hasLoopTangent = CustomData_has_layer(ldata, CD_TANGENT); - int findex, i, j; - const int *pidx; - uint(*lidx)[4]; - - for (i = 0; i < numUV; i++) { - MTFace *texface = CustomData_get_layer_n(fdata, CD_MTFACE, 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++) { - for (j = (mface ? mface[findex].v4 : (*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 = (mface ? mface[findex].v4 : (*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 = (mface ? mface[findex].v4 : (*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 = (mface ? mface[findex].v4 : (*lidx)[3]) ? 4 : 3; j--;) { - copy_v2_v2(of->uv[j], lof[(*lidx)[j]].uv); - } - } - } - - if (hasLoopNormal) { - short(*fnors)[4][3] = CustomData_get_layer(fdata, CD_TESSLOOPNORMAL); - float(*lnors)[3] = CustomData_get_layer(ldata, CD_NORMAL); - - for (findex = 0, lidx = loopindices; findex < num_faces; lidx++, findex++, fnors++) { - for (j = (mface ? mface[findex].v4 : (*lidx)[3]) ? 4 : 3; j--;) { - normal_float_to_short_v3((*fnors)[j], lnors[(*lidx)[j]]); - } - } - } - - if (hasLoopTangent) { - /* need to do for all uv maps at some point */ - float(*ftangents)[4] = CustomData_get_layer(fdata, CD_TANGENT); - float(*ltangents)[4] = CustomData_get_layer(ldata, CD_TANGENT); - - for (findex = 0, pidx = polyindices, lidx = loopindices; findex < num_faces; - pidx++, lidx++, findex++) { - int nverts = (mface ? mface[findex].v4 : (*lidx)[3]) ? 4 : 3; - for (j = nverts; j--;) { - copy_v4_v4(ftangents[findex * 4 + j], ltangents[(*lidx)[j]]); - } - } - } -} - void BKE_mesh_tangent_loops_to_tessdata(CustomData *fdata, CustomData *ldata, MFace *mface, @@ -3008,416 +2905,6 @@ void BKE_mesh_tangent_loops_to_tessdata(CustomData *fdata, } } -/** - * Recreate tessellation. - * - * \param do_face_nor_copy: Controls whether the normals from the poly - * are copied to the tessellated faces. - * - * \return number of tessellation faces. - */ -int BKE_mesh_tessface_calc_ex(CustomData *fdata, - CustomData *ldata, - CustomData *pdata, - MVert *mvert, - int totface, - int totloop, - int totpoly, - const bool do_face_nor_copy) -{ - /* use this to avoid locking pthread for _every_ polygon - * and calling the fill function */ - -#define USE_TESSFACE_SPEEDUP -#define USE_TESSFACE_QUADS /* NEEDS FURTHER TESTING */ - -/* We abuse MFace->edcode to tag quad faces. See below for details. */ -#define TESSFACE_IS_QUAD 1 - - const int looptri_num = poly_to_tri_count(totpoly, totloop); - - MPoly *mp, *mpoly; - MLoop *ml, *mloop; - MFace *mface, *mf; - MemArena *arena = NULL; - int *mface_to_poly_map; - uint(*lindices)[4]; - int poly_index, mface_index; - uint j; - - mpoly = CustomData_get_layer(pdata, CD_MPOLY); - mloop = CustomData_get_layer(ldata, CD_MLOOP); - - /* allocate the length of totfaces, avoid many small reallocs, - * if all faces are tri's it will be correct, quads == 2x allocs */ - /* take care. we are _not_ calloc'ing so be sure to initialize each field */ - mface_to_poly_map = MEM_malloc_arrayN((size_t)looptri_num, sizeof(*mface_to_poly_map), __func__); - mface = MEM_malloc_arrayN((size_t)looptri_num, sizeof(*mface), __func__); - lindices = MEM_malloc_arrayN((size_t)looptri_num, sizeof(*lindices), __func__); - - mface_index = 0; - mp = mpoly; - for (poly_index = 0; poly_index < totpoly; poly_index++, mp++) { - const uint mp_loopstart = (uint)mp->loopstart; - const uint mp_totloop = (uint)mp->totloop; - uint l1, l2, l3, l4; - uint *lidx; - if (mp_totloop < 3) { - /* do nothing */ - } - -#ifdef USE_TESSFACE_SPEEDUP - -# 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 */ \ - 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 */ \ - 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; \ - (void)0 - - else if (mp_totloop == 3) { - ML_TO_MF(0, 1, 2); - mface_index++; - } - else if (mp_totloop == 4) { -# ifdef USE_TESSFACE_QUADS - ML_TO_MF_QUAD(); - mface_index++; -# else - ML_TO_MF(0, 1, 2); - mface_index++; - ML_TO_MF(0, 2, 3); - mface_index++; -# endif - } -#endif /* USE_TESSFACE_SPEEDUP */ - else { - const float *co_curr, *co_prev; - - float normal[3]; - - float axis_mat[3][3]; - float(*projverts)[2]; - uint(*tris)[3]; - - const uint 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); - - zero_v3(normal); - - /* calc normal, flipped: to get a positive 2d cross product */ - 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; - } - if (UNLIKELY(normalize_v3(normal) == 0.0f)) { - normal[2] = 1.0f; - } - - /* project verts to 2d */ - axis_dominant_v3_to_m3_negate(axis_mat, normal); - - 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(projverts, mp_totloop, 1, tris, arena); - - /* apply fill */ - for (j = 0; j < totfilltri; j++) { - uint *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 */ - l1 = mp_loopstart + tri[0]; - l2 = mp_loopstart + tri[1]; - l3 = mp_loopstart + tri[2]; - - 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; - - mface_index++; - } - - BLI_memarena_clear(arena); - } - } - - if (arena) { - BLI_memarena_free(arena); - arena = NULL; - } - - CustomData_free(fdata, totface); - totface = mface_index; - - BLI_assert(totface <= looptri_num); - - /* not essential but without this we store over-alloc'd memory in the CustomData layers */ - if (LIKELY(looptri_num != totface)) { - mface = MEM_reallocN(mface, sizeof(*mface) * (size_t)totface); - mface_to_poly_map = MEM_reallocN(mface_to_poly_map, - sizeof(*mface_to_poly_map) * (size_t)totface); - } - - CustomData_add_layer(fdata, CD_MFACE, CD_ASSIGN, mface, totface); - - /* CD_ORIGINDEX will contain an array of indices from tessfaces to the polygons - * they are directly tessellated from */ - CustomData_add_layer(fdata, CD_ORIGINDEX, CD_ASSIGN, mface_to_poly_map, totface); - CustomData_from_bmeshpoly(fdata, ldata, totface); - - if (do_face_nor_copy) { - /* If polys have a normals layer, copying that to faces can help - * avoid the need to recalculate normals later */ - if (CustomData_has_layer(pdata, CD_NORMAL)) { - float(*pnors)[3] = CustomData_get_layer(pdata, CD_NORMAL); - float(*fnors)[3] = CustomData_add_layer(fdata, CD_NORMAL, CD_CALLOC, NULL, totface); - for (mface_index = 0; mface_index < totface; mface_index++) { - copy_v3_v3(fnors[mface_index], pnors[mface_to_poly_map[mface_index]]); - } - } - } - - /* NOTE: quad detection issue - fourth vertidx vs fourth loopidx: - * Polygons take care of their loops ordering, hence not of their vertices ordering. - * Currently, our tfaces' fourth vertex index might be 0 even for a quad. However, - * we know our fourth loop index is never 0 for quads (because they are sorted for polygons, - * and our quads are still mere copies of their polygons). - * So we pass NULL as MFace pointer, and BKE_mesh_loops_to_tessdata - * will use the fourth loop index as quad test. - * ... - */ - BKE_mesh_loops_to_tessdata(fdata, ldata, NULL, mface_to_poly_map, lindices, totface); - - /* NOTE: quad detection issue - fourth vertidx vs fourth loopidx: - * ...However, most TFace code uses 'MFace->v4 == 0' test to check whether it is a tri or quad. - * test_index_face() will check this and rotate the tessellated face if needed. - */ -#ifdef USE_TESSFACE_QUADS - mf = mface; - for (mface_index = 0; mface_index < totface; mface_index++, mf++) { - if (mf->edcode == TESSFACE_IS_QUAD) { - test_index_face(mf, fdata, mface_index, 4); - mf->edcode = 0; - } - } -#endif - - MEM_freeN(lindices); - - return totface; - -#undef USE_TESSFACE_SPEEDUP -#undef USE_TESSFACE_QUADS - -#undef ML_TO_MF -#undef ML_TO_MF_QUAD -} - -/** - * Calculate tessellation into #MLoopTri which exist only for this purpose. - */ -void BKE_mesh_recalc_looptri(const MLoop *mloop, - const MPoly *mpoly, - const MVert *mvert, - int totloop, - int totpoly, - MLoopTri *mlooptri) -{ - /* use this to avoid locking pthread for _every_ polygon - * and calling the fill function */ - -#define USE_TESSFACE_SPEEDUP - - const MPoly *mp; - const MLoop *ml; - MLoopTri *mlt; - MemArena *arena = NULL; - int poly_index, mlooptri_index; - uint j; - - mlooptri_index = 0; - mp = mpoly; - for (poly_index = 0; poly_index < totpoly; poly_index++, mp++) { - const uint mp_loopstart = (uint)mp->loopstart; - const uint mp_totloop = (uint)mp->totloop; - uint l1, l2, l3; - if (mp_totloop < 3) { - /* do nothing */ - } - -#ifdef USE_TESSFACE_SPEEDUP - -# define ML_TO_MLT(i1, i2, i3) \ - { \ - mlt = &mlooptri[mlooptri_index]; \ - l1 = mp_loopstart + i1; \ - l2 = mp_loopstart + i2; \ - l3 = mp_loopstart + i3; \ - ARRAY_SET_ITEMS(mlt->tri, l1, l2, l3); \ - mlt->poly = (uint)poly_index; \ - } \ - ((void)0) - - else if (mp_totloop == 3) { - ML_TO_MLT(0, 1, 2); - mlooptri_index++; - } - else if (mp_totloop == 4) { - ML_TO_MLT(0, 1, 2); - MLoopTri *mlt_a = mlt; - mlooptri_index++; - ML_TO_MLT(0, 2, 3); - MLoopTri *mlt_b = mlt; - mlooptri_index++; - - if (UNLIKELY(is_quad_flip_v3_first_third_fast(mvert[mloop[mlt_a->tri[0]].v].co, - mvert[mloop[mlt_a->tri[1]].v].co, - mvert[mloop[mlt_a->tri[2]].v].co, - mvert[mloop[mlt_b->tri[2]].v].co))) { - /* flip out of degenerate 0-2 state. */ - mlt_a->tri[2] = mlt_b->tri[2]; - mlt_b->tri[0] = mlt_a->tri[1]; - } - } -#endif /* USE_TESSFACE_SPEEDUP */ - else { - const float *co_curr, *co_prev; - - float normal[3]; - - float axis_mat[3][3]; - float(*projverts)[2]; - uint(*tris)[3]; - - const uint 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); - - zero_v3(normal); - - /* calc normal, flipped: to get a positive 2d cross product */ - 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; - } - if (UNLIKELY(normalize_v3(normal) == 0.0f)) { - normal[2] = 1.0f; - } - - /* project verts to 2d */ - axis_dominant_v3_to_m3_negate(axis_mat, normal); - - 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(projverts, mp_totloop, 1, tris, arena); - - /* apply fill */ - for (j = 0; j < totfilltri; j++) { - uint *tri = tris[j]; - - mlt = &mlooptri[mlooptri_index]; - - /* set loop indices, transformed to vert indices later */ - l1 = mp_loopstart + tri[0]; - l2 = mp_loopstart + tri[1]; - l3 = mp_loopstart + tri[2]; - - ARRAY_SET_ITEMS(mlt->tri, l1, l2, l3); - mlt->poly = (uint)poly_index; - - mlooptri_index++; - } - - BLI_memarena_clear(arena); - } - } - - if (arena) { - BLI_memarena_free(arena); - arena = NULL; - } - - BLI_assert(mlooptri_index == poly_to_tri_count(totpoly, totloop)); - UNUSED_VARS_NDEBUG(totloop); - -#undef USE_TESSFACE_SPEEDUP -#undef ML_TO_MLT -} - static void bm_corners_to_loops_ex(ID *id, CustomData *fdata, CustomData *ldata, diff --git a/source/blender/blenkernel/intern/mesh_tessellate.c b/source/blender/blenkernel/intern/mesh_tessellate.c new file mode 100644 index 00000000000..d0f7b7ace26 --- /dev/null +++ b/source/blender/blenkernel/intern/mesh_tessellate.c @@ -0,0 +1,584 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. + * All rights reserved. + */ + +/** \file + * \ingroup bke + * + * This file contains code for polygon tessellation + * (creating triangles from polygons). + * + * \see bmesh_mesh_tessellate.c for the #BMesh equivalent of this file. + */ + +#include <limits.h> + +#include "MEM_guardedalloc.h" + +#include "DNA_mesh_types.h" +#include "DNA_meshdata_types.h" + +#include "BLI_math.h" +#include "BLI_memarena.h" +#include "BLI_polyfill_2d.h" +#include "BLI_utildefines.h" + +#include "BKE_customdata.h" +#include "BKE_mesh.h" /* Own include. */ + +#include "BLI_strict_flags.h" + +/* -------------------------------------------------------------------- */ +/** \name MFace Tessellation + * \{ */ + +/** + * Convert all CD layers from loop/poly to tessface data. + * + * \param loopindices: is an array of an int[4] per tessface, + * mapping tessface's verts to loops indices. + * + * \note when mface is not NULL, mface[face_index].v4 + * is used to test quads, else, loopindices[face_index][3] is used. + */ +void BKE_mesh_loops_to_tessdata(CustomData *fdata, + CustomData *ldata, + MFace *mface, + const int *polyindices, + uint (*loopindices)[4], + const int num_faces) +{ + /* Note: performances are sub-optimal when we get a NULL mface, + * we could be ~25% quicker with dedicated code... + * Issue is, unless having two different functions with nearly the same code, + * there's not much ways to solve this. Better imho to live with it for now. :/ --mont29 + */ + const int numUV = CustomData_number_of_layers(ldata, CD_MLOOPUV); + 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); + const bool hasLoopNormal = CustomData_has_layer(ldata, CD_NORMAL); + const bool hasLoopTangent = CustomData_has_layer(ldata, CD_TANGENT); + int findex, i, j; + const int *pidx; + uint(*lidx)[4]; + + for (i = 0; i < numUV; i++) { + MTFace *texface = CustomData_get_layer_n(fdata, CD_MTFACE, 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++) { + for (j = (mface ? mface[findex].v4 : (*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 = (mface ? mface[findex].v4 : (*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 = (mface ? mface[findex].v4 : (*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 = (mface ? mface[findex].v4 : (*lidx)[3]) ? 4 : 3; j--;) { + copy_v2_v2(of->uv[j], lof[(*lidx)[j]].uv); + } + } + } + + if (hasLoopNormal) { + short(*fnors)[4][3] = CustomData_get_layer(fdata, CD_TESSLOOPNORMAL); + float(*lnors)[3] = CustomData_get_layer(ldata, CD_NORMAL); + + for (findex = 0, lidx = loopindices; findex < num_faces; lidx++, findex++, fnors++) { + for (j = (mface ? mface[findex].v4 : (*lidx)[3]) ? 4 : 3; j--;) { + normal_float_to_short_v3((*fnors)[j], lnors[(*lidx)[j]]); + } + } + } + + if (hasLoopTangent) { + /* need to do for all uv maps at some point */ + float(*ftangents)[4] = CustomData_get_layer(fdata, CD_TANGENT); + float(*ltangents)[4] = CustomData_get_layer(ldata, CD_TANGENT); + + for (findex = 0, pidx = polyindices, lidx = loopindices; findex < num_faces; + pidx++, lidx++, findex++) { + int nverts = (mface ? mface[findex].v4 : (*lidx)[3]) ? 4 : 3; + for (j = nverts; j--;) { + copy_v4_v4(ftangents[findex * 4 + j], ltangents[(*lidx)[j]]); + } + } + } +} + +/** + * Recreate tessellation. + * + * \param do_face_nor_copy: Controls whether the normals from the poly + * are copied to the tessellated faces. + * + * \return number of tessellation faces. + */ +int BKE_mesh_tessface_calc_ex(CustomData *fdata, + CustomData *ldata, + CustomData *pdata, + MVert *mvert, + int totface, + int totloop, + int totpoly, + const bool do_face_nor_copy) +{ + /* use this to avoid locking pthread for _every_ polygon + * and calling the fill function */ + +#define USE_TESSFACE_SPEEDUP +#define USE_TESSFACE_QUADS /* NEEDS FURTHER TESTING */ + +/* We abuse MFace->edcode to tag quad faces. See below for details. */ +#define TESSFACE_IS_QUAD 1 + + const int looptri_num = poly_to_tri_count(totpoly, totloop); + + MPoly *mp, *mpoly; + MLoop *ml, *mloop; + MFace *mface, *mf; + MemArena *arena = NULL; + int *mface_to_poly_map; + uint(*lindices)[4]; + int poly_index, mface_index; + uint j; + + mpoly = CustomData_get_layer(pdata, CD_MPOLY); + mloop = CustomData_get_layer(ldata, CD_MLOOP); + + /* allocate the length of totfaces, avoid many small reallocs, + * if all faces are tri's it will be correct, quads == 2x allocs */ + /* take care. we are _not_ calloc'ing so be sure to initialize each field */ + mface_to_poly_map = MEM_malloc_arrayN((size_t)looptri_num, sizeof(*mface_to_poly_map), __func__); + mface = MEM_malloc_arrayN((size_t)looptri_num, sizeof(*mface), __func__); + lindices = MEM_malloc_arrayN((size_t)looptri_num, sizeof(*lindices), __func__); + + mface_index = 0; + mp = mpoly; + for (poly_index = 0; poly_index < totpoly; poly_index++, mp++) { + const uint mp_loopstart = (uint)mp->loopstart; + const uint mp_totloop = (uint)mp->totloop; + uint l1, l2, l3, l4; + uint *lidx; + if (mp_totloop < 3) { + /* do nothing */ + } + +#ifdef USE_TESSFACE_SPEEDUP + +# 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 */ \ + 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 */ \ + 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; \ + (void)0 + + else if (mp_totloop == 3) { + ML_TO_MF(0, 1, 2); + mface_index++; + } + else if (mp_totloop == 4) { +# ifdef USE_TESSFACE_QUADS + ML_TO_MF_QUAD(); + mface_index++; +# else + ML_TO_MF(0, 1, 2); + mface_index++; + ML_TO_MF(0, 2, 3); + mface_index++; +# endif + } +#endif /* USE_TESSFACE_SPEEDUP */ + else { + const float *co_curr, *co_prev; + + float normal[3]; + + float axis_mat[3][3]; + float(*projverts)[2]; + uint(*tris)[3]; + + const uint 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); + + zero_v3(normal); + + /* calc normal, flipped: to get a positive 2d cross product */ + 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; + } + if (UNLIKELY(normalize_v3(normal) == 0.0f)) { + normal[2] = 1.0f; + } + + /* project verts to 2d */ + axis_dominant_v3_to_m3_negate(axis_mat, normal); + + 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(projverts, mp_totloop, 1, tris, arena); + + /* apply fill */ + for (j = 0; j < totfilltri; j++) { + uint *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 */ + l1 = mp_loopstart + tri[0]; + l2 = mp_loopstart + tri[1]; + l3 = mp_loopstart + tri[2]; + + 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; + + mface_index++; + } + + BLI_memarena_clear(arena); + } + } + + if (arena) { + BLI_memarena_free(arena); + arena = NULL; + } + + CustomData_free(fdata, totface); + totface = mface_index; + + BLI_assert(totface <= looptri_num); + + /* not essential but without this we store over-alloc'd memory in the CustomData layers */ + if (LIKELY(looptri_num != totface)) { + mface = MEM_reallocN(mface, sizeof(*mface) * (size_t)totface); + mface_to_poly_map = MEM_reallocN(mface_to_poly_map, + sizeof(*mface_to_poly_map) * (size_t)totface); + } + + CustomData_add_layer(fdata, CD_MFACE, CD_ASSIGN, mface, totface); + + /* CD_ORIGINDEX will contain an array of indices from tessfaces to the polygons + * they are directly tessellated from */ + CustomData_add_layer(fdata, CD_ORIGINDEX, CD_ASSIGN, mface_to_poly_map, totface); + CustomData_from_bmeshpoly(fdata, ldata, totface); + + if (do_face_nor_copy) { + /* If polys have a normals layer, copying that to faces can help + * avoid the need to recalculate normals later */ + if (CustomData_has_layer(pdata, CD_NORMAL)) { + float(*pnors)[3] = CustomData_get_layer(pdata, CD_NORMAL); + float(*fnors)[3] = CustomData_add_layer(fdata, CD_NORMAL, CD_CALLOC, NULL, totface); + for (mface_index = 0; mface_index < totface; mface_index++) { + copy_v3_v3(fnors[mface_index], pnors[mface_to_poly_map[mface_index]]); + } + } + } + + /* NOTE: quad detection issue - fourth vertidx vs fourth loopidx: + * Polygons take care of their loops ordering, hence not of their vertices ordering. + * Currently, our tfaces' fourth vertex index might be 0 even for a quad. However, + * we know our fourth loop index is never 0 for quads (because they are sorted for polygons, + * and our quads are still mere copies of their polygons). + * So we pass NULL as MFace pointer, and BKE_mesh_loops_to_tessdata + * will use the fourth loop index as quad test. + * ... + */ + BKE_mesh_loops_to_tessdata(fdata, ldata, NULL, mface_to_poly_map, lindices, totface); + + /* NOTE: quad detection issue - fourth vertidx vs fourth loopidx: + * ...However, most TFace code uses 'MFace->v4 == 0' test to check whether it is a tri or quad. + * test_index_face() will check this and rotate the tessellated face if needed. + */ +#ifdef USE_TESSFACE_QUADS + mf = mface; + for (mface_index = 0; mface_index < totface; mface_index++, mf++) { + if (mf->edcode == TESSFACE_IS_QUAD) { + test_index_face(mf, fdata, mface_index, 4); + mf->edcode = 0; + } + } +#endif + + MEM_freeN(lindices); + + return totface; + +#undef USE_TESSFACE_SPEEDUP +#undef USE_TESSFACE_QUADS + +#undef ML_TO_MF +#undef ML_TO_MF_QUAD +} + +void BKE_mesh_tessface_calc(Mesh *mesh) +{ + mesh->totface = BKE_mesh_tessface_calc_ex( + &mesh->fdata, + &mesh->ldata, + &mesh->pdata, + mesh->mvert, + mesh->totface, + mesh->totloop, + mesh->totpoly, + /* calc normals right after, don't copy from polys here */ + false); + + BKE_mesh_update_customdata_pointers(mesh, true); +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Loop Tessellation + * \{ */ + +/** + * Calculate tessellation into #MLoopTri which exist only for this purpose. + */ +void BKE_mesh_recalc_looptri(const MLoop *mloop, + const MPoly *mpoly, + const MVert *mvert, + int totloop, + int totpoly, + MLoopTri *mlooptri) +{ + /* use this to avoid locking pthread for _every_ polygon + * and calling the fill function */ + +#define USE_TESSFACE_SPEEDUP + + const MPoly *mp; + const MLoop *ml; + MLoopTri *mlt; + MemArena *arena = NULL; + int poly_index, mlooptri_index; + uint j; + + mlooptri_index = 0; + mp = mpoly; + for (poly_index = 0; poly_index < totpoly; poly_index++, mp++) { + const uint mp_loopstart = (uint)mp->loopstart; + const uint mp_totloop = (uint)mp->totloop; + uint l1, l2, l3; + if (mp_totloop < 3) { + /* do nothing */ + } + +#ifdef USE_TESSFACE_SPEEDUP + +# define ML_TO_MLT(i1, i2, i3) \ + { \ + mlt = &mlooptri[mlooptri_index]; \ + l1 = mp_loopstart + i1; \ + l2 = mp_loopstart + i2; \ + l3 = mp_loopstart + i3; \ + ARRAY_SET_ITEMS(mlt->tri, l1, l2, l3); \ + mlt->poly = (uint)poly_index; \ + } \ + ((void)0) + + else if (mp_totloop == 3) { + ML_TO_MLT(0, 1, 2); + mlooptri_index++; + } + else if (mp_totloop == 4) { + ML_TO_MLT(0, 1, 2); + MLoopTri *mlt_a = mlt; + mlooptri_index++; + ML_TO_MLT(0, 2, 3); + MLoopTri *mlt_b = mlt; + mlooptri_index++; + + if (UNLIKELY(is_quad_flip_v3_first_third_fast(mvert[mloop[mlt_a->tri[0]].v].co, + mvert[mloop[mlt_a->tri[1]].v].co, + mvert[mloop[mlt_a->tri[2]].v].co, + mvert[mloop[mlt_b->tri[2]].v].co))) { + /* flip out of degenerate 0-2 state. */ + mlt_a->tri[2] = mlt_b->tri[2]; + mlt_b->tri[0] = mlt_a->tri[1]; + } + } +#endif /* USE_TESSFACE_SPEEDUP */ + else { + const float *co_curr, *co_prev; + + float normal[3]; + + float axis_mat[3][3]; + float(*projverts)[2]; + uint(*tris)[3]; + + const uint 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); + + zero_v3(normal); + + /* calc normal, flipped: to get a positive 2d cross product */ + 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; + } + if (UNLIKELY(normalize_v3(normal) == 0.0f)) { + normal[2] = 1.0f; + } + + /* project verts to 2d */ + axis_dominant_v3_to_m3_negate(axis_mat, normal); + + 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(projverts, mp_totloop, 1, tris, arena); + + /* apply fill */ + for (j = 0; j < totfilltri; j++) { + uint *tri = tris[j]; + + mlt = &mlooptri[mlooptri_index]; + + /* set loop indices, transformed to vert indices later */ + l1 = mp_loopstart + tri[0]; + l2 = mp_loopstart + tri[1]; + l3 = mp_loopstart + tri[2]; + + ARRAY_SET_ITEMS(mlt->tri, l1, l2, l3); + mlt->poly = (uint)poly_index; + + mlooptri_index++; + } + + BLI_memarena_clear(arena); + } + } + + if (arena) { + BLI_memarena_free(arena); + arena = NULL; + } + + BLI_assert(mlooptri_index == poly_to_tri_count(totpoly, totloop)); + UNUSED_VARS_NDEBUG(totloop); + +#undef USE_TESSFACE_SPEEDUP +#undef ML_TO_MLT +} + +/** \} */ diff --git a/source/blender/bmesh/intern/bmesh_mesh_tessellate.c b/source/blender/bmesh/intern/bmesh_mesh_tessellate.c index 508a86d5807..7ae0c3923fa 100644 --- a/source/blender/bmesh/intern/bmesh_mesh_tessellate.c +++ b/source/blender/bmesh/intern/bmesh_mesh_tessellate.c @@ -19,6 +19,8 @@ * * This file contains code for polygon tessellation * (creating triangles from polygons). + * + * \see mesh_tessellate.c for the #Mesh equivalent of this file. */ #include "DNA_meshdata_types.h" |