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