BVH Struct Reference

Public Member Functions
int	build (const BBox &_bounds, const std::vector< Triangle > &_triangles)
void	intersect (RayHit &ray) const
void	intersect_fast (RayHit &ray) const

Public Attributes
std::vector< Node >	nodes
std::vector< Triangle >	triangles
int	root
int	direct_tests

Protected Member Functions
int	build (const BBox &bounds, const int begin, const int end)
BBox	triangle_bounds (const int begin, const int end)
void	intersect (const int index, RayHit &ray, const Vector &invd) const
void	intersect_fast (const int index, RayHit &ray, const Vector &invd) const

Detailed Description

Definition at line 180 of file tuto_bvh.cpp.

Member Function Documentation

build() [1/2]

int BVH::build ( const BBox & _bounds, const std::vector< Triangle > & _triangles )

inline

Definition at line 189 of file tuto_bvh.cpp.

    {
        triangles= _triangles;  // copie les triangles pour les trier
        nodes.clear();          // efface les noeuds
        nodes.reserve(triangles.size());
        
        // construit l'arbre... 
        root= build(_bounds, 0, triangles.size());
        // et renvoie la racine
        return root;
    }

intersect() [1/2]

void BVH::intersect ( RayHit & ray ) const

inline

Definition at line 201 of file tuto_bvh.cpp.

    {
        Vector invd= Vector(1 / ray.d.x, 1 / ray.d.y, 1 / ray.d.z);
        intersect(root, ray, invd);
    }

intersect_fast() [1/2]

void BVH::intersect_fast ( RayHit & ray ) const

inline

Definition at line 207 of file tuto_bvh.cpp.

    {
        Vector invd= Vector(1 / ray.d.x, 1 / ray.d.y, 1 / ray.d.z);
        intersect_fast(root, ray, invd);
    }

build() [2/2]

int BVH::build ( const BBox & bounds, const int begin, const int end )

inlineprotected

Definition at line 215 of file tuto_bvh.cpp.

    {
        if(end - begin < 2)
        {
            // inserer une feuille et renvoyer son indice
            int index= nodes.size();
            nodes.push_back(make_leaf(bounds, begin, end));
            return index;
        }
        
        // axe le plus etire de l'englobant
        Vector d= Vector(bounds.pmin, bounds.pmax);
        int axis;
        if(d.x > d.y && d.x > d.z)  // x plus grand que y et z ?
            axis= 0;
        else if(d.y > d.z)          // y plus grand que z ? (et que x implicitement)
            axis= 1;
        else                        // x et y ne sont pas les plus grands...
            axis= 2;
 
        // coupe l'englobant au milieu
        float cut= bounds.centroid(axis);
        
        // repartit les triangles 
        Triangle *pm= std::partition(triangles.data() + begin, triangles.data() + end, triangle_less1(axis, cut));
        int m= std::distance(triangles.data(), pm);
        
        // la repartition des triangles peut echouer, et tous les triangles sont dans la meme partie... 
        // forcer quand meme un decoupage en 2 ensembles 
        if(m == begin || m == end)
            m= (begin + end) / 2;
        assert(m != begin);
        assert(m != end);
        
        // construire le fils gauche
        // les triangles se trouvent dans [begin .. m)
        BBox bounds_left= triangle_bounds(begin, m);
        int left= build(bounds_left, begin, m);
        
        // on recommence pour le fils droit
        // les triangles se trouvent dans [m .. end)
        BBox bounds_right= triangle_bounds(m, end);
        int right= build(bounds_right, m, end);
        
        int index= nodes.size();
        nodes.push_back(make_node(bounds, left, right));
        return index;
    }

triangle_bounds()

BBox BVH::triangle_bounds ( const int begin, const int end )

inlineprotected

Definition at line 264 of file tuto_bvh.cpp.

    {
        BBox bbox= triangles[begin].bounds();
        for(int i= begin +1; i < end; i++)
            bbox.insert(triangles[i].bounds());
        
        return bbox;
    }

intersect() [2/2]

void BVH::intersect ( const int index, RayHit & ray, const Vector & invd ) const

inlineprotected

Definition at line 273 of file tuto_bvh.cpp.

    {
        const Node& node= nodes[index];
        if(node.bounds.intersect(ray, invd))
        {
            if(node.leaf())
            {
                for(int i= node.leaf_begin(); i < node.leaf_end(); i++)
                    triangles[i].intersect(ray);
            }
            else // if(node.internal())
            {
                intersect(node.internal_left(), ray, invd);
                intersect(node.internal_right(), ray, invd);
            }
        }
    }

intersect_fast() [2/2]

void BVH::intersect_fast ( const int index, RayHit & ray, const Vector & invd ) const

inlineprotected

Definition at line 291 of file tuto_bvh.cpp.

    {
        const Node& node= nodes[index];
        if(node.leaf())
        {
            for(int i= node.leaf_begin(); i < node.leaf_end(); i++)
                triangles[i].intersect(ray);
        }
        else // if(node.internal())
        {
            const Node& left_node= nodes[node.left];
            const Node& right_node= nodes[node.right];
            
            BBoxHit left= left_node.bounds.intersect(ray, invd);
            BBoxHit right= right_node.bounds.intersect(ray, invd);
            if(left && right)                                                   // les 2 fils sont touches par le rayon...
            {
                if(left.centroid() < right.centroid())                          // parcours de gauche a droite
                {
                    intersect_fast(node.internal_left(), ray, invd);
                    intersect_fast(node.internal_right(), ray, invd);
                }
                else                                                            // parcours de droite a gauche                                        
                {
                    intersect_fast(node.internal_right(), ray, invd);
                    intersect_fast(node.internal_left(), ray, invd);
                }
            }
            else if(left)                                                       // uniquement le fils gauche
                intersect_fast(node.internal_left(), ray, invd);
            else if(right)
                intersect_fast(node.internal_right(), ray, invd);               // uniquement le fils droit
        }
    }

Member Data Documentation

nodes

std::vector<Node> BVH::nodes

Definition at line 182 of file tuto_bvh.cpp.

triangles

std::vector<Triangle> BVH::triangles

Definition at line 183 of file tuto_bvh.cpp.

root

int BVH::root

Definition at line 184 of file tuto_bvh.cpp.

direct_tests

int BVH::direct_tests

Definition at line 186 of file tuto_bvh.cpp.

---

The documentation for this struct was generated from the following file:

• gkit2_tutos/tuto_bvh.cpp