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