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 #include "pbrt.h"
00026 #include "primitive.h"
00027 static StatsRatio rayTests("Grid Accelerator", "Intersection tests per ray");
00028 static StatsRatio rayHits("Grid Accelerator", "Intersections found per ray");
00029
00030 struct MailboxPrim;
00031 struct Voxel;
00032
00033 struct MailboxPrim {
00034 MailboxPrim(const Reference<Primitive> &p) {
00035 primitive = p;
00036 lastMailboxId = -1;
00037 }
00038 Reference<Primitive> primitive;
00039 int lastMailboxId;
00040 };
00041
00042 struct Voxel {
00043
00044 Voxel(MailboxPrim *op) {
00045 allCanIntersect = false;
00046 nPrimitives = 1;
00047 onePrimitive = op;
00048 }
00049 void AddPrimitive(MailboxPrim *prim) {
00050 if (nPrimitives == 1) {
00051
00052 MailboxPrim **p = new MailboxPrim *[2];
00053 p[0] = onePrimitive;
00054 primitives = p;
00055 }
00056 else if (IsPowerOf2(nPrimitives)) {
00057
00058 int nAlloc = 2 * nPrimitives;
00059 MailboxPrim **p = new MailboxPrim *[nAlloc];
00060 for (u_int i = 0; i < nPrimitives; ++i)
00061 p[i] = primitives[i];
00062 delete[] primitives;
00063 primitives = p;
00064 }
00065 primitives[nPrimitives] = prim;
00066 ++nPrimitives;
00067 }
00068 ~Voxel() {
00069 if (nPrimitives > 1) delete[] primitives;
00070 }
00071 bool Intersect(const Ray &ray,
00072 Intersection *isect,
00073 int rayId);
00074 bool IntersectP(const Ray &ray, int rayId);
00075 union {
00076 MailboxPrim *onePrimitive;
00077 MailboxPrim **primitives;
00078 };
00079 u_int allCanIntersect:1;
00080 u_int nPrimitives:31;
00081 };
00082
00083 class GridAccel : public Aggregate {
00084 public:
00085
00086 GridAccel(const vector<Reference<Primitive> > &p,
00087 bool forRefined, bool refineImmediately);
00088 BBox WorldBound() const;
00089 bool CanIntersect() const { return true; }
00090 ~GridAccel();
00091 bool Intersect(const Ray &ray, Intersection *isect) const;
00092 bool IntersectP(const Ray &ray) const;
00093 private:
00094
00095 int PosToVoxel(const Point &P, int axis) const {
00096 int v = Float2Int((P[axis] - bounds.pMin[axis]) *
00097 InvWidth[axis]);
00098 return Clamp(v, 0, NVoxels[axis]-1);
00099 }
00100 float VoxelToPos(int p, int axis) const {
00101 return bounds.pMin[axis] + p * Width[axis];
00102 }
00103 Point VoxelToPos(int x, int y, int z) const {
00104 return bounds.pMin +
00105 Vector(x * Width[0], y * Width[1], z * Width[2]);
00106 }
00107 inline int Offset(int x, int y, int z) const {
00108 return z*NVoxels[0]*NVoxels[1] + y*NVoxels[0] + x;
00109 }
00110
00111 bool gridForRefined;
00112 u_int nMailboxes;
00113 MailboxPrim *mailboxes;
00114 int NVoxels[3];
00115 BBox bounds;
00116 Vector Width, InvWidth;
00117 Voxel **voxels;
00118 ObjectArena<Voxel> voxelArena;
00119 static int curMailboxId;
00120 };
00121
00122 GridAccel::GridAccel(const vector<Reference<Primitive> > &p,
00123 bool forRefined, bool refineImmediately)
00124 : gridForRefined(forRefined) {
00125
00126 vector<Reference<Primitive> > prims;
00127 if (refineImmediately)
00128 for (u_int i = 0; i < p.size(); ++i)
00129 p[i]->FullyRefine(prims);
00130 else
00131 prims = p;
00132
00133 nMailboxes = prims.size();
00134 mailboxes = (MailboxPrim *)AllocAligned(nMailboxes *
00135 sizeof(MailboxPrim));
00136 for (u_int i = 0; i < nMailboxes; ++i)
00137 new (&mailboxes[i]) MailboxPrim(prims[i]);
00138
00139 for (u_int i = 0; i < prims.size(); ++i)
00140 bounds = Union(bounds, prims[i]->WorldBound());
00141 Vector delta = bounds.pMax - bounds.pMin;
00142
00143 int maxAxis = bounds.MaximumExtent();
00144 float invMaxWidth = 1.f / delta[maxAxis];
00145 Assert(invMaxWidth > 0.f);
00146 float cubeRoot = 3.f * powf(float(prims.size()), 1.f/3.f);
00147 float voxelsPerUnitDist = cubeRoot * invMaxWidth;
00148 for (int axis = 0; axis < 3; ++axis) {
00149 NVoxels[axis] =
00150 Round2Int(delta[axis] * voxelsPerUnitDist);
00151 NVoxels[axis] = Clamp(NVoxels[axis], 1, 64);
00152 }
00153
00154 for (int axis = 0; axis < 3; ++axis) {
00155 Width[axis] = delta[axis] / NVoxels[axis];
00156 InvWidth[axis] =
00157 (Width[axis] == 0.f) ? 0.f : 1.f / Width[axis];
00158 }
00159 int nVoxels = NVoxels[0] * NVoxels[1] * NVoxels[2];
00160 voxels = (Voxel **)AllocAligned(nVoxels * sizeof(Voxel *));
00161 memset(voxels, 0, nVoxels * sizeof(Voxel *));
00162
00163 for (u_int i = 0; i < prims.size(); ++i) {
00164
00165 BBox pb = prims[i]->WorldBound();
00166 int vmin[3], vmax[3];
00167 for (int axis = 0; axis < 3; ++axis) {
00168 vmin[axis] = PosToVoxel(pb.pMin, axis);
00169 vmax[axis] = PosToVoxel(pb.pMax, axis);
00170 }
00171
00172 for (int z = vmin[2]; z <= vmax[2]; ++z)
00173 for (int y = vmin[1]; y <= vmax[1]; ++y)
00174 for (int x = vmin[0]; x <= vmax[0]; ++x) {
00175 int offset = Offset(x, y, z);
00176 if (!voxels[offset]) {
00177
00178 voxels[offset] = new (voxelArena) Voxel(&mailboxes[i]);
00179 }
00180 else {
00181
00182 voxels[offset]->AddPrimitive(&mailboxes[i]);
00183 }
00184 }
00185 static StatsRatio nPrimitiveVoxels("Grid Accelerator",
00186 "Voxels covered vs # / primitives");
00187 nPrimitiveVoxels.Add((1 + vmax[0]-vmin[0]) * (1 + vmax[1]-vmin[1]) *
00188 (1 + vmax[2]-vmin[2]), 1);
00189 }
00190
00191 static StatsPercentage nEmptyVoxels("Grid Accelerator",
00192 "Empty voxels");
00193 static StatsRatio avgPrimsInVoxel("Grid Accelerator",
00194 "Average # of primitives in voxel");
00195 static StatsCounter maxPrimsInVoxel("Grid Accelerator",
00196 "Max # of primitives in a grid voxel");
00197 nEmptyVoxels.Add(0, NVoxels[0] * NVoxels[1] * NVoxels[2]);
00198 avgPrimsInVoxel.Add(0,NVoxels[0] * NVoxels[1] * NVoxels[2]);
00199 for (int z = 0; z < NVoxels[2]; ++z)
00200 for (int y = 0; y < NVoxels[1]; ++y)
00201 for (int x = 0; x < NVoxels[0]; ++x) {
00202 int offset = Offset(x, y, z);
00203 if (!voxels[offset]) nEmptyVoxels.Add(1, 0);
00204 else {
00205 int nPrims = voxels[offset]->nPrimitives;
00206 maxPrimsInVoxel.Max(nPrims);
00207 avgPrimsInVoxel.Add(nPrims, 0);
00208 }
00209 }
00210 }
00211 BBox GridAccel::WorldBound() const {
00212 return bounds;
00213 }
00214 GridAccel::~GridAccel() {
00215 for (u_int i = 0; i < nMailboxes; ++i)
00216 mailboxes[i].~MailboxPrim();
00217 FreeAligned(mailboxes);
00218 for (int i = 0;
00219 i < NVoxels[0]*NVoxels[1]*NVoxels[2];
00220 ++i)
00221 if (voxels[i]) voxels[i]->~Voxel();
00222 FreeAligned(voxels);
00223 }
00224 bool GridAccel::Intersect(const Ray &ray,
00225 Intersection *isect) const {
00226 if (!gridForRefined) {
00227 rayTests.Add(0, 1);
00228 rayHits.Add(0, 1);
00229 }
00230
00231 float rayT;
00232 if (bounds.Inside(ray(ray.mint)))
00233 rayT = ray.mint;
00234 else if (!bounds.IntersectP(ray, &rayT))
00235 return false;
00236 Point gridIntersect = ray(rayT);
00237
00238 int rayId = ++curMailboxId;
00239
00240 float NextCrossingT[3], DeltaT[3];
00241 int Step[3], Out[3], Pos[3];
00242 for (int axis = 0; axis < 3; ++axis) {
00243
00244 Pos[axis] = PosToVoxel(gridIntersect, axis);
00245 if (ray.d[axis] >= 0) {
00246
00247 NextCrossingT[axis] = rayT +
00248 (VoxelToPos(Pos[axis]+1, axis) - gridIntersect[axis]) /
00249 ray.d[axis];
00250 DeltaT[axis] = Width[axis] / ray.d[axis];
00251 Step[axis] = 1;
00252 Out[axis] = NVoxels[axis];
00253 }
00254 else {
00255
00256 NextCrossingT[axis] = rayT +
00257 (VoxelToPos(Pos[axis], axis) - gridIntersect[axis]) /
00258 ray.d[axis];
00259 DeltaT[axis] = -Width[axis] / ray.d[axis];
00260 Step[axis] = -1;
00261 Out[axis] = -1;
00262 }
00263 }
00264
00265 bool hitSomething = false;
00266 for (;;) {
00267 Voxel *voxel =
00268 voxels[Offset(Pos[0], Pos[1], Pos[2])];
00269 if (voxel != NULL)
00270 hitSomething |= voxel->Intersect(ray, isect, rayId);
00271
00272
00273 int bits = ((NextCrossingT[0] < NextCrossingT[1]) << 2) +
00274 ((NextCrossingT[0] < NextCrossingT[2]) << 1) +
00275 ((NextCrossingT[1] < NextCrossingT[2]));
00276 const int cmpToAxis[8] = { 2, 1, 2, 1, 2, 2, 0, 0 };
00277 int stepAxis = cmpToAxis[bits];
00278 if (ray.maxt < NextCrossingT[stepAxis])
00279 break;
00280 Pos[stepAxis] += Step[stepAxis];
00281 if (Pos[stepAxis] == Out[stepAxis])
00282 break;
00283 NextCrossingT[stepAxis] += DeltaT[stepAxis];
00284 }
00285 return hitSomething;
00286 }
00287 int GridAccel::curMailboxId = 0;
00288 bool Voxel::Intersect(const Ray &ray,
00289 Intersection *isect,
00290 int rayId) {
00291
00292 if (!allCanIntersect) {
00293 MailboxPrim **mpp;
00294 if (nPrimitives == 1) mpp = &onePrimitive;
00295 else mpp = primitives;
00296 for (u_int i = 0; i < nPrimitives; ++i) {
00297 MailboxPrim *mp = mpp[i];
00298
00299 if (!mp->primitive->CanIntersect()) {
00300 vector<Reference<Primitive> > p;
00301 mp->primitive->FullyRefine(p);
00302 Assert(p.size() > 0);
00303 if (p.size() == 1)
00304 mp->primitive = p[0];
00305 else
00306 mp->primitive = new GridAccel(p, true, false);
00307 }
00308 }
00309 allCanIntersect = true;
00310 }
00311
00312 bool hitSomething = false;
00313 MailboxPrim **mpp;
00314 if (nPrimitives == 1) mpp = &onePrimitive;
00315 else mpp = primitives;
00316 for (u_int i = 0; i < nPrimitives; ++i) {
00317 MailboxPrim *mp = mpp[i];
00318
00319 if (mp->lastMailboxId == rayId)
00320 continue;
00321
00322 mp->lastMailboxId = rayId;
00323 rayTests.Add(1, 0);
00324 if (mp->primitive->Intersect(ray, isect)) {
00325 rayHits.Add(1, 0);
00326 hitSomething = true;
00327 }
00328 }
00329 return hitSomething;
00330 }
00331 bool GridAccel::IntersectP(const Ray &ray) const {
00332 if (!gridForRefined) {
00333 rayTests.Add(0, 1);
00334 rayHits.Add(0, 1);
00335 }
00336 int rayId = ++curMailboxId;
00337
00338 float rayT;
00339 if (bounds.Inside(ray(ray.mint)))
00340 rayT = ray.mint;
00341 else if (!bounds.IntersectP(ray, &rayT))
00342 return false;
00343 Point gridIntersect = ray(rayT);
00344
00345 float NextCrossingT[3], DeltaT[3];
00346 int Step[3], Out[3], Pos[3];
00347 for (int axis = 0; axis < 3; ++axis) {
00348
00349 Pos[axis] = PosToVoxel(gridIntersect, axis);
00350 if (ray.d[axis] >= 0) {
00351
00352 NextCrossingT[axis] = rayT +
00353 (VoxelToPos(Pos[axis]+1, axis) - gridIntersect[axis]) /
00354 ray.d[axis];
00355 DeltaT[axis] = Width[axis] / ray.d[axis];
00356 Step[axis] = 1;
00357 Out[axis] = NVoxels[axis];
00358 }
00359 else {
00360
00361 NextCrossingT[axis] = rayT +
00362 (VoxelToPos(Pos[axis], axis) - gridIntersect[axis]) /
00363 ray.d[axis];
00364 DeltaT[axis] = -Width[axis] / ray.d[axis];
00365 Step[axis] = -1;
00366 Out[axis] = -1;
00367 }
00368 }
00369
00370 for (;;) {
00371 int offset = Offset(Pos[0], Pos[1], Pos[2]);
00372 Voxel *voxel = voxels[offset];
00373 if (voxel && voxel->IntersectP(ray, rayId))
00374 return true;
00375
00376
00377 int bits = ((NextCrossingT[0] < NextCrossingT[1]) << 2) +
00378 ((NextCrossingT[0] < NextCrossingT[2]) << 1) +
00379 ((NextCrossingT[1] < NextCrossingT[2]));
00380 const int cmpToAxis[8] = { 2, 1, 2, 1, 2, 2, 0, 0 };
00381 int stepAxis = cmpToAxis[bits];
00382 if (ray.maxt < NextCrossingT[stepAxis])
00383 break;
00384 Pos[stepAxis] += Step[stepAxis];
00385 if (Pos[stepAxis] == Out[stepAxis])
00386 break;
00387 NextCrossingT[stepAxis] += DeltaT[stepAxis];
00388 }
00389 return false;
00390 }
00391 bool Voxel::IntersectP(const Ray &ray, int rayId) {
00392
00393 if (!allCanIntersect) {
00394 MailboxPrim **mpp;
00395 if (nPrimitives == 1) mpp = &onePrimitive;
00396 else mpp = primitives;
00397 for (u_int i = 0; i < nPrimitives; ++i) {
00398 MailboxPrim *mp = mpp[i];
00399
00400 if (!mp->primitive->CanIntersect()) {
00401 vector<Reference<Primitive> > p;
00402 mp->primitive->FullyRefine(p);
00403 Assert(p.size() > 0);
00404 if (p.size() == 1)
00405 mp->primitive = p[0];
00406 else
00407 mp->primitive = new GridAccel(p, true, false);
00408 }
00409 }
00410 allCanIntersect = true;
00411 }
00412 MailboxPrim **mpp;
00413 if (nPrimitives == 1) mpp = &onePrimitive;
00414 else mpp = primitives;
00415 for (u_int i = 0; i < nPrimitives; ++i) {
00416 MailboxPrim *mp = mpp[i];
00417
00418 if (mp->lastMailboxId == rayId)
00419 continue;
00420
00421 mp->lastMailboxId = rayId;
00422 rayTests.Add(1, 0);
00423 if (mp->primitive->IntersectP(ray)) {
00424 rayHits.Add(1, 0);
00425 return true;
00426 }
00427 }
00428 return false;
00429 }
00430 extern "C" DLLEXPORT Primitive *CreateAccelerator(const vector<Reference<Primitive> > &prims,
00431 const ParamSet &ps) {
00432 bool refineImmediately = ps.FindOneBool("refineimmediately", false);
00433 return new GridAccel(prims, false, refineImmediately);
00434 }