diff options
Diffstat (limited to 'src/3rdparty/assimp/code/SpatialSort.cpp')
| -rw-r--r-- | src/3rdparty/assimp/code/SpatialSort.cpp | 484 |
1 files changed, 242 insertions, 242 deletions
diff --git a/src/3rdparty/assimp/code/SpatialSort.cpp b/src/3rdparty/assimp/code/SpatialSort.cpp index e54665609..c4e4ef2d5 100644 --- a/src/3rdparty/assimp/code/SpatialSort.cpp +++ b/src/3rdparty/assimp/code/SpatialSort.cpp @@ -3,12 +3,12 @@ Open Asset Import Library (assimp) --------------------------------------------------------------------------- -Copyright (c) 2006-2012, assimp team +Copyright (c) 2006-2016, assimp team All rights reserved. -Redistribution and use of this software in source and binary forms, -with or without modification, are permitted provided that the following +Redistribution and use of this software in source and binary forms, +with or without modification, are permitted provided that the following conditions are met: * Redistributions of source code must retain the above @@ -25,318 +25,318 @@ conditions are met: derived from this software without specific prior written permission of the assimp team. -THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS -"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR -A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, -SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, -DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY -THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT -(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. --------------------------------------------------------------------------- */ /** @file Implementation of the helper class to quickly find vertices close to a given position */ -#include "AssimpPCH.h" #include "SpatialSort.h" +#include <assimp/ai_assert.h> using namespace Assimp; // CHAR_BIT seems to be defined under MVSC, but not under GCC. Pray that the correct value is 8. #ifndef CHAR_BIT -# define CHAR_BIT 8 +# define CHAR_BIT 8 #endif // ------------------------------------------------------------------------------------------------ // Constructs a spatially sorted representation from the given position array. -SpatialSort::SpatialSort( const aiVector3D* pPositions, unsigned int pNumPositions, - unsigned int pElementOffset) +SpatialSort::SpatialSort( const aiVector3D* pPositions, unsigned int pNumPositions, + unsigned int pElementOffset) - // define the reference plane. We choose some arbitrary vector away from all basic axises - // in the hope that no model spreads all its vertices along this plane. - : mPlaneNormal(0.8523f, 0.34321f, 0.5736f) + // define the reference plane. We choose some arbitrary vector away from all basic axises + // in the hope that no model spreads all its vertices along this plane. + : mPlaneNormal(0.8523f, 0.34321f, 0.5736f) { - mPlaneNormal.Normalize(); - Fill(pPositions,pNumPositions,pElementOffset); + mPlaneNormal.Normalize(); + Fill(pPositions,pNumPositions,pElementOffset); } // ------------------------------------------------------------------------------------------------ SpatialSort :: SpatialSort() : mPlaneNormal(0.8523f, 0.34321f, 0.5736f) { - mPlaneNormal.Normalize(); + mPlaneNormal.Normalize(); } // ------------------------------------------------------------------------------------------------ // Destructor SpatialSort::~SpatialSort() { - // nothing to do here, everything destructs automatically + // nothing to do here, everything destructs automatically } // ------------------------------------------------------------------------------------------------ -void SpatialSort::Fill( const aiVector3D* pPositions, unsigned int pNumPositions, - unsigned int pElementOffset, - bool pFinalize /*= true */) +void SpatialSort::Fill( const aiVector3D* pPositions, unsigned int pNumPositions, + unsigned int pElementOffset, + bool pFinalize /*= true */) { - mPositions.clear(); - Append(pPositions,pNumPositions,pElementOffset,pFinalize); + mPositions.clear(); + Append(pPositions,pNumPositions,pElementOffset,pFinalize); } // ------------------------------------------------------------------------------------------------ void SpatialSort :: Finalize() { - std::sort( mPositions.begin(), mPositions.end()); + std::sort( mPositions.begin(), mPositions.end()); } // ------------------------------------------------------------------------------------------------ -void SpatialSort::Append( const aiVector3D* pPositions, unsigned int pNumPositions, - unsigned int pElementOffset, - bool pFinalize /*= true */) +void SpatialSort::Append( const aiVector3D* pPositions, unsigned int pNumPositions, + unsigned int pElementOffset, + bool pFinalize /*= true */) { - // store references to all given positions along with their distance to the reference plane - const size_t initial = mPositions.size(); - mPositions.reserve(initial + (pFinalize?pNumPositions:pNumPositions*2)); - for( unsigned int a = 0; a < pNumPositions; a++) - { - const char* tempPointer = reinterpret_cast<const char*> (pPositions); - const aiVector3D* vec = reinterpret_cast<const aiVector3D*> (tempPointer + a * pElementOffset); - - // store position by index and distance - float distance = *vec * mPlaneNormal; - mPositions.push_back( Entry( a+initial, *vec, distance)); - } - - if (pFinalize) { - // now sort the array ascending by distance. - Finalize(); - } + // store references to all given positions along with their distance to the reference plane + const size_t initial = mPositions.size(); + mPositions.reserve(initial + (pFinalize?pNumPositions:pNumPositions*2)); + for( unsigned int a = 0; a < pNumPositions; a++) + { + const char* tempPointer = reinterpret_cast<const char*> (pPositions); + const aiVector3D* vec = reinterpret_cast<const aiVector3D*> (tempPointer + a * pElementOffset); + + // store position by index and distance + float distance = *vec * mPlaneNormal; + mPositions.push_back( Entry( a+initial, *vec, distance)); + } + + if (pFinalize) { + // now sort the array ascending by distance. + Finalize(); + } } // ------------------------------------------------------------------------------------------------ // Returns an iterator for all positions close to the given position. -void SpatialSort::FindPositions( const aiVector3D& pPosition, - float pRadius, std::vector<unsigned int>& poResults) const +void SpatialSort::FindPositions( const aiVector3D& pPosition, + float pRadius, std::vector<unsigned int>& poResults) const { - const float dist = pPosition * mPlaneNormal; - const float minDist = dist - pRadius, maxDist = dist + pRadius; + const float dist = pPosition * mPlaneNormal; + const float minDist = dist - pRadius, maxDist = dist + pRadius; - // clear the array in this strange fashion because a simple clear() would also deallocate + // clear the array in this strange fashion because a simple clear() would also deallocate // the array which we want to avoid - poResults.erase( poResults.begin(), poResults.end()); - - // quick check for positions outside the range - if( mPositions.size() == 0) - return; - if( maxDist < mPositions.front().mDistance) - return; - if( minDist > mPositions.back().mDistance) - return; - - // do a binary search for the minimal distance to start the iteration there - unsigned int index = (unsigned int)mPositions.size() / 2; - unsigned int binaryStepSize = (unsigned int)mPositions.size() / 4; - while( binaryStepSize > 1) - { - if( mPositions[index].mDistance < minDist) - index += binaryStepSize; - else - index -= binaryStepSize; - - binaryStepSize /= 2; - } - - // depending on the direction of the last step we need to single step a bit back or forth - // to find the actual beginning element of the range - while( index > 0 && mPositions[index].mDistance > minDist) - index--; - while( index < (mPositions.size() - 1) && mPositions[index].mDistance < minDist) - index++; - - // Mow start iterating from there until the first position lays outside of the distance range. - // Add all positions inside the distance range within the given radius to the result aray - std::vector<Entry>::const_iterator it = mPositions.begin() + index; - const float pSquared = pRadius*pRadius; - while( it->mDistance < maxDist) - { - if( (it->mPosition - pPosition).SquareLength() < pSquared) - poResults.push_back( it->mIndex); - ++it; - if( it == mPositions.end()) - break; - } - - // that's it + poResults.erase( poResults.begin(), poResults.end()); + + // quick check for positions outside the range + if( mPositions.size() == 0) + return; + if( maxDist < mPositions.front().mDistance) + return; + if( minDist > mPositions.back().mDistance) + return; + + // do a binary search for the minimal distance to start the iteration there + unsigned int index = (unsigned int)mPositions.size() / 2; + unsigned int binaryStepSize = (unsigned int)mPositions.size() / 4; + while( binaryStepSize > 1) + { + if( mPositions[index].mDistance < minDist) + index += binaryStepSize; + else + index -= binaryStepSize; + + binaryStepSize /= 2; + } + + // depending on the direction of the last step we need to single step a bit back or forth + // to find the actual beginning element of the range + while( index > 0 && mPositions[index].mDistance > minDist) + index--; + while( index < (mPositions.size() - 1) && mPositions[index].mDistance < minDist) + index++; + + // Mow start iterating from there until the first position lays outside of the distance range. + // Add all positions inside the distance range within the given radius to the result aray + std::vector<Entry>::const_iterator it = mPositions.begin() + index; + const float pSquared = pRadius*pRadius; + while( it->mDistance < maxDist) + { + if( (it->mPosition - pPosition).SquareLength() < pSquared) + poResults.push_back( it->mIndex); + ++it; + if( it == mPositions.end()) + break; + } + + // that's it } namespace { - // Binary, signed-integer representation of a single-precision floating-point value. - // IEEE 754 says: "If two floating-point numbers in the same format are ordered then they are - // ordered the same way when their bits are reinterpreted as sign-magnitude integers." - // This allows us to convert all floating-point numbers to signed integers of arbitrary size - // and then use them to work with ULPs (Units in the Last Place, for high-precision - // computations) or to compare them (integer comparisons are faster than floating-point - // comparisons on many platforms). - typedef signed int BinFloat; - - // -------------------------------------------------------------------------------------------- - // Converts the bit pattern of a floating-point number to its signed integer representation. - BinFloat ToBinary( const float & pValue) { - - // If this assertion fails, signed int is not big enough to store a float on your platform. - // Please correct the declaration of BinFloat a few lines above - but do it in a portable, - // #ifdef'd manner! - BOOST_STATIC_ASSERT( sizeof(BinFloat) >= sizeof(float)); - - #if defined( _MSC_VER) - // If this assertion fails, Visual C++ has finally moved to ILP64. This means that this - // code has just become legacy code! Find out the current value of _MSC_VER and modify - // the #if above so it evaluates false on the current and all upcoming VC versions (or - // on the current platform, if LP64 or LLP64 are still used on other platforms). - BOOST_STATIC_ASSERT( sizeof(BinFloat) == sizeof(float)); - - // This works best on Visual C++, but other compilers have their problems with it. - const BinFloat binValue = reinterpret_cast<BinFloat const &>(pValue); - #else - // On many compilers, reinterpreting a float address as an integer causes aliasing - // problems. This is an ugly but more or less safe way of doing it. - union { - float asFloat; - BinFloat asBin; - } conversion; - conversion.asBin = 0; // zero empty space in case sizeof(BinFloat) > sizeof(float) - conversion.asFloat = pValue; - const BinFloat binValue = conversion.asBin; - #endif - - // floating-point numbers are of sign-magnitude format, so find out what signed number - // representation we must convert negative values to. - // See http://en.wikipedia.org/wiki/Signed_number_representations. - - // Two's complement? - if( (-42 == (~42 + 1)) && (binValue & 0x80000000)) - return BinFloat(1 << (CHAR_BIT * sizeof(BinFloat) - 1)) - binValue; - // One's complement? - else if( (-42 == ~42) && (binValue & 0x80000000)) - return BinFloat(-0) - binValue; - // Sign-magnitude? - else if( (-42 == (42 | (-0))) && (binValue & 0x80000000)) // -0 = 1000... binary - return binValue; - else - return binValue; - } + // Binary, signed-integer representation of a single-precision floating-point value. + // IEEE 754 says: "If two floating-point numbers in the same format are ordered then they are + // ordered the same way when their bits are reinterpreted as sign-magnitude integers." + // This allows us to convert all floating-point numbers to signed integers of arbitrary size + // and then use them to work with ULPs (Units in the Last Place, for high-precision + // computations) or to compare them (integer comparisons are faster than floating-point + // comparisons on many platforms). + typedef signed int BinFloat; + + // -------------------------------------------------------------------------------------------- + // Converts the bit pattern of a floating-point number to its signed integer representation. + BinFloat ToBinary( const float & pValue) { + + // If this assertion fails, signed int is not big enough to store a float on your platform. + // Please correct the declaration of BinFloat a few lines above - but do it in a portable, + // #ifdef'd manner! + static_assert( sizeof(BinFloat) >= sizeof(float), "sizeof(BinFloat) >= sizeof(float)"); + + #if defined( _MSC_VER) + // If this assertion fails, Visual C++ has finally moved to ILP64. This means that this + // code has just become legacy code! Find out the current value of _MSC_VER and modify + // the #if above so it evaluates false on the current and all upcoming VC versions (or + // on the current platform, if LP64 or LLP64 are still used on other platforms). + static_assert( sizeof(BinFloat) == sizeof(float), "sizeof(BinFloat) == sizeof(float)"); + + // This works best on Visual C++, but other compilers have their problems with it. + const BinFloat binValue = reinterpret_cast<BinFloat const &>(pValue); + #else + // On many compilers, reinterpreting a float address as an integer causes aliasing + // problems. This is an ugly but more or less safe way of doing it. + union { + float asFloat; + BinFloat asBin; + } conversion; + conversion.asBin = 0; // zero empty space in case sizeof(BinFloat) > sizeof(float) + conversion.asFloat = pValue; + const BinFloat binValue = conversion.asBin; + #endif + + // floating-point numbers are of sign-magnitude format, so find out what signed number + // representation we must convert negative values to. + // See http://en.wikipedia.org/wiki/Signed_number_representations. + + // Two's complement? + if( (-42 == (~42 + 1)) && (binValue & 0x80000000)) + return BinFloat(1 << (CHAR_BIT * sizeof(BinFloat) - 1)) - binValue; + // One's complement? + else if( (-42 == ~42) && (binValue & 0x80000000)) + return BinFloat(-0) - binValue; + // Sign-magnitude? + else if( (-42 == (42 | (-0))) && (binValue & 0x80000000)) // -0 = 1000... binary + return binValue; + else + return binValue; + } } // namespace // ------------------------------------------------------------------------------------------------ -// Fills an array with indices of all positions indentical to the given position. In opposite to +// Fills an array with indices of all positions identical to the given position. In opposite to // FindPositions(), not an epsilon is used but a (very low) tolerance of four floating-point units. -void SpatialSort::FindIdenticalPositions( const aiVector3D& pPosition, - std::vector<unsigned int>& poResults) const +void SpatialSort::FindIdenticalPositions( const aiVector3D& pPosition, + std::vector<unsigned int>& poResults) const { - // Epsilons have a huge disadvantage: they are of constant precision, while floating-point - // values are of log2 precision. If you apply e=0.01 to 100, the epsilon is rather small, but - // if you apply it to 0.001, it is enormous. - - // The best way to overcome this is the unit in the last place (ULP). A precision of 2 ULPs - // tells us that a float does not differ more than 2 bits from the "real" value. ULPs are of - // logarithmic precision - around 1, they are 1÷(2^24) and around 10000, they are 0.00125. - - // For standard C math, we can assume a precision of 0.5 ULPs according to IEEE 754. The - // incoming vertex positions might have already been transformed, probably using rather - // inaccurate SSE instructions, so we assume a tolerance of 4 ULPs to safely identify - // identical vertex positions. - static const int toleranceInULPs = 4; - // An interesting point is that the inaccuracy grows linear with the number of operations: - // multiplying to numbers, each inaccurate to four ULPs, results in an inaccuracy of four ULPs - // plus 0.5 ULPs for the multiplication. - // To compute the distance to the plane, a dot product is needed - that is a multiplication and - // an addition on each number. - static const int distanceToleranceInULPs = toleranceInULPs + 1; - // The squared distance between two 3D vectors is computed the same way, but with an additional - // subtraction. - static const int distance3DToleranceInULPs = distanceToleranceInULPs + 1; - - // Convert the plane distance to its signed integer representation so the ULPs tolerance can be - // applied. For some reason, VC won't optimize two calls of the bit pattern conversion. - const BinFloat minDistBinary = ToBinary( pPosition * mPlaneNormal) - distanceToleranceInULPs; - const BinFloat maxDistBinary = minDistBinary + 2 * distanceToleranceInULPs; - - // clear the array in this strange fashion because a simple clear() would also deallocate + // Epsilons have a huge disadvantage: they are of constant precision, while floating-point + // values are of log2 precision. If you apply e=0.01 to 100, the epsilon is rather small, but + // if you apply it to 0.001, it is enormous. + + // The best way to overcome this is the unit in the last place (ULP). A precision of 2 ULPs + // tells us that a float does not differ more than 2 bits from the "real" value. ULPs are of + // logarithmic precision - around 1, they are 1�(2^24) and around 10000, they are 0.00125. + + // For standard C math, we can assume a precision of 0.5 ULPs according to IEEE 754. The + // incoming vertex positions might have already been transformed, probably using rather + // inaccurate SSE instructions, so we assume a tolerance of 4 ULPs to safely identify + // identical vertex positions. + static const int toleranceInULPs = 4; + // An interesting point is that the inaccuracy grows linear with the number of operations: + // multiplying to numbers, each inaccurate to four ULPs, results in an inaccuracy of four ULPs + // plus 0.5 ULPs for the multiplication. + // To compute the distance to the plane, a dot product is needed - that is a multiplication and + // an addition on each number. + static const int distanceToleranceInULPs = toleranceInULPs + 1; + // The squared distance between two 3D vectors is computed the same way, but with an additional + // subtraction. + static const int distance3DToleranceInULPs = distanceToleranceInULPs + 1; + + // Convert the plane distance to its signed integer representation so the ULPs tolerance can be + // applied. For some reason, VC won't optimize two calls of the bit pattern conversion. + const BinFloat minDistBinary = ToBinary( pPosition * mPlaneNormal) - distanceToleranceInULPs; + const BinFloat maxDistBinary = minDistBinary + 2 * distanceToleranceInULPs; + + // clear the array in this strange fashion because a simple clear() would also deallocate // the array which we want to avoid - poResults.erase( poResults.begin(), poResults.end()); - - // do a binary search for the minimal distance to start the iteration there - unsigned int index = (unsigned int)mPositions.size() / 2; - unsigned int binaryStepSize = (unsigned int)mPositions.size() / 4; - while( binaryStepSize > 1) - { - // Ugly, but conditional jumps are faster with integers than with floats - if( minDistBinary > ToBinary(mPositions[index].mDistance)) - index += binaryStepSize; - else - index -= binaryStepSize; - - binaryStepSize /= 2; - } - - // depending on the direction of the last step we need to single step a bit back or forth - // to find the actual beginning element of the range - while( index > 0 && minDistBinary < ToBinary(mPositions[index].mDistance) ) - index--; - while( index < (mPositions.size() - 1) && minDistBinary > ToBinary(mPositions[index].mDistance)) - index++; - - // Now start iterating from there until the first position lays outside of the distance range. - // Add all positions inside the distance range within the tolerance to the result aray - std::vector<Entry>::const_iterator it = mPositions.begin() + index; - while( ToBinary(it->mDistance) < maxDistBinary) - { - if( distance3DToleranceInULPs >= ToBinary((it->mPosition - pPosition).SquareLength())) - poResults.push_back(it->mIndex); - ++it; - if( it == mPositions.end()) - break; - } - - // that's it + poResults.erase( poResults.begin(), poResults.end()); + + // do a binary search for the minimal distance to start the iteration there + unsigned int index = (unsigned int)mPositions.size() / 2; + unsigned int binaryStepSize = (unsigned int)mPositions.size() / 4; + while( binaryStepSize > 1) + { + // Ugly, but conditional jumps are faster with integers than with floats + if( minDistBinary > ToBinary(mPositions[index].mDistance)) + index += binaryStepSize; + else + index -= binaryStepSize; + + binaryStepSize /= 2; + } + + // depending on the direction of the last step we need to single step a bit back or forth + // to find the actual beginning element of the range + while( index > 0 && minDistBinary < ToBinary(mPositions[index].mDistance) ) + index--; + while( index < (mPositions.size() - 1) && minDistBinary > ToBinary(mPositions[index].mDistance)) + index++; + + // Now start iterating from there until the first position lays outside of the distance range. + // Add all positions inside the distance range within the tolerance to the result aray + std::vector<Entry>::const_iterator it = mPositions.begin() + index; + while( ToBinary(it->mDistance) < maxDistBinary) + { + if( distance3DToleranceInULPs >= ToBinary((it->mPosition - pPosition).SquareLength())) + poResults.push_back(it->mIndex); + ++it; + if( it == mPositions.end()) + break; + } + + // that's it } // ------------------------------------------------------------------------------------------------ unsigned int SpatialSort::GenerateMappingTable(std::vector<unsigned int>& fill,float pRadius) const { - fill.resize(mPositions.size(),UINT_MAX); - float dist, maxDist; - - unsigned int t=0; - const float pSquared = pRadius*pRadius; - for (size_t i = 0; i < mPositions.size();) { - dist = mPositions[i].mPosition * mPlaneNormal; - maxDist = dist + pRadius; - - fill[mPositions[i].mIndex] = t; - const aiVector3D& oldpos = mPositions[i].mPosition; - for (++i; i < fill.size() && mPositions[i].mDistance < maxDist - && (mPositions[i].mPosition - oldpos).SquareLength() < pSquared; ++i) - { - fill[mPositions[i].mIndex] = t; - } - ++t; - } + fill.resize(mPositions.size(),UINT_MAX); + float dist, maxDist; + + unsigned int t=0; + const float pSquared = pRadius*pRadius; + for (size_t i = 0; i < mPositions.size();) { + dist = mPositions[i].mPosition * mPlaneNormal; + maxDist = dist + pRadius; + + fill[mPositions[i].mIndex] = t; + const aiVector3D& oldpos = mPositions[i].mPosition; + for (++i; i < fill.size() && mPositions[i].mDistance < maxDist + && (mPositions[i].mPosition - oldpos).SquareLength() < pSquared; ++i) + { + fill[mPositions[i].mIndex] = t; + } + ++t; + } #ifdef ASSIMP_BUILD_DEBUG - // debug invariant: mPositions[i].mIndex values must range from 0 to mPositions.size()-1 - for (size_t i = 0; i < fill.size(); ++i) { - ai_assert(fill[i]<mPositions.size()); - } + // debug invariant: mPositions[i].mIndex values must range from 0 to mPositions.size()-1 + for (size_t i = 0; i < fill.size(); ++i) { + ai_assert(fill[i]<mPositions.size()); + } #endif - return t; + return t; } |