nuclear@0: /* nuclear@0: --------------------------------------------------------------------------- nuclear@0: Open Asset Import Library (assimp) nuclear@0: --------------------------------------------------------------------------- nuclear@0: nuclear@0: Copyright (c) 2006-2012, assimp team nuclear@0: nuclear@0: All rights reserved. nuclear@0: nuclear@0: Redistribution and use of this software in source and binary forms, nuclear@0: with or without modification, are permitted provided that the following nuclear@0: conditions are met: nuclear@0: nuclear@0: * Redistributions of source code must retain the above nuclear@0: copyright notice, this list of conditions and the nuclear@0: following disclaimer. nuclear@0: nuclear@0: * Redistributions in binary form must reproduce the above nuclear@0: copyright notice, this list of conditions and the nuclear@0: following disclaimer in the documentation and/or other nuclear@0: materials provided with the distribution. nuclear@0: nuclear@0: * Neither the name of the assimp team, nor the names of its nuclear@0: contributors may be used to endorse or promote products nuclear@0: derived from this software without specific prior nuclear@0: written permission of the assimp team. nuclear@0: nuclear@0: THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS nuclear@0: "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT nuclear@0: LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR nuclear@0: A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT nuclear@0: OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, nuclear@0: SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT nuclear@0: LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, nuclear@0: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY nuclear@0: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT nuclear@0: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE nuclear@0: OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. nuclear@0: --------------------------------------------------------------------------- nuclear@0: */ nuclear@0: nuclear@0: /** @file Implementation of the helper class to quickly find nuclear@0: vertices close to a given position. Special implementation for nuclear@0: the 3ds loader handling smooth groups correctly */ nuclear@0: nuclear@0: #include "AssimpPCH.h" nuclear@0: #include "SGSpatialSort.h" nuclear@0: nuclear@0: using namespace Assimp; nuclear@0: nuclear@0: nuclear@0: // ------------------------------------------------------------------------------------------------ nuclear@0: SGSpatialSort::SGSpatialSort() nuclear@0: { nuclear@0: // define the reference plane. We choose some arbitrary vector away from all basic axises nuclear@0: // in the hope that no model spreads all its vertices along this plane. nuclear@0: mPlaneNormal.Set( 0.8523f, 0.34321f, 0.5736f); nuclear@0: mPlaneNormal.Normalize(); nuclear@0: } nuclear@0: // ------------------------------------------------------------------------------------------------ nuclear@0: // Destructor nuclear@0: SGSpatialSort::~SGSpatialSort() nuclear@0: { nuclear@0: // nothing to do here, everything destructs automatically nuclear@0: } nuclear@0: // ------------------------------------------------------------------------------------------------ nuclear@0: void SGSpatialSort::Add(const aiVector3D& vPosition, unsigned int index, nuclear@0: unsigned int smoothingGroup) nuclear@0: { nuclear@0: // store position by index and distance nuclear@0: float distance = vPosition * mPlaneNormal; nuclear@0: mPositions.push_back( Entry( index, vPosition, nuclear@0: distance, smoothingGroup)); nuclear@0: } nuclear@0: // ------------------------------------------------------------------------------------------------ nuclear@0: void SGSpatialSort::Prepare() nuclear@0: { nuclear@0: // now sort the array ascending by distance. nuclear@0: std::sort( this->mPositions.begin(), this->mPositions.end()); nuclear@0: } nuclear@0: // ------------------------------------------------------------------------------------------------ nuclear@0: // Returns an iterator for all positions close to the given position. nuclear@0: void SGSpatialSort::FindPositions( const aiVector3D& pPosition, nuclear@0: uint32_t pSG, nuclear@0: float pRadius, nuclear@0: std::vector& poResults, nuclear@0: bool exactMatch /*= false*/) const nuclear@0: { nuclear@0: float dist = pPosition * mPlaneNormal; nuclear@0: float minDist = dist - pRadius, maxDist = dist + pRadius; nuclear@0: nuclear@0: // clear the array in this strange fashion because a simple clear() would also deallocate nuclear@0: // the array which we want to avoid nuclear@0: poResults.erase( poResults.begin(), poResults.end()); nuclear@0: nuclear@0: // quick check for positions outside the range nuclear@0: if( mPositions.size() == 0) nuclear@0: return; nuclear@0: if( maxDist < mPositions.front().mDistance) nuclear@0: return; nuclear@0: if( minDist > mPositions.back().mDistance) nuclear@0: return; nuclear@0: nuclear@0: // do a binary search for the minimal distance to start the iteration there nuclear@0: unsigned int index = (unsigned int)mPositions.size() / 2; nuclear@0: unsigned int binaryStepSize = (unsigned int)mPositions.size() / 4; nuclear@0: while( binaryStepSize > 1) nuclear@0: { nuclear@0: if( mPositions[index].mDistance < minDist) nuclear@0: index += binaryStepSize; nuclear@0: else nuclear@0: index -= binaryStepSize; nuclear@0: nuclear@0: binaryStepSize /= 2; nuclear@0: } nuclear@0: nuclear@0: // depending on the direction of the last step we need to single step a bit back or forth nuclear@0: // to find the actual beginning element of the range nuclear@0: while( index > 0 && mPositions[index].mDistance > minDist) nuclear@0: index--; nuclear@0: while( index < (mPositions.size() - 1) && mPositions[index].mDistance < minDist) nuclear@0: index++; nuclear@0: nuclear@0: // Mow start iterating from there until the first position lays outside of the distance range. nuclear@0: // Add all positions inside the distance range within the given radius to the result aray nuclear@0: nuclear@0: float squareEpsilon = pRadius * pRadius; nuclear@0: std::vector::const_iterator it = mPositions.begin() + index; nuclear@0: std::vector::const_iterator end = mPositions.end(); nuclear@0: nuclear@0: if (exactMatch) nuclear@0: { nuclear@0: while( it->mDistance < maxDist) nuclear@0: { nuclear@0: if((it->mPosition - pPosition).SquareLength() < squareEpsilon && it->mSmoothGroups == pSG) nuclear@0: { nuclear@0: poResults.push_back( it->mIndex); nuclear@0: } nuclear@0: ++it; nuclear@0: if( end == it )break; nuclear@0: } nuclear@0: } nuclear@0: else nuclear@0: { nuclear@0: // if the given smoothing group is 0, we'll return all surrounding vertices nuclear@0: if (!pSG) nuclear@0: { nuclear@0: while( it->mDistance < maxDist) nuclear@0: { nuclear@0: if((it->mPosition - pPosition).SquareLength() < squareEpsilon) nuclear@0: poResults.push_back( it->mIndex); nuclear@0: ++it; nuclear@0: if( end == it)break; nuclear@0: } nuclear@0: } nuclear@0: else while( it->mDistance < maxDist) nuclear@0: { nuclear@0: if((it->mPosition - pPosition).SquareLength() < squareEpsilon && nuclear@0: (it->mSmoothGroups & pSG || !it->mSmoothGroups)) nuclear@0: { nuclear@0: poResults.push_back( it->mIndex); nuclear@0: } nuclear@0: ++it; nuclear@0: if( end == it)break; nuclear@0: } nuclear@0: } nuclear@0: } nuclear@0: nuclear@0: