Complex Polygon Simplification
Author
I''m looking for a good(defined as generating the fewest convex polygons) algorithm that can take a list of polygons(some representing solid area and some representing holes to be carved from the solid area) and turn it into a list of as few convex polygons as possible that still cover all the positive area (minus holes) without overlapping etc. I know about triangulation(not the algorithms involved, just the definition of the word), but I want to generate any convex polygons not just tris and it needs to generate the least number of convex polygons possible to cover the area precisely.
Any good search keywords, references, link, resources etc on that kind of algorithm?
What youre looking for is called Constructive Solid Geometry or CSG. Its quite complicated, and in fact im learning about it right now. As for libraries that do this, i'd sure like to see one.
[edited by - Mulligan on June 3, 2003 4:16:27 PM]
[edited by - Mulligan on June 3, 2003 4:16:27 PM]
Author
Well, in my case I only need it to be done in 2D so I''m sure that simplifies it a lot (working with polygons instead of solids), but from what I''ve seen of CSG (or at least I think its CSG, in worldcraft the ''carve'' option that removes the volume of the current solid from all others overlapping it), it often generates very messy structures. For example, carving an 8 ''sided'' cylinder from a larger 8 ''sided'' cylinder (with both the same height but different radiuses) normally produced ~16 solids but you could craft the result using vertex manipulation of blocks with only 8 solids(and it ended up running much better in game because 1/3 of the faces could be eliminated from the 8 solid version to get even fewer polygons to draw for that construct)
I would probably do a constrained Delaunay triangulation -packages exist to do this.
Then iterate over every edge, from longest to shortest. If both ends remain convex when you remove the edge, remove it.
The remaining set of convex contours may not be the minimum required, but it should be very close.
Then iterate over every edge, from longest to shortest. If both ends remain convex when you remove the edge, remove it.
The remaining set of convex contours may not be the minimum required, but it should be very close.
Hi,
The fastest way is probably to triangulate the polygons first and then as a second step merge triangles into convex polygons.
Have a look at "Computational Geometry" by Mark De Berg.
This is one of the best books on computational geometry and it covers triangulation as well.
I think you can also use opengl to get the triangles.
Cheers
The fastest way is probably to triangulate the polygons first and then as a second step merge triangles into convex polygons.
Have a look at "Computational Geometry" by Mark De Berg.
This is one of the best books on computational geometry and it covers triangulation as well.
I think you can also use opengl to get the triangles.
Cheers
Author
Is triangulation very ''slow''? I''ll be needing to do it with very few, large positivle polygons with many relatively small negative polygons (holes) and I might need to recalculate it while the game is running.
I''m not even sure this is a good way to solve the problem I''m thinking about (AI navigation for an RTS), but it seems a lot better to group areas(holes will be obstacles, and the resulting polygons will be used as a nav mesh) than to use an arbitrary grid, tiles etc since a very few polygons can cover a large open area, etc. It might be best to recalculate it each time an unmovable obstacle is placed in game (like a building), but if triangulation is ''slow'' I might have to use a different method.
I''m not even sure this is a good way to solve the problem I''m thinking about (AI navigation for an RTS), but it seems a lot better to group areas(holes will be obstacles, and the resulting polygons will be used as a nav mesh) than to use an arbitrary grid, tiles etc since a very few polygons can cover a large open area, etc. It might be best to recalculate it each time an unmovable obstacle is placed in game (like a building), but if triangulation is ''slow'' I might have to use a different method.
Triangulation can be very fast if you implement it correctly. It''s not trivial to get a robust and fast implementation though. Depending on your application you might be able to make some simplifications and optimisations.
For navigation AI triangles would probably work, but I would serch the net for much more specific navigation AI algorithms instead.
Cheers,
For navigation AI triangles would probably work, but I would serch the net for much more specific navigation AI algorithms instead.
Cheers,
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
