fc06148296a60a75ea7ba216f3b6b8864a86acd7
[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 "bmesh.h"
38 #include "bmesh_private.h"
39
40 #include "math.h"
41 #include "stdio.h"
42 #include "string.h"
43
44 /*prototypes*/
45 static void bm_copy_loop_attributes(BMesh *source_mesh, BMesh *target_mesh,
46                                     BMLoop *source_loop, BMLoop *target_loop);
47
48 /*
49  * BM_CONSTRUCT.C
50  *
51  * This file contains functions for making and destroying
52  * individual elements like verts, edges and faces.
53  *
54 */
55
56 /*
57  * BMESH MAKE VERT
58  *
59  * Creates a new vertex and returns a pointer
60  * to it. If a pointer to an example vertex is
61  * passed in, it's custom data and properties
62  * will be copied to the new vertex.
63  *
64 */
65
66 BMVert *BM_Make_Vert(BMesh *bm, float co[3], BMVert *example)
67 {
68         BMVert *v = NULL;
69         v = bmesh_mv(bm, co);
70         if(example)
71                 CustomData_bmesh_copy_data(&bm->vdata, &bm->vdata, example->data, &v->data);
72         return v;
73 }
74
75 /*
76  * BMESH MAKE EDGE
77  *
78  * Creates a new edge betweeen two vertices and returns a
79  * pointer to it. If 'nodouble' equals 1, then a check is
80  * is done to make sure that an edge between those two vertices
81  * does not already exist. If it does, that edge is returned instead
82  * of creating a new one.
83  *
84  * If a new edge is created, and a pointer to an example edge is
85  * provided, it's custom data and properties will be copied to the
86  * new edge.
87  *
88 */
89
90 BMEdge *BM_Make_Edge(BMesh *bm, BMVert *v1, BMVert *v2, BMEdge *example, int nodouble)
91 {
92         BMEdge *e = NULL;
93         
94         if(nodouble) /*test if edge already exists.*/
95                 e = bmesh_disk_existedge(v1, v2);
96
97         if(!e){
98                 e = bmesh_me(bm, v1, v2);
99
100                 if(example)
101                         CustomData_bmesh_copy_data(&bm->edata, &bm->edata, example->data, &e->data);
102         }
103         
104         return e;
105         
106 }
107
108 /*
109  * BMESH MAKE QUADTRIANGLE
110  *
111  * Creates a new quad or triangle from
112  * a list of 3 or 4 vertices. If nodouble
113  * equals 1, then a check is done to see
114  * if a face with these vertices already
115  * exists and returns it instead. If a pointer
116  * to an example face is provided, it's custom
117  * data and properties will be copied to the new
118  * face.
119  *
120  * Note that the winding of the face is determined
121  * by the order of the vertices in the vertex array
122  *
123 */
124
125 BMFace *BM_Make_QuadTri(BMesh *bm, BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4, BMFace *example)
126 {
127         BMEdge *edar[4];
128         BMVert *vtar[4];
129
130         edar[0] = v1->edge;
131         edar[1] = v1->edge;
132         edar[2] = v1->edge;
133         if (v4) edar[3] = v1->edge;
134         else edar[3] = NULL;
135
136         vtar[0] = v1;
137         vtar[1] = v2;
138         vtar[2] = v3;
139         vtar[3] = v4;
140
141         return BM_Make_Quadtriangle(bm, vtar, edar, v4?4:3, example, 0);
142 }
143
144 /*remove the edge array bits from this. Its not really needed?*/
145 BMFace *BM_Make_Quadtriangle(BMesh *bm, BMVert **verts, BMEdge **edges, int len, BMFace *example, int nodouble)
146 {
147         BMEdge *edar[4];
148         BMFace *f = NULL;
149         int overlap = 0;
150
151         edar[0] = edar[1] = edar[2] = edar[3] = NULL;
152         
153         if(edges){
154                 edar[0] = edges[0];
155                 edar[1] = edges[1];
156                 edar[2] = edges[2];
157                 if(len == 4) edar[3] = edges[3];
158         }else{
159                 edar[0] = bmesh_disk_existedge(verts[0],verts[1]);
160                 edar[1] = bmesh_disk_existedge(verts[1],verts[2]);
161                 if(len == 4){
162                         edar[2] = bmesh_disk_existedge(verts[2],verts[3]);
163                         edar[3] = bmesh_disk_existedge(verts[3],verts[0]);
164
165                 }else{
166                         edar[2] = bmesh_disk_existedge(verts[2],verts[0]);
167                 }
168         }
169         
170         if(nodouble){
171                 /*check if face exists or overlaps*/
172                 if(len == 4){
173                         overlap = BM_Exist_Face_Overlaps(bm, verts, len, &f);
174                 }else{
175                         overlap = BM_Exist_Face_Overlaps(bm, verts, len, &f);
176                 }
177         }
178
179         /*make new face*/
180         if((!f) && (!overlap)){
181                 if(!edar[0]) edar[0] = bmesh_me(bm, verts[0], verts[1]);
182                 if(!edar[1]) edar[1] = bmesh_me(bm, verts[1], verts[2]);
183                 if(len == 4){
184                         if(!edar[2]) edar[2] = bmesh_me(bm, verts[2], verts[3]);
185                         if(!edar[3]) edar[3] = bmesh_me(bm, verts[3], verts[0]); 
186                 } else {
187                         if(!edar[2]) edar[2] = bmesh_me(bm, verts[2], verts[0]);
188                 }
189         
190                 if(len == 4) f = bmesh_mf(bm, verts[0], verts[1], edar, 4);
191                 else f = bmesh_mf(bm, verts[0], verts[1], edar, 3);
192         
193                 if(example)
194                         CustomData_bmesh_copy_data(&bm->pdata, &bm->pdata, example->data, &f->data);
195
196         }
197
198         return f;
199 }
200
201
202 /*copies face data from shared adjacent faces*/
203 void BM_Face_CopyShared(BMesh *bm, BMFace *f) {
204         BMIter iter;
205         BMLoop *l, *l2;
206
207         if (!f) return;
208
209         l=BMIter_New(&iter, bm, BM_LOOPS_OF_FACE, f);
210         for (; l; l=BMIter_Step(&iter)) {
211                 l2 = l->radial.next->data;
212                 
213                 if (l2 && l2 != l) {
214                         if (l2->v == l->v) {
215                                 bm_copy_loop_attributes(bm, bm, l2, l);
216                         } else {
217                                 l2 = (BMLoop*) l2->head.next;
218                                 bm_copy_loop_attributes(bm, bm, l2, l);
219                         }
220                 }
221         }
222 }
223
224 /*
225  * BMESH MAKE NGON
226  *
227  * Attempts to make a new Ngon from a list of edges.
228  * If nodouble equals one, a check for overlaps or existing
229  * 
230  * 
231  *
232 */
233 #define VERT_BUF_SIZE 100
234 BMFace *BM_Make_Ngon(BMesh *bm, BMVert *v1, BMVert *v2, BMEdge **edges, int len, int nodouble)
235 {
236         BMVert *vert_buf[VERT_BUF_SIZE];
237         BMVert **verts = vert_buf, *lastv;
238         BMFace *f = NULL;
239         int overlap = 0, i, j;
240
241         if(nodouble){
242                 if(len > VERT_BUF_SIZE)
243                         verts = MEM_callocN(sizeof(BMVert *) * len, "bmesh make ngon vertex array");
244                 
245                 /*if ((edges[i]->v1 == edges[i]->v1) || 
246                    (edges[i]->v1 == edges[i]->v2))
247                 {
248                         lastv = edges[i]->v2;
249                 } else lastv = edges[i]->v1;
250                 verts[0] = lastv;
251
252                 for (i=1; i<len; i++) {
253                         if (!BMO_TestFlag
254                 }*/
255
256                 for(i = 0, j=0; i < len; i++){
257                         if(!BMO_TestFlag(bm, edges[i]->v1, BM_EDGEVERT)){
258                                 BMO_SetFlag(bm, edges[i]->v1, BM_EDGEVERT);
259                                 verts[j++] = edges[i]->v1;
260                         }
261                         if(!BMO_TestFlag(bm, edges[i]->v2, BM_EDGEVERT)) {
262                                 BMO_SetFlag(bm, edges[i]->v2, BM_EDGEVERT);
263                                 verts[j++] = edges[i]->v2;
264                         }
265                 }
266                 
267                 if (j != len) {
268                         /*sanity check*/
269                         return NULL;
270                 }
271
272                 overlap = BM_Face_Exists(bm, verts, len, &f);
273                 
274                 /*clear flags*/
275                 for(i = 0; i < len; i++){
276                         BMO_ClearFlag(bm, edges[i]->v1, BM_EDGEVERT);
277                         BMO_ClearFlag(bm, edges[i]->v2, BM_EDGEVERT);
278                 }
279                 
280                 if(len > VERT_BUF_SIZE)
281                         MEM_freeN(verts);
282         }
283
284         if((!f) && (!overlap)) {
285                 f = bmesh_mf(bm, v1, v2, edges, len);
286         }
287
288         return f;
289 }
290
291
292 /*bmesh_make_face_from_face(BMesh *bm, BMFace *source, BMFace *target) */
293
294
295 /*
296  * REMOVE TAGGED XXX
297  *
298  * Called by operators to remove elements that they have marked for
299  * removal.
300  *
301 */
302
303 void BM_remove_tagged_faces(BMesh *bm, int flag)
304 {
305         BMHeader *current, *next;
306
307         current = bm->polys.first;
308         while(current){
309                 next = current->next;
310                 if(BMO_TestFlag(bm, current, flag)) bmesh_kf(bm, (BMFace*)current);
311                 current = next;
312         }
313 }
314 void BM_remove_tagged_edges(BMesh *bm, int flag)
315 {
316         BMHeader *current, *next;
317         
318         current = bm->edges.first;
319         
320         while(current){
321                 next = current->next;
322                 if(BMO_TestFlag(bm, current, flag)) bmesh_ke(bm, (BMEdge*)current);
323                 current = next;
324         }
325 }
326
327 void BM_remove_tagged_verts(BMesh *bm, int flag)
328 {
329         BMHeader *current, *next;
330
331         current = bm->verts.first;
332
333         while(current){
334                 next = current->next;
335                 if(BMO_TestFlag(bm, current, flag)) bmesh_kv(bm,(BMVert*)current);
336                 current = next;
337         }
338 }
339
340 static void bm_copy_vert_attributes(BMesh *source_mesh, BMesh *target_mesh, BMVert *source_vertex, BMVert *target_vertex)
341 {
342         CustomData_bmesh_copy_data(&source_mesh->vdata, &target_mesh->vdata, source_vertex->data, &target_vertex->data);        
343         target_vertex->bweight = source_vertex->bweight;
344 }
345
346 static void bm_copy_edge_attributes(BMesh *source_mesh, BMesh *target_mesh, BMEdge *source_edge, BMEdge *target_edge)
347 {
348         CustomData_bmesh_copy_data(&source_mesh->edata, &target_mesh->edata, source_edge->data, &target_edge->data);
349         target_edge->crease = source_edge->crease;
350         target_edge->bweight = source_edge->bweight;
351 }
352
353 static void bm_copy_loop_attributes(BMesh *source_mesh, BMesh *target_mesh, BMLoop *source_loop, BMLoop *target_loop)
354 {
355         CustomData_bmesh_copy_data(&source_mesh->ldata, &target_mesh->ldata, source_loop->data, &target_loop->data);
356 }
357
358 static void bm_copy_face_attributes(BMesh *source_mesh, BMesh *target_mesh, BMFace *source_face, BMFace *target_face)
359 {
360         CustomData_bmesh_copy_data(&source_mesh->pdata, &target_mesh->pdata, source_face->data, &target_face->data);    
361         target_face->mat_nr = source_face->mat_nr;
362 }
363
364 /*Todo: Special handling for hide flags?*/
365
366 void BM_Copy_Attributes(BMesh *source_mesh, BMesh *target_mesh, void *source, void *target)
367 {
368         BMHeader *sheader = source, *theader = target;
369         
370         if(sheader->type != theader->type)
371                 return;
372
373         /*First we copy select*/
374         if(BM_Is_Selected(source_mesh, source)) BM_Select(target_mesh, target, 1);
375         
376         /*Now we copy flags*/
377         theader->flag = sheader->flag;
378         
379         /*Copy specific attributes*/
380         if(theader->type == BM_VERT)
381                 bm_copy_vert_attributes(source_mesh, target_mesh, (BMVert*)source, (BMVert*)target);
382         else if(theader->type == BM_EDGE)
383                 bm_copy_edge_attributes(source_mesh, target_mesh, (BMEdge*)source, (BMEdge*)target);
384         else if(theader->type == BM_LOOP)
385                 bm_copy_loop_attributes(source_mesh, target_mesh, (BMLoop*)source, (BMLoop*)target);
386         else if(theader->type == BM_FACE)
387                 bm_copy_face_attributes(source_mesh, target_mesh, (BMFace*)source, (BMFace*)target);
388 }
389
390 BMesh *BM_Copy_Mesh(BMesh *bmold)
391 {
392         BMesh *bm;
393         BMVert *v, *v2, **vtable = NULL;
394         V_DECLARE(vtable);
395         BMEdge *e, *e2, **edges = NULL, **etable = NULL;
396         V_DECLARE(edges);
397         V_DECLARE(etable);
398         BMLoop *l, *l2, **loops = NULL;
399         V_DECLARE(loops);
400         BMFace *f, *f2;
401
402         BMIter iter, liter;
403         int allocsize[4] = {512,512,2048,512}, numTex, numCol;
404         int i;
405
406         /*allocate a bmesh*/
407         bm = BM_Make_Mesh(allocsize);
408
409         CustomData_copy(&bmold->vdata, &bm->vdata, CD_MASK_BMESH, CD_CALLOC, 0);
410         CustomData_copy(&bmold->edata, &bm->edata, CD_MASK_BMESH, CD_CALLOC, 0);
411         CustomData_copy(&bmold->ldata, &bm->ldata, CD_MASK_BMESH, CD_CALLOC, 0);
412         CustomData_copy(&bmold->pdata, &bm->pdata, CD_MASK_BMESH, CD_CALLOC, 0);
413
414         CustomData_bmesh_init_pool(&bm->vdata, allocsize[0]);
415         CustomData_bmesh_init_pool(&bm->edata, allocsize[1]);
416         CustomData_bmesh_init_pool(&bm->ldata, allocsize[2]);
417         CustomData_bmesh_init_pool(&bm->pdata, allocsize[3]);
418
419         /*needed later*/
420         numTex = CustomData_number_of_layers(&bm->pdata, CD_MTEXPOLY);
421         numCol = CustomData_number_of_layers(&bm->ldata, CD_MLOOPCOL);
422
423         v = BMIter_New(&iter, bmold, BM_VERTS_OF_MESH, NULL);
424         for (i=0; v; v=BMIter_Step(&iter), i++) {
425                 v2 = BM_Make_Vert(bm, v->co, NULL);
426                 BM_Copy_Attributes(bmold, bm, v, v2);
427                 V_GROW(vtable);
428                 VECCOPY(v2->no, v->no);
429
430                 vtable[V_COUNT(vtable)-1] = v2;
431
432                 BMINDEX_SET(v, i);
433                 BMINDEX_SET(v2, i);
434         }
435         
436         e = BMIter_New(&iter, bmold, BM_EDGES_OF_MESH, NULL);
437         for (i=0; e; e=BMIter_Step(&iter), i++) {
438                 e2 = BM_Make_Edge(bm, vtable[BMINDEX_GET(e->v1)],
439                                   vtable[BMINDEX_GET(e->v2)], e, 0);
440
441                 BM_Copy_Attributes(bmold, bm, e, e2);
442                 V_GROW(etable);
443                 etable[V_COUNT(etable)-1] = e2;
444
445                 BMINDEX_SET(e, i);
446                 BMINDEX_SET(e2, i);
447         }
448         
449         f = BMIter_New(&iter, bmold, BM_FACES_OF_MESH, NULL);
450         for (; f; f=BMIter_Step(&iter)) {
451                 V_RESET(loops);
452                 V_RESET(edges);
453                 l = BMIter_New(&liter, bmold, BM_LOOPS_OF_FACE, f);
454                 for (i=0; i<f->len; i++, l = BMIter_Step(&liter)) {
455                         V_GROW(loops);
456                         V_GROW(edges);
457                         loops[i] = l;
458                         edges[i] = etable[BMINDEX_GET(l->e)];
459                 }
460
461                 v = vtable[BMINDEX_GET(loops[0]->v)];
462                 v2 = vtable[BMINDEX_GET(loops[1]->v)];
463
464                 if (!bmesh_verts_in_edge(v, v2, edges[0])) {
465                         v = vtable[BMINDEX_GET(loops[V_COUNT(loops)-1]->v)];
466                         v2 = vtable[BMINDEX_GET(loops[0]->v)];
467                 }
468
469                 f2 = BM_Make_Ngon(bm, v, v2, edges, f->len, 0);
470                 BM_Copy_Attributes(bmold, bm, f, f2);
471                 VECCOPY(f2->no, f->no);
472
473                 l = BMIter_New(&liter, bm, BM_LOOPS_OF_FACE, f2);
474                 for (i=0; i<f->len; i++, l = BMIter_Step(&liter)) {
475                         BM_Copy_Attributes(bmold, bm, loops[i], l);
476                 }
477         }
478         
479         V_FREE(etable);
480         V_FREE(vtable);
481         V_FREE(loops);
482         V_FREE(edges);
483
484         return bm;
485 }