Archive for category Article

Creating a Planet : Geometry

I have wanted to expand on my previous post regarding ‘Cube to Sphere Projection’ for a while now, so in this article I am going to cover how I define the spherical geometry of the planets in more detail.

Read the rest of this entry »

Advertisements

22 Comments

Creating the Ships List – I

In this article I’ll be speaking about what I’ve been up to with regards to researching and defining the dimensions and specifications of the ships and engines. I aim to have engines and ship sizes which are both believable in size and capabilities, while not necessarily being so accurate as to be confusing for the player. I’m writing this simultaneously with the ships list.

Read the rest of this entry »

4 Comments

Blender3D and XNA

For the last three weeks I have started modeling the first in-game content for Horizons, the ‘Locust MK I’, using Blender3D and paint.NET. This time round, I’ll go over how I am exporting model and opaque data from blender, texturing the model with UV maps and paint.NET and importing them into XNA.

Read the rest of this entry »

4 Comments

Depth (Z-) Buffers

As with all games, Z-buffering plays an important part when rendering the pixels to the screen. During the development of Britonia I have often run into a problems related to the Z-Buffer, so I thought it would be nice to share what I have learned about them and how to avoid these issues.

Read the rest of this entry »

1 Comment

Scale and 32-Bit Imprecision

Over the last few months, I have made quite a few posts and answered a few questions about the issue of imprecision, and more importantly how I overcame it. So I have decided to write an article, so I can always link back to it.

There are a few ways of overcoming this problem, but just to be sure what we’re talking about, let me explain how this imprecision occurs. The normal way to store coordinates and positions in XNA (and DirectX for that matter) is to use 32-bit floating point numbers, for example when you use the Vector2 and Vector3 structs. This is the best way to work, especially considering that most of today’s GPUs do not support 64-bit floating point values (doubles) and it is more than enough to render normal scenes. 32-bit floating point numbers are able to store numbers with up to 15 digits, but the problem is however, that they can only do precise arithmetic on the first 5 or 6 digits. Consider the following:

0.000001 + 0.000001 does not always equal 0.000002
1000001 – 1 does not always equal 1000000

Obviously, if you are trying to navigate the camera very far away from (0,0,0) then you will start to encounter problems. This becomes a real problem say, if you are making a space shooter with realistic distances between planets, or a medieval trading game with a planet the size of EarthSmile. In the latter case, when you get down to the meter level of the planet, the vertices start to shake.

The symptoms to look for if you suspect floating point imprecision are randomly ‘shaking’ vertices and problems with navigating the camera. This is obviously a byproduct of these miscalculated values as shown above.

After doing some searching on the internet, it is quite apparent that the two main ways of overcoming this is to either,

a) Represent all object positions using fp64 values (doubles).
b) Use fixed point numbers.

After looking around, I decided to use the first option, and so this is what I will outline below. Basically, the biggest problem with (a) is that the GPU does not support fp64 values, so before rendering we must first convert everything back to fp32 values. A lot of people actually suggested that fixed point numbers (b) are the way forward, but the implementation seemed a lot harder than using doubles, and two of the biggest arguments were that 1) most older computers and resource limited devices do not have dedicated FPUs for floating point calculations, and 2) that using doubles doesn’t actually solve the problem, but the first point isn’t really a problem for today’s gaming machines and although using doubles doesn’t fix the problem, it is certainly good enough to use, as I will explain below.

Using fp64 doubles for positions:

So this was my chosen method for Britonia. But what does switching to fp64 doubles actually do for us? Well, it allows us to do calculations on values with up to 15 digits. This is enough precision to represent the space between the Sun and Pluto with a resolution down to the centremeter level, which should solve the majority of our arithmetic problems (if you are creating a universe, you would have to create different ‘spaces’ were 1 unit has different values. For example, at the Galaxy level 1 unit may be 1LY, and at the solar system level 1 unit may be 1 meter etc.)

Okay, now using 64-bits solves the arithmetic problem, but there is still the problem that the GPU doesn’t support fp64. This means we have to convert the 64-bit values into 32-bit values before sending anything off to the GPU, but if we are sending massive fp32 values to the GPU, it is also going to run into imprecision problems when transforming the vertices to clip/screen space etc.

The idea here is pretty simple. The problem of imprecision occurs when numbers get either too large or too small as we saw above. Imagine we have a ship at 15000010 and the camera is at 15000040 looking down at the ship (In 1D space). We store the positions in fp64 doubles, which enables us to calculate and apply velocity or pan the camera around the ship or whatever, all with 64-bit precision. But we still need to convert the positions into useable fp32 values. To do this, instead of treating 0 (or (0, 0, 0) in 3D space) as the origin of the universe, we use the camera’s current position as the origin. Then we calculate the positions of all the objects relative to the camera (as this is now the origin). So, for the ship we would do:

15000010 – 15000040 // ship pos minus cam position

= -30.

This means that if we set the camera position to 0 the relative ship position will be -30. As you can see, this effectively solves the imprecision from large numbers.

So, from our example above, we would calculate the 3d positional data of a scene as follows:

fp64Vector3 loCameraPosition = new fp64Vector3 (0, 1500013002, 200);
fp64Vector3 loObjectPosition = new fp64Vector3 (0, 1500011002, 0);

// Get the object position relative to the camera positon.
Fp64Vector3 loRelativeObjectPosition =  loObjectPosition - loCameraPosition;

// Convert this value into a fp32 value
Vector3 lo32bitPosition = new Vector3(
      (float) loRelativeObjectPosition.X,
      (float) loRelativeObjectPosition.Y,
      (float) loRelativeObjectPosition.Z);

// Use the 32bit position data to create a world matrix for the object which can be sent to the GPU for rendering.  Note that the rotations can be calculated like normal with 32-bit floats, as rotations here are local to the object.
Matrix loWorld = Matrix.CreateRotations(0) * Matrix.CreateTranslation(lo32bitPosition);

And from here you can render the object as you would any other object in XNA. Just pass the new world matrix for this object to the shader, set the camera position to Vector3.Zero, create a new View Matrix and render the model.

// Create a new view matrix and treat the camera as the centre as the centre of the world.
Matrix loViewMatrix = Matrix.CreateLookAt(Vector3.Zero, Camera.Forward, Camera.Up);

Effect.Parameters[“xWorld”].SetValue(loWorld); // this is the world position relative to the camera
Effect.Parameters[“xView”].SetValue(loViewMatrix); // this is our new view matrix with cam pos set to Zero.
Effect.Parameters[“xProjection”].SetValue(Camera.Projection); // this is just a normal projection matrix

// Render the model with the new view matrix with the camera position set as Vector3.Zero.
Model.Render();

Wraping Up.

As mentioned above, I would just like to point out that this method doesn’t actually fix anything, as imprecision does still occur in objects which are very far away from the camera, but by using fp64 doubles, this means that any problems will occur so far away that you wouldn’t notice a difference anyway. Just think about sitting on the sun watching two ants playing chase on Pluto.

2 Comments

Cube to Sphere Terrain Projection

Because a few people who read the blog/website have asked about how to convert a cube into a sphere when creating planets, I have decided to write this entry.

Let me just outline the goal of this post:

We want to create a planet mesh, which we can render with LOD, Culling and it should be straight forward to place objects on the ground (trees, buildings etc. etc.)

Usually when rendering terrains, I find people tend towards using Quadtree Spatial Partitioning.  This is a very good method, but it is limited in that the terrain (or plane) it partitioned along 2 axis’ only, e.g the X and Z axis (Quadtrees are explained in the post here).  The difference for us is that we will then need to define 6 quadtrees, one for each side of a cube, which means orientating each plane differently (depending on which side of the cube they are, their local X and Z axis’ will be pointing in different directions in world space). By using several Quadtrees, we will have gained the ability to use LOD when rendering, and we can also then cull all the nodes which are not visible by the camera.  We can also insert objects easily into quadtrees, and by providing the proper quadtree index (in the [0,5] range), we can specify on which side of the planet the objects are.

But just using quadtrees doesn’t actually solve the problem completly, as we still need to convert the cube to a sphere – but this part is quite easy, as you are about to see.

Part I – Defining the six quadtree sides, and creating the cube.

// Creates the planet faces.
public void BuildPlanet()
{
// Calculate the max LOD based on the radius of the planet.  For a planet the size of earth,
// the liLODMax is calculated to 46.
int liLODMax = (int)Math.Log((float)((2.0f * Math.PI * m_fRadius) / 4.0f), 2);// Now calucate the size of each cube (planet face).  We will use this variable when defining the world space

// coordinates of the vertices.
int liCubeSize = m_iLODMax * 2;
int liHalfCube = m_ liCubeSize / 2;

// Create and build quadtree face #0
//                                 cWorldNode(int index, int maxLOD, cWorld parent)
m_Faces[0] = new cWorldNode(0, liLODMax, this);// Now call the function which will create the actual mesh data for this quadtree/planet face.

//        Game game - the current instance of the game class
//        Vector3 orientation - This vector defines which side of the planet cube this quadtree should represent.
//            Two of the components should be 0, and the other component should be liHalfCube;
//              Vector3 localX - The 'direction' of the local X axis in world space.
//              Vector3 localZ - The 'direction' of the local Z axis in world space.
m_Faces[0].BuildParentNode(Game, new Vector3(0, 0, liHalfCube), new Vector3(m_ liCubeSize, 0, 0), new Vector3(0, m_ liCubeSize, 0));

// Create the other 5 planet faces /* code removed for space */

}

So, you should be able to see from the above code, that we have just created the first Quadtree plane for the positive Z-Axis of the cube.  This will of course need to be done another 5 times for the other sides, but this should be no problem.

The next part (part II) takes place within the BuildParentNode() function, and it is here that we actually create the mesh, assign texture coordinates, weights etc. (and where we will transform the cube to a sphere).

Part II – Terrain Node Creatation

/// <summary
/// Builds the parent node information for this quadtree face.  The actual terrain mesh is generated in this function.
/// Note that for child nodes, there is a separate function, BuildChildNode().
/// </summary>
/// game is the current instance of the XNA game class.
/// centre is the centre of the planet face (on one of the cube edges).
/// dx is the direction of the X-Axis in local 'terrain space'.
/// dy is the direction of the Y-Axis in local 'terrain space'.
Public void BuildParentNode(Game game, Vector3 centre, Vector3 dx, Vector3 dy)
{

/*  code removed for vertex buffer generation*/

// Define the grid size.  i.e. the number of vertices in a grid (16x16)
int liGridSize = 16;
int liGridSizePlus = 17; // liGridSize + 1

// loop through and create a grid of vertices.
for (int u = 0; u <= liGridSize; u++)
{
for (int v = 0; v <= liGridSize; v++)
{
// Create the vertex grid around the centre of thecube face (which is passed into the function as Vector3 centre).
Vector3 tempPosition = centre + (dx / liGridSize) * (v - liGridSize / 2) + (dy / liGridSize) * (u - liGridSize / 2);

// This is where we would define the height of the vertex.
lfHeight = 0;

// Project the vertex onto the sphere, taking into consideration the height of the
// vertex and the radius of the planet.  By specifying 0 as the height, we will
// get a 'perfectly' round planet/sphere.
m_vVertexPositions[liGridSizePlus * u + v] = SurfaceVectorToCoordinates(tempPosition, m_Parent.Radius, lfHeight);

/* code removed for space */
/* Assign texture coordinates and weights etc*/
}
}

/* code removed for space */
/* build the vertex buffer and create a bounding box for this terrain node */
}

/// <summary>
/// Transforms a vector from the surface of a cube, onto the surface of a sphere.
/// </summary>
/// surfacePos is the vertex position on the cube.
/// radius is the radius of the planet.
/// height is the height of the terrain at this position.
public static Vector3 SurfaceVectorToCoordinates(Vector3 surfacePos, float radius, float height)
{

// Create a return veriable.
Vector3 loReturnData = surfacePos;

// Get a unit vector ( this will 'point' in the correct direction, from (0,0,0) to
// the position of the vertex on the sphere ).
loReturnData.Normalize();

// Add the planet radius and the height of the vertex, and return the vector.
return loReturnData *(radius + height);
}
A lot of code has been removed from the above function, but it should now at least be clear how I have created the planets in Britonia.

Have fun!

// Creates the planet faces.
public void BuildPlanet()
{
// Calculate the max LOD based on the radius of the planet.  For a planet the size of earth,
// the liLODMax is calculated to 46.
int liLODMax = (int)Math.Log((float)((2.0f * Math.PI * m_fRadius) / 4.0f), 2);// Now calucate the size of each cube (planet face).  We will use this variable when defining the world space

// coordinates of the vertices.
int liCubeSize = m_iLODMax * 2;
int liHalfCube = m_ liCubeSize / 2;
// Create and build quadtree face #0
//                            cWorldNode(int index, int maxLOD, cWorld parent)
m_Faces[0] = new cWorldNode(0, liLODMax, this);// Now call the function which will create the actual mesh data for this quadtree/planet face.

//        Game game – the current instance of the game class
//        Vector3 orientation – This vector defines which side of the planet cube this quadtree should represent.
//            Two of the components should be 0, and the other component should be liHalfCube;
//        Vector3 localX – The ‘direction’ of the local X axis in world space.
//        Vector3 localZ – The ‘direction’ of the local Z axis in world space.
m_Faces[0].BuildParentNode(Game, new Vector3(0, 0, liHalfCube), new Vector3(m_ liCubeSize, 0, 0), new Vector3(0, m_ liCubeSize, 0));
// Create the other 5 planet faces /* code removed for space */
}

8 Comments