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