3.4. Terrain Concepts
In this tutorial you will learn how to clip the parts of a terrain that the user doesn't see to save vertex processing, to draw the objects of a scene in a front to back order to save pixel processing (fill rate), to apply fog to a scene and to carry out tasks in the background, printing their progress; this is useful because we are going to load a 1024 x 1024 map (very big map) and processing it takes a while.

3.4.1. Prerequisites
Before you start this tutorial make sure that you have:
• Installed XNA Game Studio 3.1
• Successfully run the starter project
• For a better understanding, is preferred to have finished the previous tutorials.

3.4.2. Game Assets
Game assets [2.3.2] for this tutorial:

3.4.3. Terrain Culling

The field of view (fov) is the portion of the world that we can see with our eyes; for example point your right arm forward and your left arm to the left like the guy in the figure; then look to the front with your right eye only, you should see part of your right arm but not the left arm, this is because the field of view of your right eye is not wide enough.

The fov can be measured by a vertical and a horizontal angle, in the figure that angle is t.

Another important concept is that in planet earth, objects too far away tend to disappear in fog; this is true for even the sunniest of days.

In a 3D scene, the fov is represented by a series of planes that make a volume; that volume is called the frustum. What the graphics card does is: for each triangle in the scene, if the triangle or part of it is inside the frustum; it is displayed, if not, it is culled. The frustum also has a near and far clipping planes that are not really part of the fov concept.

Not only the graphics card cull the triangles outside the frustum, also, it is much faster than the CPU at doing it, so, why are we doing this tutorial?

When it comes to culling, the graphics card is very fast but not very smart. In the figure, each square can potentially have many triangles, if we pass all the squares to the graphics card, it will make the culling in a triangle basis, even if the whole square is out of the frustum. What we can do is choose the squares that are inside or have a part inside the frustum and pass only those squares to the graphics card.

Notice that if we do so, the squares that are partially inside the frustum will have some triangles that are still outside the frustum; that's ok since the graphics card will handle those.

The main idea is to cull LARGE parts of the scene in the CPU and let the graphics card deal with the details.

Notice that if each square has only two triangles, the CPU will be making the culling almost in a triangle basis, and this will be extremely slow. Notice also that if you make the squares with too many triangles, then the squares that are partially outside the frustum will represent a lot of work to the graphics card.

In the figure you can see the end result of the culling process; the red lines represent the frustum/fov. At first, it looks like the user will see white chunks but since the user won't see anything outside the frustum, he/she won't even notice that we are making culling, what he/she will see is something like the image in [3.4.1].

3.4.4. Drawing in a front to back order

A graphics card performs both vertex and pixel processing. Culling a terrain saves vertex processing, since a lot of vertices are cut out of the scene. Now, if your problem is pixel processing (you have really complex pixel shaders for example) then you should consider drawing your objects in a front to back order. In the figure; if the draw order is 2, 1, then 2 is drawn and for each pixel the corresponding pixel shaders are executed, after that, when 1 is drew, the work done on some pixels of 2 will be lost when they are replaced to draw 1.

If on the other hand, the draw order is 1, 2, then 1 is drew and pixel processed but because 2 is behind 1, none of the pixels of 1 will be replaced and only some of the pixels of 2 will be processed (the visible ones).

3.4.5. Monitoring a task in the background
Creating a terrain is a long and complex task; in a production application it's not practical to process the terrain every time the application runs; instead the terrain is created, saved and just loaded in runtime. In our tutorial however, the terrain is processed every time, and that task can take a while. Since we don't like to see a white screen, ignoring if the process failed at some point or when is it going to end; we are going to create and monitor the task in the background (in another thread).

In the example above, assuming that all tasks are equally long, we state the progress of the task with the following:

Notice that the sum of the progress inside a task is 100.

You can have tasks inside tasks, in the example above we create the "Creating Building Mesh" task with an importance of 1, the sum of all tasks that are directly inside another task must sum 1, for example if task step 1 was composed of two more tasks, the code could be:

Notice the changes:

First, we have two tasks inside "Creating Building Mesh" which are "Step 1" with an importance of 0.25 and "Other steps" with an importance of 0.75, 0.25 + 0.75 = 1.0.

Second, because the call to addCurrentProgress only affects the task from which it's being called, the method is adding 50 when it's inside "Step 1" because there are only 2 steps and 20 instead of 25 when it's inside "Other steps" because it has 4 steps.

Third, when we finish a task we must remove it, notice that the  removeCurrentTask method doesn't receive any parameter; that's because there's only one task at a time being performed (actually one per thread).

Now that you know how to create tasks, you must know how to get the progress of the current task and of all the tasks:

To obtain the progress of the current task, we call:

found is a boolean that states if the Thread exists and if BetaCell is aware of it.
progress is a float value that states the progress of the task.

In a similar way, the following call gets the progress of the sum of all the tasks that belong to a Thread:

3.4.6. The using statements
Besides the using statements from the starter project, this tutorial needs the following using statements:

using BetaCell.Environment.Terrain;
using BetaCell.Environment.Mesh;
using BetaCell.Util.Drawing;
using BetaCell.Environment.Mesh.Visitors;
using BetaCell.Environment;
using BetaCell.Effects.Composer;
using BetaCell.Environment.Light;
using BetaCell.Environment.Texture.Feeder;
using BetaCell.Environment.Texture;
using BetaCell.Effects;
using BetaCell.Environment.Mesh.Content;
using BetaCell.Common.Bounding;
using BetaCell.Common.Vertex;

3.4.7. Game Attributes
The attributes that come with the starter project are explained in tutorial section 1.1.4.

For this tutorial we are going to be needing the following attributes:

BCTerrain floor;
BCMesh buildingMesh;

BCDepthSorterDrawer drawer;
Plane[] clipPlanes
;

BCFog fog;

3.4.8. The Initialize method
The frustum culling is multithreaded in BetaCell so the BCThreadPool must be initialized:

In this example, 4 threads are set. This parameter is only valid on the PC, on the XBOX is allways 4.

Since we started the thread pool we need to stop it at the end of the execution, this is done by overriding the OnExiting method:

protected override void OnExiting(object sender, EventArgs args)
{
base.OnExiting(sender, args);
}

To draw the scene in a front to back order [3.4.4], we will delegate the drawing to a class that knows how to do that instead of performing the ordering the ourselves; the Initialize method starts by creating an instance of this class:

drawer = new BCDepthSorterDrawer(device, 4, 2000);

The depth sorted drawer receives three parameters; first the device, second the log2(n) (2^n, in this example 2^4 = 16) of the number of sublist to order the scene (see the documentation for more information) and finally the maximum depth of an object to be drawn.

Now we must load the scene. If a user starts an application and a window doesn't appear immediately, he/she will think that the application didn't start at all, also if the application starts but doesn't keep feeding the user with data, he/she will think that the application hanged.

The user will be confident (doesn't mean that he/she is happy with an application that takes forever to load) with the application as long as it refreshes the data that the user sees constantly.

In the left, we have a single threaded application (only the main thread), it prints that the application started and starts to load the scene, since in XNA we can't print data and load the scene at the same time, during the portion of time devoted to loading the scene, the application will appear as it has hanged, and if the process takes long, then the user will probably end the task.

In the right we have two threads, the main one keeps printing data (showing the progress of the load procedure) and the second one loads the data. Notice the uninterrupted line of the print data task.

To achieve the scenario shown in the right side of the figure; we must create a thread, pass it the method that loads the scene and start it.

Inside it we have the tasks that load the scene. The first one is "Creating Common Data";  the new to this part is the creation of the ambient light and the fog effect parts:

BCAmbientLight ambient = new BCAmbientLight();
ambient.amb = Color.Gray;
BCDynamicEffectVisitor ambientSetter =
new BCDynamicEffectVisitor(ambientPart, ambient, 1);

This creates the ambient light, which is the light that has bounced in the scene so much that for practical purposes is applied to all the pixels in the scene, regardless of the normal of the surfaces.

fog = new BCFog();
fog.fogColor = Color.White;
fog.fogStart = 0.9f;
fog.fogRange = 0.1f;
BCFunction fogPart = fog.getFunction("Environment.Fog");

BCDynamicEffectVisitor fogSetter = new BCDynamicEffectVisitor(
fog.getFunction(BCFog.FOG), fog, BCDynamicEffect.MAX_FUNCTIONS
);

This creates the fog effect feeder, sets the fog color, the distance at which the fog starts and the distance at which the fog ends (fog range) relative to the camera's far clip plane. Also, a visitor for the fog effect is created.

The next two tasks are "Creating Building Mesh" and "Creating Terrain",  there's nothing new in them.

The following task is "Preparing terrain for culling", here; we divide the terrain in square parts. When the terrain was built, a 1024 X 1024 map was passed as a parameter; meaning that there are 1024 rows and 1024 columns right? wrong. Lets downscale the problem to a map of 16 X 16.

If we load a 16 X 16 map, it means that there will be 16 vertices in each of the axises of the terrain as shown in the figure. The problem is that vertices is different than rows/columns; if we have 16 vertices we have 15 rows/columns (count the vertices and the rows/columns).
So intuitively say that we are going to load a 16 X 16 map and divide it in 4 squares of 8 vertices X 8 vertices is wrong; in the figure the blue and green squares have 8 vertices per axis each, and you can see that we have a full column left with the 8 X 8 division.

The solution is to divide based in the number of rows/columns, if we have 16 vertices, we have 15 rows/columns, so we can divide the terrain in divisors of 15 (15, 5, 3, 1) in the figure, the red squares are divisions of 5 rows/columns (6 vertices).

The tutorial divides the terrain with the following call:

floor.prepareForCulling(device, 94, 94);

Assuming that the resulting plane is in the XZ axis, it receives the device, the number of VERTICES not columns in the x axis and the number of VERTICES not rows in the z axis. In the example of the figure the divisions in red/white would be prepareForCulling(device, 6, 6);.

The 94 X 94 division was done because we have a 1024 X 1024 map; that means that we have 1023 rows/columns. The 94 X 94 division means that each division will have 93 rows/columns. So 1023 should be divisible by 93, and 1023 / 93 = 11 so it is.

The values by which the 1024 map could be divided are 1024, 342, 94, 34, 32, 12 and 4.

The next task is "Finishing the terrain", in it, we set the textures and the effect of the terrain. We have done this before but here, we do it in a different way to save processing and memory, since the terrain has a lot of mesh parts.

The first difference is the way the textures are applied to the terrain. Since the terrain mesh has many mesh parts, it would be better to have the same textures shared by all parts than to have the textures repeated in each part; so what we do is use a BCPooledTextureStrategy instead of the  BCMemoryTextureStrategy.

To do this, we delegate the load of the textures to the texture pool of the mesh by issuing the following call for each of the 4 textures needed:

int referenceIndex =
"Content/gameAssets/channelsR", content);

The call returns an integer number that represents the texture inside the mesh. After that we create the texture visitors but with a pooled texture strategy instead of a memory texture strategy:

BCPooledTextureStrategy referenceStrategy =
new BCPooledTextureStrategy(referenceIndex, floor.terrainMesh.textures);

The pooled texture strategy takes the number that represents the texture and the texture pool that holds the texture (in this case the texture pool of the terrain mesh).

BCTextureVisitor blendMapTex =
new BCTextureVisitor("gBlendMap", referenceStrategy);

The visitor isn't new, it takes the name of the texture and the strategy.

We repeat the process for the other textures.

The second difference is the way in which the effect is dealt with. Until now, we just visited the mesh to set the effect; this technique is very useful if we have meshes with only a few mesh parts with different effects each but here we have a lot of parts, all of which have the same effect, so instead of creating an effect dynamically for each part, we create a common effect and set that effect in all the parts.

To do that, we create a dynamic effect with the functions that we have created in previous tasks; note that these functions are the ones used to create the visitors:

BCDynamicEffect commonEffect = new BCDynamicEffect(device, new BCFunction[] {
baseColor, ambientPart, lightPart, channelBlendPart, fogPart
});

Then we set the feeders for the effect:

And we create a visitor that instead of plugging an effect function into each part of the mesh, sets the entire effect of all the parts of the mesh, so all the parts end up using the very same effect.

BCEffectSetterVisitor commonEffectSetter =
new BCEffectSetterVisitor(commonEffect);

The last operation of the initialize method is to attach the finished terrain to the camera and notify that the loading process has been completed:

camera.attachWalkable(floor, 2);

We don't attach the terrain to the camera in the onActivated method because at the time the method is called, the terrain has not been finished; making it too early.

3.4.9. The Update method

First we set the camera for the fog effect; this way, the fog calculates it's depth depending on the far clip plane.

if (fog != null && fog.camera == null)
{
fog.camera = camera;
}

Then inside the updateCamera method, we update the camera and retrieve view matrix and the set of planes that define the frustum [3.4.3] with the following call:

camera.getViewAndFrustum(out view, out clipPlanes);

This gets both the view matrix and the clip planes that make the frustum.

3.4.10. The Draw method
The draw method has 2 states, the first one is when the terrain hasn't been completed, in this case the ready variable is still false and the progress of the loading process is logged to the screen:

BCLogger.instance.debug.printlnd(

bool found;
float progress;
float overallProgress;

BCLogger.instance.debug.printlnd("completeness: " + progress);

Here we get the progress of the current task of thread loader and print it using the log.

BCLogger.instance.debug.printlnd("Overall completeness: " + overallProgress);

In a similar way, Here we get the general progress of all the tasks being performed by thread loader and print it using the log.

The second state is when the terrain is completely loaded, the ready variable is set to true and the terrain is drawn in a front to back order [3.4.4]:

drawer.reset();

Here we reset the drawer to calculate again the distances from the camera to the objects; remember that when the camera changes it's position, the distance of it to the objects in the scene also changes.

floor.terrainMesh.recieveDrawer(drawer, clipPlanes);

Here the terrain's mesh receive the drawer, the other parameter is the set of planes that make the frustum. When a mesh allows a drawer to visit it, the drawer stores the mesh parts that are visible in it. In this context; visible means the parts that are wholly or partially inside the frustum.

drawer.Draw(
gameTime,
Matrix.Identity,
floor.terrainMesh.getPart(0).effect,
floor.terrainMesh.getPart(0)
);

Finally, the drawer draws the visible parts of the meshes that it visited, all the parts of the terrain share the same effect, so, for performance reasons, the effect is passed to the drawer. The last parameter is the part responsible to provide the mesh specific information for the effect like textures.

3.4.11. Conclusion
The concepts studied in this tutorial were explained so that you can apply them using BetaCell, the depth of the subjects treated here can span to many books. If you want more information, you can refer to "Introduction to 3D game programming with Direct X 9.0c, a shader approach" by Frank D Luna.

3.4.12. Complete source code
using System;
using System.Collections.Generic;

using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.GamerServices;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework.Net;
using Microsoft.Xna.Framework.Storage;

using BetaCell.Debug;
using BetaCell.Util.GlobalInfo.Content;
using BetaCell.Environment.Camera;
using BetaCell.Util.GlobalInfo;

using BetaCell.Environment.Terrain;
using BetaCell.Environment.Mesh;
using BetaCell.Util.Drawing;
using BetaCell.Environment.Mesh.Visitors;
using BetaCell.Environment;
using BetaCell.Effects.Composer;
using BetaCell.Environment.Light;
using BetaCell.Environment.Texture.Feeder;
using BetaCell.Environment.Texture;
using BetaCell.Effects;
using BetaCell.Environment.Mesh.Content;
using BetaCell.Common.Bounding;
using BetaCell.Common.Vertex;
using BetaCell.Common.Bounding.Cube;

namespace Starter
{
public class Game1 : Microsoft.Xna.Framework.Game
{
//Game attributes
GraphicsDeviceManager graphics;
GraphicsDevice device;
ContentManager content;

BCFirstPersonHumanCamera camera;
//end game attributes
BCFog fog;

BCTerrain floor;
BCMesh buildingMesh;

BCDepthSorterDrawer drawer;
Plane[] clipPlanes;

public Game1()
{
graphics = new GraphicsDeviceManager(this);
graphics.PreferredDepthStencilFormat = DepthFormat.Depth24Stencil8;
content = new ContentManager(Services);

#if(XBOX360)
graphics.PreferredBackBufferWidth = 1280;
graphics.PreferredBackBufferHeight = 768;
#else
graphics.PreferredBackBufferWidth = 852;
graphics.PreferredBackBufferHeight = 480;
#endif
}

protected override void Initialize()
{
device = graphics.GraphicsDevice;
BCLogger.instance.init(device, content);
BCInitializationManager.initialize(content);

OnActivated(null, null);

drawer = new BCDepthSorterDrawer(device, 4, 2000);

base.Initialize();
}

protected override void OnExiting(object sender, EventArgs args)
{
base.OnExiting(sender, args);
}

{

BCMaterialBase material = new BCMaterialBase();
material.specRange = 0.8f;
material.diff = Color.Gray;
material.spec = Color.White;
material.amb = Color.DarkGray;
BCMaterialVisitor materialVisitor = new BCMaterialVisitor(material);

//Color set effect composition part
BCColorSet colorSet = new BCColorSet(Color.Black);
BCDynamicEffectVisitor colorSetter = new BCDynamicEffectVisitor(baseColor, colorSet, 0);

//Light effect composition part
BCAmbientLight ambient = new BCAmbientLight();
ambient.amb = Color.Gray;
BCDynamicEffectVisitor ambientSetter = new BCDynamicEffectVisitor(ambientPart, ambient, 1);

BCBasicLight light = new BCBasicLight();
light.transform = Matrix.CreateTranslation(-1, -1, -1);
light.range = 3000;
light.cubAtten = 0;
light.constAtten = 1;
light.linAtten = 0;

BCDynamicEffectVisitor lightSetter = new BCDynamicEffectVisitor(lightPart, light, 1);

fog = new BCFog();
fog.fogColor = Color.White;
fog.fogStart = 0.9f;
fog.fogRange = 0.1f;
BCFunction fogPart = fog.getFunction("Environment.Fog");

BCDynamicEffectVisitor fogSetter = new BCDynamicEffectVisitor(
fogPart, fog, BCDynamicEffect.MAX_FUNCTIONS
);

//Creating a sampler for the texture
BCSampler sampler = new BCSampler(
"LINEAR", "LINEAR", "LINEAR", "4",
"WRAP", "WRAP", "0xffffffff"
);

"Content/gameAssets/tower", null, device, content);
buildingMesh.transform = Matrix.CreateTranslation(-250, 0, 179);

buildingMesh.visit(ambientSetter);
buildingMesh.visit(lightSetter);
buildingMesh.visit(materialVisitor);
buildingMesh.visit(fogSetter);

floor = new BCTerrain(device,
"Content/gameAssets/FinalBeta", 10f, 10f, 1024, 1024,
5f, -65, 1, 1, null, new BCVertexPosNorTexContainer(), content);

floor.prepareForCulling(device, 64, 64);

//Creating a texture feeder for the texture
//Adding a sampler per expected texture of the channel blend effect part
BCTextureFeeder texFeeder = new BCTextureFeeder();

//Getting the texture effect part function from the texture feeder

//Setting texture
int referenceIndex =
int grassIndex = floor.terrainMesh.textures.addTexture("Content/gameAssets/", "grass", content);
int stoneIndex = floor.terrainMesh.textures.addTexture("Content/gameAssets/", "stone", content);

BCPooledTextureStrategy referenceStrategy =
new BCPooledTextureStrategy(referenceIndex, floor.terrainMesh.textures);
BCTextureVisitor blendMapTex = new BCTextureVisitor("gBlendMap", referenceStrategy);

//Alternate way to initiate the texture in a single definition
BCTextureVisitor grassTex = new BCTextureVisitor(
"gTex0",
new BCPooledTextureStrategy(grassIndex, floor.terrainMesh.textures)
);
grassTex.strategy.setScale(new Vector2(1024, 1024));

BCTextureVisitor stoneTex = new BCTextureVisitor(
"gTex1",
new BCPooledTextureStrategy(stoneIndex, floor.terrainMesh.textures)
);
stoneTex.strategy.setScale(new Vector2(1024, 1024));

"gTex2",
);

floor.terrainMesh.visit(blendMapTex);
floor.terrainMesh.visit(grassTex);
floor.terrainMesh.visit(stoneTex);

floor.terrainMesh.visit(materialVisitor);

BCDynamicEffect commonEffect = new BCDynamicEffect(device, new BCFunction[] {
baseColor, ambientPart, lightPart, channelBlendPart, fogPart
});
BCEffectSetterVisitor commonEffectSetter = new BCEffectSetterVisitor(commonEffect);

floor.terrainMesh.visit(commonEffectSetter);
camera.attachWalkable(floor, 2);

base.Initialize();
}

protected override void OnActivated(object sender, EventArgs args)
{
buildViewMatrix();
base.OnActivated(sender, args);
}

void buildViewMatrix()
{
Vector3 pos = new Vector3(-250, 100, 179);
Vector3 look = new Vector3(0, 0, 1);
look.Normalize();

camera = new BCFirstPersonHumanCamera(
look, pos,
MathHelper.PiOver4, (float)this.Window.ClientBounds.Width /
(float)this.Window.ClientBounds.Height, 1f, 2000
);

if (fog != null)
{
fog.camera = camera;
}

BCGlobalInfo.instance.setMatrix(
BCGlobalInfo.VIEW_INDEX,
camera.getViewMatrix(-1)
);

BCGlobalInfo.instance.setMatrix(
BCGlobalInfo.PROJECTION_INDEX,
camera.getProjectionMatrix(-1)
);
}

protected override void Update(GameTime gameTime)
{
if (fog != null && fog.camera == null)
{
fog.camera = camera;
}
moveCamera(gameTime);
}

private void moveCamera(GameTime gameTime)
{
float df = 0;
float ds = 0;
float dy = 0;
float pitch = 0;
float angleY = 0;

float speed = 5f;
#if (XBOX360)

{
dy += 0.25f;
}
{
dy -= 0.25f;
}

speed = new Vector3(df, ds, dy).Length() * 50;
#else

KeyboardState keys = Keyboard.GetState();
MouseState mouse = Mouse.GetState();

if (keys.IsKeyDown(Keys.W))
{
df += 1;
}
if (keys.IsKeyDown(Keys.S))
{
df -= 1;
}
if (keys.IsKeyDown(Keys.D))
{
ds += 1;
}
if (keys.IsKeyDown(Keys.A))
{
ds -= 1;
}
if (keys.IsKeyDown(Keys.Q))
{
dy += 1;
}
if (keys.IsKeyDown(Keys.E))
{
dy -= 1;
}
speed = 15f;
if (keys.IsKeyDown(Keys.LeftControl))
{
speed = 30f;
}

angleY = ((float)this.Window.ClientBounds.Width / 2.0f - (float)mouse.X) * -0.05f;
pitch = ((float)this.Window.ClientBounds.Height / 2.0f - (float)mouse.Y) * -0.05f;

Mouse.SetPosition(this.Window.ClientBounds.Width / 2, this.Window.ClientBounds.Height / 2);

#endif
camera.update(df, dy, ds, pitch, angleY, speed, (float)gameTime.ElapsedGameTime.TotalSeconds);
Matrix view;
camera.getViewAndFrustum(out view, out clipPlanes, -1);

BCGlobalInfo.instance.setMatrix(BCGlobalInfo.VIEW_INDEX, view);
}

protected override void Draw(GameTime gameTime)
{
graphics.GraphicsDevice.Clear(ClearOptions.Target | ClearOptions.DepthBuffer, Color.White, 1.0f, 0);

{
drawer.reset();

floor.terrainMesh.recieveDrawer(drawer, clipPlanes);
drawer.Draw(
gameTime, Matrix.Identity, floor.terrainMesh.getPart(0).effect,
floor.terrainMesh.getPart(0)
);

if (!buildingMesh.bounding.outside(clipPlanes))
{
buildingMesh.Draw(gameTime);
}
}
else
{
bool found;
float progress;
float overallProgress;

BCLogger.instance.debug.printlnd("completeness: " + progress);