PBRT
/home/felix/UBC/projects/AdaptiveLightfieldSampling/pbrt_v2/src/core/octree.h
00001 
00002 /*
00003     pbrt source code Copyright(c) 1998-2012 Matt Pharr and Greg Humphreys.
00004 
00005     This file is part of pbrt.
00006 
00007     Redistribution and use in source and binary forms, with or without
00008     modification, are permitted provided that the following conditions are
00009     met:
00010 
00011     - Redistributions of source code must retain the above copyright
00012       notice, this list of conditions and the following disclaimer.
00013 
00014     - Redistributions in binary form must reproduce the above copyright
00015       notice, this list of conditions and the following disclaimer in the
00016       documentation and/or other materials provided with the distribution.
00017 
00018     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
00019     IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
00020     TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
00021     PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
00022     HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00023     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
00024     LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00025     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00026     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00027     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
00028     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029 
00030  */
00031 
00032 #if defined(_MSC_VER)
00033 #pragma once
00034 #endif
00035 
00036 #ifndef PBRT_CORE_OCTREE_H
00037 #define PBRT_CORE_OCTREE_H
00038 
00039 // core/octree.h*
00040 #include "pbrt.h"
00041 #include "geometry.h"
00042 
00043 // Octree Declarations
00044 template <typename NodeData> struct OctNode {
00045     OctNode() {
00046         for (int i = 0; i < 8; ++i)
00047             children[i] = NULL;
00048     }
00049     ~OctNode() {
00050         for (int i = 0; i < 8; ++i)
00051             delete children[i];
00052     }
00053     OctNode *children[8];
00054     vector<NodeData> data;
00055 };
00056 
00057 
00058 template <typename NodeData> class Octree {
00059 public:
00060     // Octree Public Methods
00061     Octree(const BBox &b, int md = 16)
00062         : maxDepth(md), bound(b) { }
00063     void Add(const NodeData &dataItem, const BBox &dataBound) {
00064         addPrivate(&root, bound, dataItem, dataBound,
00065                    DistanceSquared(dataBound.pMin, dataBound.pMax));
00066     }
00067     template <typename LookupProc> void Lookup(const Point &p,
00068                                                LookupProc &process) {
00069         if (!bound.Inside(p)) return;
00070         lookupPrivate(&root, bound, p, process);
00071     }
00072 private:
00073     // Octree Private Methods
00074     void addPrivate(OctNode<NodeData> *node, const BBox &nodeBound,
00075         const NodeData &dataItem, const BBox &dataBound, float diag2,
00076         int depth = 0);
00077     template <typename LookupProc> bool lookupPrivate(OctNode<NodeData> *node,
00078             const BBox &nodeBound, const Point &P, LookupProc &process);
00079 
00080     // Octree Private Data
00081     int maxDepth;
00082     BBox bound;
00083     OctNode<NodeData> root;
00084 };
00085 
00086 
00087 inline BBox octreeChildBound(int child, const BBox &nodeBound,
00088                              const Point &pMid) {
00089     BBox childBound;
00090     childBound.pMin.x = (child & 4) ? pMid.x : nodeBound.pMin.x;
00091     childBound.pMax.x = (child & 4) ? nodeBound.pMax.x : pMid.x;
00092     childBound.pMin.y = (child & 2) ? pMid.y : nodeBound.pMin.y;
00093     childBound.pMax.y = (child & 2) ? nodeBound.pMax.y : pMid.y;
00094     childBound.pMin.z = (child & 1) ? pMid.z : nodeBound.pMin.z;
00095     childBound.pMax.z = (child & 1) ? nodeBound.pMax.z : pMid.z;
00096     return childBound;
00097 }
00098 
00099 
00100 
00101 // Octree Method Definitions
00102 template <typename NodeData>
00103 void Octree<NodeData>::addPrivate(
00104         OctNode<NodeData> *node, const BBox &nodeBound,
00105         const NodeData &dataItem, const BBox &dataBound,
00106         float diag2, int depth) {
00107     // Possibly add data item to current octree node
00108     if (depth == maxDepth ||
00109         DistanceSquared(nodeBound.pMin, nodeBound.pMax) < diag2) {
00110         node->data.push_back(dataItem);
00111         return;
00112     }
00113 
00114     // Otherwise add data item to octree children
00115     Point pMid = .5 * nodeBound.pMin + .5 * nodeBound.pMax;
00116 
00117     // Determine which children the item overlaps
00118     bool x[2] = { dataBound.pMin.x <= pMid.x, dataBound.pMax.x > pMid.x };
00119     bool y[2] = { dataBound.pMin.y <= pMid.y, dataBound.pMax.y > pMid.y };
00120     bool z[2] = { dataBound.pMin.z <= pMid.z, dataBound.pMax.z > pMid.z };
00121     bool over[8] = { x[0] & y[0] & z[0], x[0] & y[0] & z[1],
00122                      x[0] & y[1] & z[0], x[0] & y[1] & z[1],
00123                      x[1] & y[0] & z[0], x[1] & y[0] & z[1],
00124                      x[1] & y[1] & z[0], x[1] & y[1] & z[1] };
00125     for (int child = 0; child < 8; ++child) {
00126         if (!over[child]) continue;
00127         // Allocate octree node if needed and continue recursive traversal
00128         if (!node->children[child])
00129             node->children[child] = new OctNode<NodeData>;
00130         BBox childBound = octreeChildBound(child, nodeBound, pMid);
00131         addPrivate(node->children[child], childBound,
00132                    dataItem, dataBound, diag2, depth+1);
00133     }
00134 }
00135 
00136 
00137 template <typename NodeData> template <typename LookupProc>
00138 bool Octree<NodeData>::lookupPrivate(OctNode<NodeData> *node,
00139         const BBox &nodeBound, const Point &p, LookupProc &process) {
00140     for (uint32_t i = 0; i < node->data.size(); ++i)
00141         if (!process(node->data[i]))
00142             return false;
00143     // Determine which octree child node _p_ is inside
00144     Point pMid = .5f * nodeBound.pMin + .5f * nodeBound.pMax;
00145     int child = (p.x > pMid.x ? 4 : 0) + (p.y > pMid.y ? 2 : 0) +
00146                 (p.z > pMid.z ? 1 : 0);
00147     if (!node->children[child])
00148         return true;
00149     BBox childBound = octreeChildBound(child, nodeBound, pMid);
00150     return lookupPrivate(node->children[child], childBound, p, process);
00151 }
00152 
00153 
00154 
00155 #endif // PBRT_CORE_OCTREE_H