Previous: clppl3 Up: ../plot79_c.html Next: clpsh3
SUBROUTINE CLPSH2 (NEDGE, NORMAL, PIPE, XOLD, INCX, YOLD, INCY,
X NOLD, XNEW, YNEW, NNEW, MAXNEW)
C$ (2-D Sutherland-Hodgman Polygon Clip to General Polygon)
C$ Clip a 2-D polygon to the visible part of a general polygon
C$ defined by normal vectors from each of its edges. The
C$ output of the clip is a new polygon. The arguments are:
C$
C$ NEDGE..........Number of clipping edges. The dimensional
C$ dependencies are NORMAL(3,NEDGE), and
C$ PIPE(9,NEDGE).
C$ NORMAL(*,*)....REAL array of normals (A,B,C) defining
C$ equations of clipping edges Ax + By + C = 0.
C$ The normals point to the visible side of the
C$ edges. NORMAL(*,K) is the normal for edge
C$ k.
C$ PIPE(*,*)......REAL working array with 9*NEDGE entries.
C$ XOLD(*)........REAL array of x coordinates of polygon
C$ vertices.
C$ INCX...........Increment between successive coordinates in
C$ XOLD(*) (normally 1).
C$ YOLD(*)........REAL array of y coordinates of polygon
C$ vertices.
C$ INCY...........Increment between successive coordinates in
C$ YOLD(*) (normally 1).
C$ NOLD...........Number of polygon vertices. Vertex NOLD is
C$ implicitly connected to vertex 1 to close
C$ the polygon.
C$
C$ The output arguments are:
C$
C$ XNEW(*)........x coordinates of clipped polygon vertices.
C$ YNEW(*)........y coordinates of clipped polygon vertices.
C$ NNEW...........Number of clipped polygon vertices. Vertex
C$ NNEW is implicitly connected to vertex 1 to
C$ close the polygon. NNEW will usually be
C$ less than NOLD, but it may be as large as
C$ (3*NOLD+1)/2. This case arises when
C$ adjacent vertices lie on opposite sides of
C$ the clipping edge, with NOLD/2 visible and
C$ (NOLD+1)/2 hidden; each hidden vertex
C$ contributes two new vertices on the clipping
C$ edge, giving a total of NOLD+1 new vertices,
C$ which added to the NOLD/2 old ones is
C$ (3*NOLD+1)/2.
C$ MAXNEW.........Maximum number of vertex entries available
C$ in XNEW(*) and YNEW(*). NNEW is not
C$ permitted to exceed this value, and
C$ additional vertices simply overwrite the
C$ last one.
C$
C$ If an increment INCX or INCY is negative, the starting
C$ vertex is taken as (1-NOLD)*INC + 1 instead of 1, so that
C$ the array is stepped through in reverse order.
C$
C$ The algorithm is based on the reentrant polygon clipper
C$ originally proposed by I.E. Sutherland and G.W. Hodgman,
C$ "Reentrant Polygon Clipping", Comm. ACM 17, 32-42 (1974).
C$
C$ The effect of this routine can be equivalently be obtained
C$ by calling the single edge clipper, CLPPL2, repeatedly for
C$ each successive clipping edge. This would require
C$ intermediate storage for at least 2 extra polygons if the
C$ input polygon is to be preserved. The advantage of the
C$ Sutherland-Hodgman algorithm is that as soon as a line
C$ segment is output from the clipping against one edge, it is
C$ immediately passed on for clipping against the next edge.
C$ Intermediate storage is therefore limited to three vertices
C$ (the line segment endpoints and the saved initial vertex
C$ required to close the polygon) at each clipping stage, plus
C$ two dot products, and two flags which are easily stored in
C$ a single word. Thus for 2-D points, 9 working locations
C$ are required for each clipping edge. The dot product
C$ storage could be eliminated at the expense of additional
C$ calculation, but is hardly excessive considering that few
C$ applications require more than 6 clipping edges.
C$
C$ The algorithm is essentially a series of clippers running
C$ in parallel and communicating with their neighbors via a
C$ pipeline (in Unix terminology). The output of one is the
C$ input to the next, and if the next stage consumes its input
C$ fast enough, its input buffer need never hold more than two
C$ vertices. This would be straightforward to implement in a
C$ language supporting coroutines, but since FORTRAN does not
C$ have this facility, we must program it explicitly.
C$ Obviously, if the clippers were actually operating in
C$ independently and in parallel (apart from occasional
C$ waiting on input), the pipeline buffers would have to be
C$ large enough to hold a complete polygon in the worst case.
C$ The trick (and the complication) is to superimpose a
C$ controller which prevents any one process from outputting
C$ more than 2 vertices to its neighbor process.
C$
C$ The controller is implemented as a loop with initialize,
C$ process, and terminate steps, where each cycle through the
C$ loop gives control to just one clipping process.
C$ Initialization is just the trivial copying of input from
C$ the pipeline into local variables. The process step is
C$ also simple; it clips the current line segment against the
C$ current clipping edge and outputs 0 or 1 points to the next
C$ stage, consuming exactly one vertex from its input buffer
C$ to do so. The difficult part is the termination stage
C$ which acts as the pipeline controller to select the next
C$ stage, and the comments in the procedure below describe the
C$ steps which must be taken to do this.
C$ (18-DEC-82)