Parallel Polygon Clipping
Original Publication Date: 1994-May-01
Included in the Prior Art Database: 2005-Mar-27
Parallel Polygon Clipping
clipping" is the process of removing that portion of a
polygon that lies outside a region called the "clip region". Fig. 1
shows a polygon and Fig. 2 shows its clipped counterpart.
solutions for this problem are sequential .
Theoharis and Page  discuss control and data parallel versions of
the Sutherland-Hodgman clipping algorithm . The algorithms for
boolean operations on polygons in parallel  are more general and
do not optimize for polygon clipping to a clip region.
presented here is similar to the data parallel
version in  in that exploits data parallelism. However, we do
not use a parallelization of the Sutherland-Hodgman technique and our
algorithm is organized to exploit a greater degree of data
parallelism and achieves more streamlined computation with mimimum
algorithm is simpler to exposit for the 2D case we
first discuss the solution in 2D. We then present the extension to
2. ALGORITHM PRINCIPLE AND OUTLINE
of this paper the polygon is closed and simple,
i.e., it bounds a finite region and has no holes. Polygons with
holes are handled by treating each contour of the polygon separately.
The polygon is specified as a set of vertices P(0), P(1), ....,
P(n-2), P(n-1), where n is the number of vertices in the polygon.
The vertices of the polygon are specified such that the interior of
the polygon lies to the left of the edges formed by consecutive
vertices. Each vertex P(i) is specified by its location v(i) in a
suitable coordinate space.
Note 1: The
first vertex of the polygon will be copied as the
nth vertex to avoid addition and subtraction modulo n.
We assume a
Concurrent Read Exclusive Write (CREW) Parallel
Random Access Memory (PRAM) model of computation. The algorithm we
present is also well suited to the Single Instruction Multiple Data
(SIMD) parallel machines.
We will assume
that Np is the number of processors used and n
is the number of vertices in the polygon.
Like in many
graphics problems it is clear that data
parallelism can be exploited for the clipping problem. For example
the vertices or edges of the polygon may be distributed among the
processors and reasonable load balancing be achieved. Since new
vertices may be introduced due to clipping, the main problem with
this approach is that we need to determine where in the output
polygon should these new vertices be introduced. In addition, corner
vertices may need to be added to the output polygon at the
appropriate location. These tasks could be potentially sequential
because each processor requires the results of processors responsible
for other portions of the polygon.
need an efficient technique to facilitate a
processor working on one part...