Developer Documentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
TriangleBSPCoreT.cc
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: 12862 $ *
45 * $LastChangedBy: moebius $ *
46 * $Date: 2011-11-16 14:25:59 +0100 (Wed, 16 Nov 2011) $ *
47 * *
48 \*===========================================================================*/
49 
50 
51 
52 
53 //=============================================================================
54 //
55 // CLASS TriangleBSPCoreT
56 //
57 //=============================================================================
58 
59 #define TRIANGLEBSPCORET_C
60 
61 //== INCLUDES =================================================================
62 
63 
64 #include "TriangleBSPCoreT.hh"
65 
66 
67 //== CLASS DEFINITION =========================================================
68 
69 template <class BSPTraits>
70 void
72 build(unsigned int _max_handles, unsigned int _max_depth)
73 {
74  // init
75  delete root_;
76  root_ = new Node(handles_, 0);
77 
78  // delete own handles (don't store them twice)
79  handles_ = Handles();
80 
81  nodes=1;
82  traits_.calculateBoundingBoxRoot (root_);
83  // call recursive helper
84  _build(root_, _max_handles, _max_depth);
85 
86 }
87 
88 
89 //-----------------------------------------------------------------------------
90 
91 
92 template <class BSPTraits>
93 void
95 _build(Node* _node,
96  unsigned int _max_handles,
97  unsigned int _depth)
98 {
99  // should we stop at this level ?
100  if ((_depth == 0) || ((_node->end()-_node->begin()) <= (int)_max_handles))
101  return;
102 
103  Point median;
104  int axis;
105  // compute bounding boxes for children
106  traits_.calculateBoundingBox (_node, median, axis);
107 
108  // construct splitting plane
109  const Point XYZ[3] = { Point(1,0,0), Point(0,1,0), Point(0,0,1) };
110  _node->plane_ = Plane(median, XYZ[axis]);
111 
112  // partition for left and right child
113  Handles lhandles, rhandles;
114  lhandles.reserve(_node->handles_.size()/2);
115  rhandles.reserve(_node->handles_.size()/2);
116 
117  HandleIter it;
118  Point p0, p1, p2;
119  for (it=_node->begin(); it!=_node->end(); ++it)
120  {
121  traits_.points(*it, p0, p1, p2);
122 
123  /* @TODO Remove this comment block. Replaced by the clause below
124 
125  if (_node->plane_(p0)) left = true;
126  else right = true;
127  if (_node->plane_(p1)) left = true;
128  else right = true;
129  if (_node->plane_(p2)) left = true;
130  else right = true;
131 
132  if (left) lhandles.push_back(*it);
133  if (right) rhandles.push_back(*it);
134  */
135 
136  if ( _node->plane_(p0) || _node->plane_(p1) || _node->plane_(p2) ) lhandles.push_back(*it);
137  if ( !_node->plane_(p0) || !_node->plane_(p1) || !_node->plane_(p2) ) rhandles.push_back(*it);
138 
139  }
140 
141  // check it
142  if (lhandles.size() == _node->handles_.size() ||
143  rhandles.size() == _node->handles_.size())
144  return;
145  else
146  _node->handles_ = Handles();
147 
148 
149  // create children
150  _node->left_child_ = new Node(lhandles, _node); lhandles = Handles();
151  _node->right_child_ = new Node(rhandles, _node); rhandles = Handles();
152  nodes+=2;
153 
154  //save bounding boxes for children
155  /*
156  _node->left_child_->bb_min = _node->bb_min;
157  _node->left_child_->bb_max = _node->bb_max;
158  _node->left_child_->bb_max[axis] = median [axis];
159 
160  _node->right_child_->bb_min = _node->bb_min;
161  _node->right_child_->bb_min[axis] = median [axis];
162  _node->right_child_->bb_max = _node->bb_max;
163  */
164  _node->right_child_->bb_min = _node->bb_min;
165  _node->right_child_->bb_max = _node->bb_max;
166  _node->right_child_->bb_max[axis] = median [axis];
167 
168  _node->left_child_->bb_min = _node->bb_min;
169  _node->left_child_->bb_min[axis] = median [axis];
170  _node->left_child_->bb_max = _node->bb_max;
171 
172  // recurse to childen
173  _build(_node->left_child_, _max_handles, _depth-1);
174  _build(_node->right_child_, _max_handles, _depth-1);
175 }
176 
177 //=============================================================================
178 
179 
void build(unsigned int _max_handles, unsigned int _max_depth)