header re-shuffle, some headers contained unneeded refereces to other headers, better...
[blender-staging.git] / source / blender / editors / mesh / editmesh.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19  *
20  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
21  * All rights reserved.
22  *
23  * Contributor(s): Blender Foundation, full recode 2002-2008
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28
29 #include <stdlib.h>
30 #include <string.h>
31 #include <math.h>
32
33 #include "MEM_guardedalloc.h"
34
35 #include "DNA_scene_types.h"
36 #include "DNA_object_types.h"
37 #include "DNA_key_types.h"
38 #include "DNA_meshdata_types.h"
39 #include "DNA_modifier_types.h"
40
41 #include "BLI_blenlib.h"
42 #include "BLI_math.h"
43 #include "BLI_editVert.h"
44 #include "BLI_dynstr.h"
45 #include "BLI_rand.h"
46
47 #include "BKE_DerivedMesh.h"
48 #include "BKE_context.h"
49 #include "BKE_depsgraph.h"
50 #include "BKE_global.h"
51 #include "BKE_key.h"
52 #include "BKE_main.h"
53 #include "BKE_material.h"
54 #include "BKE_mesh.h"
55 #include "BKE_paint.h"
56
57 #include "ED_mesh.h"
58 #include "ED_object.h"
59 #include "ED_retopo.h"
60 #include "ED_screen.h"
61 #include "ED_util.h"
62 #include "ED_view3d.h"
63
64 #include "RNA_access.h"
65 #include "RNA_define.h"
66
67 #include "WM_api.h"
68 #include "WM_types.h"
69
70 /* own include */
71 #include "mesh_intern.h"
72
73 /* 
74 editmesh.c:
75         - add/alloc/free data
76         - hashtables
77         - enter/exit editmode
78 */
79
80 /* XXX */
81 static void BIF_undo_push(const char *dummy) {}
82 static void error(const char *dummy) {}
83
84
85 /* ***************** HASH ********************* */
86
87
88 #define EDHASHSIZE              (512*512)
89 #define EDHASH(a, b)    (a % EDHASHSIZE)
90
91
92 /* ************ ADD / REMOVE / FIND ****************** */
93
94 static void *calloc_em(EditMesh *em, size_t size, size_t nr)
95 {
96         return calloc(size, nr);
97 }
98
99 /* used to bypass normal calloc with fast one */
100 static void *(*callocvert)(EditMesh *, size_t, size_t) = calloc_em;
101 static void *(*callocedge)(EditMesh *, size_t, size_t) = calloc_em;
102 static void *(*callocface)(EditMesh *, size_t, size_t) = calloc_em;
103
104 EditVert *addvertlist(EditMesh *em, float *vec, EditVert *example)
105 {
106         EditVert *eve;
107         static int hashnr= 0;
108
109         eve= callocvert(em, sizeof(EditVert), 1);
110         BLI_addtail(&em->verts, eve);
111         em->totvert++;
112         
113         if(vec) VECCOPY(eve->co, vec);
114
115         eve->hash= hashnr++;
116         if( hashnr>=EDHASHSIZE) hashnr= 0;
117
118         /* new verts get keyindex of -1 since they did not
119          * have a pre-editmode vertex order
120          */
121         eve->keyindex = -1;
122
123         if(example) {
124                 CustomData_em_copy_data(&em->vdata, &em->vdata, example->data, &eve->data);
125                 eve->bweight = example->bweight;
126         }
127         else {
128                 CustomData_em_set_default(&em->vdata, &eve->data);
129         }
130
131         return eve;
132 }
133
134 void free_editvert (EditMesh *em, EditVert *eve)
135 {
136
137         EM_remove_selection(em, eve, EDITVERT);
138         CustomData_em_free_block(&em->vdata, &eve->data);
139         if(eve->fast==0)
140                 free(eve);
141         
142         em->totvert--;
143 }
144
145
146 EditEdge *findedgelist(EditMesh *em, EditVert *v1, EditVert *v2)
147 {
148         EditVert *v3;
149         struct HashEdge *he;
150
151         /* swap ? */
152         if( v1 > v2) {
153                 v3= v2; 
154                 v2= v1; 
155                 v1= v3;
156         }
157         
158         if(em->hashedgetab==NULL)
159                 em->hashedgetab= MEM_callocN(EDHASHSIZE*sizeof(struct HashEdge), "hashedgetab");
160
161         he= em->hashedgetab + EDHASH(v1->hash, v2->hash);
162         
163         while(he) {
164                 
165                 if(he->eed && he->eed->v1==v1 && he->eed->v2==v2) return he->eed;
166                 
167                 he= he->next;
168         }
169         return 0;
170 }
171
172 static void insert_hashedge(EditMesh *em, EditEdge *eed)
173 {
174         /* assuming that eed is not in the list yet, and that a find has been done before */
175         
176         struct HashEdge *first, *he;
177
178         first= em->hashedgetab + EDHASH(eed->v1->hash, eed->v2->hash);
179
180         if( first->eed==0 ) {
181                 first->eed= eed;
182         }
183         else {
184                 he= &eed->hash; 
185                 he->eed= eed;
186                 he->next= first->next;
187                 first->next= he;
188         }
189 }
190
191 static void remove_hashedge(EditMesh *em, EditEdge *eed)
192 {
193         /* assuming eed is in the list */
194         
195         struct HashEdge *first, *he, *prev=NULL;
196
197         he=first= em->hashedgetab + EDHASH(eed->v1->hash, eed->v2->hash);
198
199         while(he) {
200                 if(he->eed == eed) {
201                         /* remove from list */
202                         if(he==first) {
203                                 if(first->next) {
204                                         he= first->next;
205                                         first->eed= he->eed;
206                                         first->next= he->next;
207                                 }
208                                 else he->eed= 0;
209                         }
210                         else {
211                                 prev->next= he->next;
212                         }
213                         return;
214                 }
215                 prev= he;
216                 he= he->next;
217         }
218 }
219
220 EditEdge *addedgelist(EditMesh *em, EditVert *v1, EditVert *v2, EditEdge *example)
221 {
222         EditVert *v3;
223         EditEdge *eed;
224         int swap= 0;
225         
226         if(v1==v2) return NULL;
227         if(v1==NULL || v2==NULL) return NULL;
228
229         /* swap ? */
230         if(v1>v2) {
231                 v3= v2; 
232                 v2= v1; 
233                 v1= v3;
234                 swap= 1;
235         }
236         
237         /* find in hashlist */
238         eed= findedgelist(em, v1, v2);
239
240         if(eed==NULL) {
241         
242                 eed= (EditEdge *)callocedge(em, sizeof(EditEdge), 1);
243                 eed->v1= v1;
244                 eed->v2= v2;
245                 BLI_addtail(&em->edges, eed);
246                 eed->dir= swap;
247                 insert_hashedge(em, eed);
248                 em->totedge++;
249                 
250                 /* copy edge data:
251                    rule is to do this with addedgelist call, before addfacelist */
252                 if(example) {
253                         eed->crease= example->crease;
254                         eed->bweight= example->bweight;
255                         eed->sharp = example->sharp;
256                         eed->seam = example->seam;
257                         eed->h |= (example->h & EM_FGON);
258                 }
259         }
260
261         return eed;
262 }
263
264 void remedge(EditMesh *em, EditEdge *eed)
265 {
266         BLI_remlink(&em->edges, eed);
267         remove_hashedge(em, eed);
268         
269         em->totedge--;
270 }
271
272 void free_editedge(EditMesh *em, EditEdge *eed)
273 {
274         EM_remove_selection(em, eed, EDITEDGE);
275         if(eed->fast==0){ 
276                 free(eed);
277         }
278 }
279
280 void free_editface(EditMesh *em, EditFace *efa)
281 {
282         EM_remove_selection(em, efa, EDITFACE);
283         
284         if (em->act_face==efa) {
285                 EM_set_actFace(em, em->faces.first == efa ? NULL : em->faces.first);
286         }
287                 
288         CustomData_em_free_block(&em->fdata, &efa->data);
289         if(efa->fast==0)
290                 free(efa);
291         
292         em->totface--;
293 }
294
295 void free_vertlist(EditMesh *em, ListBase *edve) 
296 {
297         EditVert *eve, *next;
298
299         if (!edve) return;
300
301         eve= edve->first;
302         while(eve) {
303                 next= eve->next;
304                 free_editvert(em, eve);
305                 eve= next;
306         }
307         edve->first= edve->last= NULL;
308         em->totvert= em->totvertsel= 0;
309 }
310
311 void free_edgelist(EditMesh *em, ListBase *lb)
312 {
313         EditEdge *eed, *next;
314         
315         eed= lb->first;
316         while(eed) {
317                 next= eed->next;
318                 free_editedge(em, eed);
319                 eed= next;
320         }
321         lb->first= lb->last= NULL;
322         em->totedge= em->totedgesel= 0;
323 }
324
325 void free_facelist(EditMesh *em, ListBase *lb)
326 {
327         EditFace *efa, *next;
328         
329         efa= lb->first;
330         while(efa) {
331                 next= efa->next;
332                 free_editface(em, efa);
333                 efa= next;
334         }
335         lb->first= lb->last= NULL;
336         em->totface= em->totfacesel= 0;
337 }
338
339 EditFace *addfacelist(EditMesh *em, EditVert *v1, EditVert *v2, EditVert *v3, EditVert *v4, EditFace *example, EditFace *exampleEdges)
340 {
341         EditFace *efa;
342         EditEdge *e1, *e2=0, *e3=0, *e4=0;
343
344         /* added sanity check... seems to happen for some tools, or for enter editmode for corrupted meshes */
345         if(v1==v4 || v2==v4 || v3==v4) v4= NULL;
346         
347         /* add face to list and do the edges */
348         if(exampleEdges) {
349                 e1= addedgelist(em, v1, v2, exampleEdges->e1);
350                 e2= addedgelist(em, v2, v3, exampleEdges->e2);
351                 if(v4) e3= addedgelist(em, v3, v4, exampleEdges->e3); 
352                 else e3= addedgelist(em, v3, v1, exampleEdges->e3);
353                 if(v4) e4= addedgelist(em, v4, v1, exampleEdges->e4);
354         }
355         else {
356                 e1= addedgelist(em, v1, v2, NULL);
357                 e2= addedgelist(em, v2, v3, NULL);
358                 if(v4) e3= addedgelist(em, v3, v4, NULL); 
359                 else e3= addedgelist(em, v3, v1, NULL);
360                 if(v4) e4= addedgelist(em, v4, v1, NULL);
361         }
362         
363         if(v1==v2 || v2==v3 || v1==v3) return NULL;
364         if(e2==0) return NULL;
365
366         efa= (EditFace *)callocface(em, sizeof(EditFace), 1);
367         efa->v1= v1;
368         efa->v2= v2;
369         efa->v3= v3;
370         efa->v4= v4;
371
372         efa->e1= e1;
373         efa->e2= e2;
374         efa->e3= e3;
375         efa->e4= e4;
376
377         if(example) {
378                 efa->mat_nr= example->mat_nr;
379                 efa->flag= example->flag;
380                 CustomData_em_copy_data(&em->fdata, &em->fdata, example->data, &efa->data);
381         }
382         else {
383                 efa->mat_nr= em->mat_nr;
384
385                 CustomData_em_set_default(&em->fdata, &efa->data);
386         }
387
388         BLI_addtail(&em->faces, efa);
389         em->totface++;
390         
391         if(efa->v4) {
392                 normal_quad_v3( efa->n,efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co);
393                 cent_quad_v3(efa->cent, efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co);
394         }
395         else {
396                 normal_tri_v3( efa->n,efa->v1->co, efa->v2->co, efa->v3->co);
397                 cent_tri_v3(efa->cent, efa->v1->co, efa->v2->co, efa->v3->co);
398         }
399
400         return efa;
401 }
402
403 /* ************************ end add/new/find ************  */
404
405 /* ************************ Edit{Vert,Edge,Face} utilss ***************************** */
406
407 /* some nice utility functions */
408
409 EditVert *editedge_getOtherVert(EditEdge *eed, EditVert *eve)
410 {
411         if (eve==eed->v1) {
412                 return eed->v2;
413         } else if (eve==eed->v2) {
414                 return eed->v1;
415         } else {
416                 return NULL;
417         }
418 }
419
420 EditVert *editedge_getSharedVert(EditEdge *eed, EditEdge *eed2) 
421 {
422         if (eed->v1==eed2->v1 || eed->v1==eed2->v2) {
423                 return eed->v1;
424         } else if (eed->v2==eed2->v1 || eed->v2==eed2->v2) {
425                 return eed->v2;
426         } else {
427                 return NULL;
428         }
429 }
430
431 int editedge_containsVert(EditEdge *eed, EditVert *eve) 
432 {
433         return (eed->v1==eve || eed->v2==eve);
434 }
435
436 int editface_containsVert(EditFace *efa, EditVert *eve) 
437 {
438         return (efa->v1==eve || efa->v2==eve || efa->v3==eve || (efa->v4 && efa->v4==eve));
439 }
440
441 int editface_containsEdge(EditFace *efa, EditEdge *eed) 
442 {
443         return (efa->e1==eed || efa->e2==eed || efa->e3==eed || (efa->e4 && efa->e4==eed));
444 }
445
446
447 /* ************************ stuct EditMesh manipulation ***************************** */
448
449 /* fake callocs for fastmalloc below */
450 static void *calloc_fastvert(EditMesh *em, size_t size, size_t nr)
451 {
452         EditVert *eve= em->curvert++;
453         eve->fast= 1;
454         return eve;
455 }
456 static void *calloc_fastedge(EditMesh *em, size_t size, size_t nr)
457 {
458         EditEdge *eed= em->curedge++;
459         eed->fast= 1;
460         return eed;
461 }
462 static void *calloc_fastface(EditMesh *em, size_t size, size_t nr)
463 {
464         EditFace *efa= em->curface++;
465         efa->fast= 1;
466         return efa;
467 }
468
469 /* allocate 1 chunk for all vertices, edges, faces. These get tagged to
470    prevent it from being freed
471 */
472 static void init_editmesh_fastmalloc(EditMesh *em, int totvert, int totedge, int totface)
473 {
474         if(totvert) em->allverts= MEM_callocN(totvert*sizeof(EditVert), "allverts");
475         else em->allverts= NULL;
476         em->curvert= em->allverts;
477         
478         if(totedge==0) totedge= 4*totface;      // max possible
479
480         if(totedge) em->alledges= MEM_callocN(totedge*sizeof(EditEdge), "alledges");
481         else em->alledges= NULL;
482         em->curedge= em->alledges;
483         
484         if(totface) em->allfaces= MEM_callocN(totface*sizeof(EditFace), "allfaces");
485         else em->allfaces= NULL;
486         em->curface= em->allfaces;
487
488         callocvert= calloc_fastvert;
489         callocedge= calloc_fastedge;
490         callocface= calloc_fastface;
491 }
492
493 static void end_editmesh_fastmalloc(void)
494 {
495         callocvert= calloc_em;
496         callocedge= calloc_em;
497         callocface= calloc_em;
498 }
499
500 /* do not free editmesh itself here */
501 void free_editMesh(EditMesh *em)
502 {
503         if(em==NULL) return;
504
505         if(em->verts.first) free_vertlist(em, &em->verts);
506         if(em->edges.first) free_edgelist(em, &em->edges);
507         if(em->faces.first) free_facelist(em, &em->faces);
508         if(em->selected.first) BLI_freelistN(&(em->selected));
509
510         CustomData_free(&em->vdata, 0);
511         CustomData_free(&em->fdata, 0);
512
513         if(em->derivedFinal) {
514                 if (em->derivedFinal!=em->derivedCage) {
515                         em->derivedFinal->needsFree= 1;
516                         em->derivedFinal->release(em->derivedFinal);
517                 }
518                 em->derivedFinal= NULL;
519         }
520         if(em->derivedCage) {
521                 em->derivedCage->needsFree= 1;
522                 em->derivedCage->release(em->derivedCage);
523                 em->derivedCage= NULL;
524         }
525
526         /* DEBUG: hashtabs are slowest part of enter/exit editmode. here a testprint */
527 #if 0
528         if(em->hashedgetab) {
529                 HashEdge *he, *hen;
530                 int a, used=0, max=0, nr;
531                 he= em->hashedgetab;
532                 for(a=0; a<EDHASHSIZE; a++, he++) {
533                         if(he->eed) used++;
534                         hen= he->next;
535                         nr= 0;
536                         while(hen) {
537                                 nr++;
538                                 hen= hen->next;
539                         }
540                         if(max<nr) max= nr;
541                 }
542                 printf("hastab used %d max %d\n", used, max);
543         }
544 #endif
545         if(em->hashedgetab) MEM_freeN(em->hashedgetab);
546         em->hashedgetab= NULL;
547         
548         if(em->allverts) MEM_freeN(em->allverts);
549         if(em->alledges) MEM_freeN(em->alledges);
550         if(em->allfaces) MEM_freeN(em->allfaces);
551         
552         em->allverts= em->curvert= NULL;
553         em->alledges= em->curedge= NULL;
554         em->allfaces= em->curface= NULL;
555         
556         mesh_octree_table(NULL, NULL, NULL, 'e');
557         mesh_mirrtopo_table(NULL, 'e');
558
559         em->totvert= em->totedge= em->totface= 0;
560
561 // XXX  if(em->retopo_paint_data) retopo_free_paint_data(em->retopo_paint_data);
562         em->retopo_paint_data= NULL;
563         em->act_face = NULL;
564 }
565
566 static void editMesh_set_hash(EditMesh *em)
567 {
568         EditEdge *eed;
569
570         if(em->hashedgetab) MEM_freeN(em->hashedgetab);
571         em->hashedgetab= NULL;
572         
573         for(eed=em->edges.first; eed; eed= eed->next)  {
574                 if( findedgelist(em, eed->v1, eed->v2)==NULL )
575                         insert_hashedge(em, eed);
576         }
577
578 }
579
580
581 /* ************************ IN & OUT EDITMODE ***************************** */
582
583
584 static void edge_normal_compare(EditEdge *eed, EditFace *efa1)
585 {
586         EditFace *efa2;
587         float cent1[3], cent2[3];
588         float inp;
589         
590         efa2 = eed->tmp.f;
591         if(efa1==efa2) return;
592         
593         inp= efa1->n[0]*efa2->n[0] + efa1->n[1]*efa2->n[1] + efa1->n[2]*efa2->n[2];
594         if(inp<0.999 && inp >-0.999) eed->f2= 1;
595                 
596         if(efa1->v4) cent_quad_v3(cent1, efa1->v1->co, efa1->v2->co, efa1->v3->co, efa1->v4->co);
597         else cent_tri_v3(cent1, efa1->v1->co, efa1->v2->co, efa1->v3->co);
598         if(efa2->v4) cent_quad_v3(cent2, efa2->v1->co, efa2->v2->co, efa2->v3->co, efa2->v4->co);
599         else cent_tri_v3(cent2, efa2->v1->co, efa2->v2->co, efa2->v3->co);
600         
601         sub_v3_v3v3(cent1, cent2, cent1);
602         normalize_v3(cent1);
603         inp= cent1[0]*efa1->n[0] + cent1[1]*efa1->n[1] + cent1[2]*efa1->n[2]; 
604
605         if(inp < -0.001 ) eed->f1= 1;
606 }
607
608 #if 0
609 typedef struct {
610         EditEdge *eed;
611         float noLen,no[3];
612         int adjCount;
613 } EdgeDrawFlagInfo;
614
615 static int edgeDrawFlagInfo_cmp(const void *av, const void *bv)
616 {
617         const EdgeDrawFlagInfo *a = av;
618         const EdgeDrawFlagInfo *b = bv;
619
620         if (a->noLen<b->noLen) return -1;
621         else if (a->noLen>b->noLen) return 1;
622         else return 0;
623 }
624 #endif
625
626 static void edge_drawflags(Mesh *me, EditMesh *em)
627 {
628         EditVert *eve;
629         EditEdge *eed, *e1, *e2, *e3, *e4;
630         EditFace *efa;
631         
632         /* - count number of times edges are used in faces: 0 en 1 time means draw edge
633          * - edges more than 1 time used: in *tmp.f is pointer to first face
634          * - check all faces, when normal differs to much: draw (flag becomes 1)
635          */
636
637         /* later on: added flags for 'cylinder' and 'sphere' intersection tests in old
638            game engine (2.04)
639          */
640         
641         recalc_editnormals(em);
642         
643         /* init */
644         eve= em->verts.first;
645         while(eve) {
646                 eve->f1= 1;             /* during test it's set at zero */
647                 eve= eve->next;
648         }
649         eed= em->edges.first;
650         while(eed) {
651                 eed->f2= eed->f1= 0;
652                 eed->tmp.f = 0;
653                 eed= eed->next;
654         }
655
656         efa= em->faces.first;
657         while(efa) {
658                 e1= efa->e1;
659                 e2= efa->e2;
660                 e3= efa->e3;
661                 e4= efa->e4;
662                 if(e1->f2<4) e1->f2+= 1;
663                 if(e2->f2<4) e2->f2+= 1;
664                 if(e3->f2<4) e3->f2+= 1;
665                 if(e4 && e4->f2<4) e4->f2+= 1;
666                 
667                 if(e1->tmp.f == 0) e1->tmp.f = (void *) efa;
668                 if(e2->tmp.f == 0) e2->tmp.f = (void *) efa;
669                 if(e3->tmp.f ==0) e3->tmp.f = (void *) efa;
670                 if(e4 && (e4->tmp.f == 0)) e4->tmp.f = (void *) efa;
671                 
672                 efa= efa->next;
673         }
674
675         if(me->drawflag & ME_ALLEDGES) {
676                 efa= em->faces.first;
677                 while(efa) {
678                         if(efa->e1->f2>=2) efa->e1->f2= 1;
679                         if(efa->e2->f2>=2) efa->e2->f2= 1;
680                         if(efa->e3->f2>=2) efa->e3->f2= 1;
681                         if(efa->e4 && efa->e4->f2>=2) efa->e4->f2= 1;
682                         
683                         efa= efa->next;
684                 }               
685         }       
686         else {
687                 
688                 /* handle single-edges for 'test cylinder flag' (old engine) */
689                 
690                 eed= em->edges.first;
691                 while(eed) {
692                         if(eed->f2==1) eed->f1= 1;
693                         eed= eed->next;
694                 }
695
696                 /* all faces, all edges with flag==2: compare normal */
697                 efa= em->faces.first;
698                 while(efa) {
699                         if(efa->e1->f2==2) edge_normal_compare(efa->e1, efa);
700                         else efa->e1->f2= 1;
701                         if(efa->e2->f2==2) edge_normal_compare(efa->e2, efa);
702                         else efa->e2->f2= 1;
703                         if(efa->e3->f2==2) edge_normal_compare(efa->e3, efa);
704                         else efa->e3->f2= 1;
705                         if(efa->e4) {
706                                 if(efa->e4->f2==2) edge_normal_compare(efa->e4, efa);
707                                 else efa->e4->f2= 1;
708                         }
709                         efa= efa->next;
710                 }
711                 
712                 /* sphere collision flag */
713                 
714                 eed= em->edges.first;
715                 while(eed) {
716                         if(eed->f1!=1) {
717                                 eed->v1->f1= eed->v2->f1= 0;
718                         }
719                         eed= eed->next;
720                 }
721                 
722         }
723 }
724
725 /* turns Mesh into editmesh */
726 void make_editMesh(Scene *scene, Object *ob)
727 {
728         Mesh *me= ob->data;
729         MFace *mface;
730         MVert *mvert;
731         MSelect *mselect;
732         KeyBlock *actkey;
733         EditMesh *em;
734         EditVert *eve, **evlist, *eve1, *eve2, *eve3, *eve4;
735         EditFace *efa, *efa_last_sel= NULL;
736         EditEdge *eed;
737         EditSelection *ese;
738         float *co, (*keyco)[3]= NULL;
739         int tot, a, eekadoodle= 0;
740
741         if(me->edit_mesh==NULL)
742                 me->edit_mesh= MEM_callocN(sizeof(EditMesh), "editmesh");
743         else 
744                 /* because of reload */
745                 free_editMesh(me->edit_mesh);
746         
747         em= me->edit_mesh;
748         
749         em->selectmode= scene->toolsettings->selectmode; // warning needs to be synced
750         em->act_face = NULL;
751         em->totvert= tot= me->totvert;
752         em->totedge= me->totedge;
753         em->totface= me->totface;
754         
755         if(tot==0) {
756                 return;
757         }
758         
759         if(ob->actcol > 0)
760                 em->mat_nr= ob->actcol-1;
761
762         /* initialize fastmalloc for editmesh */
763         init_editmesh_fastmalloc(em, me->totvert, me->totedge, me->totface);
764
765         actkey = ob_get_keyblock(ob);
766         if(actkey) {
767                 /* undo-ing in past for previous editmode sessions gives corrupt 'keyindex' values */
768                 undo_editmode_clear();
769                 keyco= actkey->data;
770                 em->shapenr= ob->shapenr;
771         }
772
773         /* make editverts */
774         CustomData_copy(&me->vdata, &em->vdata, CD_MASK_EDITMESH, CD_CALLOC, 0);
775         mvert= me->mvert;
776
777         evlist= (EditVert **)MEM_mallocN(tot*sizeof(void *),"evlist");
778         for(a=0; a<tot; a++, mvert++) {
779                 
780                 co= mvert->co;
781
782                 /* edit the shape key coordinate if available */
783                 if(keyco && a < actkey->totelem)
784                         co= keyco[a];
785
786                 eve= addvertlist(em, co, NULL);
787                 evlist[a]= eve;
788                 
789                 /* face select sets selection in next loop */
790                 if(!paint_facesel_test(ob))
791                         eve->f |= (mvert->flag & 1);
792                 
793                 if (mvert->flag & ME_HIDE) eve->h= 1;           
794                 eve->no[0]= mvert->no[0]/32767.0;
795                 eve->no[1]= mvert->no[1]/32767.0;
796                 eve->no[2]= mvert->no[2]/32767.0;
797
798                 eve->bweight= ((float)mvert->bweight)/255.0f;
799
800                 /* lets overwrite the keyindex of the editvert
801                  * with the order it used to be in before
802                  * editmode
803                  */
804                 eve->keyindex = a;
805
806                 CustomData_to_em_block(&me->vdata, &em->vdata, a, &eve->data);
807         }
808
809         if(actkey && actkey->totelem!=me->totvert);
810         else {
811                 MEdge *medge= me->medge;
812                 
813                 CustomData_copy(&me->edata, &em->edata, CD_MASK_EDITMESH, CD_CALLOC, 0);
814                 /* make edges */
815                 for(a=0; a<me->totedge; a++, medge++) {
816                         eed= addedgelist(em, evlist[medge->v1], evlist[medge->v2], NULL);
817                         /* eed can be zero when v1 and v2 are identical, dxf import does this... */
818                         if(eed) {
819                                 eed->crease= ((float)medge->crease)/255.0f;
820                                 eed->bweight= ((float)medge->bweight)/255.0f;
821                                 
822                                 if(medge->flag & ME_SEAM) eed->seam= 1;
823                                 if(medge->flag & ME_SHARP) eed->sharp = 1;
824                                 if(medge->flag & SELECT) eed->f |= SELECT;
825                                 if(medge->flag & ME_FGON) eed->h= EM_FGON;      // 2 different defines!
826                                 if(medge->flag & ME_HIDE) eed->h |= 1;
827                                 if(em->selectmode==SCE_SELECT_EDGE) 
828                                         EM_select_edge(eed, eed->f & SELECT);           // force edge selection to vertices, seems to be needed ...
829                                 CustomData_to_em_block(&me->edata,&em->edata, a, &eed->data);
830                         }
831                 }
832                 
833                 CustomData_copy(&me->fdata, &em->fdata, CD_MASK_EDITMESH, CD_CALLOC, 0);
834
835                 /* make faces */
836                 mface= me->mface;
837
838                 for(a=0; a<me->totface; a++, mface++) {
839                         eve1= evlist[mface->v1];
840                         eve2= evlist[mface->v2];
841                         if(!mface->v3) eekadoodle= 1;
842                         eve3= evlist[mface->v3];
843                         if(mface->v4) eve4= evlist[mface->v4]; else eve4= NULL;
844                         
845                         efa= addfacelist(em, eve1, eve2, eve3, eve4, NULL, NULL);
846
847                         if(efa) {
848                                 CustomData_to_em_block(&me->fdata, &em->fdata, a, &efa->data);
849
850                                 efa->mat_nr= mface->mat_nr;
851                                 efa->flag= mface->flag & ~ME_HIDE;
852                                 
853                                 /* select and hide face flag */
854                                 if(mface->flag & ME_HIDE) {
855                                         efa->h= 1;
856                                 } else {
857                                         if (a==me->act_face) {
858                                                 EM_set_actFace(em, efa);
859                                         }
860                                         
861                                         /* dont allow hidden and selected */
862                                         if(mface->flag & ME_FACE_SEL) {
863                                                 efa->f |= SELECT;
864                                                 
865                                                 if(paint_facesel_test(ob)) {
866                                                         EM_select_face(efa, 1); /* flush down */
867                                                 }
868
869                                                 efa_last_sel= efa;
870                                         }
871                                 }
872                         }
873                 }
874         }
875         
876         if(EM_get_actFace(em, 0)==NULL && efa_last_sel) {
877                 EM_set_actFace(em, efa_last_sel);
878         }
879
880         if(eekadoodle)
881                 error("This Mesh has old style edgecodes, please put it in the bugtracker!");
882         
883         MEM_freeN(evlist);
884
885         end_editmesh_fastmalloc();      // resets global function pointers
886         
887         if(me->mselect){
888                 //restore editselections
889                 EM_init_index_arrays(em, 1,1,1);
890                 mselect = me->mselect;
891                 
892                 for(a=0; a<me->totselect; a++, mselect++){
893                         /*check if recorded selection is still valid, if so copy into editmesh*/
894                         if( (mselect->type == EDITVERT && me->mvert[mselect->index].flag & SELECT) || (mselect->type == EDITEDGE && me->medge[mselect->index].flag & SELECT) || (mselect->type == EDITFACE && me->mface[mselect->index].flag & ME_FACE_SEL) ){
895                                 ese = MEM_callocN(sizeof(EditSelection), "Edit Selection");
896                                 ese->type = mselect->type;      
897                                 if(ese->type == EDITVERT) ese->data = EM_get_vert_for_index(mselect->index); else
898                                 if(ese->type == EDITEDGE) ese->data = EM_get_edge_for_index(mselect->index); else
899                                 if(ese->type == EDITFACE) ese->data = EM_get_face_for_index(mselect->index);
900                                 BLI_addtail(&(em->selected),ese);
901                         }
902                 }
903                 EM_free_index_arrays();
904         }
905         /* this creates coherent selections. also needed for older files */
906         EM_selectmode_set(em);
907         /* paranoia check to enforce hide rules */
908         EM_hide_reset(em);
909         /* sets helper flags which arent saved */
910         EM_fgon_flags(em);
911         
912         if (EM_get_actFace(em, 0)==NULL) {
913                 EM_set_actFace(em, em->faces.first ); /* will use the first face, this is so we alwats have an active face */
914         }
915 }
916
917 /* makes Mesh out of editmesh */
918 void load_editMesh(Scene *scene, Object *ob)
919 {
920         Mesh *me= ob->data;
921         MVert *mvert, *oldverts;
922         MEdge *medge;
923         MFace *mface;
924         MSelect *mselect;
925         EditMesh *em= me->edit_mesh;
926         EditVert *eve;
927         EditFace *efa, *efa_act;
928         EditEdge *eed;
929         EditSelection *ese;
930         float *fp, *newkey, *oldkey, nor[3];
931         int i, a, ototvert;
932         
933         /* this one also tests of edges are not in faces: */
934         /* eed->f2==0: not in face, f2==1: draw it */
935         /* eed->f1 : flag for dynaface (cylindertest, old engine) */
936         /* eve->f1 : flag for dynaface (sphere test, old engine) */
937         /* eve->f2 : being used in vertexnormals */
938         edge_drawflags(me, em);
939         
940         EM_stats_update(em);
941         
942         /* new Vertex block */
943         if(em->totvert==0) mvert= NULL;
944         else mvert= MEM_callocN(em->totvert*sizeof(MVert), "loadeditMesh vert");
945
946         /* new Edge block */
947         if(em->totedge==0) medge= NULL;
948         else medge= MEM_callocN(em->totedge*sizeof(MEdge), "loadeditMesh edge");
949         
950         /* new Face block */
951         if(em->totface==0) mface= NULL;
952         else mface= MEM_callocN(em->totface*sizeof(MFace), "loadeditMesh face");
953
954         /* lets save the old verts just in case we are actually working on
955          * a key ... we now do processing of the keys at the end */
956         oldverts= me->mvert;
957         ototvert= me->totvert;
958
959         /* don't free this yet */
960         CustomData_set_layer(&me->vdata, CD_MVERT, NULL);
961
962         /* free custom data */
963         CustomData_free(&me->vdata, me->totvert);
964         CustomData_free(&me->edata, me->totedge);
965         CustomData_free(&me->fdata, me->totface);
966
967         /* add new custom data */
968         me->totvert= em->totvert;
969         me->totedge= em->totedge;
970         me->totface= em->totface;
971
972         CustomData_copy(&em->vdata, &me->vdata, CD_MASK_MESH, CD_CALLOC, me->totvert);
973         CustomData_copy(&em->edata, &me->edata, CD_MASK_MESH, CD_CALLOC, me->totedge);
974         CustomData_copy(&em->fdata, &me->fdata, CD_MASK_MESH, CD_CALLOC, me->totface);
975
976         CustomData_add_layer(&me->vdata, CD_MVERT, CD_ASSIGN, mvert, me->totvert);
977         CustomData_add_layer(&me->edata, CD_MEDGE, CD_ASSIGN, medge, me->totedge);
978         CustomData_add_layer(&me->fdata, CD_MFACE, CD_ASSIGN, mface, me->totface);
979         mesh_update_customdata_pointers(me);
980
981         /* the vertices, use ->tmp.l as counter */
982         eve= em->verts.first;
983         a= 0;
984
985         while(eve) {
986                 VECCOPY(mvert->co, eve->co);
987
988                 mvert->mat_nr= 32767;  /* what was this for, halos? */
989                 
990                 /* vertex normal */
991                 VECCOPY(nor, eve->no);
992                 mul_v3_fl(nor, 32767.0);
993                 VECCOPY(mvert->no, nor);
994
995                 /* note: it used to remove me->dvert when it was not in use, cancelled
996                    that... annoying when you have a fresh vgroup */
997                 CustomData_from_em_block(&em->vdata, &me->vdata, eve->data, a);
998
999                 eve->tmp.l = a++;  /* counter */
1000                         
1001                 mvert->flag= 0;
1002                 mvert->flag |= (eve->f & SELECT);
1003                 if (eve->h) mvert->flag |= ME_HIDE;
1004                 
1005                 mvert->bweight= (char)(255.0*eve->bweight);
1006
1007                 eve= eve->next;
1008                 mvert++;
1009         }
1010
1011         /* the edges */
1012         a= 0;
1013         eed= em->edges.first;
1014         while(eed) {
1015                 medge->v1= (unsigned int) eed->v1->tmp.l;
1016                 medge->v2= (unsigned int) eed->v2->tmp.l;
1017                 
1018                 medge->flag= (eed->f & SELECT) | ME_EDGERENDER;
1019                 if(eed->f2<2) medge->flag |= ME_EDGEDRAW;
1020                 if(eed->f2==0) medge->flag |= ME_LOOSEEDGE;
1021                 if(eed->sharp) medge->flag |= ME_SHARP;
1022                 if(eed->seam) medge->flag |= ME_SEAM;
1023                 if(eed->h & EM_FGON) medge->flag |= ME_FGON;    // different defines yes
1024                 if(eed->h & 1) medge->flag |= ME_HIDE;
1025                 
1026                 medge->crease= (char)(255.0*eed->crease);
1027                 medge->bweight= (char)(255.0*eed->bweight);
1028                 CustomData_from_em_block(&em->edata, &me->edata, eed->data, a);         
1029
1030                 eed->tmp.l = a++;
1031                 
1032                 medge++;
1033                 eed= eed->next;
1034         }
1035
1036         /* the faces */
1037         a = 0;
1038         efa= em->faces.first;
1039         efa_act= EM_get_actFace(em, 0);
1040         i = 0;
1041         me->act_face = -1;
1042         while(efa) {
1043                 mface= &((MFace *) me->mface)[i];
1044                 
1045                 mface->v1= (unsigned int) efa->v1->tmp.l;
1046                 mface->v2= (unsigned int) efa->v2->tmp.l;
1047                 mface->v3= (unsigned int) efa->v3->tmp.l;
1048                 if (efa->v4) mface->v4 = (unsigned int) efa->v4->tmp.l;
1049
1050                 mface->mat_nr= efa->mat_nr;
1051                 
1052                 mface->flag= efa->flag;
1053                 /* bit 0 of flag is already taken for smooth... */
1054                 
1055                 if(efa->h) {
1056                         mface->flag |= ME_HIDE;
1057                         mface->flag &= ~ME_FACE_SEL;
1058                 } else {
1059                         if(efa->f & 1) mface->flag |= ME_FACE_SEL;
1060                         else mface->flag &= ~ME_FACE_SEL;
1061                 }
1062                 
1063                 /* mat_nr in vertex */
1064                 if(me->totcol>1) {
1065                         mvert= me->mvert+mface->v1;
1066                         if(mvert->mat_nr == (char)32767) mvert->mat_nr= mface->mat_nr;
1067                         mvert= me->mvert+mface->v2;
1068                         if(mvert->mat_nr == (char)32767) mvert->mat_nr= mface->mat_nr;
1069                         mvert= me->mvert+mface->v3;
1070                         if(mvert->mat_nr == (char)32767) mvert->mat_nr= mface->mat_nr;
1071                         if(mface->v4) {
1072                                 mvert= me->mvert+mface->v4;
1073                                 if(mvert->mat_nr == (char)32767) mvert->mat_nr= mface->mat_nr;
1074                         }
1075                 }
1076                         
1077                 /* watch: efa->e1->f2==0 means loose edge */ 
1078                         
1079                 if(efa->e1->f2==1) {
1080                         efa->e1->f2= 2;
1081                 }                       
1082                 if(efa->e2->f2==1) {
1083                         efa->e2->f2= 2;
1084                 }
1085                 if(efa->e3->f2==1) {
1086                         efa->e3->f2= 2;
1087                 }
1088                 if(efa->e4 && efa->e4->f2==1) {
1089                         efa->e4->f2= 2;
1090                 }
1091
1092                 CustomData_from_em_block(&em->fdata, &me->fdata, efa->data, i);
1093
1094                 /* no index '0' at location 3 or 4 */
1095                 test_index_face(mface, &me->fdata, i, efa->v4?4:3);
1096                 
1097                 if (efa_act == efa)
1098                         me->act_face = a;
1099
1100                 efa->tmp.l = a++;
1101                 i++;
1102                 efa= efa->next;
1103         }
1104
1105         /* patch hook indices and vertex parents */
1106         {
1107                 Object *ob;
1108                 ModifierData *md;
1109                 EditVert **vertMap = NULL;
1110                 int i,j;
1111
1112                 for (ob=G.main->object.first; ob; ob=ob->id.next) {
1113                         if (ob->parent==ob && ELEM(ob->partype, PARVERT1,PARVERT3)) {
1114                                 
1115                                 /* duplicate code from below, make it function later...? */
1116                                 if (!vertMap) {
1117                                         vertMap = MEM_callocN(sizeof(*vertMap)*ototvert, "vertMap");
1118                                         
1119                                         for (eve=em->verts.first; eve; eve=eve->next) {
1120                                                 if (eve->keyindex!=-1)
1121                                                         vertMap[eve->keyindex] = eve;
1122                                         }
1123                                 }
1124                                 if(ob->par1 < ototvert) {
1125                                         eve = vertMap[ob->par1];
1126                                         if(eve) ob->par1= eve->tmp.l;
1127                                 }
1128                                 if(ob->par2 < ototvert) {
1129                                         eve = vertMap[ob->par2];
1130                                         if(eve) ob->par2= eve->tmp.l;
1131                                 }
1132                                 if(ob->par3 < ototvert) {
1133                                         eve = vertMap[ob->par3];
1134                                         if(eve) ob->par3= eve->tmp.l;
1135                                 }
1136                                 
1137                         }
1138                         if (ob->data==me) {
1139                                 for (md=ob->modifiers.first; md; md=md->next) {
1140                                         if (md->type==eModifierType_Hook) {
1141                                                 HookModifierData *hmd = (HookModifierData*) md;
1142
1143                                                 if (!vertMap) {
1144                                                         vertMap = MEM_callocN(sizeof(*vertMap)*ototvert, "vertMap");
1145
1146                                                         for (eve=em->verts.first; eve; eve=eve->next) {
1147                                                                 if (eve->keyindex!=-1)
1148                                                                         vertMap[eve->keyindex] = eve;
1149                                                         }
1150                                                 }
1151                                                 
1152                                                 for (i=j=0; i<hmd->totindex; i++) {
1153                                                         if(hmd->indexar[i] < ototvert) {
1154                                                                 eve = vertMap[hmd->indexar[i]];
1155                                                                 
1156                                                                 if (eve) {
1157                                                                         hmd->indexar[j++] = eve->tmp.l;
1158                                                                 }
1159                                                         }
1160                                                         else j++;
1161                                                 }
1162
1163                                                 hmd->totindex = j;
1164                                         }
1165                                 }
1166                         }
1167                 }
1168
1169                 if (vertMap) MEM_freeN(vertMap);
1170         }
1171
1172         /* are there keys? */
1173         if(me->key) {
1174                 KeyBlock *currkey;
1175                 KeyBlock *actkey= BLI_findlink(&me->key->block, em->shapenr-1);
1176
1177                 float (*ofs)[3] = NULL;
1178
1179                 /* editing the base key should update others */
1180                 if(me->key->type==KEY_RELATIVE && oldverts) {
1181                         int act_is_basis = 0;
1182                         /* find if this key is a basis for any others */
1183                         for(currkey = me->key->block.first; currkey; currkey= currkey->next) {
1184                                 if(em->shapenr-1 == currkey->relative) {
1185                                         act_is_basis = 1;
1186                                         break;
1187                                 }
1188                         }
1189
1190                         if(act_is_basis) { /* active key is a base */
1191                                 i=0;
1192                                 ofs= MEM_callocN(sizeof(float) * 3 * em->totvert,  "currkey->data");
1193                                 eve= em->verts.first;
1194                                 mvert = me->mvert;
1195                                 while(eve) {
1196                                         VECSUB(ofs[i], mvert->co, oldverts[eve->keyindex].co);
1197                                         eve= eve->next;
1198                                         i++;
1199                                         mvert++;
1200                                 }
1201                         }
1202                 }
1203
1204
1205                 /* Lets reorder the key data so that things line up roughly
1206                  * with the way things were before editmode */
1207                 currkey = me->key->block.first;
1208                 while(currkey) {
1209                         int apply_offset = (ofs && (currkey != actkey) && (em->shapenr-1 == currkey->relative));
1210
1211                         fp= newkey= MEM_callocN(me->key->elemsize*em->totvert,  "currkey->data");
1212                         oldkey = currkey->data;
1213
1214                         eve= em->verts.first;
1215
1216                         i = 0;
1217                         mvert = me->mvert;
1218                         while(eve) {
1219                                 if (eve->keyindex >= 0 && eve->keyindex < currkey->totelem) { // valid old vertex
1220                                         if(currkey == actkey) {
1221                                                 if(actkey == me->key->refkey) {
1222                                                         VECCOPY(fp, mvert->co);
1223                                                 }
1224                                                 else {
1225                                                         VECCOPY(fp, mvert->co);
1226                                                         if(oldverts) {
1227                                                                 VECCOPY(mvert->co, oldverts[eve->keyindex].co);
1228                                                         }
1229                                                 }
1230                                         }
1231                                         else {
1232                                                 if(oldkey) {
1233                                                         VECCOPY(fp, oldkey + 3 * eve->keyindex);
1234                                                 }
1235                                         }
1236                                 }
1237                                 else {
1238                                         VECCOPY(fp, mvert->co);
1239                                 }
1240
1241                                 /* propagate edited basis offsets to other shapes */
1242                                 if(apply_offset) {
1243                                         VECADD(fp, fp, ofs[i]);
1244                                 }
1245
1246                                 fp+= 3;
1247                                 ++i;
1248                                 ++mvert;
1249                                 eve= eve->next;
1250                         }
1251                         currkey->totelem= em->totvert;
1252                         if(currkey->data) MEM_freeN(currkey->data);
1253                         currkey->data = newkey;
1254                         
1255                         currkey= currkey->next;
1256                 }
1257
1258                 if(ofs) MEM_freeN(ofs);
1259         }
1260
1261         if(oldverts) MEM_freeN(oldverts);
1262         
1263         i = 0;
1264         for(ese=em->selected.first; ese; ese=ese->next) i++;
1265         me->totselect = i;
1266         if(i==0) mselect= NULL;
1267         else mselect= MEM_callocN(i*sizeof(MSelect), "loadeditMesh selections");
1268         
1269         if(me->mselect) MEM_freeN(me->mselect);
1270         me->mselect= mselect;
1271         
1272         for(ese=em->selected.first; ese; ese=ese->next){
1273                 mselect->type = ese->type;
1274                 if(ese->type == EDITVERT) mselect->index = ((EditVert*)ese->data)->tmp.l;
1275                 else if(ese->type == EDITEDGE) mselect->index = ((EditEdge*)ese->data)->tmp.l;
1276                 else if(ese->type == EDITFACE) mselect->index = ((EditFace*)ese->data)->tmp.l;
1277                 mselect++;
1278         }
1279         
1280         /* to be sure: clear ->tmp.l pointers */
1281         eve= em->verts.first;
1282         while(eve) {
1283                 eve->tmp.l = 0;
1284                 eve= eve->next;
1285         }
1286         
1287         eed= em->edges.first;
1288         while(eed) { 
1289                 eed->tmp.l = 0;
1290                 eed= eed->next;
1291         }
1292         
1293         efa= em->faces.first;
1294         while(efa) {
1295                 efa->tmp.l = 0;
1296                 efa= efa->next;
1297         }
1298         
1299         /* remake softbody of all users */
1300         if(me->id.us>1) {
1301                 Base *base;
1302                 for(base= scene->base.first; base; base= base->next)
1303                         if(base->object->data==me)
1304                                 base->object->recalc |= OB_RECALC_DATA;
1305         }
1306
1307         mesh_calc_normals(me->mvert, me->totvert, me->mface, me->totface, NULL);
1308 }
1309
1310 void remake_editMesh(Scene *scene, Object *ob)
1311 {
1312         make_editMesh(scene, ob);
1313         DAG_id_flush_update(&ob->id, OB_RECALC_DATA);
1314         BIF_undo_push("Undo all changes");
1315 }
1316
1317 /* *************** Operator: separate parts *************/
1318
1319 static EnumPropertyItem prop_separate_types[] = {
1320         {0, "SELECTED", 0, "Selection", ""},
1321         {1, "MATERIAL", 0, "By Material", ""},
1322         {2, "LOOSE", 0, "By loose parts", ""},
1323         {0, NULL, 0, NULL, NULL}
1324 };
1325
1326 /* return 1: success */
1327 static int mesh_separate_selected(Main *bmain, Scene *scene, Base *editbase)
1328 {
1329         EditMesh *em, *emnew;
1330         EditVert *eve, *v1;
1331         EditEdge *eed, *e1;
1332         EditFace *efa, *f1;
1333         Object *obedit;
1334         Mesh *me, *menew;
1335         Base *basenew;
1336         
1337         if(editbase==NULL) return 0;
1338         
1339         obedit= editbase->object;
1340         me= obedit->data;
1341         em= BKE_mesh_get_editmesh(me);
1342         if(me->key) {
1343                 error("Can't separate with vertex keys");
1344                 BKE_mesh_end_editmesh(me, em);
1345                 return 0;
1346         }
1347         
1348         if(em->selected.first) 
1349                 BLI_freelistN(&(em->selected)); /* clear the selection order */
1350                 
1351         EM_selectmode_set(em);  // enforce full consistent selection flags 
1352         
1353         EM_stats_update(em);
1354         
1355         if(em->totvertsel==0) {
1356                 BKE_mesh_end_editmesh(me, em);
1357                 return 0;
1358         }
1359         
1360         /* we are going to work as follows:
1361          * 1. add a linked duplicate object: this will be the new one, we remember old pointer
1362          * 2. give new object empty mesh and put in editmode
1363          * 3: do a split if needed on current editmesh.
1364          * 4. copy over: all NOT selected verts, edges, faces
1365          * 5. call load_editMesh() on the new object
1366          */
1367         
1368         /* 1 */
1369         basenew= ED_object_add_duplicate(bmain, scene, editbase, 0);    /* 0 = fully linked */
1370         ED_base_object_select(basenew, BA_DESELECT);
1371         
1372         /* 2 */
1373         basenew->object->data= menew= add_mesh(me->id.name+2);  /* empty */
1374         assign_matarar(basenew->object, give_matarar(obedit), *give_totcolp(obedit)); /* new in 2.5 */
1375         me->id.us--;
1376         make_editMesh(scene, basenew->object);
1377         emnew= menew->edit_mesh;
1378         CustomData_copy(&em->vdata, &emnew->vdata, CD_MASK_EDITMESH, CD_DEFAULT, 0);
1379         CustomData_copy(&em->edata, &emnew->edata, CD_MASK_EDITMESH, CD_DEFAULT, 0);
1380         CustomData_copy(&em->fdata, &emnew->fdata, CD_MASK_EDITMESH, CD_DEFAULT, 0);
1381         
1382         /* 3 */
1383         /* SPLIT: first make duplicate */
1384         adduplicateflag(em, SELECT);
1385         /* SPLIT: old faces have 3x flag 128 set, delete these ones */
1386         delfaceflag(em, 128);
1387         /* since we do tricky things with verts/edges/faces, this makes sure all is selected coherent */
1388         EM_selectmode_set(em);
1389         
1390         /* 4 */
1391         /* move over: everything that is selected */
1392         for(eve= em->verts.first; eve; eve= v1) {
1393                 v1= eve->next;
1394                 if(eve->f & SELECT) {
1395                         BLI_remlink(&em->verts, eve);
1396                         BLI_addtail(&emnew->verts, eve);
1397                 }
1398         }
1399         
1400         for(eed= em->edges.first; eed; eed= e1) {
1401                 e1= eed->next;
1402                 if(eed->f & SELECT) {
1403                         BLI_remlink(&em->edges, eed);
1404                         BLI_addtail(&emnew->edges, eed);
1405                 }
1406         }
1407         
1408         for(efa= em->faces.first; efa; efa= f1) {
1409                 f1= efa->next;
1410                 if (efa == em->act_face && (efa->f & SELECT)) {
1411                         EM_set_actFace(em, NULL);
1412                 }
1413
1414                 if(efa->f & SELECT) {
1415                         BLI_remlink(&em->faces, efa);
1416                         BLI_addtail(&emnew->faces, efa);
1417                 }
1418         }
1419
1420         /* 5 */
1421         load_editMesh(scene, basenew->object);
1422         free_editMesh(emnew);
1423         MEM_freeN(menew->edit_mesh);
1424         menew->edit_mesh= NULL;
1425         
1426         /* hashedges are invalid now, make new! */
1427         editMesh_set_hash(em);
1428
1429         DAG_id_flush_update(&obedit->id, OB_RECALC_DATA);       
1430         DAG_id_flush_update(&basenew->object->id, OB_RECALC_DATA);      
1431
1432         BKE_mesh_end_editmesh(me, em);
1433
1434         return 1;
1435 }
1436
1437 /* return 1: success */
1438 static int mesh_separate_material(Main *bmain, Scene *scene, Base *editbase)
1439 {
1440         Mesh *me= editbase->object->data;
1441         EditMesh *em= BKE_mesh_get_editmesh(me);
1442         unsigned char curr_mat;
1443         
1444         for (curr_mat = 1; curr_mat < editbase->object->totcol; ++curr_mat) {
1445                 /* clear selection, we're going to use that to select material group */
1446                 EM_clear_flag_all(em, SELECT);
1447                 /* select the material */
1448                 EM_select_by_material(em, curr_mat);
1449                 /* and now separate */
1450                 if(0==mesh_separate_selected(bmain, scene, editbase)) {
1451                         BKE_mesh_end_editmesh(me, em);
1452                         return 0;
1453                 }
1454         }
1455
1456         BKE_mesh_end_editmesh(me, em);
1457         return 1;
1458 }
1459
1460 /* return 1: success */
1461 static int mesh_separate_loose(Main *bmain, Scene *scene, Base *editbase)
1462 {
1463         Mesh *me;
1464         EditMesh *em;
1465         int doit= 1;
1466         
1467         me= editbase->object->data;
1468         em= BKE_mesh_get_editmesh(me);
1469         
1470         if(me->key) {
1471                 error("Can't separate with vertex keys");
1472                 BKE_mesh_end_editmesh(me, em);
1473                 return 0;
1474         }
1475         
1476         EM_clear_flag_all(em, SELECT);
1477
1478         while(doit) {
1479                 /* Select a random vert to start with */
1480                 EditVert *eve;
1481                 int tot;
1482
1483                 /* check if all verts that are visible have been done */
1484                 for(eve=em->verts.first; eve; eve= eve->next)
1485                         if(!eve->h) break;
1486                 if(eve==NULL) break; /* only hidden verts left, quit early */
1487
1488                 /* first non hidden vert */
1489                 eve->f |= SELECT;
1490                 
1491                 selectconnected_mesh_all(em);
1492                 
1493                 /* don't separate the very last part */
1494                 for(eve=em->verts.first; eve; eve= eve->next)
1495                         if((eve->f & SELECT)==0) break;
1496                 if(eve==NULL) break;
1497
1498                 tot= BLI_countlist(&em->verts);
1499
1500                 /* and now separate */
1501                 doit= mesh_separate_selected(bmain, scene, editbase);
1502
1503                 /* with hidden verts this can happen */
1504                 if(tot == BLI_countlist(&em->verts))
1505                         break;
1506         }
1507
1508         BKE_mesh_end_editmesh(me, em);
1509         return 1;
1510 }
1511
1512
1513 static int mesh_separate_exec(bContext *C, wmOperator *op)
1514 {
1515         Main *bmain= CTX_data_main(C);
1516         Scene *scene= CTX_data_scene(C);
1517         Base *base= CTX_data_active_base(C);
1518         int retval= 0, type= RNA_enum_get(op->ptr, "type");
1519         
1520         if(type == 0)
1521                 retval= mesh_separate_selected(bmain, scene, base);
1522         else if(type == 1)
1523                 retval= mesh_separate_material(bmain, scene, base);
1524         else if(type == 2)
1525                 retval= mesh_separate_loose(bmain, scene, base);
1526            
1527         if(retval) {
1528                 WM_event_add_notifier(C, NC_GEOM|ND_DATA, base->object->data);
1529                 return OPERATOR_FINISHED;
1530         }
1531         return OPERATOR_CANCELLED;
1532 }
1533
1534 void MESH_OT_separate(wmOperatorType *ot)
1535 {
1536         /* identifiers */
1537         ot->name= "Separate";
1538         ot->description= "Separate selected geometry into a new mesh";
1539         ot->idname= "MESH_OT_separate";
1540         
1541         /* api callbacks */
1542         ot->invoke= WM_menu_invoke;
1543         ot->exec= mesh_separate_exec;
1544         ot->poll= ED_operator_editmesh;
1545         
1546         /* flags */
1547         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1548         
1549         ot->prop= RNA_def_enum(ot->srna, "type", prop_separate_types, 0, "Type", "");
1550 }
1551
1552
1553 /* ******************************************** */
1554
1555 /* *************** UNDO ***************************** */
1556 /* new mesh undo, based on pushing editmesh data itself */
1557 /* reuses same code as for global and curve undo... unify that (ton) */
1558
1559 /* only one 'hack', to save memory it doesn't store the first push, but does a remake editmesh */
1560
1561 /* a compressed version of editmesh data */
1562
1563 typedef struct EditVertC
1564 {
1565         float no[3];
1566         float co[3];
1567         unsigned char f, h;
1568         short bweight;
1569         int keyindex;
1570 } EditVertC;
1571
1572 typedef struct EditEdgeC
1573 {
1574         int v1, v2;
1575         unsigned char f, h, seam, sharp, pad;
1576         short crease, bweight, fgoni;
1577 } EditEdgeC;
1578
1579 typedef struct EditFaceC
1580 {
1581         int v1, v2, v3, v4;
1582         unsigned char flag, f, h, fgonf, pad1;
1583         short mat_nr;
1584 } EditFaceC;
1585
1586 typedef struct EditSelectionC{
1587         short type;
1588         int index;
1589 }EditSelectionC;
1590
1591 typedef struct UndoMesh {
1592         EditVertC *verts;
1593         EditEdgeC *edges;
1594         EditFaceC *faces;
1595         EditSelectionC *selected;
1596         int totvert, totedge, totface, totsel;
1597         int selectmode, shapenr;
1598         RetopoPaintData *retopo_paint_data;
1599         char retopo_mode;
1600         CustomData vdata, edata, fdata;
1601 } UndoMesh;
1602
1603 /* for callbacks */
1604
1605 static void free_undoMesh(void *umv)
1606 {
1607         UndoMesh *um= umv;
1608         
1609         if(um->verts) MEM_freeN(um->verts);
1610         if(um->edges) MEM_freeN(um->edges);
1611         if(um->faces) MEM_freeN(um->faces);
1612         if(um->selected) MEM_freeN(um->selected);
1613 // XXX  if(um->retopo_paint_data) retopo_free_paint_data(um->retopo_paint_data);
1614         CustomData_free(&um->vdata, um->totvert);
1615         CustomData_free(&um->edata, um->totedge);
1616         CustomData_free(&um->fdata, um->totface);
1617         MEM_freeN(um);
1618 }
1619
1620 static void *editMesh_to_undoMesh(void *emv)
1621 {
1622         EditMesh *em= (EditMesh *)emv;
1623         UndoMesh *um;
1624         EditVert *eve;
1625         EditEdge *eed;
1626         EditFace *efa;
1627         EditSelection *ese;
1628         EditVertC *evec=NULL;
1629         EditEdgeC *eedc=NULL;
1630         EditFaceC *efac=NULL;
1631         EditSelectionC *esec=NULL;
1632         int a;
1633
1634         um= MEM_callocN(sizeof(UndoMesh), "undomesh");
1635         
1636         um->selectmode = em->selectmode;
1637         um->shapenr = em->shapenr;
1638         
1639         for(eve=em->verts.first; eve; eve= eve->next) um->totvert++;
1640         for(eed=em->edges.first; eed; eed= eed->next) um->totedge++;
1641         for(efa=em->faces.first; efa; efa= efa->next) um->totface++;
1642         for(ese=em->selected.first; ese; ese=ese->next) um->totsel++; 
1643         /* malloc blocks */
1644         
1645         if(um->totvert) evec= um->verts= MEM_callocN(um->totvert*sizeof(EditVertC), "allvertsC");
1646         if(um->totedge) eedc= um->edges= MEM_callocN(um->totedge*sizeof(EditEdgeC), "alledgesC");
1647         if(um->totface) efac= um->faces= MEM_callocN(um->totface*sizeof(EditFaceC), "allfacesC");
1648         if(um->totsel) esec= um->selected= MEM_callocN(um->totsel*sizeof(EditSelectionC), "allselections");
1649
1650         if(um->totvert) CustomData_copy(&em->vdata, &um->vdata, CD_MASK_EDITMESH, CD_CALLOC, um->totvert);
1651         if(um->totedge) CustomData_copy(&em->edata, &um->edata, CD_MASK_EDITMESH, CD_CALLOC, um->totedge);
1652         if(um->totface) CustomData_copy(&em->fdata, &um->fdata, CD_MASK_EDITMESH, CD_CALLOC, um->totface);
1653         
1654         /* now copy vertices */
1655         a = 0;
1656         for(eve=em->verts.first; eve; eve= eve->next, evec++, a++) {
1657                 VECCOPY(evec->co, eve->co);
1658                 VECCOPY(evec->no, eve->no);
1659
1660                 evec->f= eve->f;
1661                 evec->h= eve->h;
1662                 evec->keyindex= eve->keyindex;
1663                 eve->tmp.l = a; /*store index*/
1664                 evec->bweight= (short)(eve->bweight*255.0);
1665
1666                 CustomData_from_em_block(&em->vdata, &um->vdata, eve->data, a);
1667         }
1668         
1669         /* copy edges */
1670         a = 0;
1671         for(eed=em->edges.first; eed; eed= eed->next, eedc++, a++)  {
1672                 eedc->v1= (int)eed->v1->tmp.l;
1673                 eedc->v2= (int)eed->v2->tmp.l;
1674                 eedc->f= eed->f;
1675                 eedc->h= eed->h;
1676                 eedc->seam= eed->seam;
1677                 eedc->sharp= eed->sharp;
1678                 eedc->crease= (short)(eed->crease*255.0);
1679                 eedc->bweight= (short)(eed->bweight*255.0);
1680                 eedc->fgoni= eed->fgoni;
1681                 eed->tmp.l = a; /*store index*/
1682                 CustomData_from_em_block(&em->edata, &um->edata, eed->data, a);
1683         
1684         }
1685         
1686         /* copy faces */
1687         a = 0;
1688         for(efa=em->faces.first; efa; efa= efa->next, efac++, a++) {
1689                 efac->v1= (int)efa->v1->tmp.l;
1690                 efac->v2= (int)efa->v2->tmp.l;
1691                 efac->v3= (int)efa->v3->tmp.l;
1692                 if(efa->v4) efac->v4= (int)efa->v4->tmp.l;
1693                 else efac->v4= -1;
1694                 
1695                 efac->mat_nr= efa->mat_nr;
1696                 efac->flag= efa->flag;
1697                 efac->f= efa->f;
1698                 efac->h= efa->h;
1699                 efac->fgonf= efa->fgonf;
1700
1701                 efa->tmp.l = a; /*store index*/
1702
1703                 CustomData_from_em_block(&em->fdata, &um->fdata, efa->data, a);
1704         }
1705         
1706         a = 0;
1707         for(ese=em->selected.first; ese; ese=ese->next, esec++){
1708                 esec->type = ese->type;
1709                 if(ese->type == EDITVERT) a = esec->index = ((EditVert*)ese->data)->tmp.l; 
1710                 else if(ese->type == EDITEDGE) a = esec->index = ((EditEdge*)ese->data)->tmp.l; 
1711                 else if(ese->type == EDITFACE) a = esec->index = ((EditFace*)ese->data)->tmp.l;
1712         }
1713
1714 // XXX  um->retopo_paint_data= retopo_paint_data_copy(em->retopo_paint_data);
1715 //      um->retopo_mode= scene->toolsettings->retopo_mode;
1716         
1717         return um;
1718 }
1719
1720 static void undoMesh_to_editMesh(void *umv, void *emv)
1721 {
1722         EditMesh *em= (EditMesh *)emv;
1723         UndoMesh *um= (UndoMesh *)umv;
1724         EditVert *eve, **evar=NULL;
1725         EditEdge *eed;
1726         EditFace *efa;
1727         EditSelection *ese;
1728         EditVertC *evec;
1729         EditEdgeC *eedc;
1730         EditFaceC *efac;
1731         EditSelectionC *esec;
1732         int a=0;
1733
1734         free_editMesh(em);
1735         
1736         /* malloc blocks */
1737         memset(em, 0, sizeof(EditMesh));
1738                 
1739         em->selectmode = um->selectmode;
1740         em->shapenr = um->shapenr;
1741         
1742         init_editmesh_fastmalloc(em, um->totvert, um->totedge, um->totface);
1743
1744         CustomData_free(&em->vdata, 0);
1745         CustomData_free(&em->edata, 0);
1746         CustomData_free(&em->fdata, 0);
1747
1748         CustomData_copy(&um->vdata, &em->vdata, CD_MASK_EDITMESH, CD_CALLOC, 0);
1749         CustomData_copy(&um->edata, &em->edata, CD_MASK_EDITMESH, CD_CALLOC, 0);
1750         CustomData_copy(&um->fdata, &em->fdata, CD_MASK_EDITMESH, CD_CALLOC, 0);
1751
1752         /* now copy vertices */
1753
1754         if(um->totvert) evar= MEM_mallocN(um->totvert*sizeof(EditVert *), "vertex ar");
1755         for(a=0, evec= um->verts; a<um->totvert; a++, evec++) {
1756                 eve= addvertlist(em, evec->co, NULL);
1757                 evar[a]= eve;
1758
1759                 VECCOPY(eve->no, evec->no);
1760                 eve->f= evec->f;
1761                 eve->h= evec->h;
1762                 eve->keyindex= evec->keyindex;
1763                 eve->bweight= ((float)evec->bweight)/255.0f;
1764
1765                 CustomData_to_em_block(&um->vdata, &em->vdata, a, &eve->data);
1766         }
1767
1768         /* copy edges */
1769         for(a=0, eedc= um->edges; a<um->totedge; a++, eedc++) {
1770                 eed= addedgelist(em, evar[eedc->v1], evar[eedc->v2], NULL);
1771
1772                 eed->f= eedc->f;
1773                 eed->h= eedc->h;
1774                 eed->seam= eedc->seam;
1775                 eed->sharp= eedc->sharp;
1776                 eed->fgoni= eedc->fgoni;
1777                 eed->crease= ((float)eedc->crease)/255.0f;
1778                 eed->bweight= ((float)eedc->bweight)/255.0f;
1779                 CustomData_to_em_block(&um->edata, &em->edata, a, &eed->data);
1780         }
1781         
1782         /* copy faces */
1783         for(a=0, efac= um->faces; a<um->totface; a++, efac++) {
1784                 if(efac->v4 != -1)
1785                         efa= addfacelist(em, evar[efac->v1], evar[efac->v2], evar[efac->v3], evar[efac->v4], NULL, NULL);
1786                 else 
1787                         efa= addfacelist(em, evar[efac->v1], evar[efac->v2], evar[efac->v3], NULL, NULL ,NULL);
1788
1789                 efa->mat_nr= efac->mat_nr;
1790                 efa->flag= efac->flag;
1791                 efa->f= efac->f;
1792                 efa->h= efac->h;
1793                 efa->fgonf= efac->fgonf;
1794                 
1795                 CustomData_to_em_block(&um->fdata, &em->fdata, a, &efa->data);
1796         }
1797         
1798         end_editmesh_fastmalloc();
1799         if(evar) MEM_freeN(evar);
1800         
1801         em->totvert = um->totvert;
1802         em->totedge = um->totedge;
1803         em->totface = um->totface;
1804         /*restore stored editselections*/
1805         if(um->totsel){
1806                 EM_init_index_arrays(em, 1,1,1);
1807                 for(a=0, esec= um->selected; a<um->totsel; a++, esec++){
1808                         ese = MEM_callocN(sizeof(EditSelection), "Edit Selection");
1809                         ese->type = esec->type;
1810                         if(ese->type == EDITVERT) ese->data = EM_get_vert_for_index(esec->index); else
1811                         if(ese->type == EDITEDGE) ese->data = EM_get_edge_for_index(esec->index); else
1812                         if(ese->type == EDITFACE) ese->data = EM_get_face_for_index(esec->index);
1813                         BLI_addtail(&(em->selected),ese);
1814                 }
1815                 EM_free_index_arrays();
1816         }
1817
1818         /* restore total selections */
1819         EM_nvertices_selected(em);
1820         EM_nedges_selected(em);
1821         EM_nfaces_selected(em);
1822
1823 // XXX  retopo_free_paint();
1824 //      em->retopo_paint_data= retopo_paint_data_copy(um->retopo_paint_data);
1825 //      scene->toolsettings->retopo_mode= um->retopo_mode;
1826 //      if(scene->toolsettings->retopo_mode) {
1827 // XXX          if(G.vd->depths) G.vd->depths->damaged= 1;
1828 //              retopo_queue_updates(G.vd);
1829 //              retopo_paint_view_update(G.vd);
1830 //      }
1831         
1832 }
1833
1834 static void *getEditMesh(bContext *C)
1835 {
1836         Object *obedit= CTX_data_edit_object(C);
1837         if(obedit && obedit->type==OB_MESH) {
1838                 Mesh *me= obedit->data;
1839                 return me->edit_mesh;
1840         }
1841         return NULL;
1842 }
1843
1844 /* and this is all the undo system needs to know */
1845 void undo_push_mesh(bContext *C, char *name)
1846 {
1847         undo_editmode_push(C, name, getEditMesh, free_undoMesh, undoMesh_to_editMesh, editMesh_to_undoMesh, NULL);
1848 }
1849
1850
1851
1852 /* *************** END UNDO *************/
1853
1854 static EditVert **g_em_vert_array = NULL;
1855 static EditEdge **g_em_edge_array = NULL;
1856 static EditFace **g_em_face_array = NULL;
1857
1858 void EM_init_index_arrays(EditMesh *em, int forVert, int forEdge, int forFace)
1859 {
1860         EditVert *eve;
1861         EditEdge *eed;
1862         EditFace *efa;
1863         int i;
1864
1865         if (forVert) {
1866                 em->totvert= BLI_countlist(&em->verts);
1867
1868                 if(em->totvert) {
1869                         g_em_vert_array = MEM_mallocN(sizeof(*g_em_vert_array)*em->totvert, "em_v_arr");
1870
1871                         for (i=0,eve=em->verts.first; eve; i++,eve=eve->next)
1872                                 g_em_vert_array[i] = eve;
1873                 }
1874         }
1875
1876         if (forEdge) {
1877                 em->totedge= BLI_countlist(&em->edges);
1878
1879                 if(em->totedge) {
1880                         g_em_edge_array = MEM_mallocN(sizeof(*g_em_edge_array)*em->totedge, "em_e_arr");
1881
1882                         for (i=0,eed=em->edges.first; eed; i++,eed=eed->next)
1883                                 g_em_edge_array[i] = eed;
1884                 }
1885         }
1886
1887         if (forFace) {
1888                 em->totface= BLI_countlist(&em->faces);
1889
1890                 if(em->totface) {
1891                         g_em_face_array = MEM_mallocN(sizeof(*g_em_face_array)*em->totface, "em_f_arr");
1892
1893                         for (i=0,efa=em->faces.first; efa; i++,efa=efa->next)
1894                                 g_em_face_array[i] = efa;
1895                 }
1896         }
1897 }
1898
1899 void EM_free_index_arrays(void)
1900 {
1901         if (g_em_vert_array) MEM_freeN(g_em_vert_array);
1902         if (g_em_edge_array) MEM_freeN(g_em_edge_array);
1903         if (g_em_face_array) MEM_freeN(g_em_face_array);
1904         g_em_vert_array = NULL;
1905         g_em_edge_array = NULL;
1906         g_em_face_array = NULL;
1907 }
1908
1909 EditVert *EM_get_vert_for_index(int index)
1910 {
1911         return g_em_vert_array?g_em_vert_array[index]:NULL;
1912 }
1913
1914 EditEdge *EM_get_edge_for_index(int index)
1915 {
1916         return g_em_edge_array?g_em_edge_array[index]:NULL;
1917 }
1918
1919 EditFace *EM_get_face_for_index(int index)
1920 {
1921         return g_em_face_array?g_em_face_array[index]:NULL;
1922 }
1923
1924 /* can we edit UV's for this mesh?*/
1925 int EM_texFaceCheck(EditMesh *em)
1926 {
1927         /* some of these checks could be a touch overkill */
1928         if (    (em) &&
1929                         (em->faces.first) &&
1930                         (CustomData_has_layer(&em->fdata, CD_MTFACE)))
1931                 return 1;
1932         return 0;
1933 }
1934
1935 /* can we edit colors for this mesh?*/
1936 int EM_vertColorCheck(EditMesh *em)
1937 {
1938         /* some of these checks could be a touch overkill */
1939         if (    (em) &&
1940                         (em->faces.first) &&
1941                         (CustomData_has_layer(&em->fdata, CD_MCOL)))
1942                 return 1;
1943         return 0;
1944 }
1945
1946
1947 void em_setup_viewcontext(bContext *C, ViewContext *vc)
1948 {
1949         view3d_set_viewcontext(C, vc);
1950         
1951         if(vc->obedit) {
1952                 Mesh *me= vc->obedit->data;
1953                 vc->em= me->edit_mesh;
1954         }
1955 }