bsp_tree.h
1 /*************************************************************************/
2 /* bsp_tree.h */
3 /*************************************************************************/
4 /* This file is part of: */
5 /* GODOT ENGINE */
6 /* http://www.godotengine.org */
7 /*************************************************************************/
8 /* Copyright (c) 2007-2016 Juan Linietsky, Ariel Manzur. */
9 /* */
10 /* Permission is hereby granted, free of charge, to any person obtaining */
11 /* a copy of this software and associated documentation files (the */
12 /* "Software"), to deal in the Software without restriction, including */
13 /* without limitation the rights to use, copy, modify, merge, publish, */
14 /* distribute, sublicense, and/or sell copies of the Software, and to */
15 /* permit persons to whom the Software is furnished to do so, subject to */
16 /* the following conditions: */
17 /* */
18 /* The above copyright notice and this permission notice shall be */
19 /* included in all copies or substantial portions of the Software. */
20 /* */
21 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
22 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
23 /* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/
24 /* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
25 /* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
26 /* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
27 /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
28 /*************************************************************************/
29 #ifndef BSP_TREE_H
30 #define BSP_TREE_H
31 
32 #include "plane.h"
33 #include "aabb.h"
34 #include "face3.h"
35 #include "vector.h"
36 #include "dvector.h"
37 
38 #include "variant.h"
42 class BSP_Tree {
43 public:
44 
45  enum {
46 
47  UNDER_LEAF=0xFFFF,
48  OVER_LEAF=0xFFFE,
49  MAX_NODES=0xFFFE,
50  MAX_PLANES=(1<<16)
51  };
52 
53  struct Node {
54 
55  uint16_t plane;
56  uint16_t under;
57  uint16_t over;
58  };
59 
60 
61 private:
62  // thanks to the properties of Vector,
63  // this class can be assigned and passed around between threads
64  // with no cost.
65 
66  Vector<Node> nodes;
67  Vector<Plane> planes;
68  AABB aabb;
69  float error_radius;
70 
71  int _get_points_inside(int p_node,const Vector3* p_points,int *p_indices, const Vector3& p_center,const Vector3& p_half_extents,int p_indices_count) const;
72 
73  template<class T>
74  bool _test_convex(const Node* p_nodes, const Plane* p_planes,int p_current, const T& p_convex) const;
75 
76 public:
77 
78  bool is_empty() const { return nodes.size()==0; }
79  Vector<Node> get_nodes() const;
80  Vector<Plane> get_planes() const;
81  AABB get_aabb() const;
82 
83  bool point_is_inside(const Vector3& p_point) const;
84  int get_points_inside(const Vector3* p_points, int p_point_count) const;
85  template<class T>
86  bool convex_is_inside(const T& p_convex) const;
87 
88  operator Variant() const;
89 
90  void from_aabb(const AABB& p_aabb);
91 
92  BSP_Tree();
93  BSP_Tree(const Variant& p_variant);
94  BSP_Tree(const DVector<Face3>& p_faces,float p_error_radius=0);
95  BSP_Tree(const Vector<Node> &p_nodes, const Vector<Plane> &p_planes, const AABB& p_aabb,float p_error_radius=0);
96  ~BSP_Tree();
97 
98 };
99 
100 template<class T>
101 bool BSP_Tree::_test_convex(const Node* p_nodes, const Plane* p_planes,int p_current, const T& p_convex) const {
102 
103  if (p_current==UNDER_LEAF)
104  return true;
105  else if (p_current==OVER_LEAF)
106  return false;
107 
108  bool collided=false;
109  const Node&n=p_nodes[p_current];
110 
111  const Plane& p=p_planes[n.plane];
112 
113  float min,max;
114  p_convex.project_range(p.normal,min,max);
115 
116  bool go_under = min < p.d;
117  bool go_over = max >= p.d;
118 
119  if (go_under && _test_convex(p_nodes,p_planes,n.under,p_convex))
120  collided=true;
121  if (go_over && _test_convex(p_nodes,p_planes,n.over,p_convex))
122  collided=true;
123 
124  return collided;
125 
126 }
127 
128 template<class T>
129 bool BSP_Tree::convex_is_inside(const T& p_convex) const {
130 
131  int node_count = nodes.size();
132  if (node_count==0)
133  return false;
134  const Node* nodes=&this->nodes[0];
135  const Plane* planes = &this->planes[0];
136 
137  return _test_convex(nodes,planes,node_count-1,p_convex);
138 }
139 
140 
141 #endif
Definition: variant.h:74
Definition: bsp_tree.h:53
Definition: aabb.h:43
Definition: vector3.h:38
Definition: plane.h:35
Definition: bsp_tree.h:42
Definition: vector.h:43