---

RT_Grid.h

Go to the documentation of this file.

/*
    File:           RT_Grid.h
    
    Function:       Interface for hierarchical grid raytracer
    
    Author(s):      Andrew Willmott, 1996-2000

    Copyright:      (c) 1997-2000, Andrew Willmott
*/

#ifndef __RT_Grid__
#define __RT_Grid__
    
#include "RT_Defs.h"
#include "RT_Prim.h"
#include "RT_RayStats.h"
#include "gcl/VecUtil.h"

class Renderer;

// --- RT_Grid support classes ------------------------------------------------


//  Private data structures

struct  PrimEntry;
struct  PrimListEntry;
struct  ObjEntry;
class   GridStore;

#ifdef RT_MEM_DEFRAG
const Int   PAGE_BITS = 12;         // 2 ^ PAGE_BITS = size of a memory page.
const Int   PAGE_PTR_BITS = PAGE_BITS - 2;
const Int   PAGE_PTR_SIZE = 1 << PAGE_PTR_BITS;
const Int   PAGE_PTR_MASK = (1 << PAGE_PTR_BITS) - 1;
#else
const Int   PAGE_BITS = 16;         // 2 ^ PAGE_BITS = size of a memory page.
const Int   PAGE_PTR_BITS = PAGE_BITS - 2;
const Int   PAGE_PTR_SIZE = 1 << PAGE_PTR_BITS;
const Int   PAGE_PTR_MASK = (1 << PAGE_PTR_BITS) - 1;
#endif

class GridStore
{

public:
    Void        Init(Int size);
    Void        Free();
    Int         NumPages() 
                { return numPages; };
    GCLReal     MemoryUsage()
                { return(mem / 1024.0); };
    
    PrimEntry*& operator [](Int i)
                { return(pages[i >> PAGE_PTR_BITS][i & PAGE_PTR_MASK]); };

protected:
    PrimEntry***    pages;      // Array of pointers to page data
    Int             numPages;   // How many page pointers we have
    Int             mem;
};


// --- RT_Grid Class ----------------------------------------------------------


class RT_Grid 
{
public:
// --- Public interface -------------------------------------------------------

    Void        MasterInit();
    Void        Init();
    Void        Free();

    Void        AddObject(RT_Object *object);
    Void        RemoveObject(RT_Object *object);
    Void        PrepareGrid();  

    Bool        IntersectionExists(
                    const Point&    start,
                    const Point&    end,
                    RT_Prim*        origPrim = 0,
                    RayStats*       stats = 0
                );
    
    RT_Prim*    ClosestIntersection(
                    const Point&    start,
                    const Vector&   direction,
                    RT_Prim*        origPrim = 0,
                    RayStats*       stats = 0
                );
    
    // Misc
    Void        HierPrint(ostream& s, Int index);
    static Void SetTag(Int tag)
                { sTag = tag; };
    Void        Draw(Renderer &r, Int level);
    
    // Memory management
    Void        DumpMemoryUsage();
    GCLReal     GridMemoryUsage();
    GCLReal     MemoryUsage();
    static Void SetMemLimit(Int maxKbs);

    // Low-level
    Void        SetBounds(Point &bmin, Point &bmax)
                { min = bmin; max = bmax; };
    Void        SetupGrid();
    Void        AddTriangle(RT_Tri *tri);
    Void        AddGeneric(RT_Gen *gen);
    GCLReal     GetScale()
                { return(MaxElt(max - min)); };

    // Caching
    RT_Prim*    hitPrim;    
    GCLReal     hitT;       

    Point       min, max;   
    
// --- Private! ---------------------------------------------------------------
protected:
    ObjEntry*           addedObjs;  
    ObjEntry*           addObjs;    

    GridStore           grid;       
    PrimListEntry*      addPrims;   
    RT_Grid*            subGrids;   
    RT_Grid*            next;       

    GCLReal             cellSize;
    GCLReal             areaLimit;
    Int                 numCells[3];
    Int                 xSpan, ySpan;   
    Int                 totalCells, totalPrims;

    //  Class globals

public:
    static GCLReal      sEpsilon;       
    static Int          sMem;           
    static Int          sMemLimit;      
    static Int          sTriMem;        
    static Int          sGenMem;        
    static Int          sPointMem;      

    static Int          sMaxCells;      
    static Int          sMaxCellPrims;
    static GCLReal      sPushSizeLimit;
    static GCLReal      sMaxCellRatio;
    static GCLReal      sMinDensity;
    static GCLReal      sMaxExpand;

    //  Grid maintenance

protected:
    Int                 dirty;          
    Int                 level;          
    RT_Grid*            parent;         

    Int                 stamp;          
    static Int          sStamp;         
    static Int          sTag;           
    
    //  Methods
    
    static Void         IncTime()
                        { sStamp++; };
    Void                Stamp()
                        { stamp = sStamp; };
    Bool                IsStamped()
                        { return(stamp == sStamp); };
        
    Void                UpdateBounds(Point& cellMin, Point& cellMax);
    Void                UpdateBounds(RT_Object *object);

    Void                CreateNestedGrids();
    Void                CullSubGrids();
    Void                PushPrimitives();
    Int                 CountPolys(PrimEntry *entry);
    
    Bool                FindGridStart(
                            const Point&    start, 
                            const Vector&   direction,
                            Int             cell[3],
                            Int             increment[3],
                            Int             limit[3], 
                            GCLReal&        tRay,
                            Vector&         tDelta,
                            Vector&         tMax
                        );
    
    Void                RayClampEntryPoint(Int index, Bool backEntry[3], 
                            Vector& fujiPoint, Int cell[3]);
};

struct ObjEntry
{
    RT_Object*      object;
    ObjEntry*       next;
};

#endif

---