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