|
|
Points and faces
#345402
10/25/10 21:13
10/25/10 21:13
|
Joined: Sep 2003
Posts: 9,859
FBL
OP
Senior Expert
|
OP
Senior Expert
Joined: Sep 2003
Posts: 9,859
|
Let's say I have a bunch of numbered vertices. Each vertex has a reference to the next vertex. All of these vertices define a polygon. There might be isolated vertices or a second set of numbered vertices which define a hole in the polygon. I need to triangulate the resulting shape. But I can't think of a right approach. I've searched about that topic and it doesn't seem to be that easy... bur maybe someone has a good explanation for me. Example (without isolated vertices and holes): Thanks for hints 
|
|
|
Re: Points and faces
[Re: FBL]
#345404
10/25/10 21:35
10/25/10 21:35
|
Joined: May 2002
Posts: 7,441
ventilator
Senior Expert
|
Senior Expert
Joined: May 2002
Posts: 7,441
|
http://en.wikipedia.org/wiki/Polygon_triangulationhave you looked into the algorithms mentioned here? yes, with special cases like holes it probably isn't that easy. what do you need this for? i think there also are some ready to use c/c++ libraries for triangulation.
|
|
|
Re: Points and faces
[Re: FBL]
#345405
10/25/10 21:36
10/25/10 21:36
|
Joined: Dec 2008
Posts: 271
Saturnus
Member
|
Member
Joined: Dec 2008
Posts: 271
|
Perhaps this helps?
http://computacion.cs.cinvestav.mx/~anzures/geom/triangulation.php
It's a polygon triangulation flash application (source can be downloaded as well - didn't have a look at it, though). It uses the sweep line algorithm. Doesn't look that complicated at a first glance, but I might be wrong here.
Edit: Link is also on the wiki page posted by ventilator. That's where I got it from actually.
Last edited by Saturnus; 10/25/10 21:38.
|
|
|
Re: Points and faces
[Re: ventilator]
#345408
10/25/10 22:36
10/25/10 22:36
|
Joined: Sep 2003
Posts: 9,859
FBL
OP
Senior Expert
|
OP
Senior Expert
Joined: Sep 2003
Posts: 9,859
|
http://en.wikipedia.org/wiki/Polygon_triangulationhave you looked into the algorithms mentioned here? yes, with special cases like holes it probably isn't that easy. what do you need this for? i think there also are some ready to use c/c++ libraries for triangulation. I need to convert any shape defined via vertices into a d3d mesh. Problem is the input data is not really made for polygonal meshes - I have to convert it and it seems like this is a real problem.
|
|
|
Re: Points and faces
[Re: FBL]
#345450
10/26/10 12:21
10/26/10 12:21
|
Joined: Dec 2008
Posts: 271
Saturnus
Member
|
Member
Joined: Dec 2008
Posts: 271
|
I don't know whether this helps, but I've found a relatively simple triangulation program written in C. Obviously it doesn't use any libraries at all (except for the C Standard Libary) and only consists of a few source and header files. It's also well commented (in contrast to the ActionScript thingy). From the Readme: "The algorithm handles simple polygons with holes. The input is specified as contours. [...] The output is a list of triangles."ftp://ftp.cs.unc.edu/pub/users/manocha/CODE/Triangulation/I thought, you might be interested in this.
|
|
|
Re: Points and faces
[Re: Saturnus]
#345467
10/26/10 17:04
10/26/10 17:04
|
Joined: Sep 2003
Posts: 9,859
FBL
OP
Senior Expert
|
OP
Senior Expert
Joined: Sep 2003
Posts: 9,859
|
I don't know whether this helps, but I've found a relatively simple triangulation program written in C. Obviously it doesn't use any libraries at all (except for the C Standard Libary) and only consists of a few source and header files. It's also well commented (in contrast to the ActionScript thingy). From the Readme: "The algorithm handles simple polygons with holes. The input is specified as contours. [...] The output is a list of triangles."ftp://ftp.cs.unc.edu/pub/users/manocha/CODE/Triangulation/I thought, you might be interested in this. the remark about the holes makes it very interesting. Thanks a lot for this link. I'll check it out next evening. @Joozey: Unfortunately it won't work that easy, as not every close vertex should have a direct connection. Think of very strange polygonal forms...
|
|
|
|