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