hansen@acl.lanl.gov (Charles D. Hansen) (09/28/90)
Does anyone know of a public domain hidden line removal suitable for plotters (yes, it's still 1964 here)? All the ones I have are either for rasters (use scan-line coherence) or assume regularity in the X-Y plane. I'd like one based on Atherton's algorithm or something like that. Thanks, Chuck Hansen hansen@lanl.gov
jroth@allvax.dec.com (Jim Roth) (09/30/90)
In article <HANSEN.90Sep28075502@koala.acl.lanl.gov>, hansen@acl.lanl.gov (Charles D. Hansen) writes... > >Does anyone know of a public domain hidden line removal suitable for >plotters (yes, it's still 1964 here)? All the ones I have are either >for rasters (use scan-line coherence) or assume regularity in the X-Y >plane. I'd like one based on Atherton's algorithm or something like that. There's a NASA algorithm, written by David Hedgley and available from COSMIC. I don't have the report number off the top of my head, but it's titled "A general solution to the hidden line problem". Since you mention that it's still the 60's there you won't mind that it's written in FORTRAN :-) I wrote a hidden line routine some time ago while studying various alternatives but it's not public domain. What I found worked very well was to preprocess the polygons into a spatial tree and then do the hidden line procesing against this tree; this is very general, reasonably simple, and handles free-standing edges and other generalities. The NASA routine uses instead an adaptively selected set of arrays to store the polygon descriptions, so that small polygons get put in "cells" which can be quickly indexed by screen location while large polygons are put in arrays sorted by either X or Y which also gives reasonably fast access. My dissatisfaction with this idea led me to do a more general tree (somewhat like a KD tree), which is actually simpler. FORTRAN limits one's thinking against recursion and pointers, apparently. I have not tried the cookie-cutter (Weiler-Atherton) algorithm. There is also a paperback book on graphics from Wiley that has a C program for hidden line elimination that looks useable, by an author with a Dutch name that I forget. You'll find that in software if you do have a raster, that a Z buffer algorithm is probably the fastest approach in practice. Calligraphic approaches do have the advantage of high accuracy, not limited to raster resolution. Note that Newell-Sancha also is also limited to raster precision, because it uses painters as its backend. Let me know if you want more exact citations to the book and COSMIC algorithm; I don't have them handy right now. - Jim