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