00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029 #include "bvhaccel.h"
00030 #include "paramset.h"
00031 #include "dynload.h"
00032 #include "memory.h"
00033
00034 #include "error.h"
00035
00036 #include <functional>
00037 using std::bind2nd;
00038 using std::ptr_fun;
00039
00040 using namespace lux;
00041
00042
00043 BVHAccel::BVHAccel(const vector<boost::shared_ptr<Primitive> > &p, int treetype, int csamples, int icost, int tcost, float ebonus) :
00044 costSamples(csamples), isectCost(icost), traversalCost(tcost), emptyBonus(ebonus) {
00045 vector<boost::shared_ptr<Primitive> > vPrims;
00046 const PrimitiveRefinementHints refineHints(false);
00047 for (u_int i = 0; i < p.size(); ++i) {
00048 if(p[i]->CanIntersect())
00049 vPrims.push_back(p[i]);
00050 else
00051 p[i]->Refine(vPrims, refineHints, p[i]);
00052 }
00053
00054
00055 if(treetype <= 2) treeType = 2;
00056 else if(treetype <=4) treeType = 4;
00057 else treeType = 8;
00058
00059
00060 nPrims = vPrims.size();
00061 prims = AllocAligned<boost::shared_ptr<Primitive> >(nPrims);
00062 for (u_int i = 0; i < nPrims; ++i)
00063 new (&prims[i]) boost::shared_ptr<Primitive>(vPrims[i]);
00064
00065 vector<boost::shared_ptr<BVHAccelTreeNode> > bvList;
00066 for (u_int i = 0; i < nPrims; ++i) {
00067 boost::shared_ptr<BVHAccelTreeNode> ptr(new BVHAccelTreeNode());
00068 ptr->bbox = prims[i]->WorldBound();
00069
00070 ptr->bbox.Expand(MachineEpsilon::E(ptr->bbox));
00071 ptr->primitive = prims[i].get();
00072 bvList.push_back(ptr);
00073 }
00074
00075 std::stringstream ss;
00076 ss << "Building Bounding Volume Hierarchy, primitives: " << nPrims;
00077 luxError(LUX_NOERROR, LUX_INFO, ss.str().c_str());
00078
00079 boost::shared_ptr<BVHAccelTreeNode> rootNode;
00080 nNodes = 0;
00081 rootNode = BuildHierarchy(bvList, 0, bvList.size(), 2);
00082
00083 ss.str("");
00084 ss << "Pre-processing Bounding Volume Hierarchy, total nodes: " << nNodes;
00085 luxError(LUX_NOERROR, LUX_INFO, ss.str().c_str());
00086
00087 bvhTree = AllocAligned<BVHAccelArrayNode>(nNodes);
00088 BuildArray(rootNode, 0);
00089
00090 ss.str("");
00091 ss << "Finished building Bounding Volume Hierarchy array";
00092 luxError(LUX_NOERROR, LUX_INFO, ss.str().c_str());
00093 }
00094
00095 BVHAccel::~BVHAccel() {
00096 for(u_int i=0; i<nPrims; i++)
00097 prims[i].~shared_ptr();
00098 FreeAligned(prims);
00099 FreeAligned(bvhTree);
00100 }
00101
00102
00103 bool bvh_ltf_x(boost::shared_ptr<BVHAccelTreeNode> n, float v) { return n->bbox.pMax.x+n->bbox.pMin.x < v; }
00104 bool bvh_ltf_y(boost::shared_ptr<BVHAccelTreeNode> n, float v) { return n->bbox.pMax.y+n->bbox.pMin.y < v; }
00105 bool bvh_ltf_z(boost::shared_ptr<BVHAccelTreeNode> n, float v) { return n->bbox.pMax.z+n->bbox.pMin.z < v; }
00106 bool (* const bvh_ltf[3])(boost::shared_ptr<BVHAccelTreeNode> n, float v) = {bvh_ltf_x, bvh_ltf_y, bvh_ltf_z};
00107
00108 boost::shared_ptr<BVHAccelTreeNode> BVHAccel::BuildHierarchy(vector<boost::shared_ptr<BVHAccelTreeNode> > &list, u_int begin, u_int end, u_int axis) {
00109 u_int splitAxis = axis;
00110 float splitValue;
00111
00112 nNodes += 1;
00113 if(end-begin == 1)
00114 return list[begin];
00115
00116 boost::shared_ptr<BVHAccelTreeNode> parent(new BVHAccelTreeNode());
00117 parent->primitive = NULL;
00118
00119 vector<u_int> splits; splits.reserve(treeType+1);
00120 splits.push_back(begin); splits.push_back(end);
00121 for(u_int i = 2; i <= treeType; i *= 2) {
00122 for(u_int j = 0, offset = 0; j+offset < i && splits.size() > j+1; j += 2) {
00123
00124
00125
00126
00127
00128
00129
00130
00131
00132
00133
00134
00135
00136
00137
00138
00139
00140
00141
00142
00143 if(splits[j+1] - splits[j] < 2) {
00144 j--; offset++;
00145 continue;
00146 }
00147
00148 FindBestSplit(list, splits[j], splits[j+1], &splitValue, &splitAxis);
00149
00150 vector<boost::shared_ptr<BVHAccelTreeNode> >::iterator it =
00151 partition(list.begin()+splits[j], list.begin()+splits[j+1], bind2nd(ptr_fun(bvh_ltf[splitAxis]), splitValue));
00152 u_int middle = distance(list.begin(), it);
00153 middle = max(splits[j]+1, min(splits[j+1]-1, middle));
00154 splits.insert(splits.begin()+j+1, middle);
00155 }
00156 }
00157
00158 boost::shared_ptr<BVHAccelTreeNode> child, lastChild;
00159
00160 child = BuildHierarchy(list, splits[0], splits[1], splitAxis);
00161 parent->leftChild = child;
00162 parent->bbox = Union(parent->bbox, child->bbox);
00163 lastChild = child;
00164
00165
00166 for(u_int i = 1; i < splits.size()-1; i++) {
00167 child = BuildHierarchy(list, splits[i], splits[i+1], splitAxis);
00168 lastChild->rightSibling = child;
00169 parent->bbox = Union(parent->bbox, child->bbox);
00170 lastChild = child;
00171 }
00172
00173 return parent;
00174 }
00175
00176 void BVHAccel::FindBestSplit(vector<boost::shared_ptr<BVHAccelTreeNode> > &list, u_int begin, u_int end, float *splitValue, u_int *bestAxis) {
00177 if(end-begin == 2) {
00178
00179 *splitValue = (list[begin]->bbox.pMax[0]+list[begin]->bbox.pMin[0]+
00180 list[end-1]->bbox.pMax[0]+list[end-1]->bbox.pMin[0])/2;
00181 *bestAxis = 0;
00182 } else {
00183
00184 Point mean2(0,0,0), var(0,0,0);
00185 for(u_int i = begin; i < end; i++)
00186 mean2 += list[i]->bbox.pMax+list[i]->bbox.pMin;
00187 mean2 /= end-begin;
00188
00189
00190 for(u_int i = begin; i < end; i++) {
00191 Vector v = list[i]->bbox.pMax+list[i]->bbox.pMin - mean2;
00192 v.x *= v.x; v.y *= v.y; v.z *= v.z;
00193 var += v;
00194 }
00195
00196 if (var.x > var.y && var.x > var.z)
00197 *bestAxis = 0;
00198 else if (var.y > var.z)
00199 *bestAxis = 1;
00200 else
00201 *bestAxis = 2;
00202
00203 if(costSamples > 1) {
00204 BBox nodeBounds;
00205 for(u_int i = begin; i < end; i++)
00206 nodeBounds = Union(nodeBounds, list[i]->bbox);
00207
00208 Vector d = nodeBounds.pMax - nodeBounds.pMin;
00209 float totalSA = (2.f * (d.x*d.y + d.x*d.z + d.y*d.z));
00210 float invTotalSA = 1.f / totalSA;
00211
00212
00213 float increment = 2*d[*bestAxis]/(costSamples+1);
00214 float bestCost = INFINITY;
00215 for(float splitVal = 2*nodeBounds.pMin[*bestAxis]+increment; splitVal < 2*nodeBounds.pMax[*bestAxis]; splitVal += increment) {
00216 int nBelow = 0, nAbove = 0;
00217 BBox bbBelow, bbAbove;
00218 for(u_int j = begin; j < end; j++) {
00219 if((list[j]->bbox.pMax[*bestAxis]+list[j]->bbox.pMin[*bestAxis]) < splitVal) {
00220 nBelow++;
00221 bbBelow = Union(bbBelow, list[j]->bbox);
00222 } else {
00223 nAbove++;
00224 bbAbove = Union(bbAbove, list[j]->bbox);
00225 }
00226 }
00227 Vector dBelow = bbBelow.pMax - bbBelow.pMin;
00228 Vector dAbove = bbAbove.pMax - bbAbove.pMin;
00229 float belowSA = 2 * ((dBelow.x*dBelow.y + dBelow.x*dBelow.z + dBelow.y*dBelow.z));
00230 float aboveSA = 2 * ((dAbove.x*dAbove.y + dAbove.x*dAbove.z + dAbove.y*dAbove.z));
00231 float pBelow = belowSA * invTotalSA;
00232 float pAbove = aboveSA * invTotalSA;
00233 float eb = (nAbove == 0 || nBelow == 0) ? emptyBonus : 0.f;
00234 float cost = traversalCost + isectCost * (1.f - eb) * (pBelow * nBelow + pAbove * nAbove);
00235
00236 if (cost < bestCost) {
00237 bestCost = cost;
00238 *splitValue = splitVal;
00239 }
00240 }
00241 } else {
00242
00243 *splitValue = mean2[*bestAxis];
00244 }
00245 }
00246 }
00247
00248 u_int BVHAccel::BuildArray(boost::shared_ptr<BVHAccelTreeNode> node, u_int offset) {
00249
00250 while(node) {
00251 BVHAccelArrayNode* p = &bvhTree[offset];
00252
00253 p->bbox = node->bbox;
00254 p->primitive = node->primitive;
00255 offset = BuildArray(node->leftChild, offset+1);
00256 p->skipIndex = offset;
00257
00258 node = node->rightSibling;
00259 }
00260 return offset;
00261 }
00262
00263 BBox BVHAccel::WorldBound() const {
00264 return bvhTree[0].bbox;
00265 }
00266
00267 bool BVHAccel::Intersect(const Ray &ray,
00268 Intersection *isect) const {
00269 u_int currentNode = 0;
00270 u_int stopNode = bvhTree[0].skipIndex;
00271 bool hit = false;
00272
00273 while(currentNode < stopNode) {
00274 if(bvhTree[currentNode].bbox.IntersectP(ray)) {
00275 if(bvhTree[currentNode].primitive != NULL)
00276 if(bvhTree[currentNode].primitive->Intersect(ray, isect))
00277 hit = true;
00278 currentNode++;
00279 } else {
00280 currentNode = bvhTree[currentNode].skipIndex;
00281 }
00282 }
00283
00284 return hit;
00285 }
00286
00287 bool BVHAccel::IntersectP(const Ray &ray) const {
00288 u_int currentNode = 0;
00289 u_int stopNode = bvhTree[0].skipIndex;
00290
00291 while(currentNode < stopNode) {
00292 if(bvhTree[currentNode].bbox.IntersectP(ray)) {
00293 if(bvhTree[currentNode].primitive != NULL)
00294 if(bvhTree[currentNode].primitive->IntersectP(ray))
00295 return true;
00296 currentNode++;
00297 } else {
00298 currentNode = bvhTree[currentNode].skipIndex;
00299 }
00300 }
00301
00302 return false;
00303 }
00304
00305 void BVHAccel::GetPrimitives(vector<boost::shared_ptr<Primitive> > &primitives) {
00306 primitives.reserve(nPrims);
00307 for(u_int i=0; i<nPrims; i++) {
00308 primitives.push_back(prims[i]);
00309 }
00310 }
00311
00312 Aggregate* BVHAccel::CreateAccelerator(const vector<boost::shared_ptr<Primitive> > &prims,
00313 const ParamSet &ps) {
00314 int treeType = ps.FindOneInt("treetype", 4);
00315 int costSamples = ps.FindOneInt("costsamples", 0);
00316 int isectCost = ps.FindOneInt("intersectcost", 80);
00317 int travCost = ps.FindOneInt("traversalcost", 10);
00318 float emptyBonus = ps.FindOneFloat("emptybonus", 0.5f);
00319 return new BVHAccel(prims, treeType, costSamples, isectCost, travCost, emptyBonus);
00320
00321 }
00322
00323 static DynamicLoader::RegisterAccelerator<BVHAccel> r("bvh");