Jump to content
  • Advertisement
Sign in to follow this  
Nibbles

My Quadtree class... I don't know how to test it...

This topic is 3613 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So I FINALLY grew a pair and actually made an attempt at writing a quadtree class accepting the possibility that I'd get frustrated and quit. I did however managed to whip something out that seems right (to me). Anyways, I have no idea how to test this so if anyone would mind having a quick read through I'd appreciate any advice/criticism/concerns. So far it only builds the quadtree... I'm not sure what the next step is. The coding is probably messy and will stay as such until i know that is in fact... messy. Oh, and I plan on eventually throwing a terrain in the mix (ya, original eh?). Behold:

using System;
using System.Drawing;

namespace MyFramework
{
    public enum QuadTreeNodeType
    {
        Root,
        Node,
        Leaf
    }

    /// <summary>
    /// Description of QuadTreeNode.
    /// </summary>
    public class CQuadTreeNode
    {
        public int iIndex;
        public int iSize;
        public CVector3 v3Center;

        public QuadTreeNodeType Type;

        public CQuadTreeNode qtnParent;
        public CQuadTreeNode[] qtnChild;

        public Rectangle BoundingBox;

        public CQuadTreeNode(CQuadTree quadtree, CQuadTreeNode parent, CVector3 v3center, int size)
        {
            qtnParent = parent;
            if (qtnParent == null)
                Type = QuadTreeNodeType.Root;

            iSize = size;

            v3Center = v3center;

            BoundingBox = new Rectangle((int)v3Center.X - (iSize / 2),	// X
                                        (int)v3Center.Z - (iSize / 2), 	// Y
                                        iSize, 							// W
                                        iSize);							// H

            iIndex = quadtree.iNodeIndex;
            quadtree.iNodeIndex++;

            if (iSize > quadtree.iPatchSize)
            {
                Type = QuadTreeNodeType.Node;
                Subdivide(quadtree, this, iSize / 2);
            }
            else
            {
                Type = QuadTreeNodeType.Leaf;
            }
        }

        public void Subdivide(CQuadTree quadtree, CQuadTreeNode parent, int size)
        {
            qtnChild = new CQuadTreeNode[4];

            CVector3 v1 = new CVector3(v3Center.X - (size / 2), 0, v3Center.Z - (size / 2));
            CVector3 v2 = new CVector3(v3Center.X + (size / 2), 0, v3Center.Z - (size / 2));
            CVector3 v3 = new CVector3(v3Center.X - (size / 2), 0, v3Center.Z + (size / 2));
            CVector3 v4 = new CVector3(v3Center.X + (size / 2), 0, v3Center.Z + (size / 2));

            qtnChild[0] = new CQuadTreeNode(quadtree, this, v1, size);
            qtnChild[1] = new CQuadTreeNode(quadtree, this, v2, size);
            qtnChild[2] = new CQuadTreeNode(quadtree, this, v3, size);
            qtnChild[3] = new CQuadTreeNode(quadtree, this, v4, size);
        }
    }

    /// <summary>
    /// Description of QuadTree.
    /// </summary>
    public class CQuadTree
    {
        public int iSize;
        public int iPatchSize;
        public int iNodeIndex;

        CQuadTreeNode qtnRoot;

        public CQuadTree(int size, int patchsize)
        {
            iSize = size;
            iPatchSize = patchsize;
            iNodeIndex = 0;

            qtnRoot = new CQuadTreeNode(this, null, new CVector3(iSize / 2, 0, iSize / 2), size);
        }
    }
}



Thanks, Scott Ps. After almost 8 years on this bored I suddenly hate my username.

Share this post


Link to post
Share on other sites
Advertisement
Well usually quad trees are made from input data, usually in the form of scene nodes. And the usual process is: if there are more than the maximum number of scene nodes allowed in the current section of the quad trees, then subdivide. Otherwise, stop, and continue with the other sections. You continue until you exhaust all options, meaning that all sections contain a scene node count less than the maximum.

http://www.directionsmag.com/images/articles/spatialDBMS/quadtree.gif

By looking at that you can easily tell that the maximum number of scene nodes allowed is 3.

Share this post


Link to post
Share on other sites
thanks! makes sense... I guess all i really managed to do was figure how how to recursively subdivide. i do have a question though... is terrain data (example of input data) a child of the quadtree or vice versa?

class CTerrain : CQuadtree
{
...
}

or

class CQuadtree :: CTerrain
{
...
}

or am i way out in left field.

thanks

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!