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