Ray Tracing News

"Light Makes Right"

March 26, 1988

Volume 1, Number 5

Compiled by Eric Haines erich@acm.org . Opinions expressed are mine.

All contents are copyright (c) 1988, all rights reserved by the individual authors

Archive locations: anonymous FTP at ftp://ftp-graphics.stanford.edu/pub/Graphics/RTNews/,
wuarchive.wustl.edu:/graphics/graphics/RTNews, and many others.

You may also want to check out the Ray Tracing News issue guide and the ray tracing FAQ.


Contents:


Introduction

Well, NCGA was pretty uninspiring, as it rapidly becomes more and more PC oriented. It was great to see people, though, and nice to escape the Ithaca snow and rain.

As far as ray tracing goes, a few companies announced products. The AT&T Pixel Machine now has two rendering packages, PICLIB and RAYLIB (these may be merged into one package someday - I would guess that separate development efforts caused the split [any comments, Leonard?]). With the addition of some sort of VM capability, this machine becomes pretty astounding in its ray tracing performance (in case you didn't get to SIGGRAPH last year, they had a demo of moving by mouse a shiny ball on top of the mandrill texture map: about a frame per second ray trace on a small part of the screen). HP announced its new graphics accelerator, the TurboSRX, and with it the eventual availability of a ray tracing and (the first!) radiosity package as an extension to their Starbase graphics library. Ardent and their Dore' package were sadly missing. Apollo was also noticeable for their non-appearance. Sun TAAC was there, showing off some ray traced pictures but seemingly not planning to release a ray tracer (the salesman claiming that whoever bought a TAAC would simply write their own). Stellar was there with their supercomputer workstation - interesting, but no ray-tracing in sight. Anyone else note anything of ray-tracing (or other) interest?

back to contents


Some Mailing List Changes and Additions

Changed address:

# Roman Kuchkuda
# Megatek
alias	roman_kuchkuda \
	hpfcrs!hpfcla!hplabs!ucbvax!ucsd!megatek!kuchkuda@rutgers.edu

New people:

I saw Gray at NCGA and got his email address. He worked on ray tracing at RPI and is at Cray:

# Gray Lorig - volumetric data rendering, sci-vi, and parallel & vector
#	architectures.
# Cray Research, Inc.
# 1333 Northland Drive
# Mendota Heights, MN  55120
# (612)-681-3645
alias	gray_lorig	hpfcrs!hpfcla!hplabs!gray%rhea.CRAY.COM@uc.msc.umn.edu

By way of introduction, this from Erik Jansen:

I visited the Helsinki University of Technology last week and found there a lot of ray tracing activities going on. They are even reviving their old EXCELL system (Markku Tamminen did a PhD work on a spatial index based on an adaptive binary space subdivision in '81-'82, I met him in '81 and '82 and we talked at these occasions about ray tracing and spatial subdivision. In his PhD thesis (1982) there is a ray tracing algorithm given for the EXCELL method (EXtendible CELL method). I decided to implement the algorithm for ray tracing polygon models. That implementation failed because I could only use our PDP-11 at that time and I could have about ten cells in internal memory - too less for effective coherence. The program spend 95% of its time on swapping. So far the history). I told them about the RT-news and they are very interested to receive it. I will mail them (Charles Woodward, Panu Rekola, e.o.) your address, so that they can introduce themselves to the others.

#
# Panu Rekola - spline intersection, illumination models, textures
# Helsinki University of Technology
# Laboratory of Information Processing Science
# Room Y229A
# SF-02150 Espoo
# Finland
#	pre@kiuas.hut.fi	(or pre@hutcs.hut.fi)
alias	panu_rekola	hpfcrs!hpfcla!hpda!uunet!mcvax!hutcs!pre

Panu Rekola writes:

I just received a message from Erik Jansen (Delft) in which he told me that you take care of a mailing list called "Ray Tracing News". (I already sent a message to Andrew Glassner on the same topic because Erik told me to contact him when he visited us some weeks ago.) Now, I would like to join the discussion; I promise to ask no stupid questions. I have previously worked here in a CAD project (where I wrote my MSc thesis on FEM elements) and since about a year I have been responsible of our graphics. Even though my experience in the field is quite short I suppose I have learned a lot while all people want to see their models in color and with glass etc., visualization has been the bottleneck in our CAD projects.

As an introduction to the critical members of the mailing list you could tell that I am a filter who read unstandard input from the models created by other people, manipulates the data with the normal graphics methods, and outpus images. The special features of our ray tracer are the EXCELL spatial directory (which has been optimized for ray tracing during the last few weeks), a new B-spline (and Bezier) algorithm, methods to display BR models with curved surfaces (even blend surfaces, although this part yet unfinished). The system will be semi-commercially used in a couple of companies soon (e.g. car and tableware industry).

back to contents


More on Shadow Testing, Efficiency, etc., by Jeff Goldsmith

(followup to Ohta/Goldsmith correspondence :)

From Jeff Goldsmith:

Sorry I haven't responded sooner, but movie-making has taken up all my time recently.

With respect to pre-sorting, etc. It is important to note that the preprocessing time must be MUCH smaller than the typical rendering time. So far this has been true, and even more so for animation.

O(n) in my writing (explicitly in print) means linear in the number of objects in the scene. Obviously, it is quite likely that the asymptotic time complexity (a.t.c.) of any ray tracing algorithm will be different for the number of rays. Excluding ray coherence methods and hybrid z-buffer/ray tracing methods, the current a.t.c. is O(n) in the number of rays for ray tracing. Actually, I think it is the same for these other methods because the hybrid methods just eliminate some of the rays from consideration and leave the rest to be just as hard and the coherence methods don't eliminate more than, say, 1/2 of the rays, I think. In any event, for the a.t.c. to become sub-linear, there can be no such fraction, right?

About space tracing: I think that I said that finding the closest intersection is an O(log n) problem. I agree, though, that that statement is not completely correct. Bucket sort methods, for example, can reduce the a.t.c. below log n. Also, global sort time (preprocessing) can distribute some of the computation across all rays, which can reduce the time complexity. What about the subdivide on the fly methods? (e.g.: Arvo and Kirk) How do they fit in the scheme of things? I think your evaluation of the space tracing methods is correct, though the space complexity becomes important here, too. Also, given a "full" space (like Fujimoto's demos,) the time complexity is smaller. That leads to the question, "What if the time complexity of an algorithm depends on its input data?" Standard procedure is to evaluate "worst case" complexity, but we are probably interested in "average case" or more likely, "typical case." Also, it would be worthwhile and interesting to understand which algorithms do better with which type of data. We need to quantify this answer when trying to find good hybrid schemes. (The next generation?)

At SIGGRAPH '87 we had a round table and each answered the question, "what would you like to see happen to ray tracing in the next year." My choice was to see something proven about ray tracing. It sounds like you are interested in that too. Any takers?

back to contents


More Comments on Tight Fitting Octrees for Quadrics, by Jeff Goldsmith

{followup to Ruud Waij's question last issue}

previous discussion of topic

With respect to the conversation about octree testing, I've only done one try at that. I just tested 9 points against the implicit representation of the surface. (8 corners and the middle.) I didn't use it for ray tracing (I even forget what for) but I suspect that antialiasing will hide most errors generated that way.

Jim Blinn came up with a clever way to do edges and minima/ maxima of quadric surfaces using (surprise) homogeneous coordinates. I don't think there ever was a real paper out of it, but he published a tutorial paper in the Siggraph '84 tutorial notes on "The Mathematics of Computer Graphics." That technique works for any quadric surface (cylinders aren't bounded, though) under any homogeneous transform (including perspective!) He also talks about how to render these things using his method. I tried it; it works great and is incredibly fast. I didn't implement many of his optimizations and can draw a texture mapped cylinder (no end caps) that fills the screen (512x512) on a VAX 780 in under a minute.

As to how this applies to ray tracing, he gives a method for finding the silhouette of a quadric as well as minima and maxima. It allows for easy use of forward differencing, so should be fast enough to "render" quadrics into an octree.

Bob Conley did a volume-oriented ray tracer for his thesis. I don't remember the details, but there'll be a long note about it that I'll pass on. He mentions that his code can do index of refraction varying over position. He uses a grid technique similar to Fujimoto's.

back to contents


Linear-time Voxel Walking for Octrees, by Jim Arvo

Just when you thought we had moved from octrees on to other things... This just occurred to me yesterday. (Actually, that was several days ago. This mail got bounced back to me twice now. More e-mail gremlins I guess.)

Linear-time Voxel Walking for Octrees

Here is a new way to attack the problem of "voxel walking" in octrees (at least I think it's new). By voxel walking I mean identifying the successive voxels along the path of a ray. This is more for theoretical interest than anything else, though the algorithm described below may actually be practical in some situations. I make no claims about the practicality, however, and stick to theoretical time complexity for the most part.

For this discussion assume that we have recursively subdivided a cubical volume of space into a collection of equal-sized voxels using a BSP tree -- i.e. each level imposes a single axis-orthogonal partitioning plane. The algorithm is much easier to describe using BSP trees, and from the point of view of computational complexity, there is basically no difference between BSP trees and octrees. Also, assuming that the subdivision has been carried out to uniform depth throughout simplifies the discussion, but is by no means a prerequisite. This would defeat the whole purpose because we all know how to efficiently walk the voxels along a ray in the context of uniform subdivision -- i.e. use a 3DDDA.

Assuming that the leaf nodes form an NxNxN array of voxels, any given ray will pierce at most O(N) voxels. The actual bound is something like 3N, but the point is that it's linear in N. Now, suppose that we use a "re-traversal" technique to move from one voxel to the next along the ray. That is, we create a point that is guaranteed to lie within the next voxel and then traverse the hierarchy from the root node until we find the leaf node, or voxel, containing this point. This requires O( log N ) operations. In real life this is quite insignificant, but here we are talking about the actual time complexity. Therefore, in the worst case situation of following a ray through O( N ) voxels, the "re-traversal" scheme requires O( N log N ) operations just to do the "voxel walking." Assuming that there is an upper bound on the number of objects in any voxel (i.e. independent of N), this is also the worst case time complexity for intersecting a ray with the environment.

In this note I propose a new "voxel walking" algorithm for octrees (call it the "partitioning" algorithm for now) which has a worst case time complexity of O( N ) under the conditions outlined above. In the best case of finding a hit "right away" (after O(1) voxels), both "re-traversal" and "partitioning" have a time complexity of O( log N ). That is:

		    BEST CASE: O(1) voxels    WORST CASE: O(N) voxels
		    searched before a hit.    searched before a hit.
		  +---------------------------------------------------+
		  |                                                   |
  Re-traveral     |     O( log N )               O( N Log N )         |
		  |                                                   |
  Partitioning    |     O( log N )               O( N )               |
		  |                                                   |
		  +---------------------------------------------------+

The new algorithm proceeds by recursively partitioning the ray into little line segments which intersect the leaf voxels. The top-down nature of the recursive search ensures that partition nodes are only considered ONCE PER RAY. In addition, the voxels will be visited in the correct order, thereby retaining the O( log N ) best case behavior.

Below is a pseudo code description of the "partitioning" algorithm. It is the routine for intersecting a ray with an environment which has been subdivided using a BSP tree. Little things like checking to make sure the intersection is within the appropriate interval have been omitted. The input arguments to this routine are:

    Node : A BSP tree node which comes in two flavors -- a partition node
	   or a leaf node.  A partition node defines a plane and points to
	   two child nodes which further partition the "positive" and
	   "negative" half-spaces.  A leaf node points to a list of
	   candidate objects.

    P    : The ray origin.  Actually, think of this as an endpoint of a 3D
	   line segment, since we are constraining the "ray" to be of finite
	   length.

    D    : A unit vector indicating the ray direction.

    len  : The length of the "ray" -- or, more appropriately, the line
	   segment.  This is measured from the origin, P, along the
	   direction vector, D.

The function "Intersect" is initially passed the root node of the BSP tree, the origin and direction of the ray, and a length, "len", indicating the maximum distance to intersections which are to be considered. This starts out being the distance to the far end of the original bounding cube.

==============================================

FUNCTION Intersect( Node, P, D, len ) RETURNING "results of intersection"

    IF Node is NIL THEN RETURN( "no intersection" )

    IF Node is a leaf THEN BEGIN

	intersect ray (P,D) with objects in the candidate list

	RETURN( "the closest resulting intersection" )

	END IF

    dist := signed distance along ray (P,D) to plane defined by Node

    near := child of Node in half-space which contains P

    IF 0 < dist < len THEN BEGIN  /* the interval intersects the plane */

	hit_data := Intersect( near, P, D, dist )

	IF hit_data <> "no intersection" THEN RETURN( hit_data )

	Q := P + dist * D   /* 3D coords of point of intersection */

	far := child of Node in half-space which does NOT contain P

	RETURN( Intersect( far, Q, D, len - dist ) )

	END IF

    ELSE RETURN( Intersect( near, P, D, len ) )

    END

=========================================================

As the BSP tree is traversed, the line segments are chopped up by the partitioning nodes. The "shrinking" of the line segments is critical to ensure that only relevent branches of the tree will be traversed.

The actual encodings of the intersection data, the partitioning planes, and the nodes of the tree are all irrelevant to this discussion. These are "constant time" details. Granted, they become exceedingly important when considering whether the algorithm is really practical. Let's save this for later.

A naive (and incorrect) proof of the claim that the time complexity of this algorithm is O(N) would go something like this:

    The voxel walking that we perform on behalf of a single ray is really
    just a search of a binary tree with voxels at the leaves.  Since each
    node is only processed once, and since a binary tree with k leaves has
    k - 1 internal nodes, the total number of nodes which are processed in
    the entire operation must be of the same order as the number of leaves.
    We know that there are O( N ) leaves.  Therefore, the time complexity
    is O( N ).

But wait! The tree that we search is not truly binary since many of the internal nodes have one NIL branch. This happens when we discover that the entire current line segment is on one side of a partitioning plane and we prune off the branch on the other side. This is essential because there are really N**3 leaves and we need to discard branches leading to all but O( N ) of them. Thus, k leaves does not imply that there are only k - 1 internal nodes. The quention is, "Can there be more than O( k ) internal nodes?".

Suppose we were to pick N random voxels from the N**3 possible choices, then walk up the BSP tree marking all the nodes in the tree which eventually lead to these N leaves. Let's call this the subtree "generated" by the original N voxels. Clearly this is a tree and it's uniquely determined by the leaves. A very simple argument shows that the generated subtree can have as many as 2 * ( N - 1 ) * log N nodes. This puts us right back where we started from, with a time complexity of O( N log N ), even if we visit these nodes only once. This makes sense, because the "re-traversal" method, which is also O( N log N ), treats the nodes as though they were unrelated. That is, it does not take advantage of the fact that paths leading to neighboring voxels are likely to be almost identical, diverging only very near the leaves. Therefore, if the "partitioning" scheme really does visit only O( N ) nodes, it does so because the voxels along a ray are far from random. It must implicitly take advantage of the fact that the voxels are much more likely to be brothers than distant cousins.

This is in fact the case. To prove it I found that all I needed to assume about the voxels was connectedness -- provided I made some assumptions about the "niceness" of the BSP tree. To give a careful proof of this is very tedious, so I'll just outline the strategy (which I *think* is correct). But first let's define a couple of convenient terms:

1) Two voxels are "connected" (actually "26-connected") if they meet at a face, an edge, or a corner. We will say that a collection of voxels is connected if there is a path of connected voxels between any two of them.

2) A "regular" BSP tree is one in which each axis-orthogonal partition divides the parent volume in half, and the partitions cycle: X, Y, Z, X, Y, Z, etc. (Actually, we can weaken both of these requirements considerably and still make the proof work. If we're dealing with "standard" octrees, the regularity is automatic.)

Here is a sequence of little theorems which leads to the main result:

    THEOREM 1:  A ray pierces O(N) voxels.

    THEOREM 2:  The voxels pierced by a ray form a connected set.

    THEOREM 3:  Given a collection of voxels defined by a "regular" BSP
		tree, any connected subset of K voxels generates a unique
		subtree with O( K ) nodes.

    THEOREM 4:  The "partitioning" algorithm visits exactly the nodes of
		the subtree generated by the voxels pierced by a ray.
		Furthermore, each of these nodes is visited exaclty once
		per ray.

    THEOREM 5:  The "partitioning" algorithm has a worst case complexity
		of O( N ) for walking the voxels pierced by a ray.

Theorems 1 and 2 are trivial. With the exception of the "uniqueness" part, theorem 3 is a little tricky to prove. I found that if I completely removed either of the "regularity" properties of the BSP tree (as opposed to just weakening them), I could construct a counterexample. I think that theorem 3 is true as stated, but I don't like my "proof" yet. I'm looking for an easy and intuitive proof. Theorem 4 is not hard to prove at all. All the facts become fairly clear if you see what the algorithm is doing. Finally, theorem 5, the main result, follows immediately from theorems 1 through 4.

SOME PRACTICAL MATTERS:

Since log N is typically going to be very small -- bounded by 10, say -- this whole discussion may be purely academic. However, just for the heck of it, I'll mention some things which could make this a (maybe) competative algorithm for real-life situations (in as much as ray tracing can ever be considered to be "real life").

First of all, it would probably be advisable to avoid recursive procedure calls in the "inner loop" of a voxel walker. This means maintaining an explicit stack. At the very least one should "longjump" out of the recursion once an intersection is found.

The calculation of "dist" is very simple for axis-orthogonal planes, consisting of a subtract and a multiply (assuming that the reciprocals of the direction components are computed once up front, before the recursion begins).

A nice thing which falls out for free is that arbitrary partitioning planes can be used if desired. The only penalty is a more costly distance calculation. The rest of the algorithm works without modification. There may be some situations in which this extra cost is justified.

Sigh. This turned out to be much longer than I had planned...

>>>>>> A followup message:

Here is a slightly improved version of the algorithm in my previous mail. It turns out that you never need to explicitly compute the points of intersection with the partitioning planes. This makes it a little more attractive.

				                                 -- Jim

FUNCTION BSP_Intersect( Ray, Node, min, max ) RETURNING "intersection results"

BEGIN

    IF Node is NIL THEN RETURN( "no intersection" )

    IF Node is a leaf THEN BEGIN  /* Do the real intersection checking */

	intersect Ray with each object in the candidate
	list discarding those farther away than "max."

	RETURN( "the closest resulting intersection" )

	END IF

    dist := signed distance along Ray to plane defined by Node

    near := child of Node for half-space containing the origin of Ray

    far  := the "other" child of Node -- i.e. not equal to near.

    IF dist > max OR dist < 0 THEN  /* Whole interval is on near side. */

	RETURN( BSP_Intersect( Ray, near, min, max ) )

    ELSE IF dist < min THEN  /* Whole interval is on far side. */

	RETURN( BSP_Intersect( Ray, far , min, max ) )

    ELSE BEGIN  /* the interval intersects the plane */

	hit_data := BSP_Intersect( Ray, near, min, dist ) /* Test near side */

	IF hit_data indicates that there was a hit THEN RETURN( hit_data )

	RETURN( BSP_Intersect( Ray, far, dist, max ) )  /* Test far side. */

	END IF

    END

related previous discussion of topic

more discussion of topic

back to contents


Efficiency Tricks, by Eric Haines

Some people turn out to be on the e-mail mailing list but not the hardcopy list for the RT News. In case you don't get the RT News in hardcopy form, I'm including the Efficiency Tricks article & the puzzle from it in this issue.

________

Given a ray-tracer which has some basic efficiency scheme in use, how can we make it faster? Some of my tricks are below - what are yours?

[HBV stands for Hierarchical Bounding Volumes]

Speed-up #1: [HBV and probably Octree] Keep track of the closest intersection distance. Whenever a primitive (i.e. something that exists - not a bounding volume) is hit, keep its distance as the maximum distance to search. During further intersection testing use this distance to cut short the intersection calculations.

Speed-up #2: [HBV and possibly Octree] When building the ray tree, keep the ray-tree around which was previously built. For each ray-tree node, intersect the object in the old ray tree, then proceed to intersect the new ray tree. By intersecting the old object first you can usually obtain a maximum distance immediately, which can then be used to aid Speed-up #1.

Speed-up #3: When shadow testing, keep the opaque object (if any) which shadowed each light for each ray-tree node. Try these objects immediately during the next shadow testing at that ray-tree node. Odds are that whatever shadowed your last intersection point will shadow again. If the object is hit you can immediately stop testing because the light is not seen.

Speed-up #4: When shadow testing, save transparent objects for later intersection. Only if no opaque object is hit should the transparent objects be tested.

Speed-up #5: Don't calculate the normal for each intersection. Get the normal only after all intersection calculations are done and the closest object for each node is know: after all, each ray can have only one intersection point and one normal. (Saving intermediate results is recommended for some intersection calculations.)

Speed-up #6: [HBV only] When shooting rays from a surface (e.g. reflection, refraction, or shadow rays), get the initial list of objects to intersect from the bounding volume hierarchy. For example, a ray beginning on a sphere must hit the sphere's bounding volume, so include all other objects in this bounding volume in the immediate test list. The bounding volume which is the father of the sphere's bounding volume must also automatically be hit, and its other sons should automatically be added to the test list, and so on up the object tree. Note also that this list can be calculated once for any object, and so could be created and kept around under a least-recently-used storage scheme.

more discussion of topic

back to contents


A Rendering Trick and a Puzzle, by Eric Haines

One common trick is to put a light at the eye to do better ambient lighting. Normally if a surface is lit by only ambient light, its shading is pretty crummy. For example, a non-reflective cube totally in shadow will have all of its faces shaded the exact same shade - very unrealistic. The light at the eye gives the cube definition. Note that a light at the eye does not need shadow testing - wherever the eye can see, the light can see, and vice versa.

The puzzle: Actually, I lied. This technique can cause a subtle error. Do you know what shading error the above technique would cause? [hint: assume the Hall model is used for shading].

back to contents


USENET Roundup (PECG Errata), by David Rogers

Other than a hilarious set of messages begun when Paul Heckbert's Jell-O (TM) article was posted to USENET, and the perennial question "How do I find if a point is inside a polygon?", not much of interest. However, I did get a copy of the errata in _Procedural Elements for Computer Graphics_ from David Rogers.

I updated my edition (the Second) with these corrections, which was generally a time drain: my advice is to keep the errata sheets in this edition, checking them only if you are planning to use an algorithm. However, the third edition corrections are mercifully short.

____

From: "David F. Rogers" USNA.MIL!dfr@cornell.UUCP> From: David F. Rogers (dfr@USNA.MIL) Subject: PECG correction Date: Thu, 10 Mar 88 13:21:11 EST

Correction list for PECG  2/26/86
David F. Rogers

There have been 3 printings of this book to date. The 3rd printing occurred in approximately March 85.

To see if you have the 3rd printing look on page 386, 3rd line down and see if the word magenta is spelled correctly. If it is, you have the 3rd printing. If not, then you have the 2nd or 1st printing.

To see if you have the 2nd printing look on page 90. If the 15th printed line in the algorithm is

  while Pixel(x,y) <> Boundary value

you have the 2nd printing. If not you have the 1st printing.

Please send any additional corrections to me at

Professor David F. Rogers
Aerospace Engineering Department
United States Naval Academy
Annapolis, Maryland 21402

uucp:decvax!brl-bmd!usna!dfr
arpa:dfr@usna

_____________________________________________________________

Known corrections to the third printing:

Page	Para./Eq.	Line	Was		Should be

72 2 11 (5,5) (5,1) 82 1 example 4 (8,5) delete 100 5th equation upper limit on integral should be 2 vice 1 143 Fig. 3-14 yes branch of t < 0 and t > 1 decision blocks should extend down to Exit-line invisible 144 Cyrus-Beck algorithm 7 then 3 then 4 11 then 3 then 4 145 Table 3-7 1 value for w [2 1] [-2 1] 147 1st eq. 23 V sub e sub x j V sub e sub y j

______________________________________________________________

Known corrections to the second printing: (above plus)

text:

19	2		5	Britian 	Britain
36	Eq. 3		10	replace 2nd + with =
47	4		6	delta' > 0      delta'< = 0
82	1		6	set		complement
99	1		6	multipled	multiplied
100	1		6	Fig. 2-50a	Fig. 2-57a
100	1		8	Fig. 2-50b	Fig. 2-57b
122	write for new page
186	2		6	Fig. 3-37a	Fig. 3-38a
186	2		9	Fig. 3-38	Fig. 3-38b
187	Ref. 3-5		to appear	Vol. 3, pp. 1-23, 1984
194	Eq. 1			xn +		xn -
224	14 lines from bottom	t = 1/4 	t = 3/4
329	last eq.		-0.04		-0.13
	next to last eq.	-0.04 twice	-0.13 twice
	3rd from bottom 	0.14		-0.14
330	1st eq. 		-0.09		-0.14
	2nd eq. 		-0.09		-0.14
	3rd eq. 		-0.17		-0.27
	4th eq. 		0.36		0.30
				5.25		4.65
	last eq.		5.25		4.65
332			4	beta <		beta >
			6	beta <		beta >
355	2nd eq. 		w = s(u,w)	w = s(theta,phi)
385	2		5	magneta 	magenta
386			3	magneta 	magenta

algorithms: (send self-addressed long stamped envelope for xeroxed corrections)

97	Bresenham	1	insert words  first quadrant  after modified
			10	remove ()
			12	1/2		I/2
			14	delta x 	x sub 2

117	Explicit	18	Icount = 0	delete
	clipping
			18	insert		m = Large
120			9	P'2             P'1
			12	insert after	Icount = 0
				end if
			13	insert after	1 if Icount <> 0 then
				neither end	   P' = P0
			14			removed statement label 1
			15	>=		>
			17			delete
			18			delete
			43	y>		yT>

122-124 Sutherland-	write for new pages
	Cohen

128	midpoint	4	insert after	initialize i
						i = 1
129			6	i = 1		delete
			6	insert		save original p1
						Temp = P1
			8	i = 2		i > 2
			11,12	save original.. delete
				Temp = P1
			14	add statement label 2
130			19-22	delete
			24	i = 2		i = i + 1
			29	<>		<> 0
			33	P1		P

143			3	wdotn		Wdotn
144			20	>=		>

176	Sutherland-	1	then 5		then 4
	Hodgman
177			9	4 x 4		2 x 2

198	floating	21,22	x,y		Xprev,Yprev
	horizon
199			4	Lower		Upper
200			11-19	rewrite as
				if y < Upper(x) and y > Lower(x) then Cflag = 0
				if y> = Upper(x) then Cflag = 1
				if y< = Lower(x) then Cflag = -1
			29	delete
			31	Xinc		(x2-x1)
			36	step Xinc	step 1
201			4	delete
			6	Xinc = 0       (x2-x1) = 0
			12	Y1 -		Y1 + Slope -
			12	insert after	Csign = Ysign
			13	Yi = Y1 	Yi = Y1 + Slope
			13	insert after	Xi = X1 + 1
			14-end	rewrite as	while(Csign = Ysign)
						   Yi = Yi + Slope
						    Xi = Xi + 1
						    Csign = Sign(Yi - Array(Xi))
						end while
						select nearest integer value
						if |Yi -Slope -Array(Xi - 1)| <=
						  |Yi - Array(Xi)| then
						    Yi = Yi - Slope
						    Xi = Xi -1
						end if
					     end if
					 return

258	subroutine Compute	N		i

402	HSV to Rgb	12	insert after	end if
			25	end if		delete

404	HLS to RGB	2	M1 = L*(1 - S)	M2 = L*(1 + S)
			4	M1		M2
			6	M2 = 2*L - M1	M1 = 2*L - M2
			10-12	=1		=L
			18	H		H + 120
			19	Value + 120	Value
			22	H		H - 120
			23	Value - 120	Value

405	RGB to HLS	22	M1 + M2 	M1 - M2

figures:

77	Fig. 2-39a		interchange Edge labels for scanlines 5 & 6
	Fig. 2-39b		interchange information for lists 1 & 3, 2 & 4

96	Fig. 2-57a,b		y sub i + 1	y sub(i+1)

99	Fig. 2-59		abcissa of lowest plot should be xi vice x

118	Fig. 3-4		first initialization block - add m = Large
				add F entry point just above IFLAG = -1
				decision block
119				to both IFLAG=-1 blocks add exit points to F

125	Fig. 3-5		line f - interchange Pm1 & Pm2

128	Fig. 3-6a		add initialization block immediately after Start
				initialize i, i=1

				immediately below new initialization block add
				entry point C

				in Look for the farthest vissible point from P1
				block - delete i=1

				in decision block i = 2 - change to i > 2

129	Fig. 3-6b		move return to below Save P1 , T = P1 block

				remove Switch end point codes block

				in Reset counter block replace i=2 with i=i + 1

180	Fig. 3-34b		Reverse direction of arrows of box surrounding
				word Start.

330	Fig. 5-16a		add P where rays meet surface

374	Fig. 5-42		delete unlabelled third exit from decision
				box r ray?

377	Fig. 5-44		in lowest box I=I+I sub(l (sub j)) replace
				S with S sub(j)
_________________________________________________________________________

Known corrections to the first printing:

90,91	scan line seed		write for xeroxed corrections
	fill algorithm

back to contents


Eric Haines / erich@acm.org