Equalizer  1.2.1
eqPly/vertexBufferNode.cpp
00001 
00002 /* Copyright (c) 2007, Tobias Wolf <twolf@access.unizh.ch>
00003  *               2008-2011, Stefan Eilemann <eile@equalizergraphics.com>
00004  *
00005  * Redistribution and use in source and binary forms, with or without
00006  * modification, are permitted provided that the following conditions are met:
00007  *
00008  * - Redistributions of source code must retain the above copyright notice, this
00009  *   list of conditions and the following disclaimer.
00010  * - Redistributions in binary form must reproduce the above copyright notice,
00011  *   this list of conditions and the following disclaimer in the documentation
00012  *   and/or other materials provided with the distribution.
00013  * - Neither the name of Eyescale Software GmbH nor the names of its
00014  *   contributors may be used to endorse or promote products derived from this
00015  *   software without specific prior written permission.
00016  *
00017  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
00018  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00019  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00020  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
00021  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
00022  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
00023  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
00024  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
00025  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
00026  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
00027  * POSSIBILITY OF SUCH DAMAGE.
00028  */
00029 
00030 
00031 #include "vertexBufferNode.h"
00032 #include "vertexBufferLeaf.h"
00033 #include "vertexBufferState.h"
00034 #include "vertexData.h"
00035 #include <set>
00036 
00037 namespace mesh
00038 {
00039 
00040 /*  Destructor, clears up children as well.  */
00041 VertexBufferNode::~VertexBufferNode()
00042 {
00043     delete _left;
00044     delete _right;
00045     _left = 0;
00046     _right = 0;
00047 }
00048 
00049 inline static bool _subdivide( const Index length, const size_t depth )
00050 {
00051     return ( length / 2 > LEAF_SIZE ) || ( depth < 3 && length > 1 );
00052 }
00053 
00054 /*  Continue kd-tree setup, create intermediary or leaf nodes as required.  */
00055 void VertexBufferNode::setupTree( VertexData& data, const Index start,
00056                                   const Index length, const Axis axis,
00057                                   const size_t depth,
00058                                   VertexBufferData& globalData )
00059 {
00060 #ifndef NDEBUG
00061     MESHINFO << "setupTree"
00062              << "( " << start << ", " << length << ", " << axis << ", " 
00063              << depth << " )." << std::endl;
00064 #endif
00065 
00066     data.sort( start, length, axis );
00067     const Index median = start + ( length / 2 );
00068 
00069     // left child will include elements smaller than the median
00070     const Index leftLength    = length / 2;
00071     const bool  subdivideLeft = _subdivide( leftLength, depth );
00072 
00073     if( subdivideLeft )
00074         _left = new VertexBufferNode;
00075     else
00076         _left = new VertexBufferLeaf( globalData );
00077     
00078     // right child will include elements equal to or greater than the median
00079     const Index rightLength    = ( length + 1 ) / 2;
00080     const bool  subdivideRight = _subdivide( rightLength, depth );
00081 
00082     if( subdivideRight )
00083         _right = new VertexBufferNode;
00084     else
00085         _right = new VertexBufferLeaf( globalData );
00086     
00087     // move to next axis and continue contruction in the child nodes
00088     const Axis newAxisLeft  = subdivideLeft ? 
00089                         data.getLongestAxis( start , leftLength  ) : AXIS_X;
00090 
00091     const Axis newAxisRight = subdivideRight ? 
00092                         data.getLongestAxis( median, rightLength ) : AXIS_X;
00093 
00094     static_cast< VertexBufferNode* >
00095             ( _left )->setupTree( data, start, leftLength, newAxisLeft, depth+1,
00096                                   globalData );
00097     static_cast< VertexBufferNode* >
00098         ( _right )->setupTree( data, median, rightLength, newAxisRight, depth+1,
00099                                globalData );
00100 
00101 }
00102 
00103 
00104 /*  Compute the bounding sphere from the children's bounding spheres.  */
00105 const BoundingSphere& VertexBufferNode::updateBoundingSphere()
00106 {
00107     // take the bounding spheres returned by the children
00108     const BoundingSphere& sphere1 = _left->updateBoundingSphere();
00109     const BoundingSphere& sphere2 = _right->updateBoundingSphere();
00110     
00111     // compute enclosing sphere
00112     const Vertex center1( sphere1.array );
00113     const Vertex center2( sphere2.array );
00114     Vertex c1ToC2     = center2 - center1;
00115     c1ToC2.normalize();
00116     
00117     const Vertex outer1 = center1 - c1ToC2 * sphere1.w();
00118     const Vertex outer2 = center2 + c1ToC2 * sphere2.w();
00119 
00120     Vertex vertexBoundingSphere = Vertex( outer1 + outer2 ) * 0.5f; 
00121     _boundingSphere.x() = vertexBoundingSphere.x();
00122     _boundingSphere.y() = vertexBoundingSphere.y();
00123     _boundingSphere.z() = vertexBoundingSphere.z();
00124     _boundingSphere.w() = Vertex( outer1 - outer2 ).length() * 0.5f;
00125     
00126 #ifndef NDEBUG
00127     MESHINFO << "updateBoundingSphere" << "( " << _boundingSphere << " )." 
00128              << std::endl;
00129 #endif
00130     
00131     return _boundingSphere;
00132 }
00133 
00134 
00135 /*  Compute the range from the children's ranges.  */
00136 void VertexBufferNode::updateRange()
00137 {
00138     // update the children's ranges
00139     static_cast< VertexBufferNode* >( _left )->updateRange();
00140     static_cast< VertexBufferNode* >( _right )->updateRange();
00141     
00142     // set node range to min/max of the children's ranges
00143     _range[0] = std::min( _left->getRange()[0], _right->getRange()[0] );
00144     _range[1] = std::max( _left->getRange()[1], _right->getRange()[1] );
00145     
00146 #ifndef NDEBUG
00147     MESHINFO << "updateRange" << "( " << _range[0] << ", " << _range[1]
00148              << " )." << std::endl;
00149 #endif
00150 }
00151 
00152 
00153 /*  Draw the node by rendering the children.  */
00154 void VertexBufferNode::draw( VertexBufferState& state ) const
00155 {
00156     if ( state.stopRendering( ))
00157         return;
00158 
00159     _left->draw( state );
00160     _right->draw( state );
00161 }
00162 
00163 
00164 /*  Read node from memory and continue with remaining nodes.  */
00165 void VertexBufferNode::fromMemory( char** addr, VertexBufferData& globalData )
00166 {
00167     // read node itself   
00168     size_t nodeType;
00169     memRead( reinterpret_cast< char* >( &nodeType ), addr, sizeof( size_t ) );
00170     if( nodeType != NODE_TYPE )
00171         throw MeshException( "Error reading binary file. Expected a regular "
00172                              "node, but found something else instead." );
00173     VertexBufferBase::fromMemory( addr, globalData );
00174     
00175     // read left child (peek ahead)
00176     memRead( reinterpret_cast< char* >( &nodeType ), addr, sizeof( size_t ) );
00177     if( nodeType != NODE_TYPE && nodeType != LEAF_TYPE )
00178         throw MeshException( "Error reading binary file. Expected either a "
00179                              "regular or a leaf node, but found neither." );
00180     *addr -= sizeof( size_t );
00181     if( nodeType == NODE_TYPE )
00182         _left = new VertexBufferNode;
00183     else
00184         _left = new VertexBufferLeaf( globalData );
00185     static_cast< VertexBufferNode* >( _left )->fromMemory( addr, globalData );
00186     
00187     // read right child (peek ahead)
00188     memRead( reinterpret_cast< char* >( &nodeType ), addr, sizeof( size_t ) );
00189     if( nodeType != NODE_TYPE && nodeType != LEAF_TYPE )
00190         throw MeshException( "Error reading binary file. Expected either a "
00191                              "regular or a leaf node, but found neither." );
00192     *addr -= sizeof( size_t );
00193     if( nodeType == NODE_TYPE )
00194         _right = new VertexBufferNode;
00195     else
00196         _right = new VertexBufferLeaf( globalData );
00197     static_cast< VertexBufferNode* >( _right )->fromMemory( addr, globalData );
00198 }
00199 
00200 
00201 /*  Write node to output stream and continue with remaining nodes.  */
00202 void VertexBufferNode::toStream( std::ostream& os )
00203 {
00204     size_t nodeType = NODE_TYPE;
00205     os.write( reinterpret_cast< char* >( &nodeType ), sizeof( size_t ) );
00206     VertexBufferBase::toStream( os );
00207     static_cast< VertexBufferNode* >( _left )->toStream( os );
00208     static_cast< VertexBufferNode* >( _right )->toStream( os );
00209 }
00210 
00211 }
Generated on Fri Jun 8 2012 15:44:33 for Equalizer 1.2.1 by  doxygen 1.8.0