15 #include "physxMeshHash.h"
28 i = l; j = r; mi = (l + r)/2;
32 while(itemIndices[i] < m) i++;
33 while(m < itemIndices[j]) j--;
36 k = itemIndices[i]; itemIndices[i] = itemIndices[j]; itemIndices[j] = k;
41 if (l < j) quick_sort(itemIndices, l, j);
42 if (i < r) quick_sort(itemIndices, i, r);
53 if (itemIndices.size() == 0)
return;
56 quick_sort(itemIndices, 0, itemIndices.size() - 1);
60 while (i < (
int)itemIndices.size()) {
62 while (j < (
int)itemIndices.size() && itemIndices[i] == itemIndices[j]) {
63 itemIndices[j] = -1; j++;
70 while (i < (
int)itemIndices.size()) {
71 if (itemIndices[i] < 0) {
72 itemIndices[i] = itemIndices[itemIndices.size()-1];
73 itemIndices.pop_back();
85 set_grid_spacing(
float spacing) {
88 _invSpacing = 1.0f / spacing;
111 add(
const NxBounds3 &bounds,
int itemIndex) {
117 cell_coord_of(bounds.min, x1, y1, z1);
118 cell_coord_of(bounds.max, x2, y2, z2);
121 entry.itemIndex = itemIndex;
123 for (x = x1; x <= x2; x++) {
124 for (y = y1; y <= y2; y++) {
125 for (z = z1; z <= z2; z++) {
127 int h = hash_function(x, y, z);
128 MeshHashRoot &r = _hashIndex[h];
129 int n = _entries.size();
131 if (r.timeStamp != _time || r.first < 0)
134 entry.next = r.first;
139 _entries.push_back(entry);
151 add(
const NxVec3 &pos,
int itemIndex) {
155 cell_coord_of(pos, x, y, z);
158 entry.itemIndex = itemIndex;
160 int h = hash_function(x, y, z);
161 MeshHashRoot &r = _hashIndex[h];
162 int n = _entries.size();
164 if (r.timeStamp != _time || r.first < 0)
167 entry.next = r.first;
172 _entries.push_back(entry);
181 query(
const NxBounds3 &bounds,
pvector<int> &itemIndices,
int maxIndices) {
187 cell_coord_of(bounds.min, x1, y1, z1);
188 cell_coord_of(bounds.max, x2, y2, z2);
192 for (x=x1; x<=x2; x++) {
193 for (y=y1; y<=y2; y++) {
194 for (z=z1; z<=z2; z++) {
196 int h = hash_function(x, y, z);
198 MeshHashRoot &r = _hashIndex[h];
199 if (r.timeStamp != _time)
continue;
203 MeshHashEntry &entry = _entries[i];
204 itemIndices.push_back(entry.itemIndex);
205 if (maxIndices >= 0 && (
int)itemIndices.size() >= maxIndices)
return;
219 query_unique(
const NxBounds3 &bounds,
pvector<int> &itemIndices,
int maxIndices) {
221 query(bounds, itemIndices, maxIndices);
222 compress_indices(itemIndices);
231 query(
const NxVec3 &pos,
pvector<int> &itemIndices,
int maxIndices) {
235 cell_coord_of(pos, x, y, z);
239 int h = hash_function(x, y, z);
240 MeshHashRoot &r = _hashIndex[h];
241 if (r.timeStamp != _time)
return;
245 MeshHashEntry &entry = _entries[i];
246 itemIndices.push_back(entry.itemIndex);
247 if (maxIndices >= 0 && (
int)itemIndices.size() >= maxIndices)
return;
258 query_unique(
const NxVec3 &pos,
pvector<int> &itemIndices,
int maxIndices) {
260 query(pos, itemIndices, maxIndices);
261 compress_indices(itemIndices);