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

#include <facetree.h>

Collaboration diagram for FaceTree:


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

Public Types

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

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
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