# Lloyd.NET

## Programing experiments # Hit Testing This time for my DirectX self training I implemented hit testing, frustum culling and octtrees.

On the figure above the red triangle is the triangle that the user hit with the mouse. All the code is in CodePlex, at http://directwinrt.codeplex.com/ and the screenshot is from Sample2_D2D.

### Basics

As I described in my previous blog entry, calling into C++ is costly, even with WinRT C++/CX. By that I mean crossing the ABI divide between .NET and C++ is (slightly) expensive, not that C++ itself is slow!

It’s all the motivation it took for me to port all my math code to C#.

Furthermore, hit testing need be done in code, i.e. there is no help from DirectX here.

The math being rather long to explain I will just explain what is hit testing, frustum culling and outline the basic steps involved in doing it, and let the user refer to the full source code on CodePlex and Google for an explanation of the inner mathematical working when one is needed.

But first, a word of warning,

### Note on coordinate system

When one peruse at the code, one might believe there are some elementary sign error in my math, and while it could be there are 2 initial source of confusion to be aware of!

In 3D, DirectX use a left oriented coordinate system! (as described on MSDN), whereas in normal math courses the right coordinate system is used! Also, another source of confusion, while the Y direction goes up in 3D (as seen above) it goes down in 2D!

### Ray

The ray struct represent a half line with a point of origin and a direction

public struct Ray
{
public Vector3F Origin;
public Vector3F Direction;

public static Ray operator*(Matrix4x4F m, Ray r) { /* */ }
}

It can also be applied a space transformation matrix to change its coordinate system to that of a particular object of interest.

When the user click on the screen, the code can ask the camera to create a shooting ray from the camera location in the direction of the point clicked on screen:

public class Camera : ModelBase
{
public Ray RayAt(DXContext ctxt, float x, float y) { /* */ }
//...
}

And then it can check if this ray intersect any geometry and how far they are from the ray’s source. This is the process of “hit testing”, testing that when the user click the screen, it might have “hit” a geometry under the mouse.

Rays have different method to calculate if they intersects with some objects and the distance to a given mesh (list of triangles)

public struct Ray
{
public bool IntersectBox(Box3D box) { /* */ }
public bool IntersectSphere(Vector3F p, float radius) { /* */ }
public bool IntersectTriangle(Triangle3D triangle, out float dist) { /* */}

public HitMeshResult IntersectMesh(IEnumerable<Triangle3D> mesh) { /* */ }
public struct HitMeshResult
{
public bool Hit;
public float Distance;
public int Triangle;
}
//...
}

Of course one should make sure that the ray and mesh are in the same coordinate system!
Often the mesh is loaded from a model and not edited after that, instead a world matrix transformation is applied to it. In such case one should multiple the Ray by the inverse of the object’s world transformation (provided the space is not scaled) before calculating intersection distance.

Doing an IntersectMesh on a big mesh (i.e. a mesh with lots of triangles) is expensive (the method is going to compute an intersection distance on each and all triangle of the mesh). To improve that various technique can be employed:

• First check that the bounding box of the mesh is hit (it’s a quick eliminating test)
• Place the mesh in some kind of spatial index and only test meshes that are likely to be hit, I detail this idea below in my section about OctTree.
• Index the triangle of the mesh itself in a spatial index, often an AABBTree (AABB: Axis Oriented Bounding Box), to quickly find out the triangle that should be hit tested instead of enumerating them all. This I didn’t implement at this time. Remark those particular indexes might be what make AABBTee / OctTree example on the internet rather complicated: the extra mesh’s vertice info.

### OctTree

AABB Tree, Oct Tree, Quad Tree, they are all space binary search tree; 3D space for OctTree, 2D space for QuadTree and any D for AABBtree. The only difference between each of them is the way a tree node divide the space amongst its children.

While we are on topic, I just wanted to mention here, BSP are different, they will make an ordered tree of object (instead of partitioning space).

A QuadTree node will divide the 2D space amongst its children node in 4 equal size rect. And OctTree will divide 3D space in 8 equal size wedges. An AABB tree will divide it in 2, along the longest axis for this node. Below is an example quad tree:

Seeing they all behave more or less the same I have a SpatialIndex<TItem, TBox> base class, subclasses only need to define how they partition the space. I only implemented QuadTree and OctTree so far, but I did took a page from the AABB tree and I don’t always divide space in 4 and 8 (respectively) but apply some heuristic. Consequently insert might be more costly… But it should improve memory and keep same or better query time and it will also improve some insert by making more meaningful box (i.e. equally sized, if possible).

Here is the relevant part of the implementation

public abstract class SpatialIndex<TItem, TBounds> : ICollection<TItem>
where TItem : IHasBounds<TBounds>
where TBounds : IBounds
{
public IEnumerable<TItem> Query(TBounds r) { /**/ }
public IEnumerable<TItem> Query(Predicate<TBounds> intersects) { /**/ }
//...
}

public class OctTree<T> : SpatialIndex<T, Box3D>
where T : IHasBounds<Box3D>
{ /*  */ }

public class QuadTree<T> : SpatialIndex<T, Box2D>
where T : IHasBounds<Box2D>
{ /* */ }

public interface IHasBounds<T>
where T : IBounds
{
T Bounds { get; }
}

public interface IBounds
{
bool Contains(IBounds b);
bool Intersects(IBounds b);
float MaxLength { get; }
}

As you can see both OctTree and QuadTree are collections of item with bounds.

And they have (efficient) method to query object they contain with an intersection box or an intersection predicate.

Remark this seem simple, because it is!
Most OctTree/AABB tree on the internet are complicated because they are used to index a mesh’s triangle to further optimize hit testing by only testing some triangle of a mesh instead of all triangles. This is something I left for later.

Finally OctTree brought me to the next enhancement. When one render a scene we want to render only what’s needed (for performance! DirectX can sort out what’s not visible, but it costs some time).

### Frustum culling

A frustum is a portion of a solid that lies between 2 parallel planes cutting it. In 3D graphic the frustum refer to the area that is viewed by the camera. And frustum culling mean only drawing what is in that area, culling the rest.

Again one can query the camera for the frustum. One can even do rect selection on the screen by passing a 2D box.

public class Camera
{
public Frustum GetViewFrustum(DXContext ctxt, Box2D area) { /***/ }
public Frustum GetViewFrustum() { /***/ }
//...
}

Because frustum define intersection methods it can be used to query an OctTree for visible object and only render what’s needed as in:

public override void Render(D3DGraphic g)
{
// setup graphic...
var frustum = CameraController.Camera.GetViewFrustum();
foreach (var item in octTree.Query(b => frustum.Intersects(b)))
{
// draw the item ...
}
}

### Hit Testing a scene in … Parallel

Now we got an OctTree to to index item by location, some method to test hitting, there is one last optimization that come to mind when doing hit test, how about parallelizing it?

The idea is to hit test each mesh with an hit ray in its own thread and aggregating result in the end. There is one special trick, we need to return some data!
There is Parallel.ForEach method for that! Basically it pass a value around at each iteration to aggregate the result and the code should provide a final aggregation method to aggregate all those aggregate result when all the elements have been tested!

Here is a relevant code fragment:

void HitTest()
{
// ...
// the ray of interest
var ray = RayAt(ctxt, x, y);

// will be used to coordinate threads when aggregating final results
object hitlock = new object();
// value that are calculated
float min = 0;
hitMesh = null;
// let's hit, REMARK the octTree query!
Parallel.ForEach<Tuple<HitItem, Ray.HitMeshResult>>(octTree.Query(b => ray.IntersectBox(b)),
() => null, // original result
(it, state, local) =>
{
// convert ray to mesh coordinate,
// instead of converting ALL vertices to world transform!!!
var mray = it.Transform.Invert() * ray;
var result = mray.IntersectMesh(EnumSphereTriangle());
// no hit? return current result
if (!result.Hit)
return local;

// hit!, now let's do (thread local) aggregate

// no previous result
if (local == null)
return Tuple.Create(it, result);
// merge with previous result
if (result.Distance < local.Item2.Distance)
return Tuple.Create(it, result);
return local;
},
r =>
{
if (r == null)
return;
lock (hitlock)
{
// now all thread have completed, merge the results
if (hitMesh == null || min < r.Item2.Distance)
{
hitMesh = r.Item1;
iHitTriangle = r.Item2.Triangle;
}
}
}
);
}

### Conclusion

This times I described Hit testing, Frustum culling and OctTrees, which help make those operation faster by indexing the space. I provided some code fragment to show how they are used.

There is also a fully functional hit test sample in the CodePlex repository, http://directwinrt.codeplex.com/: Sample2_HitTesting.

See you next time! :)

Tags: ,
Categories: C# | DirectX