1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
/**
*
* $Id$
*
* ***** BEGIN GPL LICENSE BLOCK *****
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software Foundation,
* Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*
* The Original Code is Copyright (C) 2006 by NaN Holding BV.
* All rights reserved.
*
* The Original Code is: all of this file.
*
* Contributor(s): André Pinto
*
* ***** END GPL LICENSE BLOCK *****
*/
#ifndef BKE_BVHUTILS_H
#define BKE_BVHUTILS_H
#include "BLI_kdopbvh.h"
#include "BLI_linklist.h"
/*
* This header encapsulates necessary code to buld a BVH
*/
struct DerivedMesh;
struct MVert;
struct MFace;
/*
* struct that kepts basic information about a BVHTree build from a mesh
*/
typedef struct BVHTreeFromMesh
{
struct BVHTree *tree;
/* default callbacks to bvh nearest and raycast */
BVHTree_NearestPointCallback nearest_callback;
BVHTree_RayCastCallback raycast_callback;
/* Mesh represented on this BVHTree */
struct DerivedMesh *mesh;
/* Vertex array, so that callbacks have instante access to data */
struct MVert *vert;
struct MEdge *edge; /* only used for BVHTreeFromMeshEdges */
struct MFace *face;
/* radius for raycast */
float sphere_radius;
/* Private data */
int cached;
} BVHTreeFromMesh;
/*
* Builds a bvh tree where nodes are the vertexs of the given mesh.
* Configures BVHTreeFromMesh.
*
* The tree is build in mesh space coordinates, this means special care must be made on queries
* so that the coordinates and rays are first translated on the mesh local coordinates.
* Reason for this is that later bvh_from_mesh_* might use a cache system and so it becames possible to reuse
* a BVHTree.
*
* free_bvhtree_from_mesh should be called when the tree is no longer needed.
*/
BVHTree* bvhtree_from_mesh_verts(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
/*
* Builds a bvh tree where nodes are the faces of the given mesh.
* Configures BVHTreeFromMesh.
*
* The tree is build in mesh space coordinates, this means special care must be made on queries
* so that the coordinates and rays are first translated on the mesh local coordinates.
* Reason for this is that later bvh_from_mesh_* might use a cache system and so it becames possible to reuse
* a BVHTree.
*
* The returned value is the same as in data->tree, its only returned to make it easier to test
* the success
*
* free_bvhtree_from_mesh should be called when the tree is no longer needed.
*/
BVHTree* bvhtree_from_mesh_faces(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
BVHTree* bvhtree_from_mesh_edges(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
/*
* Frees data allocated by a call to bvhtree_from_mesh_*.
*/
void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data);
/*
* BVHCache
*/
//Using local coordinates
#define BVHTREE_FROM_FACES 0
#define BVHTREE_FROM_VERTICES 1
#define BVHTREE_FROM_EDGES 2
typedef LinkNode* BVHCache;
/*
* Queries a bvhcache for the chache bvhtree of the request type
*/
BVHTree *bvhcache_find(BVHCache *cache, int type);
/*
* Inserts a BVHTree of the given type under the cache
* After that the caller no longer needs to worry when to free the BVHTree
* as that will be done when the cache is freed.
*
* A call to this assumes that there was no previous cached tree of the given type
*/
void bvhcache_insert(BVHCache *cache, BVHTree *tree, int type);
/*
* inits and frees a bvhcache
*/
void bvhcache_init(BVHCache *cache);
void bvhcache_free(BVHCache *cache);
#endif
|
