Use xrange() rather than range() for loop iterations.
[blender.git] / source / blender / include / reeb.h
1 /**
2  * $Id: 
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version. The Blender
10  * Foundation also sells licenses for use in proprietary software under
11  * the Blender License.  See http://www.blender.org/BL/ for information
12  * about this.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software Foundation,
21  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
22  *
23  * Contributor(s): Martin Poirier
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27  
28 #ifndef REEB_H_
29 #define REEB_H_
30
31 #include "DNA_listBase.h"
32
33 struct EdgeHash;
34 struct ReebArc;
35 struct ReebEdge;
36 struct ReebNode;
37
38 typedef struct ReebGraph {
39         ListBase arcs;
40         ListBase nodes;
41         int totnodes;
42         struct EdgeHash *emap;
43 } ReebGraph;
44
45 typedef struct EmbedBucket {
46         float val;
47         int       nv;
48         float p[3];
49 } EmbedBucket;
50
51 typedef struct ReebNode {
52         struct ReebNode *next, *prev;
53         struct ReebArc **arcs;
54         int index;
55         int degree;
56         float weight;
57         float p[3];
58         int flags;
59 } ReebNode;
60
61 typedef struct ReebEdge {
62         struct ReebEdge *next, *prev;
63         struct ReebArc  *arc;
64         struct ReebNode *v1, *v2;
65         struct ReebEdge *nextEdge;
66 } ReebEdge;
67
68 typedef struct ReebArc {
69         struct ReebArc *next, *prev;
70         ListBase edges;
71         struct ReebNode *v1, *v2;
72         struct EmbedBucket *buckets;
73         int     bcount;
74         int flags;
75 } ReebArc;
76
77 typedef struct ReebArcIterator {
78         struct ReebArc  *arc;
79         int index;
80         int start;
81         int end;
82         int stride;
83 } ReebArcIterator;
84
85 struct EditMesh;
86
87 int weightToHarmonic(struct EditMesh *em);
88 int weightFromDistance(struct EditMesh *em);
89 int weightFromLoc(struct EditMesh *me, int axis);
90 void weightToVCol(struct EditMesh *em);
91 void renormalizeWeight(struct EditMesh *em, float newmax);
92
93 ReebGraph * generateReebGraph(struct EditMesh *me, int subdivisions);
94 void freeGraph(ReebGraph *rg);
95 void exportGraph(ReebGraph *rg, int count);
96
97 #define OTHER_NODE(arc, node) ((arc->v1 == node) ? arc->v2 : arc->v1)
98
99 void initArcIterator(struct ReebArcIterator *iter, struct ReebArc *arc, struct ReebNode *head);
100 void initArcIterator2(struct ReebArcIterator *iter, struct ReebArc *arc, int start, int end);
101 struct EmbedBucket * nextBucket(struct ReebArcIterator *iter);
102
103 /* Filtering */
104 void filterNullReebGraph(ReebGraph *rg);
105 int filterExternalReebGraph(ReebGraph *rg, float threshold);
106 int filterInternalReebGraph(ReebGraph *rg, float threshold);
107
108 /* Post-Build processing */
109 void repositionNodes(ReebGraph *rg);
110 void postprocessGraph(ReebGraph *rg, char mode);
111 void removeNormalNodes(ReebGraph *rg);
112
113 /* Graph processing */
114 void buildAdjacencyList(ReebGraph *rg);
115
116 void sortNodes(ReebGraph *rg);
117 void sortArcs(ReebGraph *rg);
118
119 int subtreeDepth(ReebNode *node, ReebArc *rootArc);
120 int countConnectedArcs(ReebGraph *rg, ReebNode *node);
121 int hasAdjacencyList(ReebGraph *rg); 
122 int     isGraphCyclic(ReebGraph *rg);
123
124 /* Sanity check */
125 void verifyBuckets(ReebGraph *rg);
126
127 #endif /*REEB_H_*/