Hi, is there some simple and generic algorithm to split complex polys (even with holes) into set of triangles?
Something as easy as first algorithm on http://astronomy.swin.edu.au/~pbourke/geometry/insidepoly/. Thank you.
Awesoken at
Haha, no. If you find one, I will eat my invisible hat. : P When I first played around with OpenGL code in 2000, I thought it would be worthwhile to write my own tesselator. After a week of programming, I thought I had it working perfectly. Then later, I discovered some rare cases that it barfed on... but I was into other things at the time, so I never fixed it.
A few months later, I discovered that OpenGL comes with its own built-in tesselation routines. I've never used them, but they look like everything you want. See this link for more info.
Anonymous at
I would have used delaunay triangulation with constraints...
counting_pine at
This is sort of off the top of my head, so there's probably on a hole, so to speak, in it somewhere:
- Choose three vertices, connect them with three edges, thus forming a hypothetical triangle
- Check a point inside the triangle to make sure its is actually part of the polygon
- Make sure none of the polygon's other vertices are inside the triangle
- Make sure none of the edges of the polygon intersect with the edges edges of the triangle
- If the above conditions are true, remove the triangle from the polygon, otherwise choose another set of three vertices.
- Repeat until there's no polygon left.
I don't know if the algorithm has to be realtime, but I think it's O(n^3). There are probably ways to make it more efficient.
Are there any problems with this? Maybe procedures for checking/removing aren't as simple as I (tentatively) assume?
etko at
Glu functions seems easy but I don't want to link with 400+ kb library just for tesselations :).
I want to have algorithm realtime in manner that when for the polygon struct triangles are not present they are generated and cached, and when point & edges are added cache is invalidated and poly is reteselated.
Awesoken at
Yeah, ok. I will post my efforts in complex polygon triangulation:
http://advsys.net/ken/qb/triangul.bas It's made for QuickBasic 4.5. If you don't have that, you'll need to download Qbasic.exe from somewhere and add this to enable mouse support.
When you run the program, start by building a sector in the same fashion as the Build editor in 2D mode (space bar, move mouse, space bar, move mouse, and connect the final point by pressing space bar over the first point). You can drag points together to delete vertices, draw a loop inside a loop by doing the space bar stuff, and insert points with the insert key. The function of interest, tesspolygon, defines polygons in the exact same way as the Build structures. There are other functions, but I don't want to give it all away : )
plugwash at
Awesoken said
Haha, no. If you find one, I will eat my invisible hat. : P When I first played around with OpenGL code in 2000, I thought it would be worthwhile to write my own tesselator. After a week of programming, I thought I had it working perfectly. Then later, I discovered some rare cases that it barfed on... but I was into other things at the time, so I never fixed it.
so what does polymost use?
Awesoken at
Polymost 3D mode works with "vertical trapezoid soup". This restriction makes the issue of triangulation a bit simpler than the general case... still too complex for me to explain here though. If you have QuickBasic, you can try my original test program for Polymost: POLYMOST.BAS
plugwash at
surely you still have to triangulate the floors though and they can be any shape even with internal holes...
btw i took a quick look at polymost.bas but it didn't make a great deal of sense to me