KdtreeAccelerator.h

Go to the documentation of this file.

/*
 * Copyright (C) <2012> <EDF-R&D> <FRANCE>
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU General Public License for more details.
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */
 
#ifndef KDTREEACCELERATOR_H
#define KDTREEACCELERATOR_H
 
#include "Geometry/BBox.h"
#include <vector>
#include "Geometry/Shape.h"
#include "Accelerator.h"
 
typedef struct kdNode
{
    bool isLeaf()
    {
        return ((int)(flag & 3)) == 3;
    } 
    bool isNode()
    {
        return ((int)(flag & 3)) < 3;
    } 
    unsigned int getNbPrimitives()
    {
        return nbPrims >> 2;
    } 
    unsigned int AboveChild()
    {
        return secondChild >> 2;
    } 
    unsigned int* getPrims()
    {
        return prims;
    } 
    int getAxe()
    {
        return (flag & 3);
    } 
    float getAxeValue()
    {
        return split;
    } 
    unsigned int getFirstIndex()
    {
        return firstIndex;
    } 
    void createLeaf(unsigned int _nbPrims, unsigned int _firstIndex,
                    unsigned int* _prims);                           
    void createNode(int axis, float _split, unsigned int nextChild); 
private:
    union
    {
        int flag; 
        unsigned int
            secondChild;      
        unsigned int nbPrims; 
    };
 
    union
    {
        float split;             
        unsigned int firstIndex; 
        unsigned int* prims;     
    };
} KDNode;
 
typedef struct infoPrim
{
    unsigned int indexPrim;
    BBox box;
} InfoPrim;
 
/* Uncommented cause not used
struct CompareToMid
{
    CompareToMid(int d, float m) { dim = d; mid = m; }
    int dim;
    float mid;
    bool operator()(InfoPrim a) const
    {
        return a.box.centroid[dim] < mid;
    }
}; */
 
struct TaBRecBoundEdge
{
    TaBRecBoundEdge() {}
    TaBRecBoundEdge(float tt, int pn, bool starting)
    {
        t = tt;
        primNum = pn;
        type = starting ? START : END;
    }
    bool operator<(const TaBRecBoundEdge& e) const
    {
        if (t == e.t)
        {
            return (int)type < (int)e.type;
        }
        else
        {
            return t < e.t;
        }
    }
    float t;
    int primNum;
    enum
    {
        START,
        END
    } type;
};
struct KdToDo
{
    KDNode* node;
    float tmin, tmax;
};
 
struct KdStack
{
    KDNode node;      
    float tmin;       
    float tmax;       
    unsigned int pos; 
};
 
class KdtreeAccelerator : public Accelerator
{
 
public:
    KdtreeAccelerator(std::vector<Shape*>* _initialMesh = NULL, BBox _globalBox = BBox());
    virtual ~KdtreeAccelerator();
 
    virtual bool build();
 
    virtual decimal traverse(Ray* r, std::list<Intersection>& result) const;
 
    void setMaxProfondeur(int _maxProfondeur)
    {
        maxProfondeur = _maxProfondeur;
    }
    int getMaxProfondeur()
    {
        return maxProfondeur;
    }
 
    void setMaxPrimPerLeaf(int _maxPrimPerLeaf)
    {
        maxPrimPerLeaf = _maxPrimPerLeaf;
    }
    int getMaxPrimPerLeaf()
    {
        return maxPrimPerLeaf;
    }
    std::vector<BBox>& getBBox()
    {
        return tableBox;
    }
    void print();
 
    bool alreadyFail;    
    unsigned int nbFail; 
    Ray r;               
    bool trace;          
 
protected:
    void generateMidKdTree(int currentProfondeur, BBox& localBox, unsigned int nbPrims, unsigned int* prims);
    void generateSAHKdTree(int currentProfondeur, BBox& localBox, TaBRecBoundEdge* edges[3],
                           unsigned int nbPrims, unsigned int* prims);
    std::vector<Shape*>* initialMesh; 
                                      //    BBox globalBox;
 
    std::vector<InfoPrim> tablePrimitive; 
    std::vector<BBox> tableBox;           
    std::vector<KDNode> tableNode;
 
    int maxProfondeur;  
    int maxPrimPerLeaf; 
 
    int realMaxProfondeur; 
 
    float isectCost;     
    float emptyBonus;    
    float traversalCost; 
};
 
#endif