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