part 1 of cleaning up my little array macro library to be a formal API. also removed...
[blender.git] / source / blender / bmesh / intern / editmesh_to_bmesh.c
1
2 #include "MEM_guardedalloc.h"
3 #include "BKE_customdata.h" 
4 #include "DNA_listBase.h"
5 #include "DNA_meshdata_types.h"
6 #include "DNA_object_types.h"
7 #include "DNA_scene_types.h"
8 #include <string.h>
9 #include "BKE_utildefines.h"
10 #include "BKE_mesh.h"
11 #include "BKE_global.h"
12 #include "BKE_DerivedMesh.h"
13 #include "BKE_cdderivedmesh.h"
14
15 #include "BLI_editVert.h"
16 #include "mesh_intern.h"
17 #include "ED_mesh.h"
18
19 #include "BLI_blenlib.h"
20 #include "BLI_edgehash.h"
21 #include "BLI_array.h"
22
23 #include "bmesh.h"
24
25 /*
26  * EDITMESH TO BMESH.C
27  *
28  * This file contains functions
29  * for converting an editmesh
30  * into a Bmesh
31  *
32 */
33
34 /*
35  * EDITMESH CORNERS TO LOOPS
36  * 
37  * Converts editmesh face corner data
38  * (UVs, Vert colors, ect) to N-Gon 
39  * face-edge ('loop') data.
40  *
41 */
42
43 static void editmesh_corners_to_loops(BMesh *bm, CustomData *facedata, void *face_block, BMFace *f,int numCol, int numTex){
44         int i, j;
45         BMLoop *l;
46         MTFace *texface;
47         MTexPoly *texpoly;
48         MCol *mcol;
49         MLoopCol *mloopcol;
50         MLoopUV *mloopuv;
51         BMIter iter;
52
53         for(i=0; i < numTex; i++){
54                 texface = CustomData_em_get_n(facedata, face_block, CD_MTFACE, i);
55                 texpoly = CustomData_bmesh_get_n(&bm->pdata, f->head.data, CD_MTEXPOLY, i);
56                 
57                 texpoly->tpage = texface->tpage;
58                 texpoly->flag = texface->flag;
59                 texpoly->transp = texface->transp;
60                 texpoly->mode = texface->mode;
61                 texpoly->tile = texface->tile;
62                 texpoly->unwrap = texface->unwrap;
63                 
64                 for (j=0, l=BMIter_New(&iter, bm, BM_LOOPS_OF_FACE, f); l; j++, l=BMIter_Step(&iter)) {
65                         mloopuv = CustomData_bmesh_get_n(&bm->ldata, l->head.data, CD_MLOOPUV, i);
66                         mloopuv->uv[0] = texface->uv[j][0];
67                         mloopuv->uv[1] = texface->uv[j][1];
68                 }
69
70         }
71         for(i=0; i < numCol; i++){
72                 mcol = CustomData_em_get_n(facedata, face_block, CD_MCOL, i);
73                 for (j=0, l=BMIter_New(&iter, bm, BM_LOOPS_OF_FACE, f); l; j++, l=BMIter_Step(&iter)) {
74                         mloopcol = CustomData_bmesh_get_n(&bm->ldata, l->head.data, CD_MLOOPCOL, i);
75                         mloopcol->r = mcol[j].r;
76                         mloopcol->g = mcol[j].g;
77                         mloopcol->b = mcol[j].b;
78                         mloopcol->a = mcol[j].a;
79                 }
80         }
81 }
82
83 /*
84  * EDITVERT TO BMVert
85  *
86  * Converts an editvert to
87  * a BMVert.
88  *
89 */
90
91 static BMVert *editvert_to_BMVert(BMesh *bm, BMOperator *op, EditMesh *em, EditVert *eve)
92 {
93                 BMVert *v = NULL;
94
95                 v = BM_Make_Vert(bm, eve->co, NULL);
96                 VECCOPY(v->no, eve->no);
97
98                 /*transfer flags*/
99                 v->head.flag = eve->h ? BM_HIDDEN : 0;
100                 if(eve->f & SELECT) BM_Select_Vert(bm, v, 1);
101                 v->bweight = eve->bweight;
102
103                 BMO_Insert_MapPointer(bm, op, "map", eve, v);
104
105                 /*Copy Custom Data*/
106                 CustomData_bmesh_copy_data(&em->vdata, &bm->vdata, eve->data, &v->head.data);
107                 
108                 return v;
109 }       
110
111 /*
112  * EDITEDGE TO BMEdge
113  *
114  * Converts an editedge to 
115  * a BMEdge
116  *
117 */
118
119 static void editedge_to_BMEdge_internal(BMesh *bm, BMOperator *op, EditMesh *em, BMEdge *e, EditEdge *eed)
120 {
121         e->crease = eed->crease;
122         e->bweight = eed->bweight;
123         
124         BM_Select(bm, e, eed->f & SELECT);
125         e->head.flag |= eed->seam ? BM_SEAM : 0;
126         e->head.flag |= eed->h & 1 ? BM_HIDDEN : 0;
127         e->head.flag |= eed->h & EM_FGON ? BM_FGON : 0;
128         e->head.flag |= eed->sharp ? BM_SHARP : 0;
129
130         CustomData_bmesh_copy_data(&em->edata, &bm->edata, eed->data, &e->head.data);
131
132         BMO_Insert_MapPointer(bm, op, "map", eed, e);
133 }
134
135 static BMEdge *editedge_to_BMEdge(BMesh *bm, BMOperator *op, EditMesh *em, EditEdge *eed)
136 {
137                 BMVert *v1 = NULL, *v2 = NULL;
138                 BMEdge *e = NULL;
139                 
140                 v1 = eed->v1->tmp.p;
141                 v2 = eed->v2->tmp.p;
142         
143                 e = BM_Make_Edge(bm, v1, v2,NULL, 0); 
144
145                 editedge_to_BMEdge_internal(bm, op, em, e, eed);
146
147                 return e;
148 }
149 /*
150  * EDITFACE TO BMFace
151  *
152  * Converts an editface to a BMFace.
153  * Note that this also convert per-face
154  * corner data as well.
155  *
156 */
157
158 static BMFace *editface_to_BMFace(BMesh *bm, BMOperator *op, EditMesh *em, EditFace *efa, int numCol, int numTex)
159 {
160                 BMVert *v1 = NULL, *v2 = NULL;
161                 BMFace *f = NULL;
162                 BMEdge *edar[4];
163                 int len;
164
165                 edar[0] = BM_Make_Edge(bm, efa->v1->tmp.p, efa->v2->tmp.p, NULL, 1); 
166                 edar[1] = BM_Make_Edge(bm, efa->v2->tmp.p, efa->v3->tmp.p, NULL, 1); 
167                 if(efa->v4){
168                         edar[2] = BM_Make_Edge(bm, efa->v3->tmp.p, efa->v4->tmp.p, NULL, 1); 
169                         edar[3] = BM_Make_Edge(bm, efa->v4->tmp.p, efa->v1->tmp.p, NULL, 1); 
170                 }else{
171                         edar[2] = BM_Make_Edge(bm, efa->v3->tmp.p, efa->v1->tmp.p, NULL, 1); 
172                 }
173
174                 editedge_to_BMEdge_internal(bm, op, em, edar[0], efa->e1);
175                 editedge_to_BMEdge_internal(bm, op, em, edar[1], efa->e2);
176                 editedge_to_BMEdge_internal(bm, op, em, edar[2], efa->e3);
177                 if(efa->v4)
178                         editedge_to_BMEdge_internal(bm, op, em, edar[3], efa->e4);
179
180
181                 if(efa->e1->fgoni) edar[0]->head.flag |= BM_FGON;
182                 if(efa->e2->fgoni) edar[1]->head.flag |= BM_FGON;
183                 if(efa->e3->fgoni) edar[2]->head.flag |= BM_FGON;
184                 if(efa->v4 && efa->e4->fgoni) edar[3]->head.flag |= BM_FGON;
185
186                 if(efa->v4) len = 4;
187                 else len = 3;
188
189                 /*find v1 and v2*/
190                 v1 = efa->v1->tmp.p;
191                 v2 = efa->v2->tmp.p;
192
193                 f = BM_Make_Ngon(bm, v1, v2, edar, len, 0);
194                 
195                 VECCOPY(f->no, efa->n);
196
197                 BMO_Insert_MapPointer(bm, op, "map", efa, f);
198
199                 f->head.flag = 0;
200                 f->mat_nr = efa->mat_nr;
201                 if(efa->f & SELECT) BM_Select_Face(bm, f, 1);
202                 if (efa->flag & ME_SMOOTH) f->head.flag |= BM_SMOOTH;
203                 if(efa->h) f->head.flag |= BM_HIDDEN;
204
205                 if (efa == em->act_face) f->head.flag |= BM_ACTIVE;
206                 
207                 CustomData_bmesh_copy_data(&em->fdata, &bm->pdata, efa->data, &f->head.data);
208                 editmesh_corners_to_loops(bm, &em->fdata, efa->data, f,numCol,numTex);
209
210                 return f;
211 }
212
213 /*
214  * BMESH FGONCONVERT
215  *
216  * This function and its associated structures
217  * /helpers (fgonsort, sortfgon, fuse_fgon) are
218  * used to convert f-gons to bmesh n-gons. This
219  * is accomplished by sorting a list of fgon faces
220  * such that faces that are part of the same fgon
221  * are next to each other. These faces are then
222  * converted as is into bmesh faces and
223  * fused togather.
224  *
225  * Note that currently, there is no support for 
226  * holes in faces in the bmesh structure, so 
227  * f-gons with holes will only partially convert.
228  *
229 */
230
231 typedef struct fgonsort {
232         unsigned long x;
233         struct EditFace *efa;
234         struct BMFace *f;
235         int done;
236 }fgonsort;
237
238 static int sortfgon(const void *v1, const void *v2)
239 {
240         const struct fgonsort *x1=v1, *x2=v2;
241         
242         if( x1->x > x2->x ) return 1;
243         else if( x1->x < x2->x) return -1;
244         return 0;
245 }
246
247 static void fuse_fgon(BMesh *bm, BMFace *f)
248 {
249         BMFace *sf;
250         BMLoop *l;
251         int done, act=0;
252
253         sf = f;
254         done = 0;
255         while(!done){
256                 done = 1;
257                 l = sf->loopbase;
258                 do{
259                         if(l->e->head.flag & BM_FGON) { 
260                                 if (l->f->head.flag & BM_ACTIVE) act = BM_ACTIVE;
261                                 if (((BMLoop*)l->radial.next->data)->f->head.flag & BM_ACTIVE) act = BM_ACTIVE;
262
263                                 sf = BM_Join_Faces(bm,l->f, ((BMLoop*)l->radial.next->data)->f, l->e);
264                                 if (!sf) {
265                                         //tesselation error
266                                         break;
267                                 }
268
269                                 sf->head.flag |= act;
270                                 if(sf){
271                                         done = 0;
272                                         break;
273                                 } else { /*we have to get out of here...*/
274                                         return;
275                                 }
276                         }
277                         l = ((BMLoop*)(l->head.next));
278                 }while(l != sf->loopbase);
279         }
280 }
281
282 static BM_fgonconvert(BMesh *bm, BMOperator *op, EditMesh *em, int numCol, int numTex)
283 {
284         EditFace *efa;
285         BMFace *f;
286         BMIter iter;
287         struct fgonsort *sortblock, *sb, *sb1;
288         int a, b, amount=0;
289         
290         /*
291         for (efa=em->faces.first; efa; efa=efa->next) {
292                 f = editface_to_BMFace(bm, em, efa, numCol, numTex);
293         }
294
295         for (f=bm->polys.first; f; f=f->head.next) {
296                 fuse_fgon(bm, f);
297         }
298
299         return;*/
300
301         EM_fgon_flags(em);
302
303         /*zero out efa->tmp, we store fgon index here*/
304         for(efa = em->faces.first; efa; efa = efa->next){ 
305                 efa->tmp.l = 0;
306                 amount++;
307         }
308         /*go through and give each editface an fgon index*/
309         for(efa = em->faces.first; efa; efa = efa->next){
310                 if(efa->e1->fgoni) efa->tmp.l = efa->e1->fgoni;
311                 else if(efa->e2->fgoni) efa->tmp.l = efa->e2->fgoni;
312                 else if(efa->e3->fgoni) efa->tmp.l = efa->e3->fgoni;
313                 else if(efa->e4 && efa->e4->fgoni) efa->tmp.l = efa->e4->fgoni;
314         }
315
316         sb= sortblock= MEM_mallocN(sizeof(fgonsort)* amount,"fgon sort block");
317
318         for(efa = em->faces.first; efa; efa=efa->next){
319                 sb->x = efa->tmp.l;
320                 sb->efa = efa;
321                 sb->done = 0;
322                 sb++;
323         }
324
325         qsort(sortblock, amount, sizeof(fgonsort), sortfgon);
326
327         sb = sortblock;
328         for(a=0; a<amount; a++, sb++) {
329                 if(sb->x && sb->done == 0){
330                         /*first pass: add in faces for this fgon*/
331                         for(b=a, sb1 = sb; b<amount && sb1->x == sb->x; b++, sb1++){
332                                 efa = sb1->efa;
333                                 sb1->f = editface_to_BMFace(bm, op, em, efa, numCol, numTex);
334                                 sb1->done = 1;
335                         }
336                         /*fuse fgon*/
337                         fuse_fgon(bm, sb->f);
338                 }
339         }
340         MEM_freeN(sortblock);
341 }
342
343 /*
344  * TAG WIRE EDGES
345  *
346  * Flags editedges 'f1' member
347  * if the edge has no faces.
348  *
349 */
350
351 static void tag_wire_edges(EditMesh *em){
352         EditFace *efa;
353         EditEdge *eed;
354         for(eed = em->edges.first; eed; eed = eed->next) eed->f1 = 1;
355         for(efa = em->faces.first; efa; efa = efa->next){
356                 efa->e1->f1 = 0;
357                 efa->e2->f1 = 0;
358                 efa->e3->f1 = 0;
359                 if(efa->e4) efa->e4->f1 = 0;
360         }
361 }
362
363 /*
364  * EDITMESH TO BMESH
365  *
366  * Function to convert an editmesh to a bmesh
367  * Currently all custom data as well as 
368  * f-gons should be converted correctly.
369  *
370 */
371
372 BMesh *editmesh_to_bmesh_intern(EditMesh *em, BMesh *bm, BMOperator *op) {
373         BMVert *v;
374         EditVert *eve;
375         EditEdge *eed;
376         EditFace *efa;
377         BMEdge *e;
378         BMIter iter;
379         int allocsize[4] = {512,512,2048,512}, numTex, numCol;
380
381         /*make sure to update FGon flags*/
382         EM_fgon_flags(em);
383
384         /*copy custom data layout*/
385         CustomData_copy(&em->vdata, &bm->vdata, CD_MASK_BMESH, CD_CALLOC, 0);
386         CustomData_copy(&em->edata, &bm->edata, CD_MASK_BMESH, CD_CALLOC, 0);
387         CustomData_copy(&em->fdata, &bm->pdata, CD_MASK_BMESH, CD_CALLOC, 0);
388
389         /*copy face corner data*/
390         CustomData_to_bmeshpoly(&em->fdata, &bm->pdata, &bm->ldata, 0, 0);
391         
392         CustomData_bmesh_init_pool(&bm->vdata, allocsize[0]);
393         CustomData_bmesh_init_pool(&bm->edata, allocsize[1]);
394         CustomData_bmesh_init_pool(&bm->ldata, allocsize[2]);
395         CustomData_bmesh_init_pool(&bm->pdata, allocsize[3]);
396
397         /*needed later*/
398         numTex = CustomData_number_of_layers(&bm->pdata, CD_MTEXPOLY);
399         numCol = CustomData_number_of_layers(&bm->ldata, CD_MLOOPCOL);
400
401         /*copy over selection mode*/
402         bm->selectmode = 0;
403         if(em->selectmode & SCE_SELECT_VERTEX) bm->selectmode |= SCE_SELECT_VERTEX;
404         if(em->selectmode & SCE_SELECT_EDGE) bm->selectmode |= SCE_SELECT_EDGE;
405         if(em->selectmode & SCE_SELECT_FACE) bm->selectmode |= SCE_SELECT_FACE;
406
407
408         /*begin editloop*/
409         //BM_Begin_Edit(bm);
410
411         /*tag wire edges*/
412         tag_wire_edges(em);
413
414         /*add verts*/
415         for(eve = em->verts.first; eve; eve = eve->next){
416                 v = editvert_to_BMVert(bm, op, em, eve);
417                 eve->tmp.p = v;
418         }
419         /*convert f-gons*/
420         BM_fgonconvert(bm, op, em, numCol, numTex);
421         
422         /*clean up any dangling fgon flags*/
423         for (e=BMIter_New(&iter, bm, BM_EDGES_OF_MESH, NULL); e; e=BMIter_Step(&iter)){
424                 e->head.flag &= ~BM_FGON;
425         }
426
427         /*do quads + triangles*/
428         for(efa = em->faces.first; efa; efa = efa->next){
429                 if(!efa->tmp.l) editface_to_BMFace(bm, op, em, efa, numCol, numTex);
430         }
431
432         /*add wire edges*/      
433         for(eed = em->edges.first; eed; eed = eed->next){
434                 if(eed->f1) editedge_to_BMEdge(bm, op, em, eed);
435         }
436         //BM_end_edit(bm, BM_CALC_NORM);
437         return bm;
438 }
439
440 void edit2bmesh_exec(BMesh *bmesh, BMOperator *op)
441 {
442         editmesh_to_bmesh_intern(BMO_Get_Pnt(op, "em"), bmesh, op);
443 }
444
445 BMesh *editmesh_to_bmesh(EditMesh *em)
446 {
447         BMOperator conv;
448         BMesh *bm;
449         int allocsize[4] = {512,512,2048,512};
450
451         /*allocate a bmesh*/
452         bm = BM_Make_Mesh(allocsize);
453
454         BMO_Init_Op(&conv, "editmesh_to_bmesh");
455         BMO_Set_Pnt(&conv, "em", em);
456         BMO_Exec_Op(bm, &conv);
457         BMO_Finish_Op(bm, &conv);
458
459         return bm;
460 }
461
462 BMesh *init_editmesh_to_bmesh(EditMesh *em, BMOperator *op)
463 {
464         BMesh *bm;
465         int allocsize[4] = {512,512,2048,512}, numTex, numCol;
466
467         /*allocate a bmesh*/
468         bm = BM_Make_Mesh(allocsize);
469
470         BMO_Init_Op(op, "editmesh_to_bmesh");
471         BMO_Set_Pnt(op, "em", em);
472
473         return bm;
474 }