PDA

View Full Version : Subdivision of convex polygons.


judgex
04-06-2005, 04:40 AM
I would like a method of subdividing a convex polygon into two or more smaller polygons so that:

1. Each polygon in the result is convex.
2. The number of polygons in the result is at a minimum.
3. No edge of the original polygon is split.
4. The area of each polygon in the result is at a maximum.

I would also be interested in the same method with the last condition removed (i.e., area not important).

Any feedback on how methods like these can be found or constructed is appreciated.

nurcc
04-06-2005, 07:58 AM
When designing algorithms, I tend to start off with a simple and usually stupid approach, and then work from there. In this case, it looks like you probably just want to split a convex polygon into two, such that the split is as even as possible.

If you don't add any new vertices, then you'll be guaranteed that such a split will result in two convex polygons, as there is no straight line between any two points of a convex polygon that will go outside the original polygon.

The question then becomes, how much runtime do you have to do this? If you don't have much, I'd probably settle for some heuristic like:
- If you have n vertices around your polygon, split between the first and the n/2th
- Or, start at some point, and collect edge lengths in both directions, splitting from the original point to the point where the edge lengths are approximately equal.

If you've got plenty or runtime, might as well just try every possible split, and see which one gives you the best division of area, although there might be a fancier way to do it. It'd help to know what the limitations and goals your algorithm should be designed for.

And here's something random - Steiner vertices. I've never used them, but some people seem to think they're cool.

judgex
04-06-2005, 02:21 PM
I plan to use the algorithm to improve the quality of smooth shading on a scene. The scene is static and the processing is not done in real-time. So the available run-time is less of a concern than is the quality of the results.

nurcc
04-06-2005, 07:49 PM
I plan to use the algorithm to improve the quality of smooth shading on a scene.

What type of renderer is doing the smooth shading? If you're using OpenGL, you probably just want to split into triangles, as that's how the smooth shading is interpolated on many graphics cards anyway.. I think by default they do a triangle fan from one of the existing points, which can introduce some rather bad shading artifacts. A better method would be to find a point in the middle of the polygon, and do a fan from there, which would proabably give you more what you're looking for..

judgex
04-07-2005, 11:20 AM
I like the method of triangulating a polygon from its centre. When the polygon is a triangle, I will join the midpoint of the longest edge to the point opposite that edge. Should I do this? Remember:

1. Splitting an edge can create a crack in the scene.
2. Each crack takes two polygons to repair and these two polygons must be added to the scene.

So two extra polygons may be added to the scene for every triangle processed by the method.

CGTalk Moderation
04-07-2005, 11:20 AM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.