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