svn merge -r40140:r40148 https://svn.blender.org/svnroot/bf-blender/trunk/blender
[blender.git] / source / blender / blenlib / BLI_graph.h
1 #ifndef BLI_GRAPH_H_
2 #define BLI_GRAPH_H_
3
4 /** \file BLI_graph.h
5  *  \ingroup bli
6  */
7
8 #include "DNA_listBase.h"
9
10 struct BGraph;
11 struct BNode;
12 struct BArc;
13
14 struct RadialArc;
15
16 typedef void (*FreeArc)(struct BArc*);
17 typedef void (*FreeNode)(struct BNode*);
18 typedef void (*RadialSymmetry)(struct BNode* root_node, struct RadialArc* ring, int total);
19 typedef void (*AxialSymmetry)(struct BNode* root_node, struct BNode* node1, struct BNode* node2, struct BArc* arc1, struct BArc* arc2);
20
21 /* IF YOU MODIFY THOSE TYPES, YOU NEED TO UPDATE ALL THOSE THAT "INHERIT" FROM THEM
22  * 
23  * RigGraph, ReebGraph
24  * 
25  * */
26
27 typedef struct BGraph {
28         ListBase        arcs;
29         ListBase        nodes;
30         
31         float length;
32         
33         /* function pointer to deal with custom fonctionnality */
34         FreeArc                 free_arc;
35         FreeNode                free_node;
36         RadialSymmetry  radial_symmetry;
37         AxialSymmetry   axial_symmetry;
38 } BGraph;
39
40 typedef struct BNode {
41         void *next, *prev;
42         float p[3];
43         int flag;
44
45         int degree;
46         struct BArc **arcs;
47         
48         int subgraph_index;
49
50         int symmetry_level;
51         int symmetry_flag;
52         float symmetry_axis[3];
53 } BNode;
54
55 typedef struct BArc {
56         void *next, *prev;
57         struct BNode *head, *tail;
58         int flag;
59
60         float length;
61
62         int symmetry_level;
63         int symmetry_group;
64         int symmetry_flag;
65 } BArc;
66
67 struct BArcIterator;
68
69 void* IT_head(void* iter);
70 void* IT_tail(void* iter);
71 void* IT_peek(void* iter, int n);
72 void* IT_next(void* iter);
73 void* IT_nextN(void* iter, int n);
74 void* IT_previous(void* iter);
75 int   IT_stopped(void* iter);
76
77 typedef void* (*HeadFct)(void* iter);
78 typedef void* (*TailFct)(void* iter);
79 typedef void* (*PeekFct)(void* iter, int n);
80 typedef void* (*NextFct)(void* iter);
81 typedef void* (*NextNFct)(void* iter, int n);
82 typedef void* (*PreviousFct)(void* iter);
83 typedef int   (*StoppedFct)(void* iter);
84
85 typedef struct BArcIterator {
86         HeadFct         head;
87         TailFct         tail;
88         PeekFct         peek;
89         NextFct         next;
90         NextNFct        nextN;
91         PreviousFct     previous;
92         StoppedFct      stopped;
93         
94         float *p, *no;
95         float size;
96         
97         int length;
98         int index;
99 } BArcIterator;
100
101 /* Helper structure for radial symmetry */
102 typedef struct RadialArc
103 {
104         struct BArc *arc; 
105         float n[3]; /* normalized vector joining the nodes of the arc */
106 } RadialArc;
107
108 BNode *BLI_otherNode(BArc *arc, BNode *node);
109
110 void BLI_freeNode(BGraph *graph, BNode *node);
111 void BLI_removeNode(BGraph *graph, BNode *node);
112
113 void BLI_removeArc(BGraph *graph, BArc *arc);
114
115 void BLI_flagNodes(BGraph *graph, int flag);
116 void BLI_flagArcs(BGraph *graph, int flag);
117
118 int BLI_hasAdjacencyList(BGraph *rg);
119 void BLI_buildAdjacencyList(BGraph *rg);
120 void BLI_rebuildAdjacencyList(BGraph* rg);
121 void BLI_rebuildAdjacencyListForNode(BGraph* rg, BNode *node);
122 void BLI_freeAdjacencyList(BGraph *rg);
123
124 int BLI_FlagSubgraphs(BGraph *graph);
125 void BLI_ReflagSubgraph(BGraph *graph, int old_subgraph, int new_subgraph);
126
127 #define SHAPE_RADIX 10 /* each shape level is encoded this base */
128
129 int BLI_subtreeShape(BGraph *graph, BNode *node, BArc *rootArc, int include_root);
130 float BLI_subtreeLength(BNode *node);
131 void BLI_calcGraphLength(BGraph *graph);
132
133 void BLI_replaceNode(BGraph *graph, BNode *node_src, BNode *node_replaced);
134 void BLI_replaceNodeInArc(BGraph *graph, BArc *arc, BNode *node_src, BNode *node_replaced);
135 void BLI_removeDoubleNodes(BGraph *graph, float limit);
136 BNode * BLI_FindNodeByPosition(BGraph *graph, float *p, float limit);
137
138 BArc * BLI_findConnectedArc(BGraph *graph, BArc *arc, BNode *v);
139
140 int     BLI_isGraphCyclic(BGraph *graph);
141
142 /*------------ Symmetry handling ------------*/
143 void BLI_markdownSymmetry(BGraph *graph, BNode *root_node, float limit);
144
145 void BLI_mirrorAlongAxis(float v[3], float center[3], float axis[3]);
146
147 /* BNode symmetry flags */
148 #define SYM_TOPOLOGICAL 1
149 #define SYM_PHYSICAL    2
150
151 /* the following two are exclusive */
152 #define SYM_AXIAL               4
153 #define SYM_RADIAL              8
154
155 /* BArc symmetry flags
156  * 
157  * axial symetry sides */
158 #define SYM_SIDE_POSITIVE               1
159 #define SYM_SIDE_NEGATIVE               2
160 /* Anything higher is the order in radial symmetry */
161 #define SYM_SIDE_RADIAL                 3
162
163 #endif /*BLI_GRAPH_H_*/