Page 1 of 1

XNA—Sliding Collision Using Octrees ...and the Ziggyware.Utility.dll

#1 lesPaul456  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 173
  • View blog
  • Posts: 729
  • Joined: 16-April 09

Posted 02 June 2009 - 12:29 PM

XNA--Sliding Collision Using Octrees

What is an Octree?

An octree is a type of spatial partitioning that divides a cube recursively into eight octants (one of eight equally sized cubes) until each cube contains a specified number of polygons. You can then use this “tree” to, among other things, quickly check for collision. I have found using octrees especially useful for sliding-collision response.

Ziggyware Utility Library

In order to compile the code in this tutorial, you will need to download the Ziggyware.Utility.dll from here or, copy the library from the attached file.

This library contains several functions that make coding with XNA Framework easier. I plan on making a tutorial on how to create your own octree class. For now, though, this tutorial will show how to utilize the OCTree class that is found in the Ziggyware.Utility.dll.


This tutorial will show you how to use octrees for sliding-collision and response. I will be using a FPS style camera. Once finished, you will be able to roam a small world and see sliding collision in action. I've marked this tutorial as "Intermediate" since I am assuming that you have a clear understanding of both the C# language and the XNA Framework. Thus, I will not be pausing to explain every line.


The very first class that we create is going to be a very small one. This class, CollisinSphere.cs, will hold the player's collision data.

/// <summary>
/// Creates a CollisionSphere object.
/// Used for collision detection.
/// </summary>
public class CollisionSphere
	public BoundingSphere Bounds;
	public Vector3 Velocity;

As you can see, the CollisionSphere class is very small. It's only purpose is to store the player's BoundingSphere and Velocity, which will be necessary to detect collision.


The next class that we will create is the entity class, which will hold the majority of our code. In this class, we will store the player's position, rotation, velocity, friction, and the model to be used. We will also handle the player's update logic here.

First, create a public class called Entity.cs:

/// <summary>
/// Creates a game entity.
/// </summary>
public class Entity

To this class we need to add several global variables:

// The entity's collision sphere
public CollisionSphere ColliderSphere;

// The entity's model
public Model Model;

// The entity's rotation variables
private float RotationX;
private float RotationY;

// The entity's physics variables
public float MoveSpeed;
public float Friction;
public float Gravity;
public float RotationSpeed;
public float LookSpeed;

// The entity's jump timers
public float JumpTime;
public float CurrentJumpTime;

// Is the entity on the ground?
public bool OnGround;

Next we add our constructor:

/// <summary>
/// Empty constructor that initializes the Entity members.
/// </summary>
public Entity()
	RotationX = 0;
	RotationY = 0;

	MoveSpeed = 24;
	Friction = 0.3f;
	Gravity = 7.0f;
	RotationSpeed = 2.0f;
	LookSpeed = 1.0f;

	JumpTime = 0.15f;
	CurrentJumpTime = 0;

	OnGround = false;

Here comes the meat of our class, the update method:

/// <summary>
/// Updates the entity according to player input,
/// physics, and collision.
/// </summary>
/// <param name="gameTime">Provides a snapshot of timing values.</param>
/// <param name="sceneOct">The Octree object to check collision against.</param>
public void Update(GameTime gameTime, OCTree sceneOct)

First, let's some variables to the top of the method:

// Create a InputState object to handle user input
InputState inputState = Utility.InputState;

// Create a Vector3 to store the entity's velocity
Vector3 velocity = Vector3.Zero;

// Find out if the player is trying to jump
bool jump = inputState.IsKeyPress(Keys.Space);
bool holdingJump = inputState.IsKeyDown(Keys.Space);

Next, we can add some code to rotate the entity on both the X and Y axis:

// Rotate the entity left/right
if (inputState.IsKeyDown(Keys.Left))
	RotationY += gameTime.ElapsedSeconds() * RotationSpeed;
else if (inputState.IsKeyDown(Keys.Right))
	RotationY -= gameTime.ElapsedSeconds() * RotationSpeed;

// Rotate the entity up/down
if (inputState.IsKeyDown(Keys.Up))
	RotationX += gameTime.ElapsedSeconds() * LookSpeed;
else if (inputState.IsKeyDown(Keys.Down))
	RotationX -= gameTime.ElapsedSeconds() * LookSpeed;

Now we create some rotation matrices:

// Create our rotation matrices
Matrix RotationYMatrix = Matrix.CreateRotationY(RotationY);

Vector3 right = Vector3.TransformNormal(Vector3.Right, RotationYMatrix);
Vector3 forward = Vector3.TransformNormal(Vector3.Forward, RotationYMatrix);

Matrix RotationXMatrix = Matrix.CreateFromAxisAngle(right, RotationX);

forward = Vector3.TransformNormal(forward, RotationXMatrix);

These matrices and transformed vectors that we just created will allow us to move the entity forward/backward in the direction the entity is rotating.

Now that we have how rotation matrices made, we can move the entity forward/backward:

// Move entity left/right
if (inputState.IsKeyDown(Keys.A))
	velocity -= right * (Vector3.One - Vector3.Up) * MoveSpeed;
else if (inputState.IsKeyDown(Keys.D))
	velocity += right * (Vector3.One - Vector3.Up) * MoveSpeed;

// Move entity forward/backward
if (inputState.IsKeyDown(Keys.W))
	velocity += forward * (Vector3.One - Vector3.Up) * MoveSpeed;
else if (inputState.IsKeyDown(Keys.S))
	velocity -= forward * (Vector3.One - Vector3.Up) * MoveSpeed;

Let's allow the entity to jump, and apply gravity:

// Jump!
if ((OnGround && jump && CurrentJumpTime == 0) || CurrentJumpTime > 0)
	CurrentJumpTime += gameTime.ElapsedSeconds();

	if (CurrentJumpTime >= JumpTime || holdingJump == false)
		CurrentJumpTime = 0;

	// Apply enough force to break gravity
	velocity += Vector3.Up * Gravity * 2.5f;

// Apply gravity
velocity += Vector3.Down * Gravity;

// Move CollisionSphere object with entity
ColliderSphere.Velocity += velocity * gameTime.ElapsedSeconds();

if (ColliderSphere.Velocity.Y < -Gravity)
	ColliderSphere.Velocity.Y = -Gravity;

Now we will create a list of OCTreeIntersections. After we call the MoveSphere method of the OCTree class, the list will be filled with possible intersections. We can then use that list later to determine if the entity is on the ground. This method also checks for collision between the entity's CollisionSphere and the OCTree that we will create from our "world", and acts accordingly.

// Create a list to store possible collisions
List<OCTreeIntersection> sphereColliders = new List<OCTreeIntersection>();

// Move entity, taking into acount friction and collision
sceneOct.MoveSphere(ref ColliderSphere.Bounds, ref ColliderSphere.Velocity,
	Friction, ref sphereColliders);

Since our sphereColliders list is now full of intersections, we can determine if the user is on the ground.

OnGround = false;

// Is entity on ground?
for (int i = 0; i < sphereColliders.Count; i++)
	if (Vector3.Dot(sphereColliders[i].IntersectionNormal,
		Vector3.Up) > 0.5f)
		// The player is on the ground
		OnGround = true;

Finally, we can set up our FPS style camera:

// Create our FPS camera
Camera camera = Utility.Camera;

camera.Position = this.ColliderSphere.Bounds.Center +
	Vector3.Up * this.ColliderSphere.Bounds.Radius * 0.8f;

camera.Target = camera.Position + forward;

camera.Up = Vector3.Cross(right, forward);


Now that we have our player class setup, we can start adding code to our Game class (Game1.cs by default).

First, our global variales:

// Create our player
Entity player;

// Create our scene and octree
Model scene;
OCTree sceneOct;

In order to use the Ziggyware Utility, we must set the Utility class’s Game property to our game class.
Add this in the Initialize method:

// Must call this to use the Utility library
Utility.Game = this;

Now we can load our models, and setup our scene’s octree and the player’s collision sphere:

// Load our scene 
scene = Content.Load<Model>("Models/testRad");

// Create an octree from the model
OCTreeBuilder builder = new OCTreeBuilder(600, 15, true, 0.00015f, 0.05f);
sceneOct = builder.Build(scene);

// Load player 
player = new Entity();
player.ColliderSphere = new CollisionSphere();
player.Model = Content.Load<Model>("Models/unitSphere");

// Setup collision data
player.ColliderSphere.Velocity = Vector3.Zero;
player.ColliderSphere.Bounds = player.Model.Meshes[0].BoundingSphere;
player.ColliderSphere.Bounds.Center = Vector3.Up * 55;
player.ColliderSphere.Bounds.Radius = 10.0f;

All we need to add to the Update class is a call to our player's "Update" method:

// Udpate player
player.Update(gameTime, sceneOct);

Finally, let's add our code to draw our scene in the Draw method:

// Draw the scene using the Ziggyware Utility extension "Draw"

GraphicsDevice.RenderState.DepthBufferEnable = true;
GraphicsDevice.RenderState.AlphaBlendEnable = false;

Attached File(s)

This post has been edited by lesPaul456: 02 June 2009 - 03:57 PM

Is This A Good Question/Topic? 0
  • +

Replies To: XNA—Sliding Collision Using Octrees

#2 SixOfEleven  Icon User is offline

  • using Caffeine;
  • member icon

Reputation: 942
  • View blog
  • Posts: 6,342
  • Joined: 18-October 08

Posted 02 June 2009 - 08:22 PM

Looks good, I'll keep this in mind for my 3D projects. :^:
Was This Post Helpful? 0
  • +
  • -

#3 Guest_ektor*


Posted 02 July 2010 - 01:48 PM

Does enyone now if the octree class is serializable? The problem is the long time required to build the Octree during the game loading. Saving the structure could solve this problem.
Was This Post Helpful? 0

#4 lesPaul456  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 173
  • View blog
  • Posts: 729
  • Joined: 16-April 09

Posted 05 July 2010 - 06:04 AM

No, I don't think that it is. You could check out the source code in reflector, and try to make your own implementation that provides that ability. Or if you have the source code, you could just edit that (I'm not sure if you can still get the source code, though, since the site has been down for a while).

There's also the possibility of creating a custom model class and content processor that will create the oct-tree when the model is compiled. This may be the easier route, since there is already an example on the XNA Creators Club site that shows how to do this kind of thing.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1