PBRT
|
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