[#34013] [video sequence editor] Offset and crop of strips are wrong
[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 /* Needed for BMesh functions used in the PBVH iterator macro */
34 #include "bmesh.h"
35
36 struct CCGElem;
37 struct CCGKey;
38 struct CustomData;
39 struct DMFlagMat;
40 struct DMGridAdjacency;
41 struct GHash;
42 struct MFace;
43 struct MVert;
44 struct PBVH;
45 struct PBVHNode;
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 int (*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 /* Building */
63
64 PBVH *BKE_pbvh_new(void);
65 void BKE_pbvh_build_mesh(PBVH *bvh, struct MFace *faces, struct MVert *verts,
66                          int totface, int totvert, struct CustomData *vdata);
67 void BKE_pbvh_build_grids(PBVH *bvh, struct CCGElem **grid_elems,
68                           struct DMGridAdjacency *gridadj, int totgrid,
69                           struct CCGKey *key, void **gridfaces, struct DMFlagMat *flagmats,
70                           unsigned int **grid_hidden);
71 void BKE_pbvh_build_bmesh(PBVH *bvh, struct BMesh *bm, int smooth_shading,
72                           struct BMLog *log);
73
74 void BKE_pbvh_free(PBVH *bvh);
75
76 /* Hierarchical Search in the BVH, two methods:
77  * - for each hit calling a callback
78  * - gather nodes in an array (easy to multithread) */
79
80 void BKE_pbvh_search_callback(PBVH *bvh,
81                               BKE_pbvh_SearchCallback scb, void *search_data,
82                               BKE_pbvh_HitCallback hcb, void *hit_data);
83
84 void BKE_pbvh_search_gather(PBVH *bvh,
85                             BKE_pbvh_SearchCallback scb, void *search_data,
86                             PBVHNode ***array, int *tot);
87
88 /* Raycast
89  * the hit callback is called for all leaf nodes intersecting the ray;
90  * it's up to the callback to find the primitive within the leaves that is
91  * hit first */
92
93 void BKE_pbvh_raycast(PBVH *bvh, BKE_pbvh_HitOccludedCallback cb, void *data,
94                       const float ray_start[3], const float ray_normal[3],
95                       int original);
96
97 int BKE_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3], int use_origco,
98                           const float ray_start[3], const float ray_normal[3],
99                           float *dist);
100
101 /* Drawing */
102
103 void BKE_pbvh_node_draw(PBVHNode *node, void *data);
104 void BKE_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*face_nors)[3],
105                    int (*setMaterial)(int, void *attribs), int wireframe);
106
107 /* PBVH Access */
108 typedef enum {
109         PBVH_FACES,
110         PBVH_GRIDS,
111         PBVH_BMESH
112 } PBVHType;
113
114 PBVHType BKE_pbvh_type(const PBVH *bvh);
115
116 /* Get the PBVH root's bounding box */
117 void BKE_pbvh_bounding_box(const PBVH *bvh, float min[3], float max[3]);
118
119 /* multires hidden data, only valid for type == PBVH_GRIDS */
120 unsigned int **BKE_pbvh_grid_hidden(const PBVH *bvh);
121
122 /* multires level, only valid for type == PBVH_GRIDS */
123 void BKE_pbvh_get_grid_key(const PBVH *pbvh, struct CCGKey *key);
124
125 /* Only valid for type == PBVH_BMESH */
126 BMesh *BKE_pbvh_get_bmesh(PBVH *pbvh);
127 void BKE_pbvh_bmesh_detail_size_set(PBVH *pbvh, float detail_size);
128
129 typedef enum {
130         PBVH_Subdivide = 1,
131         PBVH_Collapse = 2,
132 } PBVHTopologyUpdateMode;
133 int BKE_pbvh_bmesh_update_topology(PBVH *bvh, PBVHTopologyUpdateMode mode,
134                                    const float center[3], float radius);
135
136 /* Node Access */
137
138 typedef enum {
139         PBVH_Leaf = 1,
140
141         PBVH_UpdateNormals = 2,
142         PBVH_UpdateBB = 4,
143         PBVH_UpdateOriginalBB = 8,
144         PBVH_UpdateDrawBuffers = 16,
145         PBVH_UpdateRedraw = 32,
146
147         PBVH_RebuildDrawBuffers = 64,
148         PBVH_FullyHidden = 128,
149
150         PBVH_UpdateTopology = 256,
151 } PBVHNodeFlags;
152
153 void BKE_pbvh_node_mark_update(PBVHNode *node);
154 void BKE_pbvh_node_mark_rebuild_draw(PBVHNode *node);
155 void BKE_pbvh_node_fully_hidden_set(PBVHNode *node, int fully_hidden);
156 void BKE_pbvh_node_mark_topology_update(PBVHNode *node);
157
158 void BKE_pbvh_node_get_grids(PBVH *bvh, PBVHNode *node,
159                              int **grid_indices, int *totgrid, int *maxgrid, int *gridsize,
160                              struct CCGElem ***grid_elems, struct DMGridAdjacency **gridadj);
161 void BKE_pbvh_node_num_verts(PBVH *bvh, PBVHNode *node,
162                              int *uniquevert, int *totvert);
163 void BKE_pbvh_node_get_verts(PBVH *bvh, PBVHNode *node,
164                              int **vert_indices, struct MVert **verts);
165
166 void BKE_pbvh_node_get_BB(PBVHNode * node, float bb_min[3], float bb_max[3]);
167 void BKE_pbvh_node_get_original_BB(PBVHNode * node, float bb_min[3], float bb_max[3]);
168
169 float BKE_pbvh_node_get_tmin(PBVHNode *node);
170
171 /* test if AABB is at least partially inside the planes' volume */
172 int BKE_pbvh_node_planes_contain_AABB(PBVHNode *node, void *data);
173 /* test if AABB is at least partially outside the planes' volume */
174 int BKE_pbvh_node_planes_exclude_AABB(PBVHNode *node, void *data);
175
176 struct GHash *BKE_pbvh_bmesh_node_unique_verts(PBVHNode *node);
177 struct GHash *BKE_pbvh_bmesh_node_other_verts(PBVHNode *node); 
178 void BKE_pbvh_bmesh_node_save_orig(PBVHNode *node);
179 void BKE_pbvh_bmesh_after_stroke(PBVH *bvh);
180
181 /* Update Normals/Bounding Box/Draw Buffers/Redraw and clear flags */
182
183 void BKE_pbvh_update(PBVH *bvh, int flags, float (*face_nors)[3]);
184 void BKE_pbvh_redraw_BB(PBVH * bvh, float bb_min[3], float bb_max[3]);
185 void BKE_pbvh_get_grid_updates(PBVH *bvh, int clear, void ***gridfaces, int *totface);
186 void BKE_pbvh_grids_update(PBVH *bvh, struct CCGElem **grid_elems,
187                            struct DMGridAdjacency *gridadj, void **gridfaces,
188                            struct DMFlagMat *flagmats, unsigned int **grid_hidden);
189
190 /* Layer displacement */
191
192 /* Get the node's displacement layer, creating it if necessary */
193 float *BKE_pbvh_node_layer_disp_get(PBVH *pbvh, PBVHNode *node);
194
195 /* If the node has a displacement layer, free it and set to null */
196 void BKE_pbvh_node_layer_disp_free(PBVHNode *node);
197
198 /* vertex deformer */
199 float (*BKE_pbvh_get_vertCos(struct PBVH *pbvh))[3];
200 void BKE_pbvh_apply_vertCos(struct PBVH *pbvh, float (*vertCos)[3]);
201 int BKE_pbvh_isDeformed(struct PBVH *pbvh);
202
203 /* Vertex Iterator */
204
205 /* this iterator has quite a lot of code, but it's designed to:
206  * - allow the compiler to eliminate dead code and variables
207  * - spend most of the time in the relatively simple inner loop */
208
209 /* note: PBVH_ITER_ALL does not skip hidden vertices,
210  * PBVH_ITER_UNIQUE does */
211 #define PBVH_ITER_ALL       0
212 #define PBVH_ITER_UNIQUE    1
213
214 typedef struct PBVHVertexIter {
215         /* iteration */
216         int g;
217         int width;
218         int height;
219         int gx;
220         int gy;
221         int i;
222
223         /* grid */
224         struct CCGElem **grids;
225         struct CCGElem *grid;
226         struct CCGKey *key;
227         BLI_bitmap *grid_hidden, gh;
228         int *grid_indices;
229         int totgrid;
230         int gridsize;
231
232         /* mesh */
233         struct MVert *mverts;
234         int totvert;
235         int *vert_indices;
236         float *vmask;
237
238         /* bmesh */
239         struct GHashIterator bm_unique_verts;
240         struct GHashIterator bm_other_verts;
241         struct CustomData *bm_vdata;
242
243         /* result: these are all computed in the macro, but we assume
244          * that compiler optimization's will skip the ones we don't use */
245         struct MVert *mvert;
246         struct BMVert *bm_vert;
247         float *co;
248         short *no;
249         float *fno;
250         float *mask;
251 } PBVHVertexIter;
252
253 #ifdef _MSC_VER
254 #pragma warning (disable:4127) // conditional expression is constant
255 #endif
256
257 void pbvh_vertex_iter_init(PBVH *bvh, PBVHNode *node,
258                            PBVHVertexIter *vi, int mode);
259
260 #define BKE_pbvh_vertex_iter_begin(bvh, node, vi, mode) \
261         pbvh_vertex_iter_init(bvh, node, &vi, mode); \
262          \
263         for (vi.i = 0, vi.g = 0; vi.g < vi.totgrid; vi.g++) { \
264                 if (vi.grids) { \
265                         vi.width = vi.gridsize; \
266                         vi.height = vi.gridsize; \
267                         vi.grid = vi.grids[vi.grid_indices[vi.g]]; \
268                         if (mode == PBVH_ITER_UNIQUE) \
269                                 vi.gh = vi.grid_hidden[vi.grid_indices[vi.g]];   \
270                 } \
271                 else { \
272                         vi.width = vi.totvert; \
273                         vi.height = 1; \
274                 } \
275                  \
276                 for (vi.gy = 0; vi.gy < vi.height; vi.gy++) { \
277                         for (vi.gx = 0; vi.gx < vi.width; vi.gx++, vi.i++) { \
278                                 if (vi.grid) { \
279                                         vi.co = CCG_elem_co(vi.key, vi.grid); \
280                                         vi.fno = CCG_elem_no(vi.key, vi.grid); \
281                                         vi.mask = vi.key->has_mask ? CCG_elem_mask(vi.key, vi.grid) : NULL; \
282                                         vi.grid = CCG_elem_next(vi.key, vi.grid); \
283                                         if (vi.gh) { \
284                                                 if (BLI_BITMAP_GET(vi.gh, vi.gy * vi.gridsize + vi.gx)) \
285                                                         continue; \
286                                         } \
287                                 } \
288                                 else if (vi.mverts) { \
289                                         vi.mvert = &vi.mverts[vi.vert_indices[vi.gx]]; \
290                                         if (mode == PBVH_ITER_UNIQUE && vi.mvert->flag & ME_HIDE) \
291                                                 continue; \
292                                         vi.co = vi.mvert->co; \
293                                         vi.no = vi.mvert->no; \
294                                         if (vi.vmask) \
295                                                 vi.mask = &vi.vmask[vi.vert_indices[vi.gx]]; \
296                                 } \
297                                 else { \
298                                         if (!BLI_ghashIterator_isDone(&vi.bm_unique_verts)) {\
299                                                 vi.bm_vert = BLI_ghashIterator_getKey(&vi.bm_unique_verts); \
300                                                 BLI_ghashIterator_step(&vi.bm_unique_verts); \
301                                         } \
302                                         else { \
303                                                 vi.bm_vert = BLI_ghashIterator_getKey(&vi.bm_other_verts); \
304                                                 BLI_ghashIterator_step(&vi.bm_other_verts); \
305                                         } \
306                                         if (mode == PBVH_ITER_UNIQUE && \
307                                                 BM_elem_flag_test(vi.bm_vert, BM_ELEM_HIDDEN)) \
308                                                 continue; \
309                                         vi.co = vi.bm_vert->co; \
310                                         vi.fno = vi.bm_vert->no; \
311                                         vi.mask = CustomData_bmesh_get(vi.bm_vdata, \
312                                                                                                    vi.bm_vert->head.data, \
313                                                                                                    CD_PAINT_MASK); \
314                                 }
315
316 #define BKE_pbvh_vertex_iter_end \
317                         } \
318                 } \
319         }
320
321 void BKE_pbvh_node_get_proxies(PBVHNode *node, PBVHProxyNode **proxies, int *proxy_count);
322 void BKE_pbvh_node_free_proxies(PBVHNode *node);
323 PBVHProxyNode *BKE_pbvh_node_add_proxy(PBVH *bvh, PBVHNode *node);
324 void BKE_pbvh_gather_proxies(PBVH *pbvh, PBVHNode ***nodes,  int *totnode);
325
326 //void BKE_pbvh_node_BB_reset(PBVHNode *node);
327 //void BKE_pbvh_node_BB_expand(PBVHNode *node, float co[3]);
328
329 void pbvh_show_diffuse_color_set(PBVH *bvh, int show_diffuse_color);
330
331 #endif /* __BKE_PBVH_H__ */
332