# Quadtree terrain engine need help

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

## Recommended Posts

can anyone already implemented rottgers Quadtree terrain in DX? can i view your code? i found a couple of Rotger Quadtree implementation on the net but its in GL and theres a part of the code where i dont understand specially the iFanCode Table with FanCode array and a FanStart( also in Trent's Pollack Terrain book) thanks

##### Share on other sites
Hi DxDotNet1,
How are you doing?
Well I would say the best way to implement any algorithm is to completely understand what is going on. I have also done some quadtrees and if it's any help. Here is how I designed mine...

[source land = c#]using System;using System.Drawing;using System.Collections;using Microsoft.DirectX;using Microsoft.DirectX.Direct3D;namespace Xilath{	public class QuadTree	{		#region members		private QuadTree topLeft = null;		private QuadTree topRight = null;		private QuadTree bottomLeft = null;		private QuadTree bottomRight = null;		private Rectangle volume;        private Vector3 pos;        private VertexBuffer vb;        private int patchSize = 33;        private int numVertices = 33 * 33;        private int numPrimitives = ((32) * (32)) * 2;		#endregion		#region properties		public bool IsLeaf 		{ 			get { return (topLeft == null && topRight == null && bottomLeft == null && bottomRight == null); } 		}		#endregion		#region constructors		/// <summary>		/// QuadTree Constructor		/// </summary>		/// <param name="terrainVolume">Take a single rectangle as the volume of the terrain</param>		public QuadTree(System.Drawing.Rectangle terrainVolume)		{			this.volume = terrainVolume;		}		#endregion		#region methods		/// <summary>		/// Split the QuadTree recursively till it gets to 32 x 32 patch sizes		/// </summary>		public void Split()		{            if ((volume.Width <= patchSize) && (volume.Height <= patchSize))				return;			topLeft = new QuadTree(new System.Drawing.Rectangle(this.volume.Left, this.volume.Top, this.volume.Width/2, this.volume.Height/2));			topRight = new QuadTree(new System.Drawing.Rectangle((this.volume.Left + this.volume.Width/2), this.volume.Top, this.volume.Width/2, this.volume.Height/2));			bottomLeft = new QuadTree(new System.Drawing.Rectangle(this.volume.Left, (this.volume.Top + this.volume.Height/2), this.volume.Width/2, this.volume.Height/2));			bottomRight = new QuadTree(new System.Drawing.Rectangle((this.volume.Left + this.volume.Width/2), (this.volume.Top + this.volume.Height/2), this.volume.Width/2, this.volume.Height/2));			topLeft.Split();			topRight.Split();			bottomLeft.Split();			bottomRight.Split();		}		/// <summary>		/// Create the indices that is needed to render the terrain		/// </summary>		/// <param name="vertices">The vertices of the terrain</param>		/// <param name="terrainWidth">Terrain width</param>		public void GenerateVertices(Device device, float[] heightValues, int terrainWidth)		{			if(IsLeaf)			{                CustomVertex.PositionNormalTextured[] vertices = new CustomVertex.PositionNormalTextured[numVertices];                int counter = 0;				for(int y = volume.Top; y <= (volume.Top + volume.Height); y++)				{					for(int x = volume.Left; x <= (volume.Left + volume.Width); x++)					{                        vertices[counter] = new CustomVertex.PositionNormalTextured((float)x * 4.0f, heightValues[x * terrainWidth + y], (float)y * 4.0f, x, heightValues[x * terrainWidth + y], y, x, y);                        counter++;					}				}                pos.X = Math.Abs(vertices[0].X - vertices[1088].X);                pos.Y = Math.Abs(vertices[0].Y - vertices[1088].Y);                pos.Z = 0.0f;                vb = new VertexBuffer(typeof(CustomVertex.PositionNormalTextured), numVertices, device, Usage.WriteOnly, CustomVertex.PositionNormalTextured.Format, Pool.Managed);                vb.SetData(vertices, 0, LockFlags.None);                //CreateAABB(vertices);			}			else			{				topLeft.GenerateVertices(device, heightValues, terrainWidth);                topRight.GenerateVertices(device, heightValues, terrainWidth);                bottomLeft.GenerateVertices(device, heightValues, terrainWidth);                bottomRight.GenerateVertices(device, heightValues, terrainWidth);			}		}        /// <summary>        /// Generate normals for the terrain        /// </summary>        /// <param name="ib">The Index buffer</param>        /// <param name="vb">The Vertex buffer</param>        public void GenerateNormals(Device device, IndexBuffer ib)        {            Mesh mesh = new Mesh(numPrimitives, numVertices, MeshFlags.Managed, CustomVertex.PositionNormalTextured.Format, device);            ib = mesh.IndexBuffer;            vb = mesh.VertexBuffer;            mesh.ComputeNormals();        }        /// <summary>        /// Render a single leaf node        /// </summary>        /// <param name="device">device</param>        public void Render(Device device, Vector3 playerPos)		{            if(IsLeaf)            {                device.SetStreamSource(0, vb, 0);                device.DrawIndexedPrimitives(PrimitiveType.TriangleList, 0, 0, numVertices, 0, numPrimitives);            }            else            {                topLeft.Render(device, playerPos);                topRight.Render(device, playerPos);                bottomLeft.Render(device, playerPos);                bottomRight.Render(device, playerPos);            }		}		#endregion	}}

It is in C# and it was for a terrain tutorial I wanted to do for the Managed DirectX coders.
Basically the only confusion is when you are thinking about splitting the terrain or that the members that you create are part of the terrain (little bit of depth thinking goes on here).

Just to explain what these leafnodes are. They are the smallest blocks you will divide your terrain into. I chose them to be of height and width of 32. You basically break your terrain into parts until the width and height is of 32x32.

If you have any further questions regarding quadtrees. Do not hesitate to ask.

##### Share on other sites
Armadon is there anyway that you could show a little bit of code implementing this. I am also interested in quadtree and am trying to take this code in. Thanks for posting it btw.

Zwigby

##### Share on other sites
Hi there Zwigby,
How are you doing?

[source lang = c#]//instantiating terrainTerrain terrain = new Terrain();terrain.Build(renderer.XilathDevice, "Engine/data/terrain/terrain513.raw");//rendering the terrain.terrain.Render(renderer.XilathDevice, player.PlayerPos);

This is all managed directX and C#
If you guys have any more questions please don't hesitate to ask me.

1. 1
2. 2
Rutin
20
3. 3
khawk
16
4. 4
A4L
14
5. 5

• 11
• 16
• 26
• 10
• 11
• ### Forum Statistics

• Total Topics
633755
• Total Posts
3013706
×