diff options
Diffstat (limited to 'source/blender')
19 files changed, 597 insertions, 503 deletions
diff --git a/source/blender/blenkernel/BKE_mesh.h b/source/blender/blenkernel/BKE_mesh.h index a3d1eb74211..500b3d8cab5 100644 --- a/source/blender/blenkernel/BKE_mesh.h +++ b/source/blender/blenkernel/BKE_mesh.h @@ -201,89 +201,6 @@ 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]); - -/* map from uv vertex to face (for select linked, stitch, uv suburf) */ - -/* UvVertMap */ -#define STD_UV_CONNECT_LIMIT 0.0001f - -typedef struct UvVertMap { - struct UvMapVert **vert; - struct UvMapVert *buf; -} UvVertMap; - -typedef struct UvMapVert { - struct UvMapVert *next; - unsigned int f; - unsigned char tfindex, separate, flag; -} UvMapVert; - -/* UvElement stores per uv information so that we can quickly access information for a uv. - * it is actually an improved UvMapVert, including an island and a direct pointer to the face - * to avoid initializing face arrays */ -typedef struct UvElement { - /* Next UvElement corresponding to same vertex */ - struct UvElement *next; - /* Face the element belongs to */ - struct BMLoop *l; - /* index in loop. */ - unsigned short tfindex; - /* Whether this element is the first of coincident elements */ - unsigned char separate; - /* general use flag */ - unsigned char flag; - /* If generating element map with island sorting, this stores the island index */ - unsigned short island; -} UvElement; - - -/* UvElementMap is a container for UvElements of a mesh. It stores some UvElements belonging to the - * same uv island in sequence and the number of uvs per island so it is possible to access all uvs - * belonging to an island directly by iterating through the buffer. - */ -typedef struct UvElementMap { - /* address UvElements by their vertex */ - struct UvElement **vert; - /* UvElement Store */ - struct UvElement *buf; - /* Total number of UVs in the layer. Useful to know */ - int totalUVs; - /* Number of Islands in the mesh */ - int totalIslands; - /* Stores the starting index in buf where each island begins */ - int *islandIndices; -} UvElementMap; - -/* invalid island index is max short. If any one has the patience - * to make that many islands, he can bite me :p */ -#define INVALID_ISLAND 0xFFFF - -/* Connectivity data */ -typedef struct MeshElemMap { - int *indices; - int count; -} MeshElemMap; - -/* 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_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, @@ -335,13 +252,6 @@ void BKE_mesh_flush_select_from_verts_ex( struct MPoly *mpoly, const int totpoly); void BKE_mesh_flush_select_from_verts(struct Mesh *me); -/* 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, diff --git a/source/blender/blenkernel/BKE_mesh_mapping.h b/source/blender/blenkernel/BKE_mesh_mapping.h new file mode 100644 index 00000000000..3c5377d7bf6 --- /dev/null +++ b/source/blender/blenkernel/BKE_mesh_mapping.h @@ -0,0 +1,128 @@ +/* + * ***** 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. + * + * The Original Code is: all of this file. + * + * Contributor(s): (mar-2001 nzc) + * + * ***** END GPL LICENSE BLOCK ***** + */ +#ifndef __BKE_MESH_MAPPING_H__ +#define __BKE_MESH_MAPPING_H__ + +/** \file BKE_mesh_mapping.h + * \ingroup bke + */ + +struct MPoly; +struct MEdge; +struct MLoop; +struct MLoopUV; + +/* map from uv vertex to face (for select linked, stitch, uv suburf) */ + +/* UvVertMap */ +#define STD_UV_CONNECT_LIMIT 0.0001f + +typedef struct UvVertMap { + struct UvMapVert **vert; + struct UvMapVert *buf; +} UvVertMap; + +typedef struct UvMapVert { + struct UvMapVert *next; + unsigned int f; + unsigned char tfindex, separate, flag; +} UvMapVert; + +/* UvElement stores per uv information so that we can quickly access information for a uv. + * it is actually an improved UvMapVert, including an island and a direct pointer to the face + * to avoid initializing face arrays */ +typedef struct UvElement { + /* Next UvElement corresponding to same vertex */ + struct UvElement *next; + /* Face the element belongs to */ + struct BMLoop *l; + /* index in loop. */ + unsigned short tfindex; + /* Whether this element is the first of coincident elements */ + unsigned char separate; + /* general use flag */ + unsigned char flag; + /* If generating element map with island sorting, this stores the island index */ + unsigned short island; +} UvElement; + + +/* UvElementMap is a container for UvElements of a mesh. It stores some UvElements belonging to the + * same uv island in sequence and the number of uvs per island so it is possible to access all uvs + * belonging to an island directly by iterating through the buffer. + */ +typedef struct UvElementMap { + /* address UvElements by their vertex */ + struct UvElement **vert; + /* UvElement Store */ + struct UvElement *buf; + /* Total number of UVs in the layer. Useful to know */ + int totalUVs; + /* Number of Islands in the mesh */ + int totalIslands; + /* Stores the starting index in buf where each island begins */ + int *islandIndices; +} UvElementMap; + +/* invalid island index is max short. If any one has the patience + * to make that many islands, he can bite me :p */ +#define INVALID_ISLAND 0xFFFF + +/* Connectivity data */ +typedef struct MeshElemMap { + int *indices; + int count; +} MeshElemMap; + +/* 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_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); + +/* 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); + +#endif /* __BKE_MESH_MAPPING_H__ */ diff --git a/source/blender/blenkernel/CMakeLists.txt b/source/blender/blenkernel/CMakeLists.txt index 437956f2297..c4c44271873 100644 --- a/source/blender/blenkernel/CMakeLists.txt +++ b/source/blender/blenkernel/CMakeLists.txt @@ -115,6 +115,7 @@ set(SRC intern/mball.c intern/mesh.c intern/mesh_evaluate.c + intern/mesh_mapping.c intern/mesh_validate.c intern/modifier.c intern/modifiers_bmesh.c @@ -212,6 +213,7 @@ set(SRC BKE_material.h BKE_mball.h BKE_mesh.h + BKE_mesh_mapping.h BKE_modifier.h BKE_movieclip.h BKE_multires.h diff --git a/source/blender/blenkernel/intern/cdderivedmesh.c b/source/blender/blenkernel/intern/cdderivedmesh.c index d57d9180697..e95847b9de4 100644 --- a/source/blender/blenkernel/intern/cdderivedmesh.c +++ b/source/blender/blenkernel/intern/cdderivedmesh.c @@ -48,6 +48,7 @@ #include "BKE_cdderivedmesh.h" #include "BKE_global.h" #include "BKE_mesh.h" +#include "BKE_mesh_mapping.h" #include "BKE_paint.h" #include "BKE_editmesh.h" #include "BKE_curve.h" diff --git a/source/blender/blenkernel/intern/mesh_evaluate.c b/source/blender/blenkernel/intern/mesh_evaluate.c index 0a85d2bfa06..24362c1a817 100644 --- a/source/blender/blenkernel/intern/mesh_evaluate.c +++ b/source/blender/blenkernel/intern/mesh_evaluate.c @@ -942,259 +942,6 @@ bool BKE_mesh_center_centroid(Mesh *me, float cent[3]) /* -------------------------------------------------------------------- */ -/** \name Mesh Connectivity Mapping - * \{ */ - - -/* ngon version wip, based on BM_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) * (size_t)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 = (unsigned char)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) * (size_t)totvert, "vert poly map"); - int *indices, *index_iter; - int i, j; - - indices = index_iter = MEM_mallocN(sizeof(int) * (size_t)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++) { - unsigned 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) * (size_t)totvert, "vert-edge map"); - int *indices = MEM_mallocN(sizeof(int[2]) * (size_t)totedge, "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 unsigned 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) * (size_t)totedge, "edge-poly map"); - int *indices = MEM_mallocN(sizeof(int) * (size_t)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) * \{ */ @@ -2070,163 +1817,6 @@ void BKE_mesh_flush_select_from_verts(Mesh *me) } /** \} */ - -/* -------------------------------------------------------------------- */ - -/** \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) * (size_t)totpoly, __func__); - poly_stack = MEM_mallocN(sizeof(int) * (size_t)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 diff --git a/source/blender/blenkernel/intern/mesh_mapping.c b/source/blender/blenkernel/intern/mesh_mapping.c new file mode 100644 index 00000000000..cbf4b4906f5 --- /dev/null +++ b/source/blender/blenkernel/intern/mesh_mapping.c @@ -0,0 +1,450 @@ +/* + * ***** 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. + * + * Contributor(s): Blender Foundation + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/blenkernel/intern/mesh_mapping.c + * \ingroup bke + * + * Functions for accessing mesh connectivity data. + * eg: polys connected to verts, UV's connected to verts. + */ + +#include "MEM_guardedalloc.h" + +#include "DNA_mesh_types.h" +#include "DNA_meshdata_types.h" + +#include "BLI_utildefines.h" +#include "BLI_math.h" + +#include "BKE_mesh_mapping.h" + +#include "BLI_strict_flags.h" + + +/* -------------------------------------------------------------------- */ + +/** \name Mesh Connectivity Mapping + * \{ */ + + +/* ngon version wip, based on BM_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) * (size_t)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 = (unsigned char)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) * (size_t)totvert, "vert poly map"); + int *indices, *index_iter; + int i, j; + + indices = index_iter = MEM_mallocN(sizeof(int) * (size_t)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++) { + unsigned 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) * (size_t)totvert, "vert-edge map"); + int *indices = MEM_mallocN(sizeof(int[2]) * (size_t)totedge, "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 unsigned 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) * (size_t)totedge, "edge-poly map"); + int *indices = MEM_mallocN(sizeof(int) * (size_t)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 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) * (size_t)totpoly, __func__); + poly_stack = MEM_mallocN(sizeof(int) * (size_t)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; +} +/** \} */ diff --git a/source/blender/blenkernel/intern/multires.c b/source/blender/blenkernel/intern/multires.c index 7ef2505f4e9..81708133bf3 100644 --- a/source/blender/blenkernel/intern/multires.c +++ b/source/blender/blenkernel/intern/multires.c @@ -49,6 +49,7 @@ #include "BKE_ccg.h" #include "BKE_cdderivedmesh.h" #include "BKE_mesh.h" +#include "BKE_mesh_mapping.h" #include "BKE_modifier.h" #include "BKE_multires.h" #include "BKE_paint.h" diff --git a/source/blender/blenkernel/intern/subsurf_ccg.c b/source/blender/blenkernel/intern/subsurf_ccg.c index 900d92d1637..e94db6f637c 100644 --- a/source/blender/blenkernel/intern/subsurf_ccg.c +++ b/source/blender/blenkernel/intern/subsurf_ccg.c @@ -59,6 +59,7 @@ #include "BKE_cdderivedmesh.h" #include "BKE_global.h" #include "BKE_mesh.h" +#include "BKE_mesh_mapping.h" #include "BKE_modifier.h" #include "BKE_multires.h" #include "BKE_paint.h" diff --git a/source/blender/editors/mesh/editmesh_utils.c b/source/blender/editors/mesh/editmesh_utils.c index 697876a3877..4982ce3571c 100644 --- a/source/blender/editors/mesh/editmesh_utils.c +++ b/source/blender/editors/mesh/editmesh_utils.c @@ -42,6 +42,7 @@ #include "BKE_depsgraph.h" #include "BKE_key.h" #include "BKE_mesh.h" +#include "BKE_mesh_mapping.h" #include "BKE_report.h" #include "BKE_editmesh.h" #include "BKE_editmesh_bvh.h" diff --git a/source/blender/editors/object/object_modifier.c b/source/blender/editors/object/object_modifier.c index d4c64552b38..16b54b4f4b4 100644 --- a/source/blender/editors/object/object_modifier.c +++ b/source/blender/editors/object/object_modifier.c @@ -63,6 +63,7 @@ #include "BKE_lattice.h" #include "BKE_main.h" #include "BKE_mesh.h" +#include "BKE_mesh_mapping.h" #include "BKE_modifier.h" #include "BKE_multires.h" #include "BKE_report.h" diff --git a/source/blender/editors/object/object_vgroup.c b/source/blender/editors/object/object_vgroup.c index f6761aab42c..a15e9130907 100644 --- a/source/blender/editors/object/object_vgroup.c +++ b/source/blender/editors/object/object_vgroup.c @@ -62,6 +62,7 @@ #include "BKE_depsgraph.h" #include "BKE_global.h" #include "BKE_mesh.h" +#include "BKE_mesh_mapping.h" #include "BKE_editmesh.h" #include "BKE_report.h" #include "BKE_DerivedMesh.h" diff --git a/source/blender/editors/sculpt_paint/sculpt.c b/source/blender/editors/sculpt_paint/sculpt.c index fa938eca487..c0f0fcf8230 100644 --- a/source/blender/editors/sculpt_paint/sculpt.c +++ b/source/blender/editors/sculpt_paint/sculpt.c @@ -62,6 +62,7 @@ #include "BKE_key.h" #include "BKE_library.h" #include "BKE_mesh.h" +#include "BKE_mesh_mapping.h" #include "BKE_modifier.h" #include "BKE_multires.h" #include "BKE_paint.h" diff --git a/source/blender/editors/sculpt_paint/sculpt_uv.c b/source/blender/editors/sculpt_paint/sculpt_uv.c index 626df03a5d4..6d5025f1a22 100644 --- a/source/blender/editors/sculpt_paint/sculpt_uv.c +++ b/source/blender/editors/sculpt_paint/sculpt_uv.c @@ -50,6 +50,7 @@ #include "BKE_main.h" #include "BKE_depsgraph.h" #include "BKE_mesh.h" +#include "BKE_mesh_mapping.h" #include "BKE_customdata.h" #include "BKE_editmesh.h" diff --git a/source/blender/editors/transform/transform_conversions.c b/source/blender/editors/transform/transform_conversions.c index c41b4deca31..4ee20ba44fb 100644 --- a/source/blender/editors/transform/transform_conversions.c +++ b/source/blender/editors/transform/transform_conversions.c @@ -78,6 +78,7 @@ #include "BKE_key.h" #include "BKE_main.h" #include "BKE_mesh.h" +#include "BKE_mesh_mapping.h" #include "BKE_modifier.h" #include "BKE_movieclip.h" #include "BKE_nla.h" diff --git a/source/blender/editors/uvedit/uvedit_ops.c b/source/blender/editors/uvedit/uvedit_ops.c index afe26ed1c4e..529a815b893 100644 --- a/source/blender/editors/uvedit/uvedit_ops.c +++ b/source/blender/editors/uvedit/uvedit_ops.c @@ -61,6 +61,7 @@ #include "BKE_main.h" #include "BKE_material.h" #include "BKE_mesh.h" +#include "BKE_mesh_mapping.h" #include "BKE_node.h" #include "BKE_report.h" #include "BKE_scene.h" diff --git a/source/blender/editors/uvedit/uvedit_smart_stitch.c b/source/blender/editors/uvedit/uvedit_smart_stitch.c index 28e28238ca9..60747450661 100644 --- a/source/blender/editors/uvedit/uvedit_smart_stitch.c +++ b/source/blender/editors/uvedit/uvedit_smart_stitch.c @@ -53,6 +53,7 @@ #include "BKE_customdata.h" #include "BKE_depsgraph.h" #include "BKE_mesh.h" +#include "BKE_mesh_mapping.h" #include "BKE_editmesh.h" #include "ED_mesh.h" diff --git a/source/blender/makesrna/intern/rna_mesh_api.c b/source/blender/makesrna/intern/rna_mesh_api.c index a25f56f2259..fe4226839d0 100644 --- a/source/blender/makesrna/intern/rna_mesh_api.c +++ b/source/blender/makesrna/intern/rna_mesh_api.c @@ -39,15 +39,16 @@ #include "BLI_utildefines.h" #include "BLI_math.h" -#include "BKE_mesh.h" -#include "ED_mesh.h" - #include "rna_internal.h" /* own include */ #ifdef RNA_RUNTIME #include "DNA_mesh_types.h" +#include "BKE_mesh.h" +#include "BKE_mesh_mapping.h" +#include "ED_mesh.h" + static const char *rna_Mesh_unit_test_compare(struct Mesh *mesh, struct Mesh *mesh2) { const char *ret = BKE_mesh_cmp(mesh, mesh2, FLT_EPSILON * 60); diff --git a/source/blender/modifiers/intern/MOD_laplaciandeform.c b/source/blender/modifiers/intern/MOD_laplaciandeform.c index df64bf63ff7..5040ffbe916 100644 --- a/source/blender/modifiers/intern/MOD_laplaciandeform.c +++ b/source/blender/modifiers/intern/MOD_laplaciandeform.c @@ -35,6 +35,7 @@ #include "MEM_guardedalloc.h" #include "BKE_mesh.h" +#include "BKE_mesh_mapping.h" #include "BKE_cdderivedmesh.h" #include "BKE_particle.h" #include "BKE_deform.h" diff --git a/source/blender/modifiers/intern/MOD_skin.c b/source/blender/modifiers/intern/MOD_skin.c index 09e0ac966d0..90c37459d31 100644 --- a/source/blender/modifiers/intern/MOD_skin.c +++ b/source/blender/modifiers/intern/MOD_skin.c @@ -76,6 +76,7 @@ #include "BKE_deform.h" #include "BKE_DerivedMesh.h" #include "BKE_mesh.h" +#include "BKE_mesh_mapping.h" #include "BKE_modifier.h" #include "bmesh.h" |