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