1 /*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version 2
5 * of the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software Foundation,
14 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15 */
16
17 /** \file
18 * \ingroup edmesh
19 *
20 * Mirror calculation for edit-mode and object mode.
21 */
22
23 #include "MEM_guardedalloc.h"
24
25 #include "BLI_math.h"
26
27 #include "DNA_mesh_types.h"
28 #include "DNA_meshdata_types.h"
29 #include "DNA_object_types.h"
30
31 #include "BKE_editmesh.h"
32 #include "BKE_mesh.h"
33 #include "BLI_kdtree.h"
34
35 #include "ED_mesh.h"
36
37 /* -------------------------------------------------------------------- */
38 /** \name Mesh Spatial Mirror API
39 * \{ */
40
41 #define KD_THRESH 0.00002f
42
43 static struct {
44 void *tree;
45 } MirrKdStore = {NULL};
46
ED_mesh_mirror_spatial_table_begin(Object * ob,BMEditMesh * em,Mesh * me_eval)47 void ED_mesh_mirror_spatial_table_begin(Object *ob, BMEditMesh *em, Mesh *me_eval)
48 {
49 Mesh *me = ob->data;
50 const bool use_em = (!me_eval && em && me->edit_mesh == em);
51 const int totvert = use_em ? em->bm->totvert : me_eval ? me_eval->totvert : me->totvert;
52
53 if (MirrKdStore.tree) { /* happens when entering this call without ending it */
54 ED_mesh_mirror_spatial_table_end(ob);
55 }
56
57 MirrKdStore.tree = BLI_kdtree_3d_new(totvert);
58
59 if (use_em) {
60 BMVert *eve;
61 BMIter iter;
62 int i;
63
64 /* this needs to be valid for index lookups later (callers need) */
65 BM_mesh_elem_table_ensure(em->bm, BM_VERT);
66
67 BM_ITER_MESH_INDEX (eve, &iter, em->bm, BM_VERTS_OF_MESH, i) {
68 BLI_kdtree_3d_insert(MirrKdStore.tree, i, eve->co);
69 }
70 }
71 else {
72 MVert *mvert = me_eval ? me_eval->mvert : me->mvert;
73 int i;
74
75 for (i = 0; i < totvert; i++, mvert++) {
76 BLI_kdtree_3d_insert(MirrKdStore.tree, i, mvert->co);
77 }
78 }
79
80 BLI_kdtree_3d_balance(MirrKdStore.tree);
81 }
82
ED_mesh_mirror_spatial_table_lookup(Object * ob,BMEditMesh * em,Mesh * me_eval,const float co[3])83 int ED_mesh_mirror_spatial_table_lookup(Object *ob,
84 BMEditMesh *em,
85 Mesh *me_eval,
86 const float co[3])
87 {
88 if (MirrKdStore.tree == NULL) {
89 ED_mesh_mirror_spatial_table_begin(ob, em, me_eval);
90 }
91
92 if (MirrKdStore.tree) {
93 KDTreeNearest_3d nearest;
94 const int i = BLI_kdtree_3d_find_nearest(MirrKdStore.tree, co, &nearest);
95
96 if (i != -1) {
97 if (nearest.dist < KD_THRESH) {
98 return i;
99 }
100 }
101 }
102 return -1;
103 }
104
ED_mesh_mirror_spatial_table_end(Object * UNUSED (ob))105 void ED_mesh_mirror_spatial_table_end(Object *UNUSED(ob))
106 {
107 /* TODO: store this in object/object-data (keep unused argument for now). */
108 if (MirrKdStore.tree) {
109 BLI_kdtree_3d_free(MirrKdStore.tree);
110 MirrKdStore.tree = NULL;
111 }
112 }
113
114 /** \} */
115
116 /* -------------------------------------------------------------------- */
117 /** \name Mesh Topology Mirror API
118 * \{ */
119
120 typedef uint MirrTopoHash_t;
121
122 typedef struct MirrTopoVert_t {
123 MirrTopoHash_t hash;
124 int v_index;
125 } MirrTopoVert_t;
126
mirrtopo_hash_sort(const void * l1,const void * l2)127 static int mirrtopo_hash_sort(const void *l1, const void *l2)
128 {
129 if ((MirrTopoHash_t)(intptr_t)l1 > (MirrTopoHash_t)(intptr_t)l2) {
130 return 1;
131 }
132 if ((MirrTopoHash_t)(intptr_t)l1 < (MirrTopoHash_t)(intptr_t)l2) {
133 return -1;
134 }
135 return 0;
136 }
137
mirrtopo_vert_sort(const void * v1,const void * v2)138 static int mirrtopo_vert_sort(const void *v1, const void *v2)
139 {
140 if (((MirrTopoVert_t *)v1)->hash > ((MirrTopoVert_t *)v2)->hash) {
141 return 1;
142 }
143 if (((MirrTopoVert_t *)v1)->hash < ((MirrTopoVert_t *)v2)->hash) {
144 return -1;
145 }
146 return 0;
147 }
148
ED_mesh_mirrtopo_recalc_check(BMEditMesh * em,Mesh * me,MirrTopoStore_t * mesh_topo_store)149 bool ED_mesh_mirrtopo_recalc_check(BMEditMesh *em, Mesh *me, MirrTopoStore_t *mesh_topo_store)
150 {
151 const bool is_editmode = em != NULL;
152 int totvert;
153 int totedge;
154
155 if (em) {
156 totvert = em->bm->totvert;
157 totedge = em->bm->totedge;
158 }
159 else {
160 totvert = me->totvert;
161 totedge = me->totedge;
162 }
163
164 if ((mesh_topo_store->index_lookup == NULL) ||
165 (mesh_topo_store->prev_is_editmode != is_editmode) ||
166 (totvert != mesh_topo_store->prev_vert_tot) || (totedge != mesh_topo_store->prev_edge_tot)) {
167 return true;
168 }
169 return false;
170 }
171
ED_mesh_mirrtopo_init(BMEditMesh * em,Mesh * me,MirrTopoStore_t * mesh_topo_store,const bool skip_em_vert_array_init)172 void ED_mesh_mirrtopo_init(BMEditMesh *em,
173 Mesh *me,
174 MirrTopoStore_t *mesh_topo_store,
175 const bool skip_em_vert_array_init)
176 {
177 if (em) {
178 BLI_assert(me == NULL);
179 }
180 const bool is_editmode = (em != NULL);
181 MEdge *medge = NULL, *med;
182
183 /* editmode*/
184 BMEdge *eed;
185 BMIter iter;
186
187 int a, last;
188 int totvert, totedge;
189 int tot_unique = -1, tot_unique_prev = -1;
190 int tot_unique_edges = 0, tot_unique_edges_prev;
191
192 MirrTopoHash_t *topo_hash = NULL;
193 MirrTopoHash_t *topo_hash_prev = NULL;
194 MirrTopoVert_t *topo_pairs;
195 MirrTopoHash_t topo_pass = 1;
196
197 intptr_t *index_lookup; /* direct access to mesh_topo_store->index_lookup */
198
199 /* reallocate if needed */
200 ED_mesh_mirrtopo_free(mesh_topo_store);
201
202 mesh_topo_store->prev_is_editmode = is_editmode;
203
204 if (em) {
205 BM_mesh_elem_index_ensure(em->bm, BM_VERT);
206
207 totvert = em->bm->totvert;
208 }
209 else {
210 totvert = me->totvert;
211 }
212
213 topo_hash = MEM_callocN(totvert * sizeof(MirrTopoHash_t), "TopoMirr");
214
215 /* Initialize the vert-edge-user counts used to detect unique topology */
216 if (em) {
217 totedge = em->bm->totedge;
218
219 BM_ITER_MESH (eed, &iter, em->bm, BM_EDGES_OF_MESH) {
220 const int i1 = BM_elem_index_get(eed->v1), i2 = BM_elem_index_get(eed->v2);
221 topo_hash[i1]++;
222 topo_hash[i2]++;
223 }
224 }
225 else {
226 totedge = me->totedge;
227 medge = me->medge;
228
229 for (a = 0, med = medge; a < totedge; a++, med++) {
230 const uint i1 = med->v1, i2 = med->v2;
231 topo_hash[i1]++;
232 topo_hash[i2]++;
233 }
234 }
235
236 topo_hash_prev = MEM_dupallocN(topo_hash);
237
238 tot_unique_prev = -1;
239 tot_unique_edges_prev = -1;
240 while (1) {
241 /* use the number of edges per vert to give verts unique topology IDs */
242
243 tot_unique_edges = 0;
244
245 /* This can make really big numbers, wrapping around here is fine */
246 if (em) {
247 BM_ITER_MESH (eed, &iter, em->bm, BM_EDGES_OF_MESH) {
248 const int i1 = BM_elem_index_get(eed->v1), i2 = BM_elem_index_get(eed->v2);
249 topo_hash[i1] += topo_hash_prev[i2] * topo_pass;
250 topo_hash[i2] += topo_hash_prev[i1] * topo_pass;
251 tot_unique_edges += (topo_hash[i1] != topo_hash[i2]);
252 }
253 }
254 else {
255 for (a = 0, med = medge; a < totedge; a++, med++) {
256 const uint i1 = med->v1, i2 = med->v2;
257 topo_hash[i1] += topo_hash_prev[i2] * topo_pass;
258 topo_hash[i2] += topo_hash_prev[i1] * topo_pass;
259 tot_unique_edges += (topo_hash[i1] != topo_hash[i2]);
260 }
261 }
262 memcpy(topo_hash_prev, topo_hash, sizeof(MirrTopoHash_t) * totvert);
263
264 /* sort so we can count unique values */
265 qsort(topo_hash_prev, totvert, sizeof(MirrTopoHash_t), mirrtopo_hash_sort);
266
267 tot_unique = 1; /* account for skipping the first value */
268 for (a = 1; a < totvert; a++) {
269 if (topo_hash_prev[a - 1] != topo_hash_prev[a]) {
270 tot_unique++;
271 }
272 }
273
274 if ((tot_unique <= tot_unique_prev) && (tot_unique_edges <= tot_unique_edges_prev)) {
275 /* Finish searching for unique values when 1 loop doesn't give a
276 * higher number of unique values compared to the previous loop. */
277 break;
278 }
279 tot_unique_prev = tot_unique;
280 tot_unique_edges_prev = tot_unique_edges;
281 /* Copy the hash calculated this iteration, so we can use them next time */
282 memcpy(topo_hash_prev, topo_hash, sizeof(MirrTopoHash_t) * totvert);
283
284 topo_pass++;
285 }
286
287 /* Hash/Index pairs are needed for sorting to find index pairs */
288 topo_pairs = MEM_callocN(sizeof(MirrTopoVert_t) * totvert, "MirrTopoPairs");
289
290 /* since we are looping through verts, initialize these values here too */
291 index_lookup = MEM_mallocN(totvert * sizeof(*index_lookup), "mesh_topo_lookup");
292
293 if (em) {
294 if (skip_em_vert_array_init == false) {
295 BM_mesh_elem_table_ensure(em->bm, BM_VERT);
296 }
297 }
298
299 for (a = 0; a < totvert; a++) {
300 topo_pairs[a].hash = topo_hash[a];
301 topo_pairs[a].v_index = a;
302
303 /* initialize lookup */
304 index_lookup[a] = -1;
305 }
306
307 qsort(topo_pairs, totvert, sizeof(MirrTopoVert_t), mirrtopo_vert_sort);
308
309 last = 0;
310
311 /* Get the pairs out of the sorted hashes, note, totvert+1 means we can use the previous 2,
312 * but you cant ever access the last 'a' index of MirrTopoPairs */
313 if (em) {
314 BMVert **vtable = em->bm->vtable;
315 for (a = 1; a <= totvert; a++) {
316 // printf("I %d %ld %d\n",
317 // (a - last), MirrTopoPairs[a].hash, MirrTopoPairs[a].v_index);
318 if ((a == totvert) || (topo_pairs[a - 1].hash != topo_pairs[a].hash)) {
319 const int match_count = a - last;
320 if (match_count == 2) {
321 const int j = topo_pairs[a - 1].v_index, k = topo_pairs[a - 2].v_index;
322 index_lookup[j] = (intptr_t)vtable[k];
323 index_lookup[k] = (intptr_t)vtable[j];
324 }
325 else if (match_count == 1) {
326 /* Center vertex. */
327 const int j = topo_pairs[a - 1].v_index;
328 index_lookup[j] = (intptr_t)vtable[j];
329 }
330 last = a;
331 }
332 }
333 }
334 else {
335 /* same as above, for mesh */
336 for (a = 1; a <= totvert; a++) {
337 if ((a == totvert) || (topo_pairs[a - 1].hash != topo_pairs[a].hash)) {
338 const int match_count = a - last;
339 if (match_count == 2) {
340 const int j = topo_pairs[a - 1].v_index, k = topo_pairs[a - 2].v_index;
341 index_lookup[j] = k;
342 index_lookup[k] = j;
343 }
344 else if (match_count == 1) {
345 /* Center vertex. */
346 const int j = topo_pairs[a - 1].v_index;
347 index_lookup[j] = j;
348 }
349 last = a;
350 }
351 }
352 }
353
354 MEM_freeN(topo_pairs);
355 topo_pairs = NULL;
356
357 MEM_freeN(topo_hash);
358 MEM_freeN(topo_hash_prev);
359
360 mesh_topo_store->index_lookup = index_lookup;
361 mesh_topo_store->prev_vert_tot = totvert;
362 mesh_topo_store->prev_edge_tot = totedge;
363 }
364
ED_mesh_mirrtopo_free(MirrTopoStore_t * mesh_topo_store)365 void ED_mesh_mirrtopo_free(MirrTopoStore_t *mesh_topo_store)
366 {
367 if (mesh_topo_store->index_lookup) {
368 MEM_freeN(mesh_topo_store->index_lookup);
369 }
370 mesh_topo_store->index_lookup = NULL;
371 mesh_topo_store->prev_vert_tot = -1;
372 mesh_topo_store->prev_edge_tot = -1;
373 }
374
375 /** \} */
376