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