vrshoot

annotate libs/assimp/SGSpatialSort.cpp @ 0:b2f14e535253

find changesets by author, revision, files, or words in the commit message
initial commit
author John Tsiombikas <nuclear@member.fsf.org>
date Sat, 01 Feb 2014 19:58:19 +0200
parents
children
rev   line source
nuclear@0 1 /*
nuclear@0 2 ---------------------------------------------------------------------------
nuclear@0 3 Open Asset Import Library (assimp)
nuclear@0 4 ---------------------------------------------------------------------------
nuclear@0 5
nuclear@0 6 Copyright (c) 2006-2012, assimp team
nuclear@0 7
nuclear@0 8 All rights reserved.
nuclear@0 9
nuclear@0 10 Redistribution and use of this software in source and binary forms,
nuclear@0 11 with or without modification, are permitted provided that the following
nuclear@0 12 conditions are met:
nuclear@0 13
nuclear@0 14 * Redistributions of source code must retain the above
nuclear@0 15 copyright notice, this list of conditions and the
nuclear@0 16 following disclaimer.
nuclear@0 17
nuclear@0 18 * Redistributions in binary form must reproduce the above
nuclear@0 19 copyright notice, this list of conditions and the
nuclear@0 20 following disclaimer in the documentation and/or other
nuclear@0 21 materials provided with the distribution.
nuclear@0 22
nuclear@0 23 * Neither the name of the assimp team, nor the names of its
nuclear@0 24 contributors may be used to endorse or promote products
nuclear@0 25 derived from this software without specific prior
nuclear@0 26 written permission of the assimp team.
nuclear@0 27
nuclear@0 28 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
nuclear@0 29 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
nuclear@0 30 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
nuclear@0 31 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
nuclear@0 32 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
nuclear@0 33 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
nuclear@0 34 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
nuclear@0 35 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
nuclear@0 36 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
nuclear@0 37 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
nuclear@0 38 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
nuclear@0 39 ---------------------------------------------------------------------------
nuclear@0 40 */
nuclear@0 41
nuclear@0 42 /** @file Implementation of the helper class to quickly find
nuclear@0 43 vertices close to a given position. Special implementation for
nuclear@0 44 the 3ds loader handling smooth groups correctly */
nuclear@0 45
nuclear@0 46 #include "AssimpPCH.h"
nuclear@0 47 #include "SGSpatialSort.h"
nuclear@0 48
nuclear@0 49 using namespace Assimp;
nuclear@0 50
nuclear@0 51
nuclear@0 52 // ------------------------------------------------------------------------------------------------
nuclear@0 53 SGSpatialSort::SGSpatialSort()
nuclear@0 54 {
nuclear@0 55 // define the reference plane. We choose some arbitrary vector away from all basic axises
nuclear@0 56 // in the hope that no model spreads all its vertices along this plane.
nuclear@0 57 mPlaneNormal.Set( 0.8523f, 0.34321f, 0.5736f);
nuclear@0 58 mPlaneNormal.Normalize();
nuclear@0 59 }
nuclear@0 60 // ------------------------------------------------------------------------------------------------
nuclear@0 61 // Destructor
nuclear@0 62 SGSpatialSort::~SGSpatialSort()
nuclear@0 63 {
nuclear@0 64 // nothing to do here, everything destructs automatically
nuclear@0 65 }
nuclear@0 66 // ------------------------------------------------------------------------------------------------
nuclear@0 67 void SGSpatialSort::Add(const aiVector3D& vPosition, unsigned int index,
nuclear@0 68 unsigned int smoothingGroup)
nuclear@0 69 {
nuclear@0 70 // store position by index and distance
nuclear@0 71 float distance = vPosition * mPlaneNormal;
nuclear@0 72 mPositions.push_back( Entry( index, vPosition,
nuclear@0 73 distance, smoothingGroup));
nuclear@0 74 }
nuclear@0 75 // ------------------------------------------------------------------------------------------------
nuclear@0 76 void SGSpatialSort::Prepare()
nuclear@0 77 {
nuclear@0 78 // now sort the array ascending by distance.
nuclear@0 79 std::sort( this->mPositions.begin(), this->mPositions.end());
nuclear@0 80 }
nuclear@0 81 // ------------------------------------------------------------------------------------------------
nuclear@0 82 // Returns an iterator for all positions close to the given position.
nuclear@0 83 void SGSpatialSort::FindPositions( const aiVector3D& pPosition,
nuclear@0 84 uint32_t pSG,
nuclear@0 85 float pRadius,
nuclear@0 86 std::vector<unsigned int>& poResults,
nuclear@0 87 bool exactMatch /*= false*/) const
nuclear@0 88 {
nuclear@0 89 float dist = pPosition * mPlaneNormal;
nuclear@0 90 float minDist = dist - pRadius, maxDist = dist + pRadius;
nuclear@0 91
nuclear@0 92 // clear the array in this strange fashion because a simple clear() would also deallocate
nuclear@0 93 // the array which we want to avoid
nuclear@0 94 poResults.erase( poResults.begin(), poResults.end());
nuclear@0 95
nuclear@0 96 // quick check for positions outside the range
nuclear@0 97 if( mPositions.size() == 0)
nuclear@0 98 return;
nuclear@0 99 if( maxDist < mPositions.front().mDistance)
nuclear@0 100 return;
nuclear@0 101 if( minDist > mPositions.back().mDistance)
nuclear@0 102 return;
nuclear@0 103
nuclear@0 104 // do a binary search for the minimal distance to start the iteration there
nuclear@0 105 unsigned int index = (unsigned int)mPositions.size() / 2;
nuclear@0 106 unsigned int binaryStepSize = (unsigned int)mPositions.size() / 4;
nuclear@0 107 while( binaryStepSize > 1)
nuclear@0 108 {
nuclear@0 109 if( mPositions[index].mDistance < minDist)
nuclear@0 110 index += binaryStepSize;
nuclear@0 111 else
nuclear@0 112 index -= binaryStepSize;
nuclear@0 113
nuclear@0 114 binaryStepSize /= 2;
nuclear@0 115 }
nuclear@0 116
nuclear@0 117 // depending on the direction of the last step we need to single step a bit back or forth
nuclear@0 118 // to find the actual beginning element of the range
nuclear@0 119 while( index > 0 && mPositions[index].mDistance > minDist)
nuclear@0 120 index--;
nuclear@0 121 while( index < (mPositions.size() - 1) && mPositions[index].mDistance < minDist)
nuclear@0 122 index++;
nuclear@0 123
nuclear@0 124 // Mow start iterating from there until the first position lays outside of the distance range.
nuclear@0 125 // Add all positions inside the distance range within the given radius to the result aray
nuclear@0 126
nuclear@0 127 float squareEpsilon = pRadius * pRadius;
nuclear@0 128 std::vector<Entry>::const_iterator it = mPositions.begin() + index;
nuclear@0 129 std::vector<Entry>::const_iterator end = mPositions.end();
nuclear@0 130
nuclear@0 131 if (exactMatch)
nuclear@0 132 {
nuclear@0 133 while( it->mDistance < maxDist)
nuclear@0 134 {
nuclear@0 135 if((it->mPosition - pPosition).SquareLength() < squareEpsilon && it->mSmoothGroups == pSG)
nuclear@0 136 {
nuclear@0 137 poResults.push_back( it->mIndex);
nuclear@0 138 }
nuclear@0 139 ++it;
nuclear@0 140 if( end == it )break;
nuclear@0 141 }
nuclear@0 142 }
nuclear@0 143 else
nuclear@0 144 {
nuclear@0 145 // if the given smoothing group is 0, we'll return all surrounding vertices
nuclear@0 146 if (!pSG)
nuclear@0 147 {
nuclear@0 148 while( it->mDistance < maxDist)
nuclear@0 149 {
nuclear@0 150 if((it->mPosition - pPosition).SquareLength() < squareEpsilon)
nuclear@0 151 poResults.push_back( it->mIndex);
nuclear@0 152 ++it;
nuclear@0 153 if( end == it)break;
nuclear@0 154 }
nuclear@0 155 }
nuclear@0 156 else while( it->mDistance < maxDist)
nuclear@0 157 {
nuclear@0 158 if((it->mPosition - pPosition).SquareLength() < squareEpsilon &&
nuclear@0 159 (it->mSmoothGroups & pSG || !it->mSmoothGroups))
nuclear@0 160 {
nuclear@0 161 poResults.push_back( it->mIndex);
nuclear@0 162 }
nuclear@0 163 ++it;
nuclear@0 164 if( end == it)break;
nuclear@0 165 }
nuclear@0 166 }
nuclear@0 167 }
nuclear@0 168
nuclear@0 169