nuclear@0: /*
nuclear@0: Open Asset Import Library (assimp)
nuclear@0: ----------------------------------------------------------------------
nuclear@0: 
nuclear@0: Copyright (c) 2006-2012, assimp team
nuclear@0: All rights reserved.
nuclear@0: 
nuclear@0: Redistribution and use of this software in source and binary forms, 
nuclear@0: with or without modification, are permitted provided that the 
nuclear@0: following conditions are met:
nuclear@0: 
nuclear@0: * Redistributions of source code must retain the above
nuclear@0:   copyright notice, this list of conditions and the
nuclear@0:   following disclaimer.
nuclear@0: 
nuclear@0: * Redistributions in binary form must reproduce the above
nuclear@0:   copyright notice, this list of conditions and the
nuclear@0:   following disclaimer in the documentation and/or other
nuclear@0:   materials provided with the distribution.
nuclear@0: 
nuclear@0: * Neither the name of the assimp team, nor the names of its
nuclear@0:   contributors may be used to endorse or promote products
nuclear@0:   derived from this software without specific prior
nuclear@0:   written permission of the assimp team.
nuclear@0: 
nuclear@0: THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
nuclear@0: "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
nuclear@0: LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
nuclear@0: A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 
nuclear@0: OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
nuclear@0: SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
nuclear@0: LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
nuclear@0: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
nuclear@0: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
nuclear@0: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
nuclear@0: OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
nuclear@0: 
nuclear@0: ----------------------------------------------------------------------
nuclear@0: */
nuclear@0: 
nuclear@0: /** Small helper classes to optimise finding vertizes close to a given location
nuclear@0:  */
nuclear@0: #ifndef AI_D3DSSPATIALSORT_H_INC
nuclear@0: #define AI_D3DSSPATIALSORT_H_INC
nuclear@0: 
nuclear@0: #include <vector>
nuclear@0: #include "assimp/types.h"
nuclear@0: 
nuclear@0: namespace Assimp	{
nuclear@0: 
nuclear@0: // ----------------------------------------------------------------------------------
nuclear@0: /** Specialized version of SpatialSort to support smoothing groups
nuclear@0:  *  This is used in by the 3DS, ASE and LWO loaders. 3DS and ASE share their 
nuclear@0:  *  normal computation code in SmoothingGroups.inl, the LWO loader has its own
nuclear@0:  *  implementation to handle all details of its file format correctly.
nuclear@0:  */
nuclear@0: // ----------------------------------------------------------------------------------
nuclear@0: class SGSpatialSort
nuclear@0: {
nuclear@0: public:
nuclear@0: 
nuclear@0: 	SGSpatialSort();
nuclear@0: 
nuclear@0: 	// -------------------------------------------------------------------
nuclear@0: 	/** Construction from a given face array, handling smoothing groups
nuclear@0: 	 *  properly
nuclear@0: 	 */
nuclear@0: 	SGSpatialSort(const std::vector<aiVector3D>& vPositions);
nuclear@0: 
nuclear@0: 	// -------------------------------------------------------------------
nuclear@0: 	/** Add a vertex to the spatial sort
nuclear@0: 	 * @param vPosition Vertex position to be added
nuclear@0: 	 * @param index Index of the vrtex
nuclear@0: 	 * @param smoothingGroup SmoothingGroup for this vertex
nuclear@0: 	 */
nuclear@0: 	void Add(const aiVector3D& vPosition, unsigned int index,
nuclear@0: 		unsigned int smoothingGroup);
nuclear@0: 
nuclear@0: 	// -------------------------------------------------------------------
nuclear@0: 	/** Prepare the spatial sorter for use. This step runs in O(logn)
nuclear@0: 	 */
nuclear@0: 	void Prepare();
nuclear@0: 
nuclear@0: 	/** Destructor */
nuclear@0: 	~SGSpatialSort();
nuclear@0: 
nuclear@0: 	// -------------------------------------------------------------------
nuclear@0: 	/** Returns an iterator for all positions close to the given position.
nuclear@0: 	 * @param pPosition The position to look for vertices.
nuclear@0: 	 * @param pSG Only included vertices with at least one shared smooth group
nuclear@0: 	 * @param pRadius Maximal distance from the position a vertex may have
nuclear@0: 	 *   to be counted in.
nuclear@0: 	 * @param poResults The container to store the indices of the found
nuclear@0: 	 *   positions. Will be emptied by the call so it may contain anything.
nuclear@0: 	 * @param exactMatch Specifies whether smoothing groups are bit masks 
nuclear@0: 	 *   (false) or integral values (true). In the latter case, a vertex
nuclear@0: 	 *   cannot belong to more than one smoothing group.
nuclear@0: 	 * @return An iterator to iterate over all vertices in the given area.
nuclear@0: 	 */
nuclear@0: 	// -------------------------------------------------------------------
nuclear@0: 	void FindPositions( const aiVector3D& pPosition, uint32_t pSG,
nuclear@0: 		float pRadius, std::vector<unsigned int>& poResults, 
nuclear@0: 		bool exactMatch = false) const;
nuclear@0: 
nuclear@0: protected:
nuclear@0: 	/** Normal of the sorting plane, normalized. The center is always at (0, 0, 0) */
nuclear@0: 	aiVector3D mPlaneNormal;
nuclear@0: 
nuclear@0: 	// -------------------------------------------------------------------
nuclear@0: 	/** An entry in a spatially sorted position array. Consists of a 
nuclear@0: 	 *  vertex index, its position and its precalculated distance from
nuclear@0: 	 *  the reference plane */
nuclear@0: 	// -------------------------------------------------------------------
nuclear@0: 	struct Entry
nuclear@0: 	{
nuclear@0: 		unsigned int mIndex;	///< The vertex referred by this entry
nuclear@0: 		aiVector3D mPosition;	///< Position
nuclear@0: 		uint32_t mSmoothGroups;
nuclear@0: 		float mDistance;		///< Distance of this vertex to the sorting plane
nuclear@0: 
nuclear@0: 		Entry() { /** intentionally not initialized.*/ }
nuclear@0: 		Entry( unsigned int pIndex, const aiVector3D& pPosition, float pDistance,uint32_t pSG) 
nuclear@0: 			: 
nuclear@0: 			mIndex( pIndex),
nuclear@0: 			mPosition( pPosition),
nuclear@0: 			mSmoothGroups (pSG),
nuclear@0: 			mDistance( pDistance)
nuclear@0: 			{ 	}
nuclear@0: 
nuclear@0: 		bool operator < (const Entry& e) const { return mDistance < e.mDistance; }
nuclear@0: 	};
nuclear@0: 
nuclear@0: 	// all positions, sorted by distance to the sorting plane
nuclear@0: 	std::vector<Entry> mPositions;
nuclear@0: };
nuclear@0: 
nuclear@0: } // end of namespace Assimp
nuclear@0: 
nuclear@0: #endif // AI_SPATIALSORT_H_INC