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