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