-
sparker
thiago
Manta Interactive Ray Tracer Development Mailing List
Text archives Help
- From: "Thiago Ize" <thiago@sci.utah.edu>
- To: manta@sci.utah.edu
- Subject: [Manta] r2148 - in trunk: Model/Groups scenes
- Date: Wed, 26 Mar 2008 12:05:45 -0600 (MDT)
Author: thiago
Date: Wed Mar 26 12:05:44 2008
New Revision: 2148
Added:
trunk/Model/Groups/RecursiveGrid.cc
trunk/Model/Groups/RecursiveGrid.h
Removed:
trunk/Model/Groups/GriddedGroup.cc
trunk/Model/Groups/GriddedGroup.h
Modified:
trunk/Model/Groups/CMakeLists.txt
trunk/scenes/triangleSceneViewer.cc
Log:
Replaced GriddedGroup, which was outdated (wasn't an
AccelerationStructure) and only single level, with
RecursiveGrid, which is a recursive grid that inherits
from AccelerationStructure.
RecursiveGrid only traces single rays and it takes a long
time to build (not at all optimized for building), so it's
more useful for static scenes with non-coherent rays. For
that it actually does quite well. For very complex scenes,
performance can be improved by using more grid levels
(argument to constructor).
There's currently a lot of extra code in RecursiveGrid
that should probably be moved elsewhere (triangle-box
overlap test and the GridArray3 structure).
To use the RecursiveGrid in the triangleSceneViewer,
use -rgrid.
Modified: trunk/Model/Groups/CMakeLists.txt
==============================================================================
--- trunk/Model/Groups/CMakeLists.txt (original)
+++ trunk/Model/Groups/CMakeLists.txt Wed Mar 26 12:05:44 2008
@@ -1,8 +1,6 @@
SET (Manta_Groups_SRCS
Groups/DynBVH.h
Groups/DynBVH.cc
- Groups/GriddedGroup.cc
- Groups/GriddedGroup.h
Groups/Group.cc
Groups/Group.h
Groups/KDTree.h
@@ -13,6 +11,7 @@
Groups/MovingMesh.h
Groups/ObjGroup.h
Groups/ObjGroup.cc
+ Groups/RecursiveGrid
)
# Include private code if available
Added: trunk/Model/Groups/RecursiveGrid.cc
==============================================================================
--- (empty file)
+++ trunk/Model/Groups/RecursiveGrid.cc Wed Mar 26 12:05:44 2008
@@ -0,0 +1,618 @@
+
+#include <Model/Groups/RecursiveGrid.h>
+#include <Model/Primitives/MeshTriangle.h>
+#include <Interface/MantaInterface.h>
+#include <Interface/RayPacket.h>
+#include <Interface/Context.h>
+#include <Core/Exceptions/IllegalArgument.h>
+#include <Core/Exceptions/InternalError.h>
+#include <Core/Geometry/BBox.h>
+#include <Core/Math/MinMax.h>
+#include <Core/Util/Args.h>
+#include <Core/Thread/Time.h>
+#include <Core/Math/MinMax.h>
+#include <Core/Thread/Mutex.h>
+#include <iostream>
+
+using namespace std;
+using namespace Manta;
+
+
+long RecursiveGrid::nIntersects=0;
+long RecursiveGrid::nCellTraversals=0;
+long RecursiveGrid::nGridTraversals=0;
+long RecursiveGrid::nCells=0;
+long RecursiveGrid::nGrids[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
+double RecursiveGrid::nFilledCells=0;
+double RecursiveGrid::nTriRefs=0;
+
+RecursiveGrid::RecursiveGrid(int numLevels) :
+ lists(NULL), currGroup(NULL), mesh(NULL), numLevels(numLevels)
+{
+}
+
+RecursiveGrid::~RecursiveGrid()
+{
+ clearGrid();
+}
+
+void RecursiveGrid::clearGrid() {
+ //delete sub-grids
+ const int totalCells = cells.getNx()*cells.getNy()*cells.getNz();
+ const int listSize = totalCells>0? cells[totalCells]: 0;
+ for (int i=0; i < listSize; ++i) {
+ if (dynamic_cast<const RecursiveGrid*>(lists[i]))
+ delete lists[i];
+ }
+
+ delete[] lists;
+}
+
+void RecursiveGrid::transformToLattice(const BBox& box,
+ int& sx, int& sy, int& sz,
+ int& ex, int& ey, int& ez) const
+{
+ Vector s = (box.getMin()-min)*inv_cellsize-Vector(1.e-6,1.e-6,1.e-6);
+ sx = Floor(s.x()); sy = Floor(s.y()); sz = Floor(s.z());
+ Vector e = (box.getMax()-min)*inv_cellsize+Vector(1.e-6,1.e-6,1.e-6);
+ ex = Ceil(e.x()); ey = Ceil(e.y()); ez = Ceil(e.z());
+}
+
+void RecursiveGrid::preprocess( const PreprocessContext &context )
+{
+ if (currGroup) {
+ currGroup->computeBounds(context, bounds);
+ currGroup->preprocess(context);
+ }
+
+#if defined (COLLECT_STATS) || defined (PARAMETER_SEARCH)
+ context.manta_interface->registerSerialPreRenderCallback(
+ Callback::create(this, &RecursiveGrid::update));
+#endif
+
+}
+
+void RecursiveGrid::setGroup(Group* new_group)
+{
+ currGroup = new_group;
+ mesh = dynamic_cast<Mesh*>(currGroup);
+}
+
+Group* RecursiveGrid::getGroup() const
+{
+ return currGroup;
+}
+
+void RecursiveGrid::rebuild(int proc, int numProcs)
+{
+ //XXX need to make this a class data member instead of static if we want
+ //to have multiple top level grids in the scene!
+ static Mutex mutex("generic build mutex");
+ mutex.lock();
+
+ //We only support serial builds right now.
+ if (proc != 0)
+ return;
+
+ bounds.reset();
+
+ //Something's wrong, let's bail. Since we reset the bounds right
+ //above, this grid should never get intersected.
+ if (!currGroup)
+ return;
+
+ PreprocessContext context;
+
+ currGroup->computeBounds(context, bounds);
+
+ clearGrid();
+ for (int i=0; i<10; ++i)
+ nGrids[i]=0;
+ nCells = 0;
+ nTriRefs = nFilledCells = 0;
+ const double start = Time::currentSeconds();
+
+ build(context, currGroup->getVectorOfObjects(), bounds, 0,
currGroup->size());
+
+ const double dt = Time::currentSeconds()-start;
+ printf("Recursive Grid built in %f seconds for a %d object scene\n", dt,
(int)currGroup->size());
+ printf("There are %ld, %ld, %ld, %ld grids per level for a total of %ld
cells\n",
+ nGrids[0], nGrids[1], nGrids[2], nGrids[3], nCells);
+
+ mutex.unlock();
+}
+
+
+/* This is a direct copy of the Moller Triangle-Box Overlap Test.
+ This one we know works, unlike the one above which doesn't quite
+ work. Unfortunately this is also slower...
+*/
+#define CROSS(dest,v1,v2) \
+ dest[0]=v1[1]*v2[2]-v1[2]*v2[1]; \
+ dest[1]=v1[2]*v2[0]-v1[0]*v2[2]; \
+ dest[2]=v1[0]*v2[1]-v1[1]*v2[0];
+
+#define DOT(v1,v2) (v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2])
+
+#define SUB(dest,v1,v2) \
+ dest[0]=v1[0]-v2[0]; \
+ dest[1]=v1[1]-v2[1]; \
+ dest[2]=v1[2]-v2[2];
+
+#define FINDMINMAX(x0,x1,x2,min,max) \
+ min = max = x0; \
+ if(x1<min) min=x1;\
+ if(x1>max) max=x1;\
+ if(x2<min) min=x2;\
+ if(x2>max) max=x2;
+
+int planeBoxOverlap(float normal[3], float vert[3], float maxbox[3])
+{
+ int q;
+ float vmin[3],vmax[3],v;
+ for(q=0;q<=2;q++)
+ {
+ v=vert[q]; // -NJMP-
+ if(normal[q]>0.0f)
+ {
+ vmin[q]=-maxbox[q] - v; // -NJMP-
+ vmax[q]= maxbox[q] - v; // -NJMP-
+ }
+ else
+ {
+ vmin[q]= maxbox[q] - v; // -NJMP-
+ vmax[q]=-maxbox[q] - v; // -NJMP-
+ }
+ }
+ if(DOT(normal,vmin)>0.0f) return false; // -NJMP-
+ if(DOT(normal,vmax)>=0.0f) return true; // -NJMP-
+
+ return false;
+}
+
+/*======================== X-tests ========================*/
+#define AXISTEST_X01(a, b, fa, fb) \
+ p0 = a*v0[1] - b*v0[2]; \
+ p2 = a*v2[1] - b*v2[2]; \
+ if(p0<p2) {min=p0; max=p2;} else {min=p2; max=p0;} \
+ rad = fa * boxhalfsize[1] + fb * boxhalfsize[2]; \
+ if(min>rad || max<-rad) return false;
+
+#define AXISTEST_X2(a, b, fa, fb) \
+ p0 = a*v0[1] - b*v0[2]; \
+ p1 = a*v1[1] - b*v1[2]; \
+ if(p0<p1) {min=p0; max=p1;} else {min=p1; max=p0;} \
+ rad = fa * boxhalfsize[1] + fb * boxhalfsize[2]; \
+ if(min>rad || max<-rad) return false;
+
+/*======================== Y-tests ========================*/
+#define AXISTEST_Y02(a, b, fa, fb) \
+ p0 = -a*v0[0] + b*v0[2]; \
+ p2 = -a*v2[0] + b*v2[2]; \
+ if(p0<p2) {min=p0; max=p2;} else {min=p2; max=p0;} \
+ rad = fa * boxhalfsize[0] + fb * boxhalfsize[2]; \
+ if(min>rad || max<-rad) return false;
+
+#define AXISTEST_Y1(a, b, fa, fb) \
+ p0 = -a*v0[0] + b*v0[2]; \
+ p1 = -a*v1[0] + b*v1[2]; \
+ if(p0<p1) {min=p0; max=p1;} else {min=p1; max=p0;} \
+ rad = fa * boxhalfsize[0] + fb * boxhalfsize[2]; \
+ if(min>rad || max<-rad) return false;
+
+/*======================== Z-tests ========================*/
+
+#define AXISTEST_Z12(a, b, fa, fb) \
+ p1 = a*v1[0] - b*v1[1]; \
+ p2 = a*v2[0] - b*v2[1]; \
+ if(p2<p1) {min=p2; max=p1;} else {min=p1; max=p2;} \
+ rad = fa * boxhalfsize[0] + fb * boxhalfsize[1]; \
+ if(min>rad || max<-rad) return false;
+
+#define AXISTEST_Z0(a, b, fa, fb) \
+ p0 = a*v0[0] - b*v0[1]; \
+ p1 = a*v1[0] - b*v1[1]; \
+ if(p0<p1) {min=p0; max=p1;} else {min=p1; max=p0;} \
+ rad = fa * boxhalfsize[0] + fb * boxhalfsize[1]; \
+ if(min>rad || max<-rad) return false;
+
+bool triBoxOverlap(Object *obj, const BBox & bbox)
+{
+ float triverts[3][3];
+ //need to figure out what kind of triangle so we can get its vertices.
+ for (size_t v=0; v < 3; ++v) {
+ const Vector vertex = static_cast<MeshTriangle*>(obj)->getVertex(v);
+ for (size_t i=0; i < 3; ++i)
+ triverts[v][i] = vertex[i];
+ }
+
+ const Vector bbox_center = bbox.center();
+ float boxcenter[3] = { bbox_center[0], bbox_center[1], bbox_center[2] };
+ const Vector bbox_half_size = bbox.diagonal()*.5;
+ float boxhalfsize[3] = { bbox_half_size[0],
+ bbox_half_size[1],
+ bbox_half_size[2] };
+
+ /* use separating axis theorem to test overlap between triangle and box
*/
+ /* need to test for overlap in these directions: */
+ /* 1) the {x,y,z}-directions (actually, since we use the AABB of the
triangle */
+ /* we do not even need to test these) */
+ /* 2) normal of the triangle */
+ /* 3) crossproduct(edge from tri, {x,y,z}-directin) */
+ /* this gives 3x3=9 more tests */
+ float v0[3],v1[3],v2[3];
+ // float axis[3];
+ float min,max,p0,p1,p2,rad,fex,fey,fez; // -NJMP- "d" local variable
removed
+ float normal[3],e0[3],e1[3],e2[3];
+
+ /* This is the fastest branch on Sun */
+ /* move everything so that the boxcenter is in (0,0,0) */
+ SUB(v0,triverts[0],boxcenter);
+ SUB(v1,triverts[1],boxcenter);
+ SUB(v2,triverts[2],boxcenter);
+
+ /* compute triangle edges */
+ SUB(e0,v1,v0); /* tri edge 0 */
+ SUB(e1,v2,v1); /* tri edge 1 */
+ SUB(e2,v0,v2); /* tri edge 2 */
+
+ /* Bullet 3: */
+ /* test the 9 tests first (this was faster) */
+ fex = fabsf(e0[0]);
+ fey = fabsf(e0[1]);
+ fez = fabsf(e0[2]);
+ AXISTEST_X01(e0[2], e0[1], fez, fey);
+ AXISTEST_Y02(e0[2], e0[0], fez, fex);
+ AXISTEST_Z12(e0[1], e0[0], fey, fex);
+
+ fex = fabsf(e1[0]);
+ fey = fabsf(e1[1]);
+ fez = fabsf(e1[2]);
+ AXISTEST_X01(e1[2], e1[1], fez, fey);
+ AXISTEST_Y02(e1[2], e1[0], fez, fex);
+ AXISTEST_Z0(e1[1], e1[0], fey, fex);
+
+ fex = fabsf(e2[0]);
+ fey = fabsf(e2[1]);
+ fez = fabsf(e2[2]);
+ AXISTEST_X2(e2[2], e2[1], fez, fey);
+ AXISTEST_Y1(e2[2], e2[0], fez, fex);
+ AXISTEST_Z12(e2[1], e2[0], fey, fex);
+
+ /* Bullet 1: */
+ /* first test overlap in the {x,y,z}-directions */
+ /* find min, max of the triangle each direction, and test for overlap in
*/
+ /* that direction -- this is equivalent to testing a minimal AABB around
*/
+ /* the triangle against the AABB */
+ //Since we know that the triangle's bounding box is inside the cell,
+ //this test is not needed.
+
+ /* test in X-direction */
+ FINDMINMAX(v0[0],v1[0],v2[0],min,max);
+ if(min>boxhalfsize[0] || max<-boxhalfsize[0]) return false;
+
+ /* test in Y-direction */
+ FINDMINMAX(v0[1],v1[1],v2[1],min,max);
+ if(min>boxhalfsize[1] || max<-boxhalfsize[1]) return false;
+
+ /* test in Z-direction */
+ FINDMINMAX(v0[2],v1[2],v2[2],min,max);
+ if(min>boxhalfsize[2] || max<-boxhalfsize[2]) return false;
+
+
+
+ /* Bullet 2: */
+ /* test if the box intersects the plane of the triangle */
+ /* compute plane equation of triangle: normal*x+d=0 */
+ CROSS(normal,e0,e1);
+ // -NJMP- (line removed here)
+ if(!planeBoxOverlap(normal,v0,boxhalfsize)) return false; // -NJMP-
+
+ return true; /* box and triangle overlaps */
+}
+
+void RecursiveGrid::build(const PreprocessContext &context,
+ const vector<Object*> &objs, const BBox &bbox,
+ int depth, int totalObjects)
+{
+ min = bbox.getMin();
+ max = bbox.getMax();
+ Vector diag;
+ diag = bbox.getMax() - bbox.getMin();
+ diag = Max(Vector(1.e-4,1.e-4,1.e-4), diag);
+ Real expandBy_f = diag.length()*1e-5;
+ Vector expandBy(expandBy_f, expandBy_f, expandBy_f);
+ min -= expandBy;
+ max += expandBy;
+ diag = max-min;
+
+ double volume = diag.x()*diag.y()*diag.z();
+ double vol3 = Cbrt(volume);
+ const float initial_exp_d = (numLevels)*2+1;
+ totalObjects = objs.size();
+ float exponent =
+ 1.0 / (initial_exp_d-depth*2);
+ //7.0/27; //optimal for single level grids
+ //4/3.0 / 3.0; //optimal for single level grid of long skinny triangles.
+
+ //Found 8^(1/3) to work well for this codebase. It's possible this
+ //could change with updated code.
+ float scale = 2;
+
+ double m = scale * powf(totalObjects, exponent);
+ //note: m^3 = M = total cells for that specfic grid level
+ bool build_N_Grid = false;
+ buildgrid:
+ if (build_N_Grid)
+ m = Cbrt((double)objs.size()); //TODO: figure out if a scalar is needed
+
+ int nx = 0, ny = 0, nz = 0;
+ while (nx*ny*nz < 8) {
+ nx = static_cast<int>((diag.x() * m) / vol3 +.5);
+ ny = static_cast<int>((diag.y() * m) / vol3 +.5);
+ nz = static_cast<int>((diag.z() * m) / vol3 +.5);
+ nx = Max(1, nx); ny = Max(1, ny); nz = Max(1, nz);
+ m*=2;
+// if (nx*ny*nz < 8) {
+// printf("%d,%d,%d %f %d\n", nx, ny, nz, m, numObjects);
+// cout <<"diag: " <<diag << endl;
+// }
+ if (m > 1e20) {
+ printf("m > 1e20");
+ break;//exit(1);
+ }
+ }
+ int M = nx*ny*nz;
+
+ cellsize = diag/Vector(nx, ny, nz);
+ inv_cellsize = cellsize.inverse();
+ cells.resize(nx, ny, nz, 1);
+ subGridList.resize(nx, ny, nz, 1);
+
+ GridArray3<vector<Object*> > cell_objects;
+ cell_objects.resize(nx, ny, nz,1);
+
+// cerr << "1. Initializing grid\n";
+ cells.initialize(0);
+ subGridList.initialize(false);
+
+// cerr << "2. Count objects\n";
+ for(int i=0;i<static_cast<int>(objs.size());i++){
+ Object* obj = objs[i];
+
+ BBox objbox;
+ obj->computeBounds(context,objbox);
+ objbox.intersection(bbox);
+ int sx, sy, sz, ex, ey, ez;
+ transformToLattice(objbox, sx, sy, sz, ex, ey, ez);
+ sx = Max(0, sx);
+ sy = Max(0, sy);
+ sz = Max(0, sz);
+ ex = Min(nx, ex);
+ ey = Min(ny, ey);
+ ez = Min(nz, ez);
+
+ for(int x=sx;x<ex;x++){
+ for(int y=sy;y<ey;y++){
+ for(int z=sz;z<ez;z++){
+ Vector xyz(x,y,z);
+ BBox cellBounds(min + xyz*cellsize,
+ min + (xyz+Vector(1,1,1)) * cellsize);
+ if (!mesh || triBoxOverlap(obj, cellBounds)) {
+ nTriRefs++;
+ cells(x, y, z)++;
+ cell_objects(x, y, z).push_back(obj);
+ }
+ }
+ }
+ }
+ }
+
+ unsigned int MAX_OBJS = 4;
+ if (depth >= numLevels-1)
+ MAX_OBJS = 100000000;
+
+// cerr << "3. Count cells\n";
+ int sum = 0;
+ int nUsedCells = 0;
+ for(int i=0;i<M;i++){
+ int nobj = cell_objects[i].size();
+ nobj = nobj> (int)MAX_OBJS ? 1: nobj;
+ cells[i] = sum;
+ sum+=nobj;
+ if (nobj > 0)
+ nUsedCells++;
+ }
+ cells[M] = sum;
+
+ nFilledCells += nUsedCells; //for debugging/testing
+
+ const float USED_CELL_THREASHOLD = 1.9f;
+ if (nUsedCells > M*USED_CELL_THREASHOLD &&
+ !build_N_Grid) {
+ //redo with O(N) cells
+ build_N_Grid = true;
+ goto buildgrid;
+ }
+
+ nGrids[depth]++;
+ nCells+=M;
+
+// cerr << "4. Allocating " << sum << " list entries\n";
+ lists = new const Object*[sum];
+
+ GridArray3<int> offset(nx, ny, nz);
+ offset.initialize(0);
+
+// cerr << "5. Filling in lists\n";
+ for (int x=0; x<nx; ++x) {
+ for (int y=0; y<ny; ++y) {
+ for (int z=0; z<nz; ++z) {
+ if (cell_objects(x,y,z).size() > MAX_OBJS) {
+ Vector xyz(x,y,z);
+ BBox cellBounds(min + xyz*cellsize,
+ min + (xyz+Vector(1,1,1)) * cellsize);
+
+ //create recursive grid with tight bounding box
+ BBox objBounds;
+ for (unsigned int i=0; i < cell_objects(x,y,z).size(); ++i) {
+ cell_objects(x,y,z)[i]->computeBounds(context, objBounds);
+ }
+ cellBounds.intersection(objBounds);
+
+ RecursiveGrid *gg = new RecursiveGrid(numLevels);
+ gg->build(context, cell_objects(x,y,z), cellBounds, depth+1,
totalObjects);
+ int start = cells(x, y, z);
+ lists[start] = gg;
+ subGridList(x,y,z)=true;
+ }
+ else { //just add individual objects to cell
+ int start = cells(x, y, z);
+ for (unsigned int i=0; i < cell_objects(x,y,z).size(); ++i) {
+ lists[start+i] = cell_objects(x,y,z)[i];
+ }
+ }
+ }
+ }
+ }
+}
+
+void RecursiveGrid::intersect( const RenderContext &context, RayPacket &rays
) const
+{
+ rays.computeInverseDirections();
+ rays.computeSigns();
+ for(int i=rays.begin(); i<rays.end(); i++) {
+ RayPacket subpacket(rays, i, i+1);
+ intersectRay(context, subpacket);
+ }
+}
+
+void RecursiveGrid::intersectRay( const RenderContext &context, RayPacket
&rays ) const
+{
+ const int i = rays.begin();
+ const Vector origin(rays.getOrigin(i));
+ const Vector direction(rays.getDirection(i));
+ const Vector inv_direction(rays.getInverseDirection(i));
+
+ // Step 2
+ const Vector v1 = (min-origin)*inv_direction;
+ const Vector v2 = (max-origin)*inv_direction;
+ const Vector vmin = Min(v1, v2);
+ const Vector vmax = Max(v1, v2);
+ Real tnear = vmin.maxComponent();
+ Real tfar = vmax.minComponent();
+ if(tnear >= tfar)
+ return;
+ if(tfar < (Real)1.e-6)
+ return;
+ if(tnear < 0)
+ tnear = 0;
+
+#ifdef COLLECT_STATS
+ nTotalRays++;
+#endif //COLLECT_STATS
+
+
+ // Step 3
+ const Vector p = origin + tnear * direction;
+ const Vector L = (p-min)*inv_cellsize;
+ int Lx = Clamp(static_cast<int>(L.x()), 0, cells.getNx()-1);
+ int Ly = Clamp(static_cast<int>(L.y()), 0, cells.getNy()-1);
+ int Lz = Clamp(static_cast<int>(L.z()), 0, cells.getNz()-1);
+
+ // Step 4
+ const int stopX[2] = {cells.getNx(), -1};
+ const int stopY[2] = {cells.getNy(), -1};
+ const int stopZ[2] = {cells.getNz(), -1};
+ int dix = 1-rays.getSign(i, 0)*2;
+ int stopx = stopX[rays.getSign(i, 0)];
+ int diy = 1-rays.getSign(i, 1)*2;
+ int stopy = stopY[rays.getSign(i, 1)];
+ int diz = 1-rays.getSign(i, 2)*2;
+ int stopz = stopZ[rays.getSign(i, 2)];
+
+ // Step 5
+ Real dtdx = Abs(cellsize.x()*inv_direction.x());
+ Real dtdy = Abs(cellsize.y()*inv_direction.y());
+ Real dtdz = Abs(cellsize.z()*inv_direction.z());
+
+ // Step 6
+// This could be written as: (but it didn't seem to improve performance)
+// Real far_x = (Lx+1-rays.getSign(i,0))*cellsize.x() + min.x();
+ Real far_x = Lx*cellsize.x() + min.x();
+ if(direction.x()>0)
+ far_x += cellsize.x();
+ Real far_y = Ly*cellsize.y() + min.y();;
+ if(direction.y()>0)
+ far_y += cellsize.y();
+ Real far_z = Lz*cellsize.z() + min.z();;
+ if(direction.z()>0)
+ far_z += cellsize.z();
+
+ // Step 7
+ Real tnext_x = (far_x - origin.x())*inv_direction.x();
+ Real tnext_y = (far_y - origin.y())*inv_direction.y();
+ Real tnext_z = (far_z - origin.z())*inv_direction.z();
+
+ // Step 8
+ while(tnear < rays.getMinT(i)){
+
+#ifdef COLLECT_STATS
+ nCellTraversals++;
+#endif //COLLECT_STATS
+
+ const int idx = cells.getIndex(Lx, Ly, Lz);
+ int l = cells[idx];
+ const int e = cells[idx+1];
+ for(;l < e; l++){
+ if (subGridList[idx]) {
+ static_cast<const RecursiveGrid*>
+ (lists[cells[idx]])->intersectRay(context, rays);
+#ifdef COLLECT_STATS
+ nGridTraversals++;
+#endif //COLLECT_STATS
+ }
+ else {
+ const Object* obj = lists[l];
+ obj->intersect(context, rays);
+#ifdef COLLECT_STATS
+ nIntersects++;
+#endif //COLLECT_STATS
+ }
+ }
+ // Step 11
+ if(tnext_x < tnext_y && tnext_x < tnext_z){
+ Lx += dix;
+ if(Lx == stopx)
+ break;
+ tnear = tnext_x;
+ tnext_x += dtdx;
+ } else if(tnext_y < tnext_z){
+ Ly += diy;
+ if(Ly == stopy)
+ break;
+ tnear = tnext_y;
+ tnext_y += dtdy;
+ } else {
+ Lz += diz;
+ if(Lz == stopz)
+ break;
+ tnear = tnext_z;
+ tnext_z += dtdz;
+ }
+ }
+}
+
+void RecursiveGrid::update(int proc, int numProcs)
+{
+#ifdef COLLECT_STATS
+ printf("primitive intersections per ray: %f\n",
(float)nIntersects/nTotalRays);
+ printf("cell traversals per ray: %f\n",
(float)nCellTraversals/nTotalRays);
+ printf("grid traversals per ray: %f\n",
(float)nGridTraversals/nTotalRays);
+ printf("number of rays: %ld\n", nTotalRays);
+ nIntersects = 0;
+ nCellTraversals = 0;
+ nGridTraversals = 0;
+ nTotalRays = 0;
+#endif
+}
Added: trunk/Model/Groups/RecursiveGrid.h
==============================================================================
--- (empty file)
+++ trunk/Model/Groups/RecursiveGrid.h Wed Mar 26 12:05:44 2008
@@ -0,0 +1,191 @@
+#ifndef RecursiveGrid_h
+#define RecursiveGrid_h
+
+#include <Model/Groups/Group.h>
+#include <Model/Groups/Mesh.h>
+#include <Core/Geometry/Vector.h>
+#include <Core/Geometry/BBox.h>
+#include <Interface/RayPacket.h>
+#include <Interface/AccelerationStructure.h>
+
+#include <vector>
+
+namespace Manta {
+
+ template<typename T>
+ class GridArray3 {
+ public:
+ GridArray3() {
+ nx = ny = nz = extra = 0;
+ xidx = yidx = zidx = 0;
+ data = 0;
+ }
+ GridArray3(int nx, int ny, int nz, int extra = 0) {
+ xidx = yidx = zidx = 0;
+ data = 0;
+ resize(nx, ny, nz, extra);
+ }
+ ~GridArray3() {
+ resize(0, 0, 0);
+ }
+
+ void resize(int newnx, int newny, int newnz, int newextra = 0) {
+ if(xidx)
+ delete[] xidx;
+ if(yidx)
+ delete[] yidx;
+ if(zidx)
+ delete[] zidx;
+ if(data)
+ delete[] data;
+ nx = newnx; ny = newny; nz = newnz; extra = newextra;
+ int total = nx*ny*nz+extra;
+ if(total != 0){
+ data = new T[total];
+ allocateAndInitializeStride(xidx, nx, 1);
+ allocateAndInitializeStride(yidx, ny, nx);
+ allocateAndInitializeStride(zidx, nz, nx*ny);
+ } else {
+ xidx = yidx = zidx = 0;
+ data = 0;
+ }
+ }
+
+ void resizeZMajor(int newnx, int newny, int newnz, int newextra = 0) {
+ if(xidx)
+ delete[] xidx;
+ if(yidx)
+ delete[] yidx;
+ if(zidx)
+ delete[] zidx;
+ if(data)
+ delete[] data;
+ nx = newnx; ny = newny; nz = newnz; extra = newextra;
+ int total = nx*ny*nz+extra;
+ if(total != 0){
+ data = new T[total];
+ allocateAndInitializeStride(xidx, nx, nz*ny);
+ allocateAndInitializeStride(yidx, ny, nz);
+ allocateAndInitializeStride(zidx, nz, 1);
+ } else {
+ xidx = yidx = zidx = 0;
+ data = 0;
+ }
+ }
+
+ void initialize(const T& value) {
+ int total = nx*ny*nz+extra;
+ for(int i=0;i<total;i++)
+ data[i] = value;
+ }
+
+ T& operator()(int x, int y, int z) {
+ return data[xidx[x] + yidx[y] + zidx[z]];
+ }
+ const T& operator()(int x, int y, int z) const {
+ return data[xidx[x] + yidx[y] + zidx[z]];
+ }
+ int getIndex(int x, int y, int z) const {
+ return xidx[x] + yidx[y] + zidx[z];
+ }
+ T& operator[](int idx) {
+ return data[idx];
+ }
+ const T& operator[](int idx) const {
+ return data[idx];
+ }
+
+ int getNx() const {
+ return nx;
+ }
+ int getNy() const {
+ return ny;
+ }
+ int getNz() const {
+ return nz;
+ }
+
+
+ private:
+ GridArray3(const GridArray3&);
+ GridArray3& operator=(const GridArray3&);
+
+ int nx, ny, nz, extra;
+ int* xidx;
+ int* yidx;
+ int* zidx;
+ T* data;
+
+ void allocateAndInitializeStride(int*& idx, int num, int stride) {
+ idx = new int[num];
+ for(int i=0;i<num;i++)
+ idx[i] = stride*i;
+ }
+ };
+
+
+ class RecursiveGrid : public AccelerationStructure {
+ public:
+ RecursiveGrid(int numLevels = 3);
+ virtual ~RecursiveGrid();
+
+ void setGroup(Group* new_group);
+ void groupDirty() {} // does nothing for now
+ Group* getGroup() const;
+
+ virtual void addToUpdateGraph(ObjectUpdateGraph* graph,
+ ObjectUpdateGraphNode* parent) { }
+
+ void rebuild(int proc=0, int numProcs=1);
+
+ virtual void preprocess( PreprocessContext const & );
+ virtual void intersect( RenderContext const &context, RayPacket &rays )
const;
+ void computeBounds(const PreprocessContext&,
+ BBox& bbox) const
+ {
+ if (currGroup)
+ bbox.extendByBox(bounds);
+ }
+
+ private:
+ void clearGrid();
+ RecursiveGrid(const RecursiveGrid&);
+ RecursiveGrid& operator=(const RecursiveGrid&);
+
+ void build(const PreprocessContext &context, const vector<Object*> &objs,
+ const BBox &bounds, const int depth, int totalObjects);
+
+ void intersectRay( const RenderContext &context, RayPacket &rays ) const;
+
+ //for performance measurements. Can be removed.
+// #define COLLECT_STATS
+ static long nIntersects;
+ static long nCellTraversals;
+ static long nGridTraversals;
+ mutable long nTotalRays;
+ static long nCells;
+ static long nGrids[10];
+ static double nFilledCells;
+ static double nTriRefs;
+ void update(int proc, int numProcs);
+
+ Vector min, max;
+ Vector cellsize;
+ Vector inv_cellsize;
+ GridArray3<int> cells;
+ const Object** lists;
+ GridArray3<bool> subGridList;
+
+ Group *currGroup;
+ Mesh *mesh;
+ BBox bounds;
+
+ int numLevels;
+
+ void transformToLattice(const BBox& box,
+ int& sx, int& sy, int& sz, int& ex, int& ey, int&
ez) const;
+
+ };
+}
+
+#endif
Modified: trunk/scenes/triangleSceneViewer.cc
==============================================================================
--- trunk/scenes/triangleSceneViewer.cc (original)
+++ trunk/scenes/triangleSceneViewer.cc Wed Mar 26 12:05:44 2008
@@ -13,6 +13,7 @@
#include <Model/Groups/Group.h>
#include <Model/Groups/KDTree.h>
#include <Model/Groups/ObjGroup.h>
+#include <Model/Groups/RecursiveGrid.h>
#include <Model/Materials/Lambertian.h>
#include <Model/Lights/PointLight.h>
#include <Model/Lights/AreaLight.h>
@@ -44,6 +45,7 @@
cerr << " -CGT - use Coherent Grid Traversal acceleration
structure\n";
#endif
cerr << " -KDTree - use KDTree acceleration structure\n";
+ cerr << " -rgrid - use single ray recursive grid acceleration
structure\n";
cerr << " -model - Required. The file to load (obj or ply file)\n";
cerr << " Can call this multiple times to load an
animation.\n";
cerr << " -animationLength - Number of seconds animation takes\n";
@@ -114,6 +116,9 @@
} else if (arg == "-KDTree") {
delete as;
as = new KDTree;
+ } else if (arg == "-rgrid") {
+ delete as;
+ as = new RecursiveGrid;
} else if (arg == "-CGT") {
#ifdef USE_PRIVATE_CODE
delete as;
- [Manta] r2148 - in trunk: Model/Groups scenes, Thiago Ize, 03/26/2008
Archive powered by MHonArc 2.6.16.
