Mesh Remap: Face Corner Data: Do not use large epsilon values to create bvhtrees.
[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 __BKE_PBVH_H__
22 #define __BKE_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 #include "BLI_ghash.h"
31 #include "BLI_utildefines.h"
32
33 struct CCGElem;
34 struct CCGKey;
35 struct CCGDerivedMesh;
36 struct CustomData;
37 struct DMFlagMat;
38 struct MPoly;
39 struct MLoop;
40 struct MLoopTri;
41 struct MVert;
42 struct PBVH;
43 struct PBVHNode;
44 struct BMesh;
45 struct BMLog;
46
47 typedef struct PBVH PBVH;
48 typedef struct PBVHNode PBVHNode;
49
50 typedef struct {
51         float (*co)[3];
52 } PBVHProxyNode;
53
54 /* Callbacks */
55
56 /* returns 1 if the search should continue from this node, 0 otherwise */
57 typedef bool (*BKE_pbvh_SearchCallback)(PBVHNode *node, void *data);
58
59 typedef void (*BKE_pbvh_HitCallback)(PBVHNode *node, void *data);
60 typedef void (*BKE_pbvh_HitOccludedCallback)(PBVHNode *node, void *data, float *tmin);
61
62 typedef void (*BKE_pbvh_SearchNearestCallback)(PBVHNode *node, void *data, float *tmin);
63
64 /* Building */
65
66 PBVH *BKE_pbvh_new(void);
67 void BKE_pbvh_build_mesh(
68         PBVH *bvh,
69         const struct MPoly *mpoly, const struct MLoop *mloop,
70         struct MVert *verts, int totvert, struct CustomData *vdata,
71         const struct MLoopTri *looptri, int looptri_num);
72 void BKE_pbvh_build_grids(PBVH *bvh, struct CCGElem **grid_elems,
73                           int totgrid,
74                           struct CCGKey *key, void **gridfaces, struct DMFlagMat *flagmats,
75                           unsigned int **grid_hidden);
76 void BKE_pbvh_build_bmesh(PBVH *bvh, struct BMesh *bm, bool smooth_shading, struct BMLog *log, const int cd_vert_node_offset, const int cd_face_node_offset);
77 void BKE_pbvh_set_ccgdm(PBVH *bvh, struct CCGDerivedMesh *ccgdm);
78 void BKE_pbvh_free(PBVH *bvh);
79 void BKE_pbvh_free_layer_disp(PBVH *bvh);
80
81 /* Hierarchical Search in the BVH, two methods:
82  * - for each hit calling a callback
83  * - gather nodes in an array (easy to multithread) */
84
85 void BKE_pbvh_search_callback(PBVH *bvh,
86                               BKE_pbvh_SearchCallback scb, void *search_data,
87                               BKE_pbvh_HitCallback hcb, void *hit_data);
88
89 void BKE_pbvh_search_gather(PBVH *bvh,
90                             BKE_pbvh_SearchCallback scb, void *search_data,
91                             PBVHNode ***array, int *tot);
92
93 /* Raycast
94  * the hit callback is called for all leaf nodes intersecting the ray;
95  * it's up to the callback to find the primitive within the leaves that is
96  * hit first */
97
98 void BKE_pbvh_raycast(
99         PBVH *bvh, BKE_pbvh_HitOccludedCallback cb, void *data,
100         const float ray_start[3], const float ray_normal[3],
101         bool original);
102
103 bool BKE_pbvh_node_raycast(
104         PBVH *bvh, PBVHNode *node, float (*origco)[3], bool use_origco,
105         const float ray_start[3], const float ray_normal[3],
106         float *depth);
107
108 bool BKE_pbvh_bmesh_node_raycast_detail(
109         PBVHNode *node,
110         const float ray_start[3], const float ray_normal[3],
111         float *depth, float *r_detail);
112
113 /* for orthographic cameras, project the far away ray segment points to the root node so
114  * we can have better precision. */
115 void BKE_pbvh_raycast_project_ray_root(
116         PBVH *bvh, bool original,
117         float ray_start[3], float ray_end[3], float ray_normal[3]);
118
119 void BKE_pbvh_find_nearest_to_ray(
120         PBVH *bvh, BKE_pbvh_HitOccludedCallback cb, void *data,
121         const float ray_start[3], const float ray_normal[3],
122         bool original);
123
124 bool BKE_pbvh_node_find_nearest_to_ray(
125         PBVH *bvh, PBVHNode *node, float (*origco)[3], bool use_origco,
126         const float ray_start[3], const float ray_normal[3],
127         float *depth, float *dist_sq);
128
129 /* Drawing */
130
131 void BKE_pbvh_node_draw(PBVHNode *node, void *data);
132 void BKE_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*face_nors)[3],
133                    int (*setMaterial)(int matnr, void *attribs), bool wireframe, bool fast);
134 void BKE_pbvh_draw_BB(PBVH *bvh);
135
136 /* PBVH Access */
137 typedef enum {
138         PBVH_FACES,
139         PBVH_GRIDS,
140         PBVH_BMESH
141 } PBVHType;
142
143 PBVHType BKE_pbvh_type(const PBVH *bvh);
144 bool     BKE_pbvh_has_faces(const PBVH *bvh);
145
146 /* Get the PBVH root's bounding box */
147 void BKE_pbvh_bounding_box(const PBVH *bvh, float min[3], float max[3]);
148
149 /* multires hidden data, only valid for type == PBVH_GRIDS */
150 unsigned int **BKE_pbvh_grid_hidden(const PBVH *bvh);
151
152 int BKE_pbvh_count_grid_quads(BLI_bitmap **grid_hidden,
153                               int *grid_indices, int totgrid,
154                               int gridsize);
155
156 /* multires level, only valid for type == PBVH_GRIDS */
157 void BKE_pbvh_get_grid_key(const PBVH *pbvh, struct CCGKey *key);
158 struct CCGDerivedMesh *BKE_pbvh_get_ccgdm(const PBVH *bvh);
159
160 /* Only valid for type == PBVH_BMESH */
161 struct BMesh *BKE_pbvh_get_bmesh(PBVH *pbvh);
162 void BKE_pbvh_bmesh_detail_size_set(PBVH *pbvh, float detail_size);
163
164 typedef enum {
165         PBVH_Subdivide = 1,
166         PBVH_Collapse = 2,
167 } PBVHTopologyUpdateMode;
168 bool BKE_pbvh_bmesh_update_topology(
169         PBVH *bvh, PBVHTopologyUpdateMode mode,
170         const float center[3], const float view_normal[3],
171         float radius, const bool use_frontface, const bool use_projected);
172
173 /* Node Access */
174
175 typedef enum {
176         PBVH_Leaf = 1,
177
178         PBVH_UpdateNormals = 2,
179         PBVH_UpdateBB = 4,
180         PBVH_UpdateOriginalBB = 8,
181         PBVH_UpdateDrawBuffers = 16,
182         PBVH_UpdateRedraw = 32,
183
184         PBVH_RebuildDrawBuffers = 64,
185         PBVH_FullyHidden = 128,
186
187         PBVH_UpdateTopology = 256,
188 } PBVHNodeFlags;
189
190 void BKE_pbvh_node_mark_update(PBVHNode *node);
191 void BKE_pbvh_node_mark_rebuild_draw(PBVHNode *node);
192 void BKE_pbvh_node_mark_redraw(PBVHNode *node);
193 void BKE_pbvh_node_mark_normals_update(PBVHNode *node);
194 void BKE_pbvh_node_mark_topology_update(PBVHNode *node);
195 void BKE_pbvh_node_fully_hidden_set(PBVHNode *node, int fully_hidden);
196
197 void BKE_pbvh_node_get_grids(
198         PBVH *bvh, PBVHNode *node,
199         int **grid_indices, int *totgrid, int *maxgrid, int *gridsize,
200         struct CCGElem ***grid_elems);
201 void BKE_pbvh_node_num_verts(
202         PBVH *bvh, PBVHNode *node,
203         int *r_uniquevert, int *r_totvert);
204 void BKE_pbvh_node_get_verts(
205         PBVH *bvh, PBVHNode *node,
206         const int **r_vert_indices, struct MVert **r_verts);
207
208 void BKE_pbvh_node_get_BB(PBVHNode *node, float bb_min[3], float bb_max[3]);
209 void BKE_pbvh_node_get_original_BB(PBVHNode *node, float bb_min[3], float bb_max[3]);
210
211 float BKE_pbvh_node_get_tmin(PBVHNode *node);
212
213 /* test if AABB is at least partially inside the planes' volume */
214 bool BKE_pbvh_node_planes_contain_AABB(PBVHNode *node, void *data);
215 /* test if AABB is at least partially outside the planes' volume */
216 bool BKE_pbvh_node_planes_exclude_AABB(PBVHNode *node, void *data);
217
218 struct GSet *BKE_pbvh_bmesh_node_unique_verts(PBVHNode *node);
219 struct GSet *BKE_pbvh_bmesh_node_other_verts(PBVHNode *node);
220 struct GSet *BKE_pbvh_bmesh_node_faces(PBVHNode *node);
221 void BKE_pbvh_bmesh_node_save_orig(PBVHNode *node);
222 void BKE_pbvh_bmesh_after_stroke(PBVH *bvh);
223
224 /* Update Normals/Bounding Box/Draw Buffers/Redraw and clear flags */
225
226 void BKE_pbvh_update(PBVH *bvh, int flags, float (*face_nors)[3]);
227 void BKE_pbvh_redraw_BB(PBVH *bvh, float bb_min[3], float bb_max[3]);
228 void BKE_pbvh_get_grid_updates(PBVH *bvh, bool clear, void ***r_gridfaces, int *r_totface);
229 void BKE_pbvh_grids_update(PBVH *bvh, struct CCGElem **grid_elems,
230                            void **gridfaces,
231                            struct DMFlagMat *flagmats, unsigned int **grid_hidden);
232
233 /* Layer displacement */
234
235 /* Get the node's displacement layer, creating it if necessary */
236 float *BKE_pbvh_node_layer_disp_get(PBVH *pbvh, PBVHNode *node);
237
238 /* If the node has a displacement layer, free it and set to null */
239 void BKE_pbvh_node_layer_disp_free(PBVHNode *node);
240
241 /* vertex deformer */
242 float (*BKE_pbvh_get_vertCos(struct PBVH *pbvh))[3];
243 void BKE_pbvh_apply_vertCos(struct PBVH *pbvh, float (*vertCos)[3]);
244 bool BKE_pbvh_isDeformed(struct PBVH *pbvh);
245
246 /* Vertex Iterator */
247
248 /* this iterator has quite a lot of code, but it's designed to:
249  * - allow the compiler to eliminate dead code and variables
250  * - spend most of the time in the relatively simple inner loop */
251
252 /* note: PBVH_ITER_ALL does not skip hidden vertices,
253  * PBVH_ITER_UNIQUE does */
254 #define PBVH_ITER_ALL       0
255 #define PBVH_ITER_UNIQUE    1
256
257 typedef struct PBVHVertexIter {
258         /* iteration */
259         int g;
260         int width;
261         int height;
262         int gx;
263         int gy;
264         int i;
265
266         /* grid */
267         struct CCGElem **grids;
268         struct CCGElem *grid;
269         struct CCGKey *key;
270         BLI_bitmap **grid_hidden, *gh;
271         int *grid_indices;
272         int totgrid;
273         int gridsize;
274
275         /* mesh */
276         struct MVert *mverts;
277         int totvert;
278         const int *vert_indices;
279         float *vmask;
280
281         /* bmesh */
282         struct GSetIterator bm_unique_verts;
283         struct GSetIterator bm_other_verts;
284         struct CustomData *bm_vdata;
285         int cd_vert_mask_offset;
286
287         /* result: these are all computed in the macro, but we assume
288          * that compiler optimization's will skip the ones we don't use */
289         struct MVert *mvert;
290         struct BMVert *bm_vert;
291         float *co;
292         short *no;
293         float *fno;
294         float *mask;
295 } PBVHVertexIter;
296
297 void pbvh_vertex_iter_init(PBVH *bvh, PBVHNode *node,
298                            PBVHVertexIter *vi, int mode);
299
300 #define BKE_pbvh_vertex_iter_begin(bvh, node, vi, mode) \
301         pbvh_vertex_iter_init(bvh, node, &vi, mode); \
302          \
303         for (vi.i = 0, vi.g = 0; vi.g < vi.totgrid; vi.g++) { \
304                 if (vi.grids) { \
305                         vi.width = vi.gridsize; \
306                         vi.height = vi.gridsize; \
307                         vi.grid = vi.grids[vi.grid_indices[vi.g]]; \
308                         if (mode == PBVH_ITER_UNIQUE) \
309                                 vi.gh = vi.grid_hidden[vi.grid_indices[vi.g]];   \
310                 } \
311                 else { \
312                         vi.width = vi.totvert; \
313                         vi.height = 1; \
314                 } \
315                  \
316                 for (vi.gy = 0; vi.gy < vi.height; vi.gy++) { \
317                         for (vi.gx = 0; vi.gx < vi.width; vi.gx++, vi.i++) { \
318                                 if (vi.grid) { \
319                                         vi.co = CCG_elem_co(vi.key, vi.grid); \
320                                         vi.fno = CCG_elem_no(vi.key, vi.grid); \
321                                         vi.mask = vi.key->has_mask ? CCG_elem_mask(vi.key, vi.grid) : NULL; \
322                                         vi.grid = CCG_elem_next(vi.key, vi.grid); \
323                                         if (vi.gh) { \
324                                                 if (BLI_BITMAP_TEST(vi.gh, vi.gy * vi.gridsize + vi.gx)) \
325                                                         continue; \
326                                         } \
327                                 } \
328                                 else if (vi.mverts) { \
329                                         vi.mvert = &vi.mverts[vi.vert_indices[vi.gx]]; \
330                                         if (mode == PBVH_ITER_UNIQUE && vi.mvert->flag & ME_HIDE) \
331                                                 continue; \
332                                         vi.co = vi.mvert->co; \
333                                         vi.no = vi.mvert->no; \
334                                         if (vi.vmask) \
335                                                 vi.mask = &vi.vmask[vi.vert_indices[vi.gx]]; \
336                                 } \
337                                 else { \
338                                         if (!BLI_gsetIterator_done(&vi.bm_unique_verts)) {\
339                                                 vi.bm_vert = BLI_gsetIterator_getKey(&vi.bm_unique_verts); \
340                                                 BLI_gsetIterator_step(&vi.bm_unique_verts); \
341                                         } \
342                                         else { \
343                                                 vi.bm_vert = BLI_gsetIterator_getKey(&vi.bm_other_verts); \
344                                                 BLI_gsetIterator_step(&vi.bm_other_verts); \
345                                         } \
346                                         if (mode == PBVH_ITER_UNIQUE && \
347                                                 BM_elem_flag_test(vi.bm_vert, BM_ELEM_HIDDEN)) \
348                                                 continue; \
349                                         vi.co = vi.bm_vert->co; \
350                                         vi.fno = vi.bm_vert->no; \
351                                         vi.mask = BM_ELEM_CD_GET_VOID_P(vi.bm_vert, vi.cd_vert_mask_offset); \
352                                 }
353
354 #define BKE_pbvh_vertex_iter_end \
355                         } \
356                 } \
357         }
358
359 void BKE_pbvh_node_get_proxies(PBVHNode *node, PBVHProxyNode **proxies, int *proxy_count);
360 void BKE_pbvh_node_free_proxies(PBVHNode *node);
361 PBVHProxyNode *BKE_pbvh_node_add_proxy(PBVH *bvh, PBVHNode *node);
362 void BKE_pbvh_gather_proxies(PBVH *pbvh, PBVHNode ***nodes,  int *totnode);
363 void BKE_pbvh_node_get_bm_orco_data(
364         PBVHNode *node,
365         int (**r_orco_tris)[3], int *r_orco_tris_num, float (**r_orco_coords)[3]);
366
367 bool BKE_pbvh_node_vert_update_check_any(PBVH *bvh, PBVHNode *node);
368
369 //void BKE_pbvh_node_BB_reset(PBVHNode *node);
370 //void BKE_pbvh_node_BB_expand(PBVHNode *node, float co[3]);
371
372 void pbvh_show_diffuse_color_set(PBVH *bvh, bool show_diffuse_color);
373 void pbvh_show_mask_set(PBVH *bvh, bool show_mask);
374
375 #endif /* __BKE_PBVH_H__ */