Board index Graphics Algorithms

Best source of Weiler(80) polygon clipper?

Best source of Weiler(80) polygon clipper?

Post by Jens Alfk » Fri, 28 Jan 1994 09:04:08



OK, the Apple library [Imagine that! I went to a library to look for
algorithms!] finally got me a copy of Weiler's 1980 paper describing his
polygon clipper. Many people have implemented this algorithm, but the paper
itself is surprisingly short and sketchy on the details. Is there a longer,
more in-depth source, or has everyone had to fill in the details themselves?
(He has a master's thesis from '77, but it describes the earlier
Weiler/Atherton algorithm.)

For those who care, I have given up completely on Vatti's half-baked clipper
and will be implementing Kilgour(87) instead. But I want a good description
of Weiler(80) for my records.

                                    This sound has no waves
--Jens Alfke                        This sound has no waves

            .apple.com              Through fog and other grey things
                                                  --Dog Faced Hermans

 
 
 
Top

1. Another Polygon Clipper (Weiler '80)

I've discovered another interesting looking polygon clipper -- the Weiler
algorithm from 1980. It's discussed in the latest edition of "Computer
Graphics Principles and Practice" (Foley, Van Dam, et al) pp.937-945.

This one looks pretty nice. Like the earlier Weiler-Atherton ('77) algorithm,
it computes the intersection, union or difference of multiple arbitrary
polygons which may be concave or have multiple contours. I don't believe it
handles self-intersection.

It's not scanline-based the way the Vatti algorithm is (having implemented
Vatti and struggled to overcome problems with horizontal edges, I'm pretty
disillusioned with the scanline-based approach.)

What's more, unlike Weiler-Atherton, it actually addresses unpleasant
real-world situations like coincident vertices and overlapping edges. (I'm
still struggling to get Vatti's algorithm to handle these; despite his
articles title "A Generic Solution To Polygon Clipping", his algorithm dies
horribly in these situations that occur all the time with real-world data.)

On the other hand, it does look like the most complex (and possibly slow)
algorithm I've seen to date.

I'm posting this for the benefit of anyone else out there interested in
polygon clippers, and on the off chance that someone has experience with this
algorithm and can give their impression of it...

                                    This sound has no waves
--Jens Alfke                        This sound has no waves

            .apple.com              Through fog and other grey things
                                                  --Dog Faced Hermans

2. SoXtGLWidget && glXMakeCurrent

3. Weiler-Atherton polygon clipper

4. New to Max 2.5 and already stuck in chapter 2 on a goblet!

5. Weiler-Atherton Polygon Clipper??

6. (no subject)

7. Weiler polygon clipping algorithm source sought

8. Ventura Bublisher export??? - vip-io2.zip [09/22]

9. SOURCES REQUESTED: Beam tracing, Weiler HSR / polygon clipping

10. Source code of Weiler-Atherton polygon clipping algorithm?

11. Two pass polygon clipper source for download.

12. 2d polygon clipper -- source?

13. Wanted: Source for Vatti (or other) polygon clipper


All times are UTC
Board index