Gamestudio Links
Zorro Links
Newest Posts
zorro license, IB connection
by miwok. 12/06/23 16:32
Newbie Questions
by fairtrader. 12/06/23 11:29
Zorro Trader GPT
by TipmyPip. 12/04/23 11:34
Square root rule
by Smallz. 12/02/23 09:15
RTest not found error
by TipmyPip. 12/01/23 21:43
neural function for Python to [Train]
by TipmyPip. 12/01/23 14:47
Xor Memory Problem.
by TipmyPip. 11/28/23 14:23
Training with command line parameters
by TipmyPip. 11/26/23 08:42
AUM Magazine
Latest Screens
A psychological thriller game
SHADOW (2014)
DEAD TASTE
Tactics of World War I
Who's Online Now
6 registered members (miwok, AndrewAMD, TipmyPip, 3run, Quad, 1 invisible), 645 guests, and 2 spiders.
Key: Admin, Global Mod, Mod
Newest Members
fairtrader, hus, Vurtis, Harry5, KelvinC
19019 Registered Users
Previous Thread
Next Thread
Print Thread
Rate Thread
Page 1 of 2 1 2
Points and faces #345402
10/25/10 21:13
10/25/10 21:13
Joined: Sep 2003
Posts: 9,859
F
FBL Offline OP
Senior Expert
FBL  Offline OP
Senior Expert
F

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 laugh

Re: Points and faces [Re: FBL] #345404
10/25/10 21:35
10/25/10 21:35
Joined: May 2002
Posts: 7,441
ventilator Offline
Senior Expert
ventilator  Offline
Senior Expert

Joined: May 2002
Posts: 7,441
http://en.wikipedia.org/wiki/Polygon_triangulation
have 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 Offline
Member
Saturnus  Offline
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: Saturnus] #345406
10/25/10 22:00
10/25/10 22:00
Joined: Sep 2003
Posts: 5,900
Bielefeld, Germany
Pappenheimer Offline
Senior Expert
Pappenheimer  Offline
Senior Expert

Joined: Sep 2003
Posts: 5,900
Bielefeld, Germany
Starting with an edge, you set a position that is perpendicular to the edge from the middle of that edge in a distance of the length of the edge - then you choose the closest free point to this position as the third point of the triangle.
This is at least, what I would start from.

Re: Points and faces [Re: Pappenheimer] #345407
10/25/10 22:32
10/25/10 22:32
Joined: Sep 2003
Posts: 9,859
F
FBL Offline OP
Senior Expert
FBL  Offline OP
Senior Expert
F

Joined: Sep 2003
Posts: 9,859
I have an idea how to triangulate the shape above. When building a face I need to check wheter the third vertex is left (outside) or right (inside) of the line conencting the first two vertices.
If this is the case I have my first triangle and I can mark point 2 as "done". I'll need points 1 and 3 for further recursion.

I'll continue like this until point 3 is on the left side. This means I have some concave form and I can't build a proper triangle. So I skip this vertex and try with the next vertex. When I've cycled through the vertex cloud once, I have some polygon shape, with some of the original vertices already "cut off".
I continue now until only 3 vertices remain. That's the last polygon.

It works for simple concave shapes, but not for complex shapes like labyrinths... so it is not a solution.

Re: Points and faces [Re: ventilator] #345408
10/25/10 22:36
10/25/10 22:36
Joined: Sep 2003
Posts: 9,859
F
FBL Offline OP
Senior Expert
FBL  Offline OP
Senior Expert
F

Joined: Sep 2003
Posts: 9,859
Originally Posted By: ventilator
http://en.wikipedia.org/wiki/Polygon_triangulation
have 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] #345410
10/25/10 22:49
10/25/10 22:49
Joined: Sep 2003
Posts: 9,859
F
FBL Offline OP
Senior Expert
FBL  Offline OP
Senior Expert
F

Joined: Sep 2003
Posts: 9,859
The sweep line method looks fine though. I did find the Wikipedia page, but I did not see the link to this nice flash app. Thanks for pointing out.

Now I need to find a save way to resolve holes in the polygon shape. I guess the basic solution is to get rid of holes by adding two lines which share the same vertices in order to connect the hole to the outer shape. As long as there is only one hole, this is easy, but there can be an undefined number of holes in the shape.

Re: Points and faces [Re: FBL] #345450
10/26/10 12:21
10/26/10 12:21
Joined: Dec 2008
Posts: 271
Saturnus Offline
Member
Saturnus  Offline
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] #345464
10/26/10 16:03
10/26/10 16:03
Joined: Oct 2004
Posts: 4,134
Netherlands
Joozey Offline
Expert
Joozey  Offline
Expert

Joined: Oct 2004
Posts: 4,134
Netherlands
I'd say just find the three closest vertices, no holes and no isolated vertices tongue but it might result in some strange geometry tongue.


Click and join the 3dgs irc community!
Room: #3dgs
Re: Points and faces [Re: Saturnus] #345467
10/26/10 17:04
10/26/10 17:04
Joined: Sep 2003
Posts: 9,859
F
FBL Offline OP
Senior Expert
FBL  Offline OP
Senior Expert
F

Joined: Sep 2003
Posts: 9,859
Originally Posted By: Saturnus
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...

Page 1 of 2 1 2

Moderated by  HeelX, Lukas, rayp, Rei_Ayanami, Superku, Tobias, TWO, VeT 

Gamestudio download | chip programmers | Zorro platform | shop | Data Protection Policy

oP group Germany GmbH | Birkenstr. 25-27 | 63549 Ronneburg / Germany | info (at) opgroup.de

Powered by UBB.threads™ PHP Forum Software 7.7.1