Blender V5.3
editors/mesh/mesh_mirror.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
10
11#include "MEM_guardedalloc.h"
12
13#include "DNA_object_types.h"
14
15#include "BKE_editmesh.hh"
16#include "BKE_mesh.hh"
17#include "BKE_mesh_types.hh"
18
19#include "BLI_kdtree.hh"
20
21#include "ED_mesh.hh"
22
23namespace blender {
24
25/* -------------------------------------------------------------------- */
28
29#define KD_THRESH 0.00002f
30
31static struct {
33} MirrKdStore = {nullptr};
34
36{
37 Mesh *mesh = id_cast<Mesh *>(ob->data);
39 const bool use_em = (!mesh_eval && em);
40 BMesh *bm = use_em ? BKE_editmesh_bmesh_get_for_write(ob) : nullptr;
41 const int totvert = use_em ? bm->totvert : mesh_eval ? mesh_eval->verts_num : mesh->verts_num;
42
43 if (MirrKdStore.tree) { /* happens when entering this call without ending it */
45 }
46
47 MirrKdStore.tree = kdtree_new<float3>(totvert);
48
49 if (use_em) {
50 BMVert *eve;
51 BMIter iter;
52 int i;
53
54 /* this needs to be valid for index lookups later (callers need) */
56
57 BM_ITER_MESH_INDEX (eve, &iter, bm, BM_VERTS_OF_MESH, i) {
59 }
60 }
61 else {
62 const Span<float3> positions = mesh_eval ? mesh_eval->vert_positions() :
63 mesh->vert_positions();
64 for (int i = 0; i < totvert; i++) {
65 kdtree_insert<float3>(MirrKdStore.tree, i, positions[i]);
66 }
67 }
68
70}
71
72int ED_mesh_mirror_spatial_table_lookup(Object *ob, Mesh *mesh_eval, const float co[3])
73{
74 if (MirrKdStore.tree == nullptr) {
76 }
77
78 if (MirrKdStore.tree) {
80 const int i = kdtree_find_nearest<float3>(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) {
96 MirrKdStore.tree = nullptr;
97 }
98}
99
101
102/* -------------------------------------------------------------------- */
105
107
112
113static int mirrtopo_hash_sort(const void *l1, const void *l2)
114{
116 return 1;
117 }
119 return -1;
120 }
121 return 0;
122}
123
124static int mirrtopo_vert_sort(const void *v1, const void *v2)
125{
126 if ((static_cast<MirrTopoVert_t *>(const_cast<void *>(v1)))->hash >
127 (static_cast<MirrTopoVert_t *>(const_cast<void *>(v2)))->hash)
128 {
129 return 1;
130 }
131 if ((static_cast<MirrTopoVert_t *>(const_cast<void *>(v1)))->hash <
132 (static_cast<MirrTopoVert_t *>(const_cast<void *>(v2)))->hash)
133 {
134 return -1;
135 }
136 return 0;
137}
138
140{
141 const bool is_editmode = bm != nullptr;
142 int totvert;
143 int totedge;
144
145 if (bm) {
146 totvert = bm->totvert;
147 totedge = bm->totedge;
148 }
149 else {
150 totvert = mesh->verts_num;
151 totedge = mesh->edges_num;
152 }
153
154 if ((mesh_topo_store->index_lookup == nullptr) ||
155 (mesh_topo_store->prev_is_editmode != is_editmode) ||
156 (totvert != mesh_topo_store->prev_vert_tot) || (totedge != mesh_topo_store->prev_edge_tot))
157 {
158 return true;
159 }
160 return false;
161}
162
164 Mesh *mesh,
165 MirrTopoStore_t *mesh_topo_store,
166 const bool skip_bm_vert_array_init)
167{
168 if (bm) {
169 BLI_assert(mesh == nullptr);
170 }
171 const bool is_editmode = (bm != nullptr);
172
173 /* Edit-mode variables. */
174 BMEdge *eed;
175 BMIter iter;
176
177 int a, last;
178 int totvert, totedge;
179 int tot_unique = -1, tot_unique_prev = -1;
180 int tot_unique_edges = 0, tot_unique_edges_prev;
181
182 MirrTopoHash_t topo_pass = 1;
183
184 /* reallocate if needed */
185 ED_mesh_mirrtopo_free(mesh_topo_store);
186
187 mesh_topo_store->prev_is_editmode = is_editmode;
188
189 if (bm) {
191
192 totvert = bm->totvert;
193 }
194 else {
195 totvert = mesh->verts_num;
196 }
197
198 MirrTopoHash_t *topo_hash = MEM_new_array_zeroed<MirrTopoHash_t>(totvert, __func__);
199
200 /* Initialize the vert-edge-user counts used to detect unique topology */
201 if (bm) {
202 totedge = bm->totedge;
203
204 BM_ITER_MESH (eed, &iter, bm, BM_EDGES_OF_MESH) {
205 const int i1 = BM_elem_index_get(eed->v1), i2 = BM_elem_index_get(eed->v2);
206 topo_hash[i1]++;
207 topo_hash[i2]++;
208 }
209 }
210 else {
211 totedge = mesh->edges_num;
212 for (const int2 &edge : mesh->edges()) {
213 topo_hash[edge[0]]++;
214 topo_hash[edge[1]]++;
215 }
216 }
217
218 MirrTopoHash_t *topo_hash_prev = MEM_dupalloc(topo_hash);
219
220 tot_unique_prev = -1;
221 tot_unique_edges_prev = -1;
222 while (true) {
223 /* use the number of edges per vert to give verts unique topology IDs */
224
225 tot_unique_edges = 0;
226
227 /* This can make really big numbers, wrapping around here is fine */
228 if (bm) {
229 BM_ITER_MESH (eed, &iter, bm, BM_EDGES_OF_MESH) {
230 const int i1 = BM_elem_index_get(eed->v1), i2 = BM_elem_index_get(eed->v2);
231 topo_hash[i1] += topo_hash_prev[i2] * topo_pass;
232 topo_hash[i2] += topo_hash_prev[i1] * topo_pass;
233 tot_unique_edges += (topo_hash[i1] != topo_hash[i2]);
234 }
235 }
236 else {
237 for (const int2 &edge : mesh->edges()) {
238 const int i1 = edge[0], i2 = edge[1];
239 topo_hash[i1] += topo_hash_prev[i2] * topo_pass;
240 topo_hash[i2] += topo_hash_prev[i1] * topo_pass;
241 tot_unique_edges += (topo_hash[i1] != topo_hash[i2]);
242 }
243 }
244 memcpy(topo_hash_prev, topo_hash, sizeof(MirrTopoHash_t) * totvert);
245
246 /* sort so we can count unique values */
247 qsort(topo_hash_prev, totvert, sizeof(MirrTopoHash_t), mirrtopo_hash_sort);
248
249 tot_unique = 1; /* account for skipping the first value */
250 for (a = 1; a < totvert; a++) {
251 if (topo_hash_prev[a - 1] != topo_hash_prev[a]) {
252 tot_unique++;
253 }
254 }
255
256 if ((tot_unique <= tot_unique_prev) && (tot_unique_edges <= tot_unique_edges_prev)) {
257 /* Finish searching for unique values when 1 loop doesn't give a
258 * higher number of unique values compared to the previous loop. */
259 break;
260 }
261 tot_unique_prev = tot_unique;
262 tot_unique_edges_prev = tot_unique_edges;
263 /* Copy the hash calculated this iteration, so we can use them next time */
264 memcpy(topo_hash_prev, topo_hash, sizeof(MirrTopoHash_t) * totvert);
265
266 topo_pass++;
267 }
268
269 /* Hash/Index pairs are needed for sorting to find index pairs */
270 MirrTopoVert_t *topo_pairs = MEM_new_array_zeroed<MirrTopoVert_t>(totvert, "MirrTopoPairs");
271
272 /* since we are looping through verts, initialize these values here too */
273 intptr_t *index_lookup = MEM_new_array_uninitialized<intptr_t>(totvert, "mesh_topo_lookup");
274
275 if (bm) {
276 if (skip_bm_vert_array_init == false) {
278 }
279 }
280
281 for (a = 0; a < totvert; a++) {
282 topo_pairs[a].hash = topo_hash[a];
283 topo_pairs[a].v_index = a;
284
285 /* initialize lookup */
286 index_lookup[a] = -1;
287 }
288
289 qsort(topo_pairs, totvert, sizeof(MirrTopoVert_t), mirrtopo_vert_sort);
290
291 last = 0;
292
293 /* Get the pairs out of the sorted hashes.
294 * NOTE: `totvert + 1` means we can use the previous 2,
295 * but you can't ever access the last 'a' index of #MirrTopoPairs. */
296 if (bm) {
297 BMVert **vtable = bm->vtable;
298 for (a = 1; a <= totvert; a++) {
299 // printf("I %d %ld %d\n",
300 // (a - last), MirrTopoPairs[a].hash, MirrTopoPairs[a].v_index);
301 if ((a == totvert) || (topo_pairs[a - 1].hash != topo_pairs[a].hash)) {
302 const int match_count = a - last;
303 if (match_count == 2) {
304 const int j = topo_pairs[a - 1].v_index, k = topo_pairs[a - 2].v_index;
305 index_lookup[j] = intptr_t(vtable[k]);
306 index_lookup[k] = intptr_t(vtable[j]);
307 }
308 else if (match_count == 1) {
309 /* Center vertex. */
310 const int j = topo_pairs[a - 1].v_index;
311 index_lookup[j] = intptr_t(vtable[j]);
312 }
313 last = a;
314 }
315 }
316 }
317 else {
318 /* same as above, for mesh */
319 for (a = 1; a <= totvert; a++) {
320 if ((a == totvert) || (topo_pairs[a - 1].hash != topo_pairs[a].hash)) {
321 const int match_count = a - last;
322 if (match_count == 2) {
323 const int j = topo_pairs[a - 1].v_index, k = topo_pairs[a - 2].v_index;
324 index_lookup[j] = k;
325 index_lookup[k] = j;
326 }
327 else if (match_count == 1) {
328 /* Center vertex. */
329 const int j = topo_pairs[a - 1].v_index;
330 index_lookup[j] = j;
331 }
332 last = a;
333 }
334 }
335 }
336
337 MEM_delete(topo_pairs);
338 topo_pairs = nullptr;
339
340 MEM_delete(topo_hash);
341 MEM_delete(topo_hash_prev);
342
343 mesh_topo_store->index_lookup = index_lookup;
344 mesh_topo_store->prev_vert_tot = totvert;
345 mesh_topo_store->prev_edge_tot = totedge;
346}
347
349{
350 MEM_SAFE_DELETE(mesh_topo_store->index_lookup);
351 mesh_topo_store->prev_vert_tot = -1;
352 mesh_topo_store->prev_edge_tot = -1;
353}
354
356
357/* -------------------------------------------------------------------- */
360
361std::optional<EditMeshSymmetryHelper> EditMeshSymmetryHelper::create_if_needed(Object *ob,
362 uchar htype)
363{
364 BLI_assert(htype != 0);
365 BLI_assert((htype & ~(BM_VERT | BM_EDGE | BM_FACE)) == 0);
366
367 if (!ob || !ob->data) {
368 return std::nullopt;
369 }
370 Mesh *mesh = id_cast<Mesh *>(ob->data);
373
374 if (!em || !bm || mesh->symmetry == 0) {
375 return std::nullopt;
376 }
377 return EditMeshSymmetryHelper(ob, htype);
378}
379
380EditMeshSymmetryHelper::EditMeshSymmetryHelper(Object *ob, uchar htype)
381 : em_(BKE_editmesh_from_object(ob)),
382 mesh_(id_cast<Mesh *>(ob->data)),
384 htype_(htype)
385{
386 use_topology_mirror_ = (mesh_->editflag & ME_EDIT_MIRROR_TOPO) != 0;
387
388 Set<BMVert *> processed_verts;
389 Set<BMEdge *> processed_edges;
390 Set<BMFace *> processed_faces;
391
392 BMIter iter;
393
394 for (int axis = 0; axis < 3; axis++) {
395 if (mesh_->symmetry & (ME_SYMMETRY_X << axis)) {
397 bm_,
398 axis,
399 (htype_ & BM_VERT) != 0,
400 (htype_ & BM_EDGE) != 0,
401 (htype_ & BM_FACE) != 0,
402 use_topology_mirror_);
403
404 if (htype_ & BM_VERT) {
405 BMVert *v_curr;
406 BM_ITER_MESH (v_curr, &iter, bm_, BM_VERTS_OF_MESH) {
407 if (processed_verts.contains(v_curr)) {
408 continue;
409 }
410 BMVert *v_mirr = EDBM_verts_mirror_get(em_, bm_, v_curr);
411 if (v_mirr && v_mirr != v_curr) {
412 BMVert *v_mirr_check = EDBM_verts_mirror_get(em_, bm_, v_mirr);
413 if (v_mirr_check == v_curr) {
414 vert_to_mirror_map_.lookup_or_add(v_curr, {}).append(v_mirr);
415 vert_to_mirror_map_.lookup_or_add(v_mirr, {}).append(v_curr);
416 processed_verts.add(v_curr);
417 processed_verts.add(v_mirr);
418 }
419 }
420 }
421 }
422
423 if (htype_ & BM_EDGE) {
424 BMEdge *e_curr;
425 BM_ITER_MESH (e_curr, &iter, bm_, BM_EDGES_OF_MESH) {
426 if (processed_edges.contains(e_curr)) {
427 continue;
428 }
429 BMEdge *e_mirr = EDBM_verts_mirror_get_edge(em_, bm_, e_curr);
430 if (e_mirr && e_mirr != e_curr) {
431 BMEdge *e_mirr_check = EDBM_verts_mirror_get_edge(em_, bm_, e_mirr);
432 if (e_mirr_check == e_curr) {
433 edge_to_mirror_map_.lookup_or_add(e_curr, {}).append(e_mirr);
434 edge_to_mirror_map_.lookup_or_add(e_mirr, {}).append(e_curr);
435 processed_edges.add(e_curr);
436 processed_edges.add(e_mirr);
437 }
438 }
439 }
440 }
441
442 if (htype_ & BM_FACE) {
443 BMFace *f_curr;
444 BM_ITER_MESH (f_curr, &iter, bm_, BM_FACES_OF_MESH) {
445 if (processed_faces.contains(f_curr)) {
446 continue;
447 }
448 BMFace *f_mirr = EDBM_verts_mirror_get_face(em_, bm_, f_curr);
449 if (f_mirr && f_mirr != f_curr) {
450 BMFace *f_mirr_check = EDBM_verts_mirror_get_face(em_, bm_, f_mirr);
451 if (f_mirr_check == f_curr) {
452 face_to_mirror_map_.lookup_or_add(f_curr, {}).append(f_mirr);
453 face_to_mirror_map_.lookup_or_add(f_mirr, {}).append(f_curr);
454 processed_faces.add(f_curr);
455 processed_faces.add(f_mirr);
456 }
457 }
458 }
459 }
460
462 }
463 }
464}
466{
467 BLI_assert((this->htype_ & BM_VERT) != 0);
468 const Vector<BMVert *> *mirrors = this->vert_to_mirror_map_.lookup_ptr(v);
469 if (mirrors) {
470 for (BMVert *v_mirr : *mirrors) {
471 op(v_mirr);
472 }
473 }
474}
475
477{
478 BLI_assert((this->htype_ & BM_EDGE) != 0);
479 const Vector<BMEdge *> *mirrors = this->edge_to_mirror_map_.lookup_ptr(e);
480 if (mirrors) {
481 for (BMEdge *e_mirr : *mirrors) {
482 op(e_mirr);
483 }
484 }
485}
486
488{
489 BLI_assert((this->htype_ & BM_FACE) != 0);
490 const Vector<BMFace *> *mirrors = this->face_to_mirror_map_.lookup_ptr(f);
491 if (mirrors) {
492 for (BMFace *f_mirr : *mirrors) {
493 op(f_mirr);
494 }
495 }
496}
497
499{
500 BLI_assert((this->htype_ & BM_VERT) != 0);
501 const Vector<BMVert *> *mirrors = this->vert_to_mirror_map_.lookup_ptr(v);
502 if (mirrors) {
503 for (BMVert *v_mirr : *mirrors) {
504 if (BM_elem_flag_test(v_mirr, hflag) && !BM_elem_flag_test(v_mirr, BM_ELEM_HIDDEN)) {
505 return true;
506 }
507 }
508 }
509 return false;
510}
511
513{
514 BLI_assert((this->htype_ & BM_EDGE) != 0);
515 const Vector<BMEdge *> *mirrors = this->edge_to_mirror_map_.lookup_ptr(e);
516 if (mirrors) {
517 for (BMEdge *e_mirr : *mirrors) {
518 if (BM_elem_flag_test(e_mirr, hflag) && !BM_elem_flag_test(e_mirr, BM_ELEM_HIDDEN)) {
519 return true;
520 }
521 }
522 }
523 return false;
524}
525
527{
528 BLI_assert((this->htype_ & BM_FACE) != 0);
529 const Vector<BMFace *> *mirrors = this->face_to_mirror_map_.lookup_ptr(f);
530 if (mirrors) {
531 for (BMFace *f_mirr : *mirrors) {
532 if (BM_elem_flag_test(f_mirr, hflag) && !BM_elem_flag_test(f_mirr, BM_ELEM_HIDDEN)) {
533 return true;
534 }
535 }
536 }
537 return false;
538}
539
541 const char hflag,
542 const bool value) const
543{
544 apply_on_mirror_verts(v, [this, hflag, value](BMVert *v_mirr) {
545 if (hflag & BM_ELEM_SELECT) {
546 BM_vert_select_set(this->bm_, v_mirr, value);
547 }
548 const char hflag_test = char(hflag & ~BM_ELEM_SELECT);
549 if (hflag_test) {
550 BM_elem_flag_set(v_mirr, hflag_test, value);
551 }
552 });
553}
554
556 char hflag,
557 const bool value) const
558{
559 apply_on_mirror_edges(e, [this, hflag, value](BMEdge *e_mirr) {
560 if (hflag & BM_ELEM_SELECT) {
561 BM_edge_select_set(this->bm_, e_mirr, value);
562 }
563 char hflag_test = char(hflag & ~BM_ELEM_SELECT);
564 if (hflag_test) {
565 BM_elem_flag_set(e_mirr, hflag_test, value);
566 }
567 });
568}
569
571 const char hflag,
572 const bool value) const
573{
574 apply_on_mirror_faces(f, [this, hflag, value](BMFace *f_mirr) {
575 if (hflag & BM_ELEM_SELECT) {
576 BM_face_select_set(this->bm_, f_mirr, value);
577 }
578 char hflag_test = char(hflag & ~BM_ELEM_SELECT);
579 if (hflag_test) {
580 BM_elem_flag_set(f_mirr, hflag_test, value);
581 }
582 });
583}
584
586
587} // namespace blender
A KD-tree for nearest neighbor search.
Object is a sort of wrapper for general info.
Read Blender memory allocation and freeing.
#define BM_elem_index_get(ele)
#define BM_elem_flag_set(ele, hflag, val)
#define BM_elem_flag_test(ele, hflag)
#define BM_ITER_MESH(ele, iter, bm, itype)
#define BM_ITER_MESH_INDEX(ele, iter, bm, itype, indexvar)
void set_hflag_on_mirror_faces(BMFace *f, char hflag, bool value) const
void set_hflag_on_mirror_edges(BMEdge *e, char hflag, bool value) const
bool any_mirror_face_selected(BMFace *f, char hflag) const
bool any_mirror_vert_selected(BMVert *v, char hflag) const
void apply_on_mirror_edges(BMEdge *e, FunctionRef< void(BMEdge *)> op) const
void apply_on_mirror_verts(BMVert *v, FunctionRef< void(BMVert *)> op) const
void apply_on_mirror_faces(BMFace *f, FunctionRef< void(BMFace *)> op) const
void set_hflag_on_mirror_verts(BMVert *v, char hflag, bool value) const
static std::optional< EditMeshSymmetryHelper > create_if_needed(Object *ob, uchar htype)
bool any_mirror_edge_selected(BMEdge *e, char hflag) const
bool contains(const Key &key) const
Definition BLI_set.hh:310
bool add(const Key &key)
Definition BLI_set.hh:248
#define KD_THRESH
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void kdtree_balance(KDTree< CoordT > *tree)
void BM_mesh_elem_index_ensure(BMesh *bm, const char htype)
void ED_mesh_mirrtopo_init(BMesh *bm, Mesh *mesh, MirrTopoStore_t *mesh_topo_store, bool skip_bm_vert_array_init)
BMesh * BKE_editmesh_bmesh_get_for_write(Mesh *mesh)
Definition editmesh.cc:79
unsigned int uint
Definition BKE_text.h:55
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
int ED_mesh_mirror_spatial_table_lookup(Object *ob, Mesh *mesh_eval, const float co[3])
void BM_mesh_elem_table_ensure(BMesh *bm, const char htype)
BMVert * EDBM_verts_mirror_get(BMEditMesh *em, BMesh *bm, BMVert *v)
BMEdge * EDBM_verts_mirror_get_edge(BMEditMesh *em, BMesh *bm, BMEdge *e)
static int mirrtopo_vert_sort(const void *v1, const void *v2)
void ED_mesh_mirror_spatial_table_end(Object *ob)
bool ED_mesh_mirrtopo_recalc_check(BMesh *bm, Mesh *mesh, MirrTopoStore_t *mesh_topo_store)
ATTR_WARN_UNUSED_RESULT const BMVert * v
void EDBM_verts_mirror_cache_begin(BMEditMesh *em, BMesh *bm, int axis, bool use_self, bool use_select, bool respecthide, bool use_topology)
KDTree< CoordT > * kdtree_new(uint nodes_len_capacity)
Definition BLI_kdtree.hh:65
VecBase< int32_t, 2 > int2
unsigned char uchar
Definition BKE_text.h:58
@ ME_EDIT_MIRROR_TOPO
BMesh const char void * data
BMFace * EDBM_verts_mirror_get_face(BMEditMesh *em, BMesh *bm, BMFace *f)
void ED_mesh_mirrtopo_free(MirrTopoStore_t *mesh_topo_store)
void kdtree_insert(KDTree< CoordT > *tree, int index, const CoordT &co)
Definition BLI_kdtree.hh:96
void BM_face_select_set(BMesh *bm, BMFace *f, const bool select)
Select Face.
static struct blender::@264141273311030207060347213277130021246260340122 MirrKdStore
int kdtree_find_nearest(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > *r_nearest)
void BM_vert_select_set(BMesh *bm, BMVert *v, const bool select)
Select Vert.
BMEditMesh * BKE_editmesh_from_object(Object *ob)
Return the BMEditMesh for a given object.
Definition editmesh.cc:59
void kdtree_free(KDTree< CoordT > *tree)
Definition BLI_kdtree.hh:84
void EDBM_verts_mirror_cache_end(BMEditMesh *em)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
void ED_mesh_mirror_spatial_table_begin(Object *ob, Mesh *mesh_eval)
static int mirrtopo_hash_sort(const void *l1, const void *l2)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
_W64 int intptr_t
Definition BKE_text.h:119
void BM_edge_select_set(BMesh *bm, BMEdge *e, const bool select)
Select Edge.
#define hash
Definition noise_c.cc:156
eMesh_EditFlag editflag
eMeshSymmetryType symmetry