 |
|
| Computers Forum Index » Computer - Graphics (Algorithms) » newbie-alert! Polygons... |
|
Page 1 of 1 |
|
| Author |
Message |
| Carsten... |
 Posted: Mon Oct 05, 2009 12:06 pm |
|
|
|
Guest
|
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 |
|
|
| Back to top |
|
|
|
| Kenneth Sloan... |
| Posted: Mon Oct 05, 2009 11:51 pm |
|
|
|
Guest
|
Carsten wrote:
Quote: 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 at (no spam) gmail.com
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/ |
|
|
| Back to top |
|
|
|
| Dave Eberly... |
| Posted: Tue Oct 06, 2009 3:55 am |
|
|
|
Guest
|
|
| Back to top |
|
|
|
| Ron Francis... |
| Posted: Fri Oct 09, 2009 4:25 am |
|
|
|
Guest
|
"Dave Eberly" <dNOSPAMeberly at (no spam) usemydomain.com> wrote in message
news:xHvym.19409$kC.12768 at (no spam) newsfe11.iad...
Thanks Dave, I'll have a look at it.
Like Carsten, I re-invented ear-clipping, but it must be pretty clumsy verbose.
Regards
Ron Francis
www.RonaldFrancis.com |
|
|
| Back to top |
|
|
|
| Carsten... |
| Posted: Wed Oct 14, 2009 4:41 pm |
|
|
|
Guest
|
Quote: Like Carsten, I re-invented ear-clipping, but it must be pretty clumsy verbose.
Wouldn't the one at GeometricTools.com, or any algoritm be pretty
heavy-duty, if the polygon-data is large and no presumptions on how
it's distributed? The link made a 'does two lines intersect'-test. ..
I've considered solving two equations with two unknowns before, and /
that/ was verbose. I still don't know if there's a quick fix to that,
but looking at the situation with the polygon ... if you don't need
the coordinates of the crossPoint. I've tested the following, and it
seems to hold:
Two lines makes four points with four possible triangles that can be
constructed between the points. It seems as if the normals of all four
triangles are equel signed if the lines intersect, and not else. If
that holds, and one has access to ie. DirectX's vector2, then it's a
quick one.
Still, there could be a lot of points that needed such a check. I'm
visualizing DEM data, and it has a lot of redundant seasurface-data. I
think that I'll use a quick algoritm, and fall back on land covering
possible hickups. A reflex-point has a good view to other neighbouring
no-reflex points, and a low probability of fouling up unless there's
strong indents and protuberances that lie together ... I think
Perhaps the vector-normal check could be put to good use on a reflex
and it's two nearest reflex neighbours, to ruleout that they block
sight to interveening ordinary points?
Carsten
... is it standard to make two hit on 'send' to accomplish? |
|
|
| Back to top |
|
|
|
|
|
All times are GMT
The time now is Thu Nov 26, 2009 5:22 pm
|
|