1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/libs/assimp/SGSpatialSort.cpp	Sat Feb 01 19:58:19 2014 +0200
     1.3 @@ -0,0 +1,169 @@
     1.4 +/*
     1.5 +---------------------------------------------------------------------------
     1.6 +Open Asset Import Library (assimp)
     1.7 +---------------------------------------------------------------------------
     1.8 +
     1.9 +Copyright (c) 2006-2012, assimp team
    1.10 +
    1.11 +All rights reserved.
    1.12 +
    1.13 +Redistribution and use of this software in source and binary forms, 
    1.14 +with or without modification, are permitted provided that the following 
    1.15 +conditions are met:
    1.16 +
    1.17 +* Redistributions of source code must retain the above
    1.18 +copyright notice, this list of conditions and the
    1.19 +following disclaimer.
    1.20 +
    1.21 +* Redistributions in binary form must reproduce the above
    1.22 +copyright notice, this list of conditions and the
    1.23 +following disclaimer in the documentation and/or other
    1.24 +materials provided with the distribution.
    1.25 +
    1.26 +* Neither the name of the assimp team, nor the names of its
    1.27 +contributors may be used to endorse or promote products
    1.28 +derived from this software without specific prior
    1.29 +written permission of the assimp team.
    1.30 +
    1.31 +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
    1.32 +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
    1.33 +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
    1.34 +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 
    1.35 +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
    1.36 +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
    1.37 +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    1.38 +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
    1.39 +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
    1.40 +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
    1.41 +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    1.42 +---------------------------------------------------------------------------
    1.43 +*/
    1.44 +
    1.45 +/** @file Implementation of the helper class to quickly find 
    1.46 +vertices close to a given position. Special implementation for 
    1.47 +the 3ds loader handling smooth groups correctly  */
    1.48 +
    1.49 +#include "AssimpPCH.h"
    1.50 +#include "SGSpatialSort.h"
    1.51 +
    1.52 +using namespace Assimp;
    1.53 +
    1.54 +
    1.55 +// ------------------------------------------------------------------------------------------------
    1.56 +SGSpatialSort::SGSpatialSort()
    1.57 +{
    1.58 +	// define the reference plane. We choose some arbitrary vector away from all basic axises 
    1.59 +	// in the hope that no model spreads all its vertices along this plane.
    1.60 +	mPlaneNormal.Set( 0.8523f, 0.34321f, 0.5736f);
    1.61 +	mPlaneNormal.Normalize();
    1.62 +}
    1.63 +// ------------------------------------------------------------------------------------------------
    1.64 +// Destructor
    1.65 +SGSpatialSort::~SGSpatialSort()
    1.66 +{
    1.67 +	// nothing to do here, everything destructs automatically
    1.68 +}
    1.69 +// ------------------------------------------------------------------------------------------------
    1.70 +void SGSpatialSort::Add(const aiVector3D& vPosition, unsigned int index,
    1.71 +	unsigned int smoothingGroup)
    1.72 +{
    1.73 +	// store position by index and distance
    1.74 +	float distance = vPosition * mPlaneNormal;
    1.75 +	mPositions.push_back( Entry( index, vPosition, 
    1.76 +		distance, smoothingGroup));
    1.77 +}
    1.78 +// ------------------------------------------------------------------------------------------------
    1.79 +void SGSpatialSort::Prepare()
    1.80 +{
    1.81 +	// now sort the array ascending by distance.
    1.82 +	std::sort( this->mPositions.begin(), this->mPositions.end());
    1.83 +}
    1.84 +// ------------------------------------------------------------------------------------------------
    1.85 +// Returns an iterator for all positions close to the given position.
    1.86 +void SGSpatialSort::FindPositions( const aiVector3D& pPosition, 
    1.87 +	uint32_t pSG,
    1.88 +	float pRadius,
    1.89 +	std::vector<unsigned int>& poResults,
    1.90 +	bool exactMatch /*= false*/) const
    1.91 +{
    1.92 +	float dist = pPosition * mPlaneNormal;
    1.93 +	float minDist = dist - pRadius, maxDist = dist + pRadius;
    1.94 +
    1.95 +	// clear the array in this strange fashion because a simple clear() would also deallocate
    1.96 +	// the array which we want to avoid
    1.97 +	poResults.erase( poResults.begin(), poResults.end());
    1.98 +
    1.99 +	// quick check for positions outside the range
   1.100 +	if( mPositions.size() == 0)
   1.101 +		return;
   1.102 +	if( maxDist < mPositions.front().mDistance)
   1.103 +		return;
   1.104 +	if( minDist > mPositions.back().mDistance)
   1.105 +		return;
   1.106 +
   1.107 +	// do a binary search for the minimal distance to start the iteration there
   1.108 +	unsigned int index = (unsigned int)mPositions.size() / 2;
   1.109 +	unsigned int binaryStepSize = (unsigned int)mPositions.size() / 4;
   1.110 +	while( binaryStepSize > 1)
   1.111 +	{
   1.112 +		if( mPositions[index].mDistance < minDist)
   1.113 +			index += binaryStepSize;
   1.114 +		else
   1.115 +			index -= binaryStepSize;
   1.116 +
   1.117 +		binaryStepSize /= 2;
   1.118 +	}
   1.119 +
   1.120 +	// depending on the direction of the last step we need to single step a bit back or forth
   1.121 +	// to find the actual beginning element of the range
   1.122 +	while( index > 0 && mPositions[index].mDistance > minDist)
   1.123 +		index--;
   1.124 +	while( index < (mPositions.size() - 1) && mPositions[index].mDistance < minDist)
   1.125 +		index++;
   1.126 +
   1.127 +	// Mow start iterating from there until the first position lays outside of the distance range.
   1.128 +	// Add all positions inside the distance range within the given radius to the result aray
   1.129 +
   1.130 +	float squareEpsilon = pRadius * pRadius;
   1.131 +	std::vector<Entry>::const_iterator it  = mPositions.begin() + index;
   1.132 +	std::vector<Entry>::const_iterator end = mPositions.end();
   1.133 +
   1.134 +	if (exactMatch)
   1.135 +	{
   1.136 +		while( it->mDistance < maxDist)
   1.137 +		{
   1.138 +			if((it->mPosition - pPosition).SquareLength() < squareEpsilon && it->mSmoothGroups == pSG)
   1.139 +			{
   1.140 +				poResults.push_back( it->mIndex);
   1.141 +			}
   1.142 +			++it;
   1.143 +			if( end == it )break;
   1.144 +		}
   1.145 +	}
   1.146 +	else
   1.147 +	{
   1.148 +		// if the given smoothing group is 0, we'll return all surrounding vertices
   1.149 +		if (!pSG)
   1.150 +		{
   1.151 +			while( it->mDistance < maxDist)
   1.152 +			{
   1.153 +				if((it->mPosition - pPosition).SquareLength() < squareEpsilon)
   1.154 +					poResults.push_back( it->mIndex);
   1.155 +				++it;
   1.156 +				if( end == it)break;
   1.157 +			}
   1.158 +		}
   1.159 +		else while( it->mDistance < maxDist)
   1.160 +		{
   1.161 +			if((it->mPosition - pPosition).SquareLength() < squareEpsilon &&
   1.162 +				(it->mSmoothGroups & pSG || !it->mSmoothGroups))
   1.163 +			{
   1.164 +				poResults.push_back( it->mIndex);
   1.165 +			}
   1.166 +			++it;
   1.167 +			if( end == it)break;
   1.168 +		}
   1.169 +	}
   1.170 +}
   1.171 +
   1.172 +