Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members  

RT_Grid Class Reference

#include <RT_Grid.h>

Collaboration diagram for RT_Grid:

List of all members.

Public Members

Void MasterInit ()
Void Init ()
Void Free ()
Void AddObject (RT_Object *object)
Void RemoveObject (RT_Object *object)
Void PrepareGrid ()
Bool IntersectionExists ( const Point& start, const Point& end, RT_Prim* origPrim = 0, RayStats* stats = 0 )
RT_PrimClosestIntersection ( const Point& start, const Vector& direction, RT_Prim* origPrim = 0, RayStats* stats = 0 )
Void HierPrint (ostream& s, Int index)
Void Draw (Renderer &r, Int level)
Void DumpMemoryUsage ()
GCLReal GridMemoryUsage ()
GCLReal MemoryUsage ()
Void SetBounds (Point &bmin, Point &bmax)
Void SetupGrid ()
Void AddTriangle (RT_Tri *tri)
Void AddGeneric (RT_Gen *gen)
GCLReal GetScale ()
Last primitive hit in this grid.

GCLReal hitT
t param of hit.

Point min
Point max
axis-aligned bounding box of grid.

Static Public Members

Void SetTag (Int tag)
Void SetMemLimit (Int maxKbs)
GCLReal sEpsilon = 1e-15
for self-intersection tests.

Int sMem = 0
memory being used by grids.

Int sMemLimit = 0
memory limit.

Int sTriMem = 0
tri memory.

Int sGenMem = 0
gen memory.

Int sPointMem = 0
points memory.

Int sMaxCells = 40
See source.

Int sMaxCellPrims = RT_Grid::sMaxCells
GCLReal sPushSizeLimit = 0.05
GCLReal sMaxCellRatio = 0.20
GCLReal sMinDensity = 0.05
GCLReal sMaxExpand = 3.00

Protected Members

Void Stamp ()
Bool IsStamped ()
Void UpdateBounds (Point& cellMin, Point& cellMax)
Void UpdateBounds (RT_Object *object)
Void CreateNestedGrids ()
Void CullSubGrids ()
Void PushPrimitives ()
Int CountPolys (PrimEntry *entry)
Bool FindGridStart ( const Point& start, const Vector& direction, Int cell[3], Int increment[3], Int limit[3], GCLReal& tRay, Vector& tDelta, Vector& tMax )
Void RayClampEntryPoint (Int index, Bool backEntry[3], Vector& fujiPoint, Int cell[3])
list of objects currently in grid.

list of objects to add to the grid.

GridStore grid
the grid itself.

list of tri lists to add to a subgrid.

RT_Grid* subGrids

RT_Grid* next
next subgrid.

GCLReal cellSize
GCLReal areaLimit
Int numCells [3]
Int xSpan
Int ySpan
byte-spans for grid array.

Int totalCells
Int totalPrims
Int dirty
do we need to re-grid?

Int level
level of the grid.

RT_Grid* parent
parent grid.

Int stamp
local time-stamp.

Static Protected Members

Void IncTime ()
Int sStamp = 1
global time-stamp.

Int sTag = 0x00000001
object groups enabled mask.

Detailed Description

A class that implements grid-traversal ray-tracing.

Usage: Call MasterInit(), AddObject() for each object, PrepareGrid(), and then IntersectionExists()/ClosestIntersection() as needed. Call Free() when no longer needed.


Traditionally, of the ray-tracing optimising schemes, grid-traversal (sometimes referred to as SEADS -- spatially enumerated abstract data structures) is amongst the fastest, if not the fastest. See for example the results from Haines' NFF testbed, widely available on the web. This scheme was used in R&H's first ray tracer. It works especially well when the objects in the grid are reasonably homogeneous.

However, the grid scheme suffers from the teapot-in-a-stadium problem, as described in ray-tracing news 8. Octrees suffer somewhat less from this, especially if the appropriate optimisations are made.

The drawback of Arvo's scheme is that it requires the modeller/animator to place the grids by hand, which we'd obviously like to avoid. I've had some ideas for automatic placement of these grids floating around for a while, and this code gave me a chance to play with them until they evolved into something that did a reasonable job of engridding an entire scene.

The major drawback of the HG scheme is that it uses more memory than the previous single grid scheme. The memory is on the order of the memory taken to store the object itself. The memory overhead can be reduced by tweaking the constants to reduce the number of extra grids created, and I've also left in hooks so the total memory used can be limited to a specified amount.

Many other, more standard optimisations were made, including

- triangle lists sorted by size

Definition at line 69 of file RT_Grid.h.

Member Function Documentation

Void RT_Grid::AddGeneric (RT_Gen * gen)

Void RT_Grid::AddObject (RT_Object * object)

Definition at line 279 of file

Void RT_Grid::AddTriangle (RT_Tri * tri)

Definition at line 517 of file

RT_Prim * RT_Grid::ClosestIntersection (const Point & start, const Vector & direction, RT_Prim * origPrim = 0, RayStats * stats = 0)

Definition at line 1019 of file

Int RT_Grid::CountPolys (PrimEntry * entry) [protected]

Void RT_Grid::CreateNestedGrids () [protected]

Definition at line 1225 of file

Void RT_Grid::CullSubGrids () [protected]

Definition at line 1366 of file

Void RT_Grid::Draw (Renderer & r, Int level)

Void RT_Grid::DumpMemoryUsage ()

Definition at line 1496 of file

Bool RT_Grid::FindGridStart (const Point & start, const Vector & direction, Int cell[3], Int increment[3], Int limit[3], GCLReal & tRay, Vector & tDelta, Vector & tMax) [protected]

Definition at line 658 of file

Void RT_Grid::Free ()

Definition at line 227 of file

GCLReal RT_Grid::GetScale () [inline]

Definition at line 114 of file RT_Grid.h.

GCLReal RT_Grid::GridMemoryUsage ()

Definition at line 1486 of file

Void RT_Grid::HierPrint (ostream & s, Int indent)

Definition at line 1466 of file

Void RT_Grid::IncTime () [inline, static, protected]

Definition at line 169 of file RT_Grid.h.

Void RT_Grid::Init ()

Definition at line 204 of file

Bool RT_Grid::IntersectionExists (const Point & start, const Point & end, RT_Prim * origPrim = 0, RayStats * stats = 0)

Definition at line 851 of file

Bool RT_Grid::IsStamped () [inline, protected]

Definition at line 173 of file RT_Grid.h.

Void RT_Grid::MasterInit ()

Definition at line 195 of file

GCLReal RT_Grid::MemoryUsage ()

Definition at line 1491 of file

Void RT_Grid::PrepareGrid ()

Definition at line 297 of file

Void RT_Grid::PushPrimitives () [protected]

Definition at line 1397 of file

Void RT_Grid::RayClampEntryPoint (Int index, Bool backEntry[3], Vector & gridPoint, Int cell[3]) [protected]

Definition at line 637 of file

Void RT_Grid::RemoveObject (RT_Object * object)

Void RT_Grid::SetBounds (Point & bmin, Point & bmax) [inline]

Definition at line 109 of file RT_Grid.h.

Void RT_Grid::SetMemLimit (Int maxKbs) [static]

Definition at line 1481 of file

Void RT_Grid::SetTag (Int tag) [inline, static]

Definition at line 98 of file RT_Grid.h.

Void RT_Grid::SetupGrid ()

Definition at line 392 of file

Void RT_Grid::Stamp () [inline, protected]

Definition at line 171 of file RT_Grid.h.

Void RT_Grid::UpdateBounds (RT_Object * object) [protected]

Definition at line 380 of file

Void RT_Grid::UpdateBounds (Point & cellMin, Point & cellMax) [protected]

Definition at line 374 of file

Member Data Documentation

ObjEntry * RT_Grid::addObjs [protected]

list of objects to add to the grid.

Definition at line 126 of file RT_Grid.h.

PrimListEntry * RT_Grid::addPrims [protected]

list of tri lists to add to a subgrid.

Definition at line 129 of file RT_Grid.h.

ObjEntry * RT_Grid::addedObjs [protected]

list of objects currently in grid.

Definition at line 125 of file RT_Grid.h.

GCLReal RT_Grid::areaLimit [protected]

Definition at line 134 of file RT_Grid.h.

GCLReal RT_Grid::cellSize [protected]

Definition at line 133 of file RT_Grid.h.

Int RT_Grid::dirty [protected]

do we need to re-grid?

Definition at line 159 of file RT_Grid.h.

GridStore RT_Grid::grid [protected]

the grid itself.

Definition at line 128 of file RT_Grid.h.

RT_Prim * RT_Grid::hitPrim

Last primitive hit in this grid.

Definition at line 118 of file RT_Grid.h.

GCLReal RT_Grid::hitT

t param of hit.

Definition at line 119 of file RT_Grid.h.

Int RT_Grid::level [protected]

level of the grid.

Definition at line 160 of file RT_Grid.h.

Point RT_Grid::max

axis-aligned bounding box of grid.

Definition at line 121 of file RT_Grid.h.

Point RT_Grid::min

Definition at line 121 of file RT_Grid.h.

RT_Grid * RT_Grid::next [protected]

next subgrid.

Definition at line 131 of file RT_Grid.h.

Int RT_Grid::numCells[3] [protected]

Definition at line 135 of file RT_Grid.h.

RT_Grid * RT_Grid::parent [protected]

parent grid.

Definition at line 161 of file RT_Grid.h.

GCLReal RT_Grid::sEpsilon = 1e-15 [static]

for self-intersection tests.

Definition at line 142 of file RT_Grid.h.

Int RT_Grid::sGenMem = 0 [static]

gen memory.

Definition at line 146 of file RT_Grid.h.

Int RT_Grid::sMaxCellPrims = RT_Grid::sMaxCells [static]

Definition at line 150 of file RT_Grid.h.

GCLReal RT_Grid::sMaxCellRatio = 0.20 [static]

Definition at line 152 of file RT_Grid.h.

Int RT_Grid::sMaxCells = 40 [static]

See source.

Definition at line 149 of file RT_Grid.h.

GCLReal RT_Grid::sMaxExpand = 3.00 [static]

Definition at line 154 of file RT_Grid.h.

Int RT_Grid::sMem = 0 [static]

memory being used by grids.

Definition at line 143 of file RT_Grid.h.

Int RT_Grid::sMemLimit = 0 [static]

memory limit.

Definition at line 144 of file RT_Grid.h.

GCLReal RT_Grid::sMinDensity = 0.05 [static]

Definition at line 153 of file RT_Grid.h.

Int RT_Grid::sPointMem = 0 [static]

points memory.

Definition at line 147 of file RT_Grid.h.

GCLReal RT_Grid::sPushSizeLimit = 0.05 [static]

Definition at line 151 of file RT_Grid.h.

Int RT_Grid::sStamp = 1 [static, protected]

global time-stamp.

Definition at line 164 of file RT_Grid.h.

Int RT_Grid::sTag = 0x00000001 [static, protected]

object groups enabled mask.

Definition at line 165 of file RT_Grid.h.

Int RT_Grid::sTriMem = 0 [static]

tri memory.

Definition at line 145 of file RT_Grid.h.

Int RT_Grid::stamp [protected]

local time-stamp.

Definition at line 163 of file RT_Grid.h.

RT_Grid * RT_Grid::subGrids [protected]


Definition at line 130 of file RT_Grid.h.

Int RT_Grid::totalCells [protected]

Definition at line 137 of file RT_Grid.h.

Int RT_Grid::totalPrims [protected]

Definition at line 137 of file RT_Grid.h.

Int RT_Grid::xSpan [protected]

Definition at line 136 of file RT_Grid.h.

Int RT_Grid::ySpan [protected]

byte-spans for grid array.

Definition at line 136 of file RT_Grid.h.

The documentation for this class was generated from the following files:
Generated at Sat Aug 5 00:26:58 2000 for Radiator by doxygen 1.1.0 written by Dimitri van Heesch, © 1997-2000