David's Blog

Mostly Hobby Stuff

Archive for June 2010

Sweep Tests

leave a comment »

Sweep tests are an essential part of any programmers tool box if they are interested in writing a 3D application. Sadly the amount of information about them is somewhat limited and often inaccessible, at least for the more sophisticated tests. So I plan on writing a number of blog posts describing the approach I have taken writing my library of sweep tests. These posts will work from basic principles, developing the more sophisticated tests based on simpler tests.

To start with I should probably define what a sweep test is: given a geometric shape and its position in space, check which shapes it intersects when it is swept along a path, returning the first shape that it intersects, the “time of impact”, the intersection point and the intersection normal. In these posts I will restrict my discussion to linear sweeps along a single line. In general sweep tests can also be formulated for rotational paths as well, but I will not cover these. In addition I will only cover “discrete” sweep tests, ie I will formulate each test individually rather than using a general method such as an adapted GJK approach.

There is a bunch of information available online(and in paper form) concerning intersection testing and some concerning sweep tests, below I will list a few useful resources:

The rough plan for posts I will make(very much subject to change):

  1. Sweeping a sphere against a point and another sphere
  2. Sweeping a sphere against a line/edge
  3. Sweeping a sphere against a plane
  4. Sweeping a sphere against a polygon
  5. Capsules and sweeping them against a sphere
  6. Sweeping a capsule against a point
  7. Sweeping a capsule against a line
  8. Sweeping a capsule against a polygon
  9. Sweeping a capsule against another capsule
  10. Sweeping a polyhedron against points, faces and edges
  11. Sweeping a polyhedron against another polyhedron

I should note that I derived the tests I use from first principles and then debugged/optimized them so that they were suitable for my needs. I do not make any assertions about their robustness or performance except that I have been using them for a while to handle player control and moving platforms etc in my hobby game.

An important point to mention is that a lot of the difficulty in writing sweep tests is related to establishing a framework to ensure they are easy to debug and robust. The approach I took was to add a command to my level editor which allowed me to experiment with the sweep tests with a visualization of important information. Being able to do this interactively is essential as most problems are related to long thin objects, objects of different scales, grazing contacts etc. In addition I created a number of unit tests to tackle regressions(however testing all permutations this way is prohibitively expensive).


Written by therealdblack

June 26, 2010 at 1:20 pm

Posted in Sweep Tests

Texture Tools and Normal Maps

leave a comment »

A while ago I noticed that the memory consumption for my hobby game was getting out of hand. So I did some profiling using the CLR Profiler and PIX to find out where all the memory was going. Unsurprising the biggest memory hog was the unmanaged memory for texture maps, especially because I mostly use 2048×2048 colour and normal maps for models.

Anyway, I started by enabling texture compression for the colour maps by enabling texture compression in the XNA texture processor. This helped, but it left a couple of problems, the normals maps were not compressed and the quality wasnt as good as it could be.

First to solve the normal map issue I did a little investigating and found that DXT5 with a little cleverness could be used(note: xna is D3D9 so I couldn’t use the nice new normal map formats in D3D10+). Since we only require 2 components to reconstruct a normal, we want to store one of the components in the alpha channel and the other in the green channel to maximize the use of the available precision. This format is sometimes called DXT5n(m). Storing the normal in the colour channels doesn’t produce very good results, (see Real-Time Normal Map DXT Compression).

There is a nice trick for doing the decompression that allows the same code to handle DXT1 compressed normal maps as well(useful when quality is not such a large concern). See Christer Ericsons Blog post.

My normal decompression function:

float4 UncompressNormals(float4 input)
float x = input.r * input.a;
float y = input.g;
float z = sqrt(1.0f - x*x - y*y);

return float4(x, y, z, 1.0f);

With that done, I now faced some quality issues, in particular the normal maps looked very weak when viewed from a distance. This suggests that the mip maps for the normal maps are not being generated correctly, not surprising since the same filtering code is being used for both colour and normal maps. Normal maps should be re-normalized after each level of the mip map is generated and they should also be processed without any gamma correction.

To improve the situation I switched to NVidia Texture Tools for the texture processing. This had a number of additional benefits:

  • Explicit Support for DXT5n
  • More sophisticated controls for gamma, resizing, mip-map generation etc
  • Support for normal map generation from height maps
  • support for more sophisticated mip-map filtering

However there was no XNA texture processor or functional .NET wrapper, which meant writing one:-) The maintainer of nvidia-texture-tools was nice enough to allow me to commit the changes, so you can grab the processor and .NET wrapper from http://code.google.com/p/nvidia-texture-tools/source/checkout. (the changes are not included in a release yet).

Written by therealdblack

June 26, 2010 at 12:13 pm

Posted in Graphics, Hobby Game, XNA