Sculpt: Grid based PBVH
[blender.git] / source / blender / blenlib / BLI_pbvh.h
1 /**
2  * A BVH for high poly meshes.
3  * 
4  * $Id$
5  *
6  * ***** BEGIN GPL LICENSE BLOCK *****
7  *
8  * This program is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, write to the Free Software Foundation,
20  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
21  *
22  * ***** END GPL LICENSE BLOCK *****
23  */
24
25 #ifndef BLI_PBVH_H
26 #define BLI_PBVH_H
27
28 struct MFace;
29 struct MVert;
30 struct DMGridData;
31 struct PBVH;
32 struct PBVHNode;
33 struct ListBase;
34
35 typedef struct PBVH PBVH;
36 typedef struct PBVHNode PBVHNode;
37
38 /* Callbacks */
39
40 /* returns 1 if the search should continue from this node, 0 otherwise */
41 typedef int (*BLI_pbvh_SearchCallback)(PBVHNode *node, void *data);
42
43 typedef void (*BLI_pbvh_HitCallback)(PBVHNode *node, void *data);
44
45 /* Building */
46
47 PBVH *BLI_pbvh_new(void);
48 void BLI_pbvh_build_mesh(PBVH *bvh, struct MFace *faces, struct MVert *verts,
49                     int totface, int totvert);
50 void BLI_pbvh_build_grids(PBVH *bvh, struct DMGridData **grids, int totgrid,
51         int gridsize, void **gridfaces);
52 void BLI_pbvh_free(PBVH *bvh);
53
54 /* Hierarchical Search in the BVH, two methods:
55    * for each hit calling a callback
56    * gather nodes in an array (easy to multithread) */
57
58 void BLI_pbvh_search_callback(PBVH *bvh,
59         BLI_pbvh_SearchCallback scb, void *search_data,
60         BLI_pbvh_HitCallback hcb, void *hit_data);
61
62 void BLI_pbvh_search_gather(PBVH *bvh,
63         BLI_pbvh_SearchCallback scb, void *search_data,
64         PBVHNode ***array, int *tot);
65
66 /* Raycast
67    the hit callback is called for all leaf nodes intersecting the ray;
68    it's up to the callback to find the primitive within the leaves that is
69    hit first */
70
71 void BLI_pbvh_raycast(PBVH *bvh, BLI_pbvh_HitCallback cb, void *data,
72                       float ray_start[3], float ray_normal[3], int original);
73 int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3],
74         float ray_start[3], float ray_normal[3], float *dist);
75
76 /* Drawing */
77
78 void BLI_pbvh_node_draw(PBVHNode *node, void *data);
79 int BLI_pbvh_node_planes_contain_AABB(PBVHNode *node, void *data);
80 void BLI_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*face_nors)[3]);
81
82 /* Node Access */
83
84 typedef enum {
85         PBVH_Leaf = 1,
86
87         PBVH_UpdateNormals = 2,
88         PBVH_UpdateBB = 4,
89         PBVH_UpdateOriginalBB = 4,
90         PBVH_UpdateDrawBuffers = 8,
91         PBVH_UpdateRedraw = 16
92 } PBVHNodeFlags;
93
94 void BLI_pbvh_node_mark_update(PBVHNode *node);
95
96 void BLI_pbvh_node_get_grids(PBVH *bvh, PBVHNode *node,
97         int **grid_indices, int *totgrid, int *maxgrid, int *gridsize);
98 void BLI_pbvh_node_num_verts(PBVH *bvh, PBVHNode *node,
99         int *uniquevert, int *totvert);
100
101 void BLI_pbvh_node_get_BB(PBVHNode *node, float bb_min[3], float bb_max[3]);
102 void BLI_pbvh_node_get_original_BB(PBVHNode *node, float bb_min[3], float bb_max[3]);
103
104 /* Update Normals/Bounding Box/Draw Buffers/Redraw and clear flags */
105
106 void BLI_pbvh_update(PBVH *bvh, int flags, float (*face_nors)[3]);
107 void BLI_pbvh_redraw_BB(PBVH *bvh, float bb_min[3], float bb_max[3]);
108 void BLI_pbvh_get_grid_updates(PBVH *bvh, void ***gridfaces, int *totface);
109
110 /* Vertex Iterator */
111
112 /* this iterator has quite a lot of code, but it's designed to:
113    - allow the compiler to eliminate dead code and variables
114    - spend most of the time in the relatively simple inner loop */
115
116 #define PBVH_ITER_ALL           0
117 #define PBVH_ITER_UNIQUE        1
118
119 typedef struct PBVHVertexIter {
120         /* iteration */
121         int g;
122         int width;
123         int height;
124         int skip;
125         int gx;
126         int gy;
127         int i;
128
129         /* grid */
130         struct DMGridData **grids;
131         struct DMGridData *grid;
132         int *grid_indices;
133         int totgrid;
134         int gridsize;
135
136         /* mesh */
137         struct MVert *mverts;
138         int totvert;
139         int *vert_indices;
140
141         /* result: these are all computed in the macro, but we assume
142            that compiler optimizations will skip the ones we don't use */
143         struct MVert *mvert;
144         float *co;
145         short *no;
146         float *fno;
147 } PBVHVertexIter;
148
149 void BLI_pbvh_node_verts_iter_init(PBVH *bvh, PBVHNode *node, PBVHVertexIter *vi, int mode);
150
151 #define BLI_pbvh_vertex_iter_begin(bvh, node, vi, mode) \
152         /* XXX breaks aliasing! */ \
153         BLI_pbvh_node_verts_iter_init(bvh, node, &vi, mode); \
154         \
155         for(vi.i=0, vi.g=0; vi.g<vi.totgrid; vi.g++) { \
156                 if(vi.grids) { \
157                         vi.width= vi.gridsize; \
158                         vi.height= vi.gridsize; \
159                         vi.grid= vi.grids[vi.grid_indices[vi.g]]; \
160                         vi.skip= 0; \
161                         \
162                         /*if(mode == PVBH_ITER_UNIQUE) { \
163                                 vi.grid += subm->grid.offset; \
164                                 vi.skip= subm->grid.skip; \
165                                 vi.grid -= skip; \
166                         }*/ \
167                 } \
168                 else { \
169                         vi.width= vi.totvert; \
170                         vi.height= 1; \
171                 } \
172                 \
173                 for(vi.gy=0; vi.gy<vi.height; vi.gy++) { \
174                         if(vi.grid) vi.grid += vi.skip; \
175                         \
176                         for(vi.gx=0; vi.gx<vi.width; vi.gx++, vi.i++) { \
177                                 if(vi.grid) { \
178                                         vi.co= vi.grid->co; \
179                                         vi.fno= vi.grid->no; \
180                                         vi.grid++; \
181                                 } \
182                                 else { \
183                                         vi.mvert= &vi.mverts[vi.vert_indices[vi.gx]]; \
184                                         vi.co= vi.mvert->co; \
185                                         vi.no= vi.mvert->no; \
186                                 } \
187
188 #define BLI_pbvh_vertex_iter_end \
189                         } \
190                 } \
191         }
192
193
194 #endif /* BLI_PBVH_H */
195