UI: de-duplicate mask context menu
[blender.git] / source / blender / blenkernel / BKE_bvhutils.h
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2006 by NaN Holding BV.
17  * All rights reserved.
18  */
19 #ifndef __BKE_BVHUTILS_H__
20 #define __BKE_BVHUTILS_H__
21
22 /** \file
23  * \ingroup bke
24  */
25
26 #include "BLI_bitmap.h"
27 #include "BLI_kdopbvh.h"
28
29 /**
30  * This header encapsulates necessary code to build a BVH
31  */
32
33 struct BMEditMesh;
34 struct MFace;
35 struct MVert;
36 struct Mesh;
37
38 typedef struct LinkNode BVHCache;
39
40 /**
41  * Struct that stores basic information about a BVHTree built from a edit-mesh.
42  */
43 typedef struct BVHTreeFromEditMesh {
44   struct BVHTree *tree;
45
46   /* default callbacks to bvh nearest and raycast */
47   BVHTree_NearestPointCallback nearest_callback;
48   BVHTree_RayCastCallback raycast_callback;
49
50   struct BMEditMesh *em;
51
52   /* Private data */
53   bool cached;
54
55 } BVHTreeFromEditMesh;
56
57 /**
58  * Struct that stores basic information about a BVHTree built from a mesh.
59  */
60 typedef struct BVHTreeFromMesh {
61   struct BVHTree *tree;
62
63   /* default callbacks to bvh nearest and raycast */
64   BVHTree_NearestPointCallback nearest_callback;
65   BVHTree_RayCastCallback raycast_callback;
66
67   /* Vertex array, so that callbacks have instante access to data */
68   const struct MVert *vert;
69   const struct MEdge *edge; /* only used for BVHTreeFromMeshEdges */
70   const struct MFace *face;
71   const struct MLoop *loop;
72   const struct MLoopTri *looptri;
73   bool vert_allocated;
74   bool edge_allocated;
75   bool face_allocated;
76   bool loop_allocated;
77   bool looptri_allocated;
78
79   /* Private data */
80   bool cached;
81
82 } BVHTreeFromMesh;
83
84 /**
85  * Builds a bvh tree where nodes are the relevant elements of the given mesh.
86  * Configures #BVHTreeFromMesh.
87  *
88  * The tree is build in mesh space coordinates, this means special care must be made on queries
89  * so that the coordinates and rays are first translated on the mesh local coordinates.
90  * Reason for this is that bvh_from_mesh_* can use a cache in some cases and so it
91  * becomes possible to reuse a #BVHTree.
92  *
93  * free_bvhtree_from_mesh should be called when the tree is no longer needed.
94  */
95 BVHTree *bvhtree_from_editmesh_verts(
96     BVHTreeFromEditMesh *data, struct BMEditMesh *em, float epsilon, int tree_type, int axis);
97
98 BVHTree *bvhtree_from_editmesh_verts_ex(BVHTreeFromEditMesh *data,
99                                         struct BMEditMesh *em,
100                                         const BLI_bitmap *mask,
101                                         int verts_num_active,
102                                         float epsilon,
103                                         int tree_type,
104                                         int axis,
105                                         const int bvh_cache_type,
106                                         BVHCache **bvh_cache);
107
108 BVHTree *bvhtree_from_mesh_verts_ex(struct BVHTreeFromMesh *data,
109                                     const struct MVert *vert,
110                                     const int numVerts,
111                                     const bool vert_allocated,
112                                     const BLI_bitmap *mask,
113                                     int verts_num_active,
114                                     float epsilon,
115                                     int tree_type,
116                                     int axis,
117                                     const int bvh_cache_type,
118                                     BVHCache **bvh_cache);
119
120 BVHTree *bvhtree_from_editmesh_edges(
121     BVHTreeFromEditMesh *data, struct BMEditMesh *em, float epsilon, int tree_type, int axis);
122
123 BVHTree *bvhtree_from_editmesh_edges_ex(BVHTreeFromEditMesh *data,
124                                         struct BMEditMesh *em,
125                                         const BLI_bitmap *edges_mask,
126                                         int edges_num_active,
127                                         float epsilon,
128                                         int tree_type,
129                                         int axis,
130                                         const int bvh_cache_type,
131                                         BVHCache **bvh_cache);
132
133 BVHTree *bvhtree_from_mesh_edges_ex(struct BVHTreeFromMesh *data,
134                                     const struct MVert *vert,
135                                     const bool vert_allocated,
136                                     const struct MEdge *edge,
137                                     const int edges_num,
138                                     const bool edge_allocated,
139                                     const BLI_bitmap *edges_mask,
140                                     int edges_num_active,
141                                     float epsilon,
142                                     int tree_type,
143                                     int axis,
144                                     const int bvh_cache_type,
145                                     BVHCache **bvh_cache);
146
147 BVHTree *bvhtree_from_mesh_faces_ex(struct BVHTreeFromMesh *data,
148                                     const struct MVert *vert,
149                                     const bool vert_allocated,
150                                     const struct MFace *face,
151                                     const int numFaces,
152                                     const bool face_allocated,
153                                     const BLI_bitmap *mask,
154                                     int numFaces_active,
155                                     float epsilon,
156                                     int tree_type,
157                                     int axis,
158                                     const int bvh_cache_type,
159                                     BVHCache **bvh_cache);
160
161 BVHTree *bvhtree_from_editmesh_looptri(
162     BVHTreeFromEditMesh *data, struct BMEditMesh *em, float epsilon, int tree_type, int axis);
163
164 BVHTree *bvhtree_from_editmesh_looptri_ex(BVHTreeFromEditMesh *data,
165                                           struct BMEditMesh *em,
166                                           const BLI_bitmap *mask,
167                                           int looptri_num_active,
168                                           float epsilon,
169                                           int tree_type,
170                                           int axis,
171                                           const int bvh_cache_type,
172                                           BVHCache **bvh_cache);
173
174 BVHTree *bvhtree_from_mesh_looptri_ex(struct BVHTreeFromMesh *data,
175                                       const struct MVert *vert,
176                                       const bool vert_allocated,
177                                       const struct MLoop *mloop,
178                                       const bool loop_allocated,
179                                       const struct MLoopTri *looptri,
180                                       const int looptri_num,
181                                       const bool looptri_allocated,
182                                       const BLI_bitmap *mask,
183                                       int looptri_num_active,
184                                       float epsilon,
185                                       int tree_type,
186                                       int axis,
187                                       const int bvh_cache_type,
188                                       BVHCache **bvh_cache);
189
190 BVHTree *BKE_bvhtree_from_mesh_get(struct BVHTreeFromMesh *data,
191                                    struct Mesh *mesh,
192                                    const int type,
193                                    const int tree_type);
194
195 BVHTree *BKE_bvhtree_from_editmesh_get(BVHTreeFromEditMesh *data,
196                                        struct BMEditMesh *em,
197                                        const int tree_type,
198                                        const int bvh_cache_type,
199                                        BVHCache **bvh_cache);
200
201 /**
202  * Frees data allocated by a call to bvhtree_from_mesh_*.
203  */
204 void free_bvhtree_from_editmesh(struct BVHTreeFromEditMesh *data);
205 void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data);
206
207 /**
208  * Math functions used by callbacks
209  */
210 float bvhtree_ray_tri_intersection(const BVHTreeRay *ray,
211                                    const float m_dist,
212                                    const float v0[3],
213                                    const float v1[3],
214                                    const float v2[3]);
215 float bvhtree_sphereray_tri_intersection(const BVHTreeRay *ray,
216                                          float radius,
217                                          const float m_dist,
218                                          const float v0[3],
219                                          const float v1[3],
220                                          const float v2[3]);
221
222 /**
223  * BVHCache
224  */
225
226 /* Using local coordinates */
227 enum {
228   BVHTREE_FROM_VERTS,
229   BVHTREE_FROM_EDGES,
230   BVHTREE_FROM_FACES,
231   BVHTREE_FROM_LOOPTRI,
232   BVHTREE_FROM_LOOPTRI_NO_HIDDEN,
233
234   BVHTREE_FROM_LOOSEVERTS,
235   BVHTREE_FROM_LOOSEEDGES,
236
237   BVHTREE_FROM_EM_VERTS,
238   BVHTREE_FROM_EM_EDGES,
239   BVHTREE_FROM_EM_LOOPTRI,
240 };
241
242 bool bvhcache_find(const BVHCache *cache, int type, BVHTree **r_tree);
243 bool bvhcache_has_tree(const BVHCache *cache, const BVHTree *tree);
244 void bvhcache_insert(BVHCache **cache_p, BVHTree *tree, int type);
245 void bvhcache_free(BVHCache **cache_p);
246
247 #endif