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