quadtree.h

/*--License:
        Lilith 3D Engine
        Copyright Lee Thomason (Grinning Lizard Software) 2002-2007
        www.grinninglizard.com/lilith

        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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

        The full text of the license can be found in license.txt
*/

#ifndef LILITH_QUADTREE_INCLUDED
#define LILITH_QUADTREE_INCLUDED

#include "../grinliz/gldebug.h"
#include "mesh.h"
#include "terrainmesh.h"

namespace lilith3d
{

class Mesh;


class QuadTree : public TerrainListener
{
  public:
        QuadTree();     
        ~QuadTree();

        void AddMesh( Mesh* item );     

        // Basic visible culling
        void DoCulling( bool stencilObjects = false );

        // Culling, accounting for shadow cast
        //void DoCullingShadow( const grinliz::Rectangle2F& shadowBounds, U32 meshMask );


        BuildingMesh* FindBuilding( int mapX, int mapY );

        // The TerrainMesh will notify the quadtree of a terrain change
        // so that the quadtree can update the z values
        virtual void TerrainChange( const grinliz::Rectangle2I& vertexBounds );
        
        // After culling, the root of the mesh list to be rendered
        // Linked list of all visible meshes
        Mesh* GetMeshRoot()                     { return meshRoot; }
        // If you can see the mesh, you can see the shadow. (Or that's the approximation
        // lilith uses.) However, you can often seen the shadows but not the mesh. This
        // is a link list of shadow-only renders.
        Mesh* GetMeshShadowRoot()       { return meshShadowRoot; }
        // All the foliage
        Mesh* GetFoliageRoot()  { return foliageRoot; }
        // All the trees
        Mesh* GetTreeRoot()             { return treeRoot; }
        // All the stencil decals
        Mesh* GetDecalStencilRoot() { return decalStencilRoot; }
        
        // Debugging - how many nodes of the tree are in use?
        float NodesInUse()      { return (float)nodesInUse / (float)NUM_QUADNODES; };

        void IntersectRay( int flags, const grinliz::Ray& ray, LilithObjectList* vec );

        enum {
                // LOD 0: 1 node
                // LOD 1: 4 nodes
                // LOD 2: 16
                // LOD 3: 64
                // #nodes at level = ( 1 << (lod*2) )
                // LOD 8: 64k
                
                MAX_LOD = MAP_POWER-2,
                QUADLEN = ( 1<<MAX_LOD ),
                QUADLEN_SQUARED = QUADLEN * QUADLEN,
                NUM_QUADNODES  = QUADLEN_SQUARED + QUADLEN_SQUARED/4 + QUADLEN_SQUARED/16 + QUADLEN_SQUARED/64 + QUADLEN_SQUARED/256 + 2*QUADLEN_SQUARED/1024
        };

  private:      

        struct QuadTreeNode
        {
                QuadTreeNode* Children( QuadTreeNode* offsets[] )
                {
                        // The memory is laid out so
                        // that the children of this node are the same
                        // offset in the NEXT lod as THIS lod. Of course the
                        // next LOD has 4 times as many nodes.
                        GLASSERT( lod < QuadTree::MAX_LOD );
                        UPTR offset = ( this - offsets[ lod ] );
                        QuadTreeNode* result = offsets[ lod+1 ] + (offset<<2);
                        return result;
                }

                QuadTreeNode* Child( U32 i, QuadTreeNode* offsets[] )
                {
                        GLASSERT( lod < QuadTree::MAX_LOD );
                        GLASSERT( i<4 );

                        QuadTreeNode* result = 0;
                        U32 offset = (U32)( this - offsets[ lod ] );
                        result = offsets[ lod+1 ] + (offset<<2) + i;
                        return result;
                }

                QuadTreeNode* Parent( QuadTreeNode* offsets[] )
                {
                        if ( lod == 0 )
                                return 0;
                        unsigned offset = (unsigned)(this - offsets[ lod ]);
                        QuadTreeNode* result = offsets[ lod-1 ] + (offset>>2);
                        return result;
                }

                static unsigned LODToSize( U32 lod )    { return ( MAPSIZE >> lod ); }

                unsigned Size() { return LODToSize( lod ); }
                unsigned LOD()  { return lod; }

                void Init( U32 _x, U32 _y, U32 _lod ) {
                        sentinel.next = &sentinel;
                        sentinel.prev = &sentinel;
                        this->x = _x;
                        this->y = _y;
                        this->lod = _lod;
                }

                // FIXME Sum to 16 bytes 
                MeshNode                sentinel;               // 12 bytes - damn vtable!
                U16                             x;                              // in map & vertex coordinates, requires 13 bits
                U16                             y;                              // in map & vertex coordinates, requires 13 bits
                U16                             lod;                    // requires 4 bits
        };
        
        void InitNodeRec( QuadTree::QuadTreeNode* node, unsigned x, unsigned y, unsigned lod );
        void DoCullingRec( QuadTreeNode* node, int frustum );
        void TerrainChangeRec( const grinliz::Rectangle2I& vertexBounds, QuadTreeNode* node );
        void IntersectRayRec( int flags, QuadTreeNode* node, const grinliz::Ray& ray, const grinliz::Rectangle2I& clip, LilithObjectList* vec );

        //void Clear( QuadTreeNode* node );

        void AddToList( Mesh* mesh, bool onlyShadow ) 
        {
                GLASSERT( mesh != meshRoot );
                GLASSERT( mesh != foliageRoot );
                GLASSERT( mesh != treeRoot );

                if ( mesh->Type() == TREEMESH ) {
                        mesh->nextRender = treeRoot;
                        treeRoot = mesh;
                }
                else if ( mesh->Type() == FOLIAGEMESH ) {
                        mesh->nextRender = foliageRoot;
                        foliageRoot = mesh;
                }
                else if ( mesh->Type() == DECALMESH && mesh->Stencil() )
                {
                        mesh->nextRender = decalStencilRoot;
                        decalStencilRoot = mesh;
                }
                else {
                        if ( onlyShadow ) {
                                mesh->nextRender = meshShadowRoot;
                                meshShadowRoot = mesh;
                        }
                        else {
                                mesh->nextRender = meshRoot;
                                meshRoot = mesh;
                        }
                }       
        }


        QuadTree::QuadTreeNode root[ NUM_QUADNODES ];   // FIXME: align to 16 bit boundaries?
        QuadTree::QuadTreeNode* offsets[ MAX_LOD+1 ];

        Lilith3D* lilith;
        Mesh* meshRoot;
        Mesh* meshShadowRoot;
        Mesh* foliageRoot;
        Mesh* treeRoot;
        Mesh* decalStencilRoot;

        unsigned nodesInUse;
        grinliz::Rectangle3F quadTreeAABB;
        //U32 cullingMask;
        //bool stencilObjects;
};

};      //namespace lilith3d
#endif

---