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