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