quadtree.h

一个纹理地形渲染器

            const int nodeB = nodeA + stride;
            const int nodeC = nodeB + stride;
            const int nodeD = nodeC + stride;

            renderRecurse(nodeA, level, stride, world_ax, world_ay, world_bx, world_by, frustum, threshold);       // top left
            renderRecurse(nodeB, level, stride, world_bx, world_ay, world_cx, world_by, frustum, threshold);       // top right
            renderRecurse(nodeC, level, stride, world_ax, world_by, world_bx, world_cy, frustum, threshold);       // bottom left
            renderRecurse(nodeD, level, stride, world_bx, world_by, world_cx, world_cy, frustum, threshold);       // bottom right
        }
    }

    /// quickly whip up a vector 4 class, we need x,y,z,w for clip space!

    class Vector4 : public Mathematics::Vector
    {
    public:

        Vector4(float x, float y, float z, float w)
        {
            this->x = x;
            this->y = y;
            this->z = z;
            this->w = w;
        }

        float w;
    };
   
    /// transform 3 space vector by matrix assuming its w=1: returns homogeneous vector x,y,z,w 

    Vector4 transform(const Matrix &matrix, const Vector &vector)
    {
        return Vector4( vector.x * matrix.m11 + vector.y * matrix.m12 + vector.z * matrix.m13 + matrix.m14,
                        vector.x * matrix.m21 + vector.y * matrix.m22 + vector.z * matrix.m23 + matrix.m24,
		                vector.x * matrix.m31 + vector.y * matrix.m32 + vector.z * matrix.m33 + matrix.m34,
		                vector.x * matrix.m41 + vector.y * matrix.m42 + vector.z * matrix.m43 + matrix.m44 );
    }

    enum ClipCode
    {
	    LEFT = 1,
	    RIGHT = 2,
	    TOP = 4,
	    BOTTOM = 8,
	    NEAR = 16,
	    FAR = 32,
    };

    /// calculate clip code for point in Direct3D style clip coordinates.

    int clipCode(const Vector4 &vector)
    {
		// code bits: [f][n][b][t][r][l]

		int code = 0;

		if (vector.z<=0) code = NEAR;
          
        // note: just near plane clipping here, the rest is done in screen space in the horizon methods

		return code;
    }

    bool clipLine(Vector4 &a, Vector4 &b)
	{
		int code_a = clipCode(a);
		int code_b = clipCode(b);

		if ((code_a | code_b)==0)
		{
			// trivially accept

            return true;
		}
		else if (code_a & code_b)
		{
			// trivially reject

            return false;
		}

		const float dx = b.x - a.x;
		const float dy = b.y - a.y;
		const float dz = b.z - a.z;
		const float dw = b.w - a.w;

        // near plane

        if (code_a & NEAR)
        {
			const float t = - a.z / dz;

			a.x = a.x + dx * t;
			a.y = a.y + dy * t;
			a.z = a.z + dz * t;
			a.w = a.w + dw * t;
        }
        else if (code_b & NEAR)
        {
			const float t = - b.z / dz;

			b.x = a.x + dx * t;
			b.y = a.y + dy * t;
			b.z = a.z + dz * t;
			b.w = a.z + dz * t;
        }

        return true;
    }
    
    /// projects and transforms to viewport space

    void projectAndViewportTransform(Vector4 &vector, float width, float height)
    {
        const float oow = 1.0f / vector.w;
       
        vector.x *= oow;
        vector.y *= oow;

        vector.x = (vector.x+1)*width*0.5f;
        vector.y = (vector.y+1)*height*0.5f;
    }

    /// clip and render line.
    /// inserts line into horizon.

    void clipAndRenderLine(Horizon &horizon, Vector4 a, Vector4 b, float width, float height)
    {
        if (clipLine(a,b))
        {
            projectAndViewportTransform(a, width, height);
            projectAndViewportTransform(b, width, height);

            horizon.insert(a.x, a.y, b.x, b.y);
        }
    }

    /// clip and test line.
    /// returns true if the entire line is below the horizon or outside frustum, false if any part is visible.

    bool clipAndTestLine(Horizon &horizon, Vector4 a, Vector4 b, float width, float height)
    {
        if (clipLine(a,b))
        {
            projectAndViewportTransform(a, width, height);
            projectAndViewportTransform(b, width, height);

            return horizon.test(a.x, a.y, b.x, b.y)==Horizon::BELOW;
        }

        return true;
    }

    /// recursive worker function for determining visible terrain tiles with horizon culling.
    ///
    /// this function is considerably more complex than the pseudocode in the paper, the reason
    /// being that this function determines visible nodes, while that pseudocode simply found the
    /// set of culled nodes -- a subtle difference! its much more efficient this way, as there
    /// should be less visible nodes than culled ones.
    ///
    /// @param index the index of the current quadtree node in the nodes array
    /// @param level the current level of the quadtree, 0 is the first level (a single 1x1 node covering the whole quadtree), then 1, 2, 3 ... up to leaf nodes.
    /// @param stride the number of nodes between each successive child node at this level (swizzled memory format, nodes are stored in memory in recurse order)
    /// @param x1 the left integer coordinate of the current quadtree node in heightfield samples
    /// @param y1 the top integer coordinate of the current quadtree node in heightfield samples
    /// @param x2 the right integer coordinate of the current quadtree node in heightfield samples
    /// @param y2 the bottom integer coordinate of the current quadtree node in heightfield samples
    /// @param world_x1 the left coordinate of the current quadtree node in world coordinates
    /// @param world_y1 the top coordinate of the current quadtree node in world coordinates
    /// @param world_x2 the right coordinate of the current quadtree node in world coordinates
    /// @param world_y2 the bottom coordinate of the current quadtree node in world coordinates
    /// @param horizon the horizon buffer
    /// @param frustum the view frustum
    /// @param tiles the array of visible terrain tiles
    /// @param tileLevel the level in the quadtree at which each node maps 1:1 to a terrain tile
    /// @param tileResolution the resolution of the terrain in tiles (see Terrain::getResolution)
    /// @param threshold the error threshold
    /// @param inserted true if already inserted into horizon (dont insert child nodes when parent is inserted already)

    void visibleTerrainTilesRecurse( unsigned int index, unsigned int level, unsigned int stride, 
                                     int x1, int y1, int x2, int y2,
                                     float world_x1, float world_y1, float world_x2, float world_y2,
                                     Horizon &horizon, 
                                     const Frustum &frustum, 
                                     std::vector<int> &tiles, unsigned int tileLevel, int tileResolution,
                                     float threshold, bool inserted )
    {
        QuadtreeNode &node = nodes[index];

        if (level<=tileLevel)
        { 
            // test node maximum against horizon and stop recursion if entirely below

            Quad minimumQuad = node.quad(world_x1, world_y1, world_x2, world_y2, QuadtreeNode::MINIMUM);
            Quad maximumQuad = node.quad(world_x1, world_y1, world_x2, world_y2, QuadtreeNode::MAXIMUM);

            Vector4 a = transform(frustum.matrix, maximumQuad.a);
            Vector4 b = transform(frustum.matrix, maximumQuad.b);
            Vector4 c = transform(frustum.matrix, maximumQuad.c);
            Vector4 d = transform(frustum.matrix, maximumQuad.d);

            Vector4 e = transform(frustum.matrix, minimumQuad.a);
            Vector4 f = transform(frustum.matrix, minimumQuad.b);
            Vector4 g = transform(frustum.matrix, minimumQuad.c);
            Vector4 h = transform(frustum.matrix, minimumQuad.d);
            
            bool below = clipAndTestLine(horizon, a, b, frustum.width, frustum.height);
            below &= clipAndTestLine(horizon, b, c, frustum.width, frustum.height);
            below &= clipAndTestLine(horizon, c, d, frustum.width, frustum.height);
            below &= clipAndTestLine(horizon, d, a, frustum.width, frustum.height);

            // look at figure 4 again, and notice that min/max planes are not vertically 
            // aligned above each other in screen space because the perspective transform
            // skews them horizontally - this is bad! the extra line checks below are
            // therefore required to ensure proper bounding of the node samples.
            //
            // try commenting them out and watch what happens... oooh that was hard to debug! :(

            below &= clipAndTestLine(horizon, a, e, frustum.width, frustum.height);
            below &= clipAndTestLine(horizon, b, f, frustum.width, frustum.height);
            below &= clipAndTestLine(horizon, c, g, frustum.width, frustum.height);
            below &= clipAndTestLine(horizon, d, h, frustum.width, frustum.height);
            
            if (below)
                return;

            // if at tile level then the tile covered by this node must be visible so add it to tile array

            if (level==tileLevel)
            {
                tiles.push_back(x1+y1*tileResolution);

                // stop now if we have already inserted into horizon

                if (inserted)
                    return;
            }
        }
        
        // test if screen space error is acceptable or leaf node

        bool insertPending = false;

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

            if (error<=threshold || level==levels.size()-1)
            {
                // set inserted flag to true

                inserted = true;

                // we cant insert just yet, we must do it after we first recurse to child nodes
                // or we will clobber their checks against the horizon, think about it...

                insertPending = true;
            }
        }

        // recurse into child nodes

        if (level<levels.size()-1)
        {
            // calculate data for traversal

            level ++;

            assert(level<(int)levels.size());

            stride = (stride - 1) >> 2;

            index ++;

            const int ax = x1<<1;            // a | .
            const int cx = x2<<1;            // - b -
            const int bx = (ax+cx)>>1;       // . | c

            const int ay = y1<<1;