Developer Documentation
BSPTreeNode.hh
1 /*===========================================================================*\
2 * *
3 * OpenFlipper *
4  * Copyright (c) 2001-2015, RWTH-Aachen University *
5  * Department of Computer Graphics and Multimedia *
6  * All rights reserved. *
7  * www.openflipper.org *
8  * *
9  *---------------------------------------------------------------------------*
10  * This file is part of OpenFlipper. *
11  *---------------------------------------------------------------------------*
12  * *
13  * Redistribution and use in source and binary forms, with or without *
14  * modification, are permitted provided that the following conditions *
15  * are met: *
16  * *
17  * 1. Redistributions of source code must retain the above copyright notice, *
18  * this list of conditions and the following disclaimer. *
19  * *
20  * 2. Redistributions in binary form must reproduce the above copyright *
21  * notice, this list of conditions and the following disclaimer in the *
22  * documentation and/or other materials provided with the distribution. *
23  * *
24  * 3. Neither the name of the copyright holder nor the names of its *
25  * contributors may be used to endorse or promote products derived from *
26  * this software without specific prior written permission. *
27  * *
28  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS *
29  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
30  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
31  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER *
32  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, *
33  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, *
34  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR *
35  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF *
36  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING *
37  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS *
38  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
39 * *
40 \*===========================================================================*/
41 
42 /*===========================================================================*\
43 * *
44 * $Revision: 10745 $ *
45 * $LastChangedBy: moebius $ *
46 * $Date: 2011-01-26 10:23:50 +0100 (Wed, 26 Jan 2011) $ *
47 * *
48 \*===========================================================================*/
49 
50 
51 
52 
53 //=============================================================================
54 //
55 // CLASS TreeNode
56 //
57 //=============================================================================
58 
59 #ifndef MB_BSPTREENODE_HH
60 #define MB_BSPTREENODE_HH
61 
62 //== INCLUDES =================================================================
63 
64 #include <ACG/Geometry/Types/PlaneT.hh>
65 #include <ACG/Geometry/Algorithms.hh>
66 #include <ostream>
67 
68 //== CLASS DEFINITION =========================================================
69 
70 // Node of the tree: contains parent, children and splitting plane
71 template <class Mesh>
72 struct TreeNode
73 {
74  typedef typename Mesh::FaceHandle Handle;
75  typedef typename Mesh::Point Point;
76  typedef typename Mesh::VertexHandle VertexHandle;
77  typedef std::vector<Handle> Handles;
78  typedef typename Handles::iterator HandleIter;
79  typedef typename Point::value_type Scalar;
80  typedef ACG::Geometry::PlaneT<Scalar> Plane;
81 
82  TreeNode(const Handles& _handles, TreeNode* _parent)
83  : handles_(_handles),
84  parent_(_parent), left_child_(0), right_child_(0) {}
85  ~TreeNode()
86  {
87  delete left_child_;
88  delete right_child_;
89 
90  if (parent_)
91  {
92  if (this == parent_->left_child_)
93  parent_->left_child_ = 0;
94  else
95  parent_->right_child_ = 0;
96  }
97  }
98 
99  HandleIter begin() {
100  return handles_.begin();
101  }
102  HandleIter end() {
103  return handles_.end();
104  }
105 
106  size_t size() const {
107  return handles_.size();
108  }
109 
110  Handles handles_;
111  TreeNode *parent_, *left_child_, *right_child_;
112  Plane plane_;
113  Point bb_min, bb_max;
114 
116  template< typename MeshT >
117  void visualizeTree(MeshT *_object, int _max_depth)
118  {
119  if (_max_depth > 0 && (left_child_ || right_child_) )
120  {
121  if (left_child_)
122  left_child_->visualizeTree(_object, _max_depth-1);
123  if (right_child_)
124  right_child_->visualizeTree(_object, _max_depth-1);
125  }
126  else
127  {
128  Point size_ = bb_max - bb_min;
129 
130  std::vector<VertexHandle> vhandle(8);
131  vhandle[0] = _object->add_vertex(bb_min+Point(0.0,0.0,size_[2]));
132  vhandle[1] = _object->add_vertex(bb_min+Point(size_[0],0.0,size_[2]));
133  vhandle[2] = _object->add_vertex(bb_min+Point(size_[0],size_[1],size_[2]));
134  vhandle[3] = _object->add_vertex(bb_min+Point(0.0,size_[1],size_[2]));
135  vhandle[4] = _object->add_vertex(bb_min+Point(0.0,0.0,0.0));
136  vhandle[5] = _object->add_vertex(bb_min+Point(size_[0],0.0,0.0));
137  vhandle[6] = _object->add_vertex(bb_min+Point(size_[0],size_[1],0.0));
138  vhandle[7] = _object->add_vertex(bb_min+Point(0.0,size_[1],0.0));
139 
140 
141  // generate (quadrilateral) faces
142  std::vector<VertexHandle> face_vhandles;
143 
144  face_vhandles.clear();
145  face_vhandles.push_back(vhandle[0]);
146  face_vhandles.push_back(vhandle[1]);
147  face_vhandles.push_back(vhandle[2]);
148  face_vhandles.push_back(vhandle[3]);
149  _object->add_face(face_vhandles);
150 
151  face_vhandles.clear();
152  face_vhandles.push_back(vhandle[7]);
153  face_vhandles.push_back(vhandle[6]);
154  face_vhandles.push_back(vhandle[5]);
155  face_vhandles.push_back(vhandle[4]);
156  _object->add_face(face_vhandles);
157 
158  face_vhandles.clear();
159  face_vhandles.push_back(vhandle[1]);
160  face_vhandles.push_back(vhandle[0]);
161  face_vhandles.push_back(vhandle[4]);
162  face_vhandles.push_back(vhandle[5]);
163  _object->add_face(face_vhandles);
164 
165  face_vhandles.clear();
166  face_vhandles.push_back(vhandle[2]);
167  face_vhandles.push_back(vhandle[1]);
168  face_vhandles.push_back(vhandle[5]);
169  face_vhandles.push_back(vhandle[6]);
170  _object->add_face(face_vhandles);
171 
172  face_vhandles.clear();
173  face_vhandles.push_back(vhandle[3]);
174  face_vhandles.push_back(vhandle[2]);
175  face_vhandles.push_back(vhandle[6]);
176  face_vhandles.push_back(vhandle[7]);
177  _object->add_face(face_vhandles);
178 
179  face_vhandles.clear();
180  face_vhandles.push_back(vhandle[0]);
181  face_vhandles.push_back(vhandle[3]);
182  face_vhandles.push_back(vhandle[7]);
183  face_vhandles.push_back(vhandle[4]);
184  _object->add_face(face_vhandles);
185  }
186  }
187 
188  private:
189  /*
190  * Noncopyable because of root_.
191  */
192  TreeNode(const TreeNode &rhs);
193  TreeNode &operator=(const TreeNode &rhs);
194 
195 };
196 
197 template<class Mesh>
198 std::ostream &operator<< (std::ostream &stream, const TreeNode<Mesh> &node) {
199  stream << "[TreeNode instance. Handles: ";
200  for (typename std::vector<typename TreeNode<Mesh>::Handle>::const_iterator it = node.handles_.begin(), it_end = node.handles_.end();
201  it != it_end; ++it) {
202  stream << it->idx();
203  if (it < it_end-1) stream << ", ";
204  }
205  stream << ", parent: " << node.parent_ << ", left_child_: " << node.left_child_
206  << ", right_child_: " << node.right_child_ << ", plane_: <not implemented>, bb_min: "
207  << node.bb_min << ", bb_max: " << node.bb_max << ", size(): " << node.size() << "]";
208  return stream;
209 }
210 
211 //=============================================================================
212 #endif // MB_BSPTREENODE_HH defined
213 //=============================================================================
ACG::SceneGraph::BaseNode::parent_
BaseNode * parent_
pointer to parent node
Definition: BaseNode.hh:741
OpenMesh::PolyMeshT::VertexHandle
Kernel::VertexHandle VertexHandle
Handle for referencing the corresponding item.
Definition: PolyMeshT.hh:139
OpenMesh::PolyMeshT::Point
Kernel::Point Point
Coordinate type.
Definition: PolyMeshT.hh:115
TreeNode::visualizeTree
void visualizeTree(MeshT *_object, int _max_depth)
This visualizes the bounding boxes.
Definition: BSPTreeNode.hh:117