Equalizer  1.6.1
eqPly/vertexBufferNode.cpp
1 
2 /* Copyright (c) 2007, Tobias Wolf <twolf@access.unizh.ch>
3  * 2008-2011, Stefan Eilemann <eile@equalizergraphics.com>
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are met:
7  *
8  * - Redistributions of source code must retain the above copyright notice, this
9  * list of conditions and the following disclaimer.
10  * - Redistributions in binary form must reproduce the above copyright notice,
11  * this list of conditions and the following disclaimer in the documentation
12  * and/or other materials provided with the distribution.
13  * - Neither the name of Eyescale Software GmbH nor the names of its
14  * contributors may be used to endorse or promote products derived from this
15  * software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
21  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27  * POSSIBILITY OF SUCH DAMAGE.
28  */
29 
30 
31 #include "vertexBufferNode.h"
32 #include "vertexBufferLeaf.h"
33 #include "vertexBufferState.h"
34 #include "vertexData.h"
35 #include <set>
36 
37 namespace mesh
38 {
39 
40 /* Destructor, clears up children as well. */
41 VertexBufferNode::~VertexBufferNode()
42 {
43  delete _left;
44  delete _right;
45  _left = 0;
46  _right = 0;
47 }
48 
49 inline static bool _subdivide( const Index length, const size_t depth )
50 {
51  return ( length / 2 > LEAF_SIZE ) || ( depth < 3 && length > 1 );
52 }
53 
54 /* Continue kd-tree setup, create intermediary or leaf nodes as required. */
55 void VertexBufferNode::setupTree( VertexData& data, const Index start,
56  const Index length, const Axis axis,
57  const size_t depth,
58  VertexBufferData& globalData )
59 {
60 #ifndef NDEBUG
61  MESHINFO << "setupTree"
62  << "( " << start << ", " << length << ", " << axis << ", "
63  << depth << " )." << std::endl;
64 #endif
65 
66  data.sort( start, length, axis );
67  const Index median = start + ( length / 2 );
68 
69  // left child will include elements smaller than the median
70  const Index leftLength = length / 2;
71  const bool subdivideLeft = _subdivide( leftLength, depth );
72 
73  if( subdivideLeft )
74  _left = new VertexBufferNode;
75  else
76  _left = new VertexBufferLeaf( globalData );
77 
78  // right child will include elements equal to or greater than the median
79  const Index rightLength = ( length + 1 ) / 2;
80  const bool subdivideRight = _subdivide( rightLength, depth );
81 
82  if( subdivideRight )
83  _right = new VertexBufferNode;
84  else
85  _right = new VertexBufferLeaf( globalData );
86 
87  // move to next axis and continue contruction in the child nodes
88  const Axis newAxisLeft = subdivideLeft ?
89  data.getLongestAxis( start , leftLength ) : AXIS_X;
90 
91  const Axis newAxisRight = subdivideRight ?
92  data.getLongestAxis( median, rightLength ) : AXIS_X;
93 
94  static_cast< VertexBufferNode* >
95  ( _left )->setupTree( data, start, leftLength, newAxisLeft, depth+1,
96  globalData );
97  static_cast< VertexBufferNode* >
98  ( _right )->setupTree( data, median, rightLength, newAxisRight, depth+1,
99  globalData );
100 
101 }
102 
103 
104 /* Compute the bounding sphere from the children's bounding spheres. */
105 const BoundingSphere& VertexBufferNode::updateBoundingSphere()
106 {
107  // take the bounding spheres returned by the children
108  const BoundingSphere& sphere1 = _left->updateBoundingSphere();
109  const BoundingSphere& sphere2 = _right->updateBoundingSphere();
110 
111  // compute enclosing sphere
112  const Vertex center1( sphere1.array );
113  const Vertex center2( sphere2.array );
114  Vertex c1ToC2 = center2 - center1;
115  c1ToC2.normalize();
116 
117  const Vertex outer1 = center1 - c1ToC2 * sphere1.w();
118  const Vertex outer2 = center2 + c1ToC2 * sphere2.w();
119 
120  Vertex vertexBoundingSphere = Vertex( outer1 + outer2 ) * 0.5f;
121  _boundingSphere.x() = vertexBoundingSphere.x();
122  _boundingSphere.y() = vertexBoundingSphere.y();
123  _boundingSphere.z() = vertexBoundingSphere.z();
124  _boundingSphere.w() = Vertex( outer1 - outer2 ).length() * 0.5f;
125 
126 #ifndef NDEBUG
127  MESHINFO << "updateBoundingSphere" << "( " << _boundingSphere << " )."
128  << std::endl;
129 #endif
130 
131  return _boundingSphere;
132 }
133 
134 
135 /* Compute the range from the children's ranges. */
136 void VertexBufferNode::updateRange()
137 {
138  // update the children's ranges
139  static_cast< VertexBufferNode* >( _left )->updateRange();
140  static_cast< VertexBufferNode* >( _right )->updateRange();
141 
142  // set node range to min/max of the children's ranges
143  _range[0] = std::min( _left->getRange()[0], _right->getRange()[0] );
144  _range[1] = std::max( _left->getRange()[1], _right->getRange()[1] );
145 
146 #ifndef NDEBUG
147  MESHINFO << "updateRange" << "( " << _range[0] << ", " << _range[1]
148  << " )." << std::endl;
149 #endif
150 }
151 
152 
153 /* Draw the node by rendering the children. */
154 void VertexBufferNode::draw( VertexBufferState& state ) const
155 {
156  if ( state.stopRendering( ))
157  return;
158 
159  _left->draw( state );
160  _right->draw( state );
161 }
162 
163 
164 /* Read node from memory and continue with remaining nodes. */
165 void VertexBufferNode::fromMemory( char** addr, VertexBufferData& globalData )
166 {
167  // read node itself
168  size_t nodeType;
169  memRead( reinterpret_cast< char* >( &nodeType ), addr, sizeof( size_t ) );
170  if( nodeType != NODE_TYPE )
171  throw MeshException( "Error reading binary file. Expected a regular "
172  "node, but found something else instead." );
173  VertexBufferBase::fromMemory( addr, globalData );
174 
175  // read left child (peek ahead)
176  memRead( reinterpret_cast< char* >( &nodeType ), addr, sizeof( size_t ) );
177  if( nodeType != NODE_TYPE && nodeType != LEAF_TYPE )
178  throw MeshException( "Error reading binary file. Expected either a "
179  "regular or a leaf node, but found neither." );
180  *addr -= sizeof( size_t );
181  if( nodeType == NODE_TYPE )
182  _left = new VertexBufferNode;
183  else
184  _left = new VertexBufferLeaf( globalData );
185  static_cast< VertexBufferNode* >( _left )->fromMemory( addr, globalData );
186 
187  // read right child (peek ahead)
188  memRead( reinterpret_cast< char* >( &nodeType ), addr, sizeof( size_t ) );
189  if( nodeType != NODE_TYPE && nodeType != LEAF_TYPE )
190  throw MeshException( "Error reading binary file. Expected either a "
191  "regular or a leaf node, but found neither." );
192  *addr -= sizeof( size_t );
193  if( nodeType == NODE_TYPE )
194  _right = new VertexBufferNode;
195  else
196  _right = new VertexBufferLeaf( globalData );
197  static_cast< VertexBufferNode* >( _right )->fromMemory( addr, globalData );
198 }
199 
200 
201 /* Write node to output stream and continue with remaining nodes. */
202 void VertexBufferNode::toStream( std::ostream& os )
203 {
204  size_t nodeType = NODE_TYPE;
205  os.write( reinterpret_cast< char* >( &nodeType ), sizeof( size_t ) );
206  VertexBufferBase::toStream( os );
207  static_cast< VertexBufferNode* >( _left )->toStream( os );
208  static_cast< VertexBufferNode* >( _right )->toStream( os );
209 }
210 
211 }