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