Support Forum       Library Source       SourceForge Page       G3D Web Page     
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Classes | Public Types | Public Member Functions | Static Public Member Functions | List of all members
G3D::TriTree Class Reference

Static bounding interval hierarchy for Ray-Tri intersections. More...

Classes

class  HighComparator
 Compares whether the high() of one Poly is less than the high() of another.
class  Node
class  Poly
 A convex polygon formed by repeatedly clipping a Tri with axis-aligned planes.
class  Settings
class  Stats
struct  ValueArray
 Does not have to be deleted; has no constructor.

Public Types

enum  SplitAlgorithm {
  MEAN_EXTENT,
  MEDIAN_AREA,
  MEDIAN_COUNT,
  SAH
}

Public Member Functions

 TriTree ()
 ~TriTree ()
void clear ()
const CPUVertexArraycpuVertexArray () const
void draw (RenderDevice *rd, int level, bool showBoxes=true, int minNodeSize=0)
 Render the tree for debugging and visualization purposes.
const CPUVertexArraygetCPUVertexArray () const
void intersectBox (const AABox &box, Array< Tri > &triArray) const
 Returns all triangles that intersect or are contained within the box.
bool intersectRay (const Ray &ray, Tri::Intersector &intersectCallback, float &distance, bool exitOnAnyHit=false, bool twoSided=false) const
 Returns true if there was an intersection.
void intersectSphere (const Sphere &sphere, Array< Tri > &triArray) const
 Returns all triangles that intersect or are contained within the sphere (technically, this is a ball intersection).
const Trioperator[] (int i) const
 Array access to the stored Tris.
void setContents (const Array< Tri > &triArray, const CPUVertexArray &vertexArray, const Settings &settings=Settings())
 The arrays will be copied, the underlying Array<Tri> is guaranteed to be in the same order as the parameter Tri Array.
void setContents (const Array< SurfaceRef > &surfaceArray, ImageStorage newStorage=IMAGE_STORAGE_CURRENT, const Settings &settings=Settings())
 This will construct a CPUVertexArray, setting all normals, tangents, and texture coordinates to 0, material will be NULL.
int size () const
Stats stats (int valuesPerNode) const
 Walk the entire tree, computing statistics.

Static Public Member Functions

static const char * algorithmName (SplitAlgorithm s)

Detailed Description

Static bounding interval hierarchy for Ray-Tri intersections.

The BIH is a tree in which each node is an axis-aligned box containing up to three child nodes: elements in the negative half space of a splitting plane, elements in the positive half space, and elements spaning both sides. When constructing the tree, spanning elements can either be inserted at a spanning node or split and inserted into the child nodes. The presence of a splitting plane allows early-out ray intersection like a kd-tree and the bounding boxes allow relatively tight tree pruning, like a bounding volume hierarchy.

Various algorithms are implemented for choosing the splitting plane that trade between ray-intersection performance and tree-building performance.

Referenced Code:
Watcher and Keller, Instant Ray Tracing: The Bounding Interval Hierarchy, EGSR 2006 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.87.4612

Member Enumeration Documentation

Enumerator:
MEAN_EXTENT 

Produce nodes with approximately equal shape by splitting nodes half-way across the bounds of their contents (similar to an oct-tree).

Fastest method for building the tree.

MEDIAN_AREA 

Split nodes so that children have about the same surface area.

MEDIAN_COUNT 

Split nodes so that children have about the same number of triangles.

SAH 

Split nodes so that they have approximately equal intersection times, according to a Surface Area Heuristic.

Theory indicates that this gives the highest performance for ray intersection, although that may not be the case for specific scenes and rays.

Constructor & Destructor Documentation

G3D::TriTree::TriTree ( )
G3D::TriTree::~TriTree ( )

Member Function Documentation

static const char* G3D::TriTree::algorithmName ( SplitAlgorithm  s)
static
void G3D::TriTree::clear ( )
const CPUVertexArray& G3D::TriTree::cpuVertexArray ( ) const
inline
void G3D::TriTree::draw ( RenderDevice rd,
int  level,
bool  showBoxes = true,
int  minNodeSize = 0 
)

Render the tree for debugging and visualization purposes.

Inefficent.

Parameters
levelShow the nodes at or above this level of the tree, where 0 = root
showBoxesRender bounding boxes for internal nodes at level == level
minNodeSizeDo not render triangles at nodes with fewer than this many triangles. Set to zero to disable, set to a high number to spot poorly-constructed nodes
const CPUVertexArray& G3D::TriTree::getCPUVertexArray ( ) const
inline
void G3D::TriTree::intersectBox ( const AABox box,
Array< Tri > &  triArray 
) const

Returns all triangles that intersect or are contained within the box.

bool G3D::TriTree::intersectRay ( const Ray ray,
Tri::Intersector intersectCallback,
float &  distance,
bool  exitOnAnyHit = false,
bool  twoSided = false 
) const

Returns true if there was an intersection.

Example:

   Tri::Intersector intersector;
   float distance = inf();
   if (tree.intersectRay(ray, intersector, distance)) {
       Vector3 position, normal;
       Vector2 texCoord;
       intersector.getResult(position, normal, texCoord);
       ...
   }
Parameters
exitOnAnyHitIf true, return any intersection, not the first (faster for shadow rays)
twoSidedIf true, both sides of triangles are tested for intersections. If a back face is hit, the normal will not automatically be flipped
void G3D::TriTree::intersectSphere ( const Sphere sphere,
Array< Tri > &  triArray 
) const

Returns all triangles that intersect or are contained within the sphere (technically, this is a ball intersection).

const Tri& G3D::TriTree::operator[] ( int  i) const
inline

Array access to the stored Tris.

void G3D::TriTree::setContents ( const Array< Tri > &  triArray,
const CPUVertexArray vertexArray,
const Settings settings = Settings() 
)

The arrays will be copied, the underlying Array<Tri> is guaranteed to be in the same order as the parameter Tri Array.

Zero area triangles are retained in the array, but will never be collided with.

void G3D::TriTree::setContents ( const Array< SurfaceRef > &  surfaceArray,
ImageStorage  newStorage = IMAGE_STORAGE_CURRENT,
const Settings settings = Settings() 
)

This will construct a CPUVertexArray, setting all normals, tangents, and texture coordinates to 0, material will be NULL.

Uses Surface::getTris to extract the triangles from each surface and then is identical to the other setContents, without the extra tri copying

int G3D::TriTree::size ( ) const
inline
Stats G3D::TriTree::stats ( int  valuesPerNode) const

Walk the entire tree, computing statistics.


documentation generated on Sat Sep 1 2012 17:52:09 using doxygen 1.8.1.2