Merging r57954 through r57961 from trunk into soc-2013-depsgraph_mt
[blender.git] / source / blender / editors / mesh / editface.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/editface.c
24  *  \ingroup edmesh
25  */
26
27
28 #include "MEM_guardedalloc.h"
29
30 #include "BLI_blenlib.h"
31 #include "BLI_math.h"
32 #include "BLI_edgehash.h"
33 #include "BLI_bitmap.h"
34
35 #include "BLF_translation.h"
36
37 #include "IMB_imbuf_types.h"
38 #include "IMB_imbuf.h"
39
40 #include "DNA_mesh_types.h"
41 #include "DNA_object_types.h"
42
43 #include "BKE_DerivedMesh.h"
44 #include "BKE_global.h"
45 #include "BKE_mesh.h"
46 #include "BKE_context.h"
47 #include "BKE_editmesh.h"
48 #include "BKE_utildefines.h"
49
50 #include "BIF_gl.h"
51
52 #include "ED_mesh.h"
53 #include "ED_screen.h"
54 #include "ED_view3d.h"
55
56 #include "WM_api.h"
57 #include "WM_types.h"
58
59 /* own include */
60
61 /* copy the face flags, most importantly selection from the mesh to the final derived mesh,
62  * use in object mode when selecting faces (while painting) */
63 void paintface_flush_flags(Object *ob)
64 {
65         Mesh *me = BKE_mesh_from_object(ob);
66         DerivedMesh *dm = ob->derivedFinal;
67         MPoly *polys, *mp_orig;
68         MFace *faces;
69         int *index_array = NULL;
70         int totface, totpoly;
71         int i;
72         
73         if (me == NULL)
74                 return;
75
76         /* note, call #BKE_mesh_flush_hidden_from_verts_ex first when changing hidden flags */
77
78         /* we could call this directly in all areas that change selection,
79          * since this could become slow for realtime updates (circle-select for eg) */
80         BKE_mesh_flush_select_from_polys(me);
81
82         if (dm == NULL)
83                 return;
84
85         /*
86          * Try to push updated mesh poly flags to three other data sets:
87          *  - Mesh polys => Mesh tess faces
88          *  - Mesh polys => Final derived polys
89          *  - Final derived polys => Final derived tessfaces
90          */
91
92         if ((index_array = CustomData_get_layer(&me->fdata, CD_ORIGINDEX))) {
93                 faces = me->mface;
94                 totface = me->totface;
95                 
96                 /* loop over tessfaces */
97                 for (i = 0; i < totface; i++) {
98                         /* Copy flags onto the original tessface from its original poly */
99                         mp_orig = me->mpoly + index_array[i];
100                         faces[i].flag = mp_orig->flag;
101                 }
102         }
103
104         if ((index_array = CustomData_get_layer(&dm->polyData, CD_ORIGINDEX))) {
105                 polys = dm->getPolyArray(dm);
106                 totpoly = dm->getNumPolys(dm);
107
108                 /* loop over final derived polys */
109                 for (i = 0; i < totpoly; i++) {
110                         /* Copy flags onto the final derived poly from the original mesh poly */
111                         mp_orig = me->mpoly + index_array[i];
112                         polys[i].flag = mp_orig->flag;
113                 }
114         }
115
116         if ((index_array = CustomData_get_layer(&dm->faceData, CD_ORIGINDEX))) {
117                 polys = dm->getPolyArray(dm);
118                 faces = dm->getTessFaceArray(dm);
119                 totface = dm->getNumTessFaces(dm);
120
121                 /* loop over tessfaces */
122                 for (i = 0; i < totface; i++) {
123                         /* Copy flags onto the final tessface from its final poly */
124                         mp_orig = polys + index_array[i];
125                         faces[i].flag = mp_orig->flag;
126                 }
127         }
128 }
129
130 void paintface_hide(Object *ob, const bool unselected)
131 {
132         Mesh *me;
133         MPoly *mpoly;
134         int a;
135         
136         me = BKE_mesh_from_object(ob);
137         if (me == NULL || me->totpoly == 0) return;
138
139         mpoly = me->mpoly;
140         a = me->totpoly;
141         while (a--) {
142                 if ((mpoly->flag & ME_HIDE) == 0) {
143                         if (((mpoly->flag & ME_FACE_SEL) == 0) == unselected) {
144                                 mpoly->flag |= ME_HIDE;
145                         }
146                 }
147
148                 if (mpoly->flag & ME_HIDE) {
149                         mpoly->flag &= ~ME_FACE_SEL;
150                 }
151                 
152                 mpoly++;
153         }
154         
155         BKE_mesh_flush_hidden_from_polys(me);
156
157         paintface_flush_flags(ob);
158 }
159
160
161 void paintface_reveal(Object *ob)
162 {
163         Mesh *me;
164         MPoly *mpoly;
165         int a;
166
167         me = BKE_mesh_from_object(ob);
168         if (me == NULL || me->totpoly == 0) return;
169
170         mpoly = me->mpoly;
171         a = me->totpoly;
172         while (a--) {
173                 if (mpoly->flag & ME_HIDE) {
174                         mpoly->flag |= ME_FACE_SEL;
175                         mpoly->flag -= ME_HIDE;
176                 }
177                 mpoly++;
178         }
179
180         BKE_mesh_flush_hidden_from_polys(me);
181
182         paintface_flush_flags(ob);
183 }
184
185 /* Set tface seams based on edge data, uses hash table to find seam edges. */
186
187 static void select_linked_tfaces_with_seams(Mesh *me, const unsigned int index, const bool select)
188 {
189         MPoly *mp;
190         MLoop *ml;
191         int a, b;
192         bool do_it = true;
193         bool mark = false;
194
195         BLI_bitmap edge_tag = BLI_BITMAP_NEW(me->totedge, __func__);
196         BLI_bitmap poly_tag = BLI_BITMAP_NEW(me->totpoly, __func__);
197
198         if (index != (unsigned int)-1) {
199                 /* only put face under cursor in array */
200                 mp = &me->mpoly[index];
201                 BKE_mesh_poly_edgebitmap_insert(edge_tag, mp, me->mloop + mp->loopstart);
202                 BLI_BITMAP_SET(poly_tag, index);
203         }
204         else {
205                 /* fill array by selection */
206                 mp = me->mpoly;
207                 for (a = 0; a < me->totpoly; a++, mp++) {
208                         if (mp->flag & ME_HIDE) {
209                                 /* pass */
210                         }
211                         else if (mp->flag & ME_FACE_SEL) {
212                                 BKE_mesh_poly_edgebitmap_insert(edge_tag, mp, me->mloop + mp->loopstart);
213                                 BLI_BITMAP_SET(poly_tag, a);
214                         }
215                 }
216         }
217
218         while (do_it) {
219                 do_it = false;
220
221                 /* expand selection */
222                 mp = me->mpoly;
223                 for (a = 0; a < me->totpoly; a++, mp++) {
224                         if (mp->flag & ME_HIDE)
225                                 continue;
226
227                         if (!BLI_BITMAP_GET(poly_tag, a)) {
228                                 mark = false;
229
230                                 ml = me->mloop + mp->loopstart;
231                                 for (b = 0; b < mp->totloop; b++, ml++) {
232                                         if ((me->medge[ml->e].flag & ME_SEAM) == 0) {
233                                                 if (BLI_BITMAP_GET(edge_tag, ml->e)) {
234                                                         mark = true;
235                                                         break;
236                                                 }
237                                         }
238                                 }
239
240                                 if (mark) {
241                                         BLI_BITMAP_SET(poly_tag, a);
242                                         BKE_mesh_poly_edgebitmap_insert(edge_tag, mp, me->mloop + mp->loopstart);
243                                         do_it = true;
244                                 }
245                         }
246                 }
247         }
248
249         MEM_freeN(edge_tag);
250
251         for (a = 0, mp = me->mpoly; a < me->totpoly; a++, mp++) {
252                 if (BLI_BITMAP_GET(poly_tag, a)) {
253                         BKE_BIT_TEST_SET(mp->flag, select, ME_FACE_SEL);
254                 }
255         }
256
257         MEM_freeN(poly_tag);
258 }
259
260 void paintface_select_linked(bContext *C, Object *ob, const int mval[2], const bool select)
261 {
262         Mesh *me;
263         unsigned int index = (unsigned int)-1;
264
265         me = BKE_mesh_from_object(ob);
266         if (me == NULL || me->totpoly == 0) return;
267
268         if (mval) {
269                 if (!ED_mesh_pick_face(C, ob, mval, &index, ED_MESH_PICK_DEFAULT_FACE_SIZE)) {
270                         return;
271                 }
272         }
273
274         select_linked_tfaces_with_seams(me, index, select);
275
276         paintface_flush_flags(ob);
277 }
278
279 void paintface_deselect_all_visible(Object *ob, int action, bool flush_flags)
280 {
281         Mesh *me;
282         MPoly *mpoly;
283         int a;
284
285         me = BKE_mesh_from_object(ob);
286         if (me == NULL) return;
287         
288         if (action == SEL_INVERT) {
289                 mpoly = me->mpoly;
290                 a = me->totpoly;
291                 while (a--) {
292                         if ((mpoly->flag & ME_HIDE) == 0) {
293                                 mpoly->flag ^= ME_FACE_SEL;
294                         }
295                         mpoly++;
296                 }
297         }
298         else {
299                 if (action == SEL_TOGGLE) {
300                         action = SEL_SELECT;
301
302                         mpoly = me->mpoly;
303                         a = me->totpoly;
304                         while (a--) {
305                                 if ((mpoly->flag & ME_HIDE) == 0 && mpoly->flag & ME_FACE_SEL) {
306                                         action = SEL_DESELECT;
307                                         break;
308                                 }
309                                 mpoly++;
310                         }
311                 }
312
313                 mpoly = me->mpoly;
314                 a = me->totpoly;
315                 while (a--) {
316                         if ((mpoly->flag & ME_HIDE) == 0) {
317                                 switch (action) {
318                                         case SEL_SELECT:
319                                                 mpoly->flag |= ME_FACE_SEL;
320                                                 break;
321                                         case SEL_DESELECT:
322                                                 mpoly->flag &= ~ME_FACE_SEL;
323                                                 break;
324                                         case SEL_INVERT:
325                                                 mpoly->flag ^= ME_FACE_SEL;
326                                                 break;
327                                 }
328                         }
329                         mpoly++;
330                 }
331         }
332
333         if (flush_flags) {
334                 paintface_flush_flags(ob);
335         }
336 }
337
338 bool paintface_minmax(Object *ob, float r_min[3], float r_max[3])
339 {
340         Mesh *me;
341         MPoly *mp;
342         MTexPoly *tf;
343         MLoop *ml;
344         MVert *mvert;
345         int a, b;
346         bool ok = false;
347         float vec[3], bmat[3][3];
348
349         me = BKE_mesh_from_object(ob);
350         if (!me || !me->mtpoly) return ok;
351         
352         copy_m3_m4(bmat, ob->obmat);
353
354         mvert = me->mvert;
355         mp = me->mpoly;
356         tf = me->mtpoly;
357         for (a = me->totpoly; a > 0; a--, mp++, tf++) {
358                 if (mp->flag & ME_HIDE || !(mp->flag & ME_FACE_SEL))
359                         continue;
360
361                 ml = me->mloop + mp->totloop;
362                 for (b = 0; b < mp->totloop; b++, ml++) {
363                         copy_v3_v3(vec, (mvert[ml->v].co));
364                         mul_m3_v3(bmat, vec);
365                         add_v3_v3v3(vec, vec, ob->obmat[3]);
366                         minmax_v3v3_v3(r_min, r_max, vec);
367                 }
368
369                 ok = true;
370         }
371
372         return ok;
373 }
374
375 bool paintface_mouse_select(struct bContext *C, Object *ob, const int mval[2], bool extend, bool deselect, bool toggle)
376 {
377         Mesh *me;
378         MPoly *mpoly, *mpoly_sel;
379         unsigned int a, index;
380         
381         /* Get the face under the cursor */
382         me = BKE_mesh_from_object(ob);
383
384         if (!ED_mesh_pick_face(C, ob, mval, &index, ED_MESH_PICK_DEFAULT_FACE_SIZE))
385                 return false;
386         
387         if (index >= me->totpoly)
388                 return false;
389
390         mpoly_sel = me->mpoly + index;
391         if (mpoly_sel->flag & ME_HIDE) return false;
392         
393         /* clear flags */
394         mpoly = me->mpoly;
395         a = me->totpoly;
396         if (!extend && !deselect && !toggle) {
397                 while (a--) {
398                         mpoly->flag &= ~ME_FACE_SEL;
399                         mpoly++;
400                 }
401         }
402         
403         me->act_face = (int)index;
404
405         if (extend) {
406                 mpoly_sel->flag |= ME_FACE_SEL;
407         }
408         else if (deselect) {
409                 mpoly_sel->flag &= ~ME_FACE_SEL;
410         }
411         else if (toggle) {
412                 if (mpoly_sel->flag & ME_FACE_SEL)
413                         mpoly_sel->flag &= ~ME_FACE_SEL;
414                 else
415                         mpoly_sel->flag |= ME_FACE_SEL;
416         }
417         else {
418                 mpoly_sel->flag |= ME_FACE_SEL;
419         }
420         
421         /* image window redraw */
422         
423         paintface_flush_flags(ob);
424         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, ob->data);
425         ED_region_tag_redraw(CTX_wm_region(C)); // XXX - should redraw all 3D views
426         return true;
427 }
428
429 int do_paintface_box_select(ViewContext *vc, rcti *rect, bool select, bool extend)
430 {
431         Object *ob = vc->obact;
432         Mesh *me;
433         MPoly *mpoly;
434         struct ImBuf *ibuf;
435         unsigned int *rt;
436         char *selar;
437         int a, index;
438         int sx = BLI_rcti_size_x(rect) + 1;
439         int sy = BLI_rcti_size_y(rect) + 1;
440         
441         me = BKE_mesh_from_object(ob);
442
443         if (me == NULL || me->totpoly == 0 || sx * sy <= 0)
444                 return OPERATOR_CANCELLED;
445
446         selar = MEM_callocN(me->totpoly + 1, "selar");
447
448         if (extend == false && select) {
449                 paintface_deselect_all_visible(vc->obact, SEL_DESELECT, false);
450
451                 mpoly = me->mpoly;
452                 for (a = 1; a <= me->totpoly; a++, mpoly++) {
453                         if ((mpoly->flag & ME_HIDE) == 0)
454                                 mpoly->flag &= ~ME_FACE_SEL;
455                 }
456         }
457
458         view3d_validate_backbuf(vc);
459
460         ibuf = IMB_allocImBuf(sx, sy, 32, IB_rect);
461         rt = ibuf->rect;
462         view3d_opengl_read_pixels(vc->ar, rect->xmin, rect->ymin, sx, sy, GL_RGBA, GL_UNSIGNED_BYTE,  ibuf->rect);
463         if (ENDIAN_ORDER == B_ENDIAN) IMB_convert_rgba_to_abgr(ibuf);
464
465         a = sx * sy;
466         while (a--) {
467                 if (*rt) {
468                         index = WM_framebuffer_to_index(*rt);
469                         if (index <= me->totpoly) selar[index] = 1;
470                 }
471                 rt++;
472         }
473
474         mpoly = me->mpoly;
475         for (a = 1; a <= me->totpoly; a++, mpoly++) {
476                 if (selar[a]) {
477                         if (mpoly->flag & ME_HIDE) {
478                                 /* pass */
479                         }
480                         else {
481                                 if (select) mpoly->flag |= ME_FACE_SEL;
482                                 else mpoly->flag &= ~ME_FACE_SEL;
483                         }
484                 }
485         }
486
487         IMB_freeImBuf(ibuf);
488         MEM_freeN(selar);
489
490 #ifdef __APPLE__        
491         glReadBuffer(GL_BACK);
492 #endif
493
494         paintface_flush_flags(vc->obact);
495
496         return OPERATOR_FINISHED;
497 }
498
499
500 /*  (similar to void paintface_flush_flags(Object *ob))
501  * copy the vertex flags, most importantly selection from the mesh to the final derived mesh,
502  * use in object mode when selecting vertices (while painting) */
503 void paintvert_flush_flags(Object *ob)
504 {
505         Mesh *me = BKE_mesh_from_object(ob);
506         DerivedMesh *dm = ob->derivedFinal;
507         MVert *dm_mvert, *dm_mv;
508         int *index_array = NULL;
509         int totvert;
510         int i;
511
512         if (me == NULL)
513                 return;
514
515         /* we could call this directly in all areas that change selection,
516          * since this could become slow for realtime updates (circle-select for eg) */
517         BKE_mesh_flush_select_from_verts(me);
518
519         if (dm == NULL)
520                 return;
521
522         index_array = dm->getVertDataArray(dm, CD_ORIGINDEX);
523
524         dm_mvert = dm->getVertArray(dm);
525         totvert = dm->getNumVerts(dm);
526
527         dm_mv = dm_mvert;
528
529         if (index_array) {
530                 int orig_index;
531                 for (i = 0; i < totvert; i++, dm_mv++) {
532                         orig_index = index_array[i];
533                         if (orig_index != ORIGINDEX_NONE) {
534                                 dm_mv->flag = me->mvert[index_array[i]].flag;
535                         }
536                 }
537         }
538         else {
539                 for (i = 0; i < totvert; i++, dm_mv++) {
540                         dm_mv->flag = me->mvert[i].flag;
541                 }
542         }
543 }
544 /*  note: if the caller passes false to flush_flags, then they will need to run paintvert_flush_flags(ob) themselves */
545 void paintvert_deselect_all_visible(Object *ob, int action, bool flush_flags)
546 {
547         Mesh *me;
548         MVert *mvert;
549         int a;
550
551         me = BKE_mesh_from_object(ob);
552         if (me == NULL) return;
553         
554         if (action == SEL_INVERT) {
555                 mvert = me->mvert;
556                 a = me->totvert;
557                 while (a--) {
558                         if ((mvert->flag & ME_HIDE) == 0) {
559                                 mvert->flag ^= SELECT;
560                         }
561                         mvert++;
562                 }
563         }
564         else {
565                 if (action == SEL_TOGGLE) {
566                         action = SEL_SELECT;
567
568                         mvert = me->mvert;
569                         a = me->totvert;
570                         while (a--) {
571                                 if ((mvert->flag & ME_HIDE) == 0 && mvert->flag & SELECT) {
572                                         action = SEL_DESELECT;
573                                         break;
574                                 }
575                                 mvert++;
576                         }
577                 }
578
579                 mvert = me->mvert;
580                 a = me->totvert;
581                 while (a--) {
582                         if ((mvert->flag & ME_HIDE) == 0) {
583                                 switch (action) {
584                                         case SEL_SELECT:
585                                                 mvert->flag |= SELECT;
586                                                 break;
587                                         case SEL_DESELECT:
588                                                 mvert->flag &= ~SELECT;
589                                                 break;
590                                         case SEL_INVERT:
591                                                 mvert->flag ^= SELECT;
592                                                 break;
593                                 }
594                         }
595                         mvert++;
596                 }
597         }
598
599         /* handle mselect */
600         if (action == SEL_SELECT) {
601                 /* pass */
602         }
603         else if (ELEM(action, SEL_DESELECT, SEL_INVERT)) {
604                 BKE_mesh_mselect_clear(me);
605         }
606         else {
607                 BKE_mesh_mselect_validate(me);
608         }
609
610         if (flush_flags) {
611                 paintvert_flush_flags(ob);
612         }
613 }
614
615 void paintvert_select_ungrouped(Object *ob, bool extend, bool flush_flags)
616 {
617         Mesh *me = BKE_mesh_from_object(ob);
618         MVert *mv;
619         MDeformVert *dv;
620         int a, tot;
621
622         if (me == NULL || me->dvert == NULL) {
623                 return;
624         }
625
626         if (!extend) {
627                 paintvert_deselect_all_visible(ob, SEL_DESELECT, false);
628         }
629
630         dv = me->dvert;
631         tot = me->totvert;
632
633         for (a = 0, mv = me->mvert; a < tot; a++, mv++, dv++) {
634                 if ((mv->flag & ME_HIDE) == 0) {
635                         if (dv->dw == NULL) {
636                                 /* if null weight then not grouped */
637                                 mv->flag |= SELECT;
638                         }
639                 }
640         }
641
642         if (flush_flags) {
643                 paintvert_flush_flags(ob);
644         }
645 }
646
647 /* ********************* MESH VERTEX MIRR TOPO LOOKUP *************** */
648 /* note, this is not the best place for the function to be but moved
649  * here to for the purpose of syncing with bmesh */
650
651 typedef unsigned int MirrTopoHash_t;
652
653 typedef struct MirrTopoVert_t {
654         MirrTopoHash_t hash;
655         int v_index;
656 } MirrTopoVert_t;
657
658 static int mirrtopo_hash_sort(const void *l1, const void *l2)
659 {
660         if      ((MirrTopoHash_t)(intptr_t)l1 > (MirrTopoHash_t)(intptr_t)l2) return 1;
661         else if ((MirrTopoHash_t)(intptr_t)l1 < (MirrTopoHash_t)(intptr_t)l2) return -1;
662         return 0;
663 }
664
665 static int mirrtopo_vert_sort(const void *v1, const void *v2)
666 {
667         if      (((MirrTopoVert_t *)v1)->hash > ((MirrTopoVert_t *)v2)->hash) return 1;
668         else if (((MirrTopoVert_t *)v1)->hash < ((MirrTopoVert_t *)v2)->hash) return -1;
669         return 0;
670 }
671
672 bool ED_mesh_mirrtopo_recalc_check(Mesh *me, const int ob_mode, MirrTopoStore_t *mesh_topo_store)
673 {
674         int totvert;
675         int totedge;
676
677         if (me->edit_btmesh) {
678                 totvert = me->edit_btmesh->bm->totvert;
679                 totedge = me->edit_btmesh->bm->totedge;
680         }
681         else {
682                 totvert = me->totvert;
683                 totedge = me->totedge;
684         }
685
686         if ((mesh_topo_store->index_lookup == NULL) ||
687             (mesh_topo_store->prev_ob_mode != ob_mode) ||
688             (totvert != mesh_topo_store->prev_vert_tot) ||
689             (totedge != mesh_topo_store->prev_edge_tot))
690         {
691                 return true;
692         }
693         else {
694                 return false;
695         }
696
697 }
698
699 void ED_mesh_mirrtopo_init(Mesh *me, const int ob_mode, MirrTopoStore_t *mesh_topo_store,
700                            const bool skip_em_vert_array_init)
701 {
702         MEdge *medge;
703         BMEditMesh *em = me->edit_btmesh;
704
705         /* editmode*/
706         BMEdge *eed;
707         BMIter iter;
708
709         int a, last;
710         int totvert, totedge;
711         int tot_unique = -1, tot_unique_prev = -1;
712
713         MirrTopoHash_t *topo_hash = NULL;
714         MirrTopoHash_t *topo_hash_prev = NULL;
715         MirrTopoVert_t *topo_pairs;
716         MirrTopoHash_t  topo_pass = 1;
717
718         intptr_t *index_lookup; /* direct access to mesh_topo_store->index_lookup */
719
720         /* reallocate if needed */
721         ED_mesh_mirrtopo_free(mesh_topo_store);
722
723         mesh_topo_store->prev_ob_mode = ob_mode;
724
725         if (em) {
726                 BM_mesh_elem_index_ensure(em->bm, BM_VERT);
727
728                 totvert = em->bm->totvert;
729         }
730         else {
731                 totvert = me->totvert;
732         }
733
734         topo_hash = MEM_callocN(totvert * sizeof(MirrTopoHash_t), "TopoMirr");
735
736         /* Initialize the vert-edge-user counts used to detect unique topology */
737         if (em) {
738                 totedge = me->edit_btmesh->bm->totedge;
739
740                 BM_ITER_MESH (eed, &iter, em->bm, BM_EDGES_OF_MESH) {
741                         topo_hash[BM_elem_index_get(eed->v1)]++;
742                         topo_hash[BM_elem_index_get(eed->v2)]++;
743                 }
744         }
745         else {
746                 totedge = me->totedge;
747
748                 for (a = 0, medge = me->medge; a < me->totedge; a++, medge++) {
749                         topo_hash[medge->v1]++;
750                         topo_hash[medge->v2]++;
751                 }
752         }
753
754         topo_hash_prev = MEM_dupallocN(topo_hash);
755
756         tot_unique_prev = -1;
757         while (1) {
758                 /* use the number of edges per vert to give verts unique topology IDs */
759
760                 if (em) {
761                         BM_ITER_MESH (eed, &iter, em->bm, BM_EDGES_OF_MESH) {
762                                 topo_hash[BM_elem_index_get(eed->v1)] += topo_hash_prev[BM_elem_index_get(eed->v2)] * topo_pass;
763                                 topo_hash[BM_elem_index_get(eed->v2)] += topo_hash_prev[BM_elem_index_get(eed->v1)] * topo_pass;
764                         }
765                 }
766                 else {
767                         for (a = 0, medge = me->medge; a < me->totedge; a++, medge++) {
768                                 /* This can make really big numbers, wrapping around here is fine */
769                                 topo_hash[medge->v1] += topo_hash_prev[medge->v2] * topo_pass;
770                                 topo_hash[medge->v2] += topo_hash_prev[medge->v1] * topo_pass;
771                         }
772                 }
773                 memcpy(topo_hash_prev, topo_hash, sizeof(MirrTopoHash_t) * totvert);
774
775                 /* sort so we can count unique values */
776                 qsort(topo_hash_prev, totvert, sizeof(MirrTopoHash_t), mirrtopo_hash_sort);
777
778                 tot_unique = 1; /* account for skiping the first value */
779                 for (a = 1; a < totvert; a++) {
780                         if (topo_hash_prev[a - 1] != topo_hash_prev[a]) {
781                                 tot_unique++;
782                         }
783                 }
784
785                 if (tot_unique <= tot_unique_prev) {
786                         /* Finish searching for unique values when 1 loop dosnt give a
787                          * higher number of unique values compared to the previous loop */
788                         break;
789                 }
790                 else {
791                         tot_unique_prev = tot_unique;
792                 }
793                 /* Copy the hash calculated this iter, so we can use them next time */
794                 memcpy(topo_hash_prev, topo_hash, sizeof(MirrTopoHash_t) * totvert);
795
796                 topo_pass++;
797         }
798
799         /* Hash/Index pairs are needed for sorting to find index pairs */
800         topo_pairs = MEM_callocN(sizeof(MirrTopoVert_t) * totvert, "MirrTopoPairs");
801
802         /* since we are looping through verts, initialize these values here too */
803         index_lookup = MEM_mallocN(totvert * sizeof(*index_lookup), "mesh_topo_lookup");
804
805         if (em) {
806                 if (skip_em_vert_array_init == false) {
807                         EDBM_index_arrays_ensure(em, BM_VERT);
808                 }
809         }
810
811
812         for (a = 0; a < totvert; a++) {
813                 topo_pairs[a].hash    = topo_hash[a];
814                 topo_pairs[a].v_index = a;
815
816                 /* initialize lookup */
817                 index_lookup[a] = -1;
818         }
819
820         qsort(topo_pairs, totvert, sizeof(MirrTopoVert_t), mirrtopo_vert_sort);
821
822         /* Since the loop starts at 2, we must define the last index where the hash's differ */
823         last = ((totvert >= 2) && (topo_pairs[0].hash == topo_pairs[1].hash)) ? 0 : 1;
824
825         /* Get the pairs out of the sorted hashes, note, totvert+1 means we can use the previous 2,
826          * but you cant ever access the last 'a' index of MirrTopoPairs */
827         for (a = 2; a <= totvert; a++) {
828                 /* printf("I %d %ld %d\n", (a-last), MirrTopoPairs[a  ].hash, MirrTopoPairs[a  ].v_index ); */
829                 if ((a == totvert) || (topo_pairs[a - 1].hash != topo_pairs[a].hash)) {
830                         if (a - last == 2) {
831                                 if (em) {
832                                         index_lookup[topo_pairs[a - 1].v_index] = (intptr_t)EDBM_vert_at_index(em, topo_pairs[a - 2].v_index);
833                                         index_lookup[topo_pairs[a - 2].v_index] = (intptr_t)EDBM_vert_at_index(em, topo_pairs[a - 1].v_index);
834                                 }
835                                 else {
836                                         index_lookup[topo_pairs[a - 1].v_index] = topo_pairs[a - 2].v_index;
837                                         index_lookup[topo_pairs[a - 2].v_index] = topo_pairs[a - 1].v_index;
838                                 }
839                         }
840                         last = a;
841                 }
842         }
843
844         MEM_freeN(topo_pairs);
845         topo_pairs = NULL;
846
847         MEM_freeN(topo_hash);
848         MEM_freeN(topo_hash_prev);
849
850         mesh_topo_store->index_lookup  = index_lookup;
851         mesh_topo_store->prev_vert_tot = totvert;
852         mesh_topo_store->prev_edge_tot = totedge;
853 }
854
855 void ED_mesh_mirrtopo_free(MirrTopoStore_t *mesh_topo_store)
856 {
857         if (mesh_topo_store->index_lookup) {
858                 MEM_freeN(mesh_topo_store->index_lookup);
859         }
860         mesh_topo_store->index_lookup  = NULL;
861         mesh_topo_store->prev_vert_tot = -1;
862         mesh_topo_store->prev_edge_tot = -1;
863 }