Is there an efficient\easy way to draw a concave polygon in Direct3d

Question

I'm trying to draw a polygon using c# and directx

All I get is an ordered list of points from a file and I need to draw the flat polygon in a 3d world.

I can load the points and draw a convex shape using a trianglefan and drawuserprimitives.

This obviously leads to incorrect results when the polygon is very concave (which it may be).

I can't imagine I'm the only person to grapple with this problem (tho I'm a gfx/directx neophyte - my background is in gui\windows application development).

Can anyone point me towards a simple to follow resource\tutorial\algorithm which may assist me?

Answer 1

Direct3D can only draw triangles (well, it can draw lines and points as well, but that's besides the point). So if you want to draw any shape that is more complex than a triangle, you have to draw a bunch of touching triangles that equal to that shape.

In your case, it's a concave polygon triangulation problem. Given a bunch of vertices, you can keep them as is, you just need to compute the "index buffer" (in simplest case, three indices per triangle that say which vertices the triangle uses). Then draw that by putting into vertex/index buffers or using DrawUserPrimitives.

Some algorithms for triangulating simple (convex or concave, but without self-intersections or holes) polygons are at VTerrain site.

I have used Ratcliff's code in the past; very simple and works well. VTerrain has a dead link to it; the code can be found here. It's C++, but porting that over to C# should be straightforward.

Oh, and don't use triangle fans. They are of very limited use, inefficient and are going away soon (e.g. Direct3D 10 does not support them anymore). Just use triangle lists.

Answer 2

Triangulation is he obvious answer, but it's hard to write a solid triangulator. Unless you have two month time to waste don't even try it.

There are a couple of codes that may help you:

The GPC Library. Very easy to use, but you may not like it's license:

http://www.cs.man.ac.uk/~toby/alan/software/gpc.html

There is also triangle:

http://www.cs.cmu.edu/~quake/triangle.html

And FIST:

http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html

Another (and my prefered) option would be to use the GLU tesselator. You can load and use the GLU library from DirectX programs just fine. It does not need an OpenGL context to use it and it's pre-installed on all windows machines. If you want source you can lift off the triangulation code from the SGI reference implementation. I did that once and it took me just a couple of hours.

So far for triangulation. There is a different way as well: You can use stencil tricks.

The general algorithm goes like this:

1. Disable color- and depth writes. Enable stencil writes and setup your stencil buffer that it will invert the current stencil value. One bit of stencil is sufficient. Oh - your stencil buffer should be cleared as well.

2. Pick a random point on the screen. Any will do. Call this point your Anchor.

3. For each edge of your polygon build a triangle from the two vertices that build the edge and your anchor. Draw that triangle.

4. Once you've drawn all these triangles, turn off stencil write, turn on stencil test and color-write and draw a fullscreen quad in your color of choice. This will fill just the pixels inside your convex polygon.

It's a good idea to place the anchor into the middle of the polygon and just draw a rectangle as large as the boundary box of your polygon. That saves a bit of fillrate.

Btw - the stencil technique works for self-intersecting polygons as well.

Hope it helps, Nils

Answer 3

If you are able to use the stencil buffer, it should not be hard to do. Here's a general algorithm:

Clear the stencil buffer to 1.
Pick an arbitrary vertex v0, probably somewhere near the polygon to reduce floating-point errors.
For each vertex v[i] of the polygon in clockwise order:
    let s be the segment v[i]->v[i+1] (where i+1 will wrap to 0 when the last vertex is reached)
    if v0 is to the "right" of s:
        draw a triangle defined by s, v[i], v[i+1] that adds 1 to the stencil buffer
    else
        draw a triangle defined by s, v[i], v[i+1] that subtracts 1 from the stencil buffer
end for
fill the screen with the desired color/texture, testing for stencil buffer values >= 2.

By "right of s" I mean from the perspective of someone standing on v[i] and facing v[i+1]. This can be tested by using a cross product:

cross(v0 - v[i], v[i+1] - v[i]) > 0

Answer 4

I just had to do this for a project. The simplest algorithm I found is called "Ear Clipping". A great paper on it is here: TriangulationByEarClipping.pdf

I took me about 250 lines of c++ code and 4 hours to implement the brute force version of it. Other algorithms have better performance, but this was simple to implement and understand.