00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015 #include "physxMeshHash.h"
00016
00017
00018
00019
00020
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
00047
00048
00049
00050 void PhysxMeshHash::
00051 compress_indices(pvector<int> &itemIndices) {
00052
00053 if (itemIndices.size() == 0) return;
00054
00055
00056 quick_sort(itemIndices, 0, itemIndices.size() - 1);
00057
00058
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
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
00081
00082
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
00095
00096
00097
00098 void PhysxMeshHash::
00099 reset() {
00100
00101 _time++;
00102 _entries.clear();
00103 }
00104
00105
00106
00107
00108
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
00147
00148
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
00177
00178
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
00215
00216
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
00227
00228
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
00254
00255
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