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
62template <class BSPTraits>
63struct 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
198template<class BSPTraits>
199std::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//=============================================================================
OpenMesh::Utils::Timer::operator<<
std::ostream & operator<<(std::ostream &_o, const Timer &_t)
Definition: Timer.hh:205
OpenVolumeMesh::GeometryKernel::add_vertex
VertexHandle add_vertex(const VecT &_p)
Add a geometric point to the mesh.
Definition: GeometryKernel.hh:111
OpenVolumeMesh::TopologyKernel::add_face
virtual FaceHandle add_face(std::vector< HalfEdgeHandle > _halfedges, bool _topologyCheck=false)
Add face via incident edges.
Definition: TopologyKernel.cc:176
TreeNode::visualizeTree
void visualizeTree(MeshT *_object, int _max_depth)
This visualizes the bounding boxes.
Definition: BSPTreeNode.hh:118