From 2646bbdccbea62d451391d3512b5a50457a95974 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Mon, 9 Sep 2013 02:11:44 +0000 Subject: move mesh evaluation functions (normal, mapping, smooth group... etc, calculations) into mesh_evaluate.c. mesh.c was over 4k lines and complex functions mixed in with general library management. --- source/blender/blenkernel/BKE_mesh.h | 326 ++- source/blender/blenkernel/CMakeLists.txt | 1 + source/blender/blenkernel/intern/mesh.c | 2402 +------------------- source/blender/blenkernel/intern/mesh_evaluate.c | 2017 ++++++++++++++++ source/blender/blenkernel/intern/mesh_validate.c | 341 ++- source/blender/blenkernel/intern/multires.c | 5 + .../blender/blenloader/intern/versioning_legacy.c | 2 +- 7 files changed, 2623 insertions(+), 2471 deletions(-) create mode 100644 source/blender/blenkernel/intern/mesh_evaluate.c (limited to 'source') diff --git a/source/blender/blenkernel/BKE_mesh.h b/source/blender/blenkernel/BKE_mesh.h index 3d443cbe38c..43e425b5ce1 100644 --- a/source/blender/blenkernel/BKE_mesh.h +++ b/source/blender/blenkernel/BKE_mesh.h @@ -31,8 +31,6 @@ * \ingroup bke */ -/***/ - struct ID; struct BoundBox; struct DispList; @@ -60,108 +58,25 @@ struct UvVertMap; struct UvMapVert; struct UvElementMap; struct UvElement; + #ifdef __cplusplus extern "C" { #endif -struct BMesh *BKE_mesh_to_bmesh(struct Mesh *me, struct Object *ob); - -/* - * this function recreates a tessellation. - * returns number of tessellation faces. - * - * use_poly_origindex sets whether or not the tessellation faces' origindex - * layer should point to original poly indices or real poly indices. - * - * use_face_origindex sets the tessellation faces' origindex layer - * to point to the tessellation faces themselves, not the polys. - * - * if both of the above are 0, it'll use the indices of the mpolys of the MPoly - * data in pdata, and ignore the origindex layer altogether. - */ -int BKE_mesh_recalc_tessellation(struct CustomData *fdata, struct CustomData *ldata, struct CustomData *pdata, - struct MVert *mvert, - int totface, int totloop, int totpoly, - const bool do_face_normals); - -/* for forwards compat only quad->tri polys to mface, skip ngons. - */ -int BKE_mesh_mpoly_to_mface(struct CustomData *fdata, struct CustomData *ldata, - struct CustomData *pdata, int totface, int totloop, int totpoly); - -/*calculates a face normal.*/ -void BKE_mesh_calc_poly_normal(struct MPoly *mpoly, struct MLoop *loopstart, - struct MVert *mvarray, float no[3]); - -void BKE_mesh_calc_poly_normal_coords(struct MPoly *mpoly, struct MLoop *loopstart, - const float (*vertex_coords)[3], float no[3]); - -void BKE_mesh_calc_poly_center(struct MPoly *mpoly, struct MLoop *loopstart, - struct MVert *mvarray, float cent[3]); - -float BKE_mesh_calc_poly_area(struct MPoly *mpoly, struct MLoop *loopstart, - struct MVert *mvarray, const float polynormal[3]); - -void BKE_mesh_calc_poly_angles(struct MPoly *mpoly, struct MLoop *loopstart, - struct MVert *mvarray, float angles[]); -int *BKE_mesh_calc_smoothgroups(const struct MEdge *medge, const int totedge, - const struct MPoly *mpoly, const int totpoly, - const struct MLoop *mloop, const int totloop, - int *r_totgroup, const bool use_bitflags); +/* *** mesh.c *** */ -void BKE_mesh_calc_relative_deform( - const struct MPoly *mpoly, const int totpoly, - const struct MLoop *mloop, const int totvert, - - const float (*vert_cos_src)[3], - const float (*vert_cos_dst)[3], - - const float (*vert_cos_org)[3], - float (*vert_cos_new)[3]); +struct BMesh *BKE_mesh_to_bmesh(struct Mesh *me, struct Object *ob); -/* Find the index of the loop in 'poly' which references vertex, - * returns -1 if not found */ int poly_find_loop_from_vert(const struct MPoly *poly, const struct MLoop *loopstart, unsigned vert); -/* Fill 'adj_r' with the loop indices in 'poly' adjacent to the - * vertex. Returns the index of the loop matching vertex, or -1 if the - * vertex is not in 'poly' */ int poly_get_adj_loops_from_vert(unsigned adj_r[3], const struct MPoly *poly, const struct MLoop *mloop, unsigned vert); -/* Return the index of the edge vert that is not equal to 'v'. If - * neither edge vertex is equal to 'v', returns -1. */ int BKE_mesh_edge_other_vert(const struct MEdge *e, int v); -/* update the hide flag for edges and polys from the corresponding - * flag in verts */ -void BKE_mesh_flush_hidden_from_verts_ex(const struct MVert *mvert, - const struct MLoop *mloop, - struct MEdge *medge, const int totedge, - struct MPoly *mpoly, const int totpoly); -void BKE_mesh_flush_hidden_from_verts(struct Mesh *me); - -void BKE_mesh_flush_hidden_from_polys_ex(struct MVert *mvert, - const struct MLoop *mloop, - struct MEdge *medge, const int totedge, - const struct MPoly *mpoly, const int totpoly); -void BKE_mesh_flush_hidden_from_polys(struct Mesh *me); - - -void BKE_mesh_flush_select_from_polys_ex(struct MVert *mvert, const int totvert, - const struct MLoop *mloop, - struct MEdge *medge, const int totedge, - const struct MPoly *mpoly, const int totpoly); -void BKE_mesh_flush_select_from_polys(struct Mesh *me); -void BKE_mesh_flush_select_from_verts_ex(const struct MVert *mvert, const int totvert, - const struct MLoop *mloop, - struct MEdge *medge, const int totedge, - struct MPoly *mpoly, const int totpoly); -void BKE_mesh_flush_select_from_verts(struct Mesh *me); - void BKE_mesh_unlink(struct Mesh *me); void BKE_mesh_free(struct Mesh *me, int unlink); struct Mesh *BKE_mesh_add(struct Main *bmain, const char *name); @@ -191,64 +106,92 @@ void BKE_mesh_to_curve(struct Scene *scene, struct Object *ob); void BKE_mesh_material_index_remove(struct Mesh *me, short index); void BKE_mesh_material_index_clear(struct Mesh *me); void BKE_mesh_smooth_flag_set(struct Object *meshOb, int enableSmooth); -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, - struct CustomData *fdata, struct CustomData *ldata, struct CustomData *pdata, - int totedge_i, int totface_i, int totloop_i, int totpoly_i, - struct MEdge *medge, struct MFace *mface, - int *totloop_r, int *totpoly_r, - struct MLoop **mloop_r, struct MPoly **mpoly_r); - -void BKE_mesh_calc_normals_tessface(struct MVert *mverts, int numVerts, struct MFace *mfaces, int numFaces, float (*faceNors_r)[3]); - -/* used for unit testing; compares two meshes, checking only - * differences we care about. should be usable with leaf's - * testing framework I get RNA work done, will use hackish - * testing code for now.*/ + const char *BKE_mesh_cmp(struct Mesh *me1, struct Mesh *me2, float thresh); struct BoundBox *BKE_mesh_boundbox_get(struct Object *ob); void BKE_mesh_texspace_get(struct Mesh *me, float r_loc[3], float r_rot[3], float r_size[3]); void BKE_mesh_texspace_copy_from_object(struct Mesh *me, struct Object *ob); -/* if old, it converts mface->edcode to edge drawflags */ -void BKE_mesh_make_edges(struct Mesh *me, const bool use_old); +float (*BKE_mesh_vertexCos_get(struct Mesh *me, int *r_numVerts))[3]; -void BKE_mesh_strip_loose_faces(struct Mesh *me); /* Needed for compatibility (some old read code). */ -void BKE_mesh_strip_loose_polysloops(struct Mesh *me); -void BKE_mesh_strip_loose_edges(struct Mesh *me); +/* vertex level transformations & checks (no derived mesh) */ + +bool BKE_mesh_minmax(struct Mesh *me, float r_min[3], float r_max[3]); +void BKE_mesh_translate(struct Mesh *me, const float offset[3], const bool do_keys); + +void BKE_mesh_ensure_navmesh(struct Mesh *me); + +void BKE_mesh_tessface_calc(struct Mesh *mesh); +void BKE_mesh_tessface_ensure(struct Mesh *mesh); +void BKE_mesh_tessface_clear(struct Mesh *mesh); + +void BKE_mesh_do_versions_cd_flag_init(struct Mesh *mesh); + + +void BKE_mesh_mselect_clear(struct Mesh *me); +void BKE_mesh_mselect_validate(struct Mesh *me); +int BKE_mesh_mselect_find(struct Mesh *me, int index, int type); +int BKE_mesh_mselect_active_get(struct Mesh *me, int type); +void BKE_mesh_mselect_active_set(struct Mesh *me, int index, int type); + + + +/* *** mesh_evaluate.c *** */ -/* Calculate vertex and face normals, face normals are returned in *faceNors_r if non-NULL - * and vertex normals are stored in actual mverts. - */ void BKE_mesh_calc_normals_mapping( struct MVert *mverts, int numVerts, struct MLoop *mloop, struct MPoly *mpolys, int numLoops, int numPolys, float (*polyNors_r)[3], struct MFace *mfaces, int numFaces, int *origIndexFace, float (*faceNors_r)[3]); -/* extended version of 'BKE_mesh_calc_normals_poly' with option not to calc vertex normals */ void BKE_mesh_calc_normals_mapping_ex( struct MVert *mverts, int numVerts, struct MLoop *mloop, struct MPoly *mpolys, int numLoops, int numPolys, float (*polyNors_r)[3], struct MFace *mfaces, int numFaces, int *origIndexFace, float (*faceNors_r)[3], const bool only_face_normals); - void BKE_mesh_calc_normals_poly( struct MVert *mverts, int numVerts, struct MLoop *mloop, struct MPoly *mpolys, int numLoops, int numPolys, float (*polyNors_r)[3], const bool only_face_normals); - void BKE_mesh_calc_normals(struct Mesh *me); +void BKE_mesh_calc_normals_tessface( + struct MVert *mverts, int numVerts, + struct MFace *mfaces, int numFaces, + float (*faceNors_r)[3]); + + +void BKE_mesh_calc_poly_normal( + struct MPoly *mpoly, struct MLoop *loopstart, + struct MVert *mvarray, float no[3]); +void BKE_mesh_calc_poly_normal_coords( + struct MPoly *mpoly, struct MLoop *loopstart, + const float (*vertex_coords)[3], float no[3]); +void BKE_mesh_calc_poly_center( + struct MPoly *mpoly, struct MLoop *loopstart, + struct MVert *mvarray, float cent[3]); +float BKE_mesh_calc_poly_area( + struct MPoly *mpoly, struct MLoop *loopstart, + struct MVert *mvarray, const float polynormal[3]); +void BKE_mesh_calc_poly_angles( + struct MPoly *mpoly, struct MLoop *loopstart, + struct MVert *mvarray, float angles[]); + +void BKE_mesh_poly_edgehash_insert( + struct EdgeHash *ehash, + const struct MPoly *mp, const struct MLoop *mloop); +void BKE_mesh_poly_edgebitmap_insert( + unsigned int *edge_bitmap, + const struct MPoly *mp, const struct MLoop *mloop); + + +bool BKE_mesh_center_median(struct Mesh *me, float cent[3]); +bool BKE_mesh_center_bounds(struct Mesh *me, float cent[3]); +bool BKE_mesh_center_centroid(struct Mesh *me, float cent[3]); -/* Return a newly MEM_malloc'd array of all the mesh vertex locations - * (_numVerts_r_ may be NULL) */ -float (*BKE_mesh_vertexCos_get(struct Mesh *me, int *r_numVerts))[3]; /* map from uv vertex to face (for select linked, stitch, uv suburf) */ /* UvVertMap */ - #define STD_UV_CONNECT_LIMIT 0.0001f typedef struct UvVertMap { @@ -302,45 +245,107 @@ typedef struct UvElementMap { * to make that many islands, he can bite me :p */ #define INVALID_ISLAND 0xFFFF -UvVertMap *BKE_mesh_uv_vert_map_create(struct MPoly *mpoly, struct MLoop *mloop, struct MLoopUV *mloopuv, - unsigned int totpoly, unsigned int totvert, int selected, float *limit); -UvMapVert *BKE_mesh_uv_vert_map_get_vert(UvVertMap *vmap, unsigned int v); -void BKE_mesh_uv_vert_map_free(UvVertMap *vmap); - /* Connectivity data */ typedef struct MeshElemMap { int *indices; int count; } MeshElemMap; - -typedef struct IndexNode { - struct IndexNode *next, *prev; - int index; -} IndexNode; -void BKE_mesh_vert_poly_map_create(MeshElemMap **r_map, int **r_mem, - const struct MPoly *mface, const struct MLoop *mloop, - int totvert, int totface, int totloop); +/* mapping */ +UvVertMap *BKE_mesh_uv_vert_map_create( + struct MPoly *mpoly, struct MLoop *mloop, struct MLoopUV *mloopuv, + unsigned int totpoly, unsigned int totvert, int selected, float *limit); +UvMapVert *BKE_mesh_uv_vert_map_get_vert(UvVertMap *vmap, unsigned int v); +void BKE_mesh_uv_vert_map_free(UvVertMap *vmap); -void BKE_mesh_vert_edge_map_create(MeshElemMap **r_map, int **r_mem, - const struct MEdge *medge, int totvert, int totedge); +void BKE_mesh_vert_poly_map_create( + MeshElemMap **r_map, int **r_mem, + const struct MPoly *mface, const struct MLoop *mloop, + int totvert, int totface, int totloop); +void BKE_mesh_vert_edge_map_create( + MeshElemMap **r_map, int **r_mem, + const struct MEdge *medge, int totvert, int totedge); +void BKE_mesh_edge_poly_map_create( + MeshElemMap **r_map, int **r_mem, + const struct MEdge *medge, const int totedge, + const struct MPoly *mpoly, const int totpoly, + const struct MLoop *mloop, const int totloop); + +/* tessface */ +void BKE_mesh_loops_to_mface_corners( + struct CustomData *fdata, struct CustomData *ldata, + struct CustomData *pdata, int lindex[4], int findex, + const int polyindex, const int mf_len, + const int numTex, const int numCol, + const bool hasPCol, const bool hasOrigSpace); +int BKE_mesh_recalc_tessellation( + struct CustomData *fdata, struct CustomData *ldata, struct CustomData *pdata, + struct MVert *mvert, + int totface, int totloop, int totpoly, + const bool do_face_normals); +int BKE_mesh_mpoly_to_mface( + struct CustomData *fdata, struct CustomData *ldata, + struct CustomData *pdata, int totface, int totloop, int totpoly); +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, + struct CustomData *fdata, struct CustomData *ldata, struct CustomData *pdata, + int totedge_i, int totface_i, int totloop_i, int totpoly_i, + struct MEdge *medge, struct MFace *mface, + int *totloop_r, int *totpoly_r, + struct MLoop **mloop_r, struct MPoly **mpoly_r); + +/* flush flags */ +void BKE_mesh_flush_hidden_from_verts_ex( + const struct MVert *mvert, + const struct MLoop *mloop, + struct MEdge *medge, const int totedge, + struct MPoly *mpoly, const int totpoly); +void BKE_mesh_flush_hidden_from_verts(struct Mesh *me); +void BKE_mesh_flush_hidden_from_polys_ex( + struct MVert *mvert, + const struct MLoop *mloop, + struct MEdge *medge, const int totedge, + const struct MPoly *mpoly, const int totpoly); +void BKE_mesh_flush_hidden_from_polys(struct Mesh *me); +void BKE_mesh_flush_select_from_polys_ex( + struct MVert *mvert, const int totvert, + const struct MLoop *mloop, + struct MEdge *medge, const int totedge, + const struct MPoly *mpoly, const int totpoly); +void BKE_mesh_flush_select_from_polys(struct Mesh *me); +void BKE_mesh_flush_select_from_verts_ex( + const struct MVert *mvert, const int totvert, + const struct MLoop *mloop, + struct MEdge *medge, const int totedge, + struct MPoly *mpoly, const int totpoly); +void BKE_mesh_flush_select_from_verts(struct Mesh *me); -void BKE_mesh_edge_poly_map_create(MeshElemMap **r_map, int **r_mem, - const struct MEdge *medge, const int totedge, - const struct MPoly *mpoly, const int totpoly, - const struct MLoop *mloop, const int totloop); +/* smoothgroups */ +int *BKE_mesh_calc_smoothgroups( + const struct MEdge *medge, const int totedge, + const struct MPoly *mpoly, const int totpoly, + const struct MLoop *mloop, const int totloop, + int *r_totgroup, const bool use_bitflags); + +/* spatial evaluation */ +void BKE_mesh_calc_relative_deform( + const struct MPoly *mpoly, const int totpoly, + const struct MLoop *mloop, const int totvert, + + const float (*vert_cos_src)[3], + const float (*vert_cos_dst)[3], + + const float (*vert_cos_org)[3], + float (*vert_cos_new)[3]); -/* vertex level transformations & checks (no derived mesh) */ -bool BKE_mesh_minmax(struct Mesh *me, float r_min[3], float r_max[3]); -bool BKE_mesh_center_median(struct Mesh *me, float cent[3]); -bool BKE_mesh_center_bounds(struct Mesh *me, float cent[3]); -bool BKE_mesh_center_centroid(struct Mesh *me, float cent[3]); -void BKE_mesh_translate(struct Mesh *me, const float offset[3], const bool do_keys); -/* mesh_validate.c */ -/* XXX Loop v/e are unsigned, so using max uint_32 value as invalid marker... */ -#define INVALID_LOOP_EDGE_MARKER 4294967295u +/* *** mesh_validate.c *** */ + +int BKE_mesh_validate(struct Mesh *me, const int do_verbose); + bool BKE_mesh_validate_arrays( struct Mesh *me, struct MVert *mverts, unsigned int totvert, @@ -359,34 +364,13 @@ bool BKE_mesh_validate_all_customdata( const bool do_verbose, const bool do_fixes, bool *r_change); -int BKE_mesh_validate(struct Mesh *me, const int do_verbose); +void BKE_mesh_strip_loose_faces(struct Mesh *me); +void BKE_mesh_strip_loose_polysloops(struct Mesh *me); +void BKE_mesh_strip_loose_edges(struct Mesh *me); +void BKE_mesh_calc_edges_legacy(struct Mesh *me, const bool use_old); void BKE_mesh_calc_edges(struct Mesh *mesh, bool update, const bool select); -void BKE_mesh_ensure_navmesh(struct Mesh *me); - -void BKE_mesh_tessface_calc(struct Mesh *mesh); -void BKE_mesh_tessface_ensure(struct Mesh *mesh); -void BKE_mesh_tessface_clear(struct Mesh *mesh); - -/* Convert a triangle or quadrangle of loop/poly data to tessface data */ -void BKE_mesh_loops_to_mface_corners(struct CustomData *fdata, struct CustomData *ldata, - struct CustomData *pdata, int lindex[4], int findex, - const int polyindex, const int mf_len, - const int numTex, const int numCol, const int hasPCol, const int hasOrigSpace); - -void BKE_mesh_poly_edgehash_insert(struct EdgeHash *ehash, const struct MPoly *mp, const struct MLoop *mloop); -void BKE_mesh_poly_edgebitmap_insert(unsigned int *edge_bitmap, const struct MPoly *mp, const struct MLoop *mloop); - -void BKE_mesh_do_versions_cd_flag_init(struct Mesh *mesh); - - -void BKE_mesh_mselect_clear(struct Mesh *me); -void BKE_mesh_mselect_validate(struct Mesh *me); -int BKE_mesh_mselect_find(struct Mesh *me, int index, int type); -int BKE_mesh_mselect_active_get(struct Mesh *me, int type); -void BKE_mesh_mselect_active_set(struct Mesh *me, int index, int type); - #ifdef __cplusplus } #endif diff --git a/source/blender/blenkernel/CMakeLists.txt b/source/blender/blenkernel/CMakeLists.txt index e9142ef1abd..0ac3737b6a2 100644 --- a/source/blender/blenkernel/CMakeLists.txt +++ b/source/blender/blenkernel/CMakeLists.txt @@ -115,6 +115,7 @@ set(SRC intern/material.c intern/mball.c intern/mesh.c + intern/mesh_evaluate.c intern/mesh_validate.c intern/modifier.c intern/modifiers_bmesh.c diff --git a/source/blender/blenkernel/intern/mesh.c b/source/blender/blenkernel/intern/mesh.c index 459f7216d00..63a7b8cd982 100644 --- a/source/blender/blenkernel/intern/mesh.c +++ b/source/blender/blenkernel/intern/mesh.c @@ -27,12 +27,6 @@ * \ingroup bke */ - -#include -#include -#include -#include - #include "MEM_guardedalloc.h" #include "DNA_scene_types.h" @@ -40,23 +34,15 @@ #include "DNA_object_types.h" #include "DNA_key_types.h" #include "DNA_mesh_types.h" -#include "DNA_meshdata_types.h" #include "DNA_ipo_types.h" -#include "DNA_customdata_types.h" #include "BLI_utildefines.h" -#include "BLI_blenlib.h" -#include "BLI_memarena.h" #include "BLI_math.h" +#include "BLI_listbase.h" #include "BLI_edgehash.h" -#include "BLI_bitmap.h" -#include "BLI_scanfill.h" -#include "BLI_array.h" -#include "BLI_alloca.h" #include "BKE_animsys.h" #include "BKE_main.h" -#include "BKE_customdata.h" #include "BKE_DerivedMesh.h" #include "BKE_global.h" #include "BKE_mesh.h" @@ -71,9 +57,7 @@ /* -- */ #include "BKE_object.h" #include "BKE_editmesh.h" -#include "BLI_edgehash.h" -#include "bmesh.h" enum { MESHCMP_DVERT_WEIGHTMISMATCH = 1, @@ -275,7 +259,12 @@ static int customdata_compare(CustomData *c1, CustomData *c2, Mesh *m1, Mesh *m2 return 0; } -/*used for testing. returns an error string the two meshes don't match*/ +/** + * Used for unit testing; compares two meshes, checking only + * differences we care about. should be usable with leaf's + * testing framework I get RNA work done, will use hackish + * testing code for now. + */ const char *BKE_mesh_cmp(Mesh *me1, Mesh *me2, float thresh) { int c; @@ -866,309 +855,6 @@ void BKE_mesh_assign_object(Object *ob, Mesh *me) test_object_modifiers(ob); } -/* ************** make edges in a Mesh, for outside of editmode */ - -struct EdgeSort { - unsigned int v1, v2; - char is_loose, is_draw; -}; - -/* edges have to be added with lowest index first for sorting */ -static void to_edgesort(struct EdgeSort *ed, - unsigned int v1, unsigned int v2, - char is_loose, short is_draw) -{ - if (v1 < v2) { - ed->v1 = v1; ed->v2 = v2; - } - else { - ed->v1 = v2; ed->v2 = v1; - } - ed->is_loose = is_loose; - ed->is_draw = is_draw; -} - -static int vergedgesort(const void *v1, const void *v2) -{ - const struct EdgeSort *x1 = v1, *x2 = v2; - - if (x1->v1 > x2->v1) return 1; - else if (x1->v1 < x2->v1) return -1; - else if (x1->v2 > x2->v2) return 1; - else if (x1->v2 < x2->v2) return -1; - - return 0; -} - - -/* Create edges based on known verts and faces, - * this function is only used when loading very old blend files */ - -static void make_edges_mdata(MVert *UNUSED(allvert), MFace *allface, MLoop *allloop, - MPoly *allpoly, int UNUSED(totvert), int totface, int UNUSED(totloop), int totpoly, - const bool use_old, - MEdge **r_medge, int *r_totedge) -{ - MPoly *mpoly; - MFace *mface; - MEdge *medge, *med; - EdgeHash *hash; - struct EdgeSort *edsort, *ed; - int a, totedge = 0; - unsigned int totedge_final = 0; - unsigned int edge_index; - - /* we put all edges in array, sort them, and detect doubles that way */ - - for (a = totface, mface = allface; a > 0; a--, mface++) { - if (mface->v4) totedge += 4; - else if (mface->v3) totedge += 3; - else totedge += 1; - } - - if (totedge == 0) { - /* flag that mesh has edges */ - (*r_medge) = MEM_callocN(0, __func__); - (*r_totedge) = 0; - return; - } - - ed = edsort = MEM_mallocN(totedge * sizeof(struct EdgeSort), "EdgeSort"); - - for (a = totface, mface = allface; a > 0; a--, mface++) { - to_edgesort(ed++, mface->v1, mface->v2, !mface->v3, mface->edcode & ME_V1V2); - if (mface->v4) { - to_edgesort(ed++, mface->v2, mface->v3, 0, mface->edcode & ME_V2V3); - to_edgesort(ed++, mface->v3, mface->v4, 0, mface->edcode & ME_V3V4); - to_edgesort(ed++, mface->v4, mface->v1, 0, mface->edcode & ME_V4V1); - } - else if (mface->v3) { - to_edgesort(ed++, mface->v2, mface->v3, 0, mface->edcode & ME_V2V3); - to_edgesort(ed++, mface->v3, mface->v1, 0, mface->edcode & ME_V3V1); - } - } - - qsort(edsort, totedge, sizeof(struct EdgeSort), vergedgesort); - - /* count final amount */ - for (a = totedge, ed = edsort; a > 1; a--, ed++) { - /* edge is unique when it differs from next edge, or is last */ - if (ed->v1 != (ed + 1)->v1 || ed->v2 != (ed + 1)->v2) totedge_final++; - } - totedge_final++; - - medge = MEM_callocN(sizeof(MEdge) * totedge_final, __func__); - - for (a = totedge, med = medge, ed = edsort; a > 1; a--, ed++) { - /* edge is unique when it differs from next edge, or is last */ - if (ed->v1 != (ed + 1)->v1 || ed->v2 != (ed + 1)->v2) { - med->v1 = ed->v1; - med->v2 = ed->v2; - if (use_old == false || ed->is_draw) med->flag = ME_EDGEDRAW | ME_EDGERENDER; - if (ed->is_loose) med->flag |= ME_LOOSEEDGE; - - /* order is swapped so extruding this edge as a surface wont flip face normals - * with cyclic curves */ - if (ed->v1 + 1 != ed->v2) { - SWAP(unsigned int, med->v1, med->v2); - } - med++; - } - else { - /* equal edge, we merge the drawflag */ - (ed + 1)->is_draw |= ed->is_draw; - } - } - /* last edge */ - med->v1 = ed->v1; - med->v2 = ed->v2; - med->flag = ME_EDGEDRAW; - if (ed->is_loose) med->flag |= ME_LOOSEEDGE; - med->flag |= ME_EDGERENDER; - - MEM_freeN(edsort); - - /* set edge members of mloops */ - hash = BLI_edgehash_new_ex(__func__, totedge_final); - for (edge_index = 0, med = medge; edge_index < totedge_final; edge_index++, med++) { - BLI_edgehash_insert(hash, med->v1, med->v2, SET_UINT_IN_POINTER(edge_index)); - } - - mpoly = allpoly; - for (a = 0; a < totpoly; a++, mpoly++) { - MLoop *ml, *ml_next; - int i = mpoly->totloop; - - ml_next = allloop + mpoly->loopstart; /* first loop */ - ml = &ml_next[i - 1]; /* last loop */ - - while (i-- != 0) { - ml->e = GET_UINT_FROM_POINTER(BLI_edgehash_lookup(hash, ml->v, ml_next->v)); - ml = ml_next; - ml_next++; - } - } - - BLI_edgehash_free(hash, NULL); - - *r_medge = medge; - *r_totedge = totedge_final; -} - -void BKE_mesh_make_edges(Mesh *me, const bool use_old) -{ - MEdge *medge; - int totedge = 0; - - make_edges_mdata(me->mvert, me->mface, me->mloop, me->mpoly, - me->totvert, me->totface, me->totloop, me->totpoly, - use_old, &medge, &totedge); - - if (totedge == 0) { - /* flag that mesh has edges */ - me->medge = medge; - me->totedge = 0; - return; - } - - medge = CustomData_add_layer(&me->edata, CD_MEDGE, CD_ASSIGN, medge, totedge); - me->medge = medge; - me->totedge = totedge; - - BKE_mesh_strip_loose_faces(me); -} - -/* We need to keep this for edge creation (for now?), and some old readfile code... */ -void BKE_mesh_strip_loose_faces(Mesh *me) -{ - MFace *f; - int a, b; - - for (a = b = 0, f = me->mface; a < me->totface; a++, f++) { - if (f->v3) { - if (a != b) { - memcpy(&me->mface[b], f, sizeof(me->mface[b])); - CustomData_copy_data(&me->fdata, &me->fdata, a, b, 1); - } - b++; - } - } - if (a != b) { - CustomData_free_elem(&me->fdata, b, a - b); - me->totface = b; - } -} - -/* Works on both loops and polys! */ -/* Note: It won't try to guess which loops of an invalid poly to remove! - * this is the work of the caller, to mark those loops... - * See e.g. BKE_mesh_validate_arrays(). */ -void BKE_mesh_strip_loose_polysloops(Mesh *me) -{ - MPoly *p; - MLoop *l; - int a, b; - /* New loops idx! */ - int *new_idx = MEM_mallocN(sizeof(int) * me->totloop, __func__); - - for (a = b = 0, p = me->mpoly; a < me->totpoly; a++, p++) { - int invalid = FALSE; - int i = p->loopstart; - int stop = i + p->totloop; - - if (stop > me->totloop || stop < i) { - invalid = TRUE; - } - else { - l = &me->mloop[i]; - i = stop - i; - /* If one of the poly's loops is invalid, the whole poly is invalid! */ - for (; i--; l++) { - if (l->e == INVALID_LOOP_EDGE_MARKER) { - invalid = TRUE; - break; - } - } - } - - if (p->totloop >= 3 && !invalid) { - if (a != b) { - memcpy(&me->mpoly[b], p, sizeof(me->mpoly[b])); - CustomData_copy_data(&me->pdata, &me->pdata, a, b, 1); - } - b++; - } - } - if (a != b) { - CustomData_free_elem(&me->pdata, b, a - b); - me->totpoly = b; - } - - /* And now, get rid of invalid loops. */ - for (a = b = 0, l = me->mloop; a < me->totloop; a++, l++) { - if (l->e != INVALID_LOOP_EDGE_MARKER) { - if (a != b) { - memcpy(&me->mloop[b], l, sizeof(me->mloop[b])); - CustomData_copy_data(&me->ldata, &me->ldata, a, b, 1); - } - new_idx[a] = b; - b++; - } - else { - /* XXX Theoretically, we should be able to not do this, as no remaining poly - * should use any stripped loop. But for security's sake... */ - new_idx[a] = -a; - } - } - if (a != b) { - CustomData_free_elem(&me->ldata, b, a - b); - me->totloop = b; - } - - /* And now, update polys' start loop index. */ - /* Note: At this point, there should never be any poly using a striped loop! */ - for (a = 0, p = me->mpoly; a < me->totpoly; a++, p++) { - p->loopstart = new_idx[p->loopstart]; - } - - MEM_freeN(new_idx); -} - -void BKE_mesh_strip_loose_edges(Mesh *me) -{ - MEdge *e; - MLoop *l; - int a, b; - unsigned int *new_idx = MEM_mallocN(sizeof(int) * me->totedge, __func__); - - for (a = b = 0, e = me->medge; a < me->totedge; a++, e++) { - if (e->v1 != e->v2) { - if (a != b) { - memcpy(&me->medge[b], e, sizeof(me->medge[b])); - CustomData_copy_data(&me->edata, &me->edata, a, b, 1); - } - new_idx[a] = b; - b++; - } - else { - new_idx[a] = INVALID_LOOP_EDGE_MARKER; - } - } - if (a != b) { - CustomData_free_elem(&me->edata, b, a - b); - me->totedge = b; - } - - /* And now, update loops' edge indices. */ - /* XXX We hope no loop was pointing to a striped edge! - * Else, its e will be set to INVALID_LOOP_EDGE_MARKER :/ */ - for (a = 0, l = me->mloop; a < me->totloop; a++, l++) { - l->e = new_idx[l->e]; - } - - MEM_freeN(new_idx); -} - void BKE_mesh_from_metaball(ListBase *lb, Mesh *me) { DispList *dl; @@ -1933,2023 +1619,143 @@ void BKE_mesh_smooth_flag_set(Object *meshOb, int enableSmooth) } /** - * Call when there are no polygons. + * Return a newly MEM_malloc'd array of all the mesh vertex locations + * \note \a numVerts_r may be NULL */ -static void mesh_calc_normals_vert_fallback(MVert *mverts, int numVerts) +float (*BKE_mesh_vertexCos_get(Mesh *me, int *r_numVerts))[3] { - int i; - for (i = 0; i < numVerts; i++) { - MVert *mv = &mverts[i]; - float no[3]; + int i, numVerts = me->totvert; + float (*cos)[3] = MEM_mallocN(sizeof(*cos) * numVerts, "vertexcos1"); - normalize_v3_v3(no, mv->co); - normal_float_to_short_v3(mv->no, no); - } -} + if (r_numVerts) *r_numVerts = numVerts; + for (i = 0; i < numVerts; i++) + copy_v3_v3(cos[i], me->mvert[i].co); -void BKE_mesh_calc_normals_mapping(MVert *mverts, int numVerts, - MLoop *mloop, MPoly *mpolys, int numLoops, int numPolys, float (*polyNors_r)[3], - MFace *mfaces, int numFaces, int *origIndexFace, float (*faceNors_r)[3]) -{ - BKE_mesh_calc_normals_mapping_ex(mverts, numVerts, mloop, mpolys, - numLoops, numPolys, polyNors_r, mfaces, numFaces, - origIndexFace, faceNors_r, FALSE); + return cos; } -void BKE_mesh_calc_normals_mapping_ex(MVert *mverts, int numVerts, - MLoop *mloop, MPoly *mpolys, - int numLoops, int numPolys, float (*polyNors_r)[3], - MFace *mfaces, int numFaces, int *origIndexFace, float (*faceNors_r)[3], - const bool only_face_normals) +/** + * Find the index of the loop in 'poly' which references vertex, + * returns -1 if not found + */ +int poly_find_loop_from_vert(const MPoly *poly, const MLoop *loopstart, + unsigned vert) { - float (*pnors)[3] = polyNors_r, (*fnors)[3] = faceNors_r; - int i; - MFace *mf; - MPoly *mp; - - if (numPolys == 0) { - if (only_face_normals == FALSE) { - mesh_calc_normals_vert_fallback(mverts, numVerts); - } - return; - } - - /* if we are not calculating verts and no verts were passes then we have nothing to do */ - if ((only_face_normals == TRUE) && (polyNors_r == NULL) && (faceNors_r == NULL)) { - printf("%s: called with nothing to do\n", __func__); - return; - } - - if (!pnors) pnors = MEM_callocN(sizeof(float) * 3 * numPolys, "poly_nors mesh.c"); - /* if (!fnors) fnors = MEM_callocN(sizeof(float) * 3 * numFaces, "face nors mesh.c"); */ /* NO NEED TO ALLOC YET */ - - - if (only_face_normals == FALSE) { - /* vertex normals are optional, they require some extra calculations, - * so make them optional */ - BKE_mesh_calc_normals_poly(mverts, numVerts, mloop, mpolys, numLoops, numPolys, pnors, false); - } - else { - /* only calc poly normals */ - mp = mpolys; - for (i = 0; i < numPolys; i++, mp++) { - BKE_mesh_calc_poly_normal(mp, mloop + mp->loopstart, mverts, pnors[i]); - } - } - - if (origIndexFace && - /* fnors == faceNors_r */ /* NO NEED TO ALLOC YET */ - fnors != NULL && - numFaces) - { - mf = mfaces; - for (i = 0; i < numFaces; i++, mf++, origIndexFace++) { - if (*origIndexFace < numPolys) { - copy_v3_v3(fnors[i], pnors[*origIndexFace]); - } - else { - /* eek, we're not corresponding to polys */ - printf("error in %s: tessellation face indices are incorrect. normals may look bad.\n", __func__); - } - } + int j; + for (j = 0; j < poly->totloop; j++, loopstart++) { + if (loopstart->v == vert) + return j; } - - if (pnors != polyNors_r) MEM_freeN(pnors); - /* if (fnors != faceNors_r) MEM_freeN(fnors); */ /* NO NEED TO ALLOC YET */ - - fnors = pnors = NULL; + return -1; } -static void mesh_calc_normals_poly_accum(MPoly *mp, MLoop *ml, - MVert *mvert, float polyno[3], float (*tnorms)[3]) +/** + * Fill \a adj_r with the loop indices in \a poly adjacent to the + * vertex. Returns the index of the loop matching vertex, or -1 if the + * vertex is not in \a poly + */ +int poly_get_adj_loops_from_vert(unsigned adj_r[3], const MPoly *poly, + const MLoop *mloop, unsigned vert) { - const int nverts = mp->totloop; - float (*edgevecbuf)[3] = BLI_array_alloca(edgevecbuf, nverts); - int i; - - /* Polygon Normal and edge-vector */ - /* inline version of #BKE_mesh_calc_poly_normal, also does edge-vectors */ - { - int i_prev = nverts - 1; - float const *v_prev = mvert[ml[i_prev].v].co; - float const *v_curr; - - zero_v3(polyno); - /* Newell's Method */ - for (i = 0; i < nverts; i++) { - v_curr = mvert[ml[i].v].co; - add_newell_cross_v3_v3v3(polyno, v_prev, v_curr); - - /* Unrelated to normalize, calcualte edge-vector */ - sub_v3_v3v3(edgevecbuf[i_prev], v_prev, v_curr); - normalize_v3(edgevecbuf[i_prev]); - i_prev = i; - - v_prev = v_curr; - } - if (UNLIKELY(normalize_v3(polyno) == 0.0f)) { - polyno[2] = 1.0f; /* other axis set to 0.0 */ - } - } - - /* accumulate angle weighted face normal */ - /* inline version of #accumulate_vertex_normals_poly */ - { - const float *prev_edge = edgevecbuf[nverts - 1]; - - for (i = 0; i < nverts; i++) { - const float *cur_edge = edgevecbuf[i]; - - /* calculate angle between the two poly edges incident on - * this vertex */ - const float fac = saacos(-dot_v3v3(cur_edge, prev_edge)); + int corner = poly_find_loop_from_vert(poly, + &mloop[poly->loopstart], + vert); + + if (corner != -1) { + const MLoop *ml = &mloop[poly->loopstart + corner]; - /* accumulate */ - madd_v3_v3fl(tnorms[ml[i].v], polyno, fac); - prev_edge = cur_edge; - } + /* vertex was found */ + adj_r[0] = ME_POLY_LOOP_PREV(mloop, poly, corner)->v; + adj_r[1] = ml->v; + adj_r[2] = ME_POLY_LOOP_NEXT(mloop, poly, corner)->v; } + return corner; } -void BKE_mesh_calc_normals_poly(MVert *mverts, int numVerts, MLoop *mloop, MPoly *mpolys, - int UNUSED(numLoops), int numPolys, float (*r_polynors)[3], - const bool only_face_normals) +/** + * Return the index of the edge vert that is not equal to \a v. If + * neither edge vertex is equal to \a v, returns -1. + */ +int BKE_mesh_edge_other_vert(const MEdge *e, int v) { - float (*pnors)[3] = r_polynors; - float (*tnorms)[3]; - int i; - MPoly *mp; - - if (only_face_normals) { - BLI_assert(pnors != NULL); + if (e->v1 == v) + return e->v2; + else if (e->v2 == v) + return e->v1; + else + return -1; +} -#pragma omp parallel for if (numPolys > BM_OMP_LIMIT) - for (i = 0; i < numPolys; i++) { - BKE_mesh_calc_poly_normal(&mpolys[i], mloop + mpolys[i].loopstart, mverts, pnors[i]); - } - return; +/* basic vertex data functions */ +bool BKE_mesh_minmax(Mesh *me, float r_min[3], float r_max[3]) +{ + int i = me->totvert; + MVert *mvert; + for (mvert = me->mvert; i--; mvert++) { + minmax_v3v3_v3(r_min, r_max, mvert->co); } + + return (me->totvert != 0); +} - /* first go through and calculate normals for all the polys */ - tnorms = MEM_callocN(sizeof(*tnorms) * numVerts, __func__); - - if (pnors) { - mp = mpolys; - for (i = 0; i < numPolys; i++, mp++) { - mesh_calc_normals_poly_accum(mp, mloop + mp->loopstart, mverts, pnors[i], tnorms); - } +void BKE_mesh_translate(Mesh *me, const float offset[3], const bool do_keys) +{ + int i = me->totvert; + MVert *mvert; + for (mvert = me->mvert; i--; mvert++) { + add_v3_v3(mvert->co, offset); } - else { - float tpnor[3]; /* temp poly normal */ - mp = mpolys; - for (i = 0; i < numPolys; i++, mp++) { - mesh_calc_normals_poly_accum(mp, mloop + mp->loopstart, mverts, tpnor, tnorms); + + if (do_keys && me->key) { + KeyBlock *kb; + for (kb = me->key->block.first; kb; kb = kb->next) { + float *fp = kb->data; + for (i = kb->totelem; i--; fp += 3) { + add_v3_v3(fp, offset); + } } } +} - /* following Mesh convention; we use vertex coordinate itself for normal in this case */ - for (i = 0; i < numVerts; i++) { - MVert *mv = &mverts[i]; - float *no = tnorms[i]; - - if (UNLIKELY(normalize_v3(no) == 0.0f)) { - normalize_v3_v3(no, mv->co); +void BKE_mesh_ensure_navmesh(Mesh *me) +{ + if (!CustomData_has_layer(&me->pdata, CD_RECAST)) { + int i; + int numFaces = me->totpoly; + int *recastData; + recastData = (int *)MEM_mallocN(numFaces * sizeof(int), __func__); + for (i = 0; i < numFaces; i++) { + recastData[i] = i + 1; } - - normal_float_to_short_v3(mv->no, no); + CustomData_add_layer_named(&me->pdata, CD_RECAST, CD_ASSIGN, recastData, numFaces, "recastData"); } - - MEM_freeN(tnorms); } -void BKE_mesh_calc_normals(Mesh *mesh) +void BKE_mesh_tessface_calc(Mesh *mesh) { - BKE_mesh_calc_normals_poly(mesh->mvert, mesh->totvert, - mesh->mloop, mesh->mpoly, mesh->totloop, mesh->totpoly, - NULL, false); + mesh->totface = BKE_mesh_recalc_tessellation(&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_calc_normals_tessface(MVert *mverts, int numVerts, MFace *mfaces, int numFaces, float (*faceNors_r)[3]) +void BKE_mesh_tessface_ensure(Mesh *mesh) { - float (*tnorms)[3] = MEM_callocN(numVerts * sizeof(*tnorms), "tnorms"); - float (*fnors)[3] = (faceNors_r) ? faceNors_r : MEM_callocN(sizeof(*fnors) * numFaces, "meshnormals"); - int i; - - for (i = 0; i < numFaces; i++) { - MFace *mf = &mfaces[i]; - float *f_no = fnors[i]; - float *n4 = (mf->v4) ? tnorms[mf->v4] : NULL; - float *c4 = (mf->v4) ? mverts[mf->v4].co : NULL; - - if (mf->v4) - normal_quad_v3(f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co, mverts[mf->v4].co); - else - normal_tri_v3(f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co); - - accumulate_vertex_normals(tnorms[mf->v1], tnorms[mf->v2], tnorms[mf->v3], n4, - f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co, c4); - } - - /* following Mesh convention; we use vertex coordinate itself for normal in this case */ - for (i = 0; i < numVerts; i++) { - MVert *mv = &mverts[i]; - float *no = tnorms[i]; - - if (UNLIKELY(normalize_v3(no) == 0.0f)) { - normalize_v3_v3(no, mv->co); - } - - normal_float_to_short_v3(mv->no, no); + if (mesh->totpoly && mesh->totface == 0) { + BKE_mesh_tessface_calc(mesh); } - - MEM_freeN(tnorms); - - if (fnors != faceNors_r) - MEM_freeN(fnors); } -static void bm_corners_to_loops_ex(ID *id, CustomData *fdata, CustomData *ldata, CustomData *pdata, - MFace *mface, int totloop, int findex, int loopstart, int numTex, int numCol) -{ - MTFace *texface; - MTexPoly *texpoly; - MCol *mcol; - MLoopCol *mloopcol; - MLoopUV *mloopuv; - MFace *mf; - int i; - - mf = mface + findex; - - for (i = 0; i < numTex; i++) { - texface = CustomData_get_n(fdata, CD_MTFACE, findex, i); - texpoly = CustomData_get_n(pdata, CD_MTEXPOLY, findex, i); - - ME_MTEXFACE_CPY(texpoly, texface); - - mloopuv = CustomData_get_n(ldata, CD_MLOOPUV, loopstart, i); - copy_v2_v2(mloopuv->uv, texface->uv[0]); mloopuv++; - copy_v2_v2(mloopuv->uv, texface->uv[1]); mloopuv++; - copy_v2_v2(mloopuv->uv, texface->uv[2]); mloopuv++; - - if (mf->v4) { - copy_v2_v2(mloopuv->uv, texface->uv[3]); mloopuv++; - } - } - - for (i = 0; i < numCol; i++) { - mloopcol = CustomData_get_n(ldata, CD_MLOOPCOL, loopstart, i); - mcol = CustomData_get_n(fdata, CD_MCOL, findex, i); - - MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[0]); mloopcol++; - MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[1]); mloopcol++; - MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[2]); mloopcol++; - if (mf->v4) { - MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[3]); mloopcol++; - } - } - - if (CustomData_has_layer(fdata, CD_MDISPS)) { - MDisps *ld = CustomData_get(ldata, loopstart, CD_MDISPS); - MDisps *fd = CustomData_get(fdata, findex, CD_MDISPS); - float (*disps)[3] = fd->disps; - int tot = mf->v4 ? 4 : 3; - int side, corners; - - if (CustomData_external_test(fdata, CD_MDISPS)) { - if (id && fdata->external) { - CustomData_external_add(ldata, id, CD_MDISPS, - totloop, fdata->external->filename); - } - } - - corners = multires_mdisp_corners(fd); - - if (corners == 0) { - /* Empty MDisp layers appear in at least one of the sintel.blend files. - * Not sure why this happens, but it seems fine to just ignore them here. - * If (corners == 0) for a non-empty layer though, something went wrong. */ - BLI_assert(fd->totdisp == 0); - } - else { - side = sqrt(fd->totdisp / corners); - - for (i = 0; i < tot; i++, disps += side * side, ld++) { - ld->totdisp = side * side; - ld->level = (int)(logf(side - 1.0f) / (float)M_LN2) + 1; - - if (ld->disps) - MEM_freeN(ld->disps); - - ld->disps = MEM_mallocN(sizeof(float) * 3 * side * side, "converted loop mdisps"); - if (fd->disps) { - memcpy(ld->disps, disps, sizeof(float) * 3 * side * side); - } - else { - memset(ld->disps, 0, sizeof(float) * 3 * side * side); - } - } - } - } -} - -void BKE_mesh_convert_mfaces_to_mpolys(Mesh *mesh) -{ - BKE_mesh_convert_mfaces_to_mpolys_ex(&mesh->id, &mesh->fdata, &mesh->ldata, &mesh->pdata, - mesh->totedge, mesh->totface, mesh->totloop, mesh->totpoly, - mesh->medge, mesh->mface, - &mesh->totloop, &mesh->totpoly, &mesh->mloop, &mesh->mpoly); - - BKE_mesh_update_customdata_pointers(mesh, true); -} - -/* the same as BKE_mesh_convert_mfaces_to_mpolys but oriented to be used in do_versions from readfile.c - * the difference is how active/render/clone/stencil indices are handled here - * - * normally thay're being set from pdata which totally makes sense for meshes which are already - * converted to bmesh structures, but when loading older files indices shall be updated in other - * way around, so newly added pdata and ldata would have this indices set based on fdata layer - * - * this is normally only needed when reading older files, in all other cases BKE_mesh_convert_mfaces_to_mpolys - * shall be always used - */ -void BKE_mesh_do_versions_convert_mfaces_to_mpolys(Mesh *mesh) -{ - BKE_mesh_convert_mfaces_to_mpolys_ex(&mesh->id, &mesh->fdata, &mesh->ldata, &mesh->pdata, - mesh->totedge, mesh->totface, mesh->totloop, mesh->totpoly, - mesh->medge, mesh->mface, - &mesh->totloop, &mesh->totpoly, &mesh->mloop, &mesh->mpoly); - - CustomData_bmesh_do_versions_update_active_layers(&mesh->fdata, &mesh->pdata, &mesh->ldata); - - BKE_mesh_update_customdata_pointers(mesh, true); -} - -void BKE_mesh_convert_mfaces_to_mpolys_ex(ID *id, CustomData *fdata, CustomData *ldata, CustomData *pdata, - int totedge_i, int totface_i, int totloop_i, int totpoly_i, - MEdge *medge, MFace *mface, - int *totloop_r, int *totpoly_r, - MLoop **mloop_r, MPoly **mpoly_r) -{ - MFace *mf; - MLoop *ml, *mloop; - MPoly *mp, *mpoly; - MEdge *me; - EdgeHash *eh; - int numTex, numCol; - int i, j, totloop, totpoly, *polyindex; - - /* just in case some of these layers are filled in (can happen with python created meshes) */ - CustomData_free(ldata, totloop_i); - CustomData_free(pdata, totpoly_i); - - totpoly = totface_i; - mpoly = MEM_callocN(sizeof(MPoly) * totpoly, "mpoly converted"); - CustomData_add_layer(pdata, CD_MPOLY, CD_ASSIGN, mpoly, totpoly); - - numTex = CustomData_number_of_layers(fdata, CD_MTFACE); - numCol = CustomData_number_of_layers(fdata, CD_MCOL); - - totloop = 0; - mf = mface; - for (i = 0; i < totface_i; i++, mf++) { - totloop += mf->v4 ? 4 : 3; - } - - mloop = MEM_callocN(sizeof(MLoop) * totloop, "mloop converted"); - - CustomData_add_layer(ldata, CD_MLOOP, CD_ASSIGN, mloop, totloop); - - CustomData_to_bmeshpoly(fdata, pdata, ldata, totloop, totpoly); - - if (id) { - /* ensure external data is transferred */ - CustomData_external_read(fdata, id, CD_MASK_MDISPS, totface_i); - } - - eh = BLI_edgehash_new_ex(__func__, totedge_i); - - /* build edge hash */ - me = medge; - for (i = 0; i < totedge_i; i++, me++) { - BLI_edgehash_insert(eh, me->v1, me->v2, SET_INT_IN_POINTER(i)); - - /* unrelated but avoid having the FGON flag enabled, so we can reuse it later for something else */ - me->flag &= ~ME_FGON; - } - - polyindex = CustomData_get_layer(fdata, CD_ORIGINDEX); - - j = 0; /* current loop index */ - ml = mloop; - mf = mface; - mp = mpoly; - for (i = 0; i < totface_i; i++, mf++, mp++) { - mp->loopstart = j; - - mp->totloop = mf->v4 ? 4 : 3; - - mp->mat_nr = mf->mat_nr; - mp->flag = mf->flag; - -# define ML(v1, v2) { \ - ml->v = mf->v1; ml->e = GET_INT_FROM_POINTER(BLI_edgehash_lookup(eh, mf->v1, mf->v2)); ml++; j++; \ - } (void)0 - - ML(v1, v2); - ML(v2, v3); - if (mf->v4) { - ML(v3, v4); - ML(v4, v1); - } - else { - ML(v3, v1); - } - -# undef ML - - bm_corners_to_loops_ex(id, fdata, ldata, pdata, mface, totloop, i, mp->loopstart, numTex, numCol); - - if (polyindex) { - *polyindex = i; - polyindex++; - } - } - - /* note, we don't convert NGons at all, these are not even real ngons, - * they have their own UV's, colors etc - its more an editing feature. */ - - BLI_edgehash_free(eh, NULL); - - *totpoly_r = totpoly; - *totloop_r = totloop; - *mpoly_r = mpoly; - *mloop_r = mloop; -} - -float (*BKE_mesh_vertexCos_get(Mesh *me, int *r_numVerts))[3] -{ - int i, numVerts = me->totvert; - float (*cos)[3] = MEM_mallocN(sizeof(*cos) * numVerts, "vertexcos1"); - - if (r_numVerts) *r_numVerts = numVerts; - for (i = 0; i < numVerts; i++) - copy_v3_v3(cos[i], me->mvert[i].co); - - return cos; -} - - -/* ngon version wip, based on EDBM_uv_vert_map_create */ -/* this replaces the non bmesh function (in trunk) which takes MTFace's, if we ever need it back we could - * but for now this replaces it because its unused. */ - -UvVertMap *BKE_mesh_uv_vert_map_create(struct MPoly *mpoly, struct MLoop *mloop, struct MLoopUV *mloopuv, - unsigned int totpoly, unsigned int totvert, int selected, float *limit) -{ - UvVertMap *vmap; - UvMapVert *buf; - MPoly *mp; - unsigned int a; - int i, totuv, nverts; - - totuv = 0; - - /* generate UvMapVert array */ - mp = mpoly; - for (a = 0; a < totpoly; a++, mp++) - if (!selected || (!(mp->flag & ME_HIDE) && (mp->flag & ME_FACE_SEL))) - totuv += mp->totloop; - - if (totuv == 0) - return NULL; - - vmap = (UvVertMap *)MEM_callocN(sizeof(*vmap), "UvVertMap"); - if (!vmap) - return NULL; - - vmap->vert = (UvMapVert **)MEM_callocN(sizeof(*vmap->vert) * totvert, "UvMapVert*"); - buf = vmap->buf = (UvMapVert *)MEM_callocN(sizeof(*vmap->buf) * totuv, "UvMapVert"); - - if (!vmap->vert || !vmap->buf) { - BKE_mesh_uv_vert_map_free(vmap); - return NULL; - } - - mp = mpoly; - for (a = 0; a < totpoly; a++, mp++) { - if (!selected || (!(mp->flag & ME_HIDE) && (mp->flag & ME_FACE_SEL))) { - nverts = mp->totloop; - - for (i = 0; i < nverts; i++) { - buf->tfindex = i; - buf->f = a; - buf->separate = 0; - buf->next = vmap->vert[mloop[mp->loopstart + i].v]; - vmap->vert[mloop[mp->loopstart + i].v] = buf; - buf++; - } - } - } - - /* sort individual uvs for each vert */ - for (a = 0; a < totvert; a++) { - UvMapVert *newvlist = NULL, *vlist = vmap->vert[a]; - UvMapVert *iterv, *v, *lastv, *next; - float *uv, *uv2, uvdiff[2]; - - while (vlist) { - v = vlist; - vlist = vlist->next; - v->next = newvlist; - newvlist = v; - - uv = mloopuv[mpoly[v->f].loopstart + v->tfindex].uv; - lastv = NULL; - iterv = vlist; - - while (iterv) { - next = iterv->next; - - uv2 = mloopuv[mpoly[iterv->f].loopstart + iterv->tfindex].uv; - sub_v2_v2v2(uvdiff, uv2, uv); - - - if (fabsf(uv[0] - uv2[0]) < limit[0] && fabsf(uv[1] - uv2[1]) < limit[1]) { - if (lastv) lastv->next = next; - else vlist = next; - iterv->next = newvlist; - newvlist = iterv; - } - else - lastv = iterv; - - iterv = next; - } - - newvlist->separate = 1; - } - - vmap->vert[a] = newvlist; - } - - return vmap; -} - -UvMapVert *BKE_mesh_uv_vert_map_get_vert(UvVertMap *vmap, unsigned int v) -{ - return vmap->vert[v]; -} - -void BKE_mesh_uv_vert_map_free(UvVertMap *vmap) -{ - if (vmap) { - if (vmap->vert) MEM_freeN(vmap->vert); - if (vmap->buf) MEM_freeN(vmap->buf); - MEM_freeN(vmap); - } -} - -/* Generates a map where the key is the vertex and the value is a list - * of polys that use that vertex as a corner. The lists are allocated - * from one memory pool. */ -void BKE_mesh_vert_poly_map_create(MeshElemMap **r_map, int **r_mem, - const MPoly *mpoly, const MLoop *mloop, - int totvert, int totpoly, int totloop) -{ - MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * totvert, "vert poly map"); - int *indices, *index_iter; - int i, j; - - indices = index_iter = MEM_mallocN(sizeof(int) * totloop, "vert poly map mem"); - - /* Count number of polys for each vertex */ - for (i = 0; i < totpoly; i++) { - const MPoly *p = &mpoly[i]; - - for (j = 0; j < p->totloop; j++) - map[mloop[p->loopstart + j].v].count++; - } - - /* Assign indices mem */ - for (i = 0; i < totvert; i++) { - map[i].indices = index_iter; - index_iter += map[i].count; - - /* Reset 'count' for use as index in last loop */ - map[i].count = 0; - } - - /* Find the users */ - for (i = 0; i < totpoly; i++) { - const MPoly *p = &mpoly[i]; - - for (j = 0; j < p->totloop; j++) { - int v = mloop[p->loopstart + j].v; - - map[v].indices[map[v].count] = i; - map[v].count++; - } - } - - *r_map = map; - *r_mem = indices; -} - -/* Generates a map where the key is the vertex and the value is a list - * of edges that use that vertex as an endpoint. The lists are allocated - * from one memory pool. */ -void BKE_mesh_vert_edge_map_create(MeshElemMap **r_map, int **r_mem, - const MEdge *medge, int totvert, int totedge) -{ - MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * totvert, "vert-edge map"); - int *indices = MEM_mallocN(sizeof(int) * totedge * 2, "vert-edge map mem"); - int *i_pt = indices; - - int i; - - /* Count number of edges for each vertex */ - for (i = 0; i < totedge; i++) { - map[medge[i].v1].count++; - map[medge[i].v2].count++; - } - - /* Assign indices mem */ - for (i = 0; i < totvert; i++) { - map[i].indices = i_pt; - i_pt += map[i].count; - - /* Reset 'count' for use as index in last loop */ - map[i].count = 0; - } - - /* Find the users */ - for (i = 0; i < totedge; i++) { - const int v[2] = {medge[i].v1, medge[i].v2}; - - map[v[0]].indices[map[v[0]].count] = i; - map[v[1]].indices[map[v[1]].count] = i; - - map[v[0]].count++; - map[v[1]].count++; - } - - *r_map = map; - *r_mem = indices; -} - -void BKE_mesh_edge_poly_map_create(MeshElemMap **r_map, int **r_mem, - const MEdge *UNUSED(medge), const int totedge, - const MPoly *mpoly, const int totpoly, - const MLoop *mloop, const int totloop) -{ - MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * totedge, "edge-poly map"); - int *indices = MEM_mallocN(sizeof(int) * totloop, "edge-poly map mem"); - int *index_step; - const MPoly *mp; - int i; - - /* count face users */ - for (i = 0, mp = mpoly; i < totpoly; mp++, i++) { - const MLoop *ml; - int j = mp->totloop; - for (ml = &mloop[mp->loopstart]; j--; ml++) { - map[ml->e].count++; - } - } - - /* create offsets */ - index_step = indices; - for (i = 0; i < totedge; i++) { - map[i].indices = index_step; - index_step += map[i].count; - - /* re-count, using this as an index below */ - map[i].count = 0; - - } - - /* assign poly-edge users */ - for (i = 0, mp = mpoly; i < totpoly; mp++, i++) { - const MLoop *ml; - int j = mp->totloop; - for (ml = &mloop[mp->loopstart]; j--; ml++) { - MeshElemMap *map_ele = &map[ml->e]; - map_ele->indices[map_ele->count++] = i; - } - } - - *r_map = map; - *r_mem = indices; -} - -void BKE_mesh_loops_to_mface_corners(CustomData *fdata, CustomData *ldata, - CustomData *pdata, int lindex[4], int findex, - const int polyindex, - const int mf_len, /* 3 or 4 */ - - /* cache values to avoid lookups every time */ - 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) */ - ) -{ - MTFace *texface; - MTexPoly *texpoly; - MCol *mcol; - MLoopCol *mloopcol; - MLoopUV *mloopuv; - int i, j; - - for (i = 0; i < numTex; i++) { - texface = CustomData_get_n(fdata, CD_MTFACE, findex, i); - texpoly = CustomData_get_n(pdata, CD_MTEXPOLY, polyindex, i); - - ME_MTEXFACE_CPY(texface, texpoly); - - for (j = 0; j < mf_len; j++) { - mloopuv = CustomData_get_n(ldata, CD_MLOOPUV, lindex[j], i); - copy_v2_v2(texface->uv[j], mloopuv->uv); - } - } - - for (i = 0; i < numCol; i++) { - mcol = CustomData_get_n(fdata, CD_MCOL, findex, i); - - for (j = 0; j < mf_len; j++) { - mloopcol = CustomData_get_n(ldata, CD_MLOOPCOL, lindex[j], i); - MESH_MLOOPCOL_TO_MCOL(mloopcol, &mcol[j]); - } - } - - if (hasPCol) { - mcol = CustomData_get(fdata, findex, CD_PREVIEW_MCOL); - - for (j = 0; j < mf_len; j++) { - mloopcol = CustomData_get(ldata, lindex[j], CD_PREVIEW_MLOOPCOL); - MESH_MLOOPCOL_TO_MCOL(mloopcol, &mcol[j]); - } - } - - if (hasOrigSpace) { - OrigSpaceFace *of = CustomData_get(fdata, findex, CD_ORIGSPACE); - OrigSpaceLoop *lof; - - for (j = 0; j < mf_len; j++) { - lof = CustomData_get(ldata, lindex[j], CD_ORIGSPACE_MLOOP); - copy_v2_v2(of->uv[j], lof->uv); - } - } -} - -/* - * this function recreates a tessellation. - * returns number of tessellation faces. - */ -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) -{ - /* 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 - -#define TESSFACE_SCANFILL (1 << 0) -#define TESSFACE_IS_QUAD (1 << 1) - - const int looptris_tot = poly_to_tri_count(totpoly, totloop); - - 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; - 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 int hasPCol = CustomData_has_layer(ldata, CD_PREVIEW_MLOOPCOL); - const int hasOrigSpace = CustomData_has_layer(ldata, CD_ORIGSPACE_MLOOP); - - 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_mallocN(sizeof(*mface_to_poly_map) * looptris_tot, __func__); - mface = MEM_mallocN(sizeof(*mface) * looptris_tot, __func__); - - mface_index = 0; - mp = mpoly; - for (poly_index = 0; poly_index < totpoly; poly_index++, mp++) { - 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]; \ - /* set loop indices, transformed to vert indices later */ \ - mf->v1 = mp->loopstart + i1; \ - mf->v2 = mp->loopstart + i2; \ - mf->v3 = mp->loopstart + i3; \ - mf->v4 = 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]; \ - /* 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 */ \ - mf->mat_nr = mp->mat_nr; \ - mf->flag = mp->flag; \ - mf->edcode = TESSFACE_IS_QUAD; /* EXCEPTION */ \ - (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 { -#define USE_TESSFACE_CALCNORMAL - - 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__); - } - - 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); - - sf_vert->keyindex = 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; - } - 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 <= mp->totloop - 2); - (void)totfilltri; - - for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next, mf++) { - 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->v4 = 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++; - } - - BLI_scanfill_end_arena(&sf_ctx, sf_arena); - -#undef USE_TESSFACE_CALCNORMAL - } - } - - if (sf_arena) { - BLI_memarena_free(sf_arena); - sf_arena = NULL; - } - - CustomData_free(fdata, totface); - totface = mface_index; - - BLI_assert(totface <= looptris_tot); - - /* not essential but without this we store over-alloc'd memory in the CustomData layers */ - if (LIKELY(looptris_tot != totface)) { - mface = MEM_reallocN(mface, sizeof(*mface) * totface); - mface_to_poly_map = MEM_reallocN(mface_to_poly_map, sizeof(*mface_to_poly_map) * 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, pdata, ldata, totface); - - if (do_face_nor_cpy) { - /* 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]]); - } - } - } - - 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] = mf->v1; - lindex[1] = mf->v2; - lindex[2] = mf->v3; -#ifdef USE_TESSFACE_QUADS - if (mf_len == 4) lindex[3] = mf->v4; -#endif - - /*transform loop indices to vert indices*/ - mf->v1 = mloop[mf->v1].v; - mf->v2 = mloop[mf->v2].v; - mf->v3 = mloop[mf->v3].v; -#ifdef USE_TESSFACE_QUADS - if (mf_len == 4) mf->v4 = mloop[mf->v4].v; -#endif - - 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, -#endif - numTex, numCol, hasPCol, hasOrigSpace); - - -#ifdef USE_TESSFACE_QUADS - test_index_face(mf, fdata, mface_index, mf_len); -#endif - - } - - return totface; - -#undef USE_TESSFACE_SPEEDUP - -} - - -#ifdef USE_BMESH_SAVE_AS_COMPAT - -/* - * this function recreates a tessellation. - * returns number of tessellation faces. - */ -int BKE_mesh_mpoly_to_mface(struct CustomData *fdata, struct CustomData *ldata, - struct CustomData *pdata, int totface, int UNUSED(totloop), int totpoly) -{ - MLoop *mloop; - - int lindex[4]; - int i; - int k; - - MPoly *mp, *mpoly; - MFace *mface = NULL, *mf; - BLI_array_declare(mface); - - 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); - - mpoly = CustomData_get_layer(pdata, CD_MPOLY); - mloop = CustomData_get_layer(ldata, CD_MLOOP); - - mp = mpoly; - k = 0; - for (i = 0; i < totpoly; i++, mp++) { - if (ELEM(mp->totloop, 3, 4)) { - BLI_array_grow_one(mface); - mf = &mface[k]; - - mf->mat_nr = mp->mat_nr; - mf->flag = mp->flag; - - mf->v1 = mp->loopstart + 0; - mf->v2 = mp->loopstart + 1; - mf->v3 = mp->loopstart + 2; - mf->v4 = (mp->totloop == 4) ? (mp->loopstart + 3) : 0; - - /* abuse edcode for temp storage and clear next loop */ - mf->edcode = (char)mp->totloop; /* only ever 3 or 4 */ - - k++; - } - } - - CustomData_free(fdata, totface); - - totface = k; - - CustomData_add_layer(fdata, CD_MFACE, CD_ASSIGN, mface, totface); - - CustomData_from_bmeshpoly(fdata, pdata, ldata, totface); - - mp = mpoly; - k = 0; - for (i = 0; i < totpoly; i++, mp++) { - if (ELEM(mp->totloop, 3, 4)) { - mf = &mface[k]; - - if (mf->edcode == 3) { - /* sort loop indices to ensure winding is correct */ - /* NO SORT - looks like we can skip this */ - - lindex[0] = mf->v1; - lindex[1] = mf->v2; - lindex[2] = mf->v3; - lindex[3] = 0; /* unused */ - - /* transform loop indices to vert indices */ - mf->v1 = mloop[mf->v1].v; - mf->v2 = mloop[mf->v2].v; - mf->v3 = mloop[mf->v3].v; - - BKE_mesh_loops_to_mface_corners(fdata, ldata, pdata, - lindex, k, i, 3, - numTex, numCol, hasPCol, hasOrigSpace); - test_index_face(mf, fdata, k, 3); - } - else { - /* sort loop indices to ensure winding is correct */ - /* NO SORT - looks like we can skip this */ - - lindex[0] = mf->v1; - lindex[1] = mf->v2; - lindex[2] = mf->v3; - lindex[3] = mf->v4; - - /* transform loop indices to vert indices */ - mf->v1 = mloop[mf->v1].v; - mf->v2 = mloop[mf->v2].v; - mf->v3 = mloop[mf->v3].v; - mf->v4 = mloop[mf->v4].v; - - BKE_mesh_loops_to_mface_corners(fdata, ldata, pdata, - lindex, k, i, 4, - numTex, numCol, hasPCol, hasOrigSpace); - test_index_face(mf, fdata, k, 4); - } - - mf->edcode = 0; - - k++; - } - } - - return k; -} -#endif /* USE_BMESH_SAVE_AS_COMPAT */ - -/* - * COMPUTE POLY NORMAL - * - * Computes the normal of a planar - * polygon See Graphics Gems for - * computing newell normal. - * - */ -static void mesh_calc_ngon_normal(MPoly *mpoly, MLoop *loopstart, - MVert *mvert, float normal[3]) -{ - const int nverts = mpoly->totloop; - float const *v_prev = mvert[loopstart[nverts - 1].v].co; - float const *v_curr; - int i; - - zero_v3(normal); - - /* Newell's Method */ - for (i = 0; i < nverts; i++) { - v_curr = mvert[loopstart[i].v].co; - add_newell_cross_v3_v3v3(normal, v_prev, v_curr); - v_prev = v_curr; - } - - if (UNLIKELY(normalize_v3(normal) == 0.0f)) { - normal[2] = 1.0f; /* other axis set to 0.0 */ - } -} - -void BKE_mesh_calc_poly_normal(MPoly *mpoly, MLoop *loopstart, - MVert *mvarray, float no[3]) -{ - if (mpoly->totloop > 4) { - mesh_calc_ngon_normal(mpoly, loopstart, mvarray, no); - } - else if (mpoly->totloop == 3) { - normal_tri_v3(no, - mvarray[loopstart[0].v].co, - mvarray[loopstart[1].v].co, - mvarray[loopstart[2].v].co - ); - } - else if (mpoly->totloop == 4) { - normal_quad_v3(no, - mvarray[loopstart[0].v].co, - mvarray[loopstart[1].v].co, - mvarray[loopstart[2].v].co, - mvarray[loopstart[3].v].co - ); - } - else { /* horrible, two sided face! */ - no[0] = 0.0; - no[1] = 0.0; - no[2] = 1.0; - } -} -/* duplicate of function above _but_ takes coords rather then mverts */ -static void mesh_calc_ngon_normal_coords(MPoly *mpoly, MLoop *loopstart, - const float (*vertex_coords)[3], float normal[3]) -{ - const int nverts = mpoly->totloop; - float const *v_prev = vertex_coords[loopstart[nverts - 1].v]; - float const *v_curr; - int i; - - zero_v3(normal); - - /* Newell's Method */ - for (i = 0; i < nverts; i++) { - v_curr = vertex_coords[loopstart[i].v]; - add_newell_cross_v3_v3v3(normal, v_prev, v_curr); - v_prev = v_curr; - } - - if (UNLIKELY(normalize_v3(normal) == 0.0f)) { - normal[2] = 1.0f; /* other axis set to 0.0 */ - } -} - -void BKE_mesh_calc_poly_normal_coords(MPoly *mpoly, MLoop *loopstart, - const float (*vertex_coords)[3], float no[3]) -{ - if (mpoly->totloop > 4) { - mesh_calc_ngon_normal_coords(mpoly, loopstart, vertex_coords, no); - } - else if (mpoly->totloop == 3) { - normal_tri_v3(no, - vertex_coords[loopstart[0].v], - vertex_coords[loopstart[1].v], - vertex_coords[loopstart[2].v] - ); - } - else if (mpoly->totloop == 4) { - normal_quad_v3(no, - vertex_coords[loopstart[0].v], - vertex_coords[loopstart[1].v], - vertex_coords[loopstart[2].v], - vertex_coords[loopstart[3].v] - ); - } - else { /* horrible, two sided face! */ - no[0] = 0.0; - no[1] = 0.0; - no[2] = 1.0; - } -} - -static void mesh_calc_ngon_center(MPoly *mpoly, MLoop *loopstart, - MVert *mvert, float cent[3]) -{ - const float w = 1.0f / (float)mpoly->totloop; - int i; - - zero_v3(cent); - - for (i = 0; i < mpoly->totloop; i++) { - madd_v3_v3fl(cent, mvert[(loopstart++)->v].co, w); - } -} - -void BKE_mesh_calc_poly_center(MPoly *mpoly, MLoop *loopstart, - MVert *mvarray, float cent[3]) -{ - if (mpoly->totloop == 3) { - cent_tri_v3(cent, - mvarray[loopstart[0].v].co, - mvarray[loopstart[1].v].co, - mvarray[loopstart[2].v].co - ); - } - else if (mpoly->totloop == 4) { - cent_quad_v3(cent, - mvarray[loopstart[0].v].co, - mvarray[loopstart[1].v].co, - mvarray[loopstart[2].v].co, - mvarray[loopstart[3].v].co - ); - } - else { - mesh_calc_ngon_center(mpoly, loopstart, mvarray, cent); - } -} - -/* note, passing polynormal is only a speedup so we can skip calculating it */ -float BKE_mesh_calc_poly_area(MPoly *mpoly, MLoop *loopstart, - MVert *mvarray, const float polynormal[3]) -{ - if (mpoly->totloop == 3) { - return area_tri_v3(mvarray[loopstart[0].v].co, - mvarray[loopstart[1].v].co, - mvarray[loopstart[2].v].co - ); - } - else if (mpoly->totloop == 4) { - return area_quad_v3(mvarray[loopstart[0].v].co, - mvarray[loopstart[1].v].co, - mvarray[loopstart[2].v].co, - mvarray[loopstart[3].v].co - ); - } - else { - int i; - MLoop *l_iter = loopstart; - float area, polynorm_local[3]; - float (*vertexcos)[3] = BLI_array_alloca(vertexcos, mpoly->totloop); - const float *no = polynormal ? polynormal : polynorm_local; - - /* pack vertex cos into an array for area_poly_v3 */ - for (i = 0; i < mpoly->totloop; i++, l_iter++) { - copy_v3_v3(vertexcos[i], mvarray[l_iter->v].co); - } - - /* need normal for area_poly_v3 as well */ - if (polynormal == NULL) { - BKE_mesh_calc_poly_normal(mpoly, loopstart, mvarray, polynorm_local); - } - - /* finally calculate the area */ - area = area_poly_v3(mpoly->totloop, vertexcos, no); - - return area; - } -} - -/* note, results won't be correct if polygon is non-planar */ -static float mesh_calc_poly_planar_area_centroid(MPoly *mpoly, MLoop *loopstart, MVert *mvarray, float cent[3]) -{ - int i; - float tri_area; - float total_area = 0.0f; - float v1[3], v2[3], v3[3], normal[3], tri_cent[3]; - - BKE_mesh_calc_poly_normal(mpoly, loopstart, mvarray, normal); - copy_v3_v3(v1, mvarray[loopstart[0].v].co); - copy_v3_v3(v2, mvarray[loopstart[1].v].co); - zero_v3(cent); - - for (i = 2; i < mpoly->totloop; i++) { - copy_v3_v3(v3, mvarray[loopstart[i].v].co); - - tri_area = area_tri_signed_v3(v1, v2, v3, normal); - total_area += tri_area; - - cent_tri_v3(tri_cent, v1, v2, v3); - madd_v3_v3fl(cent, tri_cent, tri_area); - - copy_v3_v3(v2, v3); - } - - mul_v3_fl(cent, 1.0f / total_area); - - return total_area; -} - -/** - * Calculate smooth groups from sharp edges. - * - * \param r_totgroup The total number of groups, 1 or more. - * \return Polygon aligned array of group index values (bitflags if use_bitflags is true), starting at 1. - */ -int *BKE_mesh_calc_smoothgroups(const MEdge *medge, const int totedge, - const MPoly *mpoly, const int totpoly, - const MLoop *mloop, const int totloop, - int *r_totgroup, const bool use_bitflags) -{ - int *poly_groups; - int *poly_stack; - - int poly_prev = 0; - const int temp_poly_group_id = 3; /* Placeholder value. */ - const int poly_group_id_overflowed = 5; /* Group we could not find any available bit, will be reset to 0 at end */ - int tot_group = 0; - bool group_id_overflow = false; - - /* map vars */ - MeshElemMap *edge_poly_map; - int *edge_poly_mem; - - if (totpoly == 0) { - *r_totgroup = 0; - return NULL; - } - - BKE_mesh_edge_poly_map_create(&edge_poly_map, &edge_poly_mem, - medge, totedge, - mpoly, totpoly, - mloop, totloop); - - poly_groups = MEM_callocN(sizeof(int) * totpoly, __func__); - poly_stack = MEM_mallocN(sizeof(int) * totpoly, __func__); - - while (true) { - int poly; - int bit_poly_group_mask = 0; - int poly_group_id; - int ps_curr_idx = 0, ps_end_idx = 0; /* stack indices */ - - for (poly = poly_prev; poly < totpoly; poly++) { - if (poly_groups[poly] == 0) { - break; - } - } - - if (poly == totpoly) { - /* all done */ - break; - } - - poly_group_id = use_bitflags ? temp_poly_group_id : ++tot_group; - - /* start searching from here next time */ - poly_prev = poly + 1; - - poly_groups[poly] = poly_group_id; - poly_stack[ps_end_idx++] = poly; - - while (ps_curr_idx != ps_end_idx) { - const MPoly *mp; - const MLoop *ml; - int j; - - poly = poly_stack[ps_curr_idx++]; - BLI_assert(poly_groups[poly] == poly_group_id); - - mp = &mpoly[poly]; - for (ml = &mloop[mp->loopstart], j = mp->totloop; j--; ml++) { - /* loop over poly users */ - const MeshElemMap *map_ele = &edge_poly_map[ml->e]; - int *p = map_ele->indices; - int i = map_ele->count; - if (!(medge[ml->e].flag & ME_SHARP)) { - for (; i--; p++) { - /* if we meet other non initialized its a bug */ - BLI_assert(ELEM(poly_groups[*p], 0, poly_group_id)); - - if (poly_groups[*p] == 0) { - poly_groups[*p] = poly_group_id; - poly_stack[ps_end_idx++] = *p; - } - } - } - else if (use_bitflags) { - /* Find contiguous smooth groups already assigned, these are the values we can't reuse! */ - for (; i--; p++) { - int bit = poly_groups[*p]; - if (!ELEM3(bit, 0, poly_group_id, poly_group_id_overflowed) && - !(bit_poly_group_mask & bit)) - { - bit_poly_group_mask |= bit; - } - } - } - } - } - /* And now, we have all our poly from current group in poly_stack (from 0 to (ps_end_idx - 1)), as well as - * all smoothgroups bits we can't use in bit_poly_group_mask. - */ - if (use_bitflags) { - int i, *p, gid_bit = 0; - poly_group_id = 1; - - /* Find first bit available! */ - for (; (poly_group_id & bit_poly_group_mask) && (gid_bit < 32); gid_bit++) { - poly_group_id <<= 1; /* will 'overflow' on last possible iteration. */ - } - if (UNLIKELY(gid_bit > 31)) { - /* All bits used in contiguous smooth groups, we can't do much! - * Note: this is *very* unlikely - theoretically, four groups are enough, I don't think we can reach - * this goal with such a simple algo, but I don't think either we'll never need all 32 groups! - */ - printf("Warning, could not find an available id for current smooth group, faces will me marked " - "as out of any smooth group...\n"); - poly_group_id = poly_group_id_overflowed; /* Can't use 0, will have to set them to this value later. */ - group_id_overflow = true; - } - if (gid_bit > tot_group) { - tot_group = gid_bit; - } - /* And assign the final smooth group id to that poly group! */ - for (i = ps_end_idx, p = poly_stack; i--; p++) { - poly_groups[*p] = poly_group_id; - } - } - } - - if (UNLIKELY(group_id_overflow)) { - int i = totpoly, *gid = poly_groups; - for (; i--; gid++) { - if (*gid == poly_group_id_overflowed) { - *gid = 0; - } - } - } - - MEM_freeN(edge_poly_map); - MEM_freeN(edge_poly_mem); - MEM_freeN(poly_stack); - - *r_totgroup = tot_group + 1; - - return poly_groups; -} - - - -/** - * This function takes the difference between 2 vertex-coord-arrays - * (\a vert_cos_src, \a vert_cos_dst), - * and applies the difference to \a vert_cos_new relative to \a vert_cos_org. - * - * \param vert_cos_src reference deform source. - * \param vert_cos_dst reference deform destination. - * - * \param vert_cos_org reference for the output location. - * \param vert_cos_new resulting coords. - */ -void BKE_mesh_calc_relative_deform( - const MPoly *mpoly, const int totpoly, - const MLoop *mloop, const int totvert, - - const float (*vert_cos_src)[3], - const float (*vert_cos_dst)[3], - - const float (*vert_cos_org)[3], - float (*vert_cos_new)[3]) -{ - const MPoly *mp; - int i; - - int *vert_accum = MEM_callocN(sizeof(*vert_accum) * totvert, __func__); - - memset(vert_cos_new, '\0', sizeof(*vert_cos_new) * totvert); - - for (i = 0, mp = mpoly; i < totpoly; i++, mp++) { - const MLoop *loopstart = mloop + mp->loopstart; - int j; - - for (j = 0; j < mp->totloop; j++) { - int v_prev = (loopstart + ((mp->totloop + (j - 1)) % mp->totloop))->v; - int v_curr = (loopstart + j)->v; - int v_next = (loopstart + ((j + 1) % mp->totloop))->v; - - float tvec[3]; - - barycentric_transform( - tvec, vert_cos_dst[v_curr], - vert_cos_org[v_prev], vert_cos_org[v_curr], vert_cos_org[v_next], - vert_cos_src[v_prev], vert_cos_src[v_curr], vert_cos_src[v_next] - ); - - add_v3_v3(vert_cos_new[v_curr], tvec); - vert_accum[v_curr] += 1; - } - } - - for (i = 0; i < totvert; i++) { - if (vert_accum[i]) { - mul_v3_fl(vert_cos_new[i], 1.0f / (float)vert_accum[i]); - } - else { - copy_v3_v3(vert_cos_new[i], vert_cos_org[i]); - } - } - - MEM_freeN(vert_accum); -} - -/* Find the index of the loop in 'poly' which references vertex, - * returns -1 if not found */ -int poly_find_loop_from_vert(const MPoly *poly, const MLoop *loopstart, - unsigned vert) -{ - int j; - for (j = 0; j < poly->totloop; j++, loopstart++) { - if (loopstart->v == vert) - return j; - } - - return -1; -} - -/* Fill 'adj_r' with the loop indices in 'poly' adjacent to the - * vertex. Returns the index of the loop matching vertex, or -1 if the - * vertex is not in 'poly' */ -int poly_get_adj_loops_from_vert(unsigned adj_r[3], const MPoly *poly, - const MLoop *mloop, unsigned vert) -{ - int corner = poly_find_loop_from_vert(poly, - &mloop[poly->loopstart], - vert); - - if (corner != -1) { - const MLoop *ml = &mloop[poly->loopstart + corner]; - - /* vertex was found */ - adj_r[0] = ME_POLY_LOOP_PREV(mloop, poly, corner)->v; - adj_r[1] = ml->v; - adj_r[2] = ME_POLY_LOOP_NEXT(mloop, poly, corner)->v; - } - - return corner; -} - -/* Return the index of the edge vert that is not equal to 'v'. If - * neither edge vertex is equal to 'v', returns -1. */ -int BKE_mesh_edge_other_vert(const MEdge *e, int v) -{ - if (e->v1 == v) - return e->v2; - else if (e->v2 == v) - return e->v1; - else - return -1; -} - -/* update the hide flag for edges and faces from the corresponding - * flag in verts */ -void BKE_mesh_flush_hidden_from_verts_ex(const MVert *mvert, - const MLoop *mloop, - MEdge *medge, const int totedge, - MPoly *mpoly, const int totpoly) -{ - int i, j; - - for (i = 0; i < totedge; i++) { - MEdge *e = &medge[i]; - if (mvert[e->v1].flag & ME_HIDE || - mvert[e->v2].flag & ME_HIDE) - { - e->flag |= ME_HIDE; - } - else { - e->flag &= ~ME_HIDE; - } - } - for (i = 0; i < totpoly; i++) { - MPoly *p = &mpoly[i]; - p->flag &= ~ME_HIDE; - for (j = 0; j < p->totloop; j++) { - if (mvert[mloop[p->loopstart + j].v].flag & ME_HIDE) - p->flag |= ME_HIDE; - } - } -} -void BKE_mesh_flush_hidden_from_verts(Mesh *me) -{ - BKE_mesh_flush_hidden_from_verts_ex(me->mvert, me->mloop, - me->medge, me->totedge, - me->mpoly, me->totpoly); -} - -void BKE_mesh_flush_hidden_from_polys_ex(MVert *mvert, - const MLoop *mloop, - MEdge *medge, const int UNUSED(totedge), - const MPoly *mpoly, const int totpoly) -{ - const MPoly *mp; - int i; - - i = totpoly; - for (mp = mpoly; i--; mp++) { - if (mp->flag & ME_HIDE) { - const MLoop *ml; - int j; - j = mp->totloop; - for (ml = &mloop[mp->loopstart]; j--; ml++) { - mvert[ml->v].flag |= ME_HIDE; - medge[ml->e].flag |= ME_HIDE; - } - } - } - - i = totpoly; - for (mp = mpoly; i--; mp++) { - if ((mp->flag & ME_HIDE) == 0) { - const MLoop *ml; - int j; - j = mp->totloop; - for (ml = &mloop[mp->loopstart]; j--; ml++) { - mvert[ml->v].flag &= ~ME_HIDE; - medge[ml->e].flag &= ~ME_HIDE; - } - } - } -} -void BKE_mesh_flush_hidden_from_polys(Mesh *me) -{ - BKE_mesh_flush_hidden_from_polys_ex(me->mvert, me->mloop, - me->medge, me->totedge, - me->mpoly, me->totpoly); -} - -/** - * simple poly -> vert/edge selection. - */ -void BKE_mesh_flush_select_from_polys_ex(MVert *mvert, const int totvert, - const MLoop *mloop, - MEdge *medge, const int totedge, - const MPoly *mpoly, const int totpoly) -{ - MVert *mv; - MEdge *med; - const MPoly *mp; - int i; - - i = totvert; - for (mv = mvert; i--; mv++) { - mv->flag &= ~SELECT; - } - - i = totedge; - for (med = medge; i--; med++) { - med->flag &= ~SELECT; - } - - i = totpoly; - for (mp = mpoly; i--; mp++) { - /* assume if its selected its not hidden and none of its verts/edges are hidden - * (a common assumption)*/ - if (mp->flag & ME_FACE_SEL) { - const MLoop *ml; - int j; - j = mp->totloop; - for (ml = &mloop[mp->loopstart]; j--; ml++) { - mvert[ml->v].flag |= SELECT; - medge[ml->e].flag |= SELECT; - } - } - } -} -void BKE_mesh_flush_select_from_polys(Mesh *me) -{ - BKE_mesh_flush_select_from_polys_ex(me->mvert, me->totvert, - me->mloop, - me->medge, me->totedge, - me->mpoly, me->totpoly); -} - -void BKE_mesh_flush_select_from_verts_ex(const MVert *mvert, const int UNUSED(totvert), - const MLoop *mloop, - MEdge *medge, const int totedge, - MPoly *mpoly, const int totpoly) -{ - MEdge *med; - MPoly *mp; - int i; - - /* edges */ - i = totedge; - for (med = medge; i--; med++) { - if ((med->flag & ME_HIDE) == 0) { - if ((mvert[med->v1].flag & SELECT) && (mvert[med->v2].flag & SELECT)) { - med->flag |= SELECT; - } - else { - med->flag &= ~SELECT; - } - } - } - - /* polys */ - i = totpoly; - for (mp = mpoly; i--; mp++) { - if ((mp->flag & ME_HIDE) == 0) { - int ok = TRUE; - const MLoop *ml; - int j; - j = mp->totloop; - for (ml = &mloop[mp->loopstart]; j--; ml++) { - if ((mvert[ml->v].flag & SELECT) == 0) { - ok = FALSE; - break; - } - } - - if (ok) { - mp->flag |= ME_FACE_SEL; - } - else { - mp->flag &= ~ME_FACE_SEL; - } - } - } -} -void BKE_mesh_flush_select_from_verts(Mesh *me) -{ - BKE_mesh_flush_select_from_verts_ex(me->mvert, me->totvert, - me->mloop, - me->medge, me->totedge, - me->mpoly, me->totpoly); -} - - -/* basic vertex data functions */ -bool BKE_mesh_minmax(Mesh *me, float r_min[3], float r_max[3]) -{ - int i = me->totvert; - MVert *mvert; - for (mvert = me->mvert; i--; mvert++) { - minmax_v3v3_v3(r_min, r_max, mvert->co); - } - - return (me->totvert != 0); -} - -bool BKE_mesh_center_median(Mesh *me, float cent[3]) -{ - int i = me->totvert; - MVert *mvert; - zero_v3(cent); - for (mvert = me->mvert; i--; mvert++) { - add_v3_v3(cent, mvert->co); - } - /* otherwise we get NAN for 0 verts */ - if (me->totvert) { - mul_v3_fl(cent, 1.0f / (float)me->totvert); - } - - return (me->totvert != 0); -} - -bool BKE_mesh_center_bounds(Mesh *me, float cent[3]) -{ - float min[3], max[3]; - INIT_MINMAX(min, max); - if (BKE_mesh_minmax(me, min, max)) { - mid_v3_v3v3(cent, min, max); - return true; - } - - return false; -} - -bool BKE_mesh_center_centroid(Mesh *me, float cent[3]) -{ - int i = me->totpoly; - MPoly *mpoly; - float poly_area; - float total_area = 0.0f; - float poly_cent[3]; - - zero_v3(cent); - - /* calculate a weighted average of polygon centroids */ - for (mpoly = me->mpoly; i--; mpoly++) { - poly_area = mesh_calc_poly_planar_area_centroid(mpoly, me->mloop + mpoly->loopstart, me->mvert, poly_cent); - - madd_v3_v3fl(cent, poly_cent, poly_area); - total_area += poly_area; - } - /* otherwise we get NAN for 0 polys */ - if (me->totpoly) { - mul_v3_fl(cent, 1.0f / total_area); - } - - /* zero area faces cause this, fallback to median */ - if (UNLIKELY(!is_finite_v3(cent))) { - return BKE_mesh_center_median(me, cent); - } - - return (me->totpoly != 0); -} - -void BKE_mesh_translate(Mesh *me, const float offset[3], const bool do_keys) -{ - int i = me->totvert; - MVert *mvert; - for (mvert = me->mvert; i--; mvert++) { - add_v3_v3(mvert->co, offset); - } - - if (do_keys && me->key) { - KeyBlock *kb; - for (kb = me->key->block.first; kb; kb = kb->next) { - float *fp = kb->data; - for (i = kb->totelem; i--; fp += 3) { - add_v3_v3(fp, offset); - } - } - } -} - -void BKE_mesh_ensure_navmesh(Mesh *me) -{ - if (!CustomData_has_layer(&me->pdata, CD_RECAST)) { - int i; - int numFaces = me->totpoly; - int *recastData; - recastData = (int *)MEM_mallocN(numFaces * sizeof(int), __func__); - for (i = 0; i < numFaces; i++) { - recastData[i] = i + 1; - } - CustomData_add_layer_named(&me->pdata, CD_RECAST, CD_ASSIGN, recastData, numFaces, "recastData"); - } -} - -void BKE_mesh_tessface_calc(Mesh *mesh) -{ - mesh->totface = BKE_mesh_recalc_tessellation(&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) { - BKE_mesh_tessface_calc(mesh); - } -} - -void BKE_mesh_tessface_clear(Mesh *mesh) +void BKE_mesh_tessface_clear(Mesh *mesh) { mesh_tessface_clear_intern(mesh, TRUE); } -#if 0 /* slow version of the function below */ -void BKE_mesh_calc_poly_angles(MPoly *mpoly, MLoop *loopstart, - MVert *mvarray, float angles[]) -{ - MLoop *ml; - MLoop *mloop = &loopstart[-mpoly->loopstart]; - - int j; - for (j = 0, ml = loopstart; j < mpoly->totloop; j++, ml++) { - MLoop *ml_prev = ME_POLY_LOOP_PREV(mloop, mpoly, j); - MLoop *ml_next = ME_POLY_LOOP_NEXT(mloop, mpoly, j); - - float e1[3], e2[3]; - - sub_v3_v3v3(e1, mvarray[ml_next->v].co, mvarray[ml->v].co); - sub_v3_v3v3(e2, mvarray[ml_prev->v].co, mvarray[ml->v].co); - - angles[j] = (float)M_PI - angle_v3v3(e1, e2); - } -} - -#else /* equivalent the function above but avoid multiple subtractions + normalize */ - -void BKE_mesh_calc_poly_angles(MPoly *mpoly, MLoop *loopstart, - MVert *mvarray, float angles[]) -{ - float nor_prev[3]; - float nor_next[3]; - - int i_this = mpoly->totloop - 1; - int i_next = 0; - - sub_v3_v3v3(nor_prev, mvarray[loopstart[i_this - 1].v].co, mvarray[loopstart[i_this].v].co); - normalize_v3(nor_prev); - - while (i_next < mpoly->totloop) { - sub_v3_v3v3(nor_next, mvarray[loopstart[i_this].v].co, mvarray[loopstart[i_next].v].co); - normalize_v3(nor_next); - angles[i_this] = angle_normalized_v3v3(nor_prev, nor_next); - - /* step */ - copy_v3_v3(nor_prev, nor_next); - i_this = i_next; - i_next++; - } -} -#endif - -void BKE_mesh_poly_edgehash_insert(EdgeHash *ehash, const MPoly *mp, const MLoop *mloop) -{ - const MLoop *ml, *ml_next; - int i = mp->totloop; - - ml_next = mloop; /* first loop */ - ml = &ml_next[i - 1]; /* last loop */ - - while (i-- != 0) { - BLI_edgehash_reinsert(ehash, ml->v, ml_next->v, NULL); - - ml = ml_next; - ml_next++; - } -} - -void BKE_mesh_poly_edgebitmap_insert(unsigned int *edge_bitmap, const MPoly *mp, const MLoop *mloop) -{ - const MLoop *ml; - int i = mp->totloop; - - ml = mloop; - - while (i-- != 0) { - BLI_BITMAP_SET(edge_bitmap, ml->e); - ml++; - } -} - void BKE_mesh_do_versions_cd_flag_init(Mesh *mesh) { if (UNLIKELY(mesh->cd_flag)) { diff --git a/source/blender/blenkernel/intern/mesh_evaluate.c b/source/blender/blenkernel/intern/mesh_evaluate.c new file mode 100644 index 00000000000..d35d91cc45a --- /dev/null +++ b/source/blender/blenkernel/intern/mesh_evaluate.c @@ -0,0 +1,2017 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * 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. + * + * Contributor(s): Blender Foundation + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/blenkernel/intern/mesh_evaluate.c + * \ingroup bke + * + * Functions to evaluate mesh data. + */ + +#include "MEM_guardedalloc.h" + +#include "DNA_object_types.h" +#include "DNA_mesh_types.h" +#include "DNA_meshdata_types.h" + +#include "BLI_utildefines.h" +#include "BLI_memarena.h" +#include "BLI_math.h" +#include "BLI_edgehash.h" +#include "BLI_bitmap.h" +#include "BLI_scanfill.h" +#include "BLI_alloca.h" +#include "BLI_array.h" + +#include "BKE_customdata.h" +#include "BKE_mesh.h" +#include "BKE_multires.h" + + +/* -------------------------------------------------------------------- */ + +/** \name Mesh Normal Calculation + * \{ */ + +/** + * Call when there are no polygons. + */ +static void mesh_calc_normals_vert_fallback(MVert *mverts, int numVerts) +{ + int i; + for (i = 0; i < numVerts; i++) { + MVert *mv = &mverts[i]; + float no[3]; + + normalize_v3_v3(no, mv->co); + normal_float_to_short_v3(mv->no, no); + } +} + +/* Calculate vertex and face normals, face normals are returned in *faceNors_r if non-NULL + * and vertex normals are stored in actual mverts. + */ +void BKE_mesh_calc_normals_mapping(MVert *mverts, int numVerts, + MLoop *mloop, MPoly *mpolys, int numLoops, int numPolys, float (*polyNors_r)[3], + MFace *mfaces, int numFaces, int *origIndexFace, float (*faceNors_r)[3]) +{ + BKE_mesh_calc_normals_mapping_ex(mverts, numVerts, mloop, mpolys, + numLoops, numPolys, polyNors_r, mfaces, numFaces, + origIndexFace, faceNors_r, FALSE); +} +/* extended version of 'BKE_mesh_calc_normals_poly' with option not to calc vertex normals */ +void BKE_mesh_calc_normals_mapping_ex( + MVert *mverts, int numVerts, + MLoop *mloop, MPoly *mpolys, + int numLoops, int numPolys, float (*polyNors_r)[3], + MFace *mfaces, int numFaces, int *origIndexFace, float (*faceNors_r)[3], + const bool only_face_normals) +{ + float (*pnors)[3] = polyNors_r, (*fnors)[3] = faceNors_r; + int i; + MFace *mf; + MPoly *mp; + + if (numPolys == 0) { + if (only_face_normals == FALSE) { + mesh_calc_normals_vert_fallback(mverts, numVerts); + } + return; + } + + /* if we are not calculating verts and no verts were passes then we have nothing to do */ + if ((only_face_normals == TRUE) && (polyNors_r == NULL) && (faceNors_r == NULL)) { + printf("%s: called with nothing to do\n", __func__); + return; + } + + if (!pnors) pnors = MEM_callocN(sizeof(float) * 3 * numPolys, "poly_nors mesh.c"); + /* if (!fnors) fnors = MEM_callocN(sizeof(float) * 3 * numFaces, "face nors mesh.c"); */ /* NO NEED TO ALLOC YET */ + + + if (only_face_normals == FALSE) { + /* vertex normals are optional, they require some extra calculations, + * so make them optional */ + BKE_mesh_calc_normals_poly(mverts, numVerts, mloop, mpolys, numLoops, numPolys, pnors, false); + } + else { + /* only calc poly normals */ + mp = mpolys; + for (i = 0; i < numPolys; i++, mp++) { + BKE_mesh_calc_poly_normal(mp, mloop + mp->loopstart, mverts, pnors[i]); + } + } + + if (origIndexFace && + /* fnors == faceNors_r */ /* NO NEED TO ALLOC YET */ + fnors != NULL && + numFaces) + { + mf = mfaces; + for (i = 0; i < numFaces; i++, mf++, origIndexFace++) { + if (*origIndexFace < numPolys) { + copy_v3_v3(fnors[i], pnors[*origIndexFace]); + } + else { + /* eek, we're not corresponding to polys */ + printf("error in %s: tessellation face indices are incorrect. normals may look bad.\n", __func__); + } + } + } + + if (pnors != polyNors_r) MEM_freeN(pnors); + /* if (fnors != faceNors_r) MEM_freeN(fnors); */ /* NO NEED TO ALLOC YET */ + + fnors = pnors = NULL; + +} + +static void mesh_calc_normals_poly_accum(MPoly *mp, MLoop *ml, + MVert *mvert, float polyno[3], float (*tnorms)[3]) +{ + const int nverts = mp->totloop; + float (*edgevecbuf)[3] = BLI_array_alloca(edgevecbuf, nverts); + int i; + + /* Polygon Normal and edge-vector */ + /* inline version of #BKE_mesh_calc_poly_normal, also does edge-vectors */ + { + int i_prev = nverts - 1; + float const *v_prev = mvert[ml[i_prev].v].co; + float const *v_curr; + + zero_v3(polyno); + /* Newell's Method */ + for (i = 0; i < nverts; i++) { + v_curr = mvert[ml[i].v].co; + add_newell_cross_v3_v3v3(polyno, v_prev, v_curr); + + /* Unrelated to normalize, calcualte edge-vector */ + sub_v3_v3v3(edgevecbuf[i_prev], v_prev, v_curr); + normalize_v3(edgevecbuf[i_prev]); + i_prev = i; + + v_prev = v_curr; + } + if (UNLIKELY(normalize_v3(polyno) == 0.0f)) { + polyno[2] = 1.0f; /* other axis set to 0.0 */ + } + } + + /* accumulate angle weighted face normal */ + /* inline version of #accumulate_vertex_normals_poly */ + { + const float *prev_edge = edgevecbuf[nverts - 1]; + + for (i = 0; i < nverts; i++) { + const float *cur_edge = edgevecbuf[i]; + + /* calculate angle between the two poly edges incident on + * this vertex */ + const float fac = saacos(-dot_v3v3(cur_edge, prev_edge)); + + /* accumulate */ + madd_v3_v3fl(tnorms[ml[i].v], polyno, fac); + prev_edge = cur_edge; + } + } + +} + +void BKE_mesh_calc_normals_poly(MVert *mverts, int numVerts, MLoop *mloop, MPoly *mpolys, + int UNUSED(numLoops), int numPolys, float (*r_polynors)[3], + const bool only_face_normals) +{ + float (*pnors)[3] = r_polynors; + float (*tnorms)[3]; + int i; + MPoly *mp; + + if (only_face_normals) { + BLI_assert(pnors != NULL); + +#pragma omp parallel for if (numPolys > BM_OMP_LIMIT) + for (i = 0; i < numPolys; i++) { + BKE_mesh_calc_poly_normal(&mpolys[i], mloop + mpolys[i].loopstart, mverts, pnors[i]); + } + return; + } + + /* first go through and calculate normals for all the polys */ + tnorms = MEM_callocN(sizeof(*tnorms) * numVerts, __func__); + + if (pnors) { + mp = mpolys; + for (i = 0; i < numPolys; i++, mp++) { + mesh_calc_normals_poly_accum(mp, mloop + mp->loopstart, mverts, pnors[i], tnorms); + } + } + else { + float tpnor[3]; /* temp poly normal */ + mp = mpolys; + for (i = 0; i < numPolys; i++, mp++) { + mesh_calc_normals_poly_accum(mp, mloop + mp->loopstart, mverts, tpnor, tnorms); + } + } + + /* following Mesh convention; we use vertex coordinate itself for normal in this case */ + for (i = 0; i < numVerts; i++) { + MVert *mv = &mverts[i]; + float *no = tnorms[i]; + + if (UNLIKELY(normalize_v3(no) == 0.0f)) { + normalize_v3_v3(no, mv->co); + } + + normal_float_to_short_v3(mv->no, no); + } + + MEM_freeN(tnorms); +} + +void BKE_mesh_calc_normals(Mesh *mesh) +{ + BKE_mesh_calc_normals_poly(mesh->mvert, mesh->totvert, + mesh->mloop, mesh->mpoly, mesh->totloop, mesh->totpoly, + NULL, false); +} + +void BKE_mesh_calc_normals_tessface(MVert *mverts, int numVerts, MFace *mfaces, int numFaces, float (*faceNors_r)[3]) +{ + float (*tnorms)[3] = MEM_callocN(numVerts * sizeof(*tnorms), "tnorms"); + float (*fnors)[3] = (faceNors_r) ? faceNors_r : MEM_callocN(sizeof(*fnors) * numFaces, "meshnormals"); + int i; + + for (i = 0; i < numFaces; i++) { + MFace *mf = &mfaces[i]; + float *f_no = fnors[i]; + float *n4 = (mf->v4) ? tnorms[mf->v4] : NULL; + float *c4 = (mf->v4) ? mverts[mf->v4].co : NULL; + + if (mf->v4) + normal_quad_v3(f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co, mverts[mf->v4].co); + else + normal_tri_v3(f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co); + + accumulate_vertex_normals(tnorms[mf->v1], tnorms[mf->v2], tnorms[mf->v3], n4, + f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co, c4); + } + + /* following Mesh convention; we use vertex coordinate itself for normal in this case */ + for (i = 0; i < numVerts; i++) { + MVert *mv = &mverts[i]; + float *no = tnorms[i]; + + if (UNLIKELY(normalize_v3(no) == 0.0f)) { + normalize_v3_v3(no, mv->co); + } + + normal_float_to_short_v3(mv->no, no); + } + + MEM_freeN(tnorms); + + if (fnors != faceNors_r) + MEM_freeN(fnors); +} +/** \} */ + + +/* -------------------------------------------------------------------- */ + +/** \name Polygon Calculations + * \{ */ + +/* + * COMPUTE POLY NORMAL + * + * Computes the normal of a planar + * polygon See Graphics Gems for + * computing newell normal. + * + */ +static void mesh_calc_ngon_normal(MPoly *mpoly, MLoop *loopstart, + MVert *mvert, float normal[3]) +{ + const int nverts = mpoly->totloop; + float const *v_prev = mvert[loopstart[nverts - 1].v].co; + float const *v_curr; + int i; + + zero_v3(normal); + + /* Newell's Method */ + for (i = 0; i < nverts; i++) { + v_curr = mvert[loopstart[i].v].co; + add_newell_cross_v3_v3v3(normal, v_prev, v_curr); + v_prev = v_curr; + } + + if (UNLIKELY(normalize_v3(normal) == 0.0f)) { + normal[2] = 1.0f; /* other axis set to 0.0 */ + } +} + +void BKE_mesh_calc_poly_normal(MPoly *mpoly, MLoop *loopstart, + MVert *mvarray, float no[3]) +{ + if (mpoly->totloop > 4) { + mesh_calc_ngon_normal(mpoly, loopstart, mvarray, no); + } + else if (mpoly->totloop == 3) { + normal_tri_v3(no, + mvarray[loopstart[0].v].co, + mvarray[loopstart[1].v].co, + mvarray[loopstart[2].v].co + ); + } + else if (mpoly->totloop == 4) { + normal_quad_v3(no, + mvarray[loopstart[0].v].co, + mvarray[loopstart[1].v].co, + mvarray[loopstart[2].v].co, + mvarray[loopstart[3].v].co + ); + } + else { /* horrible, two sided face! */ + no[0] = 0.0; + no[1] = 0.0; + no[2] = 1.0; + } +} +/* duplicate of function above _but_ takes coords rather then mverts */ +static void mesh_calc_ngon_normal_coords(MPoly *mpoly, MLoop *loopstart, + const float (*vertex_coords)[3], float normal[3]) +{ + const int nverts = mpoly->totloop; + float const *v_prev = vertex_coords[loopstart[nverts - 1].v]; + float const *v_curr; + int i; + + zero_v3(normal); + + /* Newell's Method */ + for (i = 0; i < nverts; i++) { + v_curr = vertex_coords[loopstart[i].v]; + add_newell_cross_v3_v3v3(normal, v_prev, v_curr); + v_prev = v_curr; + } + + if (UNLIKELY(normalize_v3(normal) == 0.0f)) { + normal[2] = 1.0f; /* other axis set to 0.0 */ + } +} + +void BKE_mesh_calc_poly_normal_coords(MPoly *mpoly, MLoop *loopstart, + const float (*vertex_coords)[3], float no[3]) +{ + if (mpoly->totloop > 4) { + mesh_calc_ngon_normal_coords(mpoly, loopstart, vertex_coords, no); + } + else if (mpoly->totloop == 3) { + normal_tri_v3(no, + vertex_coords[loopstart[0].v], + vertex_coords[loopstart[1].v], + vertex_coords[loopstart[2].v] + ); + } + else if (mpoly->totloop == 4) { + normal_quad_v3(no, + vertex_coords[loopstart[0].v], + vertex_coords[loopstart[1].v], + vertex_coords[loopstart[2].v], + vertex_coords[loopstart[3].v] + ); + } + else { /* horrible, two sided face! */ + no[0] = 0.0; + no[1] = 0.0; + no[2] = 1.0; + } +} + +static void mesh_calc_ngon_center(MPoly *mpoly, MLoop *loopstart, + MVert *mvert, float cent[3]) +{ + const float w = 1.0f / (float)mpoly->totloop; + int i; + + zero_v3(cent); + + for (i = 0; i < mpoly->totloop; i++) { + madd_v3_v3fl(cent, mvert[(loopstart++)->v].co, w); + } +} + +void BKE_mesh_calc_poly_center(MPoly *mpoly, MLoop *loopstart, + MVert *mvarray, float cent[3]) +{ + if (mpoly->totloop == 3) { + cent_tri_v3(cent, + mvarray[loopstart[0].v].co, + mvarray[loopstart[1].v].co, + mvarray[loopstart[2].v].co + ); + } + else if (mpoly->totloop == 4) { + cent_quad_v3(cent, + mvarray[loopstart[0].v].co, + mvarray[loopstart[1].v].co, + mvarray[loopstart[2].v].co, + mvarray[loopstart[3].v].co + ); + } + else { + mesh_calc_ngon_center(mpoly, loopstart, mvarray, cent); + } +} + +/* note, passing polynormal is only a speedup so we can skip calculating it */ +float BKE_mesh_calc_poly_area(MPoly *mpoly, MLoop *loopstart, + MVert *mvarray, const float polynormal[3]) +{ + if (mpoly->totloop == 3) { + return area_tri_v3(mvarray[loopstart[0].v].co, + mvarray[loopstart[1].v].co, + mvarray[loopstart[2].v].co + ); + } + else if (mpoly->totloop == 4) { + return area_quad_v3(mvarray[loopstart[0].v].co, + mvarray[loopstart[1].v].co, + mvarray[loopstart[2].v].co, + mvarray[loopstart[3].v].co + ); + } + else { + int i; + MLoop *l_iter = loopstart; + float area, polynorm_local[3]; + float (*vertexcos)[3] = BLI_array_alloca(vertexcos, mpoly->totloop); + const float *no = polynormal ? polynormal : polynorm_local; + + /* pack vertex cos into an array for area_poly_v3 */ + for (i = 0; i < mpoly->totloop; i++, l_iter++) { + copy_v3_v3(vertexcos[i], mvarray[l_iter->v].co); + } + + /* need normal for area_poly_v3 as well */ + if (polynormal == NULL) { + BKE_mesh_calc_poly_normal(mpoly, loopstart, mvarray, polynorm_local); + } + + /* finally calculate the area */ + area = area_poly_v3(mpoly->totloop, vertexcos, no); + + return area; + } +} + +/* note, results won't be correct if polygon is non-planar */ +static float mesh_calc_poly_planar_area_centroid(MPoly *mpoly, MLoop *loopstart, MVert *mvarray, float cent[3]) +{ + int i; + float tri_area; + float total_area = 0.0f; + float v1[3], v2[3], v3[3], normal[3], tri_cent[3]; + + BKE_mesh_calc_poly_normal(mpoly, loopstart, mvarray, normal); + copy_v3_v3(v1, mvarray[loopstart[0].v].co); + copy_v3_v3(v2, mvarray[loopstart[1].v].co); + zero_v3(cent); + + for (i = 2; i < mpoly->totloop; i++) { + copy_v3_v3(v3, mvarray[loopstart[i].v].co); + + tri_area = area_tri_signed_v3(v1, v2, v3, normal); + total_area += tri_area; + + cent_tri_v3(tri_cent, v1, v2, v3); + madd_v3_v3fl(cent, tri_cent, tri_area); + + copy_v3_v3(v2, v3); + } + + mul_v3_fl(cent, 1.0f / total_area); + + return total_area; +} + +#if 0 /* slow version of the function below */ +void BKE_mesh_calc_poly_angles(MPoly *mpoly, MLoop *loopstart, + MVert *mvarray, float angles[]) +{ + MLoop *ml; + MLoop *mloop = &loopstart[-mpoly->loopstart]; + + int j; + for (j = 0, ml = loopstart; j < mpoly->totloop; j++, ml++) { + MLoop *ml_prev = ME_POLY_LOOP_PREV(mloop, mpoly, j); + MLoop *ml_next = ME_POLY_LOOP_NEXT(mloop, mpoly, j); + + float e1[3], e2[3]; + + sub_v3_v3v3(e1, mvarray[ml_next->v].co, mvarray[ml->v].co); + sub_v3_v3v3(e2, mvarray[ml_prev->v].co, mvarray[ml->v].co); + + angles[j] = (float)M_PI - angle_v3v3(e1, e2); + } +} + +#else /* equivalent the function above but avoid multiple subtractions + normalize */ + +void BKE_mesh_calc_poly_angles(MPoly *mpoly, MLoop *loopstart, + MVert *mvarray, float angles[]) +{ + float nor_prev[3]; + float nor_next[3]; + + int i_this = mpoly->totloop - 1; + int i_next = 0; + + sub_v3_v3v3(nor_prev, mvarray[loopstart[i_this - 1].v].co, mvarray[loopstart[i_this].v].co); + normalize_v3(nor_prev); + + while (i_next < mpoly->totloop) { + sub_v3_v3v3(nor_next, mvarray[loopstart[i_this].v].co, mvarray[loopstart[i_next].v].co); + normalize_v3(nor_next); + angles[i_this] = angle_normalized_v3v3(nor_prev, nor_next); + + /* step */ + copy_v3_v3(nor_prev, nor_next); + i_this = i_next; + i_next++; + } +} +#endif + +void BKE_mesh_poly_edgehash_insert(EdgeHash *ehash, const MPoly *mp, const MLoop *mloop) +{ + const MLoop *ml, *ml_next; + int i = mp->totloop; + + ml_next = mloop; /* first loop */ + ml = &ml_next[i - 1]; /* last loop */ + + while (i-- != 0) { + BLI_edgehash_reinsert(ehash, ml->v, ml_next->v, NULL); + + ml = ml_next; + ml_next++; + } +} + +void BKE_mesh_poly_edgebitmap_insert(unsigned int *edge_bitmap, const MPoly *mp, const MLoop *mloop) +{ + const MLoop *ml; + int i = mp->totloop; + + ml = mloop; + + while (i-- != 0) { + BLI_BITMAP_SET(edge_bitmap, ml->e); + ml++; + } +} + +/** \} */ + + +/* -------------------------------------------------------------------- */ + +/** \name Mesh Center Calculation + * \{ */ + +bool BKE_mesh_center_median(Mesh *me, float cent[3]) +{ + int i = me->totvert; + MVert *mvert; + zero_v3(cent); + for (mvert = me->mvert; i--; mvert++) { + add_v3_v3(cent, mvert->co); + } + /* otherwise we get NAN for 0 verts */ + if (me->totvert) { + mul_v3_fl(cent, 1.0f / (float)me->totvert); + } + + return (me->totvert != 0); +} + +bool BKE_mesh_center_bounds(Mesh *me, float cent[3]) +{ + float min[3], max[3]; + INIT_MINMAX(min, max); + if (BKE_mesh_minmax(me, min, max)) { + mid_v3_v3v3(cent, min, max); + return true; + } + + return false; +} + +bool BKE_mesh_center_centroid(Mesh *me, float cent[3]) +{ + int i = me->totpoly; + MPoly *mpoly; + float poly_area; + float total_area = 0.0f; + float poly_cent[3]; + + zero_v3(cent); + + /* calculate a weighted average of polygon centroids */ + for (mpoly = me->mpoly; i--; mpoly++) { + poly_area = mesh_calc_poly_planar_area_centroid(mpoly, me->mloop + mpoly->loopstart, me->mvert, poly_cent); + + madd_v3_v3fl(cent, poly_cent, poly_area); + total_area += poly_area; + } + /* otherwise we get NAN for 0 polys */ + if (me->totpoly) { + mul_v3_fl(cent, 1.0f / total_area); + } + + /* zero area faces cause this, fallback to median */ + if (UNLIKELY(!is_finite_v3(cent))) { + return BKE_mesh_center_median(me, cent); + } + + return (me->totpoly != 0); +} +/** \} */ + + +/* -------------------------------------------------------------------- */ + +/** \name Mesh Connectivity Mapping + * \{ */ + + +/* ngon version wip, based on EDBM_uv_vert_map_create */ +/* this replaces the non bmesh function (in trunk) which takes MTFace's, if we ever need it back we could + * but for now this replaces it because its unused. */ + +UvVertMap *BKE_mesh_uv_vert_map_create(struct MPoly *mpoly, struct MLoop *mloop, struct MLoopUV *mloopuv, + unsigned int totpoly, unsigned int totvert, int selected, float *limit) +{ + UvVertMap *vmap; + UvMapVert *buf; + MPoly *mp; + unsigned int a; + int i, totuv, nverts; + + totuv = 0; + + /* generate UvMapVert array */ + mp = mpoly; + for (a = 0; a < totpoly; a++, mp++) + if (!selected || (!(mp->flag & ME_HIDE) && (mp->flag & ME_FACE_SEL))) + totuv += mp->totloop; + + if (totuv == 0) + return NULL; + + vmap = (UvVertMap *)MEM_callocN(sizeof(*vmap), "UvVertMap"); + if (!vmap) + return NULL; + + vmap->vert = (UvMapVert **)MEM_callocN(sizeof(*vmap->vert) * totvert, "UvMapVert*"); + buf = vmap->buf = (UvMapVert *)MEM_callocN(sizeof(*vmap->buf) * totuv, "UvMapVert"); + + if (!vmap->vert || !vmap->buf) { + BKE_mesh_uv_vert_map_free(vmap); + return NULL; + } + + mp = mpoly; + for (a = 0; a < totpoly; a++, mp++) { + if (!selected || (!(mp->flag & ME_HIDE) && (mp->flag & ME_FACE_SEL))) { + nverts = mp->totloop; + + for (i = 0; i < nverts; i++) { + buf->tfindex = i; + buf->f = a; + buf->separate = 0; + buf->next = vmap->vert[mloop[mp->loopstart + i].v]; + vmap->vert[mloop[mp->loopstart + i].v] = buf; + buf++; + } + } + } + + /* sort individual uvs for each vert */ + for (a = 0; a < totvert; a++) { + UvMapVert *newvlist = NULL, *vlist = vmap->vert[a]; + UvMapVert *iterv, *v, *lastv, *next; + float *uv, *uv2, uvdiff[2]; + + while (vlist) { + v = vlist; + vlist = vlist->next; + v->next = newvlist; + newvlist = v; + + uv = mloopuv[mpoly[v->f].loopstart + v->tfindex].uv; + lastv = NULL; + iterv = vlist; + + while (iterv) { + next = iterv->next; + + uv2 = mloopuv[mpoly[iterv->f].loopstart + iterv->tfindex].uv; + sub_v2_v2v2(uvdiff, uv2, uv); + + + if (fabsf(uv[0] - uv2[0]) < limit[0] && fabsf(uv[1] - uv2[1]) < limit[1]) { + if (lastv) lastv->next = next; + else vlist = next; + iterv->next = newvlist; + newvlist = iterv; + } + else + lastv = iterv; + + iterv = next; + } + + newvlist->separate = 1; + } + + vmap->vert[a] = newvlist; + } + + return vmap; +} + +UvMapVert *BKE_mesh_uv_vert_map_get_vert(UvVertMap *vmap, unsigned int v) +{ + return vmap->vert[v]; +} + +void BKE_mesh_uv_vert_map_free(UvVertMap *vmap) +{ + if (vmap) { + if (vmap->vert) MEM_freeN(vmap->vert); + if (vmap->buf) MEM_freeN(vmap->buf); + MEM_freeN(vmap); + } +} + +/* Generates a map where the key is the vertex and the value is a list + * of polys that use that vertex as a corner. The lists are allocated + * from one memory pool. */ +void BKE_mesh_vert_poly_map_create(MeshElemMap **r_map, int **r_mem, + const MPoly *mpoly, const MLoop *mloop, + int totvert, int totpoly, int totloop) +{ + MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * totvert, "vert poly map"); + int *indices, *index_iter; + int i, j; + + indices = index_iter = MEM_mallocN(sizeof(int) * totloop, "vert poly map mem"); + + /* Count number of polys for each vertex */ + for (i = 0; i < totpoly; i++) { + const MPoly *p = &mpoly[i]; + + for (j = 0; j < p->totloop; j++) + map[mloop[p->loopstart + j].v].count++; + } + + /* Assign indices mem */ + for (i = 0; i < totvert; i++) { + map[i].indices = index_iter; + index_iter += map[i].count; + + /* Reset 'count' for use as index in last loop */ + map[i].count = 0; + } + + /* Find the users */ + for (i = 0; i < totpoly; i++) { + const MPoly *p = &mpoly[i]; + + for (j = 0; j < p->totloop; j++) { + int v = mloop[p->loopstart + j].v; + + map[v].indices[map[v].count] = i; + map[v].count++; + } + } + + *r_map = map; + *r_mem = indices; +} + +/* Generates a map where the key is the vertex and the value is a list + * of edges that use that vertex as an endpoint. The lists are allocated + * from one memory pool. */ +void BKE_mesh_vert_edge_map_create(MeshElemMap **r_map, int **r_mem, + const MEdge *medge, int totvert, int totedge) +{ + MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * totvert, "vert-edge map"); + int *indices = MEM_mallocN(sizeof(int) * totedge * 2, "vert-edge map mem"); + int *i_pt = indices; + + int i; + + /* Count number of edges for each vertex */ + for (i = 0; i < totedge; i++) { + map[medge[i].v1].count++; + map[medge[i].v2].count++; + } + + /* Assign indices mem */ + for (i = 0; i < totvert; i++) { + map[i].indices = i_pt; + i_pt += map[i].count; + + /* Reset 'count' for use as index in last loop */ + map[i].count = 0; + } + + /* Find the users */ + for (i = 0; i < totedge; i++) { + const int v[2] = {medge[i].v1, medge[i].v2}; + + map[v[0]].indices[map[v[0]].count] = i; + map[v[1]].indices[map[v[1]].count] = i; + + map[v[0]].count++; + map[v[1]].count++; + } + + *r_map = map; + *r_mem = indices; +} + +void BKE_mesh_edge_poly_map_create(MeshElemMap **r_map, int **r_mem, + const MEdge *UNUSED(medge), const int totedge, + const MPoly *mpoly, const int totpoly, + const MLoop *mloop, const int totloop) +{ + MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * totedge, "edge-poly map"); + int *indices = MEM_mallocN(sizeof(int) * totloop, "edge-poly map mem"); + int *index_step; + const MPoly *mp; + int i; + + /* count face users */ + for (i = 0, mp = mpoly; i < totpoly; mp++, i++) { + const MLoop *ml; + int j = mp->totloop; + for (ml = &mloop[mp->loopstart]; j--; ml++) { + map[ml->e].count++; + } + } + + /* create offsets */ + index_step = indices; + for (i = 0; i < totedge; i++) { + map[i].indices = index_step; + index_step += map[i].count; + + /* re-count, using this as an index below */ + map[i].count = 0; + + } + + /* assign poly-edge users */ + for (i = 0, mp = mpoly; i < totpoly; mp++, i++) { + const MLoop *ml; + int j = mp->totloop; + for (ml = &mloop[mp->loopstart]; j--; ml++) { + MeshElemMap *map_ele = &map[ml->e]; + map_ele->indices[map_ele->count++] = i; + } + } + + *r_map = map; + *r_mem = indices; +} + + +/** \} */ + + +/* -------------------------------------------------------------------- */ + +/** \name NGon Tessellation (NGon/Tessface Conversion) + * \{ */ + +/** + * Convert a triangle or quadrangle of loop/poly data to tessface data + */ +void BKE_mesh_loops_to_mface_corners( + CustomData *fdata, CustomData *ldata, + CustomData *pdata, int lindex[4], int findex, + const int polyindex, + const int mf_len, /* 3 or 4 */ + + /* cache values to avoid lookups every time */ + 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) */ +) +{ + MTFace *texface; + MTexPoly *texpoly; + MCol *mcol; + MLoopCol *mloopcol; + MLoopUV *mloopuv; + int i, j; + + for (i = 0; i < numTex; i++) { + texface = CustomData_get_n(fdata, CD_MTFACE, findex, i); + texpoly = CustomData_get_n(pdata, CD_MTEXPOLY, polyindex, i); + + ME_MTEXFACE_CPY(texface, texpoly); + + for (j = 0; j < mf_len; j++) { + mloopuv = CustomData_get_n(ldata, CD_MLOOPUV, lindex[j], i); + copy_v2_v2(texface->uv[j], mloopuv->uv); + } + } + + for (i = 0; i < numCol; i++) { + mcol = CustomData_get_n(fdata, CD_MCOL, findex, i); + + for (j = 0; j < mf_len; j++) { + mloopcol = CustomData_get_n(ldata, CD_MLOOPCOL, lindex[j], i); + MESH_MLOOPCOL_TO_MCOL(mloopcol, &mcol[j]); + } + } + + if (hasPCol) { + mcol = CustomData_get(fdata, findex, CD_PREVIEW_MCOL); + + for (j = 0; j < mf_len; j++) { + mloopcol = CustomData_get(ldata, lindex[j], CD_PREVIEW_MLOOPCOL); + MESH_MLOOPCOL_TO_MCOL(mloopcol, &mcol[j]); + } + } + + if (hasOrigSpace) { + OrigSpaceFace *of = CustomData_get(fdata, findex, CD_ORIGSPACE); + OrigSpaceLoop *lof; + + for (j = 0; j < mf_len; j++) { + lof = CustomData_get(ldata, lindex[j], CD_ORIGSPACE_MLOOP); + copy_v2_v2(of->uv[j], lof->uv); + } + } +} + +/** + * Recreate tessellation. + * + * use_poly_origindex sets whether or not the tessellation faces' origindex + * layer should point to original poly indices or real poly indices. + * + * use_face_origindex sets the tessellation faces' origindex layer + * to point to the tessellation faces themselves, not the polys. + * + * if both of the above are 0, it'll use the indices of the mpolys of the MPoly + * data in pdata, and ignore the origindex layer altogether. + * + * \return number of tessellation faces. + */ +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) +{ + /* 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 + +#define TESSFACE_SCANFILL (1 << 0) +#define TESSFACE_IS_QUAD (1 << 1) + + const int looptris_tot = poly_to_tri_count(totpoly, totloop); + + 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; + 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); + + 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_mallocN(sizeof(*mface_to_poly_map) * looptris_tot, __func__); + mface = MEM_mallocN(sizeof(*mface) * looptris_tot, __func__); + + mface_index = 0; + mp = mpoly; + for (poly_index = 0; poly_index < totpoly; poly_index++, mp++) { + 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]; \ + /* set loop indices, transformed to vert indices later */ \ + mf->v1 = mp->loopstart + i1; \ + mf->v2 = mp->loopstart + i2; \ + mf->v3 = mp->loopstart + i3; \ + mf->v4 = 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]; \ + /* 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 */ \ + mf->mat_nr = mp->mat_nr; \ + mf->flag = mp->flag; \ + mf->edcode = TESSFACE_IS_QUAD; /* EXCEPTION */ \ + (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 { +#define USE_TESSFACE_CALCNORMAL + + 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__); + } + + 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); + + sf_vert->keyindex = 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; + } + 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 <= mp->totloop - 2); + (void)totfilltri; + + for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next, mf++) { + 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->v4 = 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++; + } + + BLI_scanfill_end_arena(&sf_ctx, sf_arena); + +#undef USE_TESSFACE_CALCNORMAL + } + } + + if (sf_arena) { + BLI_memarena_free(sf_arena); + sf_arena = NULL; + } + + CustomData_free(fdata, totface); + totface = mface_index; + + BLI_assert(totface <= looptris_tot); + + /* not essential but without this we store over-alloc'd memory in the CustomData layers */ + if (LIKELY(looptris_tot != totface)) { + mface = MEM_reallocN(mface, sizeof(*mface) * totface); + mface_to_poly_map = MEM_reallocN(mface_to_poly_map, sizeof(*mface_to_poly_map) * 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, pdata, ldata, totface); + + if (do_face_nor_cpy) { + /* 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]]); + } + } + } + + 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] = mf->v1; + lindex[1] = mf->v2; + lindex[2] = mf->v3; +#ifdef USE_TESSFACE_QUADS + if (mf_len == 4) lindex[3] = mf->v4; +#endif + + /*transform loop indices to vert indices*/ + mf->v1 = mloop[mf->v1].v; + mf->v2 = mloop[mf->v2].v; + mf->v3 = mloop[mf->v3].v; +#ifdef USE_TESSFACE_QUADS + if (mf_len == 4) mf->v4 = mloop[mf->v4].v; +#endif + + 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, +#endif + numTex, numCol, hasPCol, hasOrigSpace); + + +#ifdef USE_TESSFACE_QUADS + test_index_face(mf, fdata, mface_index, mf_len); +#endif + + } + + return totface; + +#undef USE_TESSFACE_SPEEDUP + +} + + +#ifdef USE_BMESH_SAVE_AS_COMPAT + +/** + * This function recreates a tessellation. + * returns number of tessellation faces. + * + * for forwards compat only quad->tri polys to mface, skip ngons. + */ +int BKE_mesh_mpoly_to_mface(struct CustomData *fdata, struct CustomData *ldata, + struct CustomData *pdata, int totface, int UNUSED(totloop), int totpoly) +{ + MLoop *mloop; + + int lindex[4]; + int i; + int k; + + MPoly *mp, *mpoly; + MFace *mface = NULL, *mf; + BLI_array_declare(mface); + + 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); + + mpoly = CustomData_get_layer(pdata, CD_MPOLY); + mloop = CustomData_get_layer(ldata, CD_MLOOP); + + mp = mpoly; + k = 0; + for (i = 0; i < totpoly; i++, mp++) { + if (ELEM(mp->totloop, 3, 4)) { + BLI_array_grow_one(mface); + mf = &mface[k]; + + mf->mat_nr = mp->mat_nr; + mf->flag = mp->flag; + + mf->v1 = mp->loopstart + 0; + mf->v2 = mp->loopstart + 1; + mf->v3 = mp->loopstart + 2; + mf->v4 = (mp->totloop == 4) ? (mp->loopstart + 3) : 0; + + /* abuse edcode for temp storage and clear next loop */ + mf->edcode = (char)mp->totloop; /* only ever 3 or 4 */ + + k++; + } + } + + CustomData_free(fdata, totface); + + totface = k; + + CustomData_add_layer(fdata, CD_MFACE, CD_ASSIGN, mface, totface); + + CustomData_from_bmeshpoly(fdata, pdata, ldata, totface); + + mp = mpoly; + k = 0; + for (i = 0; i < totpoly; i++, mp++) { + if (ELEM(mp->totloop, 3, 4)) { + mf = &mface[k]; + + if (mf->edcode == 3) { + /* sort loop indices to ensure winding is correct */ + /* NO SORT - looks like we can skip this */ + + lindex[0] = mf->v1; + lindex[1] = mf->v2; + lindex[2] = mf->v3; + lindex[3] = 0; /* unused */ + + /* transform loop indices to vert indices */ + mf->v1 = mloop[mf->v1].v; + mf->v2 = mloop[mf->v2].v; + mf->v3 = mloop[mf->v3].v; + + BKE_mesh_loops_to_mface_corners(fdata, ldata, pdata, + lindex, k, i, 3, + numTex, numCol, hasPCol, hasOrigSpace); + test_index_face(mf, fdata, k, 3); + } + else { + /* sort loop indices to ensure winding is correct */ + /* NO SORT - looks like we can skip this */ + + lindex[0] = mf->v1; + lindex[1] = mf->v2; + lindex[2] = mf->v3; + lindex[3] = mf->v4; + + /* transform loop indices to vert indices */ + mf->v1 = mloop[mf->v1].v; + mf->v2 = mloop[mf->v2].v; + mf->v3 = mloop[mf->v3].v; + mf->v4 = mloop[mf->v4].v; + + BKE_mesh_loops_to_mface_corners(fdata, ldata, pdata, + lindex, k, i, 4, + numTex, numCol, hasPCol, hasOrigSpace); + test_index_face(mf, fdata, k, 4); + } + + mf->edcode = 0; + + k++; + } + } + + return k; +} +#endif /* USE_BMESH_SAVE_AS_COMPAT */ + + +static void bm_corners_to_loops_ex(ID *id, CustomData *fdata, CustomData *ldata, CustomData *pdata, + MFace *mface, int totloop, int findex, int loopstart, int numTex, int numCol) +{ + MTFace *texface; + MTexPoly *texpoly; + MCol *mcol; + MLoopCol *mloopcol; + MLoopUV *mloopuv; + MFace *mf; + int i; + + mf = mface + findex; + + for (i = 0; i < numTex; i++) { + texface = CustomData_get_n(fdata, CD_MTFACE, findex, i); + texpoly = CustomData_get_n(pdata, CD_MTEXPOLY, findex, i); + + ME_MTEXFACE_CPY(texpoly, texface); + + mloopuv = CustomData_get_n(ldata, CD_MLOOPUV, loopstart, i); + copy_v2_v2(mloopuv->uv, texface->uv[0]); mloopuv++; + copy_v2_v2(mloopuv->uv, texface->uv[1]); mloopuv++; + copy_v2_v2(mloopuv->uv, texface->uv[2]); mloopuv++; + + if (mf->v4) { + copy_v2_v2(mloopuv->uv, texface->uv[3]); mloopuv++; + } + } + + for (i = 0; i < numCol; i++) { + mloopcol = CustomData_get_n(ldata, CD_MLOOPCOL, loopstart, i); + mcol = CustomData_get_n(fdata, CD_MCOL, findex, i); + + MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[0]); mloopcol++; + MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[1]); mloopcol++; + MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[2]); mloopcol++; + if (mf->v4) { + MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[3]); mloopcol++; + } + } + + if (CustomData_has_layer(fdata, CD_MDISPS)) { + MDisps *ld = CustomData_get(ldata, loopstart, CD_MDISPS); + MDisps *fd = CustomData_get(fdata, findex, CD_MDISPS); + float (*disps)[3] = fd->disps; + int tot = mf->v4 ? 4 : 3; + int side, corners; + + if (CustomData_external_test(fdata, CD_MDISPS)) { + if (id && fdata->external) { + CustomData_external_add(ldata, id, CD_MDISPS, + totloop, fdata->external->filename); + } + } + + corners = multires_mdisp_corners(fd); + + if (corners == 0) { + /* Empty MDisp layers appear in at least one of the sintel.blend files. + * Not sure why this happens, but it seems fine to just ignore them here. + * If (corners == 0) for a non-empty layer though, something went wrong. */ + BLI_assert(fd->totdisp == 0); + } + else { + side = sqrt(fd->totdisp / corners); + + for (i = 0; i < tot; i++, disps += side * side, ld++) { + ld->totdisp = side * side; + ld->level = (int)(logf(side - 1.0f) / (float)M_LN2) + 1; + + if (ld->disps) + MEM_freeN(ld->disps); + + ld->disps = MEM_mallocN(sizeof(float) * 3 * side * side, "converted loop mdisps"); + if (fd->disps) { + memcpy(ld->disps, disps, sizeof(float) * 3 * side * side); + } + else { + memset(ld->disps, 0, sizeof(float) * 3 * side * side); + } + } + } + } +} + + +void BKE_mesh_convert_mfaces_to_mpolys(Mesh *mesh) +{ + BKE_mesh_convert_mfaces_to_mpolys_ex(&mesh->id, &mesh->fdata, &mesh->ldata, &mesh->pdata, + mesh->totedge, mesh->totface, mesh->totloop, mesh->totpoly, + mesh->medge, mesh->mface, + &mesh->totloop, &mesh->totpoly, &mesh->mloop, &mesh->mpoly); + + BKE_mesh_update_customdata_pointers(mesh, true); +} + +/* the same as BKE_mesh_convert_mfaces_to_mpolys but oriented to be used in do_versions from readfile.c + * the difference is how active/render/clone/stencil indices are handled here + * + * normally thay're being set from pdata which totally makes sense for meshes which are already + * converted to bmesh structures, but when loading older files indices shall be updated in other + * way around, so newly added pdata and ldata would have this indices set based on fdata layer + * + * this is normally only needed when reading older files, in all other cases BKE_mesh_convert_mfaces_to_mpolys + * shall be always used + */ +void BKE_mesh_do_versions_convert_mfaces_to_mpolys(Mesh *mesh) +{ + BKE_mesh_convert_mfaces_to_mpolys_ex(&mesh->id, &mesh->fdata, &mesh->ldata, &mesh->pdata, + mesh->totedge, mesh->totface, mesh->totloop, mesh->totpoly, + mesh->medge, mesh->mface, + &mesh->totloop, &mesh->totpoly, &mesh->mloop, &mesh->mpoly); + + CustomData_bmesh_do_versions_update_active_layers(&mesh->fdata, &mesh->pdata, &mesh->ldata); + + BKE_mesh_update_customdata_pointers(mesh, true); +} + +void BKE_mesh_convert_mfaces_to_mpolys_ex(ID *id, CustomData *fdata, CustomData *ldata, CustomData *pdata, + int totedge_i, int totface_i, int totloop_i, int totpoly_i, + MEdge *medge, MFace *mface, + int *totloop_r, int *totpoly_r, + MLoop **mloop_r, MPoly **mpoly_r) +{ + MFace *mf; + MLoop *ml, *mloop; + MPoly *mp, *mpoly; + MEdge *me; + EdgeHash *eh; + int numTex, numCol; + int i, j, totloop, totpoly, *polyindex; + + /* just in case some of these layers are filled in (can happen with python created meshes) */ + CustomData_free(ldata, totloop_i); + CustomData_free(pdata, totpoly_i); + + totpoly = totface_i; + mpoly = MEM_callocN(sizeof(MPoly) * totpoly, "mpoly converted"); + CustomData_add_layer(pdata, CD_MPOLY, CD_ASSIGN, mpoly, totpoly); + + numTex = CustomData_number_of_layers(fdata, CD_MTFACE); + numCol = CustomData_number_of_layers(fdata, CD_MCOL); + + totloop = 0; + mf = mface; + for (i = 0; i < totface_i; i++, mf++) { + totloop += mf->v4 ? 4 : 3; + } + + mloop = MEM_callocN(sizeof(MLoop) * totloop, "mloop converted"); + + CustomData_add_layer(ldata, CD_MLOOP, CD_ASSIGN, mloop, totloop); + + CustomData_to_bmeshpoly(fdata, pdata, ldata, totloop, totpoly); + + if (id) { + /* ensure external data is transferred */ + CustomData_external_read(fdata, id, CD_MASK_MDISPS, totface_i); + } + + eh = BLI_edgehash_new_ex(__func__, totedge_i); + + /* build edge hash */ + me = medge; + for (i = 0; i < totedge_i; i++, me++) { + BLI_edgehash_insert(eh, me->v1, me->v2, SET_INT_IN_POINTER(i)); + + /* unrelated but avoid having the FGON flag enabled, so we can reuse it later for something else */ + me->flag &= ~ME_FGON; + } + + polyindex = CustomData_get_layer(fdata, CD_ORIGINDEX); + + j = 0; /* current loop index */ + ml = mloop; + mf = mface; + mp = mpoly; + for (i = 0; i < totface_i; i++, mf++, mp++) { + mp->loopstart = j; + + mp->totloop = mf->v4 ? 4 : 3; + + mp->mat_nr = mf->mat_nr; + mp->flag = mf->flag; + +# define ML(v1, v2) { \ + ml->v = mf->v1; ml->e = GET_INT_FROM_POINTER(BLI_edgehash_lookup(eh, mf->v1, mf->v2)); ml++; j++; \ + } (void)0 + + ML(v1, v2); + ML(v2, v3); + if (mf->v4) { + ML(v3, v4); + ML(v4, v1); + } + else { + ML(v3, v1); + } + +# undef ML + + bm_corners_to_loops_ex(id, fdata, ldata, pdata, mface, totloop, i, mp->loopstart, numTex, numCol); + + if (polyindex) { + *polyindex = i; + polyindex++; + } + } + + /* note, we don't convert NGons at all, these are not even real ngons, + * they have their own UV's, colors etc - its more an editing feature. */ + + BLI_edgehash_free(eh, NULL); + + *totpoly_r = totpoly; + *totloop_r = totloop; + *mpoly_r = mpoly; + *mloop_r = mloop; +} +/** \} */ + + +/* -------------------------------------------------------------------- */ + +/** \name Mesh Flag Flushing + * \{ */ + +/* update the hide flag for edges and faces from the corresponding + * flag in verts */ +void BKE_mesh_flush_hidden_from_verts_ex(const MVert *mvert, + const MLoop *mloop, + MEdge *medge, const int totedge, + MPoly *mpoly, const int totpoly) +{ + int i, j; + + for (i = 0; i < totedge; i++) { + MEdge *e = &medge[i]; + if (mvert[e->v1].flag & ME_HIDE || + mvert[e->v2].flag & ME_HIDE) + { + e->flag |= ME_HIDE; + } + else { + e->flag &= ~ME_HIDE; + } + } + for (i = 0; i < totpoly; i++) { + MPoly *p = &mpoly[i]; + p->flag &= ~ME_HIDE; + for (j = 0; j < p->totloop; j++) { + if (mvert[mloop[p->loopstart + j].v].flag & ME_HIDE) + p->flag |= ME_HIDE; + } + } +} +void BKE_mesh_flush_hidden_from_verts(Mesh *me) +{ + BKE_mesh_flush_hidden_from_verts_ex(me->mvert, me->mloop, + me->medge, me->totedge, + me->mpoly, me->totpoly); +} + +void BKE_mesh_flush_hidden_from_polys_ex(MVert *mvert, + const MLoop *mloop, + MEdge *medge, const int UNUSED(totedge), + const MPoly *mpoly, const int totpoly) +{ + const MPoly *mp; + int i; + + i = totpoly; + for (mp = mpoly; i--; mp++) { + if (mp->flag & ME_HIDE) { + const MLoop *ml; + int j; + j = mp->totloop; + for (ml = &mloop[mp->loopstart]; j--; ml++) { + mvert[ml->v].flag |= ME_HIDE; + medge[ml->e].flag |= ME_HIDE; + } + } + } + + i = totpoly; + for (mp = mpoly; i--; mp++) { + if ((mp->flag & ME_HIDE) == 0) { + const MLoop *ml; + int j; + j = mp->totloop; + for (ml = &mloop[mp->loopstart]; j--; ml++) { + mvert[ml->v].flag &= ~ME_HIDE; + medge[ml->e].flag &= ~ME_HIDE; + } + } + } +} +void BKE_mesh_flush_hidden_from_polys(Mesh *me) +{ + BKE_mesh_flush_hidden_from_polys_ex(me->mvert, me->mloop, + me->medge, me->totedge, + me->mpoly, me->totpoly); +} + +/** + * simple poly -> vert/edge selection. + */ +void BKE_mesh_flush_select_from_polys_ex(MVert *mvert, const int totvert, + const MLoop *mloop, + MEdge *medge, const int totedge, + const MPoly *mpoly, const int totpoly) +{ + MVert *mv; + MEdge *med; + const MPoly *mp; + int i; + + i = totvert; + for (mv = mvert; i--; mv++) { + mv->flag &= ~SELECT; + } + + i = totedge; + for (med = medge; i--; med++) { + med->flag &= ~SELECT; + } + + i = totpoly; + for (mp = mpoly; i--; mp++) { + /* assume if its selected its not hidden and none of its verts/edges are hidden + * (a common assumption)*/ + if (mp->flag & ME_FACE_SEL) { + const MLoop *ml; + int j; + j = mp->totloop; + for (ml = &mloop[mp->loopstart]; j--; ml++) { + mvert[ml->v].flag |= SELECT; + medge[ml->e].flag |= SELECT; + } + } + } +} +void BKE_mesh_flush_select_from_polys(Mesh *me) +{ + BKE_mesh_flush_select_from_polys_ex(me->mvert, me->totvert, + me->mloop, + me->medge, me->totedge, + me->mpoly, me->totpoly); +} + +void BKE_mesh_flush_select_from_verts_ex(const MVert *mvert, const int UNUSED(totvert), + const MLoop *mloop, + MEdge *medge, const int totedge, + MPoly *mpoly, const int totpoly) +{ + MEdge *med; + MPoly *mp; + int i; + + /* edges */ + i = totedge; + for (med = medge; i--; med++) { + if ((med->flag & ME_HIDE) == 0) { + if ((mvert[med->v1].flag & SELECT) && (mvert[med->v2].flag & SELECT)) { + med->flag |= SELECT; + } + else { + med->flag &= ~SELECT; + } + } + } + + /* polys */ + i = totpoly; + for (mp = mpoly; i--; mp++) { + if ((mp->flag & ME_HIDE) == 0) { + int ok = TRUE; + const MLoop *ml; + int j; + j = mp->totloop; + for (ml = &mloop[mp->loopstart]; j--; ml++) { + if ((mvert[ml->v].flag & SELECT) == 0) { + ok = FALSE; + break; + } + } + + if (ok) { + mp->flag |= ME_FACE_SEL; + } + else { + mp->flag &= ~ME_FACE_SEL; + } + } + } +} +void BKE_mesh_flush_select_from_verts(Mesh *me) +{ + BKE_mesh_flush_select_from_verts_ex(me->mvert, me->totvert, + me->mloop, + me->medge, me->totedge, + me->mpoly, me->totpoly); +} +/** \} */ + + +/* -------------------------------------------------------------------- */ + +/** \name Mesh Smooth Groups + * \{ */ + +/** + * Calculate smooth groups from sharp edges. + * + * \param r_totgroup The total number of groups, 1 or more. + * \return Polygon aligned array of group index values (bitflags if use_bitflags is true), starting at 1. + */ +int *BKE_mesh_calc_smoothgroups(const MEdge *medge, const int totedge, + const MPoly *mpoly, const int totpoly, + const MLoop *mloop, const int totloop, + int *r_totgroup, const bool use_bitflags) +{ + int *poly_groups; + int *poly_stack; + + int poly_prev = 0; + const int temp_poly_group_id = 3; /* Placeholder value. */ + const int poly_group_id_overflowed = 5; /* Group we could not find any available bit, will be reset to 0 at end */ + int tot_group = 0; + bool group_id_overflow = false; + + /* map vars */ + MeshElemMap *edge_poly_map; + int *edge_poly_mem; + + if (totpoly == 0) { + *r_totgroup = 0; + return NULL; + } + + BKE_mesh_edge_poly_map_create(&edge_poly_map, &edge_poly_mem, + medge, totedge, + mpoly, totpoly, + mloop, totloop); + + poly_groups = MEM_callocN(sizeof(int) * totpoly, __func__); + poly_stack = MEM_mallocN(sizeof(int) * totpoly, __func__); + + while (true) { + int poly; + int bit_poly_group_mask = 0; + int poly_group_id; + int ps_curr_idx = 0, ps_end_idx = 0; /* stack indices */ + + for (poly = poly_prev; poly < totpoly; poly++) { + if (poly_groups[poly] == 0) { + break; + } + } + + if (poly == totpoly) { + /* all done */ + break; + } + + poly_group_id = use_bitflags ? temp_poly_group_id : ++tot_group; + + /* start searching from here next time */ + poly_prev = poly + 1; + + poly_groups[poly] = poly_group_id; + poly_stack[ps_end_idx++] = poly; + + while (ps_curr_idx != ps_end_idx) { + const MPoly *mp; + const MLoop *ml; + int j; + + poly = poly_stack[ps_curr_idx++]; + BLI_assert(poly_groups[poly] == poly_group_id); + + mp = &mpoly[poly]; + for (ml = &mloop[mp->loopstart], j = mp->totloop; j--; ml++) { + /* loop over poly users */ + const MeshElemMap *map_ele = &edge_poly_map[ml->e]; + int *p = map_ele->indices; + int i = map_ele->count; + if (!(medge[ml->e].flag & ME_SHARP)) { + for (; i--; p++) { + /* if we meet other non initialized its a bug */ + BLI_assert(ELEM(poly_groups[*p], 0, poly_group_id)); + + if (poly_groups[*p] == 0) { + poly_groups[*p] = poly_group_id; + poly_stack[ps_end_idx++] = *p; + } + } + } + else if (use_bitflags) { + /* Find contiguous smooth groups already assigned, these are the values we can't reuse! */ + for (; i--; p++) { + int bit = poly_groups[*p]; + if (!ELEM3(bit, 0, poly_group_id, poly_group_id_overflowed) && + !(bit_poly_group_mask & bit)) + { + bit_poly_group_mask |= bit; + } + } + } + } + } + /* And now, we have all our poly from current group in poly_stack (from 0 to (ps_end_idx - 1)), as well as + * all smoothgroups bits we can't use in bit_poly_group_mask. + */ + if (use_bitflags) { + int i, *p, gid_bit = 0; + poly_group_id = 1; + + /* Find first bit available! */ + for (; (poly_group_id & bit_poly_group_mask) && (gid_bit < 32); gid_bit++) { + poly_group_id <<= 1; /* will 'overflow' on last possible iteration. */ + } + if (UNLIKELY(gid_bit > 31)) { + /* All bits used in contiguous smooth groups, we can't do much! + * Note: this is *very* unlikely - theoretically, four groups are enough, I don't think we can reach + * this goal with such a simple algo, but I don't think either we'll never need all 32 groups! + */ + printf("Warning, could not find an available id for current smooth group, faces will me marked " + "as out of any smooth group...\n"); + poly_group_id = poly_group_id_overflowed; /* Can't use 0, will have to set them to this value later. */ + group_id_overflow = true; + } + if (gid_bit > tot_group) { + tot_group = gid_bit; + } + /* And assign the final smooth group id to that poly group! */ + for (i = ps_end_idx, p = poly_stack; i--; p++) { + poly_groups[*p] = poly_group_id; + } + } + } + + if (UNLIKELY(group_id_overflow)) { + int i = totpoly, *gid = poly_groups; + for (; i--; gid++) { + if (*gid == poly_group_id_overflowed) { + *gid = 0; + } + } + } + + MEM_freeN(edge_poly_map); + MEM_freeN(edge_poly_mem); + MEM_freeN(poly_stack); + + *r_totgroup = tot_group + 1; + + return poly_groups; +} +/** \} */ + + +/* -------------------------------------------------------------------- */ + +/** \name Mesh Spatial Calculation + * \{ */ + +/** + * This function takes the difference between 2 vertex-coord-arrays + * (\a vert_cos_src, \a vert_cos_dst), + * and applies the difference to \a vert_cos_new relative to \a vert_cos_org. + * + * \param vert_cos_src reference deform source. + * \param vert_cos_dst reference deform destination. + * + * \param vert_cos_org reference for the output location. + * \param vert_cos_new resulting coords. + */ +void BKE_mesh_calc_relative_deform( + const MPoly *mpoly, const int totpoly, + const MLoop *mloop, const int totvert, + + const float (*vert_cos_src)[3], + const float (*vert_cos_dst)[3], + + const float (*vert_cos_org)[3], + float (*vert_cos_new)[3]) +{ + const MPoly *mp; + int i; + + int *vert_accum = MEM_callocN(sizeof(*vert_accum) * totvert, __func__); + + memset(vert_cos_new, '\0', sizeof(*vert_cos_new) * totvert); + + for (i = 0, mp = mpoly; i < totpoly; i++, mp++) { + const MLoop *loopstart = mloop + mp->loopstart; + int j; + + for (j = 0; j < mp->totloop; j++) { + int v_prev = (loopstart + ((mp->totloop + (j - 1)) % mp->totloop))->v; + int v_curr = (loopstart + j)->v; + int v_next = (loopstart + ((j + 1) % mp->totloop))->v; + + float tvec[3]; + + barycentric_transform( + tvec, vert_cos_dst[v_curr], + vert_cos_org[v_prev], vert_cos_org[v_curr], vert_cos_org[v_next], + vert_cos_src[v_prev], vert_cos_src[v_curr], vert_cos_src[v_next] + ); + + add_v3_v3(vert_cos_new[v_curr], tvec); + vert_accum[v_curr] += 1; + } + } + + for (i = 0; i < totvert; i++) { + if (vert_accum[i]) { + mul_v3_fl(vert_cos_new[i], 1.0f / (float)vert_accum[i]); + } + else { + copy_v3_v3(vert_cos_new[i], vert_cos_org[i]); + } + } + + MEM_freeN(vert_accum); +} +/** \} */ diff --git a/source/blender/blenkernel/intern/mesh_validate.c b/source/blender/blenkernel/intern/mesh_validate.c index b5056f75bf9..6ec14add8a9 100644 --- a/source/blender/blenkernel/intern/mesh_validate.c +++ b/source/blender/blenkernel/intern/mesh_validate.c @@ -49,7 +49,12 @@ #include "MEM_guardedalloc.h" -#define SELECT 1 +/* loop v/e are unsigned, so using max uint_32 value as invalid marker... */ +#define INVALID_LOOP_EDGE_MARKER 4294967295u + + +/** \name Internal functions + * \{ */ typedef union { uint32_t verts[2]; @@ -181,6 +186,14 @@ static int search_polyloop_cmp(const void *v1, const void *v2) /* Else, sort on loopstart. */ return sp1->loopstart > sp2->loopstart ? 1 : sp1->loopstart < sp2->loopstart ? -1 : 0; } +/** \} */ + + + +/* -------------------------------------------------------------------- */ + +/** \name Mesh Validation + * \{ */ #define PRINT_MSG(...) (void) \ ( \ @@ -960,6 +973,331 @@ int BKE_mesh_validate(Mesh *me, const int do_verbose) return false; } } +/** \} */ + + + +/* -------------------------------------------------------------------- */ + +/** \name Mesh Stripping (removing invalid data) + * \{ */ + +/* We need to keep this for edge creation (for now?), and some old readfile code... */ +void BKE_mesh_strip_loose_faces(Mesh *me) +{ + MFace *f; + int a, b; + + for (a = b = 0, f = me->mface; a < me->totface; a++, f++) { + if (f->v3) { + if (a != b) { + memcpy(&me->mface[b], f, sizeof(me->mface[b])); + CustomData_copy_data(&me->fdata, &me->fdata, a, b, 1); + } + b++; + } + } + if (a != b) { + CustomData_free_elem(&me->fdata, b, a - b); + me->totface = b; + } +} + +/* Works on both loops and polys! */ +/* Note: It won't try to guess which loops of an invalid poly to remove! + * this is the work of the caller, to mark those loops... + * See e.g. BKE_mesh_validate_arrays(). */ +void BKE_mesh_strip_loose_polysloops(Mesh *me) +{ + MPoly *p; + MLoop *l; + int a, b; + /* New loops idx! */ + int *new_idx = MEM_mallocN(sizeof(int) * me->totloop, __func__); + + for (a = b = 0, p = me->mpoly; a < me->totpoly; a++, p++) { + int invalid = FALSE; + int i = p->loopstart; + int stop = i + p->totloop; + + if (stop > me->totloop || stop < i) { + invalid = TRUE; + } + else { + l = &me->mloop[i]; + i = stop - i; + /* If one of the poly's loops is invalid, the whole poly is invalid! */ + for (; i--; l++) { + if (l->e == INVALID_LOOP_EDGE_MARKER) { + invalid = TRUE; + break; + } + } + } + + if (p->totloop >= 3 && !invalid) { + if (a != b) { + memcpy(&me->mpoly[b], p, sizeof(me->mpoly[b])); + CustomData_copy_data(&me->pdata, &me->pdata, a, b, 1); + } + b++; + } + } + if (a != b) { + CustomData_free_elem(&me->pdata, b, a - b); + me->totpoly = b; + } + + /* And now, get rid of invalid loops. */ + for (a = b = 0, l = me->mloop; a < me->totloop; a++, l++) { + if (l->e != INVALID_LOOP_EDGE_MARKER) { + if (a != b) { + memcpy(&me->mloop[b], l, sizeof(me->mloop[b])); + CustomData_copy_data(&me->ldata, &me->ldata, a, b, 1); + } + new_idx[a] = b; + b++; + } + else { + /* XXX Theoretically, we should be able to not do this, as no remaining poly + * should use any stripped loop. But for security's sake... */ + new_idx[a] = -a; + } + } + if (a != b) { + CustomData_free_elem(&me->ldata, b, a - b); + me->totloop = b; + } + + /* And now, update polys' start loop index. */ + /* Note: At this point, there should never be any poly using a striped loop! */ + for (a = 0, p = me->mpoly; a < me->totpoly; a++, p++) { + p->loopstart = new_idx[p->loopstart]; + } + + MEM_freeN(new_idx); +} + +void BKE_mesh_strip_loose_edges(Mesh *me) +{ + MEdge *e; + MLoop *l; + int a, b; + unsigned int *new_idx = MEM_mallocN(sizeof(int) * me->totedge, __func__); + + for (a = b = 0, e = me->medge; a < me->totedge; a++, e++) { + if (e->v1 != e->v2) { + if (a != b) { + memcpy(&me->medge[b], e, sizeof(me->medge[b])); + CustomData_copy_data(&me->edata, &me->edata, a, b, 1); + } + new_idx[a] = b; + b++; + } + else { + new_idx[a] = INVALID_LOOP_EDGE_MARKER; + } + } + if (a != b) { + CustomData_free_elem(&me->edata, b, a - b); + me->totedge = b; + } + + /* And now, update loops' edge indices. */ + /* XXX We hope no loop was pointing to a striped edge! + * Else, its e will be set to INVALID_LOOP_EDGE_MARKER :/ */ + for (a = 0, l = me->mloop; a < me->totloop; a++, l++) { + l->e = new_idx[l->e]; + } + + MEM_freeN(new_idx); +} +/** \} */ + + + +/* -------------------------------------------------------------------- */ + +/** \name Mesh Edge Calculation + * \{ */ + +/* make edges in a Mesh, for outside of editmode */ + +struct EdgeSort { + unsigned int v1, v2; + char is_loose, is_draw; +}; + +/* edges have to be added with lowest index first for sorting */ +static void to_edgesort(struct EdgeSort *ed, + unsigned int v1, unsigned int v2, + char is_loose, short is_draw) +{ + if (v1 < v2) { + ed->v1 = v1; ed->v2 = v2; + } + else { + ed->v1 = v2; ed->v2 = v1; + } + ed->is_loose = is_loose; + ed->is_draw = is_draw; +} + +static int vergedgesort(const void *v1, const void *v2) +{ + const struct EdgeSort *x1 = v1, *x2 = v2; + + if (x1->v1 > x2->v1) return 1; + else if (x1->v1 < x2->v1) return -1; + else if (x1->v2 > x2->v2) return 1; + else if (x1->v2 < x2->v2) return -1; + + return 0; +} + + +/* Create edges based on known verts and faces, + * this function is only used when loading very old blend files */ + +static void mesh_calc_edges_mdata( + MVert *UNUSED(allvert), MFace *allface, MLoop *allloop, + MPoly *allpoly, int UNUSED(totvert), int totface, int UNUSED(totloop), int totpoly, + const bool use_old, + MEdge **r_medge, int *r_totedge) +{ + MPoly *mpoly; + MFace *mface; + MEdge *medge, *med; + EdgeHash *hash; + struct EdgeSort *edsort, *ed; + int a, totedge = 0; + unsigned int totedge_final = 0; + unsigned int edge_index; + + /* we put all edges in array, sort them, and detect doubles that way */ + + for (a = totface, mface = allface; a > 0; a--, mface++) { + if (mface->v4) totedge += 4; + else if (mface->v3) totedge += 3; + else totedge += 1; + } + + if (totedge == 0) { + /* flag that mesh has edges */ + (*r_medge) = MEM_callocN(0, __func__); + (*r_totedge) = 0; + return; + } + + ed = edsort = MEM_mallocN(totedge * sizeof(struct EdgeSort), "EdgeSort"); + + for (a = totface, mface = allface; a > 0; a--, mface++) { + to_edgesort(ed++, mface->v1, mface->v2, !mface->v3, mface->edcode & ME_V1V2); + if (mface->v4) { + to_edgesort(ed++, mface->v2, mface->v3, 0, mface->edcode & ME_V2V3); + to_edgesort(ed++, mface->v3, mface->v4, 0, mface->edcode & ME_V3V4); + to_edgesort(ed++, mface->v4, mface->v1, 0, mface->edcode & ME_V4V1); + } + else if (mface->v3) { + to_edgesort(ed++, mface->v2, mface->v3, 0, mface->edcode & ME_V2V3); + to_edgesort(ed++, mface->v3, mface->v1, 0, mface->edcode & ME_V3V1); + } + } + + qsort(edsort, totedge, sizeof(struct EdgeSort), vergedgesort); + + /* count final amount */ + for (a = totedge, ed = edsort; a > 1; a--, ed++) { + /* edge is unique when it differs from next edge, or is last */ + if (ed->v1 != (ed + 1)->v1 || ed->v2 != (ed + 1)->v2) totedge_final++; + } + totedge_final++; + + medge = MEM_callocN(sizeof(MEdge) * totedge_final, __func__); + + for (a = totedge, med = medge, ed = edsort; a > 1; a--, ed++) { + /* edge is unique when it differs from next edge, or is last */ + if (ed->v1 != (ed + 1)->v1 || ed->v2 != (ed + 1)->v2) { + med->v1 = ed->v1; + med->v2 = ed->v2; + if (use_old == false || ed->is_draw) med->flag = ME_EDGEDRAW | ME_EDGERENDER; + if (ed->is_loose) med->flag |= ME_LOOSEEDGE; + + /* order is swapped so extruding this edge as a surface wont flip face normals + * with cyclic curves */ + if (ed->v1 + 1 != ed->v2) { + SWAP(unsigned int, med->v1, med->v2); + } + med++; + } + else { + /* equal edge, we merge the drawflag */ + (ed + 1)->is_draw |= ed->is_draw; + } + } + /* last edge */ + med->v1 = ed->v1; + med->v2 = ed->v2; + med->flag = ME_EDGEDRAW; + if (ed->is_loose) med->flag |= ME_LOOSEEDGE; + med->flag |= ME_EDGERENDER; + + MEM_freeN(edsort); + + /* set edge members of mloops */ + hash = BLI_edgehash_new_ex(__func__, totedge_final); + for (edge_index = 0, med = medge; edge_index < totedge_final; edge_index++, med++) { + BLI_edgehash_insert(hash, med->v1, med->v2, SET_UINT_IN_POINTER(edge_index)); + } + + mpoly = allpoly; + for (a = 0; a < totpoly; a++, mpoly++) { + MLoop *ml, *ml_next; + int i = mpoly->totloop; + + ml_next = allloop + mpoly->loopstart; /* first loop */ + ml = &ml_next[i - 1]; /* last loop */ + + while (i-- != 0) { + ml->e = GET_UINT_FROM_POINTER(BLI_edgehash_lookup(hash, ml->v, ml_next->v)); + ml = ml_next; + ml_next++; + } + } + + BLI_edgehash_free(hash, NULL); + + *r_medge = medge; + *r_totedge = totedge_final; +} + +/** + * If the mesh is from a very old blender version, + * convert mface->edcode to edge drawflags + */ +void BKE_mesh_calc_edges_legacy(Mesh *me, const bool use_old) +{ + MEdge *medge; + int totedge = 0; + + mesh_calc_edges_mdata(me->mvert, me->mface, me->mloop, me->mpoly, + me->totvert, me->totface, me->totloop, me->totpoly, + use_old, &medge, &totedge); + + if (totedge == 0) { + /* flag that mesh has edges */ + me->medge = medge; + me->totedge = 0; + return; + } + + medge = CustomData_add_layer(&me->edata, CD_MEDGE, CD_ASSIGN, medge, totedge); + me->medge = medge; + me->totedge = totedge; + + BKE_mesh_strip_loose_faces(me); +} + /** * Calculate edges from polygons @@ -1055,3 +1393,4 @@ void BKE_mesh_calc_edges(Mesh *mesh, bool update, const bool select) BLI_edgehash_free(eh, NULL); } +/** \} */ diff --git a/source/blender/blenkernel/intern/multires.c b/source/blender/blenkernel/intern/multires.c index 32ca3ea6d5a..4519a116946 100644 --- a/source/blender/blenkernel/intern/multires.c +++ b/source/blender/blenkernel/intern/multires.c @@ -1645,6 +1645,11 @@ void multires_free(Multires *mr) } } +typedef struct IndexNode { + struct IndexNode *next, *prev; + int index; +} IndexNode; + static void create_old_vert_face_map(ListBase **map, IndexNode **mem, const MultiresFace *mface, const int totvert, const int totface) { diff --git a/source/blender/blenloader/intern/versioning_legacy.c b/source/blender/blenloader/intern/versioning_legacy.c index dad132f45df..f32215dbf03 100644 --- a/source/blender/blenloader/intern/versioning_legacy.c +++ b/source/blender/blenloader/intern/versioning_legacy.c @@ -2089,7 +2089,7 @@ void blo_do_versions_pre250(FileData *fd, Library *lib, Main *main) for (me = main->mesh.first; me; me = me->id.next) { if (!me->medge) { - BKE_mesh_make_edges(me, 1); /* 1 = use mface->edcode */ + BKE_mesh_calc_edges_legacy(me, true); /* true = use mface->edcode */ } else { BKE_mesh_strip_loose_faces(me); -- cgit v1.2.3