gilles@cannes.Sun.COM (Patrick-Gilles Maillot) (04/10/90)
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
jcs@crash.cts.com (John Schultz) (04/11/90)
The fast clipper (FC) 2D line clipper algorithm uses line encoding
as opposed to end point encoding as with the Cohen-Sutherland (CS)
method, or parametric methods of Liang-Barsky and Cyrus-Beck. The
Sobkow-Pospisil-Yang paper shows benchmarks where the FC clipper
is over twice as fast as the CS algorithm. The parametric methods are
much slower. The paper has a source code listing in C, which has a few
errors. These errors were in the #define statements for clipping to
screen edges. A divide and a subtract were left out:
as published:
#define ClipPTop (*Px) = (*Px) + ((*Qx) - (*Px)) * (YTop - (*Py))
should read:
#define ClipPTop (*Px) = (*Px) + ((*Qx) - (*Px)) * (YTop - (*Py)) /
((*Qy) - (*Py))
Once these errors were corrected, the algorithm worked properly.
At the time I was experimenting with clipping, I was using a Modula-2
compiler, so my HLL source is in modula-2. The latest version is in
68000 assembly, linked to C test code.
The original paper on the FC algorithm was published in
Computers & Graphics Vol. 11, No. 4, pp. 459-467, 1987
Printed in Great Britain. The publisher was Pergamon Journals Ltd.
I also heard it was published in ACM, but don't know when or where.
Authors of the paper:
Mark S. Sobkow, Paul Pospisil, and Yee-Hong Yang (to whom
correspondence should be addressed),
Department of Computational Science, University of Saskatchewan, Saskatoon,
Saskatchewan, Canada S7N 0W0.
I never tested my code against any other algorithms, so I'm curious to
see if it is twice as fast as SC. Please let me know of any further
optimizations. (Check comp.sources.misc for the source)
John