Previous: clpsh2 Up: ../plot79_c.html Next: clptr
SUBROUTINE CLPSH3 (NPLANE, NORMAL, PIPE, XOLD, INCX, YOLD, INCY,
X ZOLD, INCZ, NOLD, XNEW, YNEW, ZNEW, NNEW, MAXNEW)
C$ (3-D Sutherland-Hodgman Polygon Clip to General Polyhedron)
C$ Clip a 3-D polygon to the visible part of a general
C$ polyhedron defined by normal vectors from each of its
C$ faces. The output of the clip is a new polygon. The
C$ arguments are:
C$
C$ NPLANE.........Number of clipping planes. The dimensional
C$ dependencies are NORMAL(4,NPLANE), and
C$ PIPE(12,NPLANE).
C$ NORMAL(*,*)....REAL array of normals (A,B,C,D) defining
C$ equations of clipping planes Ax + By + Cz +
C$ D = 0. The normals point to the visible
C$ side of the planes. NORMAL(*,K) is the
C$ normal for plane k.
C$ PIPE(*,*)......REAL working array with 12*NPLANE 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$ ZOLD(*)........REAL array of z coordinates of polygon
C$ vertices.
C$ INCZ...........Increment between successive coordinates in
C$ ZOLD(*) (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$ ZNEW(*)........z 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 plane, with NOLD/2 visible and
C$ (NOLD+1)/2 hidden; each hidden vertex
C$ contributes two new vertices on the clipping
C$ plane, giving a total of NOLD+1 new
C$ vertices, which added to the NOLD/2 old ones
C$ is (3*NOLD+1)/2.
C$ MAXNEW.........Maximum number of vertex entries available
C$ in XNEW(*), YNEW(*), and ZNEW(*). NNEW is
C$ not permitted to exceed this value, and
C$ additional vertices simply overwrite the
C$ last one.
C$
C$ If an increment INCX, INCY, or INCZ is negative, the
C$ starting vertex is taken as (1-NOLD)*INC + 1 instead of 1,
C$ so that 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 plane clipper, CLPPL3, repeatedly for
C$ each successive clipping plane. 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 plane, it
C$ is immediately passed on for clipping against the next
C$ plane. Intermediate storage is therefore limited to three
C$ vertices (the line segment endpoints and the saved initial
C$ vertex required to close the polygon) at each clipping
C$ stage, plus two dot products, and two flags which are
C$ easily stored in a single word. Thus for 3-D points, 12
C$ working locations are required for each clipping plane.
C$ The dot product storage could be eliminated at the expense
C$ of additional calculation, but is hardly excessive
C$ considering that few applications require more than 6
C$ clipping planes.
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 plane and outputs 0 or 1 points to the
C$ next stage, consuming exactly one vertex from its input
C$ buffer to do so. The difficult part is the termination
C$ stage which acts as the pipeline controller to select the
C$ next stage, and the comments in the procedure below
C$ describe the steps which must be taken to do this.
C$ (18-DEC-82)