Panda3D
Loading...
Searching...
No Matches
physxMeshHash.cxx
Go to the documentation of this file.
1/**
2 * PANDA 3D SOFTWARE
3 * Copyright (c) Carnegie Mellon University. All rights reserved.
4 *
5 * All use of this software is subject to the terms of the revised BSD
6 * license. You should have received a copy of this license along
7 * with this source code in a file named "LICENSE."
8 *
9 * @file physxMeshHash.cxx
10 * @author enn0x
11 * @date 2010-09-13
12 */
13
14#include "physxMeshHash.h"
15
16/**
17 *
18 */
19void PhysxMeshHash::
20quick_sort(pvector<int> &itemIndices, int l, int r) {
21
22 int i, j, mi;
23 int k, m;
24
25 i = l; j = r; mi = (l + r)/2;
26 m = itemIndices[mi];
27
28 while (i <= j) {
29 while(itemIndices[i] < m) i++;
30 while(m < itemIndices[j]) j--;
31
32 if (i <= j) {
33 k = itemIndices[i]; itemIndices[i] = itemIndices[j]; itemIndices[j] = k;
34 i++; j--;
35 }
36 }
37
38 if (l < j) quick_sort(itemIndices, l, j);
39 if (i < r) quick_sort(itemIndices, i, r);
40}
41
42/**
43 *
44 */
45void PhysxMeshHash::
46compress_indices(pvector<int> &itemIndices) {
47
48 if (itemIndices.size() == 0) return;
49
50 // Sort results
51 quick_sort(itemIndices, 0, itemIndices.size() - 1);
52
53 // Mark duplicates
54 int i = 0;
55 while (i < (int)itemIndices.size()) {
56 int j = i+1;
57 while (j < (int)itemIndices.size() && itemIndices[i] == itemIndices[j]) {
58 itemIndices[j] = -1; j++;
59 }
60 i = j;
61 }
62
63 // Remove duplicates
64 i = 0;
65 while (i < (int)itemIndices.size()) {
66 if (itemIndices[i] < 0) {
67 itemIndices[i] = itemIndices[itemIndices.size()-1];
68 itemIndices.pop_back();
69 }
70 else i++;
71 }
72}
73
74/**
75 *
76 */
77void PhysxMeshHash::
78set_grid_spacing(float spacing) {
79
80 _spacing = spacing;
81 _invSpacing = 1.0f / spacing;
82
83 reset();
84}
85
86/**
87 *
88 */
89void PhysxMeshHash::
90reset() {
91
92 _time++;
93 _entries.clear();
94}
95
96/**
97 *
98 */
99void PhysxMeshHash::
100add(const NxBounds3 &bounds, int itemIndex) {
101
102 int x1,y1,z1;
103 int x2,y2,z2;
104 int x,y,z;
105
106 cell_coord_of(bounds.min, x1, y1, z1);
107 cell_coord_of(bounds.max, x2, y2, z2);
108
109 MeshHashEntry entry;
110 entry.itemIndex = itemIndex;
111
112 for (x = x1; x <= x2; x++) {
113 for (y = y1; y <= y2; y++) {
114 for (z = z1; z <= z2; z++) {
115
116 int h = hash_function(x, y, z);
117 MeshHashRoot &r = _hashIndex[h];
118 int n = _entries.size();
119
120 if (r.timeStamp != _time || r.first < 0)
121 entry.next = -1;
122 else
123 entry.next = r.first;
124
125 r.first = n;
126 r.timeStamp = _time;
127
128 _entries.push_back(entry);
129 }
130 }
131 }
132}
133
134/**
135 *
136 */
137void PhysxMeshHash::
138add(const NxVec3 &pos, int itemIndex) {
139
140 int x, y, z;
141
142 cell_coord_of(pos, x, y, z);
143
144 MeshHashEntry entry;
145 entry.itemIndex = itemIndex;
146
147 int h = hash_function(x, y, z);
148 MeshHashRoot &r = _hashIndex[h];
149 int n = _entries.size();
150
151 if (r.timeStamp != _time || r.first < 0)
152 entry.next = -1;
153 else
154 entry.next = r.first;
155
156 r.first = n;
157 r.timeStamp = _time;
158
159 _entries.push_back(entry);
160}
161
162/**
163 *
164 */
165void PhysxMeshHash::
166query(const NxBounds3 &bounds, pvector<int> &itemIndices, int maxIndices) {
167
168 int x1, y1, z1;
169 int x2, y2, z2;
170 int x, y, z;
171
172 cell_coord_of(bounds.min, x1, y1, z1);
173 cell_coord_of(bounds.max, x2, y2, z2);
174
175 itemIndices.clear();
176
177 for (x=x1; x<=x2; x++) {
178 for (y=y1; y<=y2; y++) {
179 for (z=z1; z<=z2; z++) {
180
181 int h = hash_function(x, y, z);
182
183 MeshHashRoot &r = _hashIndex[h];
184 if (r.timeStamp != _time) continue;
185 int i = r.first;
186
187 while (i >= 0) {
188 MeshHashEntry &entry = _entries[i];
189 itemIndices.push_back(entry.itemIndex);
190 if (maxIndices >= 0 && (int)itemIndices.size() >= maxIndices) return;
191 i = entry.next;
192 }
193 }
194 }
195 }
196}
197
198/**
199 *
200 */
201void PhysxMeshHash::
202query_unique(const NxBounds3 &bounds, pvector<int> &itemIndices, int maxIndices) {
203
204 query(bounds, itemIndices, maxIndices);
205 compress_indices(itemIndices);
206}
207
208/**
209 *
210 */
211void PhysxMeshHash::
212query(const NxVec3 &pos, pvector<int> &itemIndices, int maxIndices) {
213
214 int x, y, z;
215
216 cell_coord_of(pos, x, y, z);
217
218 itemIndices.clear();
219
220 int h = hash_function(x, y, z);
221 MeshHashRoot &r = _hashIndex[h];
222 if (r.timeStamp != _time) return;
223 int i = r.first;
224
225 while (i >= 0) {
226 MeshHashEntry &entry = _entries[i];
227 itemIndices.push_back(entry.itemIndex);
228 if (maxIndices >= 0 && (int)itemIndices.size() >= maxIndices) return;
229 i = entry.next;
230 }
231}
232
233/**
234 *
235 */
236void PhysxMeshHash::
237query_unique(const NxVec3 &pos, pvector<int> &itemIndices, int maxIndices) {
238
239 query(pos, itemIndices, maxIndices);
240 compress_indices(itemIndices);
241}
This is our own Panda specialization on the default STL vector.
Definition pvector.h:42
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.