libsurf
Programmer's Documentation

Classes | Public Types | Public Member Functions | Private Member Functions | Private Attributes | List of all members
FaceTree Class Reference

Detailed Description

Binary tree for triangles.

A search data structure used to efficiently locate intersecting pairs of triangles. The bounding volume used is an axis-aligned bounding box, and the tree split operator divides the set of triangles along the estimated principal axis of the contained set of vertices. This is a relatively simple implementation which yields fairly well-balanced trees for reasonably shaped triangles. The split operator will fail to produce well-separated child trees for very strongly stretched triangles.

See Also
Intersector

#include <facetree.h>

Collaboration diagram for FaceTree:
[legend]

Classes

class  Segment
 Intersection between triangle and plane. More...
 

Public Types

typedef SharedVector< TriFaceFaceArray
 
typedef boost::shared_ptr
< FaceTree
FaceTreePtr
 
typedef std::vector
< FaceTree::Segment
SegmentArray
 

Public Member Functions

 FaceTree ()
 empty constructor
 
 FaceTree (const TriMesh &t)
 root node constructor
 
bool isLeaf () const
 check if this is a leaf node
 
const FaceTreeleft () const
 access left sibling
 
const FaceTreeright () const
 access right sibling
 
uint nfaces () const
 count faces belonging to this tree
 
const TriFaceface (uint i) const
 access face
 
const TriEdge & edge (uint i) const
 access edge
 
void split (uint depth, uint npmin)
 split recursively
 
bool bbintersects (const FaceTree &other) const
 check bounding box intersection
 
uint intersect (const FaceTree &other, FaceIsecMap &m) const
 determine face-edge intersections
 
uint selfIntersect (FaceIsecMap &m) const
 determine the number of self-intersections
 
void collectEdges (Indices &eix) const
 collect edge indices
 
void intersectPlane (const Plane &pln, Indices &ifaces) const
 collect faces intersected by plane pln
 
void intersectPlane (const Plane &pln, SegmentArray &segments) const
 collect intersection segments with plane pln
 

Private Member Functions

 FaceTree (const FaceArray &fcs, const Indices &ix, uint lv)
 childnode constructor
 
void init ()
 initialize geometric properties
 
void fork ()
 create child nodes
 
bool isLeft (const TriFace &f) const
 check if face belongs to the left child node
 

Private Attributes

FaceTreePtr lft
 children
 
FaceTreePtr rgt
 
FaceArray faces
 shared array of faces, data stored in/owned by root node
 
Indices idx
 indices for this node
 
const TriMeshsrf
 associated mesh
 
Vct3 ctr
 center and principal direction
 
Vct3 pcp
 
BndBox bb
 bounding box
 
uint level
 tree depth
 

The documentation for this class was generated from the following files:
Generated on Mon May 23 2022 03:03:16 for libsurf by   doxygen 1.8.5