quadtree.h

一个纹理地形渲染器

// Quadtree class

#pragma once

#include "Frustum.h"
#include "Horizon.h"
#include "Terrain.h"
#include "QuadtreeNode.h"
#include "QuadtreeLevel.h"

using namespace Mathematics;


/// A quadtree of nodes forming min/max planes that bound heightfield data z=f(x,y).
/// Implements the terrain approximation quadtree as described in the article.

class Quadtree
{
public:

    /// Initialize the quadtree fitting the supplied heightfield data.

    void initialize(System::Display *display, Heightfield &heightfield, int resolution)
    {
        this->display = display;

        // create material

        material = display->createMaterial();
        material->ambient(Color(1,1,1));
        material->diffuse(Color(1,1,1));
        material->specular(Color(0,0,0));
        material->power(0);

        // heightfield must be square!

        assert(heightfield.width()==heightfield.height());

        this->resolution = resolution;
        this->heightfield = &heightfield;

        // calculate number of node levels and total number of nodes in quadtree
        
        const int leafSize = resolution;

        int total = 0;
        int width = (heightfield.width() - 1) / leafSize;
        int height = (heightfield.height() - 1) / leafSize;
        int levelCount = 0;
        do
        {
            total += width * height;

            width >>= 1;
            height >>= 1;

            levelCount++;
        }
		while (width>0 && height>0);

        // allocate nodes

		nodes.resize(total);
        
        // store information about node levels

        levels.resize(levelCount);

        width = (heightfield.width() - 1) / leafSize;
        height = (heightfield.height() - 1) / leafSize;

        for (int l=levelCount-1; l>=0; l--)
        {
            levels[l].width = width;
            levels[l].height = height;
            levels[l].delta = (heightfield.width()-1) / width;
            levels[l].size = width * height;

            width >>= 1;
            height >>= 1;
        }

        // funky stride calculations

        int stride = 1;

        for (int l=levelCount-1; l>0; l--)
        {
            levels[l].stride = stride;

            stride = stride*4 + 1;
        }

        assert(stride==total);

        levels[0].stride = stride;

        rebuild();
    }

    /// quadtree build type enumeration

    enum BuildType
    {
        TOPDOWN,        ///< standard top-down build
        BOTTOMUP        ///< optimized bottom-up build as described in "Making it Dynamic" section
    };

    /// rebuild entire quadtree using specified method.

    void rebuild(BuildType type=TOPDOWN)
    {
        float x1,y1,x2,y2;
        heightfield->vectorAtIndex(0, 0, x1, y1);
        heightfield->vectorAtIndex(heightfield->width()-1, heightfield->height()-1, x2, y2);

        if (type==TOPDOWN)
        {
            buildTopDownRecurse(0, 0, levels[0].stride, 0, 0, 1, 1, x1, y1, x2, y2);
        }
        else
        {
            LeastSquaresSums sums;
            buildBottomUpRecurse(0, 0, levels[0].stride, 0, 0, 1, 1, x1, y1, x2, y2, sums);
        }
    }

    /// render quadtree nodes in wireframe to given error threshold.

    void render(const Frustum &frustum, float threshold)
    {
        display->blendMode(System::Display::Blend::ADD);
        
        display->selectMaterial(material);

        display->beginLineStream();

        float x1,y1,x2,y2;
        heightfield->vectorAtIndex(0, 0, x1, y1);
        heightfield->vectorAtIndex(heightfield->width()-1, heightfield->height()-1, x2, y2);

        renderRecurse(0, 0, levels[0].stride, x1, y1, x2, y2, frustum, threshold);

        display->endLineStream();

        display->selectMaterial(0);

        display->blendMode(System::Display::Blend::NONE);
    }

    /// determine visible terrain tiles using horizon culling operating at specified error threshold.

    void visibleTerrainTiles(Horizon &horizon, const Frustum &frustum, std::vector<int> &tiles, int tileSize, int tileResolution, float threshold)
    {
        int tileLevel = -1;

        for (unsigned int i=0; i<levels.size(); i++)
        {
            if (levels[i].delta==tileSize)
            {
                tileLevel = i;
                break;
            }
        }

        assert(tileLevel>=0);
        assert(tileLevel<(int)levels.size());

        horizon.clear();

        float x1,y1,x2,y2;
        heightfield->vectorAtIndex(0, 0, x1, y1);
        heightfield->vectorAtIndex(heightfield->width()-1, heightfield->height()-1, x2, y2);

        visibleTerrainTilesRecurse(0, 0, levels[0].stride, 0, 0, 1, 1, x1, y1, x2, y2, horizon, frustum, tiles, (unsigned) tileLevel, tileResolution, threshold, false);
    }

    typedef std::vector<QuadtreeNode> Nodes;           ///< typedef for a vector of quadtree nodes for easy access and iteration
    typedef std::vector<QuadtreeLevel> Levels;         ///< typedef for a vector of quadtree levels for easy access and iteration

protected:

    inline void renderWireframeQuad(System::Display *display, const Vector &a, const Vector &b, const Vector &c, const Vector &d, const Vector &normal = Vector(0,0,1))
    {
        display->renderLine(a,b);
        display->renderLine(b,c);
        display->renderLine(c,d);
        display->renderLine(d,a);
    }

    void renderSlab(System::Display *display, const Mathematics::Slab &slab)
    {
        // build slab vertices

	    const float nx_x1 = slab.normal.x * slab.x1;
        const float ny_y1 = slab.normal.y * slab.y1;
        const float nx_x2 = slab.normal.x * slab.x2;
        const float ny_y2 = slab.normal.y * slab.y2;

	    Vector vertex[8];
        vertex[0] = Vector(slab.x1, slab.y1, slab.maximum - nx_x1 - ny_y1);
        vertex[1] = Vector(slab.x2, slab.y1, slab.maximum - nx_x2 - ny_y1);
        vertex[2] = Vector(slab.x2, slab.y2, slab.maximum - nx_x2 - ny_y2);
        vertex[3] = Vector(slab.x1, slab.y2, slab.maximum - nx_x1 - ny_y2);
        vertex[4] = Vector(slab.x1, slab.y1, slab.minimum - nx_x1 - ny_y1);
        vertex[5] = Vector(slab.x2, slab.y1, slab.minimum - nx_x2 - ny_y1);
        vertex[6] = Vector(slab.x2, slab.y2, slab.minimum - nx_x2 - ny_y2);
        vertex[7] = Vector(slab.x1, slab.y2, slab.minimum - nx_x1 - ny_y2);

	    // render slab faces

	    renderWireframeQuad(display, vertex[0], vertex[1], vertex[2], vertex[3]);		// top
	    renderWireframeQuad(display, vertex[4], vertex[5], vertex[6], vertex[7]);		// bottom

	    // connect faces with lines

	    display->renderLine(vertex[0], vertex[4]);
	    display->renderLine(vertex[1], vertex[5]);
	    display->renderLine(vertex[2], vertex[6]);
	    display->renderLine(vertex[3], vertex[7]);
    }

    /// calculate screen space node error.
    /// the error corresponds roughly to the vertical distance between the
    /// minimum and maximum nodes in screen space, hence the scale by (1-direction.z).

    float screenSpaceError(const QuadtreeNode &node, float cx, float cy, const Vector &eye, const Vector &direction, float k)
    {
        // determine node screen space error

        const float dx = cx - eye.x;
        const float dy = cx - eye.y;
        const float dz = eye.z;

        const float inverseDistance = Float::inverse_sqrt(dx*dx+dy*dy+dz*dz);
        
        return node.getError() * inverseDistance * k * (1.0f-Float::abs(direction.z));
    }

    /// recursive worker function for rendering quadtree nodes.

    void renderRecurse( unsigned int index, unsigned int level, unsigned int stride, 
                        float world_x1, float world_y1, float world_x2, float world_y2,
                        const Frustum &frustum, float threshold )
    {
        // determine screen space error

        QuadtreeNode &node = nodes[index];

        const float error = screenSpaceError(node, (world_x1+world_x2)*0.5f, (world_y1+world_y2)*0.5f, frustum.eye, frustum.direction, frustum.k);

        // render if error threshold is acceptable or leaf node

        if (error<=threshold || level==levels.size()-1)
        {
            // render node in wireframe

            Mathematics::Slab slab = node.slab(world_x1, world_y1, world_x2, world_y2);
            renderSlab(display, slab);
        }
        else
        {
            // recurse into children

            level ++;

            stride = (stride - 1) >> 2;

            index ++;

            const float world_ax = world_x1;
            const float world_cx = world_x2;
            const float world_bx = (world_x1+world_x2)*0.5f;

            const float world_ay = world_y1;
            const float world_cy = world_y2;
            const float world_by = (world_y1+world_y2)*0.5f;

            const int nodeA = index;