Jump to content
  • Advertisement
Sign in to follow this  
dxdotnet1

Quadtree terrain engine need help

This topic is 4767 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

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
Share on other sites
Hi there Zwigby,
How are you doing?


[source lang = c#]
//instantiating terrain
Terrain 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.

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!