1928e85fa229c84addc3f89892fa8fd83b01e3db
[blender.git] / source / blender / bmesh / intern / bmesh_construct.c
1 /**
2  * bmesh_construct.c    August 2008
3  *
4  *      BM construction functions.
5  *
6  * ***** BEGIN GPL LICENSE BLOCK *****
7  *
8  * This program is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version.
12  * about this.  
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software Foundation,
21  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
22  *
23  * The Original Code is Copyright (C) 2007 Blender Foundation.
24  * All rights reserved.
25  *
26  * The Original Code is: all of this file.
27  *
28  * Contributor(s): Geoffrey Bantle.
29  *
30  * ***** END GPL LICENSE BLOCK *****
31  */
32
33 #include "MEM_guardedalloc.h"
34 #include "BKE_customdata.h" 
35 #include "BKE_utildefines.h"
36
37 #include "DNA_meshdata_types.h"
38 #include "DNA_mesh_types.h"
39
40 #include "bmesh.h"
41 #include "bmesh_private.h"
42
43 #include "math.h"
44 #include "stdio.h"
45 #include "string.h"
46
47 #define SELECT 1
48
49 /*prototypes*/
50 static void bm_copy_loop_attributes(BMesh *source_mesh, BMesh *target_mesh,
51                                     BMLoop *source_loop, BMLoop *target_loop);
52
53 /*
54  * BM_CONSTRUCT.C
55  *
56  * This file contains functions for making and destroying
57  * individual elements like verts, edges and faces.
58  *
59 */
60
61 /*
62  * BMESH MAKE VERT
63  *
64  * Creates a new vertex and returns a pointer
65  * to it. If a pointer to an example vertex is
66  * passed in, it's custom data and properties
67  * will be copied to the new vertex.
68  *
69 */
70
71 BMVert *BM_Make_Vert(BMesh *bm, float co[3], BMVert *example)
72 {
73         BMVert *v = NULL;
74         v = bmesh_mv(bm, co);
75         if(example)
76                 CustomData_bmesh_copy_data(&bm->vdata, &bm->vdata, example->head.data, &v->head.data);
77         return v;
78 }
79
80 /*
81  * BMESH MAKE EDGE
82  *
83  * Creates a new edge betweeen two vertices and returns a
84  * pointer to it. If 'nodouble' equals 1, then a check is
85  * is done to make sure that an edge between those two vertices
86  * does not already exist. If it does, that edge is returned instead
87  * of creating a new one.
88  *
89  * If a new edge is created, and a pointer to an example edge is
90  * provided, it's custom data and properties will be copied to the
91  * new edge.
92  *
93 */
94
95 BMEdge *BM_Make_Edge(BMesh *bm, BMVert *v1, BMVert *v2, BMEdge *example, int nodouble)
96 {
97         BMEdge *e = NULL;
98         
99         if(nodouble) /*test if edge already exists.*/
100                 e = bmesh_disk_existedge(v1, v2);
101
102         if(!e){
103                 e = bmesh_me(bm, v1, v2);
104
105                 if(example)
106                         CustomData_bmesh_copy_data(&bm->edata, &bm->edata, example->head.data, &e->head.data);
107         }
108         
109         return e;
110         
111 }
112
113 /*
114  * BMESH MAKE QUADTRIANGLE
115  *
116  * Creates a new quad or triangle from
117  * a list of 3 or 4 vertices. If nodouble
118  * equals 1, then a check is done to see
119  * if a face with these vertices already
120  * exists and returns it instead. If a pointer
121  * to an example face is provided, it's custom
122  * data and properties will be copied to the new
123  * face.
124  *
125  * Note that the winding of the face is determined
126  * by the order of the vertices in the vertex array
127  *
128 */
129
130 BMFace *BM_Make_QuadTri(BMesh *bm, BMVert *v1, BMVert *v2, BMVert *v3, 
131                         BMVert *v4, BMFace *example, int nodouble)
132 {
133         BMEdge *edar[4];
134         BMVert *vtar[4];
135
136         edar[0] = bmesh_disk_existedge(v1, v2);
137         edar[1] = bmesh_disk_existedge(v2, v3);
138         edar[2] = bmesh_disk_existedge(v3, v4? v4 : v1);
139         if (v4) edar[3] = bmesh_disk_existedge(v4, v1);
140         else edar[3] = NULL;
141
142         if (!edar[0]) edar[0] = BM_Make_Edge(bm, v1, v2, NULL, 0);
143         if (!edar[1]) edar[1] = BM_Make_Edge(bm, v2, v3, NULL, 0);
144         if (!edar[2]) edar[2] = BM_Make_Edge(bm, v3, v4?v4:v1, NULL, 0);
145         if (!edar[0] && v4) edar[0] = BM_Make_Edge(bm, v4, v1, NULL, 0);
146
147         vtar[0] = v1;
148         vtar[1] = v2;
149         vtar[2] = v3;
150         vtar[3] = v4;
151
152         return BM_Make_Quadtriangle(bm, vtar, edar, v4?4:3, example, nodouble);
153 }
154
155 /*remove the edge array bits from this. Its not really needed?*/
156 BMFace *BM_Make_Quadtriangle(BMesh *bm, BMVert **verts, BMEdge **edges, int len, BMFace *example, int nodouble)
157 {
158         BMEdge *edar[4];
159         BMFace *f = NULL;
160         int overlap = 0;
161
162         edar[0] = edar[1] = edar[2] = edar[3] = NULL;
163         
164         if(edges){
165                 edar[0] = edges[0];
166                 edar[1] = edges[1];
167                 edar[2] = edges[2];
168                 if(len == 4) edar[3] = edges[3];
169         }else{
170                 edar[0] = bmesh_disk_existedge(verts[0],verts[1]);
171                 edar[1] = bmesh_disk_existedge(verts[1],verts[2]);
172                 if(len == 4){
173                         edar[2] = bmesh_disk_existedge(verts[2],verts[3]);
174                         edar[3] = bmesh_disk_existedge(verts[3],verts[0]);
175
176                 }else{
177                         edar[2] = bmesh_disk_existedge(verts[2],verts[0]);
178                 }
179         }
180         
181         if(nodouble){
182                 /*check if face exists or overlaps*/
183                 if(len == 4){
184                         overlap = BM_Exist_Face_Overlaps(bm, verts, len, &f);
185                 }else{
186                         overlap = BM_Exist_Face_Overlaps(bm, verts, len, &f);
187                 }
188         }
189
190         /*make new face*/
191         if((!f) && (!overlap)){
192                 if(!edar[0]) edar[0] = bmesh_me(bm, verts[0], verts[1]);
193                 if(!edar[1]) edar[1] = bmesh_me(bm, verts[1], verts[2]);
194                 if(len == 4){
195                         if(!edar[2]) edar[2] = bmesh_me(bm, verts[2], verts[3]);
196                         if(!edar[3]) edar[3] = bmesh_me(bm, verts[3], verts[0]); 
197                 } else {
198                         if(!edar[2]) edar[2] = bmesh_me(bm, verts[2], verts[0]);
199                 }
200         
201                 if(len == 4) f = bmesh_mf(bm, verts[0], verts[1], edar, 4);
202                 else f = bmesh_mf(bm, verts[0], verts[1], edar, 3);
203         
204                 if(example)
205                         CustomData_bmesh_copy_data(&bm->pdata, &bm->pdata, example->head.data, &f->head.data);
206
207         }
208
209         return f;
210 }
211
212
213 /*copies face data from shared adjacent faces*/
214 void BM_Face_CopyShared(BMesh *bm, BMFace *f) {
215         BMIter iter;
216         BMLoop *l, *l2;
217
218         if (!f) return;
219
220         l=BMIter_New(&iter, bm, BM_LOOPS_OF_FACE, f);
221         for (; l; l=BMIter_Step(&iter)) {
222                 l2 = l->radial.next->data;
223                 
224                 if (l2 && l2 != l) {
225                         if (l2->v == l->v) {
226                                 bm_copy_loop_attributes(bm, bm, l2, l);
227                         } else {
228                                 l2 = (BMLoop*) l2->head.next;
229                                 bm_copy_loop_attributes(bm, bm, l2, l);
230                         }
231                 }
232         }
233 }
234
235 /*
236  * BMESH MAKE NGON
237  *
238  * Attempts to make a new Ngon from a list of edges.
239  * If nodouble equals one, a check for overlaps or existing
240  * 
241  * 
242  *
243 */
244 #define VERT_BUF_SIZE 100
245 BMFace *BM_Make_Ngon(BMesh *bm, BMVert *v1, BMVert *v2, BMEdge **edges, int len, int nodouble)
246 {
247         BMVert *vert_buf[VERT_BUF_SIZE];
248         BMVert **verts = vert_buf, *lastv;
249         BMFace *f = NULL;
250         int overlap = 0, i, j;
251         
252         /*note: need to make sure this is correct*/
253         if(bmesh_verts_in_edge(v1,v2,edges[0]) == 0) {
254                 if (v1 == edges[0]->v1)
255                         v2 = edges[0]->v2;
256                 else {
257                         v1 = edges[0]->v2;
258                         v2 = edges[0]->v1;
259                 }
260         }
261
262         if(nodouble) {
263                 if(len > VERT_BUF_SIZE)
264                         verts = MEM_callocN(sizeof(BMVert *) * len, "bmesh make ngon vertex array");
265                 
266                 /*if ((edges[i]->v1 == edges[i]->v1) || 
267                    (edges[i]->v1 == edges[i]->v2))
268                 {
269                         lastv = edges[i]->v2;
270                 } else lastv = edges[i]->v1;
271                 verts[0] = lastv;
272
273                 for (i=1; i<len; i++) {
274                         if (!BMO_TestFlag
275                 }*/
276
277                 /*clear flags first*/
278                 for(i = 0; i < len; i++){
279                         BMO_ClearFlag(bm, edges[i]->v1, BM_EDGEVERT);
280                         BMO_ClearFlag(bm, edges[i]->v2, BM_EDGEVERT);
281                 }
282
283                 for(i = 0, j=0; i < len; i++){
284                         if(!BMO_TestFlag(bm, edges[i]->v1, BM_EDGEVERT)){
285                                 BMO_SetFlag(bm, edges[i]->v1, BM_EDGEVERT);
286                                 verts[j++] = edges[i]->v1;
287                         }
288                         if(!BMO_TestFlag(bm, edges[i]->v2, BM_EDGEVERT)) {
289                                 BMO_SetFlag(bm, edges[i]->v2, BM_EDGEVERT);
290                                 verts[j++] = edges[i]->v2;
291                         }
292                 }
293                 
294                 if (j != len) {
295                         /*sanity check*/
296                         return NULL;
297                 }
298
299                 overlap = BM_Face_Exists(bm, verts, len, &f);
300                 
301                 /*clear flags*/
302                 for(i = 0; i < len; i++){
303                         BMO_ClearFlag(bm, edges[i]->v1, BM_EDGEVERT);
304                         BMO_ClearFlag(bm, edges[i]->v2, BM_EDGEVERT);
305                 }
306                 
307                 if(len > VERT_BUF_SIZE)
308                         MEM_freeN(verts);
309         }
310
311         if((!f) && (!overlap)) {
312                 f = bmesh_mf(bm, v1, v2, edges, len);
313         } else return NULL;
314
315         return f;
316 }
317
318
319 /*bmesh_make_face_from_face(BMesh *bm, BMFace *source, BMFace *target) */
320
321
322 /*
323  * REMOVE TAGGED XXX
324  *
325  * Called by operators to remove elements that they have marked for
326  * removal.
327  *
328 */
329
330 void BM_remove_tagged_faces(BMesh *bm, int flag)
331 {
332         BMHeader *current, *next;
333
334         current = bm->polys.first;
335         while(current){
336                 next = current->next;
337                 if(BMO_TestFlag(bm, current, flag)) bmesh_kf(bm, (BMFace*)current);
338                 current = next;
339         }
340 }
341 void BM_remove_tagged_edges(BMesh *bm, int flag)
342 {
343         BMHeader *current, *next;
344         
345         current = bm->edges.first;
346         
347         while(current){
348                 next = current->next;
349                 if(BMO_TestFlag(bm, current, flag)) bmesh_ke(bm, (BMEdge*)current);
350                 current = next;
351         }
352 }
353
354 void BM_remove_tagged_verts(BMesh *bm, int flag)
355 {
356         BMHeader *current, *next;
357
358         current = bm->verts.first;
359
360         while(current){
361                 next = current->next;
362                 if(BMO_TestFlag(bm, current, flag)) bmesh_kv(bm,(BMVert*)current);
363                 current = next;
364         }
365 }
366
367 static void bm_copy_vert_attributes(BMesh *source_mesh, BMesh *target_mesh, BMVert *source_vertex, BMVert *target_vertex)
368 {
369         CustomData_bmesh_copy_data(&source_mesh->vdata, &target_mesh->vdata, source_vertex->head.data, &target_vertex->head.data);      
370         target_vertex->bweight = source_vertex->bweight;
371 }
372
373 static void bm_copy_edge_attributes(BMesh *source_mesh, BMesh *target_mesh, BMEdge *source_edge, BMEdge *target_edge)
374 {
375         CustomData_bmesh_copy_data(&source_mesh->edata, &target_mesh->edata, source_edge->head.data, &target_edge->head.data);
376         target_edge->crease = source_edge->crease;
377         target_edge->bweight = source_edge->bweight;
378 }
379
380 static void bm_copy_loop_attributes(BMesh *source_mesh, BMesh *target_mesh, BMLoop *source_loop, BMLoop *target_loop)
381 {
382         CustomData_bmesh_copy_data(&source_mesh->ldata, &target_mesh->ldata, source_loop->head.data, &target_loop->head.data);
383 }
384
385 static void bm_copy_face_attributes(BMesh *source_mesh, BMesh *target_mesh, BMFace *source_face, BMFace *target_face)
386 {
387         CustomData_bmesh_copy_data(&source_mesh->pdata, &target_mesh->pdata, source_face->head.data, &target_face->head.data);  
388         target_face->mat_nr = source_face->mat_nr;
389 }
390
391 /*Todo: Special handling for hide flags?*/
392
393 void BM_Copy_Attributes(BMesh *source_mesh, BMesh *target_mesh, void *source, void *target)
394 {
395         BMHeader *sheader = source, *theader = target;
396         
397         if(sheader->type != theader->type)
398                 return;
399
400         /*First we copy select*/
401         if(BM_Selected(source_mesh, source)) BM_Select(target_mesh, target, 1);
402         
403         /*Now we copy flags*/
404         theader->flag = sheader->flag;
405         
406         /*Copy specific attributes*/
407         if(theader->type == BM_VERT)
408                 bm_copy_vert_attributes(source_mesh, target_mesh, (BMVert*)source, (BMVert*)target);
409         else if(theader->type == BM_EDGE)
410                 bm_copy_edge_attributes(source_mesh, target_mesh, (BMEdge*)source, (BMEdge*)target);
411         else if(theader->type == BM_LOOP)
412                 bm_copy_loop_attributes(source_mesh, target_mesh, (BMLoop*)source, (BMLoop*)target);
413         else if(theader->type == BM_FACE)
414                 bm_copy_face_attributes(source_mesh, target_mesh, (BMFace*)source, (BMFace*)target);
415 }
416
417 BMesh *BM_Copy_Mesh(BMesh *bmold)
418 {
419         BMesh *bm;
420         BMVert *v, *v2, **vtable = NULL;
421         V_DECLARE(vtable);
422         BMEdge *e, *e2, **edges = NULL, **etable = NULL;
423         V_DECLARE(edges);
424         V_DECLARE(etable);
425         BMLoop *l, *l2, **loops = NULL;
426         V_DECLARE(loops);
427         BMFace *f, *f2, **ftable = NULL;
428         V_DECLARE(ftable);
429         BMEditSelection *ese;
430         BMIter iter, liter;
431         int allocsize[4] = {512,512,2048,512}, numTex, numCol;
432         int i, j;
433
434         /*allocate a bmesh*/
435         bm = BM_Make_Mesh(allocsize);
436
437         CustomData_copy(&bmold->vdata, &bm->vdata, CD_MASK_BMESH, CD_CALLOC, 0);
438         CustomData_copy(&bmold->edata, &bm->edata, CD_MASK_BMESH, CD_CALLOC, 0);
439         CustomData_copy(&bmold->ldata, &bm->ldata, CD_MASK_BMESH, CD_CALLOC, 0);
440         CustomData_copy(&bmold->pdata, &bm->pdata, CD_MASK_BMESH, CD_CALLOC, 0);
441
442         CustomData_bmesh_init_pool(&bm->vdata, allocsize[0]);
443         CustomData_bmesh_init_pool(&bm->edata, allocsize[1]);
444         CustomData_bmesh_init_pool(&bm->ldata, allocsize[2]);
445         CustomData_bmesh_init_pool(&bm->pdata, allocsize[3]);
446
447         /*needed later*/
448         numTex = CustomData_number_of_layers(&bm->pdata, CD_MTEXPOLY);
449         numCol = CustomData_number_of_layers(&bm->ldata, CD_MLOOPCOL);
450
451         v = BMIter_New(&iter, bmold, BM_VERTS_OF_MESH, NULL);
452         for (i=0; v; v=BMIter_Step(&iter), i++) {
453                 v2 = BM_Make_Vert(bm, v->co, NULL);
454                 BM_Copy_Attributes(bmold, bm, v, v2);
455                 V_GROW(vtable);
456                 VECCOPY(v2->no, v->no);
457
458                 vtable[V_COUNT(vtable)-1] = v2;
459
460                 BMINDEX_SET(v, i);
461                 BMINDEX_SET(v2, i);
462         }
463         
464         e = BMIter_New(&iter, bmold, BM_EDGES_OF_MESH, NULL);
465         for (i=0; e; e=BMIter_Step(&iter), i++) {
466                 e2 = BM_Make_Edge(bm, vtable[BMINDEX_GET(e->v1)],
467                                   vtable[BMINDEX_GET(e->v2)], e, 0);
468
469                 BM_Copy_Attributes(bmold, bm, e, e2);
470                 V_GROW(etable);
471                 etable[V_COUNT(etable)-1] = e2;
472
473                 BMINDEX_SET(e, i);
474                 BMINDEX_SET(e2, i);
475         }
476         
477         f = BMIter_New(&iter, bmold, BM_FACES_OF_MESH, NULL);
478         for (i=0; f; f=BMIter_Step(&iter), i++) {
479                 V_RESET(loops);
480                 V_RESET(edges);
481                 l = BMIter_New(&liter, bmold, BM_LOOPS_OF_FACE, f);
482                 for (j=0; j<f->len; j++, l = BMIter_Step(&liter)) {
483                         V_GROW(loops);
484                         V_GROW(edges);
485                         loops[j] = l;
486                         edges[j] = etable[BMINDEX_GET(l->e)];
487                 }
488
489                 v = vtable[BMINDEX_GET(loops[0]->v)];
490                 v2 = vtable[BMINDEX_GET(loops[1]->v)];
491
492                 if (!bmesh_verts_in_edge(v, v2, edges[0])) {
493                         v = vtable[BMINDEX_GET(loops[V_COUNT(loops)-1]->v)];
494                         v2 = vtable[BMINDEX_GET(loops[0]->v)];
495                 }
496
497                 f2 = BM_Make_Ngon(bm, v, v2, edges, f->len, 0);
498                 
499                 BMINDEX_SET(f, i);
500                 V_GROW(ftable);
501                 ftable[i] = f2;
502
503                 BM_Copy_Attributes(bmold, bm, f, f2);
504                 VECCOPY(f2->no, f->no);
505
506                 l = BMIter_New(&liter, bm, BM_LOOPS_OF_FACE, f2);
507                 for (j=0; j<f->len; j++, l = BMIter_Step(&liter)) {
508                         BM_Copy_Attributes(bmold, bm, loops[j], l);
509                 }
510
511                 if (f == bmold->act_face) bm->act_face = f2;
512         }
513
514         /*copy over edit selection history*/
515         for (ese=bmold->selected.first; ese; ese=ese->next) {
516                 void *ele;
517
518                 if (ese->type == BM_VERT)
519                         ele = vtable[BMINDEX_GET(ese->data)];
520                 else if (ese->type == BM_EDGE)
521                         ele = etable[BMINDEX_GET(ese->data)];
522                 else if (ese->type == BM_FACE) {
523                         ele = ftable[BMINDEX_GET(ese->data)];
524                 }
525
526                 BM_store_selection(bm, ele);
527         }
528
529         V_FREE(etable);
530         V_FREE(vtable);
531         V_FREE(ftable);
532
533         V_FREE(loops);
534         V_FREE(edges);
535
536         return bm;
537 }
538
539 /*
540   BM FLAGS TO ME FLAGS
541
542   Returns the flags stored in element,
543   which much be either a BMVert, BMEdge,
544   or BMFace, converted to mesh flags.
545 */
546
547 int BMFlags_To_MEFlags(void *element) {
548         BMHeader *h = element;
549         int f = 0;
550
551         if (h->flag & BM_PINNED) f |= ME_PIN;
552         if (h->flag & BM_HIDDEN) f |= ME_HIDE;
553
554         if (h->type == BM_FACE) {
555                 if (h->flag & BM_SELECT) f |= ME_FACE_SEL;
556                 if (h->flag & BM_SMOOTH) f |= ME_SMOOTH;
557         } else if (h->type == BM_EDGE) {
558                 if (h->flag & BM_SELECT) f |= BM_SELECT;
559                 if (h->flag & BM_SEAM) f |= ME_SEAM;
560                 if (h->flag & BM_SHARP) f |= ME_SHARP;
561                 if (BM_Wire_Edge(NULL, element)) f |= ME_LOOSEEDGE;
562                 f |= ME_EDGEDRAW;
563         } else if (h->type == BM_VERT) {
564                 if (h->flag & BM_SELECT) f |= BM_SELECT;
565         }
566
567         return f;
568 }
569
570 /*
571   BM FLAGS TO ME FLAGS
572
573   Returns the flags stored in element,
574   which much be either a MVert, MEdge,
575   or MPoly, converted to mesh flags.
576   type must be either BM_VERT, BM_EDGE,
577   or BM_FACE.
578 */
579 int MEFlags_To_BMFlags(int flag, int type) {
580         int f = 0;
581         if (flag & ME_PIN) f |= BM_PINNED;
582
583         if (type == BM_FACE) {
584                 if (flag & ME_FACE_SEL) f |= BM_SELECT;
585                 if (flag & ME_SMOOTH) f |= BM_SMOOTH;
586                 if (flag & ME_HIDE) f |= BM_HIDDEN;
587         } else if (type == BM_EDGE) {
588                 if (flag & SELECT) f |= BM_SELECT;
589                 if (flag & ME_SEAM) f |= BM_SEAM;
590                 if (flag & ME_SHARP) f |= BM_SHARP;
591                 if (flag & ME_HIDE) f |= BM_HIDDEN;
592         } else if (type == BM_VERT) {
593                 if (flag & SELECT) f |= BM_SELECT;
594                 if (flag & ME_HIDE) f |= BM_HIDDEN;
595         }
596
597         return f;
598 }