minor include cleanup, add GPL header (copied from BKE_animsys.h
[blender.git] / source / blender / blenlib / BLI_graph.h
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2008 Blender Foundation.
19  * All rights reserved.
20  *
21  * Contributor(s): Joshua Leung
22  *
23  * ***** END GPL LICENSE BLOCK *****
24  */
25 #ifndef BLI_GRAPH_H_
26 #define BLI_GRAPH_H_
27
28 /** \file BLI_graph.h
29  *  \ingroup bli
30  */
31
32 #include "DNA_listBase.h"
33
34 struct BGraph;
35 struct BNode;
36 struct BArc;
37
38 struct RadialArc;
39
40 typedef void (*FreeArc)(struct BArc*);
41 typedef void (*FreeNode)(struct BNode*);
42 typedef void (*RadialSymmetry)(struct BNode* root_node, struct RadialArc* ring, int total);
43 typedef void (*AxialSymmetry)(struct BNode* root_node, struct BNode* node1, struct BNode* node2, struct BArc* arc1, struct BArc* arc2);
44
45 /* IF YOU MODIFY THOSE TYPES, YOU NEED TO UPDATE ALL THOSE THAT "INHERIT" FROM THEM
46  * 
47  * RigGraph, ReebGraph
48  * 
49  * */
50
51 typedef struct BGraph {
52         ListBase        arcs;
53         ListBase        nodes;
54         
55         float length;
56         
57         /* function pointer to deal with custom fonctionnality */
58         FreeArc                 free_arc;
59         FreeNode                free_node;
60         RadialSymmetry  radial_symmetry;
61         AxialSymmetry   axial_symmetry;
62 } BGraph;
63
64 typedef struct BNode {
65         void *next, *prev;
66         float p[3];
67         int flag;
68
69         int degree;
70         struct BArc **arcs;
71         
72         int subgraph_index;
73
74         int symmetry_level;
75         int symmetry_flag;
76         float symmetry_axis[3];
77 } BNode;
78
79 typedef struct BArc {
80         void *next, *prev;
81         struct BNode *head, *tail;
82         int flag;
83
84         float length;
85
86         int symmetry_level;
87         int symmetry_group;
88         int symmetry_flag;
89 } BArc;
90
91 struct BArcIterator;
92
93 void* IT_head(void* iter);
94 void* IT_tail(void* iter);
95 void* IT_peek(void* iter, int n);
96 void* IT_next(void* iter);
97 void* IT_nextN(void* iter, int n);
98 void* IT_previous(void* iter);
99 int   IT_stopped(void* iter);
100
101 typedef void* (*HeadFct)(void* iter);
102 typedef void* (*TailFct)(void* iter);
103 typedef void* (*PeekFct)(void* iter, int n);
104 typedef void* (*NextFct)(void* iter);
105 typedef void* (*NextNFct)(void* iter, int n);
106 typedef void* (*PreviousFct)(void* iter);
107 typedef int   (*StoppedFct)(void* iter);
108
109 typedef struct BArcIterator {
110         HeadFct         head;
111         TailFct         tail;
112         PeekFct         peek;
113         NextFct         next;
114         NextNFct        nextN;
115         PreviousFct     previous;
116         StoppedFct      stopped;
117         
118         float *p, *no;
119         float size;
120         
121         int length;
122         int index;
123 } BArcIterator;
124
125 /* Helper structure for radial symmetry */
126 typedef struct RadialArc
127 {
128         struct BArc *arc; 
129         float n[3]; /* normalized vector joining the nodes of the arc */
130 } RadialArc;
131
132 BNode *BLI_otherNode(BArc *arc, BNode *node);
133
134 void BLI_freeNode(BGraph *graph, BNode *node);
135 void BLI_removeNode(BGraph *graph, BNode *node);
136
137 void BLI_removeArc(BGraph *graph, BArc *arc);
138
139 void BLI_flagNodes(BGraph *graph, int flag);
140 void BLI_flagArcs(BGraph *graph, int flag);
141
142 int BLI_hasAdjacencyList(BGraph *rg);
143 void BLI_buildAdjacencyList(BGraph *rg);
144 void BLI_rebuildAdjacencyList(BGraph* rg);
145 void BLI_rebuildAdjacencyListForNode(BGraph* rg, BNode *node);
146 void BLI_freeAdjacencyList(BGraph *rg);
147
148 int BLI_FlagSubgraphs(BGraph *graph);
149 void BLI_ReflagSubgraph(BGraph *graph, int old_subgraph, int new_subgraph);
150
151 #define SHAPE_RADIX 10 /* each shape level is encoded this base */
152
153 int BLI_subtreeShape(BGraph *graph, BNode *node, BArc *rootArc, int include_root);
154 float BLI_subtreeLength(BNode *node);
155 void BLI_calcGraphLength(BGraph *graph);
156
157 void BLI_replaceNode(BGraph *graph, BNode *node_src, BNode *node_replaced);
158 void BLI_replaceNodeInArc(BGraph *graph, BArc *arc, BNode *node_src, BNode *node_replaced);
159 void BLI_removeDoubleNodes(BGraph *graph, float limit);
160 BNode * BLI_FindNodeByPosition(BGraph *graph, float *p, float limit);
161
162 BArc * BLI_findConnectedArc(BGraph *graph, BArc *arc, BNode *v);
163
164 int     BLI_isGraphCyclic(BGraph *graph);
165
166 /*------------ Symmetry handling ------------*/
167 void BLI_markdownSymmetry(BGraph *graph, BNode *root_node, float limit);
168
169 void BLI_mirrorAlongAxis(float v[3], float center[3], float axis[3]);
170
171 /* BNode symmetry flags */
172 #define SYM_TOPOLOGICAL 1
173 #define SYM_PHYSICAL    2
174
175 /* the following two are exclusive */
176 #define SYM_AXIAL               4
177 #define SYM_RADIAL              8
178
179 /* BArc symmetry flags
180  * 
181  * axial symetry sides */
182 #define SYM_SIDE_POSITIVE               1
183 #define SYM_SIDE_NEGATIVE               2
184 /* Anything higher is the order in radial symmetry */
185 #define SYM_SIDE_RADIAL                 3
186
187 #endif /*BLI_GRAPH_H_*/