Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!pt.cs.cmu.edu!f.gp.cs.cmu.edu!mleone
From: mleone@f.gp.cs.cmu.edu (Mark Leone)
Newsgroups: comp.sys.amiga
Subject: Re: Clipping
Message-ID: <8003@pt.cs.cmu.edu>
Date: 15 Feb 90 17:39:48 GMT
References: <11230@baldrick.udel.EDU>
Organization: Carnegie-Mellon University, CS/RI
Lines: 65

In article <11230@baldrick.udel.EDU> 1LENDL%EDVZ.UNI-SALZBURG.ADA.AT@cunyvm.cuny.edu writes:
>I'm searching for a *FAST* clipping algorithm, because I'm writing
>an animated Vektorgraphic in assembler, and I want to clip all lines
>which go out of the screen :
>
>For example :
>
>   Such a line          Should be Clipped to :
>         \
>   _______\______            ______________
>   I       \    I            I       \    I
>   I        \   I            I        \   I
>   I         \  I            I         \  I
>   I          \ I            I          \ I
>   ------------\-            --------------
>                \

Here's an easy and fast clipping algorithm from Newman & Sproull,
_Principles of Interactive Computer Graphics_.  The algorithm was
invented by Cohen & Sutherland.

The basic idea is to use a bit-encoding to categorize the positions
of points relative to the screen (or window):

First bit:  point is to the left of the left-hand side of the screen.
Second bit: point is to the right of the right-hand side of the screen.
Third bit:  point is below the bottom edge of the screen.
Fourth bit: point is above the top edge of the screen.

Obviously, all visible points have the encoding 0000.  The other
possible encodings are as follows:

                 |        |
           1001  |  1000  |  1010
                 |        |
          -------|--------|--------
                 |(screen)|        
           0001  |  0000  |  0010
                 |        |      
          -------|--------|--------
                 |        |        
           0101  |  0100  |  0110
                 |        |     

It's easy write a function that, given a point, returns the
appropriate four-bit encoding.

Now, for the algorithm: Given a line segment, compute the encodings of
the endpoints.  Check whether both endpoints are visible (codes are
both 0000).  If so, display the line.  If not, compute the bitwise
"and" of the two encodings.  If this value is NON-ZERO, the whole line
is INVISIBLE.  

Otherwise, part of the line may be visible.  Find the coordinates of
the point where the line intersects the "tic-tac-toe" grid above.  (It
may intersect the grid several times; just choose any point of
intersection).  Discard the part of the line that is invisible, and
recursively apply the algorithm to the remainder of the line.  (The
algorithm gets slightly faster if you intelligently choose which part
of the line to ignore).  Pretty simple!

--
Mark R. Leone  <mleone@cs.cmu.edu>              "Don't just do something,
Computer Science, Carnegie Mellon University     sit there!"
Pittsburgh, PA 15213