8970e7ff70595191b7d31ae3197c7faa8d9e3173
[blender.git] / source / blender / blenkernel / intern / BME_structure.c
1 /*
2  * BME_structure.c    jan 2007
3  *
4  *      Low level routines for manipulating the BMesh structure.
5  *
6  * $Id$
7  *
8  * ***** BEGIN GPL LICENSE BLOCK *****
9  *
10  * This program is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU General Public License
12  * as published by the Free Software Foundation; either version 2
13  * of the License, or (at your option) any later version.
14  * about this.  
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License
22  * along with this program; if not, write to the Free Software Foundation,
23  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
24  *
25  * The Original Code is Copyright (C) 2007 Blender Foundation.
26  * All rights reserved.
27  *
28  * The Original Code is: all of this file.
29  *
30  * Contributor(s): Geoffrey Bantle.
31  *
32  * ***** END GPL LICENSE BLOCK *****
33  */
34
35 #include <limits.h>
36
37 #include "MEM_guardedalloc.h"
38 #include "BLI_utildefines.h"
39 #include "BKE_bmesh.h"
40 /**
41  *      MISC utility functions.
42  *
43  */
44  
45 int BME_vert_in_edge(BME_Edge *e, BME_Vert *v){
46         if(e->v1 == v || e->v2 == v) return 1;
47         return 0;
48 }
49 int BME_verts_in_edge(BME_Vert *v1, BME_Vert *v2, BME_Edge *e){
50         if(e->v1 == v1 && e->v2 == v2) return 1;
51         else if(e->v1 == v2 && e->v2 == v1) return 1;
52         return 0;
53 }
54
55 BME_Vert *BME_edge_getothervert(BME_Edge *e, BME_Vert *v){      
56         if(e->v1 == v) return e->v2;
57         else if(e->v2 == v) return e->v1;
58         return NULL;
59 }
60
61 int BME_edge_swapverts(BME_Edge *e, BME_Vert *orig, BME_Vert *new){
62         if(e->v1 == orig){ 
63                 e->v1 = new;
64                 e->d1.next = NULL;
65                 e->d1.prev = NULL;
66                 return 1;
67         }
68         else if(e->v2 == orig){
69                 e->v2 = new;
70                 e->d2.next = NULL;
71                 e->d2.prev = NULL;
72                 return 1;
73         }
74         return 0;
75 }
76
77 /**
78  *      ALLOCATION/DEALLOCATION FUNCTIONS
79  */
80
81 BME_Vert *BME_addvertlist(BME_Mesh *bm, BME_Vert *example){
82         BME_Vert *v=NULL;
83         v = BLI_mempool_alloc(bm->vpool);
84         v->next = v->prev = NULL;
85         v->EID = bm->nextv;
86         v->co[0] = v->co[1] = v->co[2] = 0.0f;
87         v->no[0] = v->no[1] = v->no[2] = 0.0f;
88         v->edge = NULL;
89         v->data = NULL;
90         v->eflag1 = v->eflag2 = v->tflag1 = v->tflag2 = 0;
91         v->flag = v->h = 0;
92         v->bweight = 0.0f;
93         BLI_addtail(&(bm->verts), v);
94         bm->nextv++;
95         bm->totvert++;
96
97         if(example){
98                 VECCOPY(v->co,example->co);
99                 CustomData_bmesh_copy_data(&bm->vdata, &bm->vdata, example->data, &v->data);
100         }
101         else
102                 CustomData_bmesh_set_default(&bm->vdata, &v->data);
103
104         return v;
105 }
106 BME_Edge *BME_addedgelist(BME_Mesh *bm, BME_Vert *v1, BME_Vert *v2, BME_Edge *example){
107         BME_Edge *e=NULL;
108         e = BLI_mempool_alloc(bm->epool);
109         e->next = e->prev = NULL;
110         e->EID = bm->nexte;
111         e->v1 = v1;
112         e->v2 = v2;
113         e->d1.next = e->d1.prev = e->d2.next = e->d2.prev = NULL;
114         e->d1.data = e;
115         e->d2.data = e;
116         e->loop = NULL;
117         e->data = NULL;
118         e->eflag1 = e->eflag2 = e->tflag1 = e->tflag2 = 0;
119         e->flag = e->h = 0;
120         e->crease = e->bweight = 0.0f;
121         bm->nexte++;
122         bm->totedge++;
123         BLI_addtail(&(bm->edges), e);
124         
125         if(example)
126                 CustomData_bmesh_copy_data(&bm->edata, &bm->edata, example->data, &e->data);
127         else
128                 CustomData_bmesh_set_default(&bm->edata, &e->data);
129
130
131         return e;
132 }
133 BME_Loop *BME_create_loop(BME_Mesh *bm, BME_Vert *v, BME_Edge *e, BME_Poly *f, BME_Loop *example){
134         BME_Loop *l=NULL;
135         l = BLI_mempool_alloc(bm->lpool);
136         l->next = l->prev = NULL;
137         l->EID = bm->nextl;
138         l->radial.next = l->radial.prev = NULL;
139         l->radial.data = l;
140         l->v = v;
141         l->e = e;
142         l->f = f;
143         l->data = NULL;
144         l->eflag1 = l->eflag2 = l->tflag1 = l->tflag2 = 0;
145         l->flag = l->h = 0; //stupid waste!
146         bm->nextl++;
147         bm->totloop++;
148         
149         if(example)
150                 CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, example->data, &l->data);
151         else
152                 CustomData_bmesh_set_default(&bm->ldata, &l->data);
153
154         return l;
155 }
156
157 BME_Poly *BME_addpolylist(BME_Mesh *bm, BME_Poly *example){
158         BME_Poly *f = NULL;
159         f = BLI_mempool_alloc(bm->ppool);
160         f->next = f->prev = NULL;
161         f->EID = bm->nextp;
162         f->loopbase = NULL;
163         f->len = 0;
164         f->data = NULL;
165         f->eflag1 = f->eflag2 = f->tflag1 = f->tflag2 = 0;
166         f->flag = f->h = f->mat_nr;
167         BLI_addtail(&(bm->polys),f);
168         bm->nextp++;
169         bm->totpoly++;
170
171         if(example)
172                 CustomData_bmesh_copy_data(&bm->pdata, &bm->pdata, example->data, &f->data);
173         else
174                 CustomData_bmesh_set_default(&bm->pdata, &f->data);
175
176
177         return f;
178 }
179
180 /*      free functions dont do much *yet*. When per-vertex, per-edge and per-face/faceloop
181         data is added though these will be needed.
182 */
183 void BME_free_vert(BME_Mesh *bm, BME_Vert *v){
184         bm->totvert--;
185         CustomData_bmesh_free_block(&bm->vdata, &v->data);
186         BLI_mempool_free(bm->vpool, v);
187 }
188 void BME_free_edge(BME_Mesh *bm, BME_Edge *e){
189         bm->totedge--;
190         CustomData_bmesh_free_block(&bm->edata, &e->data);
191         BLI_mempool_free(bm->epool, e);
192 }
193 void BME_free_poly(BME_Mesh *bm, BME_Poly *f){
194         bm->totpoly--;
195         CustomData_bmesh_free_block(&bm->pdata, &f->data);
196         BLI_mempool_free(bm->ppool, f);
197 }
198 void BME_free_loop(BME_Mesh *bm, BME_Loop *l){
199         bm->totloop--;
200         CustomData_bmesh_free_block(&bm->ldata, &l->data);
201         BLI_mempool_free(bm->lpool, l);
202 }
203 /**
204  *      BMESH CYCLES
205  *
206  *      Cycles are circular doubly linked lists that form the basis of adjacency
207  *      information in the BME modeller. Full adjacency relations can be derived
208  *      from examining these cycles very quickly. Although each cycle is a double
209  *  circular linked list, each one is considered to have a 'base' or 'head',
210  *      and care must be taken by Euler code when modifying the contents of a cycle.
211  *
212  *      The contents of this file are split into two parts. First there are the 
213  *      BME_cycle family of functions which are generic circular double linked list 
214  *      procedures. The second part contains higher level procedures for supporting 
215  *      modification of specific cycle types.
216  *
217  *      The three cycles explicitly stored in the BMesh data structure are as follows:
218  *
219  *      1: The Disk Cycle - A circle of edges around a vertex
220  *     Base: vertex->edge pointer.
221  *         
222  *     This cycle is the most complicated in terms of its structure. Each BME_Edge contains     
223  *         two BME_CycleNode structures to keep track of that edge's membership in the disk cycle
224  *         of each of its vertices. However for any given vertex it may be the first in some edges
225  *         in its disk cycle and the second for others. The BME_disk_XXX family of functions contain
226  *         some nice utilities for navigating disk cycles in a way that hides this detail from the 
227  *         tool writer.
228  *
229  *              Note that the disk cycle is completley independant from face data. One advantage of this
230  *              is that wire edges are fully integrated into the topology database. Another is that the 
231  *          the disk cycle has no problems dealing with non-manifold conditions involving faces.
232  *
233  *              Functions relating to this cycle:
234  *              
235  *                      BME_disk_append_edge
236  *                      BME_disk_remove_edge
237  *                      BME_disk_nextedge
238  *                      BME_disk_getpointer
239  *
240  *      2: The Radial Cycle - A circle of face edges (BME_Loop) around an edge
241  *         Base: edge->loop->radial structure.
242  *
243  *              The radial cycle is similar to the radial cycle in the radial edge data structure.*
244  *              Unlike the radial edge however, the radial cycle does not require a large amount of memory 
245  *              to store non-manifold conditions since BMesh does not keep track of region/shell
246  *              information.
247  *              
248  *              Functions relating to this cycle:
249  *                      
250  *                      BME_radial_append
251  *                      BME_radial_remove_loop
252  *                      BME_radial_nextloop
253  *                      BME_radial_find_face
254  *              
255  *
256  *      3: The Loop Cycle - A circle of face edges around a polygon.
257  *     Base: polygon->loopbase.
258  *
259  *         The loop cycle keeps track of a faces vertices and edges. It should be noted that the
260  *     direction of a loop cycle is either CW or CCW depending on the face normal, and is 
261  *     not oriented to the faces editedges. 
262  *
263  *              Functions relating to this cycle:
264  *              
265  *                      BME_cycle_XXX family of functions.
266  *
267  *      
268  *      Note that the order of elements in all cycles except the loop cycle is undefined. This 
269  *  leads to slightly increased seek time for deriving some adjacency relations, however the 
270  *  advantage is that no intrinsic properties of the data structures are dependant upon the 
271  *  cycle order and all non-manifold conditions are represented trivially.
272  *
273 */
274  
275  
276 void BME_cycle_append(void *h, void *nt)
277 {
278         BME_CycleNode *oldtail, *head, *newtail;
279         
280         head = (BME_CycleNode*)h;
281         newtail = (BME_CycleNode*)nt;
282         
283         if(head->next == NULL){
284                 head->next = newtail;
285                 head->prev = newtail;
286                 newtail->next = head;
287                 newtail->prev = head;
288         }
289         else{
290                 oldtail = head->prev;
291                 oldtail->next = newtail;
292                 newtail->next = head;
293                 newtail->prev = oldtail;
294                 head->prev = newtail;
295                 
296         }
297 }
298
299 /**
300  *                      BME_cycle_length
301  *
302  *      Count the nodes in a cycle.
303  *
304  *  Returns -
305  *      Integer
306  */
307
308 int BME_cycle_length(void *h){
309         
310         int len = 0;
311         BME_CycleNode *head, *curnode;
312         head = (BME_CycleNode*)h;
313         
314         if(head){ 
315                 len = 1;
316                 for(curnode = head->next; curnode != head; curnode=curnode->next){ 
317                         if(len == INT_MAX){ //check for infinite loop/corrupted cycle
318                                         return -1;
319                         }
320                         len++;
321                 }
322         }
323         return len;
324 }
325
326
327 /**
328  *                      BME_cycle_remove
329  *
330  *      Removes a node from a cycle.
331  *
332  *  Returns -
333  *      1 for success, 0 for failure.
334  */
335
336 int BME_cycle_remove(void *h, void *remn)
337 {
338         int i, len;
339         BME_CycleNode *head, *remnode, *curnode;
340         
341         head = (BME_CycleNode*)h;
342         remnode = (BME_CycleNode*)remn;
343         len = BME_cycle_length(h);
344         
345         if(len == 1 && head == remnode){
346                 head->next = NULL;
347                 head->prev = NULL;
348                 return 1;
349         }
350         else{
351                 for(i=0, curnode = head; i < len; curnode = curnode->next){
352                         if(curnode == remnode){
353                                 remnode->prev->next = remnode->next;
354                                 remnode->next->prev = remnode->prev;
355                                 /*zero out remnode pointers, important!*/
356                                 //remnode->next = NULL;
357                                 //remnode->prev = NULL;
358                                 return 1;
359                 
360                         }
361                 }
362         }
363         return 0;
364 }
365
366 /**
367  *                      BME_cycle_validate
368  *
369  *      Validates a cycle. Takes as an argument the expected length of the cycle and
370  *      a pointer to the cycle head or base.
371  *
372  *
373  *  Returns -
374  *      1 for success, 0 for failure.
375  */
376
377 int BME_cycle_validate(int len, void *h){
378         int i;
379         BME_CycleNode *curnode, *head;
380         head = (BME_CycleNode*)h;
381         
382         /*forward validation*/
383         for(i = 0, curnode = head; i < len; i++, curnode = curnode->next);
384         if(curnode != head) return 0;
385         
386         /*reverse validation*/
387         for(i = 0, curnode = head; i < len; i++, curnode = curnode->prev);
388         if(curnode != head) return 0;
389         
390         return 1;
391 }
392
393 /*Begin Disk Cycle routines*/
394
395 /**
396  *                      BME_disk_nextedge
397  *
398  *      Find the next edge in a disk cycle
399  *
400  *  Returns -
401  *      Pointer to the next edge in the disk cycle for the vertex v.
402  */
403  
404 BME_Edge *BME_disk_nextedge(BME_Edge *e, BME_Vert *v)
405 {       
406         if(BME_vert_in_edge(e, v)){
407                 if(e->v1 == v) return e->d1.next->data;
408                 else if(e->v2 == v) return e->d2.next->data;
409         }
410         return NULL;
411 }
412
413 /**
414  *                      BME_disk_getpointer
415  *
416  *      Given an edge and one of its vertices, find the apporpriate CycleNode
417  *
418  *  Returns -
419  *      Pointer to BME_CycleNode.
420  */
421 BME_CycleNode *BME_disk_getpointer(BME_Edge *e, BME_Vert *v){
422         /*returns pointer to the cycle node for the appropriate vertex in this disk*/
423         if(e->v1 == v) return &(e->d1);
424         else if (e->v2 == v) return &(e->d2);
425         return NULL;
426 }
427
428 /**
429  *                      BME_disk_append_edge
430  *
431  *      Appends edge to the end of a vertex disk cycle.
432  *
433  *  Returns -
434  *      1 for success, 0 for failure
435  */
436
437 int BME_disk_append_edge(BME_Edge *e, BME_Vert *v)
438
439         
440         BME_CycleNode *base, *tail;
441         
442         if(BME_vert_in_edge(e, v) == 0) return 0; /*check to make sure v is in e*/
443         
444         /*check for loose vert first*/
445         if(v->edge == NULL){
446                 v->edge = e;
447                 base = tail = BME_disk_getpointer(e, v);
448                 BME_cycle_append(base, tail); /*circular reference is ok!*/
449                 return 1;
450         }
451         
452         /*insert e at the end of disk cycle and make it the new v->edge*/
453         base = BME_disk_getpointer(v->edge, v);
454         tail = BME_disk_getpointer(e, v);
455         BME_cycle_append(base, tail);
456         return 1;
457 }
458
459 /**
460  *                      BME_disk_remove_edge
461  *
462  *      Removes an edge from a disk cycle. If the edge to be removed is
463  *      at the base of the cycle, the next edge becomes the new base.
464  *
465  *
466  *  Returns -
467  *      Nothing
468  */
469
470 void BME_disk_remove_edge(BME_Edge *e, BME_Vert *v)
471 {
472         BME_CycleNode *base, *remnode;
473         BME_Edge *newbase;
474         int len;
475         
476         base = BME_disk_getpointer(v->edge, v);
477         remnode = BME_disk_getpointer(e, v);
478         
479         /*first deal with v->edge pointer...*/
480         len = BME_cycle_length(base);
481         if(len == 1) newbase = NULL;
482         else if(v->edge == e) newbase = base->next-> data;
483         else newbase = v->edge;
484         
485         /*remove and rebase*/
486         BME_cycle_remove(base, remnode);
487         v->edge = newbase;
488 }
489
490 /**
491  *                      BME_disk_next_edgeflag
492  *
493  *      Searches the disk cycle of v, starting with e, for the 
494  *  next edge that has either eflag or tflag.
495  *
496  *      BME_Edge pointer.
497  */
498
499 BME_Edge *BME_disk_next_edgeflag(BME_Edge *e, BME_Vert *v, int eflag, int tflag){
500         
501         BME_CycleNode *diskbase;
502         BME_Edge *curedge;
503         int len, ok;
504         
505         if(eflag && tflag) return NULL;
506         
507         ok = BME_vert_in_edge(e,v);
508         if(ok){
509                 diskbase = BME_disk_getpointer(e, v);
510                 len = BME_cycle_length(diskbase);
511                 curedge = BME_disk_nextedge(e,v);
512                 while(curedge != e){
513                         if(tflag){
514                                 if(curedge->tflag1 == tflag) return curedge;
515                         }
516                         else if(eflag){
517                                 if(curedge->eflag1 == eflag) return curedge;
518                         }
519                         curedge = BME_disk_nextedge(curedge, v);
520                 }
521         }
522         return NULL;
523 }
524
525 /**
526  *                      BME_disk_count_edgeflag
527  *
528  *      Counts number of edges in this verts disk cycle which have 
529  *      either eflag or tflag (but not both!)
530  *
531  *  Returns -
532  *      Integer.
533  */
534
535 int BME_disk_count_edgeflag(BME_Vert *v, int eflag, int tflag){
536         BME_CycleNode *diskbase;
537         BME_Edge *curedge;
538         int i, len=0, count=0;
539         
540         if(v->edge){
541                 if(eflag && tflag) return 0; /*tflag and eflag are reserved for different functions!*/
542                 diskbase = BME_disk_getpointer(v->edge, v);
543                 len = BME_cycle_length(diskbase);
544                 
545                 for(i = 0, curedge=v->edge; i<len; i++){
546                         if(tflag){
547                                 if(curedge->tflag1 == tflag) count++;
548                         }
549                         else if(eflag){
550                                 if(curedge->eflag1 == eflag) count++;
551                         }
552                         curedge = BME_disk_nextedge(curedge, v);
553                 }
554         }
555         return count;
556 }
557
558 int BME_disk_hasedge(BME_Vert *v, BME_Edge *e){
559         BME_CycleNode *diskbase;
560         BME_Edge *curedge;
561         int i, len=0;
562         
563         if(v->edge){
564                 diskbase = BME_disk_getpointer(v->edge,v);
565                 len = BME_cycle_length(diskbase);
566                 
567                 for(i = 0, curedge=v->edge; i<len; i++){
568                         if(curedge == e) return 1;
569                         else curedge=BME_disk_nextedge(curedge, v);
570                 }
571         }
572         return 0;
573 }
574 /*end disk cycle routines*/
575
576 BME_Loop *BME_radial_nextloop(BME_Loop *l){
577         return (BME_Loop*)(l->radial.next->data);
578 }
579
580 void BME_radial_append(BME_Edge *e, BME_Loop *l){
581         if(e->loop == NULL) e->loop = l;
582         BME_cycle_append(&(e->loop->radial), &(l->radial));
583 }
584
585 void BME_radial_remove_loop(BME_Loop *l, BME_Edge *e)
586 {
587         BME_Loop *newbase;
588         int len;
589         
590         /*deal with edge->loop pointer*/
591         len = BME_cycle_length(&(e->loop->radial));
592         if(len == 1) newbase = NULL;
593         else if(e->loop == l) newbase = e->loop->radial.next->data;
594         else newbase = e->loop;
595         
596         /*remove and rebase*/
597         BME_cycle_remove(&(e->loop->radial), &(l->radial));
598         e->loop = newbase;
599 }
600
601 int BME_radial_find_face(BME_Edge *e,BME_Poly *f)
602 {
603                 
604         BME_Loop *curloop;
605         int i, len;
606         
607         len = BME_cycle_length(&(e->loop->radial));
608         for(i = 0, curloop = e->loop; i < len; i++, curloop = curloop->radial.next->data){
609                 if(curloop->f == f) return 1;
610         }
611         return 0;
612 }
613
614 struct BME_Loop *BME_loop_find_loop(struct BME_Poly *f, struct BME_Vert *v) {
615         BME_Loop *l;
616         int i, len;
617         
618         len = BME_cycle_length(f->loopbase);
619         for (i = 0, l=f->loopbase; i < len; i++, l=l->next) {
620                 if (l->v == v) return l;
621         }
622         return NULL;
623 }