Blender  V3.3
editors/mesh/mesh_mirror.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
9 #include "MEM_guardedalloc.h"
10 
11 #include "BLI_math.h"
12 
13 #include "DNA_mesh_types.h"
14 #include "DNA_meshdata_types.h"
15 #include "DNA_object_types.h"
16 
17 #include "BKE_editmesh.h"
18 #include "BKE_mesh.h"
19 #include "BLI_kdtree.h"
20 
21 #include "ED_mesh.h"
22 
23 /* -------------------------------------------------------------------- */
27 #define KD_THRESH 0.00002f
28 
29 static struct {
30  void *tree;
32 
34 {
35  Mesh *me = ob->data;
36  const bool use_em = (!me_eval && em && me->edit_mesh == em);
37  const int totvert = use_em ? em->bm->totvert : me_eval ? me_eval->totvert : me->totvert;
38 
39  if (MirrKdStore.tree) { /* happens when entering this call without ending it */
41  }
42 
43  MirrKdStore.tree = BLI_kdtree_3d_new(totvert);
44 
45  if (use_em) {
46  BMVert *eve;
47  BMIter iter;
48  int i;
49 
50  /* this needs to be valid for index lookups later (callers need) */
52 
53  BM_ITER_MESH_INDEX (eve, &iter, em->bm, BM_VERTS_OF_MESH, i) {
54  BLI_kdtree_3d_insert(MirrKdStore.tree, i, eve->co);
55  }
56  }
57  else {
58  MVert *mvert = me_eval ? me_eval->mvert : me->mvert;
59  int i;
60 
61  for (i = 0; i < totvert; i++, mvert++) {
62  BLI_kdtree_3d_insert(MirrKdStore.tree, i, mvert->co);
63  }
64  }
65 
66  BLI_kdtree_3d_balance(MirrKdStore.tree);
67 }
68 
70  BMEditMesh *em,
71  Mesh *me_eval,
72  const float co[3])
73 {
74  if (MirrKdStore.tree == NULL) {
75  ED_mesh_mirror_spatial_table_begin(ob, em, me_eval);
76  }
77 
78  if (MirrKdStore.tree) {
79  KDTreeNearest_3d nearest;
80  const int i = BLI_kdtree_3d_find_nearest(MirrKdStore.tree, co, &nearest);
81 
82  if (i != -1) {
83  if (nearest.dist < KD_THRESH) {
84  return i;
85  }
86  }
87  }
88  return -1;
89 }
90 
92 {
93  /* TODO: store this in object/object-data (keep unused argument for now). */
94  if (MirrKdStore.tree) {
95  BLI_kdtree_3d_free(MirrKdStore.tree);
96  MirrKdStore.tree = NULL;
97  }
98 }
99 
102 /* -------------------------------------------------------------------- */
107 
108 typedef struct MirrTopoVert_t {
110  int v_index;
112 
113 static int mirrtopo_hash_sort(const void *l1, const void *l2)
114 {
116  return 1;
117  }
119  return -1;
120  }
121  return 0;
122 }
123 
124 static int mirrtopo_vert_sort(const void *v1, const void *v2)
125 {
126  if (((MirrTopoVert_t *)v1)->hash > ((MirrTopoVert_t *)v2)->hash) {
127  return 1;
128  }
129  if (((MirrTopoVert_t *)v1)->hash < ((MirrTopoVert_t *)v2)->hash) {
130  return -1;
131  }
132  return 0;
133 }
134 
136 {
137  const bool is_editmode = em != NULL;
138  int totvert;
139  int totedge;
140 
141  if (em) {
142  totvert = em->bm->totvert;
143  totedge = em->bm->totedge;
144  }
145  else {
146  totvert = me->totvert;
147  totedge = me->totedge;
148  }
149 
150  if ((mesh_topo_store->index_lookup == NULL) ||
151  (mesh_topo_store->prev_is_editmode != is_editmode) ||
152  (totvert != mesh_topo_store->prev_vert_tot) || (totedge != mesh_topo_store->prev_edge_tot)) {
153  return true;
154  }
155  return false;
156 }
157 
159  Mesh *me,
161  const bool skip_em_vert_array_init)
162 {
163  if (em) {
164  BLI_assert(me == NULL);
165  }
166  const bool is_editmode = (em != NULL);
167  MEdge *medge = NULL, *med;
168 
169  /* Edit-mode variables. */
170  BMEdge *eed;
171  BMIter iter;
172 
173  int a, last;
174  int totvert, totedge;
175  int tot_unique = -1, tot_unique_prev = -1;
176  int tot_unique_edges = 0, tot_unique_edges_prev;
177 
178  MirrTopoHash_t *topo_hash = NULL;
179  MirrTopoHash_t *topo_hash_prev = NULL;
180  MirrTopoVert_t *topo_pairs;
181  MirrTopoHash_t topo_pass = 1;
182 
183  intptr_t *index_lookup; /* direct access to mesh_topo_store->index_lookup */
184 
185  /* reallocate if needed */
187 
188  mesh_topo_store->prev_is_editmode = is_editmode;
189 
190  if (em) {
192 
193  totvert = em->bm->totvert;
194  }
195  else {
196  totvert = me->totvert;
197  }
198 
199  topo_hash = MEM_callocN(totvert * sizeof(MirrTopoHash_t), "TopoMirr");
200 
201  /* Initialize the vert-edge-user counts used to detect unique topology */
202  if (em) {
203  totedge = em->bm->totedge;
204 
205  BM_ITER_MESH (eed, &iter, em->bm, BM_EDGES_OF_MESH) {
206  const int i1 = BM_elem_index_get(eed->v1), i2 = BM_elem_index_get(eed->v2);
207  topo_hash[i1]++;
208  topo_hash[i2]++;
209  }
210  }
211  else {
212  totedge = me->totedge;
213  medge = me->medge;
214 
215  for (a = 0, med = medge; a < totedge; a++, med++) {
216  const uint i1 = med->v1, i2 = med->v2;
217  topo_hash[i1]++;
218  topo_hash[i2]++;
219  }
220  }
221 
222  topo_hash_prev = MEM_dupallocN(topo_hash);
223 
224  tot_unique_prev = -1;
225  tot_unique_edges_prev = -1;
226  while (1) {
227  /* use the number of edges per vert to give verts unique topology IDs */
228 
229  tot_unique_edges = 0;
230 
231  /* This can make really big numbers, wrapping around here is fine */
232  if (em) {
233  BM_ITER_MESH (eed, &iter, em->bm, BM_EDGES_OF_MESH) {
234  const int i1 = BM_elem_index_get(eed->v1), i2 = BM_elem_index_get(eed->v2);
235  topo_hash[i1] += topo_hash_prev[i2] * topo_pass;
236  topo_hash[i2] += topo_hash_prev[i1] * topo_pass;
237  tot_unique_edges += (topo_hash[i1] != topo_hash[i2]);
238  }
239  }
240  else {
241  for (a = 0, med = medge; a < totedge; a++, med++) {
242  const uint i1 = med->v1, i2 = med->v2;
243  topo_hash[i1] += topo_hash_prev[i2] * topo_pass;
244  topo_hash[i2] += topo_hash_prev[i1] * topo_pass;
245  tot_unique_edges += (topo_hash[i1] != topo_hash[i2]);
246  }
247  }
248  memcpy(topo_hash_prev, topo_hash, sizeof(MirrTopoHash_t) * totvert);
249 
250  /* sort so we can count unique values */
251  qsort(topo_hash_prev, totvert, sizeof(MirrTopoHash_t), mirrtopo_hash_sort);
252 
253  tot_unique = 1; /* account for skipping the first value */
254  for (a = 1; a < totvert; a++) {
255  if (topo_hash_prev[a - 1] != topo_hash_prev[a]) {
256  tot_unique++;
257  }
258  }
259 
260  if ((tot_unique <= tot_unique_prev) && (tot_unique_edges <= tot_unique_edges_prev)) {
261  /* Finish searching for unique values when 1 loop doesn't give a
262  * higher number of unique values compared to the previous loop. */
263  break;
264  }
265  tot_unique_prev = tot_unique;
266  tot_unique_edges_prev = tot_unique_edges;
267  /* Copy the hash calculated this iteration, so we can use them next time */
268  memcpy(topo_hash_prev, topo_hash, sizeof(MirrTopoHash_t) * totvert);
269 
270  topo_pass++;
271  }
272 
273  /* Hash/Index pairs are needed for sorting to find index pairs */
274  topo_pairs = MEM_callocN(sizeof(MirrTopoVert_t) * totvert, "MirrTopoPairs");
275 
276  /* since we are looping through verts, initialize these values here too */
277  index_lookup = MEM_mallocN(totvert * sizeof(*index_lookup), "mesh_topo_lookup");
278 
279  if (em) {
280  if (skip_em_vert_array_init == false) {
282  }
283  }
284 
285  for (a = 0; a < totvert; a++) {
286  topo_pairs[a].hash = topo_hash[a];
287  topo_pairs[a].v_index = a;
288 
289  /* initialize lookup */
290  index_lookup[a] = -1;
291  }
292 
293  qsort(topo_pairs, totvert, sizeof(MirrTopoVert_t), mirrtopo_vert_sort);
294 
295  last = 0;
296 
297  /* Get the pairs out of the sorted hashes.
298  * NOTE: `totvert + 1` means we can use the previous 2,
299  * but you can't ever access the last 'a' index of #MirrTopoPairs. */
300  if (em) {
301  BMVert **vtable = em->bm->vtable;
302  for (a = 1; a <= totvert; a++) {
303  // printf("I %d %ld %d\n",
304  // (a - last), MirrTopoPairs[a].hash, MirrTopoPairs[a].v_index);
305  if ((a == totvert) || (topo_pairs[a - 1].hash != topo_pairs[a].hash)) {
306  const int match_count = a - last;
307  if (match_count == 2) {
308  const int j = topo_pairs[a - 1].v_index, k = topo_pairs[a - 2].v_index;
309  index_lookup[j] = (intptr_t)vtable[k];
310  index_lookup[k] = (intptr_t)vtable[j];
311  }
312  else if (match_count == 1) {
313  /* Center vertex. */
314  const int j = topo_pairs[a - 1].v_index;
315  index_lookup[j] = (intptr_t)vtable[j];
316  }
317  last = a;
318  }
319  }
320  }
321  else {
322  /* same as above, for mesh */
323  for (a = 1; a <= totvert; a++) {
324  if ((a == totvert) || (topo_pairs[a - 1].hash != topo_pairs[a].hash)) {
325  const int match_count = a - last;
326  if (match_count == 2) {
327  const int j = topo_pairs[a - 1].v_index, k = topo_pairs[a - 2].v_index;
328  index_lookup[j] = k;
329  index_lookup[k] = j;
330  }
331  else if (match_count == 1) {
332  /* Center vertex. */
333  const int j = topo_pairs[a - 1].v_index;
334  index_lookup[j] = j;
335  }
336  last = a;
337  }
338  }
339  }
340 
341  MEM_freeN(topo_pairs);
342  topo_pairs = NULL;
343 
344  MEM_freeN(topo_hash);
345  MEM_freeN(topo_hash_prev);
346 
347  mesh_topo_store->index_lookup = index_lookup;
348  mesh_topo_store->prev_vert_tot = totvert;
349  mesh_topo_store->prev_edge_tot = totedge;
350 }
351 
353 {
357 }
358 
#define BLI_assert(a)
Definition: BLI_assert.h:46
A KD-tree for nearest neighbor search.
unsigned int uint
Definition: BLI_sys_types.h:67
#define UNUSED(x)
Object is a sort of wrapper for general info.
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint i1
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
Read Guarded memory(de)allocation.
#define MEM_SAFE_FREE(v)
@ BM_VERT
Definition: bmesh_class.h:383
#define BM_elem_index_get(ele)
Definition: bmesh_inline.h:110
#define BM_ITER_MESH(ele, iter, bm, itype)
#define BM_ITER_MESH_INDEX(ele, iter, bm, itype, indexvar)
@ BM_EDGES_OF_MESH
@ BM_VERTS_OF_MESH
void BM_mesh_elem_table_ensure(BMesh *bm, const char htype)
Definition: bmesh_mesh.cc:558
void BM_mesh_elem_index_ensure(BMesh *bm, const char htype)
Definition: bmesh_mesh.cc:446
ATTR_WARN_UNUSED_RESULT const BMVert * v2
int ED_mesh_mirror_spatial_table_lookup(Object *ob, BMEditMesh *em, Mesh *me_eval, const float co[3])
void ED_mesh_mirror_spatial_table_begin(Object *ob, BMEditMesh *em, Mesh *me_eval)
static int mirrtopo_vert_sort(const void *v1, const void *v2)
bool ED_mesh_mirrtopo_recalc_check(BMEditMesh *em, Mesh *me, MirrTopoStore_t *mesh_topo_store)
static int mirrtopo_hash_sort(const void *l1, const void *l2)
#define KD_THRESH
void ED_mesh_mirrtopo_free(MirrTopoStore_t *mesh_topo_store)
static struct @484 MirrKdStore
struct MirrTopoVert_t MirrTopoVert_t
void ED_mesh_mirror_spatial_table_end(Object *UNUSED(ob))
void * tree
void ED_mesh_mirrtopo_init(BMEditMesh *em, Mesh *me, MirrTopoStore_t *mesh_topo_store, const bool skip_em_vert_array_init)
uint MirrTopoHash_t
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_dupallocN)(const void *vmemh)
Definition: mallocn.c:28
void *(* MEM_callocN)(size_t len, const char *str)
Definition: mallocn.c:31
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
static MirrTopoStore_t mesh_topo_store
Definition: meshtools.cc:838
static unsigned a[3]
Definition: RandGen.cpp:78
#define hash
Definition: noise.c:153
_W64 int intptr_t
Definition: stdint.h:118
BMVert * v1
Definition: bmesh_class.h:122
BMVert * v2
Definition: bmesh_class.h:122
struct BMesh * bm
Definition: BKE_editmesh.h:40
float co[3]
Definition: bmesh_class.h:87
int totvert
Definition: bmesh_class.h:297
int totedge
Definition: bmesh_class.h:297
BMVert ** vtable
Definition: bmesh_class.h:321
float co[3]
struct MEdge * medge
struct BMEditMesh * edit_mesh
struct MVert * mvert
int totedge
int totvert
intptr_t * index_lookup
Definition: ED_mesh.h:432
int prev_edge_tot
Definition: ED_mesh.h:434
int prev_vert_tot
Definition: ED_mesh.h:433
bool prev_is_editmode
Definition: ED_mesh.h:435
void * data