include/assimp/SGSpatialSort.h

0001 /*
0002 Open Asset Import Library (assimp)
0003 ----------------------------------------------------------------------
0004
0005 Copyright (c) 2006-2024, assimp team
0006
0007 All rights reserved.
0008
0009 Redistribution and use of this software in source and binary forms,
0010 with or without modification, are permitted provided that the
0011 following conditions are met:
0012
0013 * Redistributions of source code must retain the above
0014   copyright notice, this list of conditions and the
0015   following disclaimer.
0016
0017 * Redistributions in binary form must reproduce the above
0018   copyright notice, this list of conditions and the
0019   following disclaimer in the documentation and/or other
0020   materials provided with the distribution.
0021
0022 * Neither the name of the assimp team, nor the names of its
0023   contributors may be used to endorse or promote products
0024   derived from this software without specific prior
0025   written permission of the assimp team.
0026
0027 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
0028 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
0029 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
0030 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
0031 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
0032 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
0033 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
0034 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
0035 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
0036 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
0037 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
0038
0039 ----------------------------------------------------------------------
0040 */
0041
0042 /** Small helper classes to optimize finding vertices close to a given location
0043  */
0044 #pragma once
0045 #ifndef AI_D3DSSPATIALSORT_H_INC
0046 #define AI_D3DSSPATIALSORT_H_INC
0047
0048 #ifdef __GNUC__
0049 #   pragma GCC system_header
0050 #endif
0051
0052 #include <assimp/types.h>
0053 #include <vector>
0054 #include <stdint.h>
0055
0056 namespace Assimp    {
0057
0058 // ----------------------------------------------------------------------------------
0059 /** Specialized version of SpatialSort to support smoothing groups
0060  *  This is used in by the 3DS, ASE and LWO loaders. 3DS and ASE share their
0061  *  normal computation code in SmoothingGroups.inl, the LWO loader has its own
0062  *  implementation to handle all details of its file format correctly.
0063  */
0064 // ----------------------------------------------------------------------------------
0065 class ASSIMP_API SGSpatialSort {
0066 public:
0067     SGSpatialSort();
0068
0069     // -------------------------------------------------------------------
0070     /** Construction from a given face array, handling smoothing groups
0071      *  properly
0072      */
0073     explicit SGSpatialSort(const std::vector<aiVector3D>& vPositions);
0074
0075     // -------------------------------------------------------------------
0076     /** Add a vertex to the spatial sort
0077      * @param vPosition Vertex position to be added
0078      * @param index Index of the vrtex
0079      * @param smoothingGroup SmoothingGroup for this vertex
0080      */
0081     void Add(const aiVector3D& vPosition, unsigned int index,
0082         unsigned int smoothingGroup);
0083
0084     // -------------------------------------------------------------------
0085     /** Prepare the spatial sorter for use. This step runs in O(logn)
0086      */
0087     void Prepare();
0088
0089     /** Destructor */
0090     ~SGSpatialSort() = default;
0091
0092     // -------------------------------------------------------------------
0093     /** Returns an iterator for all positions close to the given position.
0094      * @param pPosition The position to look for vertices.
0095      * @param pSG Only included vertices with at least one shared smooth group
0096      * @param pRadius Maximal distance from the position a vertex may have
0097      *   to be counted in.
0098      * @param poResults The container to store the indices of the found
0099      *   positions. Will be emptied by the call so it may contain anything.
0100      * @param exactMatch Specifies whether smoothing groups are bit masks
0101      *   (false) or integral values (true). In the latter case, a vertex
0102      *   cannot belong to more than one smoothing group.
0103      * @return An iterator to iterate over all vertices in the given area.
0104      */
0105     // -------------------------------------------------------------------
0106     void FindPositions( const aiVector3D& pPosition, uint32_t pSG,
0107         float pRadius, std::vector<unsigned int>& poResults,
0108         bool exactMatch = false) const;
0109
0110 protected:
0111     /** Normal of the sorting plane, normalized. The center is always at (0, 0, 0) */
0112     aiVector3D mPlaneNormal;
0113
0114     // -------------------------------------------------------------------
0115     /** An entry in a spatially sorted position array. Consists of a
0116      *  vertex index, its position and its pre-calculated distance from
0117      *  the reference plane */
0118     // -------------------------------------------------------------------
0119     struct Entry {
0120         unsigned int mIndex;    ///< The vertex referred by this entry
0121         aiVector3D mPosition;   ///< Position
0122         uint32_t mSmoothGroups;
0123         float mDistance;        ///< Distance of this vertex to the sorting plane
0124
0125         Entry() AI_NO_EXCEPT
0126         : mIndex(0)
0127         , mPosition()
0128         , mSmoothGroups(0)
0129         , mDistance(0.0f) {
0130             // empty
0131         }
0132
0133         Entry( unsigned int pIndex, const aiVector3D& pPosition, float pDistance,uint32_t pSG)
0134         : mIndex( pIndex)
0135         , mPosition( pPosition)
0136         , mSmoothGroups(pSG)
0137         , mDistance( pDistance) {
0138             // empty
0139         }
0140
0141         bool operator < (const Entry& e) const {
0142             return mDistance < e.mDistance;
0143         }
0144     };
0145
0146     // all positions, sorted by distance to the sorting plane
0147     std::vector<Entry> mPositions;
0148 };
0149
0150 } // end of namespace Assimp
0151
0152 #endif // AI_SPATIALSORT_H_INC