Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!newstop!sun!cannes!gilles
From: gilles@cannes.Sun.COM (Patrick-Gilles Maillot)
Newsgroups: comp.graphics
Subject: Re: 2D line clippers
Keywords: 2D line clipping
Message-ID: <134185@sun.Eng.Sun.COM>
Date: 9 Apr 90 20:29:37 GMT
Sender: news@sun.Eng.Sun.COM
Reply-To: gilles@sun.UUCP (Patrick-Gilles Maillot)
Organization: Sun Microsystems, Mountain View
Lines: 28


Hi Netland,

There seems to be a lot of mail about 2D line clippers.

The Liang-Barsky algorithm for 2D line clipping has been published in
ACM TOG, vol 3, No 1 January 1984. 

It is based on the parametric equation of a line segment. Finding the
parameter at the intersection point gives the intersection coordinates.

This method is (said by the authors to be) faster than the good old CS
(Cohen-Sutherland). But, for sure the CS is faster when the points are
inside the clip region, i.e. for trival acceptance/rejection cases. It
may be not true with certain CPUs, or when the algorithms are casted to
HW.

There are lots of other methods:

SPY: <I don't have access to any ref on the technical report>
Cyrus-Beck: 2 and 3 dimensional clipping. Comp&Graphics, Vol 3 No 1, 1978.
Nicholl, Nicholl & Robin: Computer graphics, Vol 21, No 4, July 87.

A collection of algorithms for clipping 1 to N dim lines (and other
graphic goodies) can be found (sorry, in French) in my PhD Thesis,
(send mail if interested).

-Patrick