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 #include "stdafx.h"
00027 #include "accelerators/grid.h"
00028 #include "probes.h"
00029 #include "paramset.h"
00030
00031
00032 GridAccel::GridAccel(const vector<Reference<Primitive> > &p,
00033 bool refineImmediately) {
00034 PBRT_GRID_STARTED_CONSTRUCTION(this, p.size());
00035
00036 if (refineImmediately)
00037 for (uint32_t i = 0; i < p.size(); ++i)
00038 p[i]->FullyRefine(primitives);
00039 else
00040 primitives = p;
00041
00042
00043 for (uint32_t i = 0; i < primitives.size(); ++i)
00044 bounds = Union(bounds, primitives[i]->WorldBound());
00045 Vector delta = bounds.pMax - bounds.pMin;
00046
00047
00048 int maxAxis = bounds.MaximumExtent();
00049 float invMaxWidth = 1.f / delta[maxAxis];
00050 Assert(invMaxWidth > 0.f);
00051 float cubeRoot = 3.f * powf(float(primitives.size()), 1.f/3.f);
00052 float voxelsPerUnitDist = cubeRoot * invMaxWidth;
00053 for (int axis = 0; axis < 3; ++axis) {
00054 nVoxels[axis] = Round2Int(delta[axis] * voxelsPerUnitDist);
00055 nVoxels[axis] = Clamp(nVoxels[axis], 1, 64);
00056 }
00057 PBRT_GRID_BOUNDS_AND_RESOLUTION(&bounds, nVoxels);
00058
00059
00060 for (int axis = 0; axis < 3; ++axis) {
00061 width[axis] = delta[axis] / nVoxels[axis];
00062 invWidth[axis] = (width[axis] == 0.f) ? 0.f : 1.f / width[axis];
00063 }
00064 int nv = nVoxels[0] * nVoxels[1] * nVoxels[2];
00065 voxels = AllocAligned<Voxel *>(nv);
00066 memset(voxels, 0, nv * sizeof(Voxel *));
00067
00068
00069 for (uint32_t i = 0; i < primitives.size(); ++i) {
00070
00071 BBox pb = primitives[i]->WorldBound();
00072 int vmin[3], vmax[3];
00073 for (int axis = 0; axis < 3; ++axis) {
00074 vmin[axis] = posToVoxel(pb.pMin, axis);
00075 vmax[axis] = posToVoxel(pb.pMax, axis);
00076 }
00077
00078
00079 PBRT_GRID_VOXELIZED_PRIMITIVE(vmin, vmax);
00080 for (int z = vmin[2]; z <= vmax[2]; ++z)
00081 for (int y = vmin[1]; y <= vmax[1]; ++y)
00082 for (int x = vmin[0]; x <= vmax[0]; ++x) {
00083 int o = offset(x, y, z);
00084 if (!voxels[o]) {
00085
00086 voxels[o] = voxelArena.Alloc<Voxel>();
00087 *voxels[o] = Voxel(primitives[i]);
00088 }
00089 else {
00090
00091 voxels[o]->AddPrimitive(primitives[i]);
00092 }
00093 }
00094 }
00095
00096
00097 rwMutex = RWMutex::Create();
00098 PBRT_GRID_FINISHED_CONSTRUCTION(this);
00099 }
00100
00101
00102 BBox GridAccel::WorldBound() const {
00103 return bounds;
00104 }
00105
00106
00107 GridAccel::~GridAccel() {
00108 for (int i = 0; i < nVoxels[0]*nVoxels[1]*nVoxels[2]; ++i)
00109 if (voxels[i]) voxels[i]->~Voxel();
00110 FreeAligned(voxels);
00111 RWMutex::Destroy(rwMutex);
00112 }
00113
00114
00115 bool GridAccel::Intersect(const Ray &ray, Intersection *isect) const {
00116 PBRT_GRID_INTERSECTION_TEST(const_cast<GridAccel *>(this), const_cast<Ray *>(&ray));
00117
00118 float rayT;
00119 if (bounds.Inside(ray(ray.mint)))
00120 rayT = ray.mint;
00121 else if (!bounds.IntersectP(ray, &rayT))
00122 {
00123 PBRT_GRID_RAY_MISSED_BOUNDS();
00124 return false;
00125 }
00126 Point gridIntersect = ray(rayT);
00127
00128
00129 float NextCrossingT[3], DeltaT[3];
00130 int Step[3], Out[3], Pos[3];
00131 for (int axis = 0; axis < 3; ++axis) {
00132
00133 Pos[axis] = posToVoxel(gridIntersect, axis);
00134 if (ray.d[axis] >= 0) {
00135
00136 NextCrossingT[axis] = rayT +
00137 (voxelToPos(Pos[axis]+1, axis) - gridIntersect[axis]) / ray.d[axis];
00138 DeltaT[axis] = width[axis] / ray.d[axis];
00139 Step[axis] = 1;
00140 Out[axis] = nVoxels[axis];
00141 }
00142 else {
00143
00144 NextCrossingT[axis] = rayT +
00145 (voxelToPos(Pos[axis], axis) - gridIntersect[axis]) / ray.d[axis];
00146 DeltaT[axis] = -width[axis] / ray.d[axis];
00147 Step[axis] = -1;
00148 Out[axis] = -1;
00149 }
00150 }
00151
00152
00153 RWMutexLock lock(*rwMutex, READ);
00154 bool hitSomething = false;
00155 for (;;) {
00156
00157 Voxel *voxel = voxels[offset(Pos[0], Pos[1], Pos[2])];
00158 PBRT_GRID_RAY_TRAVERSED_VOXEL(Pos, voxel ? voxel->size() : 0);
00159 if (voxel != NULL)
00160 hitSomething |= voxel->Intersect(ray, isect, lock);
00161
00162
00163
00164
00165 int bits = ((NextCrossingT[0] < NextCrossingT[1]) << 2) +
00166 ((NextCrossingT[0] < NextCrossingT[2]) << 1) +
00167 ((NextCrossingT[1] < NextCrossingT[2]));
00168 const int cmpToAxis[8] = { 2, 1, 2, 1, 2, 2, 0, 0 };
00169 int stepAxis = cmpToAxis[bits];
00170 if (ray.maxt < NextCrossingT[stepAxis])
00171 break;
00172 Pos[stepAxis] += Step[stepAxis];
00173 if (Pos[stepAxis] == Out[stepAxis])
00174 break;
00175 NextCrossingT[stepAxis] += DeltaT[stepAxis];
00176 }
00177 return hitSomething;
00178 }
00179
00180
00181 bool Voxel::Intersect(const Ray &ray, Intersection *isect,
00182 RWMutexLock &lock) {
00183
00184 if (!allCanIntersect) {
00185 lock.UpgradeToWrite();
00186 for (uint32_t i = 0; i < primitives.size(); ++i) {
00187 Reference<Primitive> &prim = primitives[i];
00188
00189 if (!prim->CanIntersect()) {
00190 vector<Reference<Primitive> > p;
00191 prim->FullyRefine(p);
00192 Assert(p.size() > 0);
00193 if (p.size() == 1)
00194 primitives[i] = p[0];
00195 else
00196 primitives[i] = new GridAccel(p, false);
00197 }
00198 }
00199 allCanIntersect = true;
00200 lock.DowngradeToRead();
00201 }
00202
00203
00204 bool hitSomething = false;
00205 for (uint32_t i = 0; i < primitives.size(); ++i) {
00206 Reference<Primitive> &prim = primitives[i];
00207 PBRT_GRID_RAY_PRIMITIVE_INTERSECTION_TEST(const_cast<Primitive *>(prim.GetPtr()));
00208 if (prim->Intersect(ray, isect))
00209 {
00210 PBRT_GRID_RAY_PRIMITIVE_HIT(const_cast<Primitive *>(prim.GetPtr()));
00211 hitSomething = true;
00212 }
00213 }
00214 return hitSomething;
00215 }
00216
00217
00218 bool GridAccel::IntersectP(const Ray &ray) const {
00219 PBRT_GRID_INTERSECTIONP_TEST(const_cast<GridAccel *>(this), const_cast<Ray *>(&ray));
00220 RWMutexLock lock(*rwMutex, READ);
00221
00222 float rayT;
00223 if (bounds.Inside(ray(ray.mint)))
00224 rayT = ray.mint;
00225 else if (!bounds.IntersectP(ray, &rayT))
00226 {
00227 PBRT_GRID_RAY_MISSED_BOUNDS();
00228 return false;
00229 }
00230 Point gridIntersect = ray(rayT);
00231
00232
00233 float NextCrossingT[3], DeltaT[3];
00234 int Step[3], Out[3], Pos[3];
00235 for (int axis = 0; axis < 3; ++axis) {
00236
00237 Pos[axis] = posToVoxel(gridIntersect, axis);
00238 if (ray.d[axis] >= 0) {
00239
00240 NextCrossingT[axis] = rayT +
00241 (voxelToPos(Pos[axis]+1, axis) - gridIntersect[axis]) / ray.d[axis];
00242 DeltaT[axis] = width[axis] / ray.d[axis];
00243 Step[axis] = 1;
00244 Out[axis] = nVoxels[axis];
00245 }
00246 else {
00247
00248 NextCrossingT[axis] = rayT +
00249 (voxelToPos(Pos[axis], axis) - gridIntersect[axis]) / ray.d[axis];
00250 DeltaT[axis] = -width[axis] / ray.d[axis];
00251 Step[axis] = -1;
00252 Out[axis] = -1;
00253 }
00254 }
00255
00256
00257 for (;;) {
00258 int o = offset(Pos[0], Pos[1], Pos[2]);
00259 Voxel *voxel = voxels[o];
00260 PBRT_GRID_RAY_TRAVERSED_VOXEL(Pos, voxel ? voxel->size() : 0);
00261 if (voxel && voxel->IntersectP(ray, lock))
00262 return true;
00263
00264
00265
00266 int bits = ((NextCrossingT[0] < NextCrossingT[1]) << 2) +
00267 ((NextCrossingT[0] < NextCrossingT[2]) << 1) +
00268 ((NextCrossingT[1] < NextCrossingT[2]));
00269 const int cmpToAxis[8] = { 2, 1, 2, 1, 2, 2, 0, 0 };
00270 int stepAxis = cmpToAxis[bits];
00271 if (ray.maxt < NextCrossingT[stepAxis])
00272 break;
00273 Pos[stepAxis] += Step[stepAxis];
00274 if (Pos[stepAxis] == Out[stepAxis])
00275 break;
00276 NextCrossingT[stepAxis] += DeltaT[stepAxis];
00277 }
00278 return false;
00279 }
00280
00281
00282 bool Voxel::IntersectP(const Ray &ray, RWMutexLock &lock) {
00283
00284 if (!allCanIntersect) {
00285 lock.UpgradeToWrite();
00286 for (uint32_t i = 0; i < primitives.size(); ++i) {
00287 Reference<Primitive> &prim = primitives[i];
00288
00289 if (!prim->CanIntersect()) {
00290 vector<Reference<Primitive> > p;
00291 prim->FullyRefine(p);
00292 Assert(p.size() > 0);
00293 if (p.size() == 1)
00294 primitives[i] = p[0];
00295 else
00296 primitives[i] = new GridAccel(p, false);
00297 }
00298 }
00299 allCanIntersect = true;
00300 lock.DowngradeToRead();
00301 }
00302 for (uint32_t i = 0; i < primitives.size(); ++i) {
00303 Reference<Primitive> &prim = primitives[i];
00304 PBRT_GRID_RAY_PRIMITIVE_INTERSECTIONP_TEST(const_cast<Primitive *>(prim.GetPtr()));
00305 if (prim->IntersectP(ray)) {
00306 PBRT_GRID_RAY_PRIMITIVE_HIT(const_cast<Primitive *>(prim.GetPtr()));
00307 return true;
00308 }
00309 }
00310 return false;
00311 }
00312
00313
00314 GridAccel *CreateGridAccelerator(const vector<Reference<Primitive> > &prims,
00315 const ParamSet &ps) {
00316 bool refineImmediately = ps.FindOneBool("refineimmediately", false);
00317 return new GridAccel(prims, refineImmediately);
00318 }
00319
00320