## Re: [Algorithms] theoretical clipping behavior

 Re: [Algorithms] theoretical clipping behavior From: Ron Levine - 2000-11-02 00:19:22 ```Neil Tringhan wrote > As I recall, the general result is that for clipping a convex polygon of n > vertices against m planes, the resulting clipped polygon can have up to > (n+m) vertices, though I can't find my proof for this:-) The way to prove it is to bound the number of edges. Recall that the intersection of two convex sets is convex, so the result of clipping a convex polygon by a plane is convex. Consider the result of clipping a convex polygon by a single plane. The edges of the clipped polygon are each either an edge of the original polygon, a subsegment of an edge of the original polygon, or a segment contained in the line of intersection of the plane of the polygon and the clipping plane. Moreover, by convexity, each original edge can contribute at most one subsegment and the line of intersection can contribute at most one edge. So the result of clipping a convex polygon by a plane has at most one more edge than the original polygon. Also, the result of clipping a convex polygon by a plane is a convex polygon. So by induction, you can increase the number of edges by at most one for each clipping plane. A polygon has as many vertices as edges. QED >You can wave your > hands about and say something along the lines of "the maximum number of > output vertices is the number of input vertices plus the number of times an > input edge could have cut a plane", though. That is indeed hand-waving, for the desired conclusion does not follow. It could happen that some input edges cut every clipping plane and some clipping planes are cut by two input edges, so this assertion still allows a greater limit on the number of vertices than you are seeking. To cut it down you have to invoke convexity and induction. ```

 [Algorithms] theoretical clipping behavior From: Andrew Sega - 2000-11-01 18:03:45 ```In the midst of debugging a Sutherland-Hodgman style polygon clipper, I came across an interesting question: Clipping a 2D triangle to a single plane will give you a most 2 resultant triangles (when the plane cuts two edges). Clipping a 2D triangle to a box (4 planes) will give you at most 5 resultant triangles (when the box cuts through all four edges of the box). exxtending the question to 3D... How many potential triangles can you get by clipping an arbitrary 3D triangle to an arbitrary 3D box (6 planes)? And how would one derive such a result? - andrew ```
 Re: [Algorithms] theoretical clipping behavior From: Daniel Renkel - 2000-11-01 18:46:01 Attachments: clipping.jpg ```hi andrew, probably i got somethign completely wrong, but i get much more tris than you do (already in 2d) and i believe that this is the same in 3d (but talking to a digital anviler makes me think that i miss a point here =0) take a look at the attached jpeg ;o) [best done in your favourite browser] my 2 cents, Daniel "SirLeto" Renkel [D.Renkel@...] technical design director - creactivity and technowhow Future Interactive [http://www.FutureInt.de] ----- Original Message ----- From: "Andrew Sega" To: Sent: Wednesday, November 01, 2000 7:03 PM Subject: [Algorithms] theoretical clipping behavior > > In the midst of debugging a Sutherland-Hodgman style polygon clipper, I came > across an interesting question: > > Clipping a 2D triangle to a single plane will give you a most 2 resultant > triangles (when the plane cuts two edges). > Clipping a 2D triangle to a box (4 planes) will give you at most 5 resultant > triangles (when the box cuts through all four edges of the box). > > exxtending the question to 3D... > > How many potential triangles can you get by clipping an arbitrary 3D > triangle to an arbitrary 3D box (6 planes)? And how would one derive such a > result? > > - andrew > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > ```
 Re: [Algorithms] theoretical clipping behavior From: Neal Tringham - 2000-11-01 18:51:06 ```From: Andrew Sega > > In the midst of debugging a Sutherland-Hodgman style polygon clipper, I came > across an interesting question: > > Clipping a 2D triangle to a single plane will give you a most 2 resultant > triangles (when the plane cuts two edges). > Clipping a 2D triangle to a box (4 planes) will give you at most 5 resultant > triangles (when the box cuts through all four edges of the box). > > exxtending the question to 3D... > > How many potential triangles can you get by clipping an arbitrary 3D > triangle to an arbitrary 3D box (6 planes)? And how would one derive such a > result? As I recall, the general result is that for clipping a convex polygon of n vertices against m planes, the resulting clipped polygon can have up to (n+m) vertices, though I can't find my proof for this:-) You can wave your hands about and say something along the lines of "the maximum number of output vertices is the number of input vertices plus the number of times an input edge could have cut a plane", though. I think it should then be possible to represent the polygon output by the clipper as a convex triangle fan, in which case you have (k-2) separate triangles, where k is the number of vertices in the clipped polygon ((n+m) in the paragraph above). Thus for your example, the triangle clipped against the 6 sided box can yield an output polygon with up to 9 vertices, which in turn can be represented as up to 7 separate convex triangles. Hopefully that was of some use... Does anybody have a counter example for this? Or even a proper proof which contradicts it? :-) Neal Tringham (Sick Puppies / Empire Interactive) neal@... neal@... ```
 Re: [Algorithms] theoretical clipping behavior From: Daniel Renkel - 2000-11-01 19:31:46 ```thx neal, you gave the well written theory behind my grapical representing practical example ;o) i bleive having n+m is alway the "maximum" full cut, havin less means not having a full cut. greetz, Daniel "SirLeto" Renkel [D.Renkel@...] technical design director - creactivity and technowhow Future Interactive [http://www.FutureInt.de] ----- Original Message ----- From: "Neal Tringham" To: Sent: Wednesday, November 01, 2000 7:53 PM Subject: Re: [Algorithms] theoretical clipping behavior > > As I recall, the general result is that for clipping a convex polygon of n > vertices against m planes, the resulting clipped polygon can have up to > (n+m) vertices, though I can't find my proof for this:-) You can wave your > hands about and say something along the lines of "the maximum number of > output vertices is the number of input vertices plus the number of times an > input edge could have cut a plane", though. > > I think it should then be possible to represent the polygon output by the > clipper as a convex triangle fan, in which case you have (k-2) separate > triangles, where k is the number of vertices in the clipped polygon ((n+m) > in the paragraph above). > > Thus for your example, the triangle clipped against the 6 sided box can > yield an output polygon with up to 9 vertices, which in turn can be > represented as up to 7 separate convex triangles. > > Hopefully that was of some use... Does anybody have a counter example for > this? Or even a proper proof which contradicts it? :-) > > > Neal Tringham (Sick Puppies / Empire Interactive) > ```
 Re: [Algorithms] theoretical clipping behavior From: Ron Levine - 2000-11-02 00:19:22 ```Neil Tringhan wrote > As I recall, the general result is that for clipping a convex polygon of n > vertices against m planes, the resulting clipped polygon can have up to > (n+m) vertices, though I can't find my proof for this:-) The way to prove it is to bound the number of edges. Recall that the intersection of two convex sets is convex, so the result of clipping a convex polygon by a plane is convex. Consider the result of clipping a convex polygon by a single plane. The edges of the clipped polygon are each either an edge of the original polygon, a subsegment of an edge of the original polygon, or a segment contained in the line of intersection of the plane of the polygon and the clipping plane. Moreover, by convexity, each original edge can contribute at most one subsegment and the line of intersection can contribute at most one edge. So the result of clipping a convex polygon by a plane has at most one more edge than the original polygon. Also, the result of clipping a convex polygon by a plane is a convex polygon. So by induction, you can increase the number of edges by at most one for each clipping plane. A polygon has as many vertices as edges. QED >You can wave your > hands about and say something along the lines of "the maximum number of > output vertices is the number of input vertices plus the number of times an > input edge could have cut a plane", though. That is indeed hand-waving, for the desired conclusion does not follow. It could happen that some input edges cut every clipping plane and some clipping planes are cut by two input edges, so this assertion still allows a greater limit on the number of vertices than you are seeking. To cut it down you have to invoke convexity and induction. ```
 Re: [Algorithms] theoretical clipping behavior From: Eric Lengyel - 2000-11-01 22:42:11 ```> In the midst of debugging a Sutherland-Hodgman style polygon clipper, I came > across an interesting question: > > Clipping a 2D triangle to a single plane will give you a most 2 resultant > triangles (when the plane cuts two edges). > Clipping a 2D triangle to a box (4 planes) will give you at most 5 resultant > triangles (when the box cuts through all four edges of the box). > > exxtending the question to 3D... > > How many potential triangles can you get by clipping an arbitrary 3D > triangle to an arbitrary 3D box (6 planes)? And how would one derive such a > result? For an arbitrary convex polygon of n vertices, clipping against a single plane will result in a convex polygon of at most n+1 vertices. Thus, clipping the original polygon against m arbitrary planes results in a polygon of at most n+m vertices. The resultant polygon can then be treated as a triangle fan of at most n+m-2 triangles. For a triangle clipped against six planes, this gives us a maximum of 3+6-2 = 7 triangles. Now that result is the maximum for six *arbitrary* planes -- knowing that the six planes are arranged as a box may very well reduce that maximum, but I haven't spent the time to figure that out. -- Eric Lengyel ```
 Re: [Algorithms] theoretical clipping behavior From: Ron Levine - 2000-11-01 23:29:19 ```Andrew Sega wrote > > In the midst of debugging a Sutherland-Hodgman style polygon clipper, I came > across an interesting question: > > Clipping a 2D triangle to a single plane... First, ALL triangles are 2D in the sense that they all lie entirely in a plane. The clipping plane will be a plane that intersects the plane of the triangle in a line, so it is superfluous to say "2D" >...will give you a most 2 resultant > triangles (when the plane cuts two edges). Rather I would say that the clipped part (remaining on the "in" side of the clipping plane) is either a triangle or a trapezoid. The trapezoid may then be triangulated into two triangles (in two different ways). > Clipping a 2D triangle to a box (4 planes) will give you at most 5 resultant > triangles (when the box cuts through all four edges of the box). > Rather, I would say that the clipped part is a triangle, a convex quadrilateral, a convex pentagon, or a convex hexagon, depending on whether each leg of the triangle intersects 0, 1, or 2 edges of the box. Each of this cases can be triangulated into a number of triangles one less than the number of sides, but in several different ways. > exxtending the question to 3D... > > How many potential triangles can you get by clipping an arbitrary 3D > triangle to an arbitrary 3D box (6 planes)? And how would one derive such a > result? > A 3D triangle IS a 2D triangle, considered in its own plane (see above). The intersection of any clipping plane with the plane of the triangle is a line. Your question is vacuous. The 3D case is exactly the same as the 2D case. ```