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