Started by Nov 12 2012 08:10 PM

,
No replies to this topic

Posted 12 November 2012 - 08:10 PM

Hello. I have a question regarding clipping a polygon against a view frustum.

For simplicity, consider the case of clipping a triangle to a rectangle. The Sutherland-Hodgman algorithm achieves this by clipping the triangle to each side of the rectangle successively. A new polygon must be created and stored after each clipping phase, to be sent on to be clipped against the next edge of the rectangle.

My question is this: can we take advantage of the recursive nature of the algorithm to avoid storing these (four) temporary polygons? Once a vertex has been clipped to one side, can we send it straight to the next clipping phase? Below is the logic I have developed thus far. It processes each line of the triangle separately by clipping against the boundaries in the following order:

[source lang="cpp"] Top -> Bottom -> Left -> Right -> Output[/source]

Points that pass the final clipping phase (Right) are added to the output polygon.

It is currently incorrect. It cannot 'wrap' a triangle around a corner of the rectangle. I think I'm on the right track though. I would love some feedback

Here are the functions in pseudocode:

[source lang="cpp"]//Clip polygon master function. The clipping rectangle has previously been defined.void ClipPolygon(point p0, point p1, point p2){ ClipToTop(p0, p1); ClipToTop(p1, p2); ClipToTop(p2, p0);}//--------------------------------------------------------------------------------// Clip to top//--------------------------------------------------------------------------------ClipToTop(point previous, point current){ if (/*previous and current are both inside*/) { ClipToBottom(previous,current); return; } if (/*previous inside and current outside*/) { //find intersection: 'intersect' ClipToBottom(previous,intersect); return; } //If both outside: do nothing if (/*previous outside and current inside*/) { //find intersection: 'intersect' ClipToBottom(previous,intersect); ClipToBottom(intersect,current); return; }}//--------------------------------------------------------------------------------// Clip to bottom//--------------------------------------------------------------------------------ClipToBottom(point previous, point current){ if (/*previous and current are both inside*/) { ClipToLeft(previous,current); return; } if (/*previous inside and current outside*/) { //find intersection: 'intersect' ClipToLeft(previous,intersect); return; } //If both outside: do nothing if (/*previous outside and current inside*/) { //find intersection: 'intersect' ClipToLeft(previous,intersect); ClipToLeft(intersect,current); return; }}//--------------------------------------------------------------------------------// Clip to left//--------------------------------------------------------------------------------ClipToLeft(point previous, point current){ if (/*previous and current are both inside*/) { ClipToRight(previous,current); return; } if (/*previous inside and current outside*/) { //find intersection: 'intersect' ClipToRight(previous,intersect); return; } //If both outside: do nothing if (/*previous outside and current inside*/) { //find intersection: 'intersect' ClipToRight(previous,intersect); ClipToRight(intersect,current); return; }}//--------------------------------------------------------------------------------// Clip to Right//--------------------------------------------------------------------------------ClipToRight(point previous, point current){ if (/*previous and current are both inside*/) { //Add current to output polygon } if (/*previous inside and current outside*/) { //find intersection: 'intersect' //Add intersect to output polygon } //If both outside: do nothing if (/*previous outside and current inside*/) { //find intersection: 'intersect' //Add intersect to output polygon //Add current to output polygon }}[/source]

For simplicity, consider the case of clipping a triangle to a rectangle. The Sutherland-Hodgman algorithm achieves this by clipping the triangle to each side of the rectangle successively. A new polygon must be created and stored after each clipping phase, to be sent on to be clipped against the next edge of the rectangle.

My question is this: can we take advantage of the recursive nature of the algorithm to avoid storing these (four) temporary polygons? Once a vertex has been clipped to one side, can we send it straight to the next clipping phase? Below is the logic I have developed thus far. It processes each line of the triangle separately by clipping against the boundaries in the following order:

[source lang="cpp"] Top -> Bottom -> Left -> Right -> Output[/source]

Points that pass the final clipping phase (Right) are added to the output polygon.

It is currently incorrect. It cannot 'wrap' a triangle around a corner of the rectangle. I think I'm on the right track though. I would love some feedback

Here are the functions in pseudocode:

[source lang="cpp"]//Clip polygon master function. The clipping rectangle has previously been defined.void ClipPolygon(point p0, point p1, point p2){ ClipToTop(p0, p1); ClipToTop(p1, p2); ClipToTop(p2, p0);}//--------------------------------------------------------------------------------// Clip to top//--------------------------------------------------------------------------------ClipToTop(point previous, point current){ if (/*previous and current are both inside*/) { ClipToBottom(previous,current); return; } if (/*previous inside and current outside*/) { //find intersection: 'intersect' ClipToBottom(previous,intersect); return; } //If both outside: do nothing if (/*previous outside and current inside*/) { //find intersection: 'intersect' ClipToBottom(previous,intersect); ClipToBottom(intersect,current); return; }}//--------------------------------------------------------------------------------// Clip to bottom//--------------------------------------------------------------------------------ClipToBottom(point previous, point current){ if (/*previous and current are both inside*/) { ClipToLeft(previous,current); return; } if (/*previous inside and current outside*/) { //find intersection: 'intersect' ClipToLeft(previous,intersect); return; } //If both outside: do nothing if (/*previous outside and current inside*/) { //find intersection: 'intersect' ClipToLeft(previous,intersect); ClipToLeft(intersect,current); return; }}//--------------------------------------------------------------------------------// Clip to left//--------------------------------------------------------------------------------ClipToLeft(point previous, point current){ if (/*previous and current are both inside*/) { ClipToRight(previous,current); return; } if (/*previous inside and current outside*/) { //find intersection: 'intersect' ClipToRight(previous,intersect); return; } //If both outside: do nothing if (/*previous outside and current inside*/) { //find intersection: 'intersect' ClipToRight(previous,intersect); ClipToRight(intersect,current); return; }}//--------------------------------------------------------------------------------// Clip to Right//--------------------------------------------------------------------------------ClipToRight(point previous, point current){ if (/*previous and current are both inside*/) { //Add current to output polygon } if (/*previous inside and current outside*/) { //find intersection: 'intersect' //Add intersect to output polygon } //If both outside: do nothing if (/*previous outside and current inside*/) { //find intersection: 'intersect' //Add intersect to output polygon //Add current to output polygon }}[/source]