Fix build error on Windows 32 bit.
[blender-staging.git] / source / blender / blenkernel / BKE_bvhutils.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  * The Original Code is Copyright (C) 2006 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): AndrĂ© Pinto
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27 #ifndef __BKE_BVHUTILS_H__
28 #define __BKE_BVHUTILS_H__
29
30 /** \file BKE_bvhutils.h
31  *  \ingroup bke
32  */
33
34 #include "BLI_bitmap.h"
35 #include "BLI_kdopbvh.h"
36
37 /**
38  * This header encapsulates necessary code to buld a BVH
39  */
40
41 struct DerivedMesh;
42 struct BMEditMesh;
43 struct MVert;
44 struct MFace;
45
46 typedef struct LinkNode BVHCache;
47
48 /**
49  * Struct that stores basic information about a BVHTree built from a edit-mesh.
50  */
51 typedef struct BVHTreeFromEditMesh {
52         struct BVHTree *tree;
53
54         /* default callbacks to bvh nearest and raycast */
55         BVHTree_NearestPointCallback nearest_callback;
56         BVHTree_RayCastCallback raycast_callback;
57
58         struct BMEditMesh *em;
59
60         /* radius for raycast */
61         float sphere_radius;
62
63         /* Private data */
64         bool cached;
65
66 } BVHTreeFromEditMesh;
67
68 /**
69  * Struct that stores basic information about a BVHTree built from a mesh.
70  */
71 typedef struct BVHTreeFromMesh {
72         struct BVHTree *tree;
73
74         /* default callbacks to bvh nearest and raycast */
75         BVHTree_NearestPointCallback nearest_callback;
76         BVHTree_RayCastCallback raycast_callback;
77
78         /* Vertex array, so that callbacks have instante access to data */
79         const struct MVert *vert;
80         const struct MEdge *edge;     /* only used for BVHTreeFromMeshEdges */
81         const struct MFace *face;
82         const struct MLoop *loop;
83         const struct MLoopTri *looptri;
84         bool vert_allocated;
85         bool edge_allocated;
86         bool face_allocated;
87         bool loop_allocated;
88         bool looptri_allocated;
89
90         /* radius for raycast */
91         float sphere_radius;
92
93         /* Private data */
94         bool cached;
95
96 } BVHTreeFromMesh;
97
98 /**
99  * Builds a bvh tree where nodes are the relevant elements of the given mesh.
100  * Configures BVHTreeFromMesh.
101  *
102  * The tree is build in mesh space coordinates, this means special care must be made on queries
103  * so that the coordinates and rays are first translated on the mesh local coordinates.
104  * Reason for this is that bvh_from_mesh_* can use a cache in some cases and so it becomes possible to reuse a BVHTree.
105  *
106  * free_bvhtree_from_mesh should be called when the tree is no longer needed.
107  */
108 BVHTree *bvhtree_from_editmesh_verts(
109         BVHTreeFromEditMesh *data, struct BMEditMesh *em,
110         float epsilon, int tree_type, int axis);
111 BVHTree *bvhtree_from_editmesh_verts_ex(
112         BVHTreeFromEditMesh *data, struct BMEditMesh *em,
113         const BLI_bitmap *mask, int verts_num_active,
114         float epsilon, int tree_type, int axis);
115
116 BVHTree *bvhtree_from_mesh_verts(
117         struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
118 BVHTree *bvhtree_from_mesh_verts_ex(
119         struct BVHTreeFromMesh *data, const struct MVert *vert, const int numVerts,
120         const bool vert_allocated, const BLI_bitmap *mask, int verts_num_active,
121         float epsilon, int tree_type, int axis);
122
123 BVHTree *bvhtree_from_editmesh_edges(
124         BVHTreeFromEditMesh *data, struct BMEditMesh *em,
125         float epsilon, int tree_type, int axis);
126 BVHTree *bvhtree_from_editmesh_edges_ex(
127         BVHTreeFromEditMesh *data, struct BMEditMesh *em,
128         const BLI_bitmap *edges_mask, int edges_num_active,
129         float epsilon, int tree_type, int axis);
130
131 BVHTree *bvhtree_from_mesh_edges(
132         struct BVHTreeFromMesh *data, struct DerivedMesh *mesh,
133         float epsilon, int tree_type, int axis);
134 BVHTree *bvhtree_from_mesh_edges_ex(
135         struct BVHTreeFromMesh *data,
136         const struct MVert *vert, const bool vert_allocated,
137         const struct MEdge *edge, const int edges_num, const bool edge_allocated,
138         const BLI_bitmap *edges_mask, int edges_num_active,
139         float epsilon, int tree_type, int axis);
140
141 BVHTree *bvhtree_from_mesh_faces(
142         struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon,
143         int tree_type, int axis);
144 BVHTree *bvhtree_from_mesh_faces_ex(
145         struct BVHTreeFromMesh *data,
146         const struct MVert *vert, const bool vert_allocated,
147         const struct MFace *face, const int numFaces, const bool face_allocated,
148         const BLI_bitmap *mask, int numFaces_active,
149         float epsilon, int tree_type, int axis);
150
151 BVHTree *bvhtree_from_editmesh_looptri(
152         BVHTreeFromEditMesh *data, struct BMEditMesh *em,
153         float epsilon, int tree_type, int axis, BVHCache **bvhCache);
154 BVHTree *bvhtree_from_editmesh_looptri_ex(
155         BVHTreeFromEditMesh *data, struct BMEditMesh *em,
156         const BLI_bitmap *mask, int looptri_num_active,
157         float epsilon, int tree_type, int axis, BVHCache **bvhCache);
158
159 BVHTree *bvhtree_from_mesh_looptri(
160         struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
161 BVHTree *bvhtree_from_mesh_looptri_ex(
162         struct BVHTreeFromMesh *data,
163         const struct MVert *vert, const bool vert_allocated,
164         const struct MLoop *mloop, const bool loop_allocated,
165         const struct MLoopTri *looptri, const int looptri_num, const bool looptri_allocated,
166         const BLI_bitmap *mask, int looptri_num_active,
167         float epsilon, int tree_type, int axis);
168
169 /**
170  * Frees data allocated by a call to bvhtree_from_mesh_*.
171  */
172 void free_bvhtree_from_editmesh(struct BVHTreeFromEditMesh *data);
173 void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data);
174
175 /**
176  * Math functions used by callbacks
177  */
178 float bvhtree_ray_tri_intersection(
179         const BVHTreeRay *ray, const float m_dist,
180         const float v0[3], const float v1[3], const float v2[3]);
181 float bvhtree_sphereray_tri_intersection(
182         const BVHTreeRay *ray, float radius, const float m_dist,
183         const float v0[3], const float v1[3], const float v2[3]);
184
185
186 /**
187  * BVHCache
188  */
189
190 /* Using local coordinates */
191 enum {
192         BVHTREE_FROM_VERTS           = 0,
193         BVHTREE_FROM_EDGES           = 1,
194         BVHTREE_FROM_FACES           = 2,
195         BVHTREE_FROM_LOOPTRI         = 3,
196
197         BVHTREE_FROM_EM_LOOPTRI      = 4,
198 };
199
200
201 BVHTree *bvhcache_find(BVHCache *cache, int type);
202 bool     bvhcache_has_tree(const BVHCache *cache, const BVHTree *tree);
203 void     bvhcache_insert(BVHCache **cache_p, BVHTree *tree, int type);
204 void     bvhcache_init(BVHCache **cache_p);
205 void     bvhcache_free(BVHCache **cache_p);
206
207
208 #endif