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

Question

I am trying to draw a polygon using c # and directx

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

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

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

I can not imagine that I am the only person who can cope with this problem (I am a neophyte gfx / directx - my background is in the development of gui \ windows applications).

Can someone point me to a simple approach to the resource \ tutorial \ algorithm that can help me?

Answer 1

Direct3D can only draw triangles (well, it can also draw lines and points, but apart from the point). Therefore, if you want to draw any complex shape than a triangle, you need to draw a bunch of touching triangles equal to this shape.

In your case, this is a concave polygonal triangulation problem. Given a bunch of vertices, you can save them as they are, you just need to calculate the "index buffer" (in the simplest case, three indices per triangle, which say which vertices use the triangle). Then draw this by putting in vertex buffers / index or using DrawUserPrimitives.

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

I have used Ratcliff code in the past; very simple and works well. VTerrain has a dead link to it; The code can be found here . This is C ++, but porting to C # should be simple.

Oh, and don't use triangle fans. They are very limited, inefficient, and will leave soon (for example, Direct3D 10 no longer supports them). Just use lists of triangles.

Answer 2

Triangulation is the obvious answer, but it's hard to write a solid triangulator. If you do not have a two-month time for waste, do not even try.

There are several codes that can help you:

GPC library. Very easy to use, but you may not like the license:

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

There is also a 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 preferred) option would be to use the GLU tester. You can download and use the GLU library from DirectX programs just fine. It does not need an OpenGL context to use it, and it is pre-installed on all Windows machines. If you want to use the source, you can remove the triangulation code from the SGI reference implementation. I did this once, and it took me just a couple of hours.

So far for triangulation. There is another way: you can use stencil tricks.

The general algorithm is as follows:

• Disable recording color and depth. Turn on screen recording and adjust the screen buffer to invert the current screen value. One piece of stencil is enough. Oh - your stencil buffer should also be cleared.

• Select a random point on the screen. Anyone will do. Call this item your anchor.

• For each edge of your polygon, build a triangle of two vertices that build an edge and your anchor. Draw this triangle.

• After you draw all these triangles, turn off screen printing, turn on screen printing and color recording and draw a full-screen square in your color of choice. This will only fill the pixels inside your convex polygon.

It’s a good idea to place the anchor in the middle of the polygon and just draw a rectangle the size of the border field of your polygon. This saves a bit of filling.

Btw - The stencil method works for self-intersecting polygons.

Hope this helps, Nils

Answer 3

If you can use a stencil buffer, this is not difficult to do. Here's the 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 s" I mean from the point of view of a person standing on v [i] and facing v [i + 1]. This can be tested using a cross-product:

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

Answer 4

I just needed to do this for the project. The simplest algorithm I have found is called Ear Trimming. Great article on it: TriangulationByEarClipping.pdf

I took about 250 lines of C ++ code and 4 hours to implement its version for brute force. Other algorithms have better performance, but it was easy to implement and understand.