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