Panda3D
|
00001 // Filename: physxMeshHash.cxx 00002 // Created by: enn0x (13Sep10) 00003 // 00004 //////////////////////////////////////////////////////////////////// 00005 // 00006 // PANDA 3D SOFTWARE 00007 // Copyright (c) Carnegie Mellon University. All rights reserved. 00008 // 00009 // All use of this software is subject to the terms of the revised BSD 00010 // license. You should have received a copy of this license along 00011 // with this source code in a file named "LICENSE." 00012 // 00013 //////////////////////////////////////////////////////////////////// 00014 00015 #include "physxMeshHash.h" 00016 00017 //////////////////////////////////////////////////////////////////// 00018 // Function: PhysxMeshHash::quick_sort 00019 // Access: Private 00020 // Description: 00021 //////////////////////////////////////////////////////////////////// 00022 void PhysxMeshHash:: 00023 quick_sort(pvector<int> &itemIndices, int l, int r) { 00024 00025 int i, j, mi; 00026 int k, m; 00027 00028 i = l; j = r; mi = (l + r)/2; 00029 m = itemIndices[mi]; 00030 00031 while (i <= j) { 00032 while(itemIndices[i] < m) i++; 00033 while(m < itemIndices[j]) j--; 00034 00035 if (i <= j) { 00036 k = itemIndices[i]; itemIndices[i] = itemIndices[j]; itemIndices[j] = k; 00037 i++; j--; 00038 } 00039 } 00040 00041 if (l < j) quick_sort(itemIndices, l, j); 00042 if (i < r) quick_sort(itemIndices, i, r); 00043 } 00044 00045 //////////////////////////////////////////////////////////////////// 00046 // Function: PhysxMeshHash::compress_indices 00047 // Access: Private 00048 // Description: 00049 //////////////////////////////////////////////////////////////////// 00050 void PhysxMeshHash:: 00051 compress_indices(pvector<int> &itemIndices) { 00052 00053 if (itemIndices.size() == 0) return; 00054 00055 // Sort results 00056 quick_sort(itemIndices, 0, itemIndices.size() - 1); 00057 00058 // Mark duplicates 00059 int i = 0; 00060 while (i < (int)itemIndices.size()) { 00061 int j = i+1; 00062 while (j < (int)itemIndices.size() && itemIndices[i] == itemIndices[j]) { 00063 itemIndices[j] = -1; j++; 00064 } 00065 i = j; 00066 } 00067 00068 // Remove duplicates 00069 i = 0; 00070 while (i < (int)itemIndices.size()) { 00071 if (itemIndices[i] < 0) { 00072 itemIndices[i] = itemIndices[itemIndices.size()-1]; 00073 itemIndices.pop_back(); 00074 } 00075 else i++; 00076 } 00077 } 00078 00079 //////////////////////////////////////////////////////////////////// 00080 // Function: PhysxMeshHash::set_grid_spacing 00081 // Access: Public 00082 // Description: 00083 //////////////////////////////////////////////////////////////////// 00084 void PhysxMeshHash:: 00085 set_grid_spacing(float spacing) { 00086 00087 _spacing = spacing; 00088 _invSpacing = 1.0f / spacing; 00089 00090 reset(); 00091 } 00092 00093 //////////////////////////////////////////////////////////////////// 00094 // Function: PhysxMeshHash::reset 00095 // Access: Public 00096 // Description: 00097 //////////////////////////////////////////////////////////////////// 00098 void PhysxMeshHash:: 00099 reset() { 00100 00101 _time++; 00102 _entries.clear(); 00103 } 00104 00105 //////////////////////////////////////////////////////////////////// 00106 // Function: PhysxMeshHash::add 00107 // Access: Public 00108 // Description: 00109 //////////////////////////////////////////////////////////////////// 00110 void PhysxMeshHash:: 00111 add(const NxBounds3 &bounds, int itemIndex) { 00112 00113 int x1,y1,z1; 00114 int x2,y2,z2; 00115 int x,y,z; 00116 00117 cell_coord_of(bounds.min, x1, y1, z1); 00118 cell_coord_of(bounds.max, x2, y2, z2); 00119 00120 MeshHashEntry entry; 00121 entry.itemIndex = itemIndex; 00122 00123 for (x = x1; x <= x2; x++) { 00124 for (y = y1; y <= y2; y++) { 00125 for (z = z1; z <= z2; z++) { 00126 00127 int h = hash_function(x, y, z); 00128 MeshHashRoot &r = _hashIndex[h]; 00129 int n = _entries.size(); 00130 00131 if (r.timeStamp != _time || r.first < 0) 00132 entry.next = -1; 00133 else 00134 entry.next = r.first; 00135 00136 r.first = n; 00137 r.timeStamp = _time; 00138 00139 _entries.push_back(entry); 00140 } 00141 } 00142 } 00143 } 00144 00145 //////////////////////////////////////////////////////////////////// 00146 // Function: PhysxMeshHash::add 00147 // Access: Public 00148 // Description: 00149 //////////////////////////////////////////////////////////////////// 00150 void PhysxMeshHash:: 00151 add(const NxVec3 &pos, int itemIndex) { 00152 00153 int x, y, z; 00154 00155 cell_coord_of(pos, x, y, z); 00156 00157 MeshHashEntry entry; 00158 entry.itemIndex = itemIndex; 00159 00160 int h = hash_function(x, y, z); 00161 MeshHashRoot &r = _hashIndex[h]; 00162 int n = _entries.size(); 00163 00164 if (r.timeStamp != _time || r.first < 0) 00165 entry.next = -1; 00166 else 00167 entry.next = r.first; 00168 00169 r.first = n; 00170 r.timeStamp = _time; 00171 00172 _entries.push_back(entry); 00173 } 00174 00175 //////////////////////////////////////////////////////////////////// 00176 // Function: PhysxMeshHash::query 00177 // Access: Public 00178 // Description: 00179 //////////////////////////////////////////////////////////////////// 00180 void PhysxMeshHash:: 00181 query(const NxBounds3 &bounds, pvector<int> &itemIndices, int maxIndices) { 00182 00183 int x1, y1, z1; 00184 int x2, y2, z2; 00185 int x, y, z; 00186 00187 cell_coord_of(bounds.min, x1, y1, z1); 00188 cell_coord_of(bounds.max, x2, y2, z2); 00189 00190 itemIndices.clear(); 00191 00192 for (x=x1; x<=x2; x++) { 00193 for (y=y1; y<=y2; y++) { 00194 for (z=z1; z<=z2; z++) { 00195 00196 int h = hash_function(x, y, z); 00197 00198 MeshHashRoot &r = _hashIndex[h]; 00199 if (r.timeStamp != _time) continue; 00200 int i = r.first; 00201 00202 while (i >= 0) { 00203 MeshHashEntry &entry = _entries[i]; 00204 itemIndices.push_back(entry.itemIndex); 00205 if (maxIndices >= 0 && (int)itemIndices.size() >= maxIndices) return; 00206 i = entry.next; 00207 } 00208 } 00209 } 00210 } 00211 } 00212 00213 //////////////////////////////////////////////////////////////////// 00214 // Function: PhysxMeshHash::query_unique 00215 // Access: Public 00216 // Description: 00217 //////////////////////////////////////////////////////////////////// 00218 void PhysxMeshHash:: 00219 query_unique(const NxBounds3 &bounds, pvector<int> &itemIndices, int maxIndices) { 00220 00221 query(bounds, itemIndices, maxIndices); 00222 compress_indices(itemIndices); 00223 } 00224 00225 //////////////////////////////////////////////////////////////////// 00226 // Function: PhysxMeshHash::query 00227 // Access: Public 00228 // Description: 00229 //////////////////////////////////////////////////////////////////// 00230 void PhysxMeshHash:: 00231 query(const NxVec3 &pos, pvector<int> &itemIndices, int maxIndices) { 00232 00233 int x, y, z; 00234 00235 cell_coord_of(pos, x, y, z); 00236 00237 itemIndices.clear(); 00238 00239 int h = hash_function(x, y, z); 00240 MeshHashRoot &r = _hashIndex[h]; 00241 if (r.timeStamp != _time) return; 00242 int i = r.first; 00243 00244 while (i >= 0) { 00245 MeshHashEntry &entry = _entries[i]; 00246 itemIndices.push_back(entry.itemIndex); 00247 if (maxIndices >= 0 && (int)itemIndices.size() >= maxIndices) return; 00248 i = entry.next; 00249 } 00250 } 00251 00252 //////////////////////////////////////////////////////////////////// 00253 // Function: PhysxMeshHash::query_unique 00254 // Access: Public 00255 // Description: 00256 //////////////////////////////////////////////////////////////////// 00257 void PhysxMeshHash:: 00258 query_unique(const NxVec3 &pos, pvector<int> &itemIndices, int maxIndices) { 00259 00260 query(pos, itemIndices, maxIndices); 00261 compress_indices(itemIndices); 00262 } 00263