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