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 //=============================================================================
45 //
46 // CLASS TreeNode
47 //
48 //=============================================================================
49 
50 #ifndef MB_BSPTREENODE_HH
51 #define MB_BSPTREENODE_HH
52 
53 //== INCLUDES =================================================================
54 
55 #include <ACG/Geometry/Types/PlaneT.hh>
56 #include <ACG/Geometry/Algorithms.hh>
57 #include <ostream>
58 
59 //== CLASS DEFINITION =========================================================
60 
61 // Node of the tree: contains parent, children and splitting plane
62 template <class BSPTraits>
63 struct TreeNode
64 {
65  typedef typename BSPTraits::Handle Handle;
66  typedef typename BSPTraits::Point Point;
67  typedef typename BSPTraits::VertexHandle VertexHandle;
68  typedef std::vector<Handle> Handles;
69  typedef typename Handles::iterator HandleIter;
70  typedef typename Handles::const_iterator HandleConstIter;
71  typedef typename Point::value_type Scalar;
72  typedef ACG::Geometry::PlaneT<Scalar> Plane;
73 
74  TreeNode(const Handles& _handles, TreeNode* _parent)
75  : handles_(_handles),
76  parent_(_parent), left_child_(0), right_child_(0) {}
77  ~TreeNode()
78  {
79  delete left_child_;
80  delete right_child_;
81 
82  if (parent_)
83  {
84  if (this == parent_->left_child_)
85  parent_->left_child_ = 0;
86  else
87  parent_->right_child_ = 0;
88  }
89  }
90 
91  HandleIter begin() {
92  return handles_.begin();
93  }
94 
95  HandleIter end() {
96  return handles_.end();
97  }
98 
99  HandleConstIter begin() const {
100  return handles_.begin();
101  }
102 
103  HandleConstIter end() const {
104  return handles_.end();
105  }
106 
107  size_t size() const {
108  return handles_.size();
109  }
110 
111  Handles handles_;
112  TreeNode *parent_, *left_child_, *right_child_;
113  Plane plane_;
114  Point bb_min, bb_max;
115 
117  template< typename MeshT >
118  void visualizeTree(MeshT *_object, int _max_depth)
119  {
120  if (_max_depth > 0 && (left_child_ || right_child_) )
121  {
122  if (left_child_)
123  left_child_->visualizeTree(_object, _max_depth-1);
124  if (right_child_)
125  right_child_->visualizeTree(_object, _max_depth-1);
126  }
127  else
128  {
129  Point size_ = bb_max - bb_min;
130 
131  std::vector<VertexHandle> vhandle(8);
132  vhandle[0] = _object->add_vertex(bb_min+Point(0.0,0.0,size_[2]));
133  vhandle[1] = _object->add_vertex(bb_min+Point(size_[0],0.0,size_[2]));
134  vhandle[2] = _object->add_vertex(bb_min+Point(size_[0],size_[1],size_[2]));
135  vhandle[3] = _object->add_vertex(bb_min+Point(0.0,size_[1],size_[2]));
136  vhandle[4] = _object->add_vertex(bb_min+Point(0.0,0.0,0.0));
137  vhandle[5] = _object->add_vertex(bb_min+Point(size_[0],0.0,0.0));
138  vhandle[6] = _object->add_vertex(bb_min+Point(size_[0],size_[1],0.0));
139  vhandle[7] = _object->add_vertex(bb_min+Point(0.0,size_[1],0.0));
140 
141 
142  // generate (quadrilateral) faces
143  std::vector<VertexHandle> face_vhandles;
144 
145  face_vhandles.clear();
146  face_vhandles.push_back(vhandle[0]);
147  face_vhandles.push_back(vhandle[1]);
148  face_vhandles.push_back(vhandle[2]);
149  face_vhandles.push_back(vhandle[3]);
150  _object->add_face(face_vhandles);
151 
152  face_vhandles.clear();
153  face_vhandles.push_back(vhandle[7]);
154  face_vhandles.push_back(vhandle[6]);
155  face_vhandles.push_back(vhandle[5]);
156  face_vhandles.push_back(vhandle[4]);
157  _object->add_face(face_vhandles);
158 
159  face_vhandles.clear();
160  face_vhandles.push_back(vhandle[1]);
161  face_vhandles.push_back(vhandle[0]);
162  face_vhandles.push_back(vhandle[4]);
163  face_vhandles.push_back(vhandle[5]);
164  _object->add_face(face_vhandles);
165 
166  face_vhandles.clear();
167  face_vhandles.push_back(vhandle[2]);
168  face_vhandles.push_back(vhandle[1]);
169  face_vhandles.push_back(vhandle[5]);
170  face_vhandles.push_back(vhandle[6]);
171  _object->add_face(face_vhandles);
172 
173  face_vhandles.clear();
174  face_vhandles.push_back(vhandle[3]);
175  face_vhandles.push_back(vhandle[2]);
176  face_vhandles.push_back(vhandle[6]);
177  face_vhandles.push_back(vhandle[7]);
178  _object->add_face(face_vhandles);
179 
180  face_vhandles.clear();
181  face_vhandles.push_back(vhandle[0]);
182  face_vhandles.push_back(vhandle[3]);
183  face_vhandles.push_back(vhandle[7]);
184  face_vhandles.push_back(vhandle[4]);
185  _object->add_face(face_vhandles);
186  }
187  }
188 
189  private:
190  /*
191  * Noncopyable because of root_.
192  */
193  TreeNode(const TreeNode &rhs);
194  TreeNode &operator=(const TreeNode &rhs);
195 
196 };
197 
198 template<class BSPTraits>
199 std::ostream &operator<< (std::ostream &stream, const TreeNode<BSPTraits> &node) {
200  stream << "[TreeNode instance. Handles: ";
201  for (typename TreeNode<BSPTraits>::Handles::const_iterator it = node.handles_.begin(), it_end = node.handles_.end();
202  it != it_end; ++it) {
203  stream << it->idx();
204  if (it < it_end-1) stream << ", ";
205  }
206  stream << ", parent: " << node.parent_ << ", left_child_: " << node.left_child_
207  << ", right_child_: " << node.right_child_ << ", plane_: <not implemented>, bb_min: "
208  << node.bb_min << ", bb_max: " << node.bb_max << ", size(): " << node.size() << "]";
209  return stream;
210 }
211 
212 //=============================================================================
213 #endif // MB_BSPTREENODE_HH defined
214 //=============================================================================
TreeNode::visualizeTree
void visualizeTree(MeshT *_object, int _max_depth)
This visualizes the bounding boxes.
Definition: BSPTreeNode.hh:118