VectorSet.h (8683B)
1 /* 2 =========================================================================== 3 4 Doom 3 BFG Edition GPL Source Code 5 Copyright (C) 1993-2012 id Software LLC, a ZeniMax Media company. 6 7 This file is part of the Doom 3 BFG Edition GPL Source Code ("Doom 3 BFG Edition Source Code"). 8 9 Doom 3 BFG Edition Source Code is free software: you can redistribute it and/or modify 10 it under the terms of the GNU General Public License as published by 11 the Free Software Foundation, either version 3 of the License, or 12 (at your option) any later version. 13 14 Doom 3 BFG Edition Source Code is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 GNU General Public License for more details. 18 19 You should have received a copy of the GNU General Public License 20 along with Doom 3 BFG Edition Source Code. If not, see <http://www.gnu.org/licenses/>. 21 22 In addition, the Doom 3 BFG Edition Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 BFG Edition Source Code. If not, please request a copy in writing from id Software at the address below. 23 24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA. 25 26 =========================================================================== 27 */ 28 29 #ifndef __VECTORSET_H__ 30 #define __VECTORSET_H__ 31 32 /* 33 =============================================================================== 34 35 Vector Set 36 37 Creates a set of vectors without duplicates. 38 39 =============================================================================== 40 */ 41 42 template< class type, int dimension > 43 class idVectorSet : public idList<type> { 44 public: 45 idVectorSet(); 46 idVectorSet( const type &mins, const type &maxs, const int boxHashSize, const int initialSize ); 47 48 // returns total size of allocated memory 49 size_t Allocated() const { return idList<type>::Allocated() + hash.Allocated(); } 50 // returns total size of allocated memory including size of type 51 size_t Size() const { return sizeof( *this ) + Allocated(); } 52 53 void Init( const type &mins, const type &maxs, const int boxHashSize, const int initialSize ); 54 void ResizeIndex( const int newSize ); 55 void Clear(); 56 57 int FindVector( const type &v, const float epsilon ); 58 59 private: 60 idHashIndex hash; 61 type mins; 62 type maxs; 63 int boxHashSize; 64 float boxInvSize[dimension]; 65 float boxHalfSize[dimension]; 66 }; 67 68 template< class type, int dimension > 69 ID_INLINE idVectorSet<type,dimension>::idVectorSet() { 70 hash.Clear( idMath::IPow( boxHashSize, dimension ), 128 ); 71 boxHashSize = 16; 72 memset( boxInvSize, 0, dimension * sizeof( boxInvSize[0] ) ); 73 memset( boxHalfSize, 0, dimension * sizeof( boxHalfSize[0] ) ); 74 } 75 76 template< class type, int dimension > 77 ID_INLINE idVectorSet<type,dimension>::idVectorSet( const type &mins, const type &maxs, const int boxHashSize, const int initialSize ) { 78 Init( mins, maxs, boxHashSize, initialSize ); 79 } 80 81 template< class type, int dimension > 82 ID_INLINE void idVectorSet<type,dimension>::Init( const type &mins, const type &maxs, const int boxHashSize, const int initialSize ) { 83 int i; 84 float boxSize; 85 86 idList<type>::AssureSize( initialSize ); 87 idList<type>::SetNum( 0, false ); 88 89 hash.Clear( idMath::IPow( boxHashSize, dimension ), initialSize ); 90 91 this->mins = mins; 92 this->maxs = maxs; 93 this->boxHashSize = boxHashSize; 94 95 for ( i = 0; i < dimension; i++ ) { 96 boxSize = ( maxs[i] - mins[i] ) / (float) boxHashSize; 97 boxInvSize[i] = 1.0f / boxSize; 98 boxHalfSize[i] = boxSize * 0.5f; 99 } 100 } 101 102 template< class type, int dimension > 103 ID_INLINE void idVectorSet<type,dimension>::ResizeIndex( const int newSize ) { 104 idList<type>::Resize( newSize ); 105 hash.ResizeIndex( newSize ); 106 } 107 108 template< class type, int dimension > 109 ID_INLINE void idVectorSet<type,dimension>::Clear() { 110 idList<type>::Clear(); 111 hash.Clear(); 112 } 113 114 template< class type, int dimension > 115 ID_INLINE int idVectorSet<type,dimension>::FindVector( const type &v, const float epsilon ) { 116 int i, j, k, hashKey, partialHashKey[dimension]; 117 118 for ( i = 0; i < dimension; i++ ) { 119 assert( epsilon <= boxHalfSize[i] ); 120 partialHashKey[i] = (int) ( ( v[i] - mins[i] - boxHalfSize[i] ) * boxInvSize[i] ); 121 } 122 123 for ( i = 0; i < ( 1 << dimension ); i++ ) { 124 125 hashKey = 0; 126 for ( j = 0; j < dimension; j++ ) { 127 hashKey *= boxHashSize; 128 hashKey += partialHashKey[j] + ( ( i >> j ) & 1 ); 129 } 130 131 for ( j = hash.First( hashKey ); j >= 0; j = hash.Next( j ) ) { 132 const type &lv = (*this)[j]; 133 for ( k = 0; k < dimension; k++ ) { 134 if ( idMath::Fabs( lv[k] - v[k] ) > epsilon ) { 135 break; 136 } 137 } 138 if ( k >= dimension ) { 139 return j; 140 } 141 } 142 } 143 144 hashKey = 0; 145 for ( i = 0; i < dimension; i++ ) { 146 hashKey *= boxHashSize; 147 hashKey += (int) ( ( v[i] - mins[i] ) * boxInvSize[i] ); 148 } 149 150 hash.Add( hashKey, idList<type>::Num() ); 151 Append( v ); 152 return idList<type>::Num()-1; 153 } 154 155 156 /* 157 =============================================================================== 158 159 Vector Subset 160 161 Creates a subset without duplicates from an existing list with vectors. 162 163 =============================================================================== 164 */ 165 166 template< class type, int dimension > 167 class idVectorSubset { 168 public: 169 idVectorSubset(); 170 idVectorSubset( const type &mins, const type &maxs, const int boxHashSize, const int initialSize ); 171 172 // returns total size of allocated memory 173 size_t Allocated() const { return idList<type>::Allocated() + hash.Allocated(); } 174 // returns total size of allocated memory including size of type 175 size_t Size() const { return sizeof( *this ) + Allocated(); } 176 177 void Init( const type &mins, const type &maxs, const int boxHashSize, const int initialSize ); 178 void Clear(); 179 180 // returns either vectorNum or an index to a previously found vector 181 int FindVector( const type *vectorList, const int vectorNum, const float epsilon ); 182 183 private: 184 idHashIndex hash; 185 type mins; 186 type maxs; 187 int boxHashSize; 188 float boxInvSize[dimension]; 189 float boxHalfSize[dimension]; 190 }; 191 192 template< class type, int dimension > 193 ID_INLINE idVectorSubset<type,dimension>::idVectorSubset() { 194 hash.Clear( idMath::IPow( boxHashSize, dimension ), 128 ); 195 boxHashSize = 16; 196 memset( boxInvSize, 0, dimension * sizeof( boxInvSize[0] ) ); 197 memset( boxHalfSize, 0, dimension * sizeof( boxHalfSize[0] ) ); 198 } 199 200 template< class type, int dimension > 201 ID_INLINE idVectorSubset<type,dimension>::idVectorSubset( const type &mins, const type &maxs, const int boxHashSize, const int initialSize ) { 202 Init( mins, maxs, boxHashSize, initialSize ); 203 } 204 205 template< class type, int dimension > 206 ID_INLINE void idVectorSubset<type,dimension>::Init( const type &mins, const type &maxs, const int boxHashSize, const int initialSize ) { 207 int i; 208 float boxSize; 209 210 hash.Clear( idMath::IPow( boxHashSize, dimension ), initialSize ); 211 212 this->mins = mins; 213 this->maxs = maxs; 214 this->boxHashSize = boxHashSize; 215 216 for ( i = 0; i < dimension; i++ ) { 217 boxSize = ( maxs[i] - mins[i] ) / (float) boxHashSize; 218 boxInvSize[i] = 1.0f / boxSize; 219 boxHalfSize[i] = boxSize * 0.5f; 220 } 221 } 222 223 template< class type, int dimension > 224 ID_INLINE void idVectorSubset<type,dimension>::Clear() { 225 idList<type>::Clear(); 226 hash.Clear(); 227 } 228 229 template< class type, int dimension > 230 ID_INLINE int idVectorSubset<type,dimension>::FindVector( const type *vectorList, const int vectorNum, const float epsilon ) { 231 int i, j, k, hashKey, partialHashKey[dimension]; 232 const type &v = vectorList[vectorNum]; 233 234 for ( i = 0; i < dimension; i++ ) { 235 assert( epsilon <= boxHalfSize[i] ); 236 partialHashKey[i] = (int) ( ( v[i] - mins[i] - boxHalfSize[i] ) * boxInvSize[i] ); 237 } 238 239 for ( i = 0; i < ( 1 << dimension ); i++ ) { 240 241 hashKey = 0; 242 for ( j = 0; j < dimension; j++ ) { 243 hashKey *= boxHashSize; 244 hashKey += partialHashKey[j] + ( ( i >> j ) & 1 ); 245 } 246 247 for ( j = hash.First( hashKey ); j >= 0; j = hash.Next( j ) ) { 248 const type &lv = vectorList[j]; 249 for ( k = 0; k < dimension; k++ ) { 250 if ( idMath::Fabs( lv[k] - v[k] ) > epsilon ) { 251 break; 252 } 253 } 254 if ( k >= dimension ) { 255 return j; 256 } 257 } 258 } 259 260 hashKey = 0; 261 for ( i = 0; i < dimension; i++ ) { 262 hashKey *= boxHashSize; 263 hashKey += (int) ( ( v[i] - mins[i] ) * boxInvSize[i] ); 264 } 265 266 hash.Add( hashKey, vectorNum ); 267 return vectorNum; 268 } 269 270 #endif /* !__VECTORSET_H__ */