doxygen: editor entry
[blender.git] / source / blender / blenlib / BLI_pbvh.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.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 #ifndef BLI_PBVH_H
24 #define BLI_PBVH_H
25
26 /** \file BLI_pbvh.h
27  *  \ingroup bli
28  *  \brief A BVH for high poly meshes.
29  */
30
31 struct MFace;
32 struct MVert;
33 struct DMGridAdjacency;
34 struct DMGridData;
35 struct PBVH;
36 struct PBVHNode;
37 struct ListBase;
38
39 typedef struct PBVH PBVH;
40 typedef struct PBVHNode PBVHNode;
41
42 typedef struct {
43         float (*co)[3];
44 } PBVHProxyNode;
45
46 /* Callbacks */
47
48 /* returns 1 if the search should continue from this node, 0 otherwise */
49 typedef int (*BLI_pbvh_SearchCallback)(PBVHNode *node, void *data);
50
51 typedef void (*BLI_pbvh_HitCallback)(PBVHNode *node, void *data);
52 typedef void (*BLI_pbvh_HitOccludedCallback)(PBVHNode *node, void *data, float* tmin);
53
54 /* Building */
55
56 PBVH *BLI_pbvh_new(void);
57 void BLI_pbvh_build_mesh(PBVH *bvh, struct MFace *faces, struct MVert *verts,
58                         int totface, int totvert);
59 void BLI_pbvh_build_grids(PBVH *bvh, struct DMGridData **grids,
60         struct DMGridAdjacency *gridadj, int totgrid,
61         int gridsize, void **gridfaces);
62 void BLI_pbvh_free(PBVH *bvh);
63
64 /* Hierarchical Search in the BVH, two methods:
65    * for each hit calling a callback
66    * gather nodes in an array (easy to multithread) */
67
68 void BLI_pbvh_search_callback(PBVH *bvh,
69         BLI_pbvh_SearchCallback scb, void *search_data,
70         BLI_pbvh_HitCallback hcb, void *hit_data);
71
72 void BLI_pbvh_search_gather(PBVH *bvh,
73         BLI_pbvh_SearchCallback scb, void *search_data,
74         PBVHNode ***array, int *tot);
75
76 /* Raycast
77    the hit callback is called for all leaf nodes intersecting the ray;
78    it's up to the callback to find the primitive within the leaves that is
79    hit first */
80
81 void BLI_pbvh_raycast(PBVH *bvh, BLI_pbvh_HitOccludedCallback cb, void *data,
82                           float ray_start[3], float ray_normal[3], int original);
83 int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3],
84         float ray_start[3], float ray_normal[3], float *dist);
85
86 /* Drawing */
87
88 void BLI_pbvh_node_draw(PBVHNode *node, void *data);
89 int BLI_pbvh_node_planes_contain_AABB(PBVHNode *node, void *data);
90 void BLI_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*face_nors)[3], int smooth);
91
92 /* Node Access */
93
94 typedef enum {
95         PBVH_Leaf = 1,
96
97         PBVH_UpdateNormals = 2,
98         PBVH_UpdateBB = 4,
99         PBVH_UpdateOriginalBB = 8,
100         PBVH_UpdateDrawBuffers = 16,
101         PBVH_UpdateRedraw = 32
102 } PBVHNodeFlags;
103
104 void BLI_pbvh_node_mark_update(PBVHNode *node);
105
106 void BLI_pbvh_node_get_grids(PBVH *bvh, PBVHNode *node,
107         int **grid_indices, int *totgrid, int *maxgrid, int *gridsize,
108         struct DMGridData ***griddata, struct DMGridAdjacency **gridadj);
109 void BLI_pbvh_node_num_verts(PBVH *bvh, PBVHNode *node,
110         int *uniquevert, int *totvert);
111 void BLI_pbvh_node_get_verts(PBVH *bvh, PBVHNode *node,
112         int **vert_indices, struct MVert **verts);
113
114 void BLI_pbvh_node_get_BB(PBVHNode *node, float bb_min[3], float bb_max[3]);
115 void BLI_pbvh_node_get_original_BB(PBVHNode *node, float bb_min[3], float bb_max[3]);
116
117 float BLI_pbvh_node_get_tmin(PBVHNode* node);
118
119 /* Update Normals/Bounding Box/Draw Buffers/Redraw and clear flags */
120
121 void BLI_pbvh_update(PBVH *bvh, int flags, float (*face_nors)[3]);
122 void BLI_pbvh_redraw_BB(PBVH *bvh, float bb_min[3], float bb_max[3]);
123 void BLI_pbvh_get_grid_updates(PBVH *bvh, int clear, void ***gridfaces, int *totface);
124 void BLI_pbvh_grids_update(PBVH *bvh, struct DMGridData **grids,
125         struct DMGridAdjacency *gridadj, void **gridfaces);;
126
127 /* vertex deformer */
128 float (*BLI_pbvh_get_vertCos(struct PBVH *pbvh))[3];
129 void BLI_pbvh_apply_vertCos(struct PBVH *pbvh, float (*vertCos)[3]);
130 int BLI_pbvh_isDeformed(struct PBVH *pbvh);
131
132
133 /* Vertex Iterator */
134
135 /* this iterator has quite a lot of code, but it's designed to:
136    - allow the compiler to eliminate dead code and variables
137    - spend most of the time in the relatively simple inner loop */
138
139 #define PBVH_ITER_ALL           0
140 #define PBVH_ITER_UNIQUE        1
141
142 typedef struct PBVHVertexIter {
143         /* iteration */
144         int g;
145         int width;
146         int height;
147         int skip;
148         int gx;
149         int gy;
150         int i;
151
152         /* grid */
153         struct DMGridData **grids;
154         struct DMGridData *grid;
155         int *grid_indices;
156         int totgrid;
157         int gridsize;
158
159         /* mesh */
160         struct MVert *mverts;
161         int totvert;
162         int *vert_indices;
163
164         /* result: these are all computed in the macro, but we assume
165            that compiler optimizations will skip the ones we don't use */
166         struct MVert *mvert;
167         float *co;
168         short *no;
169         float *fno;
170 } PBVHVertexIter;
171
172 #ifdef _MSC_VER
173 #pragma warning (disable:4127) // conditional expression is constant
174 #endif
175
176 #define BLI_pbvh_vertex_iter_begin(bvh, node, vi, mode) \
177         { \
178                 struct DMGridData **grids; \
179                 struct MVert *verts; \
180                 int *grid_indices, totgrid, gridsize, *vert_indices, uniq_verts, totvert; \
181                 \
182                 vi.grid= 0; \
183                 vi.no= 0; \
184                 vi.fno= 0; \
185                 vi.mvert= 0; \
186                 vi.skip= 0; \
187                 \
188                 BLI_pbvh_node_get_grids(bvh, node, &grid_indices, &totgrid, NULL, &gridsize, &grids, NULL); \
189                 BLI_pbvh_node_num_verts(bvh, node, &uniq_verts, &totvert); \
190                 BLI_pbvh_node_get_verts(bvh, node, &vert_indices, &verts); \
191                 \
192                 vi.grids= grids; \
193                 vi.grid_indices= grid_indices; \
194                 vi.totgrid= (grids)? totgrid: 1; \
195                 vi.gridsize= gridsize; \
196                 \
197                 if(mode == PBVH_ITER_ALL) \
198                         vi.totvert = totvert; \
199                 else \
200                         vi.totvert= uniq_verts; \
201                 vi.vert_indices= vert_indices; \
202                 vi.mverts= verts; \
203         }\
204         \
205         for(vi.i=0, vi.g=0; vi.g<vi.totgrid; vi.g++) { \
206                 if(vi.grids) { \
207                         vi.width= vi.gridsize; \
208                         vi.height= vi.gridsize; \
209                         vi.grid= vi.grids[vi.grid_indices[vi.g]]; \
210                         vi.skip= 0; \
211                          \
212                         /*if(mode == PVBH_ITER_UNIQUE) { \
213                                 vi.grid += subm->grid.offset; \
214                                 vi.skip= subm->grid.skip; \
215                                 vi.grid -= skip; \
216                         }*/ \
217                 } \
218                 else { \
219                         vi.width= vi.totvert; \
220                         vi.height= 1; \
221                 } \
222                  \
223                 for(vi.gy=0; vi.gy<vi.height; vi.gy++) { \
224                         if(vi.grid) vi.grid += vi.skip; \
225                         \
226                         for(vi.gx=0; vi.gx<vi.width; vi.gx++, vi.i++) { \
227                                 if(vi.grid) { \
228                                         vi.co= vi.grid->co; \
229                                         vi.fno= vi.grid->no; \
230                                         vi.grid++; \
231                                 } \
232                                 else { \
233                                         vi.mvert= &vi.mverts[vi.vert_indices[vi.gx]]; \
234                                         vi.co= vi.mvert->co; \
235                                         vi.no= vi.mvert->no; \
236                                 } \
237
238 #define BLI_pbvh_vertex_iter_end \
239                         } \
240                 } \
241         }
242
243 void BLI_pbvh_node_get_proxies(PBVHNode* node, PBVHProxyNode** proxies, int* proxy_count);
244 void BLI_pbvh_node_free_proxies(PBVHNode* node);
245 PBVHProxyNode* BLI_pbvh_node_add_proxy(PBVH* bvh, PBVHNode* node);
246 void BLI_pbvh_gather_proxies(PBVH* pbvh, PBVHNode*** nodes,  int* totnode);
247
248 //void BLI_pbvh_node_BB_reset(PBVHNode* node);
249 //void BLI_pbvh_node_BB_expand(PBVHNode* node, float co[3]);
250
251 #endif /* BLI_PBVH_H */
252