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