1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  */
16 
17 #pragma once
18 
19 /** \file
20  * \ingroup bke
21  * \brief A BVH for high poly meshes.
22  */
23 
24 #include "BLI_bitmap.h"
25 #include "BLI_ghash.h"
26 
27 /* For embedding CCGKey in iterator. */
28 #include "BKE_ccg.h"
29 
30 #ifdef __cplusplus
31 extern "C" {
32 #endif
33 
34 struct BMLog;
35 struct BMesh;
36 struct CCGElem;
37 struct CCGKey;
38 struct CustomData;
39 struct DMFlagMat;
40 struct GPU_PBVH_Buffers;
41 struct IsectRayPrecalc;
42 struct MLoop;
43 struct MLoopTri;
44 struct MPoly;
45 struct MVert;
46 struct Mesh;
47 struct PBVH;
48 struct PBVHNode;
49 struct SubdivCCG;
50 struct TaskParallelSettings;
51 struct TaskParallelTLS;
52 
53 typedef struct PBVH PBVH;
54 typedef struct PBVHNode PBVHNode;
55 
56 typedef struct {
57   float (*co)[3];
58 } PBVHProxyNode;
59 
60 typedef struct {
61   float (*color)[4];
62 } PBVHColorBufferNode;
63 
64 typedef enum {
65   PBVH_Leaf = 1 << 0,
66 
67   PBVH_UpdateNormals = 1 << 1,
68   PBVH_UpdateBB = 1 << 2,
69   PBVH_UpdateOriginalBB = 1 << 3,
70   PBVH_UpdateDrawBuffers = 1 << 4,
71   PBVH_UpdateRedraw = 1 << 5,
72   PBVH_UpdateMask = 1 << 6,
73   PBVH_UpdateVisibility = 1 << 8,
74 
75   PBVH_RebuildDrawBuffers = 1 << 9,
76   PBVH_FullyHidden = 1 << 10,
77   PBVH_FullyMasked = 1 << 11,
78   PBVH_FullyUnmasked = 1 << 12,
79 
80   PBVH_UpdateTopology = 1 << 13,
81   PBVH_UpdateColor = 1 << 14,
82 } PBVHNodeFlags;
83 
84 typedef struct PBVHFrustumPlanes {
85   float (*planes)[4];
86   int num_planes;
87 } PBVHFrustumPlanes;
88 
89 void BKE_pbvh_set_frustum_planes(PBVH *pbvh, PBVHFrustumPlanes *planes);
90 void BKE_pbvh_get_frustum_planes(PBVH *pbvh, PBVHFrustumPlanes *planes);
91 
92 /* Callbacks */
93 
94 /* returns 1 if the search should continue from this node, 0 otherwise */
95 typedef bool (*BKE_pbvh_SearchCallback)(PBVHNode *node, void *data);
96 
97 typedef void (*BKE_pbvh_HitCallback)(PBVHNode *node, void *data);
98 typedef void (*BKE_pbvh_HitOccludedCallback)(PBVHNode *node, void *data, float *tmin);
99 
100 typedef void (*BKE_pbvh_SearchNearestCallback)(PBVHNode *node, void *data, float *tmin);
101 
102 /* Building */
103 
104 PBVH *BKE_pbvh_new(void);
105 void BKE_pbvh_build_mesh(PBVH *pbvh,
106                          const struct Mesh *mesh,
107                          const struct MPoly *mpoly,
108                          const struct MLoop *mloop,
109                          struct MVert *verts,
110                          int totvert,
111                          struct CustomData *vdata,
112                          struct CustomData *ldata,
113                          struct CustomData *pdata,
114                          const struct MLoopTri *looptri,
115                          int looptri_num);
116 void BKE_pbvh_build_grids(PBVH *pbvh,
117                           struct CCGElem **grids,
118                           int totgrid,
119                           struct CCGKey *key,
120                           void **gridfaces,
121                           struct DMFlagMat *flagmats,
122                           unsigned int **grid_hidden);
123 void BKE_pbvh_build_bmesh(PBVH *pbvh,
124                           struct BMesh *bm,
125                           bool smooth_shading,
126                           struct BMLog *log,
127                           const int cd_vert_node_offset,
128                           const int cd_face_node_offset);
129 void BKE_pbvh_free(PBVH *pbvh);
130 
131 /* Hierarchical Search in the BVH, two methods:
132  * - for each hit calling a callback
133  * - gather nodes in an array (easy to multithread) */
134 
135 void BKE_pbvh_search_callback(PBVH *pbvh,
136                               BKE_pbvh_SearchCallback scb,
137                               void *search_data,
138                               BKE_pbvh_HitCallback hcb,
139                               void *hit_data);
140 
141 void BKE_pbvh_search_gather(
142     PBVH *pbvh, BKE_pbvh_SearchCallback scb, void *search_data, PBVHNode ***array, int *tot);
143 
144 /* Raycast
145  * the hit callback is called for all leaf nodes intersecting the ray;
146  * it's up to the callback to find the primitive within the leaves that is
147  * hit first */
148 
149 void BKE_pbvh_raycast(PBVH *pbvh,
150                       BKE_pbvh_HitOccludedCallback cb,
151                       void *data,
152                       const float ray_start[3],
153                       const float ray_normal[3],
154                       bool original);
155 
156 bool BKE_pbvh_node_raycast(PBVH *pbvh,
157                            PBVHNode *node,
158                            float (*origco)[3],
159                            bool use_origco,
160                            const float ray_start[3],
161                            const float ray_normal[3],
162                            struct IsectRayPrecalc *isect_precalc,
163                            float *depth,
164                            int *active_vertex_index,
165                            int *active_face_grid_index,
166                            float *face_normal);
167 
168 bool BKE_pbvh_bmesh_node_raycast_detail(PBVHNode *node,
169                                         const float ray_start[3],
170                                         struct IsectRayPrecalc *isect_precalc,
171                                         float *depth,
172                                         float *r_edge_length);
173 
174 /* for orthographic cameras, project the far away ray segment points to the root node so
175  * we can have better precision. */
176 void BKE_pbvh_raycast_project_ray_root(
177     PBVH *pbvh, bool original, float ray_start[3], float ray_end[3], float ray_normal[3]);
178 
179 void BKE_pbvh_find_nearest_to_ray(PBVH *pbvh,
180                                   BKE_pbvh_HitOccludedCallback cb,
181                                   void *data,
182                                   const float ray_start[3],
183                                   const float ray_normal[3],
184                                   bool original);
185 
186 bool BKE_pbvh_node_find_nearest_to_ray(PBVH *pbvh,
187                                        PBVHNode *node,
188                                        float (*origco)[3],
189                                        bool use_origco,
190                                        const float ray_start[3],
191                                        const float ray_normal[3],
192                                        float *depth,
193                                        float *dist_sq);
194 
195 /* Drawing */
196 
197 void BKE_pbvh_draw_cb(PBVH *pbvh,
198                       bool update_only_visible,
199                       PBVHFrustumPlanes *update_frustum,
200                       PBVHFrustumPlanes *draw_frustum,
201                       void (*draw_fn)(void *user_data, struct GPU_PBVH_Buffers *buffers),
202                       void *user_data);
203 
204 void BKE_pbvh_draw_debug_cb(
205     PBVH *pbvh,
206     void (*draw_fn)(void *user_data, const float bmin[3], const float bmax[3], PBVHNodeFlags flag),
207     void *user_data);
208 
209 /* PBVH Access */
210 typedef enum {
211   PBVH_FACES,
212   PBVH_GRIDS,
213   PBVH_BMESH,
214 } PBVHType;
215 
216 PBVHType BKE_pbvh_type(const PBVH *pbvh);
217 bool BKE_pbvh_has_faces(const PBVH *pbvh);
218 
219 /* Get the PBVH root's bounding box */
220 void BKE_pbvh_bounding_box(const PBVH *pbvh, float min[3], float max[3]);
221 
222 /* multires hidden data, only valid for type == PBVH_GRIDS */
223 unsigned int **BKE_pbvh_grid_hidden(const PBVH *pbvh);
224 
225 int BKE_pbvh_count_grid_quads(BLI_bitmap **grid_hidden,
226                               const int *grid_indices,
227                               int totgrid,
228                               int gridsize);
229 
230 void BKE_pbvh_sync_face_sets_to_grids(PBVH *pbvh);
231 
232 /* multires level, only valid for type == PBVH_GRIDS */
233 const struct CCGKey *BKE_pbvh_get_grid_key(const PBVH *pbvh);
234 
235 struct CCGElem **BKE_pbvh_get_grids(const PBVH *pbvh);
236 BLI_bitmap **BKE_pbvh_get_grid_visibility(const PBVH *pbvh);
237 int BKE_pbvh_get_grid_num_vertices(const PBVH *pbvh);
238 
239 /* Only valid for type == PBVH_BMESH */
240 struct BMesh *BKE_pbvh_get_bmesh(PBVH *pbvh);
241 void BKE_pbvh_bmesh_detail_size_set(PBVH *pbvh, float detail_size);
242 
243 typedef enum {
244   PBVH_Subdivide = 1,
245   PBVH_Collapse = 2,
246 } PBVHTopologyUpdateMode;
247 bool BKE_pbvh_bmesh_update_topology(PBVH *pbvh,
248                                     PBVHTopologyUpdateMode mode,
249                                     const float center[3],
250                                     const float view_normal[3],
251                                     float radius,
252                                     const bool use_frontface,
253                                     const bool use_projected);
254 
255 /* Node Access */
256 
257 void BKE_pbvh_node_mark_update(PBVHNode *node);
258 void BKE_pbvh_node_mark_update_mask(PBVHNode *node);
259 void BKE_pbvh_node_mark_update_color(PBVHNode *node);
260 void BKE_pbvh_node_mark_update_visibility(PBVHNode *node);
261 void BKE_pbvh_node_mark_rebuild_draw(PBVHNode *node);
262 void BKE_pbvh_node_mark_redraw(PBVHNode *node);
263 void BKE_pbvh_node_mark_normals_update(PBVHNode *node);
264 void BKE_pbvh_node_mark_topology_update(PBVHNode *node);
265 void BKE_pbvh_node_fully_hidden_set(PBVHNode *node, int fully_hidden);
266 bool BKE_pbvh_node_fully_hidden_get(PBVHNode *node);
267 void BKE_pbvh_node_fully_masked_set(PBVHNode *node, int fully_masked);
268 bool BKE_pbvh_node_fully_masked_get(PBVHNode *node);
269 void BKE_pbvh_node_fully_unmasked_set(PBVHNode *node, int fully_masked);
270 bool BKE_pbvh_node_fully_unmasked_get(PBVHNode *node);
271 
272 void BKE_pbvh_node_get_grids(PBVH *pbvh,
273                              PBVHNode *node,
274                              int **grid_indices,
275                              int *totgrid,
276                              int *maxgrid,
277                              int *gridsize,
278                              struct CCGElem ***r_griddata);
279 void BKE_pbvh_node_num_verts(PBVH *pbvh, PBVHNode *node, int *r_uniquevert, int *r_totvert);
280 void BKE_pbvh_node_get_verts(PBVH *pbvh,
281                              PBVHNode *node,
282                              const int **r_vert_indices,
283                              struct MVert **r_verts);
284 
285 void BKE_pbvh_node_get_BB(PBVHNode *node, float bb_min[3], float bb_max[3]);
286 void BKE_pbvh_node_get_original_BB(PBVHNode *node, float bb_min[3], float bb_max[3]);
287 
288 float BKE_pbvh_node_get_tmin(PBVHNode *node);
289 
290 /* test if AABB is at least partially inside the PBVHFrustumPlanes volume */
291 bool BKE_pbvh_node_frustum_contain_AABB(PBVHNode *node, void *frustum);
292 /* test if AABB is at least partially outside the PBVHFrustumPlanes volume */
293 bool BKE_pbvh_node_frustum_exclude_AABB(PBVHNode *node, void *frustum);
294 
295 struct GSet *BKE_pbvh_bmesh_node_unique_verts(PBVHNode *node);
296 struct GSet *BKE_pbvh_bmesh_node_other_verts(PBVHNode *node);
297 struct GSet *BKE_pbvh_bmesh_node_faces(PBVHNode *node);
298 void BKE_pbvh_bmesh_node_save_orig(struct BMesh *bm, PBVHNode *node);
299 void BKE_pbvh_bmesh_after_stroke(PBVH *pbvh);
300 
301 /* Update Bounding Box/Redraw and clear flags */
302 
303 void BKE_pbvh_update_bounds(PBVH *pbvh, int flags);
304 void BKE_pbvh_update_vertex_data(PBVH *pbvh, int flags);
305 void BKE_pbvh_update_visibility(PBVH *pbvh);
306 void BKE_pbvh_update_normals(PBVH *pbvh, struct SubdivCCG *subdiv_ccg);
307 void BKE_pbvh_redraw_BB(PBVH *pbvh, float bb_min[3], float bb_max[3]);
308 void BKE_pbvh_get_grid_updates(PBVH *pbvh, bool clear, void ***r_gridfaces, int *r_totface);
309 void BKE_pbvh_grids_update(PBVH *pbvh,
310                            struct CCGElem **grids,
311                            void **gridfaces,
312                            struct DMFlagMat *flagmats,
313                            unsigned int **grid_hidden);
314 void BKE_pbvh_subdiv_cgg_set(PBVH *pbvh, struct SubdivCCG *subdiv_ccg);
315 void BKE_pbvh_face_sets_set(PBVH *pbvh, int *face_sets);
316 
317 void BKE_pbvh_face_sets_color_set(PBVH *pbvh, int seed, int color_default);
318 
319 void BKE_pbvh_respect_hide_set(PBVH *pbvh, bool respect_hide);
320 
321 /* vertex deformer */
322 float (*BKE_pbvh_vert_coords_alloc(struct PBVH *pbvh))[3];
323 void BKE_pbvh_vert_coords_apply(struct PBVH *pbvh, const float (*vertCos)[3], const int totvert);
324 bool BKE_pbvh_is_deformed(struct PBVH *pbvh);
325 
326 /* Vertex Iterator */
327 
328 /* this iterator has quite a lot of code, but it's designed to:
329  * - allow the compiler to eliminate dead code and variables
330  * - spend most of the time in the relatively simple inner loop */
331 
332 /* note: PBVH_ITER_ALL does not skip hidden vertices,
333  * PBVH_ITER_UNIQUE does */
334 #define PBVH_ITER_ALL 0
335 #define PBVH_ITER_UNIQUE 1
336 
337 typedef struct PBVHVertexIter {
338   /* iteration */
339   int g;
340   int width;
341   int height;
342   int gx;
343   int gy;
344   int i;
345   int index;
346   bool respect_hide;
347 
348   /* grid */
349   struct CCGKey key;
350   struct CCGElem **grids;
351   struct CCGElem *grid;
352   BLI_bitmap **grid_hidden, *gh;
353   int *grid_indices;
354   int totgrid;
355   int gridsize;
356 
357   /* mesh */
358   struct MVert *mverts;
359   int totvert;
360   const int *vert_indices;
361   struct MPropCol *vcol;
362   float *vmask;
363 
364   /* bmesh */
365   struct GSetIterator bm_unique_verts;
366   struct GSetIterator bm_other_verts;
367   struct CustomData *bm_vdata;
368   int cd_vert_mask_offset;
369 
370   /* result: these are all computed in the macro, but we assume
371    * that compiler optimization's will skip the ones we don't use */
372   struct MVert *mvert;
373   struct BMVert *bm_vert;
374   float *co;
375   short *no;
376   float *fno;
377   float *mask;
378   float *col;
379   bool visible;
380 } PBVHVertexIter;
381 
382 void pbvh_vertex_iter_init(PBVH *pbvh, PBVHNode *node, PBVHVertexIter *vi, int mode);
383 
384 #define BKE_pbvh_vertex_iter_begin(pbvh, node, vi, mode) \
385   pbvh_vertex_iter_init(pbvh, node, &vi, mode); \
386 \
387   for (vi.i = 0, vi.g = 0; vi.g < vi.totgrid; vi.g++) { \
388     if (vi.grids) { \
389       vi.width = vi.gridsize; \
390       vi.height = vi.gridsize; \
391       vi.index = vi.grid_indices[vi.g] * vi.key.grid_area - 1; \
392       vi.grid = vi.grids[vi.grid_indices[vi.g]]; \
393       if (mode == PBVH_ITER_UNIQUE) { \
394         vi.gh = vi.grid_hidden[vi.grid_indices[vi.g]]; \
395       } \
396     } \
397     else { \
398       vi.width = vi.totvert; \
399       vi.height = 1; \
400     } \
401 \
402     for (vi.gy = 0; vi.gy < vi.height; vi.gy++) { \
403       for (vi.gx = 0; vi.gx < vi.width; vi.gx++, vi.i++) { \
404         if (vi.grid) { \
405           vi.co = CCG_elem_co(&vi.key, vi.grid); \
406           vi.fno = CCG_elem_no(&vi.key, vi.grid); \
407           vi.mask = vi.key.has_mask ? CCG_elem_mask(&vi.key, vi.grid) : NULL; \
408           vi.grid = CCG_elem_next(&vi.key, vi.grid); \
409           vi.index++; \
410           vi.visible = true; \
411           if (vi.gh) { \
412             if (BLI_BITMAP_TEST(vi.gh, vi.gy * vi.gridsize + vi.gx)) { \
413               continue; \
414             } \
415           } \
416         } \
417         else if (vi.mverts) { \
418           vi.mvert = &vi.mverts[vi.vert_indices[vi.gx]]; \
419           if (vi.respect_hide) { \
420             vi.visible = !(vi.mvert->flag & ME_HIDE); \
421             if (mode == PBVH_ITER_UNIQUE && !vi.visible) { \
422               continue; \
423             } \
424           } \
425           else { \
426             BLI_assert(vi.visible); \
427           } \
428           vi.co = vi.mvert->co; \
429           vi.no = vi.mvert->no; \
430           vi.index = vi.vert_indices[vi.i]; \
431           if (vi.vmask) { \
432             vi.mask = &vi.vmask[vi.index]; \
433           } \
434           if (vi.vcol) { \
435             vi.col = vi.vcol[vi.index].color; \
436           } \
437         } \
438         else { \
439           if (!BLI_gsetIterator_done(&vi.bm_unique_verts)) { \
440             vi.bm_vert = BLI_gsetIterator_getKey(&vi.bm_unique_verts); \
441             BLI_gsetIterator_step(&vi.bm_unique_verts); \
442           } \
443           else { \
444             vi.bm_vert = BLI_gsetIterator_getKey(&vi.bm_other_verts); \
445             BLI_gsetIterator_step(&vi.bm_other_verts); \
446           } \
447           vi.visible = !BM_elem_flag_test_bool(vi.bm_vert, BM_ELEM_HIDDEN); \
448           if (mode == PBVH_ITER_UNIQUE && !vi.visible) { \
449             continue; \
450           } \
451           vi.co = vi.bm_vert->co; \
452           vi.fno = vi.bm_vert->no; \
453           vi.index = BM_elem_index_get(vi.bm_vert); \
454           vi.mask = BM_ELEM_CD_GET_VOID_P(vi.bm_vert, vi.cd_vert_mask_offset); \
455         }
456 
457 #define BKE_pbvh_vertex_iter_end \
458   } \
459   } \
460   } \
461   ((void)0)
462 
463 void BKE_pbvh_node_get_proxies(PBVHNode *node, PBVHProxyNode **proxies, int *proxy_count);
464 void BKE_pbvh_node_free_proxies(PBVHNode *node);
465 PBVHProxyNode *BKE_pbvh_node_add_proxy(PBVH *pbvh, PBVHNode *node);
466 void BKE_pbvh_gather_proxies(PBVH *pbvh, PBVHNode ***r_array, int *r_tot);
467 void BKE_pbvh_node_get_bm_orco_data(PBVHNode *node,
468                                     int (**r_orco_tris)[3],
469                                     int *r_orco_tris_num,
470                                     float (**r_orco_coords)[3]);
471 
472 bool BKE_pbvh_node_vert_update_check_any(PBVH *pbvh, PBVHNode *node);
473 
474 // void BKE_pbvh_node_BB_reset(PBVHNode *node);
475 // void BKE_pbvh_node_BB_expand(PBVHNode *node, float co[3]);
476 
477 bool pbvh_has_mask(PBVH *pbvh);
478 void pbvh_show_mask_set(PBVH *pbvh, bool show_mask);
479 
480 bool pbvh_has_face_sets(PBVH *pbvh);
481 void pbvh_show_face_sets_set(PBVH *pbvh, bool show_face_sets);
482 
483 /* Parallelization */
484 void BKE_pbvh_parallel_range_settings(struct TaskParallelSettings *settings,
485                                       bool use_threading,
486                                       int totnode);
487 
488 struct MVert *BKE_pbvh_get_verts(const PBVH *pbvh);
489 
490 PBVHColorBufferNode *BKE_pbvh_node_color_buffer_get(PBVHNode *node);
491 void BKE_pbvh_node_color_buffer_free(PBVH *pbvh);
492 
493 #ifdef __cplusplus
494 }
495 #endif
496