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