Panda3D
 All Classes Functions Variables Enumerations
physxMeshHash.cxx
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 
 All Classes Functions Variables Enumerations