GLC_lib  2.5.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
glc_octreenode.cpp
Go to the documentation of this file.
1 /****************************************************************************
2 
3  This file is part of the GLC-lib library.
4  Copyright (C) 2005-2008 Laurent Ribon (laumaya@users.sourceforge.net)
5  http://glc-lib.sourceforge.net
6 
7  GLC-lib is free software; you can redistribute it and/or modify
8  it under the terms of the GNU Lesser General Public License as published by
9  the Free Software Foundation; either version 3 of the License, or
10  (at your option) any later version.
11 
12  GLC-lib is distributed in the hope that it will be useful,
13  but WITHOUT ANY WARRANTY; without even the implied warranty of
14  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  GNU Lesser General Public License for more details.
16 
17  You should have received a copy of the GNU Lesser General Public License
18  along with GLC-lib; if not, write to the Free Software
19  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20 
21  *****************************************************************************/
23 
24 #include "glc_octreenode.h"
25 
27 
29 : m_BoundingBox(boundingBox)
30 , m_pParent(pParent)
31 , m_Children()
32 , m_3DViewInstanceSet()
33 , m_Empty(true)
34 {
35 
36 
37 }
38 
40 : m_BoundingBox(octreeNode.m_BoundingBox)
41 , m_pParent(pParent)
42 , m_Children()
43 , m_3DViewInstanceSet(octreeNode.m_3DViewInstanceSet)
44 , m_Empty(octreeNode.m_Empty)
45 {
46  if (!octreeNode.m_Children.isEmpty())
47  {
48  const int size= octreeNode.m_Children.size();
49  for (int i= 0; i < size; ++i)
50  {
51  m_Children.append(new GLC_OctreeNode(*(octreeNode.m_Children.at(i)), this));
52  }
53  }
54 }
55 
57 {
58  const int size= m_Children.size();
59  for (int i= 0; i < size; ++i)
60  {
61  delete m_Children.at(i);
62  }
63 }
64 
66 {
67  return m_useBoundingSphere;
68 }
69 
70 QSet<GLC_3DViewInstance*> GLC_OctreeNode::setOfIntersectedInstances(const GLC_BoundingBox& bBox)
71 {
72  QSet<GLC_3DViewInstance*> instanceSet;
73  if (intersect(bBox))
74  {
75  QSet<GLC_3DViewInstance*>::iterator iInstance= m_3DViewInstanceSet.begin();
76  while (m_3DViewInstanceSet.constEnd() != iInstance)
77  {
78  if ((*iInstance)->boundingBox().intersect(bBox))
79  {
80  instanceSet << *(iInstance);
81  }
82  ++iInstance;
83  }
84  const int childCount= m_Children.size();
85  for (int i= 0; i < childCount; ++i)
86  {
87  instanceSet.unite(m_Children[i]->setOfIntersectedInstances(bBox));
88  }
89  }
90 
91  return instanceSet;
92 }
94 // Set Functions
96 
98 {
99  Q_ASSERT(m_Children.isEmpty());
100  Q_ASSERT(!m_BoundingBox.isEmpty());
101 
102  const double xLower= m_BoundingBox.lowerCorner().x();
103  const double yLower= m_BoundingBox.lowerCorner().y();
104  const double zLower= m_BoundingBox.lowerCorner().z();
105 
106  const double xUpper= m_BoundingBox.upperCorner().x();
107  const double dX= (xUpper - xLower) / 2.0;
108  const double yUpper= m_BoundingBox.upperCorner().y();
109  const double dY= (yUpper - yLower) / 2.0;
110  const double zUpper= m_BoundingBox.upperCorner().z();
111  const double dZ= (zUpper - zLower) / 2.0;
112 
113 
114  // Add 8 Children
115  GLC_Point3d lower;
116  GLC_Point3d upper;
117  GLC_OctreeNode* pOctreeNode= NULL;
118 
119  { // Child 1
120  lower.setVect(xLower, yLower, zLower);
121  upper.setVect(xLower + dX, yLower + dY, zLower + dZ);
122  GLC_BoundingBox box(lower, upper);
123  pOctreeNode= new GLC_OctreeNode(box, this);
124  m_Children.append(pOctreeNode);
125  }
126  { // Child 2
127  lower.setVect(xLower + dX, yLower, zLower);
128  upper.setVect(xUpper, yLower + dY, zLower + dZ);
129  GLC_BoundingBox box(lower, upper);
130  pOctreeNode= new GLC_OctreeNode(box, this);
131  m_Children.append(pOctreeNode);
132  }
133  { // Child 3
134  lower.setVect(xLower + dX, yLower + dY, zLower);
135  upper.setVect(xUpper, yUpper, zLower + dZ);
136  GLC_BoundingBox box(lower, upper);
137  pOctreeNode= new GLC_OctreeNode(box, this);
138  m_Children.append(pOctreeNode);
139  }
140  { // Child 4
141  lower.setVect(xLower, yLower + dY, zLower);
142  upper.setVect(xLower + dX, yUpper, zLower + dZ);
143  GLC_BoundingBox box(lower, upper);
144  pOctreeNode= new GLC_OctreeNode(box, this);
145  m_Children.append(pOctreeNode);
146  }
147  { // Child 5
148  lower.setVect(xLower, yLower, zLower + dZ);
149  upper.setVect(xLower + dX, yLower + dY, zUpper);
150  GLC_BoundingBox box(lower, upper);
151  pOctreeNode= new GLC_OctreeNode(box, this);
152  m_Children.append(pOctreeNode);
153  }
154  { // Child 6
155  lower.setVect(xLower + dX, yLower, zLower + dZ);
156  upper.setVect(xUpper, yLower + dY, zUpper);
157  GLC_BoundingBox box(lower, upper);
158  pOctreeNode= new GLC_OctreeNode(box, this);
159  m_Children.append(pOctreeNode);
160  }
161  { // Child 7
162  lower.setVect(xLower + dX, yLower + dY, zLower + dZ);
163  upper.setVect(xUpper, yUpper, zUpper);
164  GLC_BoundingBox box(lower, upper);
165  pOctreeNode= new GLC_OctreeNode(box, this);
166  m_Children.append(pOctreeNode);
167  }
168  { // Child 8
169  lower.setVect(xLower, yLower + dY, zLower + dZ);
170  upper.setVect(xLower + dX, yUpper, zUpper);
171  GLC_BoundingBox box(lower, upper);
172  pOctreeNode= new GLC_OctreeNode(box, this);
173  m_Children.append(pOctreeNode);
174  }
175 }
176 
177 
179 {
180  m_Empty= false;
181  const GLC_BoundingBox instanceBox= pInstance->boundingBox();
182  // Check if the instance's bounding box intersect this node bounding box
183  if (!instanceBox.isEmpty() && intersect(instanceBox))
184  {
185  if (0 == depth)
186  {
187  m_3DViewInstanceSet.insert(pInstance);
188  }
189  else
190  {
191  if (m_Children.isEmpty())
192  {
193  // Create children
194  addChildren();
195  }
196  QVector<bool> childIntersect(8);
197  bool allIntersect= true;
198  bool currentIntersect= false;
199  for (int i= 0; i < 8; ++i)
200  {
201  currentIntersect= m_Children.at(i)->intersect(instanceBox);
202  allIntersect= allIntersect && currentIntersect;
203  childIntersect[i]= currentIntersect;
204  }
205  if (allIntersect)
206  {
207  m_3DViewInstanceSet.insert(pInstance);
208  }
209  else
210  {
211  for (int i= 0; i < 8; ++i)
212  {
213  if (childIntersect[i])
214  {
215  m_Children[i]->addInstance(pInstance, depth - 1);
216  }
217  }
218  }
219  }
220 
221  }
222 }
223 
224 
225 void GLC_OctreeNode::updateViewableInstances(const GLC_Frustum& frustum, QSet<GLC_3DViewInstance*>* pInstanceSet)
226 {
227 
228  bool firstCall= false;
229  // Create the set of viewable instance if necessary
230  if (NULL == pInstanceSet)
231  {
232  pInstanceSet= new QSet<GLC_3DViewInstance*>();
233  firstCall= true;
234  }
235 
236  // Test the localisation of current octree node
238  if (nodeLocalisation == GLC_Frustum::OutFrustum)
239  {
240  disableViewFlag(pInstanceSet);
241  }
242  else if (nodeLocalisation == GLC_Frustum::InFrustum)
243  {
244  unableViewFlag(pInstanceSet);
245  }
246  else // The current node intersect the frustum
247  {
248  QSet<GLC_3DViewInstance*>::iterator iInstance= m_3DViewInstanceSet.begin();
249  while (m_3DViewInstanceSet.constEnd() != iInstance)
250  {
251  // Test if the instances is in the viewable set
252  if (!pInstanceSet->contains(*iInstance))
253  {
254  GLC_3DViewInstance* pCurrentInstance= (*iInstance);
255  // Test the localisation of the current instance
256  GLC_Frustum::Localisation instanceLocalisation= frustum.localizeBoundingBox(pCurrentInstance->boundingBox());
257 
258  if (instanceLocalisation == GLC_Frustum::OutFrustum)
259  {
260  pCurrentInstance->setViewable(GLC_3DViewInstance::NoViewable);
261  }
262  else if (instanceLocalisation == GLC_Frustum::InFrustum)
263  {
264  pInstanceSet->insert(pCurrentInstance);
266  }
267  else
268  {
269  pInstanceSet->insert(pCurrentInstance);
271  //Update the geometries viewable property of the instance
272  GLC_Matrix4x4 instanceMat= pCurrentInstance->matrix();
273  const int size= pCurrentInstance->numberOfBody();
274  for (int i= 0; i < size; ++i)
275  {
276  // Get the geometry bounding box
277  GLC_BoundingBox geomBox= pCurrentInstance->geomAt(i)->boundingBox();
278  GLC_Point3d center(instanceMat * geomBox.center());
279  double radius= geomBox.boundingSphereRadius() * instanceMat.scalingX();
280  GLC_Frustum::Localisation geomLocalisation= frustum.localizeSphere(center, radius);
281 
282  pCurrentInstance->setGeomViewable(i, geomLocalisation != GLC_Frustum::OutFrustum);
283  }
284  }
285  }
286 
287  ++iInstance;
288  }
289  const int size= m_Children.size();
290  for (int i= 0; i < size; ++i)
291  {
292  m_Children.at(i)->updateViewableInstances(frustum, pInstanceSet);
293  }
294  }
295  if (firstCall) delete pInstanceSet;
296 }
297 
298 
300 {
301  NodeList::iterator iList= m_Children.begin();
302  while(m_Children.constEnd() != iList)
303  {
304  GLC_OctreeNode* pCurrentChild= *iList;
305  if (pCurrentChild->isEmpty())
306  {
307  delete pCurrentChild;
308  iList= m_Children.erase(iList);
309  }
310  else
311  {
312  pCurrentChild->removeEmptyChildren();
313  if (pCurrentChild->isEmpty())
314  {
315  delete pCurrentChild;
316  iList= m_Children.erase(iList);
317  }
318  else ++iList;
319  }
320  }
321  // Update empty flag
322  if (m_Children.isEmpty() && (NULL != m_pParent))
323  {
324  if (1 == m_3DViewInstanceSet.size())
325  {
327  m_3DViewInstanceSet.clear();
328  }
329  m_Empty= m_3DViewInstanceSet.isEmpty();
330  }
331 }
332 
334 {
335  m_useBoundingSphere= use;
336 }
337 
338 void GLC_OctreeNode::unableViewFlag(QSet<GLC_3DViewInstance*>* pInstanceSet)
339 {
340  QSet<GLC_3DViewInstance*>::iterator iInstance= m_3DViewInstanceSet.begin();
341  while (m_3DViewInstanceSet.constEnd() != iInstance)
342  {
343  if (!pInstanceSet->contains(*iInstance))
344  {
345  (*iInstance)->setViewable(GLC_3DViewInstance::FullViewable);
346  pInstanceSet->insert(*iInstance);
347  }
348 
349  ++iInstance;
350  }
351  const int size= m_Children.size();
352  for (int i= 0; i < size; ++i)
353  {
354  m_Children.at(i)->unableViewFlag(pInstanceSet);
355  }
356 }
357 
358 
359 void GLC_OctreeNode::disableViewFlag(QSet<GLC_3DViewInstance*>* pInstanceSet)
360 {
361  QSet<GLC_3DViewInstance*>::iterator iInstance= m_3DViewInstanceSet.begin();
362  while (m_3DViewInstanceSet.constEnd() != iInstance)
363  {
364  if (!pInstanceSet->contains(*iInstance))
365  (*iInstance)->setViewable(GLC_3DViewInstance::NoViewable);
366 
367  ++iInstance;
368  }
369  const int size= m_Children.size();
370  for (int i= 0; i < size; ++i)
371  {
372  m_Children.at(i)->disableViewFlag(pInstanceSet);
373  }
374 }
375 

©2005-2013 Laurent Ribon