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