correct fsf address
[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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 void BLI_pbvh_node_get_verts(PBVH *bvh, PBVHNode *node,
104         int **vert_indices, struct MVert **verts);
105
106 void BLI_pbvh_node_get_BB(PBVHNode *node, float bb_min[3], float bb_max[3]);
107 void BLI_pbvh_node_get_original_BB(PBVHNode *node, float bb_min[3], float bb_max[3]);
108
109 /* Update Normals/Bounding Box/Draw Buffers/Redraw and clear flags */
110
111 void BLI_pbvh_update(PBVH *bvh, int flags, float (*face_nors)[3]);
112 void BLI_pbvh_redraw_BB(PBVH *bvh, float bb_min[3], float bb_max[3]);
113 void BLI_pbvh_get_grid_updates(PBVH *bvh, int clear, void ***gridfaces, int *totface);
114
115 /* Vertex Iterator */
116
117 /* this iterator has quite a lot of code, but it's designed to:
118    - allow the compiler to eliminate dead code and variables
119    - spend most of the time in the relatively simple inner loop */
120
121 #define PBVH_ITER_ALL           0
122 #define PBVH_ITER_UNIQUE        1
123
124 typedef struct PBVHVertexIter {
125         /* iteration */
126         int g;
127         int width;
128         int height;
129         int skip;
130         int gx;
131         int gy;
132         int i;
133
134         /* grid */
135         struct DMGridData **grids;
136         struct DMGridData *grid;
137         int *grid_indices;
138         int totgrid;
139         int gridsize;
140
141         /* mesh */
142         struct MVert *mverts;
143         int totvert;
144         int *vert_indices;
145
146         /* result: these are all computed in the macro, but we assume
147            that compiler optimizations will skip the ones we don't use */
148         struct MVert *mvert;
149         float *co;
150         short *no;
151         float *fno;
152 } PBVHVertexIter;
153
154 #define BLI_pbvh_vertex_iter_begin(bvh, node, vi, mode) \
155         { \
156                 struct DMGridData **grids; \
157                 struct MVert *verts; \
158                 int *grid_indices, totgrid, gridsize, *vert_indices, uniq_verts, totvert; \
159                 \
160                 memset(&vi, 0, sizeof(PBVHVertexIter)); \
161                 \
162                 BLI_pbvh_node_get_grids(bvh, node, &grid_indices, &totgrid, NULL, &gridsize, &grids, NULL); \
163                 BLI_pbvh_node_num_verts(bvh, node, &uniq_verts, &totvert); \
164                 BLI_pbvh_node_get_verts(bvh, node, &vert_indices, &verts); \
165                 \
166                 vi.grids= grids; \
167                 vi.grid_indices= grid_indices; \
168                 vi.totgrid= (grids)? totgrid: 1; \
169                 vi.gridsize= gridsize; \
170                 \
171                 if(mode == PBVH_ITER_ALL) \
172                         vi.totvert = totvert; \
173                 else \
174                         vi.totvert= uniq_verts; \
175                 vi.vert_indices= vert_indices; \
176                 vi.mverts= verts; \
177         }\
178         \
179         for(vi.i=0, vi.g=0; vi.g<vi.totgrid; vi.g++) { \
180                 if(vi.grids) { \
181                         vi.width= vi.gridsize; \
182                         vi.height= vi.gridsize; \
183                         vi.grid= vi.grids[vi.grid_indices[vi.g]]; \
184                         vi.skip= 0; \
185                         \
186                         /*if(mode == PVBH_ITER_UNIQUE) { \
187                                 vi.grid += subm->grid.offset; \
188                                 vi.skip= subm->grid.skip; \
189                                 vi.grid -= skip; \
190                         }*/ \
191                 } \
192                 else { \
193                         vi.width= vi.totvert; \
194                         vi.height= 1; \
195                 } \
196                 \
197                 for(vi.gy=0; vi.gy<vi.height; vi.gy++) { \
198                         if(vi.grid) vi.grid += vi.skip; \
199                         \
200                         for(vi.gx=0; vi.gx<vi.width; vi.gx++, vi.i++) { \
201                                 if(vi.grid) { \
202                                         vi.co= vi.grid->co; \
203                                         vi.fno= vi.grid->no; \
204                                         vi.grid++; \
205                                 } \
206                                 else { \
207                                         vi.mvert= &vi.mverts[vi.vert_indices[vi.gx]]; \
208                                         vi.co= vi.mvert->co; \
209                                         vi.no= vi.mvert->no; \
210                                 } \
211
212 #define BLI_pbvh_vertex_iter_end \
213                         } \
214                 } \
215         }
216
217
218 #endif /* BLI_PBVH_H */
219