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