00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 #include "unsafekdtreeaccel.h"
00025 #include "paramset.h"
00026 #include "dynload.h"
00027
00028 using namespace lux;
00029
00030
00031 UnsafeKdTreeAccel::
00032 UnsafeKdTreeAccel(const vector<boost::shared_ptr<Primitive> > &p,
00033 int icost, int tcost,
00034 float ebonus, int maxp, int maxDepth)
00035 : isectCost(icost), traversalCost(tcost),
00036 maxPrims(maxp), emptyBonus(ebonus) {
00037 vector<boost::shared_ptr<Primitive> > prims;
00038 PrimitiveRefinementHints refineHints(false);
00039 for (u_int i = 0; i < p.size(); ++i) {
00040 if(p[i]->CanIntersect())
00041 prims.push_back(p[i]);
00042 else
00043 p[i]->Refine(prims, refineHints, p[i]);
00044 }
00045
00046 curMailboxId = 0;
00047 nMailboxes = prims.size();
00048 mailboxPrims = AllocAligned<MailboxPrim>(nMailboxes);
00049 for (u_int i = 0; i < nMailboxes; ++i)
00050 new (&mailboxPrims[i]) MailboxPrim(prims[i]);
00051
00052 nextFreeNode = nAllocedNodes = 0;
00053 if (maxDepth <= 0)
00054 maxDepth =
00055 Round2Int(8 + 1.3f * Log2Int(float(prims.size())));
00056
00057 vector<BBox> primBounds;
00058 primBounds.reserve(prims.size());
00059 for (u_int i = 0; i < prims.size(); ++i) {
00060 BBox b = prims[i]->WorldBound();
00061 bounds = Union(bounds, b);
00062 primBounds.push_back(b);
00063 }
00064
00065 UnsafeBoundEdge *edges[3];
00066 for (int i = 0; i < 3; ++i)
00067 edges[i] = new UnsafeBoundEdge[2*prims.size()];
00068 int *prims0 = new int[prims.size()];
00069 int *prims1 = new int[(maxDepth+1) * prims.size()];
00070
00071 int *primNums = new int[prims.size()];
00072 for (u_int i = 0; i < prims.size(); ++i)
00073 primNums[i] = i;
00074
00075 buildTree(0, bounds, primBounds, primNums,
00076 prims.size(), maxDepth, edges,
00077 prims0, prims1);
00078
00079 delete[] primNums;
00080 for (int i = 0; i < 3; ++i)
00081 delete[] edges[i];
00082 delete[] prims0;
00083 delete[] prims1;
00084 }
00085
00086 UnsafeKdTreeAccel::~UnsafeKdTreeAccel() {
00087 for (u_int i = 0; i < nMailboxes; ++i)
00088 mailboxPrims[i].~MailboxPrim();
00089 FreeAligned(mailboxPrims);
00090 FreeAligned(nodes);
00091 }
00092
00093 void UnsafeKdTreeAccel::buildTree(int nodeNum,
00094 const BBox &nodeBounds,
00095 const vector<BBox> &allPrimBounds, int *primNums,
00096 int nPrims, int depth, UnsafeBoundEdge *edges[3],
00097 int *prims0, int *prims1, int badRefines) {
00098 BOOST_ASSERT(nodeNum == nextFreeNode);
00099
00100 if (nextFreeNode == nAllocedNodes) {
00101 int nAlloc = max(2 * nAllocedNodes, 512);
00102 UnsafeKdAccelNode *n = AllocAligned<UnsafeKdAccelNode>(nAlloc);
00103 if (nAllocedNodes > 0) {
00104 memcpy(n, nodes,
00105 nAllocedNodes * sizeof(UnsafeKdAccelNode));
00106 FreeAligned(nodes);
00107 }
00108 nodes = n;
00109 nAllocedNodes = nAlloc;
00110 }
00111 ++nextFreeNode;
00112
00113 if (nPrims <= maxPrims || depth == 0) {
00114 nodes[nodeNum].initLeaf(primNums, nPrims,
00115 mailboxPrims, arena);
00116 return;
00117 }
00118
00119
00120 int bestAxis = -1, bestOffset = -1;
00121 float bestCost = INFINITY;
00122 float oldCost = isectCost * float(nPrims);
00123 Vector d = nodeBounds.pMax - nodeBounds.pMin;
00124 float totalSA = (2.f * (d.x*d.y + d.x*d.z + d.y*d.z));
00125 float invTotalSA = 1.f / totalSA;
00126
00127 int axis;
00128 if (d.x > d.y && d.x > d.z) axis = 0;
00129 else axis = (d.y > d.z) ? 1 : 2;
00130 int retries = 0;
00131 retrySplit:
00132
00133 for (int i = 0; i < nPrims; ++i) {
00134 int pn = primNums[i];
00135 const BBox &bbox = allPrimBounds[pn];
00136 edges[axis][2*i] =
00137 UnsafeBoundEdge(bbox.pMin[axis], pn, true);
00138 edges[axis][2*i+1] =
00139 UnsafeBoundEdge(bbox.pMax[axis], pn, false);
00140 }
00141 sort(&edges[axis][0], &edges[axis][2*nPrims]);
00142
00143 int nBelow = 0, nAbove = nPrims;
00144 for (int i = 0; i < 2*nPrims; ++i) {
00145 if (edges[axis][i].type == UnsafeBoundEdge::END) --nAbove;
00146 float edget = edges[axis][i].t;
00147 if (edget > nodeBounds.pMin[axis] &&
00148 edget < nodeBounds.pMax[axis]) {
00149
00150 int otherAxis[3][2] = { {1, 2}, {0, 2}, {0, 1} };
00151 int otherAxis0 = otherAxis[axis][0];
00152 int otherAxis1 = otherAxis[axis][1];
00153 float belowSA = 2 * (d[otherAxis0] * d[otherAxis1] +
00154 (edget - nodeBounds.pMin[axis]) *
00155 (d[otherAxis0] + d[otherAxis1]));
00156 float aboveSA = 2 * (d[otherAxis0] * d[otherAxis1] +
00157 (nodeBounds.pMax[axis] - edget) *
00158 (d[otherAxis0] + d[otherAxis1]));
00159 float pBelow = belowSA * invTotalSA;
00160 float pAbove = aboveSA * invTotalSA;
00161 float eb = (nAbove == 0 || nBelow == 0) ? emptyBonus : 0.f;
00162 float cost = traversalCost + isectCost * (1.f - eb) *
00163 (pBelow * nBelow + pAbove * nAbove);
00164
00165 if (cost < bestCost) {
00166 bestCost = cost;
00167 bestAxis = axis;
00168 bestOffset = i;
00169 }
00170 }
00171 if (edges[axis][i].type == UnsafeBoundEdge::START) ++nBelow;
00172 }
00173 BOOST_ASSERT(nBelow == nPrims && nAbove == 0);
00174
00175 if (bestAxis == -1 && retries < 2) {
00176 ++retries;
00177 axis = (axis+1) % 3;
00178 goto retrySplit;
00179 }
00180 if (bestCost > oldCost) ++badRefines;
00181 if ((bestCost > 4.f * oldCost && nPrims < 16) ||
00182 bestAxis == -1 || badRefines == 3) {
00183 nodes[nodeNum].initLeaf(primNums, nPrims,
00184 mailboxPrims, arena);
00185 return;
00186 }
00187
00188 int n0 = 0, n1 = 0;
00189 for (int i = 0; i < bestOffset; ++i)
00190 if (edges[bestAxis][i].type == UnsafeBoundEdge::START)
00191 prims0[n0++] = edges[bestAxis][i].primNum;
00192 for (int i = bestOffset+1; i < 2*nPrims; ++i)
00193 if (edges[bestAxis][i].type == UnsafeBoundEdge::END)
00194 prims1[n1++] = edges[bestAxis][i].primNum;
00195
00196 float tsplit = edges[bestAxis][bestOffset].t;
00197 nodes[nodeNum].initInterior(bestAxis, tsplit);
00198 BBox bounds0 = nodeBounds, bounds1 = nodeBounds;
00199 bounds0.pMax[bestAxis] = bounds1.pMin[bestAxis] = tsplit;
00200 buildTree(nodeNum+1, bounds0,
00201 allPrimBounds, prims0, n0, depth-1, edges,
00202 prims0, prims1 + nPrims, badRefines);
00203 nodes[nodeNum].aboveChild = nextFreeNode;
00204 buildTree(nodes[nodeNum].aboveChild, bounds1, allPrimBounds,
00205 prims1, n1, depth-1, edges,
00206 prims0, prims1 + nPrims, badRefines);
00207 }
00208
00209 bool UnsafeKdTreeAccel::Intersect(const Ray &ray,
00210 Intersection *isect) const {
00211
00212 float tmin, tmax;
00213 if (!bounds.IntersectP(ray, &tmin, &tmax))
00214 return false;
00215
00216 int rayId = curMailboxId++;
00217 Vector invDir(1.f/ray.d.x, 1.f/ray.d.y, 1.f/ray.d.z);
00218 #define MAX_TODO 64
00219 KdToDo todo[MAX_TODO];
00220 int todoPos = 0;
00221
00222 bool hit = false;
00223 const UnsafeKdAccelNode *node = &nodes[0];
00224 while (node != NULL) {
00225
00226 if (ray.maxt < tmin) break;
00227
00228
00229
00230 if (!node->IsLeaf()) {
00231
00232
00233 int axis = node->SplitAxis();
00234 float tplane = (node->SplitPos() - ray.o[axis]) *
00235 invDir[axis];
00236
00237 const UnsafeKdAccelNode *firstChild, *secondChild;
00238
00239 int belowFirst = (ray.o[axis] < node->SplitPos()) ||
00240 (ray.o[axis] == node->SplitPos() && ray.d[axis] < 0);
00241 if (belowFirst) {
00242 firstChild = node + 1;
00243 secondChild = &nodes[node->aboveChild];
00244 }
00245 else {
00246 firstChild = &nodes[node->aboveChild];
00247 secondChild = node + 1;
00248 }
00249
00250
00251
00252 if (tplane > tmax || tplane <= 0)
00253 node = firstChild;
00254 else if (tplane < tmin)
00255 node = secondChild;
00256 else {
00257
00258 todo[todoPos].node = secondChild;
00259 todo[todoPos].tmin = tplane;
00260 todo[todoPos].tmax = tmax;
00261 ++todoPos;
00262 node = firstChild;
00263 tmax = tplane;
00264 }
00265 }
00266 else {
00267
00268 u_int nPrimitives = node->nPrimitives();
00269 if (nPrimitives == 1) {
00270 MailboxPrim *mp = node->onePrimitive;
00271
00272 if (mp->lastMailboxId != rayId) {
00273 mp->lastMailboxId = rayId;
00274 if (mp->primitive->Intersect(ray, isect))
00275 hit = true;
00276 }
00277 }
00278 else {
00279 MailboxPrim **prims = node->primitives;
00280 for (u_int i = 0; i < nPrimitives; ++i) {
00281 MailboxPrim *mp = prims[i];
00282
00283 if (mp->lastMailboxId != rayId) {
00284 mp->lastMailboxId = rayId;
00285 if (mp->primitive->Intersect(ray, isect))
00286 hit = true;
00287 }
00288 }
00289 }
00290
00291 if (todoPos > 0) {
00292 --todoPos;
00293 node = todo[todoPos].node;
00294 tmin = todo[todoPos].tmin;
00295 tmax = todo[todoPos].tmax;
00296 }
00297 else
00298 break;
00299 }
00300 }
00301 return hit;
00302 }
00303
00304 bool UnsafeKdTreeAccel::IntersectP(const Ray &ray) const {
00305
00306 float tmin, tmax;
00307 if (!bounds.IntersectP(ray, &tmin, &tmax))
00308 return false;
00309
00310 int rayId = curMailboxId++;
00311 Vector invDir(1.f/ray.d.x, 1.f/ray.d.y, 1.f/ray.d.z);
00312 #define MAX_TODO 64
00313 KdToDo todo[MAX_TODO];
00314 int todoPos = 0;
00315 const UnsafeKdAccelNode *node = &nodes[0];
00316 while (node != NULL) {
00317
00318
00319
00320
00321 if (node->IsLeaf()) {
00322
00323 u_int nPrimitives = node->nPrimitives();
00324 if (nPrimitives == 1) {
00325 MailboxPrim *mp = node->onePrimitive;
00326 if (mp->lastMailboxId != rayId) {
00327 mp->lastMailboxId = rayId;
00328 if (mp->primitive->IntersectP(ray))
00329 return true;
00330 }
00331 }
00332 else {
00333 MailboxPrim **prims = node->primitives;
00334 for (u_int i = 0; i < nPrimitives; ++i) {
00335 MailboxPrim *mp = prims[i];
00336 if (mp->lastMailboxId != rayId) {
00337 mp->lastMailboxId = rayId;
00338 if (mp->primitive->IntersectP(ray))
00339 return true;
00340 }
00341 }
00342 }
00343
00344 if (todoPos > 0) {
00345 --todoPos;
00346 node = todo[todoPos].node;
00347 tmin = todo[todoPos].tmin;
00348 tmax = todo[todoPos].tmax;
00349 }
00350 else
00351 break;
00352 }
00353 else {
00354
00355
00356 int axis = node->SplitAxis();
00357 float tplane = (node->SplitPos() - ray.o[axis]) *
00358 invDir[axis];
00359
00360 const UnsafeKdAccelNode *firstChild, *secondChild;
00361
00362 int belowFirst = (ray.o[axis] < node->SplitPos()) ||
00363 (ray.o[axis] == node->SplitPos() && ray.d[axis] < 0);
00364 if (belowFirst) {
00365 firstChild = node + 1;
00366 secondChild = &nodes[node->aboveChild];
00367 }
00368 else {
00369 firstChild = &nodes[node->aboveChild];
00370 secondChild = node + 1;
00371 }
00372
00373
00374
00375 if (tplane > tmax || tplane <= 0)
00376 node = firstChild;
00377 else if (tplane < tmin)
00378 node = secondChild;
00379 else {
00380
00381 todo[todoPos].node = secondChild;
00382 todo[todoPos].tmin = tplane;
00383 todo[todoPos].tmax = tmax;
00384 ++todoPos;
00385 node = firstChild;
00386 tmax = tplane;
00387 }
00388 }
00389 }
00390 return false;
00391 }
00392
00393 void UnsafeKdTreeAccel::GetPrimitives(vector<boost::shared_ptr<Primitive> > &primitives) {
00394 primitives.reserve(nMailboxes);
00395 for(u_int i=0; i < nMailboxes; i++) {
00396 primitives.push_back(mailboxPrims[i].primitive);
00397 }
00398 }
00399
00400 Aggregate *UnsafeKdTreeAccel::CreateAccelerator(const vector<boost::shared_ptr<Primitive> > &prims,
00401 const ParamSet &ps) {
00402 int isectCost = ps.FindOneInt("intersectcost", 80);
00403 int travCost = ps.FindOneInt("traversalcost", 1);
00404 float emptyBonus = ps.FindOneFloat("emptybonus", 0.5f);
00405 int maxPrims = ps.FindOneInt("maxprims", 1);
00406 int maxDepth = ps.FindOneInt("maxdepth", -1);
00407 return new UnsafeKdTreeAccel(prims, isectCost, travCost,
00408 emptyBonus, maxPrims, maxDepth);
00409 }
00410
00411 static DynamicLoader::RegisterAccelerator<UnsafeKdTreeAccel> r("unsafekdtree");