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