vrshoot

annotate libs/assimp/SpatialSort.h @ 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 Open Asset Import Library (assimp)
nuclear@0 3 ----------------------------------------------------------------------
nuclear@0 4
nuclear@0 5 Copyright (c) 2006-2012, assimp team
nuclear@0 6 All rights reserved.
nuclear@0 7
nuclear@0 8 Redistribution and use of this software in source and binary forms,
nuclear@0 9 with or without modification, are permitted provided that the
nuclear@0 10 following conditions are met:
nuclear@0 11
nuclear@0 12 * Redistributions of source code must retain the above
nuclear@0 13 copyright notice, this list of conditions and the
nuclear@0 14 following disclaimer.
nuclear@0 15
nuclear@0 16 * Redistributions in binary form must reproduce the above
nuclear@0 17 copyright notice, this list of conditions and the
nuclear@0 18 following disclaimer in the documentation and/or other
nuclear@0 19 materials provided with the distribution.
nuclear@0 20
nuclear@0 21 * Neither the name of the assimp team, nor the names of its
nuclear@0 22 contributors may be used to endorse or promote products
nuclear@0 23 derived from this software without specific prior
nuclear@0 24 written permission of the assimp team.
nuclear@0 25
nuclear@0 26 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
nuclear@0 27 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
nuclear@0 28 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
nuclear@0 29 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
nuclear@0 30 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
nuclear@0 31 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
nuclear@0 32 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
nuclear@0 33 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
nuclear@0 34 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
nuclear@0 35 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
nuclear@0 36 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
nuclear@0 37
nuclear@0 38 ----------------------------------------------------------------------
nuclear@0 39 */
nuclear@0 40
nuclear@0 41 /** Small helper classes to optimise finding vertizes close to a given location */
nuclear@0 42 #ifndef AI_SPATIALSORT_H_INC
nuclear@0 43 #define AI_SPATIALSORT_H_INC
nuclear@0 44
nuclear@0 45 #include <vector>
nuclear@0 46 #include "assimp/types.h"
nuclear@0 47
nuclear@0 48 namespace Assimp
nuclear@0 49 {
nuclear@0 50
nuclear@0 51 // ------------------------------------------------------------------------------------------------
nuclear@0 52 /** A little helper class to quickly find all vertices in the epsilon environment of a given
nuclear@0 53 * position. Construct an instance with an array of positions. The class stores the given positions
nuclear@0 54 * by their indices and sorts them by their distance to an arbitrary chosen plane.
nuclear@0 55 * You can then query the instance for all vertices close to a given position in an average O(log n)
nuclear@0 56 * time, with O(n) worst case complexity when all vertices lay on the plane. The plane is chosen
nuclear@0 57 * so that it avoids common planes in usual data sets. */
nuclear@0 58 // ------------------------------------------------------------------------------------------------
nuclear@0 59 class SpatialSort
nuclear@0 60 {
nuclear@0 61 public:
nuclear@0 62
nuclear@0 63 SpatialSort();
nuclear@0 64
nuclear@0 65 // ------------------------------------------------------------------------------------
nuclear@0 66 /** Constructs a spatially sorted representation from the given position array.
nuclear@0 67 * Supply the positions in its layout in memory, the class will only refer to them
nuclear@0 68 * by index.
nuclear@0 69 * @param pPositions Pointer to the first position vector of the array.
nuclear@0 70 * @param pNumPositions Number of vectors to expect in that array.
nuclear@0 71 * @param pElementOffset Offset in bytes from the beginning of one vector in memory
nuclear@0 72 * to the beginning of the next vector. */
nuclear@0 73 SpatialSort( const aiVector3D* pPositions, unsigned int pNumPositions,
nuclear@0 74 unsigned int pElementOffset);
nuclear@0 75
nuclear@0 76 /** Destructor */
nuclear@0 77 ~SpatialSort();
nuclear@0 78
nuclear@0 79 public:
nuclear@0 80
nuclear@0 81 // ------------------------------------------------------------------------------------
nuclear@0 82 /** Sets the input data for the SpatialSort. This replaces existing data, if any.
nuclear@0 83 * The new data receives new indices in ascending order.
nuclear@0 84 *
nuclear@0 85 * @param pPositions Pointer to the first position vector of the array.
nuclear@0 86 * @param pNumPositions Number of vectors to expect in that array.
nuclear@0 87 * @param pElementOffset Offset in bytes from the beginning of one vector in memory
nuclear@0 88 * to the beginning of the next vector.
nuclear@0 89 * @param pFinalize Specifies whether the SpatialSort's internal representation
nuclear@0 90 * is finalized after the new data has been added. Finalization is
nuclear@0 91 * required in order to use #FindPosition() or #GenerateMappingTable().
nuclear@0 92 * If you don't finalize yet, you can use #Append() to add data from
nuclear@0 93 * other sources.*/
nuclear@0 94 void Fill( const aiVector3D* pPositions, unsigned int pNumPositions,
nuclear@0 95 unsigned int pElementOffset,
nuclear@0 96 bool pFinalize = true);
nuclear@0 97
nuclear@0 98
nuclear@0 99 // ------------------------------------------------------------------------------------
nuclear@0 100 /** Same as #Fill(), except the method appends to existing data in the #SpatialSort. */
nuclear@0 101 void Append( const aiVector3D* pPositions, unsigned int pNumPositions,
nuclear@0 102 unsigned int pElementOffset,
nuclear@0 103 bool pFinalize = true);
nuclear@0 104
nuclear@0 105
nuclear@0 106 // ------------------------------------------------------------------------------------
nuclear@0 107 /** Finalize the spatial hash data structure. This can be useful after
nuclear@0 108 * multiple calls to #Append() with the pFinalize parameter set to false.
nuclear@0 109 * This is finally required before one of #FindPositions() and #GenerateMappingTable()
nuclear@0 110 * can be called to query the spatial sort.*/
nuclear@0 111 void Finalize();
nuclear@0 112
nuclear@0 113 // ------------------------------------------------------------------------------------
nuclear@0 114 /** Returns an iterator for all positions close to the given position.
nuclear@0 115 * @param pPosition The position to look for vertices.
nuclear@0 116 * @param pRadius Maximal distance from the position a vertex may have to be counted in.
nuclear@0 117 * @param poResults The container to store the indices of the found positions.
nuclear@0 118 * Will be emptied by the call so it may contain anything.
nuclear@0 119 * @return An iterator to iterate over all vertices in the given area.*/
nuclear@0 120 void FindPositions( const aiVector3D& pPosition, float pRadius,
nuclear@0 121 std::vector<unsigned int>& poResults) const;
nuclear@0 122
nuclear@0 123 // ------------------------------------------------------------------------------------
nuclear@0 124 /** Fills an array with indices of all positions indentical to the given position. In
nuclear@0 125 * opposite to FindPositions(), not an epsilon is used but a (very low) tolerance of
nuclear@0 126 * four floating-point units.
nuclear@0 127 * @param pPosition The position to look for vertices.
nuclear@0 128 * @param poResults The container to store the indices of the found positions.
nuclear@0 129 * Will be emptied by the call so it may contain anything.*/
nuclear@0 130 void FindIdenticalPositions( const aiVector3D& pPosition,
nuclear@0 131 std::vector<unsigned int>& poResults) const;
nuclear@0 132
nuclear@0 133 // ------------------------------------------------------------------------------------
nuclear@0 134 /** Compute a table that maps each vertex ID referring to a spatially close
nuclear@0 135 * enough position to the same output ID. Output IDs are assigned in ascending order
nuclear@0 136 * from 0...n.
nuclear@0 137 * @param fill Will be filled with numPositions entries.
nuclear@0 138 * @param pRadius Maximal distance from the position a vertex may have to
nuclear@0 139 * be counted in.
nuclear@0 140 * @return Number of unique vertices (n). */
nuclear@0 141 unsigned int GenerateMappingTable(std::vector<unsigned int>& fill,
nuclear@0 142 float pRadius) const;
nuclear@0 143
nuclear@0 144 protected:
nuclear@0 145 /** Normal of the sorting plane, normalized. The center is always at (0, 0, 0) */
nuclear@0 146 aiVector3D mPlaneNormal;
nuclear@0 147
nuclear@0 148 /** An entry in a spatially sorted position array. Consists of a vertex index,
nuclear@0 149 * its position and its precalculated distance from the reference plane */
nuclear@0 150 struct Entry
nuclear@0 151 {
nuclear@0 152 unsigned int mIndex; ///< The vertex referred by this entry
nuclear@0 153 aiVector3D mPosition; ///< Position
nuclear@0 154 float mDistance; ///< Distance of this vertex to the sorting plane
nuclear@0 155
nuclear@0 156 Entry() { /** intentionally not initialized.*/ }
nuclear@0 157 Entry( unsigned int pIndex, const aiVector3D& pPosition, float pDistance)
nuclear@0 158 : mIndex( pIndex), mPosition( pPosition), mDistance( pDistance)
nuclear@0 159 { }
nuclear@0 160
nuclear@0 161 bool operator < (const Entry& e) const { return mDistance < e.mDistance; }
nuclear@0 162 };
nuclear@0 163
nuclear@0 164 // all positions, sorted by distance to the sorting plane
nuclear@0 165 std::vector<Entry> mPositions;
nuclear@0 166 };
nuclear@0 167
nuclear@0 168 } // end of namespace Assimp
nuclear@0 169
nuclear@0 170 #endif // AI_SPATIALSORT_H_INC