quadtree.h

一个纹理地形渲染器

            const int cy = y2<<1;
            const int by = (ay+cy)>>1;

            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;

            // a b
            // c d

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

            // recurse into children in bottom to top order in screen space
            //
            // ...or at least attempt to, this seems to be approximate only, hence
            // there are some artifacts in the culling if you look closely.
            //
            // sorry for the hack, i just plain ran out of time - try to come
            // up with an exact way of traversing in the right order, and
            // any artifacts should go away!

            const float dx = world_bx - frustum.base.x;
            const float dy = world_by - frustum.base.y;

            int mask = 0;

            if (dx<0) mask |= 1;
            if (dy<0) mask |= 2;

            switch (mask)
            {
                case 0:
                    visibleTerrainTilesRecurse(nodeA, level, stride, ax, ay, bx, by, world_ax, world_ay, world_bx, world_by, horizon, frustum, tiles, tileLevel, tileResolution, threshold, inserted);
                    visibleTerrainTilesRecurse(nodeB, level, stride, bx, ay, cx, by, world_bx, world_ay, world_cx, world_by, horizon, frustum, tiles, tileLevel, tileResolution, threshold, inserted);
                    visibleTerrainTilesRecurse(nodeC, level, stride, ax, by, bx, cy, world_ax, world_by, world_bx, world_cy, horizon, frustum, tiles, tileLevel, tileResolution, threshold, inserted);
                    visibleTerrainTilesRecurse(nodeD, level, stride, bx, by, cx, cy, world_bx, world_by, world_cx, world_cy, horizon, frustum, tiles, tileLevel, tileResolution, threshold, inserted);
                    break;

                case 1:
                    visibleTerrainTilesRecurse(nodeB, level, stride, bx, ay, cx, by, world_bx, world_ay, world_cx, world_by, horizon, frustum, tiles, tileLevel, tileResolution, threshold, inserted);
                    visibleTerrainTilesRecurse(nodeA, level, stride, ax, ay, bx, by, world_ax, world_ay, world_bx, world_by, horizon, frustum, tiles, tileLevel, tileResolution, threshold, inserted);
                    visibleTerrainTilesRecurse(nodeD, level, stride, bx, by, cx, cy, world_bx, world_by, world_cx, world_cy, horizon, frustum, tiles, tileLevel, tileResolution, threshold, inserted);
                    visibleTerrainTilesRecurse(nodeC, level, stride, ax, by, bx, cy, world_ax, world_by, world_bx, world_cy, horizon, frustum, tiles, tileLevel, tileResolution, threshold, inserted);
                    break;

                case 2:
                    visibleTerrainTilesRecurse(nodeC, level, stride, ax, by, bx, cy, world_ax, world_by, world_bx, world_cy, horizon, frustum, tiles, tileLevel, tileResolution, threshold, inserted);
                    visibleTerrainTilesRecurse(nodeA, level, stride, ax, ay, bx, by, world_ax, world_ay, world_bx, world_by, horizon, frustum, tiles, tileLevel, tileResolution, threshold, inserted);
                    visibleTerrainTilesRecurse(nodeD, level, stride, bx, by, cx, cy, world_bx, world_by, world_cx, world_cy, horizon, frustum, tiles, tileLevel, tileResolution, threshold, inserted);
                    visibleTerrainTilesRecurse(nodeB, level, stride, bx, ay, cx, by, world_bx, world_ay, world_cx, world_by, horizon, frustum, tiles, tileLevel, tileResolution, threshold, inserted);
                    break;

                case 3:
                    visibleTerrainTilesRecurse(nodeD, level, stride, bx, by, cx, cy, world_bx, world_by, world_cx, world_cy, horizon, frustum, tiles, tileLevel, tileResolution, threshold, inserted);
                    visibleTerrainTilesRecurse(nodeC, level, stride, ax, by, bx, cy, world_ax, world_by, world_bx, world_cy, horizon, frustum, tiles, tileLevel, tileResolution, threshold, inserted);
                    visibleTerrainTilesRecurse(nodeB, level, stride, bx, ay, cx, by, world_bx, world_ay, world_cx, world_by, horizon, frustum, tiles, tileLevel, tileResolution, threshold, inserted);
                    visibleTerrainTilesRecurse(nodeA, level, stride, ax, ay, bx, by, world_ax, world_ay, world_bx, world_by, horizon, frustum, tiles, tileLevel, tileResolution, threshold, inserted);
                    break;
            }
        }

        // insert here, on the way back up as to not interfere with node testing

        if (insertPending)
        {
            // insert node minimum quad in horizon

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

            Vector4 a = transform(frustum.matrix, quad.a);
            Vector4 b = transform(frustum.matrix, quad.b);
            Vector4 c = transform(frustum.matrix, quad.c);
            Vector4 d = transform(frustum.matrix, quad.d);
            
            clipAndRenderLine(horizon, a, b, frustum.width, frustum.height);
            clipAndRenderLine(horizon, b, c, frustum.width, frustum.height);
            clipAndRenderLine(horizon, c, d, frustum.width, frustum.height);
            clipAndRenderLine(horizon, d, a, frustum.width, frustum.height);
        }
    }

    /// recursively worker function to build the quadtree top-down.
    ///
    /// @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

    void buildTopDownRecurse( 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 )
    {
        assert(x1!=x2);
        assert(y1!=y2);

        QuadtreeNode &node = nodes[index];

        const int heightfield_x1 = x1 * levels[level].delta;
        const int heightfield_y1 = y1 * levels[level].delta;
        const int heightfield_x2 = x2 * levels[level].delta;
        const int heightfield_y2 = y2 * levels[level].delta;

        LeastSquaresSums sums;
        calculateLeastSquaresSums(*heightfield, heightfield_x1, heightfield_y1, heightfield_x2, heightfield_y2, world_x1, world_y1, sums);

        Vector center;
        node.initialize(sums, *heightfield, heightfield_x1, heightfield_y1, heightfield_x2, heightfield_y2, center);

        if (level<levels.size()-1)
        {
            // parent node

            level ++;

            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;
            const int cy = y2<<1;
            const int by = (ay+cy)>>1;

            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;
            const int nodeB = nodeA + stride;
            const int nodeC = nodeB + stride;
            const int nodeD = nodeC + stride;

            buildTopDownRecurse(nodeA, level, stride, ax, ay, bx, by, world_ax, world_ay, world_bx, world_by);       // top left
            buildTopDownRecurse(nodeB, level, stride, bx, ay, cx, by, world_bx, world_ay, world_cx, world_by);       // top right
            buildTopDownRecurse(nodeC, level, stride, ax, by, bx, cy, world_ax, world_by, world_bx, world_cy);       // bottom left
            buildTopDownRecurse(nodeD, level, stride, bx, by, cx, cy, world_bx, world_by, world_cx, world_cy);       // bottom right
        }
    }

    /// recursively worker function to build the quadtree bottom-up.
    ///
    /// @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

    void buildBottomUpRecurse( 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,
                               LeastSquaresSums &sums )
    {
        assert(x1!=x2);
        assert(y1!=y2);

        QuadtreeNode &node = nodes[index];

        if (level<levels.size()-1)
        {
            // parent node

            level ++;

            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;
            const int cy = y2<<1;
            const int by = (ay+cy)>>1;

            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;
            const int nodeB = nodeA + stride;
            const int nodeC = nodeB + stride;
            const int nodeD = nodeC + stride;

            LeastSquaresSums sumsA, sumsB, sumsC, sumsD;

            buildBottomUpRecurse(nodeA, level, stride, ax, ay, bx, by, world_ax, world_ay, world_bx, world_by, sumsA);       // top left
            buildBottomUpRecurse(nodeB, level, stride, bx, ay, cx, by, world_bx, world_ay, world_cx, world_by, sumsB);       // top right
            buildBottomUpRecurse(nodeC, level, stride, ax, by, bx, cy, world_ax, world_by, world_bx, world_cy, sumsC);       // bottom left
            buildBottomUpRecurse(nodeD, level, stride, bx, by, cx, cy, world_bx, world_by, world_cx, world_cy, sumsD);       // bottom right
            
            // in theory there are samples that overlap between child nodes that should be handled correctly,
            // however, in practice their effect is not noticeable so there is no real need to do so - phew!

			sums = sumsA;
            sums += sumsB;
            sums += sumsC;
            sums += sumsD;

            Vector center;
            node.initialize(sums, center);

            const float normalX = node.getNormalX();
            const float normalY = node.getNormalY();
            
            float minimumD = node.getCenterD();
            float maximumD = minimumD;

            nodes[nodeA].pushOut(world_ax, world_ay, world_bx, world_by, normalX, normalY, maximumD, minimumD);
            nodes[nodeB].pushOut(world_bx, world_ay, world_cx, world_by, normalX, normalY, maximumD, minimumD);
            nodes[nodeC].pushOut(world_ax, world_by, world_bx, world_cy, normalX, normalY, maximumD, minimumD);
            nodes[nodeD].pushOut(world_bx, world_by, world_cx, world_cy, normalX, normalY, maximumD, minimumD);

            node.calculateError(maximumD, minimumD);
        }
        else
        {
            // leaf node assuming 1x1 resolution at leaves (!)

            assert(x2-x1==1);
            assert(y2-y1==1);

            calculateLeastSquaresSums_1x1(*heightfield, x1, y1, world_x1, world_y1, sums);

            Vector center;
            node.initialize(sums, *heightfield, x1, y1, x2, y2, center);
        }
    }

private:

    Nodes nodes;                          ///< the array of nodes in swizzled memory layout
    Levels levels;                        ///< array of quadtree level objects

    int resolution;                       ///< resolution of leaf nodes in terrain samples (assumes square nodes)

    Heightfield *heightfield;             ///< the heightfield object from which this quadtree was generated

    System::Display *display;             ///< display object
    System::Material *material;           ///< material for rendering nodes
};