00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #ifndef LUX_OCTREE_H
00024 #define LUX_OCTREE_H
00025
00026 #include "lux.h"
00027 #include "geometry.h"
00028
00029 namespace lux
00030 {
00031
00032
00033 template <class NodeData> struct OctNode {
00034 OctNode() {
00035 for (int i = 0; i < 8; ++i)
00036 children[i] = NULL;
00037 }
00038 ~OctNode() {
00039 for (int i = 0; i < 8; ++i)
00040 delete children[i];
00041 }
00042 OctNode *children[8];
00043 vector<NodeData> data;
00044 };
00045 template <class NodeData, class LookupProc> class Octree {
00046 public:
00047
00048 Octree(const BBox &b, int md = 16)
00049 : bound(b) {
00050 maxDepth = md;
00051 }
00052 void Add(const NodeData &dataItem, const BBox &dataBound) {
00053 addPrivate(&root, bound, dataItem, dataBound,
00054 DistanceSquared(dataBound.pMin, dataBound.pMax));
00055 }
00056 void Lookup(const Point &p, const LookupProc &process) {
00057 if (!bound.Inside(p)) return;
00058 lookupPrivate(&root, bound, p, process);
00059 }
00060 private:
00061
00062 void addPrivate(OctNode<NodeData> *node, const BBox &nodeBound,
00063 const NodeData &dataItem, const BBox &dataBound, float diag2,
00064 int depth = 0);
00065 void lookupPrivate(OctNode<NodeData> *node, const BBox &nodeBound, const Point &P,
00066 const LookupProc &process);
00067
00068 int maxDepth;
00069 BBox bound;
00070 OctNode<NodeData> root;
00071 };
00072
00073 template <class NodeData, class LookupProc>
00074 void Octree<NodeData, LookupProc>::addPrivate(
00075 OctNode<NodeData> *node, const BBox &nodeBound,
00076 const NodeData &dataItem, const BBox &dataBound,
00077 float diag2, int depth) {
00078
00079 if (depth == maxDepth ||
00080 DistanceSquared(nodeBound.pMin,
00081 nodeBound.pMax) < diag2) {
00082 node->data.push_back(dataItem);
00083 return;
00084 }
00085
00086 Point pMid = .5 * nodeBound.pMin + .5 * nodeBound.pMax;
00087
00088 bool over[8];
00089 over[0] = over[1] =
00090 over[2] =
00091 over[3] = (dataBound.pMin.x <= pMid.x);
00092 over[4] = over[5] =
00093 over[6] =
00094 over[7] = (dataBound.pMax.x > pMid.x);
00095 over[0] &= (dataBound.pMin.y <= pMid.y);
00096 over[1] &= (dataBound.pMin.y <= pMid.y);
00097 over[4] &= (dataBound.pMin.y <= pMid.y);
00098 over[5] &= (dataBound.pMin.y <= pMid.y);
00099 over[2] &= (dataBound.pMax.y > pMid.y);
00100 over[3] &= (dataBound.pMax.y > pMid.y);
00101 over[6] &= (dataBound.pMax.y > pMid.y);
00102 over[7] &= (dataBound.pMax.y > pMid.y);
00103 over[0] &= (dataBound.pMin.z <= pMid.z);
00104 over[2] &= (dataBound.pMin.z <= pMid.z);
00105 over[4] &= (dataBound.pMin.z <= pMid.z);
00106 over[6] &= (dataBound.pMin.z <= pMid.z);
00107 over[1] &= (dataBound.pMax.z > pMid.z);
00108 over[3] &= (dataBound.pMax.z > pMid.z);
00109 over[5] &= (dataBound.pMax.z > pMid.z);
00110 over[7] &= (dataBound.pMax.z > pMid.z);
00111 for (int child = 0; child < 8; ++child) {
00112 if (!over[child]) continue;
00113 if (!node->children[child])
00114 node->children[child] = new OctNode<NodeData>;
00115
00116 BBox childBound;
00117 childBound.pMin.x = (child & 4) ? pMid.x : nodeBound.pMin.x;
00118 childBound.pMax.x = (child & 4) ? nodeBound.pMax.x : pMid.x;
00119 childBound.pMin.y = (child & 2) ? pMid.y : nodeBound.pMin.y;
00120 childBound.pMax.y = (child & 2) ? nodeBound.pMax.y : pMid.y;
00121 childBound.pMin.z = (child & 1) ? pMid.z : nodeBound.pMin.z;
00122 childBound.pMax.z = (child & 1) ? nodeBound.pMax.z : pMid.z;
00123 addPrivate(node->children[child], childBound,
00124 dataItem, dataBound, diag2, depth+1);
00125 }
00126 }
00127 template <class NodeData, class LookupProc>
00128 void Octree<NodeData, LookupProc>::lookupPrivate(
00129 OctNode<NodeData> *node, const BBox &nodeBound,
00130 const Point &p, const LookupProc &process) {
00131 for (u_int i = 0; i < node->data.size(); ++i)
00132 process(p, node->data[i]);
00133
00134 Point pMid = .5f * nodeBound.pMin + .5f * nodeBound.pMax;
00135 int child = (p.x > pMid.x ? 4 : 0) +
00136 (p.y > pMid.y ? 2 : 0) + (p.z > pMid.z ? 1 : 0);
00137 if (node->children[child]) {
00138
00139 BBox childBound;
00140 childBound.pMin.x = (child & 4) ? pMid.x : nodeBound.pMin.x;
00141 childBound.pMax.x = (child & 4) ? nodeBound.pMax.x : pMid.x;
00142 childBound.pMin.y = (child & 2) ? pMid.y : nodeBound.pMin.y;
00143 childBound.pMax.y = (child & 2) ? nodeBound.pMax.y : pMid.y;
00144 childBound.pMin.z = (child & 1) ? pMid.z : nodeBound.pMin.z;
00145 childBound.pMax.z = (child & 1) ? nodeBound.pMax.z : pMid.z;
00146 lookupPrivate(node->children[child], childBound, p,
00147 process);
00148 }
00149 }
00150
00151 }
00152
00153 #endif // LUX_OCTREE_H