Visualization Library 2.1.0

A lightweight C++ OpenGL middleware for 2D/3D graphics

VL     Star     Watch     Fork     Issue

[Download] [Tutorials] [All Classes] [Grouped Classes]
ActorKdTree.cpp
Go to the documentation of this file.
1 /**************************************************************************************/
2 /* */
3 /* Visualization Library */
4 /* http://visualizationlibrary.org */
5 /* */
6 /* Copyright (c) 2005-2020, Michele Bosi */
7 /* All rights reserved. */
8 /* */
9 /* Redistribution and use in source and binary forms, with or without modification, */
10 /* are permitted provided that the following conditions are met: */
11 /* */
12 /* - Redistributions of source code must retain the above copyright notice, this */
13 /* list of conditions and the following disclaimer. */
14 /* */
15 /* - Redistributions in binary form must reproduce the above copyright notice, this */
16 /* list of conditions and the following disclaimer in the documentation and/or */
17 /* other materials provided with the distribution. */
18 /* */
19 /* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND */
20 /* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED */
21 /* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE */
22 /* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR */
23 /* ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES */
24 /* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; */
25 /* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON */
26 /* ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT */
27 /* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS */
28 /* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */
29 /* */
30 /**************************************************************************************/
31 
33 #include <vlCore/Log.hpp>
34 #include <algorithm>
35 
36 using namespace vl;
37 
38 namespace
39 {
40  //-----------------------------------------------------------------------------
41  // sortX
42  //-----------------------------------------------------------------------------
43  bool sortX(const ref<Actor>& a1, const ref<Actor>& a2) /*const*/
44  {
45  VL_CHECK(a1->lod(0))
46  VL_CHECK(a2->lod(0))
47  return a1->boundingBox().minCorner().x() < a2->boundingBox().minCorner().x();
48  }
49  //-----------------------------------------------------------------------------
50  // sortY
51  //-----------------------------------------------------------------------------
52  bool sortY(const ref<Actor>& a1, const ref<Actor>& a2) /*const*/
53  {
54  VL_CHECK(a1->lod(0))
55  VL_CHECK(a2->lod(0))
56  return a1->boundingBox().minCorner().y() < a2->boundingBox().minCorner().y();
57  }
58  //-----------------------------------------------------------------------------
59  // sortZ
60  //-----------------------------------------------------------------------------
61  bool sortZ(const ref<Actor>& a1, const ref<Actor>& a2) /*const*/
62  {
63  VL_CHECK(a1->lod(0))
64  VL_CHECK(a2->lod(0))
65  return a1->boundingBox().minCorner().z() < a2->boundingBox().minCorner().z();
66  }
67 }
68 
69 //-----------------------------------------------------------------------------
70 ref<ActorKdTree> ActorKdTree::kdtreeFromNonLeafyActors(int max_depth, float minimum_volume)
71 {
72  ActorCollection acts;
74  ref<ActorKdTree> newtree = new ActorKdTree;
75  newtree->buildKdTree(acts, max_depth, minimum_volume);
76  return newtree;
77 }
78 //-----------------------------------------------------------------------------
80 {
81  VL_CHECK( (actors()->size() && (mChildN == 0 && mChildP == 0)) || !(mChildN == 0 && mChildP == 0) );
82 
83  if ( mChildN || mChildP )
84  {
85  for(int i=0; i<(int)actors()->size(); ++i)
86  acts.push_back(actors()->at(i));
87  actors()->clear();
88  }
89 
90  if(mChildN) childN()->harvestNonLeafActors( acts );
91  if(mChildP) childP()->harvestNonLeafActors( acts );
92 }
93 //-----------------------------------------------------------------------------
94 void ActorKdTree::computeLocalAABB(const ActorCollection& acts)
95 {
96  mAABB.setNull();
97  for(int i=0; i<(int)acts.size(); ++i)
98  {
99  VL_CHECK( acts[i]->lod(0) )
100  mAABB += acts[i]->boundingBox();
101  }
102 }
103 //-----------------------------------------------------------------------------
104 void ActorKdTree::buildKdTree(ActorCollection& acts, int max_depth, float minimum_volume)
105 {
106  int counter = 0;
107  prepareActors(acts);
108  compileTree_internal(acts, counter, max_depth, minimum_volume);
109 }
110 //-----------------------------------------------------------------------------
111 void ActorKdTree::rebuildKdTree(int max_depth, float minimum_volume)
112 {
113  ActorCollection acts;
114  extractActors(acts);
115  buildKdTree(acts, max_depth, minimum_volume);
116 }
117 //-----------------------------------------------------------------------------
118 void ActorKdTree::compileTree_internal(ActorCollection& acts, int& counter, int max_depth, float minimum_volume)
119 {
120  mChildN = NULL;
121  mChildP = NULL;
122  actors()->clear();
123  mAABB.setNull();
124  mPlane = Plane();
125 
126  if (acts.size() == 0)
127  return;
128 
129  computeLocalAABB(acts);
130 
131  if (acts.size() == 1 || max_depth == 0 || mAABB.volume() < minimum_volume)
132  {
133  mActors = acts;
134  return;
135  }
136 
137  if ( !findBestPlane(mPlane, counter, acts) )
138  {
139  mActors = acts;
140  return;
141  }
142 
143  ActorCollection actorsN;
144  ActorCollection actorsP;
145  actorsN.reserve(acts.size());
146  actorsP.reserve(acts.size());
147 
148  for(int i=0; i<(int)acts.size(); ++i)
149  {
150  VL_CHECK(acts[i]->lod(0))
151  switch( mPlane.classify(acts[i]->boundingBox()) )
152  {
153  case 0: actors()->push_back(acts[i].get()); break;
154  case -1: actorsN. push_back(acts[i].get()); break;
155  case +1: actorsP. push_back(acts[i].get()); break;
156  }
157  }
158 
159  int counter1 = counter;
160  int counter2 = counter;
161  if (actorsN.size())
162  {
163  setChildN(new ActorKdTree);
164  childN()->compileTree_internal(actorsN, counter1, max_depth-1, minimum_volume);
165  }
166 
167  if (actorsP.size())
168  {
169  setChildP(new ActorKdTree);
170  childP()->compileTree_internal(actorsP, counter2, max_depth-1, minimum_volume);
171  }
172 
173 }
174 //-----------------------------------------------------------------------------
175 int ActorKdTree::scorePlane(const Plane& plane, const ActorCollection& acts)
176 {
177  int cN=0, cC=0, cP=0;
178  for(int i=0; i<(int)acts.size(); ++i)
179  {
180  VL_CHECK(acts[i]->lod(0))
181  switch( plane.classify(acts[i]->boundingBox()) )
182  {
183  case -1: cN++; break;
184  case 0: cC++; break;
185  case +1: cP++; break;
186  }
187  }
188  return cC + ::abs(cN-cP);
189 }
190 //-----------------------------------------------------------------------------
192 bool ActorKdTree::findBestPlane(Plane& plane, int& counter, ActorCollection& acts)
193 {
194  int median = (int)acts.size() / 2;
195  if (counter%3 == 0)
196  {
197  std::sort(acts.vector().begin(), acts.vector().end(), sortX);
198  VL_CHECK(acts[median]->lod(0))
199  plane = Plane(acts[median]->boundingBox().minCorner().x(), vec3(1,0,0));
200  counter++;
201  if (scorePlane(plane, acts) == (int)acts.size())
202  {
203  std::sort(acts.vector().begin(), acts.vector().end(), sortY);
204  VL_CHECK(acts[median]->lod(0))
205  plane = Plane(acts[median]->boundingBox().minCorner().y(), vec3(0,1,0));
206  counter++;
207  if (scorePlane(plane, acts) == (int)acts.size())
208  {
209  std::sort(acts.vector().begin(), acts.vector().end(), sortZ);
210  VL_CHECK(acts[median]->lod(0))
211  plane = Plane(acts[median]->boundingBox().minCorner().z(), vec3(0,0,1));
212  counter++;
213  if (scorePlane(plane, acts) == (int)acts.size())
214  return false;
215  }
216  }
217  }
218  else
219  if (counter%3 == 1)
220  {
221  std::sort(acts.vector().begin(), acts.vector().end(), sortY);
222  VL_CHECK(acts[median]->lod(0))
223  plane = Plane(acts[median]->boundingBox().minCorner().y(), vec3(0,1,0));
224  counter++;
225  if (scorePlane(plane, acts) == (int)acts.size())
226  {
227  std::sort(acts.vector().begin(), acts.vector().end(), sortZ);
228  VL_CHECK(acts[median]->lod(0))
229  plane = Plane(acts[median]->boundingBox().minCorner().z(), vec3(0,0,1));
230  counter++;
231  if (scorePlane(plane, acts) == (int)acts.size())
232  {
233  std::sort(acts.vector().begin(), acts.vector().end(), sortX);
234  VL_CHECK(acts[median]->lod(0))
235  plane = Plane(acts[median]->boundingBox().minCorner().x(), vec3(1,0,0));
236  counter++;
237  if (scorePlane(plane, acts) == (int)acts.size())
238  return false;
239  }
240  }
241  }
242  else
243  if (counter%3 == 2)
244  {
245  std::sort(acts.vector().begin(), acts.vector().end(), sortZ);
246  VL_CHECK(acts[median]->lod(0))
247  plane = Plane(acts[median]->boundingBox().minCorner().z(), vec3(0,0,1));
248  counter++;
249  if (scorePlane(plane, acts) == (int)acts.size())
250  {
251  std::sort(acts.vector().begin(), acts.vector().end(), sortX);
252  VL_CHECK(acts[median]->lod(0))
253  plane = Plane(acts[median]->boundingBox().minCorner().x(), vec3(1,0,0));
254  counter++;
255  if (scorePlane(plane, acts) == (int)acts.size())
256  {
257  std::sort(acts.vector().begin(), acts.vector().end(), sortY);
258  VL_CHECK(acts[median]->lod(0))
259  plane = Plane(acts[median]->boundingBox().minCorner().y(), vec3(0,1,0));
260  counter++;
261  if (scorePlane(plane, acts) == (int)acts.size())
262  return false;
263  }
264  }
265  }
266  return true;
267 }
268 //-----------------------------------------------------------------------------
270 {
271  VL_CHECK(actor->lod(0))
272  if (childN() == 0 && childP() == 0)
273  actors()->push_back(actor);
274  else
275  {
276  switch( mPlane.classify(actor->boundingBox()) )
277  {
278  case -1: if (!childN()) setChildN(new ActorKdTree); return childN()->insertActor(actor);
279  case 0: actors()->push_back(actor); break;
280  case +1: if (!childP()) setChildP(new ActorKdTree); return childP()->insertActor(actor);
281  }
282  }
283  return this;
284 }
285 //-----------------------------------------------------------------------------
287 {
288  if (mChildN && mChildP)
289  return 2;
290  else
291  if (mChildN || mChildP)
292  return 1;
293  else
294  return 0;
295 }
296 //-----------------------------------------------------------------------------
298 {
299  if (i == 0)
300  return mChildN ? mChildN.get() : mChildP.get();
301  else
302  if (i == 1)
303  return mChildP.get();
304  else
305  {
306  vl::Log::error( "ActorKdTree::child(int): bad child node requested, a ActorKdTree can have only 2 child nodes.\n" );
307  return NULL;
308  }
309 }
310 //-----------------------------------------------------------------------------
312 {
313  if (i == 0)
314  return mChildN ? mChildN.get() : mChildP.get();
315  else
316  if (i == 1)
317  return mChildP.get();
318  else
319  {
320  vl::Log::error( "ActorKdTree::child(int): bad child node requested, a ActorKdTree can have only 2 child nodes.\n" );
321  return NULL;
322  }
323 }
324 //-----------------------------------------------------------------------------
Associates a Renderable object to an Effect and Transform.
Definition: Actor.hpp:130
const Renderable * lod(int lod_index) const
Returns the Renderable object representing the LOD level specifed by lod_index.
Definition: Actor.hpp:173
ref< ActorKdTree > mChildP
void rebuildKdTree(int max_depth=100, float minimum_volume=0)
Builds a ActorKdTree with the Actors contained in the tree.
ActorKdTree * childP()
Returns the child node that lies in the positive space defined by the splitting plane.
Definition: ActorKdTree.hpp:92
const T * get() const
Definition: Object.hpp:128
const Plane & plane() const
Returns the splitting plane used to divide its two child nodes.
Definition: ActorKdTree.hpp:84
void reserve(size_t capacity)
Definition: Collection.hpp:95
The Plane class defines a plane using a normal and an origin.
Definition: Plane.hpp:49
virtual int childrenCount() const
Returns the number of child nodes of an ActorTreeAbstract node.
const T_Scalar & z() const
Definition: Vector3.hpp:92
ActorKdTree * insertActor(Actor *actor)
Inserts an Actor in the ActorKdTree node hierarchy.
static void error(const String &message)
Use this function to provide information about run-time errors: file not found, out of memory...
Definition: Log.cpp:165
void setNull()
Sets ths AABB as null, that is, empty.
Definition: AABB.hpp:57
static void prepareActors(ActorCollection &actors)
Updates the Transform and the bounds of the given Actors.
Visualization Library main namespace.
int classify(const AABB &) const
returns 0 if the AABB intersects the plane, 1 if it&#39;s in the positive side, -1 if it&#39;s in the negativ...
Definition: Plane.cpp:54
virtual ActorTreeAbstract * child(int i)
Returns the i-th child node of an ActorTreeAbstract node.
const ActorCollection * actors() const
Returns the actors contained in a ActorTree node.
const std::vector< ref< T > > & vector() const
Definition: Collection.hpp:164
ActorKdTree * childN()
Returns the child node that lies in the negative space defined by the splitting plane.
Definition: ActorKdTree.hpp:87
void harvestNonLeafActors(ActorCollection &actors)
Removes the Actors in the internal nodes of the ActorKdTree and appends them in the given ActorCollec...
Definition: ActorKdTree.cpp:79
void push_back(T *data)
Definition: Collection.hpp:79
The ActorTreeAbstract class implements the interface of a generic tree containing Actors in its nodes...
void buildKdTree(ActorCollection &actors, int max_depth=100, float minimum_volume=0)
Builds a ActorKdTree with the given list of Actors.
const T_Scalar & y() const
Definition: Vector3.hpp:91
T abs(T a)
Definition: glsl_math.hpp:646
const AABB & boundingBox() const
Returns the bounding box (not guaranteed to be up to date) that contains this Actor.
Definition: Actor.hpp:205
#define NULL
Definition: OpenGLDefs.hpp:81
const vec3 & minCorner() const
Returns the corner of the AABB with the minimum x y z coordinates.
Definition: AABB.hpp:190
ActorKdTree class extends the ActorTreeAbstract class implementing a space partitioning scheme based ...
Definition: ActorKdTree.hpp:57
Defined as a simple subclass of Collection<Actor>, see Collection for more information.
Definition: Actor.hpp:479
fvec3 vec3
Defined as: &#39;typedef fvec3 vec3&#39;. See also VL_PIPELINE_PRECISION.
Definition: Vector3.hpp:270
const T_Scalar & x() const
Definition: Vector3.hpp:90
real volume() const
Returns the volume of the AABB.
Definition: AABB.hpp:208
ref< ActorKdTree > kdtreeFromNonLeafyActors(int max_depth=100, float minimum_volume=0)
Removes the Actors in the internal nodes of the ActorKdTree and uses them to create a new ActorKdTree...
Definition: ActorKdTree.cpp:70
void extractActors(ActorCollection &list)
Extracts all the Actors contained in th ActorTree hierarchy and appends them to the given ActorCollec...
#define VL_CHECK(expr)
Definition: checks.hpp:73
size_t size() const
Definition: Collection.hpp:85
ref< ActorKdTree > mChildN