From: Ben D. <bn...@li...> - 2000-07-07 00:44:09
|
> > Ahem. I did actually say how big the arrays need to be :-) > > > > "Take the number of vertices in the original polygon, add the number of > > clipping planes, and that's how many entries you need." > > > > This is because each plane can only ever add one vertex to the polygon > (the > > polygon is clipped to one plane at a time). Think about it. > > That's as long as the polygon is convex and planar. And it should be, > if > > you're using it with polygon3d_f() etc. > > > > By the way there are 6 clipping planes, or 5 if you don't do the max_z > > clipping. > > Yes, you are right, but the Allegro docs were confusing me because they > make the number of added vertices depend on the number of vertices in the > polygon (clip3d_f probably supports non-convex as well as non-planar > polygons, so this isn't completely wrong) Yes, it would support them. Let's consider the case for a polygon of n vertices. It could be twisted, convex, weird, make the polygon3d_f routine restart the computer (unlikely, unless you've got unsaved work in Micro$oft Office :-), even contain NaNs and Infs if you want... When a polygon is clipped to a plane, the routine first makes a list of which points are outside the plane and which are inside, in the int out[] parameter. If a single point is outside the polygon, it is replaced with two points on the plane (cutting one corner off and creating an extra side). Therefore the number of vertices could increase by 1. If two or more adjacent points are outside, they are both/all removed and two are inserted in their place, where the plane intersected with the relevant sides. Therefore the number of vertices doesn't change, or it decreases. Thus to have the most vertices in the resultant polygon, there must be as many single points outside as possible. For a triangle this is 1. For a quadrilateral it's 2. For a pentagon it's also 2. For a hexagon it's 3. So the maximum number of extra vertices for any one clipping plane is n>>1. The maximum total number of vertices is n+(n>>1). This should calculate the maximum number of output vertices required, o, given n input vertices: int o, n, c; for (o=n, c=0; c<N_CLIPPING_PLANES; c++) o+=o>>1; If someone wants to work out a non-iterative formula, be my guest. However, you may have to sacrifice the rounding at each step: after all, a pentagon will never become a hept-and-a-half-agon... Bear in mind that each time we allow for extra vertices, we consider the NEW polygon. So if a pentagon becomes a heptagon, the heptagon could then become a decagon if it wanted. Here are a few examples. Take the penultimate number for 5 clipping planes, or the last number for 6 clipping planes. 3 vertices -> 4 -> 6 -> 9 -> 13 -> 19 -> 28 4 vertices -> 6 -> 9 -> 13 -> 19 -> 28 -> 42 5 vertices -> 7 -> 10 -> 15 -> 22 -> 33 -> 49 6 vertices -> 9 -> 13 -> 19 -> 28 -> 42 -> 63 Note that a triangle cannot be concave or twisted. Also note that clip3d_f is unlikely to create the worst polygons possible when it clips, so these numbers are probably still larger than necessary. But if you really DO want to be safe, and don't want to assume that your polygons are nice, then that's the sad truth about clip3d_f! Hope this helps, Ben Davis |