1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/libs/assimp/SGSpatialSort.h	Sat Feb 01 19:58:19 2014 +0200
     1.3 @@ -0,0 +1,139 @@
     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 + */
    1.46 +#ifndef AI_D3DSSPATIALSORT_H_INC
    1.47 +#define AI_D3DSSPATIALSORT_H_INC
    1.48 +
    1.49 +#include <vector>
    1.50 +#include "assimp/types.h"
    1.51 +
    1.52 +namespace Assimp	{
    1.53 +
    1.54 +// ----------------------------------------------------------------------------------
    1.55 +/** Specialized version of SpatialSort to support smoothing groups
    1.56 + *  This is used in by the 3DS, ASE and LWO loaders. 3DS and ASE share their 
    1.57 + *  normal computation code in SmoothingGroups.inl, the LWO loader has its own
    1.58 + *  implementation to handle all details of its file format correctly.
    1.59 + */
    1.60 +// ----------------------------------------------------------------------------------
    1.61 +class SGSpatialSort
    1.62 +{
    1.63 +public:
    1.64 +
    1.65 +	SGSpatialSort();
    1.66 +
    1.67 +	// -------------------------------------------------------------------
    1.68 +	/** Construction from a given face array, handling smoothing groups
    1.69 +	 *  properly
    1.70 +	 */
    1.71 +	SGSpatialSort(const std::vector<aiVector3D>& vPositions);
    1.72 +
    1.73 +	// -------------------------------------------------------------------
    1.74 +	/** Add a vertex to the spatial sort
    1.75 +	 * @param vPosition Vertex position to be added
    1.76 +	 * @param index Index of the vrtex
    1.77 +	 * @param smoothingGroup SmoothingGroup for this vertex
    1.78 +	 */
    1.79 +	void Add(const aiVector3D& vPosition, unsigned int index,
    1.80 +		unsigned int smoothingGroup);
    1.81 +
    1.82 +	// -------------------------------------------------------------------
    1.83 +	/** Prepare the spatial sorter for use. This step runs in O(logn)
    1.84 +	 */
    1.85 +	void Prepare();
    1.86 +
    1.87 +	/** Destructor */
    1.88 +	~SGSpatialSort();
    1.89 +
    1.90 +	// -------------------------------------------------------------------
    1.91 +	/** Returns an iterator for all positions close to the given position.
    1.92 +	 * @param pPosition The position to look for vertices.
    1.93 +	 * @param pSG Only included vertices with at least one shared smooth group
    1.94 +	 * @param pRadius Maximal distance from the position a vertex may have
    1.95 +	 *   to be counted in.
    1.96 +	 * @param poResults The container to store the indices of the found
    1.97 +	 *   positions. Will be emptied by the call so it may contain anything.
    1.98 +	 * @param exactMatch Specifies whether smoothing groups are bit masks 
    1.99 +	 *   (false) or integral values (true). In the latter case, a vertex
   1.100 +	 *   cannot belong to more than one smoothing group.
   1.101 +	 * @return An iterator to iterate over all vertices in the given area.
   1.102 +	 */
   1.103 +	// -------------------------------------------------------------------
   1.104 +	void FindPositions( const aiVector3D& pPosition, uint32_t pSG,
   1.105 +		float pRadius, std::vector<unsigned int>& poResults, 
   1.106 +		bool exactMatch = false) const;
   1.107 +
   1.108 +protected:
   1.109 +	/** Normal of the sorting plane, normalized. The center is always at (0, 0, 0) */
   1.110 +	aiVector3D mPlaneNormal;
   1.111 +
   1.112 +	// -------------------------------------------------------------------
   1.113 +	/** An entry in a spatially sorted position array. Consists of a 
   1.114 +	 *  vertex index, its position and its precalculated distance from
   1.115 +	 *  the reference plane */
   1.116 +	// -------------------------------------------------------------------
   1.117 +	struct Entry
   1.118 +	{
   1.119 +		unsigned int mIndex;	///< The vertex referred by this entry
   1.120 +		aiVector3D mPosition;	///< Position
   1.121 +		uint32_t mSmoothGroups;
   1.122 +		float mDistance;		///< Distance of this vertex to the sorting plane
   1.123 +
   1.124 +		Entry() { /** intentionally not initialized.*/ }
   1.125 +		Entry( unsigned int pIndex, const aiVector3D& pPosition, float pDistance,uint32_t pSG) 
   1.126 +			: 
   1.127 +			mIndex( pIndex),
   1.128 +			mPosition( pPosition),
   1.129 +			mSmoothGroups (pSG),
   1.130 +			mDistance( pDistance)
   1.131 +			{ 	}
   1.132 +
   1.133 +		bool operator < (const Entry& e) const { return mDistance < e.mDistance; }
   1.134 +	};
   1.135 +
   1.136 +	// all positions, sorted by distance to the sorting plane
   1.137 +	std::vector<Entry> mPositions;
   1.138 +};
   1.139 +
   1.140 +} // end of namespace Assimp
   1.141 +
   1.142 +#endif // AI_SPATIALSORT_H_INC