rnewton@mipos3.intel.com (Richard Newton) (10/14/88)
Recently, the algorithms discussed in this group have dealt with ray
tracing. In college, my senior project was to add some features (transparency,
polygon-splitting, back-face removal, etc.) to a graphics program using a
scan-line algorithm.
Does anybody actually use scan-line algorithms (or anything else, other
than ray-tracing) to do actual graphics work? The big advantages of ray
tracing is the ease of coding, but it is computationally expensive. The
most important part of a ray tracer is the intersection algorithm; is
there now an algorithm that makes ray-tracing as fast as other algorithms?
I've been considering rewriting the scanline program in C (it is in PASCAL;
ugh!), but since all discussion on the net seems to be about ray-tracing,
I'm wondering if I should bother.
I've never done any benchmarking of different algorithms; any info out there?
--
Richard Newton II ...!{decwrl|hplabs!oliveb|amd}!intelca!mipos3!rnewton
Intel Corp., 2625 Walsh Ave, Mail Stop SC4-37, Santa Clara, CA 95052-8122markv@uoregon.uoregon.edu (Mark VandeWettering) (10/16/88)
In article <3023@mipos3.intel.com> rnewton@mipos3.UUCP (Richard Newton II ~) writes: > Recently, the algorithms discussed in this group have dealt with ray >tracing. In college, my senior project was to add some features (transparency, >polygon-splitting, back-face removal, etc.) to a graphics program using a >scan-line algorithm. The problem with most traditional scanline techniques is their lack of good global illumination model: they don't handle reflections and refractions in a convincing manner. I have yet to here of a good scanline algorithm for the insertion of shadows which is "immune" to numerical instabilities and inaccuracies. Raytracers are moderately simple to code. There is no question that faster rendering methods exist, but "you get what you pay for". > Does anybody actually use scan-line algorithms (or anything else, other >than ray-tracing) to do actual graphics work? The big advantages of ray >tracing is the ease of coding, but it is computationally expensive. The >most important part of a ray tracer is the intersection algorithm; is >there now an algorithm that makes ray-tracing as fast as other algorithms? >I've been considering rewriting the scanline program in C (it is in PASCAL; >ugh!), but since all discussion on the net seems to be about ray-tracing, >I'm wondering if I should bother. Most hierarchy algorithms allow a "fast" O(logn) search for intersecting objects. In practice, this isn't too bad. For instance, in my raytracer, about 40% of the time is spent locating the next object, and mine could probably optimized by some loop unrolling. Octree methods are typically much less (I think James Arvo quoted < 20%). My advice to anyone who is coding these things up "for fun" is to put some effort into writing a good raytracer. Mine was alot of fun, mainly because raytracing is simple enough to get right. Or alternatively try something to do radiosity. The 88 Siggraph has a paper from the group at Cornell on turning their radiosity into a fast linear algorithm. It make MUCH more sense than the original formulation of the radiosity algorithm. I think radiosity will be my next project.... All I need is time... *sigh* mark vandewettering
jevans@cpsc.ucalgary.ca (David Jevans) (10/19/88)
At the University of Calgary we have used an abuffer scanline renderer
for several years. Before that we used a pretty much bog standard
zbuffer algorithm. Scanline algorithms are used because they are
usually faster than things like ray tracing. The reason people use
raytracing is not for its ease of coding. In fact, to write a fast
ray tracer requires a lot of thought, research, and often some
difficult coding.
Ray tracing is used primarily to get shadows, reflections and refractions.
Of course these can be faked pretty well for scanline algorithms though
the use of light/shadow buffers and environment maps, although it is my
opinion that ray tracing is more elegant and can be made faster than
a scanline method which uses all these tricks.
Recently I have been working on new spatial subdivision methods to
speed up ray tracing and I have several test images which do not take
much longer to ray trace than to render with our abuffer renderer. These
images consist of large(?) numbers of polygons ( > 20000) and are rendered
with shadows and multiple light sources while the abuffer renderer has
no shadows at all.
You will get varying arguments from everyone. I think scanline methods
are probably still faster for generating images with textures and that
use environment maps, although you will need to ray trace to get nice
refractions. Of course my big argument for ray tracing is that it
lends itself to parallelization so easily. Try arguing with a dedicated
scanline freak as to the usefullness of this though...
"we're dancing down church aisles, dancing on holy books..."
David Jevans, U of Calgary Computer Science, Calgary AB T2N 1N4 Canada
uucp: ...{ubc-cs,utai,alberta}!calgary!jevans
David Jevans, U of Calgary Computer Science, Calgary AB T2N 1N4 Canada
uucp: ...{ubc-cs,utai,alberta}!calgary!jevans