Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!mailrus!cornell!uw-beaver!uoregon!markv
From: markv@uoregon.uoregon.edu (Mark VandeWettering)
Newsgroups: comp.graphics
Subject: Re: Ray tracing vs. Scanline algorithms
Message-ID: <2974@uoregon.uoregon.edu>
Date: 15 Oct 88 18:15:22 GMT
References: <3023@mipos3.intel.com>
Reply-To: markv@drizzle.UUCP (Mark VandeWettering)
Distribution: na
Organization: University of Oregon, Computer Science, Eugene OR
Lines: 47

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