Panda3D

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 */
19 void PhysxMeshHash::
20 quick_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 */
45 void PhysxMeshHash::
46 compress_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 */
77 void PhysxMeshHash::
78 set_grid_spacing(float spacing) {
79
80 _spacing = spacing;
81 _invSpacing = 1.0f / spacing;
82
83 reset();
84 }
85
86 /**
87 *
88 */
89 void PhysxMeshHash::
90 reset() {
91
92 _time++;
93 _entries.clear();
94 }
95
96 /**
97 *
98 */
99 void PhysxMeshHash::
100 add(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 */
137 void PhysxMeshHash::
138 add(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 */
165 void PhysxMeshHash::
166 query(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 */
201 void PhysxMeshHash::
202 query_unique(const NxBounds3 &bounds, pvector<int> &itemIndices, int maxIndices) {
203
204 query(bounds, itemIndices, maxIndices);
205 compress_indices(itemIndices);
206 }
207
208 /**
209 *
210 */
211 void PhysxMeshHash::
212 query(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 */
236 void PhysxMeshHash::
237 query_unique(const NxVec3 &pos, pvector<int> &itemIndices, int maxIndices) {
238
239 query(pos, itemIndices, maxIndices);
240 compress_indices(itemIndices);
241 }
pvector< int >
physxMeshHash.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.