Browse Prior Art Database

Efficient Clipping Method

IP.com Disclosure Number: IPCOM000104791D
Original Publication Date: 1993-Jun-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 4 page(s) / 69K

Publishing Venue

IBM

Related People

Murihashi, S: AUTHOR [+3]

Abstract

This invention relates to the method of a clipping system on two - dimensional window system.

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

Efficient Clipping Method

      This invention relates to the method of a clipping system on
two - dimensional window system.

      Graphic input-output devices which exclude line-segments
outside a given rectangle window are called a clipping device.  Prior
clipping technology used the Cohen-Sutherland Algorithm.  It needs 8
coordinate comparisons for each line-segment, as shown in Figure 1,
to encode the allocation of extreme points against the window.  Then,
using these codes, it identifies whether the line-segment will be
displayed or not.

      This invention improves upon the Cohen-Sutherland Algorithm by
rejecting un-needed comparison.

      Let's suppose that the line-segment (sx,sy)-(fx,fy) and the
rectangular window(xmin,xmax,ymin,ymax) are given.  If  sx < xmin is
true, sx > xmax  is always false, and this latter comparison is not
neccesary.

      In another case, if sx < xmin is true, and if fx < xmin is
true, then we can tell that the given line-segment should be rejected
at this point.

      Also, if given line-segments are consecutive, we can suppose
that the code of a line-segment will be the same, or similar.  So, by
changing comparison order dynamically, we can lessen un-needed
comparison.

      This algorithm uses 4 Evaluation Trees as shown in Figure 2.
Eval-tree X and X', Y and Y', are called pair-tree.  By using one of
8 permutations of (X, X', Y, Y'), which are (X-Y),(X-Y'),(X'-Y),
(X'-Y'),(Y-X),(Y-X'),(Y'-X)...