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