Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Parallel Polygon Clipping

IP.com Disclosure Number: IPCOM000112456D
Original Publication Date: 1994-May-01
Included in the Prior Art Database: 2005-Mar-27

Publishing Venue

IBM

Related People

Narayanaswami, C: AUTHOR

Abstract

1. INTRODUCTION

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 15% of the total text.

Parallel Polygon Clipping

1.  INTRODUCTION

      "Polygon 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.

      Most known solutions for this problem are sequential [2].
Theoharis and Page [4]  discuss control and data parallel versions of
the Sutherland-Hodgman clipping algorithm [2].  The algorithms for
boolean operations on polygons in parallel [3]  are more general and
do not optimize for polygon clipping to a clip region.

      The algorithm presented here is similar to the data parallel
version in [4]  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
synchronization overheads.

      Since the algorithm is simpler to exposit for the 2D case we
first discuss the solution in 2D.  We then present the extension to
3D.

2.  ALGORITHM PRINCIPLE AND OUTLINE

2.1 ASSUMPTIONS

      For purpose 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.

2.2.  PRINCIPLES

      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.

      Therefore, we need an efficient technique to facilitate a
processor working on one part...