Sculpt Branch:
[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 DMGridAdjacency;
31 struct DMGridData;
32 struct PBVH;
33 struct PBVHNode;
34 struct ListBase;
35
36 typedef struct PBVH PBVH;
37 typedef struct PBVHNode PBVHNode;
38
39 /* Callbacks */
40
41 /* returns 1 if the search should continue from this node, 0 otherwise */
42 typedef int (*BLI_pbvh_SearchCallback)(PBVHNode *node, void *data);
43
44 typedef void (*BLI_pbvh_HitCallback)(PBVHNode *node, void *data);
45
46 /* Building */
47
48 PBVH *BLI_pbvh_new(void);
49 void BLI_pbvh_build_mesh(PBVH *bvh, struct MFace *faces, struct MVert *verts,
50                     int totface, int totvert);
51 void BLI_pbvh_build_grids(PBVH *bvh, struct DMGridData **grids,
52         struct DMGridAdjacency *gridadj, int totgrid,
53         int gridsize, void **gridfaces);
54 void BLI_pbvh_free(PBVH *bvh);
55
56 /* Hierarchical Search in the BVH, two methods:
57    * for each hit calling a callback
58    * gather nodes in an array (easy to multithread) */
59
60 void BLI_pbvh_search_callback(PBVH *bvh,
61         BLI_pbvh_SearchCallback scb, void *search_data,
62         BLI_pbvh_HitCallback hcb, void *hit_data);
63
64 void BLI_pbvh_search_gather(PBVH *bvh,
65         BLI_pbvh_SearchCallback scb, void *search_data,
66         PBVHNode ***array, int *tot);
67
68 /* Raycast
69    the hit callback is called for all leaf nodes intersecting the ray;
70    it's up to the callback to find the primitive within the leaves that is
71    hit first */
72
73 void BLI_pbvh_raycast(PBVH *bvh, BLI_pbvh_HitCallback cb, void *data,
74                       float ray_start[3], float ray_normal[3], int original);
75 int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3],
76         float ray_start[3], float ray_normal[3], float *dist);
77
78 /* Drawing */
79
80 void BLI_pbvh_node_draw(PBVHNode *node, void *data);
81 int BLI_pbvh_node_planes_contain_AABB(PBVHNode *node, void *data);
82 void BLI_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*face_nors)[3]);
83
84 /* Node Access */
85
86 typedef enum {
87         PBVH_Leaf = 1,
88
89         PBVH_UpdateNormals = 2,
90         PBVH_UpdateBB = 4,
91         PBVH_UpdateOriginalBB = 8,
92         PBVH_UpdateDrawBuffers = 16,
93         PBVH_UpdateRedraw = 32
94 } PBVHNodeFlags;
95
96 void BLI_pbvh_node_mark_update(PBVHNode *node);
97
98 void BLI_pbvh_node_get_grids(PBVH *bvh, PBVHNode *node,
99         int **grid_indices, int *totgrid, int *maxgrid, int *gridsize,
100         struct DMGridData ***griddata, struct DMGridAdjacency **gridadj);
101 void BLI_pbvh_node_num_verts(PBVH *bvh, PBVHNode *node,
102         int *uniquevert, int *totvert);
103
104 void BLI_pbvh_node_get_BB(PBVHNode *node, float bb_min[3], float bb_max[3]);
105 void BLI_pbvh_node_get_original_BB(PBVHNode *node, float bb_min[3], float bb_max[3]);
106
107 /* Update Normals/Bounding Box/Draw Buffers/Redraw and clear flags */
108
109 void BLI_pbvh_update(PBVH *bvh, int flags, float (*face_nors)[3]);
110 void BLI_pbvh_redraw_BB(PBVH *bvh, float bb_min[3], float bb_max[3]);
111 void BLI_pbvh_get_grid_updates(PBVH *bvh, int clear, void ***gridfaces, int *totface);
112
113 /* Vertex Iterator */
114
115 /* this iterator has quite a lot of code, but it's designed to:
116    - allow the compiler to eliminate dead code and variables
117    - spend most of the time in the relatively simple inner loop */
118
119 #define PBVH_ITER_ALL           0
120 #define PBVH_ITER_UNIQUE        1
121
122 typedef struct PBVHVertexIter {
123         /* iteration */
124         int g;
125         int width;
126         int height;
127         int skip;
128         int gx;
129         int gy;
130         int i;
131
132         /* grid */
133         struct DMGridData **grids;
134         struct DMGridData *grid;
135         int *grid_indices;
136         int totgrid;
137         int gridsize;
138
139         /* mesh */
140         struct MVert *mverts;
141         int totvert;
142         int *vert_indices;
143
144         /* result: these are all computed in the macro, but we assume
145            that compiler optimizations will skip the ones we don't use */
146         struct MVert *mvert;
147         float *co;
148         short *no;
149         float *fno;
150 } PBVHVertexIter;
151
152 void BLI_pbvh_node_verts_iter_init(PBVH *bvh, PBVHNode *node, PBVHVertexIter *vi, int mode);
153
154 #define BLI_pbvh_vertex_iter_begin(bvh, node, vi, mode) \
155         /* XXX breaks aliasing! */ \
156         BLI_pbvh_node_verts_iter_init(bvh, node, &vi, mode); \
157         \
158         for(vi.i=0, vi.g=0; vi.g<vi.totgrid; vi.g++) { \
159                 if(vi.grids) { \
160                         vi.width= vi.gridsize; \
161                         vi.height= vi.gridsize; \
162                         vi.grid= vi.grids[vi.grid_indices[vi.g]]; \
163                         vi.skip= 0; \
164                         \
165                         /*if(mode == PVBH_ITER_UNIQUE) { \
166                                 vi.grid += subm->grid.offset; \
167                                 vi.skip= subm->grid.skip; \
168                                 vi.grid -= skip; \
169                         }*/ \
170                 } \
171                 else { \
172                         vi.width= vi.totvert; \
173                         vi.height= 1; \
174                 } \
175                 \
176                 for(vi.gy=0; vi.gy<vi.height; vi.gy++) { \
177                         if(vi.grid) vi.grid += vi.skip; \
178                         \
179                         for(vi.gx=0; vi.gx<vi.width; vi.gx++, vi.i++) { \
180                                 if(vi.grid) { \
181                                         vi.co= vi.grid->co; \
182                                         vi.fno= vi.grid->no; \
183                                         vi.grid++; \
184                                 } \
185                                 else { \
186                                         vi.mvert= &vi.mverts[vi.vert_indices[vi.gx]]; \
187                                         vi.co= vi.mvert->co; \
188                                         vi.no= vi.mvert->no; \
189                                 } \
190
191 #define BLI_pbvh_vertex_iter_end \
192                         } \
193                 } \
194         }
195
196
197 #endif /* BLI_PBVH_H */
198