Lloyd.NET

Programing experiments

Hit Testing

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!

coordinatesystem3d

 

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:

quadtree

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 the tree is thread safe for reading and querying.

 

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.

piramid

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
Permalink | Comments (0) | Post RSSRSS comment feed

D2D Progress

For my DirectX WinRT wrapper (now on CodePlex http://directwinrt.codeplex.com/) I took a break of D3D as I had some problem with it (more on that later) and implemented most of D2D, it was easy! ^^

And I also made the initialization even easier and more flexible.

Screenshot of Sample_D2D

So today I will write a quick how to start (with D2D) and about my latest D3D breakthrough (which is just some  C++/CX – C# technicality)

 

Initializing DirectX Graphics

To start DirectX graphic (with my API) one just initialize a DXContext and set a target, like so

var ctxt = new DXContext();
ctxt.Target = (IRenderTarget) ...;

There are 3 types of target to choose from (so far):

DXTargetSwapPanelOrWindow;
DXTargetImageSource;
Texture2D;

Target can even be changed while drawing (for example draw first on a Texture2D, which then can be used in the final scene).

DXTargetSwapPanelOrWindow wrap a SwapChainBackgroundPanel in XAML application.
Of interest DXUtils.Scenes.ScenePanel initialize DirectX, create a Target and call render on every frame.

Then one can draw, for each frame, with pseudo code like that

void Draw(DXContext ctxt)
{
    ctxt.Render = true;
    ctxt.Clear(Colors.White);

    var g3 = new D3DGraphic(ctxt)
    g3.DrawSomething(...);

    var g2 = new D2DGraphic(ctxt);
    g2.DrawSomething(...);

    ctxt.Render = false;
}

 

D2D

Remark at this stage one can download the source (http://directwinrt.codeplex.com/) and have a look at the D2D sample: Sample2_D2D.

 

This weekend and week I wrapped most of D2D API. To be precise I wrapped the following:
- geometries, brushes, bitmap, stroke style, text format, text layout, transforms

(Missing, from the top of my head, would be 2d effects, glyph run and lots of DWrite)

 

Initialization

When drawing a scene (whether D2D or D3D), for performance reason, one should initialize all items first and just call the draw primitives while rendering.

For example lets create a few geometry and brushes

public MyD2DScene()
{
    bImage = new BitmapBrush { Bitmap = new Bitmap(), };
    bImage.Bitmap.CreateWic("Assets\\space-background.jpg");

    bYRB = new LinearGradientBrush
    {
        StartPoint = new Point(100, 100),
        EndPoint = new Point(800, 800),
        GradientStops = new []
        {
            new GradientStop { position = 0, color = Colors.Yellow },
            new GradientStop { position = 0.4f, color = Colors.Red },
            new GradientStop { position = 1, color = Colors.Blue},
        },
    };

    gPath = new PathGeometry();
    using (var sink = gPath.Open())
    {
        sink.BeginFigure(new Point(), FIGURE_BEGIN.FILLED);
        sink.AddLines(new[] {
            new Point(25, 200),
            new Point(275, 175),
            new Point(50, 30),
        });
        sink.EndFigure(FIGURE_END.OPEN);
    }

    //......
}

 

In that scene snippet I created an image brush from a resource image, a gradient brush and a simple path geometry.

 

Rendering

Now I can just render all my items with just few drawing command, like so (for the geometry):

public void Render(DXContext ctxt)
{
    var g = new D2DGraphics(ctxt);
    g.Clear(Colors.Beige);

    g.Transform = DXMath.translate2d(pSkewedRect);
    g.FillGeometry(gPath, bImage);
    g.DrawGeometry(gPath, bYRB, 12, null);
}

 

D3D

Now that was easy and I got back to try to solve my dissatisfaction with my current implementation of D3D. Mostly that the C# developer is (currently) limited to the vertex buffer that I hard coded in the API.

And then I had a breakthrough. Let’s create a native pointer wrapper and write some code on the C# side that make it strongly typed.

My first attempt looked like that:

public ref class NativePointer sealed
{
private:
    uint32 sizeoft, capacity;
    void* data;

internal:
    property void* Ptr { void* get(); }

public:
    NativePointer(uint32 sizeOfT);
    virtual ~NativePointer();

    property Platform::IntPtr Data { Platform::IntPtr get(); }
    property uint32 SizeOfT { uint32 get(); }
    property uint32 Capacity;
    void Insert(uint32 offset, uint32 count);
    void Remove(uint32 offset, uint32 count);
};

That look promising, it even compiled! But then… WTF!!! Platform::IntPtr doesn’t cross ABI!!
Damn you Microsoft!

Then I had a breakthrough, what about… size_t ?!

It’s a perfectly ordinary type, except for the little twist that it projects to int32 when compiling for x86 and int64 when compiling for x64! It worked just fine, sweet!

So this is the change:

property size_t Data { size_t get(); }

On the C# side I was originally hoping to have a generic Pointer<T> class and finally use some unsafe C#.

Well I did use the unsafe C#, but I couldn’t compile code like that

public unsafe static T Get<T>(IntPtr p, int pos)
{
    T* pp = (T*)p;
    return pp[pos];
}

The compiler returns the error

Cannot take the address of, get the size of, or declare a pointer to a managed type ('T')

But it did accepts

public unsafe static int GetInt(IntPtr p, int pos)
{
    int* pp = (int*)p;
    return pp[pos];
}

Sweet…

In the end I create an abstract BasePointer<T> and a .tt template that generate all the template that I need!

Now I just have to implement a class like XNA’s VertexDeclaration and I will get a (reasonably?) solid base to go on…

And also rewrite all my buffers to use this native pointer class.

That’s it for today!
And remember: http://directwinrt.codeplex.com/


Tags: , , ,
Categories: .NET | DirectX | WinRT | C#
Permalink | Comments (0) | Post RSSRSS comment feed