Sutherland–Hodgman algorithm: Difference between revisions

Revision as of 09:41, 24 June 2009

Revision as of 10:11, 24 June 2009

Line 12:

==Pseudo Code==

Given a specificlist of edges in a clip planepolygon, and ana arraylist containing theof vertices ofin a singlesubject polygon, the following procedure clips the subject polygon against the planeclip polygon.

List outputList = subjectPolygon;

arrayLength = array.size

for (Edge clipEdge in clipPolygon) do

vertex S = array[ arrayLength - 1 ]

for( j = 0,List j < arrayLength, jinputList = j+1 )outputList;

outputList.clear();

{

vertexPoint PS = array[ j ]inputList.last;

iffor (Point PE is inside clip_planein inputList) do

if (E inside clipEdge) then

{

if( (S is not inside clip_plane clipEdge) then

Output( ComputeIntersection( P, S, clip_plane ) outputList.add(ComputeIntersection(S,E,clipEdge));

{

Output(end ComputeIntersection( S, P, clip_plane ) )if

} outputList.add(E);

Outputelse if (S Pinside clipEdge) then

outputList.add(ComputeIntersection(S,E,clipEdge));

}

else if( S isend inside clip_plane )if

{ S = E;

{done

Output( ComputeIntersection( P, S, clip_plane ) )

}done

S = P

}

The vertices of the clipped polygon are to be found in ''outputList'' when the algorithm terminates. Note that a point is defined as being ''inside'' an edge if it lies on the same side of the edge as the remainder of the polygon. If the vertices of the clip polygon are consistently listed in a clockwise direction, then this is equivalent to testing whether the point lies to the right of the line, and can be implemented simply by using a [[dot product]].

'''Output''' and '''ComputeIntersection''' are functions that have not been implemented here for ease of readability (and they are not very complex).

''ComputeIntersection'' is a trivial function, omitted here for clarity, which returns the intersection of a line segment and an infinite edge. Note that it is only called if such an intersection is known to exist, and hence can simply treat both lines as being infinitely long.

'''Output''' is generally some function or code that adds vertices to an array.

'''ComputeIntersection''' finds the intersection points of a line segment and a clip plane and returns that values (vertices) in order from S to P.

==See also==