1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/libs/assimp/SpatialSort.h	Sat Feb 01 19:58:19 2014 +0200
     1.3 @@ -0,0 +1,170 @@
     1.4 +/*
     1.5 +Open Asset Import Library (assimp)
     1.6 +----------------------------------------------------------------------
     1.7 +
     1.8 +Copyright (c) 2006-2012, assimp team
     1.9 +All rights reserved.
    1.10 +
    1.11 +Redistribution and use of this software in source and binary forms, 
    1.12 +with or without modification, are permitted provided that the 
    1.13 +following conditions are met:
    1.14 +
    1.15 +* Redistributions of source code must retain the above
    1.16 +  copyright notice, this list of conditions and the
    1.17 +  following disclaimer.
    1.18 +
    1.19 +* Redistributions in binary form must reproduce the above
    1.20 +  copyright notice, this list of conditions and the
    1.21 +  following disclaimer in the documentation and/or other
    1.22 +  materials provided with the distribution.
    1.23 +
    1.24 +* Neither the name of the assimp team, nor the names of its
    1.25 +  contributors may be used to endorse or promote products
    1.26 +  derived from this software without specific prior
    1.27 +  written permission of the assimp team.
    1.28 +
    1.29 +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
    1.30 +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
    1.31 +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
    1.32 +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 
    1.33 +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
    1.34 +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
    1.35 +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    1.36 +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
    1.37 +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
    1.38 +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
    1.39 +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    1.40 +
    1.41 +----------------------------------------------------------------------
    1.42 +*/
    1.43 +
    1.44 +/** Small helper classes to optimise finding vertizes close to a given location */
    1.45 +#ifndef AI_SPATIALSORT_H_INC
    1.46 +#define AI_SPATIALSORT_H_INC
    1.47 +
    1.48 +#include <vector>
    1.49 +#include "assimp/types.h"
    1.50 +
    1.51 +namespace Assimp
    1.52 +{
    1.53 +
    1.54 +// ------------------------------------------------------------------------------------------------
    1.55 +/** A little helper class to quickly find all vertices in the epsilon environment of a given
    1.56 + * position. Construct an instance with an array of positions. The class stores the given positions
    1.57 + * by their indices and sorts them by their distance to an arbitrary chosen plane.
    1.58 + * You can then query the instance for all vertices close to a given position in an average O(log n) 
    1.59 + * time, with O(n) worst case complexity when all vertices lay on the plane. The plane is chosen
    1.60 + * so that it avoids common planes in usual data sets. */
    1.61 +// ------------------------------------------------------------------------------------------------
    1.62 +class SpatialSort
    1.63 +{
    1.64 +public:
    1.65 +
    1.66 +	SpatialSort();
    1.67 +
    1.68 +	// ------------------------------------------------------------------------------------
    1.69 +	/** Constructs a spatially sorted representation from the given position array.
    1.70 +	 * Supply the positions in its layout in memory, the class will only refer to them
    1.71 +	 * by index.
    1.72 +	 * @param pPositions Pointer to the first position vector of the array.
    1.73 +	 * @param pNumPositions Number of vectors to expect in that array.
    1.74 +	 * @param pElementOffset Offset in bytes from the beginning of one vector in memory 
    1.75 +	 *   to the beginning of the next vector. */
    1.76 +	SpatialSort( const aiVector3D* pPositions, unsigned int pNumPositions, 
    1.77 +		unsigned int pElementOffset);
    1.78 +
    1.79 +	/** Destructor */
    1.80 +	~SpatialSort();
    1.81 +
    1.82 +public:
    1.83 +
    1.84 +	// ------------------------------------------------------------------------------------
    1.85 +	/** Sets the input data for the SpatialSort. This replaces existing data, if any.
    1.86 +	 *  The new data receives new indices in ascending order.
    1.87 +	 *
    1.88 +	 * @param pPositions Pointer to the first position vector of the array.
    1.89 +	 * @param pNumPositions Number of vectors to expect in that array.
    1.90 +	 * @param pElementOffset Offset in bytes from the beginning of one vector in memory 
    1.91 +	 *   to the beginning of the next vector. 
    1.92 +	 * @param pFinalize Specifies whether the SpatialSort's internal representation
    1.93 +	 *   is finalized after the new data has been added. Finalization is
    1.94 +	 *   required in order to use #FindPosition() or #GenerateMappingTable().
    1.95 +	 *   If you don't finalize yet, you can use #Append() to add data from
    1.96 +	 *   other sources.*/
    1.97 +	void Fill( const aiVector3D* pPositions, unsigned int pNumPositions, 
    1.98 +		unsigned int pElementOffset,
    1.99 +		bool pFinalize = true);
   1.100 +
   1.101 +
   1.102 +	// ------------------------------------------------------------------------------------
   1.103 +	/** Same as #Fill(), except the method appends to existing data in the #SpatialSort. */
   1.104 +	void Append( const aiVector3D* pPositions, unsigned int pNumPositions, 
   1.105 +		unsigned int pElementOffset,
   1.106 +		bool pFinalize = true);
   1.107 +
   1.108 +
   1.109 +	// ------------------------------------------------------------------------------------
   1.110 +	/** Finalize the spatial hash data structure. This can be useful after
   1.111 +	 *  multiple calls to #Append() with the pFinalize parameter set to false.
   1.112 +	 *  This is finally required before one of #FindPositions() and #GenerateMappingTable()
   1.113 +	 *  can be called to query the spatial sort.*/
   1.114 +	void Finalize();
   1.115 +
   1.116 +	// ------------------------------------------------------------------------------------
   1.117 +	/** Returns an iterator for all positions close to the given position.
   1.118 +	 * @param pPosition The position to look for vertices.
   1.119 +	 * @param pRadius Maximal distance from the position a vertex may have to be counted in.
   1.120 +	 * @param poResults The container to store the indices of the found positions. 
   1.121 +	 *   Will be emptied by the call so it may contain anything.
   1.122 +	 * @return An iterator to iterate over all vertices in the given area.*/
   1.123 +	void FindPositions( const aiVector3D& pPosition, float pRadius, 
   1.124 +		std::vector<unsigned int>& poResults) const;
   1.125 +
   1.126 +	// ------------------------------------------------------------------------------------
   1.127 +	/** Fills an array with indices of all positions indentical to the given position. In
   1.128 +	 *  opposite to FindPositions(), not an epsilon is used but a (very low) tolerance of
   1.129 +	 *  four floating-point units.
   1.130 +	 * @param pPosition The position to look for vertices.
   1.131 +	 * @param poResults The container to store the indices of the found positions. 
   1.132 +	 *   Will be emptied by the call so it may contain anything.*/
   1.133 +	void FindIdenticalPositions( const aiVector3D& pPosition,
   1.134 +		std::vector<unsigned int>& poResults) const;
   1.135 +
   1.136 +	// ------------------------------------------------------------------------------------
   1.137 +	/** Compute a table that maps each vertex ID referring to a spatially close
   1.138 +	 *  enough position to the same output ID. Output IDs are assigned in ascending order
   1.139 +	 *  from 0...n.
   1.140 +	 * @param fill Will be filled with numPositions entries. 
   1.141 +	 * @param pRadius Maximal distance from the position a vertex may have to
   1.142 +	 *   be counted in.
   1.143 +	 *  @return Number of unique vertices (n).  */
   1.144 +	unsigned int GenerateMappingTable(std::vector<unsigned int>& fill,
   1.145 +		float pRadius) const;
   1.146 +
   1.147 +protected:
   1.148 +	/** Normal of the sorting plane, normalized. The center is always at (0, 0, 0) */
   1.149 +	aiVector3D mPlaneNormal;
   1.150 +
   1.151 +	/** An entry in a spatially sorted position array. Consists of a vertex index,
   1.152 +	 * its position and its precalculated distance from the reference plane */
   1.153 +	struct Entry
   1.154 +	{
   1.155 +		unsigned int mIndex; ///< The vertex referred by this entry
   1.156 +		aiVector3D mPosition; ///< Position
   1.157 +		float mDistance; ///< Distance of this vertex to the sorting plane
   1.158 +
   1.159 +		Entry() { /** intentionally not initialized.*/ }
   1.160 +		Entry( unsigned int pIndex, const aiVector3D& pPosition, float pDistance) 
   1.161 +			: mIndex( pIndex), mPosition( pPosition), mDistance( pDistance)
   1.162 +		{ 	}
   1.163 +
   1.164 +		bool operator < (const Entry& e) const { return mDistance < e.mDistance; }
   1.165 +	};
   1.166 +
   1.167 +	// all positions, sorted by distance to the sorting plane
   1.168 +	std::vector<Entry> mPositions;
   1.169 +};
   1.170 +
   1.171 +} // end of namespace Assimp
   1.172 +
   1.173 +#endif // AI_SPATIALSORT_H_INC