Re: newbie-alert! Polygons

Carsten wrote:
HI all
I'm about to write a code that draws a polygon in directX 9. Only
primitive triangles are available to draw, so the polygon (an array of
2d vectors) are going to be split into into primitive triangles.
No swet for a purely concave polygon.
I'm considering running through all points and calculate the normal in
each point (the point the center with two closest neighbours). I've
given up zero constraints, and demand a clockwise/anticlockwise
constructed polygon ... that way, the normal will change sign for
points that lie convex in the polygon.- great!
The next step is .. still up for grabs.
One convex point in the polygon makes a good startingpoint for drawing
triangles (ie a fan) with the point as a member in all of them- great!
Two convex points are ideal to join and thus split the polygon into
two concave polygons.

My idea for multiple convex points are, to step through every second
point, check weather the mid-point-normal is ok, draw the triangle (if
ok), and take the point off the polygon. To iterate: Make a new
polygon with a reduced point-count + a set of redy drawable triangles.
I've noticed on my scetch, that the number of concave points shrink
through this procedure, and it'll have to converge toward 2.

Only snag is, that the ok-points that I take out to draw ... there is
no guarantee, that they won't end up covering a convex point and draw
outside the polygon. Though it may be a rare ocurrence, I thought that
you guys have been presented with the problem before and maybe have a
less clumsy way, or even ... the right way ;o)

Cheers

I used to mail through OutlookExpress
... so, this message may wind up 'somewhere'
... with a life of its own

You have (almost) re-invented "ear-clipping". Move around the polygon until you reach a convex vertex. CHECK to be sure that painting the triangle (previous vertex, THIS convex vertex, next vertex) will not obscure any other vertex. If so, paint it, it not, keep going.

Once you get it working, you can start worrying about making it fast (fast enough for YOUR application).

Google "ear clipping triangulating polygons" and you should find many discussions of this algorithm.

There are other, more THEORETICALLY appealing methods - but my standard advice is that no one should even consider these until after ear-clipping is already working and you are getting some real work done with it.

If you are desperate, I can probably dig up some ancient C code - please poke me off-list if you really want 20 year old C code.


--
Kenneth Sloan KennethRSloan@xxxxxxxxx
Computer and Information Sciences +1-205-932-2213
University of Alabama at Birmingham FAX +1-205-934-5473
Birmingham, AL 35294-1170 http://KennethRSloan.com/
.

Relevant Pages

  • RE: Mesh and Polygon
    ... Does it need to be done using DirectX? ... > I can draw triangles, and sets of triangles to draw simple polygons. ... > But when I try to draw one ireegular polygon I don't have anything to ...
    (microsoft.public.win32.programmer.directx.managed)
  • Re: How to get trinagles from a polygon?
    ... For arbitrary triangles there are a lot of non trivial algorithms you can ... > If the polygon is concave, start at a vertex and read the ... > other vertexes in succession (clock wise or anti-clock wise, ... > If it is convex, the previous process will generally fails (it may ...
    (microsoft.public.win32.programmer.directx.managed)
  • Mesh and Polygon
    ... I'm a newbie in DirectX and this should be very easy but I cannot ... I can draw triangles, and sets of triangles to draw simple polygons. ... But when I try to draw one ireegular polygon I don't have anything to ...
    (microsoft.public.win32.programmer.directx.managed)
  • Re: outline polygon of overlapping triangles
    ... where I can get an algorithm that creates ... If you want the polygon that is the union of the ... triangles, the suggestion to use Alan Murtha's ...
    (comp.graphics.algorithms)
  • Re: From Triangle tiles to convex Polygons.
    ... I start out with a complicated non-convex polygon with holes. ... it into OpenGL GLU, and I get back a few hundred triangles that ... problem is that a few hundred triangles is way too many, ... I think you can do this by taking your triangulation and merge triangles to build multiple convex polygons from it. ...
    (comp.graphics.algorithms)
Loading