_ __ ______ _ __ ' ) ) / ' ) ) /--' __. __ , --/ __ __. _. o ____ _, / / _ , , , _ / \_(_/|_/ (_/_ (_/ / (_(_/|_(__<_/ / <_(_)_ / (_ +---+---+ ^ | 2 | $ | Numbers are the order of cubes moved through. | +---#---+ Y | 1 | 3 | +---+---+ ^________ray started here, and hit almost at the "#". (ray is in +X, +Y direction) This went into an infinite loop, going between 2 and 3 forever. The reason was that when I hit the boundary 1&2 I would add a Y increment (half minimum box size) to the intersection point, then convert this to find that I was now in box 2. I would then shoot the ray again and it would hit the wall at 2&$. To this intersection point I would add an X increment. However, what would happen is that the Y intersection point would actually be ever so slightly low - earlier when I hit the 1&2 wall adding the increment pushed us into box 2. But now when the Y intersection point was converted it would put us in the 1+3 boxes, and X would then put us in box 3. Basically, the precision of the machine made the mapping between world space and octree space be ever so slightly off. The infinite loop occurred when we shot the ray again at box 3. It would hit the 3/$ wall, get Y incremented, and because X was ever so slightly less than what was truly needed to put the intersection point in the 3+$ boxes, we would go back to box 2, ad infinitum. Another way to look at this is that when we would intersect the ray against any of the walls near the "#" point, the intersection point (due to roundoff) was always mapping to box 1 if not incremented. Incrementing in Y would move it to box 2, and in X would move it to box 3, but then the next intersection test would yield another point that would be in box 1. Since we couldn't increment in both directions at once, we could never get past 2 and 3 simultaneously. This bug occurs very rarely because of this: the intersection points all have to be such that they are very near a corner, and the mapping of the points must all land within box 1. This problem occurred for me once in a few million rays, which of course made it all that much more fun to search for it. My solution was to check the distance of the intersections generated each time: if the closest intersection was a smaller distance from the origin than the closest distance for the previous cube move, then this intersection point would not be used, but rather the next higher would be. In this way forward progress along the ray would always be made. By the way, I found that it was worthwhile to always use the original ray origin for testing ray/cube intersections - doing this avoids any cumulative precision errors which could occur by successively starting from each new intersection point. To simulate the origin starting within the cube I would simply test only the 3 cube faces which faced away from the ray direction (this was also faster to test). Anyway, hope this made sense - has anyone else run into this bug? Any other solutions? --------------------------------------------- A Pet Peeve (by Jeff Goldsmith) ----------- Don't ever refer to pixels as rows and columns. It makes it hard to get the order (row,column)? (column,row)? right. Refer to pixels as (x,y) coordinates. Not only is that the natural system to do math on them, but it is much easier to visualize in a debugging environment, as well as running the thing. I use the -x and -y npix switches on the tracer command line to override any settings and have found them to be much easier to deal with than the -r and -c that seem to be everywhere. Note that C's normal array order is (I think. I always get these things wrong.) (y,x). [I agree: my problem now is that Y=0 is the bottom edge of the screen when dealing with the graphics package (HP's Starbase), and Y=0 is the top when directly accessing the frame buffer (HP's SRX). -- EAH] --------------------------------------------- Next "RT News" issue I'll include a write-up of Goldsmith/Salmon which should hopefully make the algorithm clearer, plus some little additions I've made. I've found Goldsmith/Salmon to be a worthwhile, robust efficiency scheme which hasn't received much attention. It embodies an odd way of thinking (I have to reread my notes about it when I want to change the code), as there are a number of costs which must be taken into account and inherited. It's not immediately intuitive, but has a certain sense to it once all the pieces are in place. Hopefully I'll be able to shed some more light on it. All for now, Eric _ __ ______ _ __ ' ) ) / ' ) ) /--' __. __ , --/ __ __. _. o ____ _, / / _ , , , _ / \_(_/|_/ (_/_ (_/ / (_(_/|_(__<_/ / <_(_)_ / (_Efficiency Tricks >Since illumination rays form the bulk of the rays we >trace. If so, instead of space tracing, you should use ray coherence at least for the illumination rays. The ray coherent approaches are found in CG&A vol. 6, no. 9 "The Light Buffer: A Shadow-Testing Accelerator" and in my paper "ray coherence theorem and constant time ray tracing algorithm" in proceedings of CG International '87. >In addition, if CSG is used, more times occur when the nearest >intersection is of less value. This seems to indicate that >space tracing techniques are doing some amount of needless work. How about tracing illumination rays from light sources, instead of from object surface? It will be faster for your CSG case, if the surface point lies in the shadow, though if the surface point is illuminated, there will be no speed improvement. The problem is interesting to me because my research on coherent ray tracer also suggests that it is much better to trace illumination rays from the light source. Do you have any other reasons to determine from where illumination rays are fired? ---------------------------------------------------------------------- Jeff Goldsmith's reply: Actually, I believe you, though I won't say with certainty that we know the best way to do shadow testing. However, I'm interested in fundamentally understanding the ray tracing algorithm and determining what computation MUST be done, so the realization that space tracing illumination rays still seems meaningful. In fact, it is my opinion that space tracing is not the right way to go and "backwards" (classical) ray tracing will eventually be closer to what will be used 30 years from now. I won't even try to defend that position; no one knows the answers. What we are trying to do is shed a little "light" on the subject. Thanks for your comments. ----------------- From Eric Haines: I just got from Ohta the same note Ohta sent to you, plus your reply. Your reply is so short that I've lost the sense of it. So, if you don't mind, a quick explanation would be useful. > However, > I'm interested in fundamentally understanding the ray tracing > algorithm and determining what computation MUST be done, so > the realization that space tracing illumination rays still > seems meaningful. What is "the realization that space tracing illumination rays"? I'm missing something here - which realization? > In fact, it is my opinion that space tracing > is not the right way to go and "backwards" (classical) ray > tracing will eventually be closer to what will be used 30 > years from now. Do you mean by "space tracing" Ohta's method? Basically, it looks like I should reread Ohta's article, but I thought I'd check first. -------------- Further explanation from Jeff Goldsmith: I think that a word got dropped from the sentence, either when I typed it in or later. (Who knows--I do that about as often as computers do.) I meant: Since distance order is not needed for illumination rays, space tracing methods in general (not Ohta's in particular) do extra work. It's not always clear that extra information costs extra computation, but they usually go hand in hand. (It was just a rehash of the original message.) Anyway, if extra computation is being done, perhaps then there is an algorithm that does not do this computation, yet does all the others (or some others...) that is of lower asymptotic time complexity. Basically, this all boils down to my response to various claims that people have "constant time" ray tracers. It is just not true. It can't be true if they are using a method that will yield the first intersection along a path since we know that that computation cannot be done in less than O(n log n) without a discretized distance measurement. I don't think that space tracers discretize distance in the sense of a bucket sort, but I could be convinced, I suppose. Anyway, that's what the ramblings are all about. If you have some insights, I'd like to start an argument (sorry, discussion) on the net about the topic. What do you think? ------------------------------------------------------------ Extracts from USENET news ------------------------- There was recently some interesting interchange about octree building on USENET. Some people don't read or don't receive comp.graphics, so the rest of this issue consists of these messages. ---------------- From Ruud Waij (who is not on the RT News e-mail mailing list): In article <198@dutrun.UUCP> winffhp@dutrun.UUCP (ruud waij) writes: My ray tracing program, which can display the primitives block, sphere cone and cylinder, uses spatial enumeration of the object space (subdivision in regularly located cubical cells (voxels)) to speed up computation. The voxels each have a list of primitives. If the surface of a primitive is inside a voxel, this primitive will be put in the list of the voxel. I am currently using bounding boxes around the primitives: if part of the bounding box is inside the voxel, the surface of the primitive is said to be inside the voxel. This is a very easy method but also very s-l-o-w. I am trying to find a better way of determining whether the surface of a primitive is in a voxel or not, but I am not very succesful. Does anyone out there have any suggestions ? --------------- Response from Paul Heckbert: Yes, interesting problem! Fitting a bounding box around the object and listing that object in all voxels intersected by the bounding box will be inefficient as it can list the object in many voxels not intersected by the object itself. Imagine a long, thin cylinder at an angle to the voxel grid. I've never implemented this, but I think it would solve your problem for general quadrics: find zmin and zmax for the object. loop over z from zmin to zmax, stepping from grid plane to grid plane. find the conic curve of the intersection of the quadric with the plane. this will be a second degree equation in x and y (an ellipse, parabola, hyperbola, or line). note that you'll have to deal with the end caps of your cylinders and similar details. find ymin and ymax for the conic curve. loop over y from ymin to ymax, stepping from grid line to grid line within the current z-plane find the intersection points of the current y line with the conic. this will be zero, one, or two points. find xmin and xmax of these points. loop over x from xmin to xmax. the voxel at (x, y, z) intersects the object Perhaps others out there have actually implemented stuff like this and will enlighten us with their experience. ----------------- Response from Andrew Glassner: Ruud and I have discussed this in person, but I thought I'd respond anyway - both to summarize our discussions and offer some comments on the technique. The central question of the posting was how to assign the surfaces of various objects to volume cells, in order to use some form spatial subdivision to accelerate ray tracing. Notice that there are at least two assumptions underlying this method. The first assumes that the interior of each object is homogeneous in all respects, and thus uninteresting from a ray-tracing point of view. As a counterexample, if we have smoke swirling around inside a crystal ball, then this "homogeneous-contents" assumption breaks down fast. To compensate, we either must include the volume inside each object to each cell's object list (and support a more complex object description encompassing both the surface and the contents), or include as new objects the stuff within the original. The other assumption is that objects have hard edges; otherwise we have to revise our definition of "surface" in this context. This can begin to be a problem with implicit surfaces, though I haven't seen this really discussed yet in print. But so as long as we're using hard-edged objects with homogeneous interiors, the "surface in a cell" approach is still attractive. From here on I'll assume that cells are rectangular boxes. So to which cells do we attach a particular surface? Ruud's current technique (gathered from his posting) finds the bounding box of the surface and marks every cell that is even partly within the bounding volume. Sure, this marks a lot of cells that need not be marked. One way to reduce the marked cell count is to notice that if the object is convex, we can unmark any cell that is completely within the object; we test the 8 corners with an inside/outside test (fast and simple for quadrics; only slightly slower and harder for polyhedra). If all 8 corners are "inside", unmark the cell. Of course, this assumes convex cells - like boxes. Note that some quadrics are not convex (e.g. hyperboloid of one sheet) so you must be at least a little careful here. The opposite doesn't hold - just because all 8 corners are outside does NOT mean a cell may be unmarked. Consider the end of a cylinder poking into one side of a box, like an ice-cream bar on a stick, where the ice-cream bar itself is our cell. The stick is within the ice cream, but all the corners of the ice cream bar are outside the stick. Since this box contains some of the stick's surface, the box should still be marked. So our final cells have either some inside and some outside corners, or all outside corners. What do we lose by having lots of extra cells marked? Probably not much. By storing the ray intersection parameter with each object after an intersection has been computed, we don't ever need to actually repeat an intersection. If the ray id# that is being traced matches the ray id# for which the object holds the intersection parameter, we simply return the intersection value. This requires getting access to the object's description and then a comparison - probably the object access is the most expensive step. But most objects are locally coherent (if you hit a cell containing object A, the next time you need object A again will probably be pretty soon). So "false positives" - cells who claim to contain an object they really don't - aren't so bad, since the pages containing an object will probably still be resident when we need it again. We do need to protect ourselves, though, against a little gotcha that I neglected to discuss in my '84 CG&A paper. If you enter a cell and find that you hit an object it claims to contain, you must check that the intersection you computed actually resides within that cell. It's possible that the cell is a false positive, so the object itself isn't even in the cell. It's also possible that the object is something like a boomerang, where it really is within the current cell but the actual intersection is in another cell. The loss comes in when the intersection is actually in the next cell, but another surface in the next cell (but not in this one) is actually in front. Even worse, if you're doing CSG, that phony intersection can distort your entire precious CSG status tree! The moral is not to be fooled just because you hit an object in a cell; check to be sure that the intersection itself is also within the cell. How to find the bounding box of a quadric? A really simple way is to find the bounding box of the quadric in its canonical space, and then transform the box into the object's position. Fit a new bounding box around the eight transformed corners of the original bounding box. This will not make a very tight volume at all, (imagine a slanted, tilted cylinder and its bounding box), but it's quick and dirty and I use it for getting code debugged and at least running. If you have a convex hull program, you can compute the hull for concave polyhedra and use its bounding box; obviously you needn't bother for convex polyhedra. For parametric curved surfaces you can try to find a polyhedral shell the is guaranteed to enclose the surface; again you can find the shell's convex hull and then find the extreme values along each co-ordinate. If your boxes don't have to be axis-aligned, then the problem changes significantly. Consider a sphere: an infinite number of equally-sized boxes at different orientation will enclose the sphere minimally. More complicated shapes appear more formidable. An O(n^3) algorithm for non-aligned bounding boxes can be found in "Finding Minimal Enclosing Boxes" by O'Rourke (International Journal of Computer and Information Sciences, Vol 14, No 3, 1985, pp. 183-199). Other approaches include traditional 3-d scan conversion, which I think should be easily convertable into an adaptive octree environment. Or you can grab the bull by the horns and go for raw octree encoding, approximating the surface with lots of little sugar cubes. Then mark any cell in your space subdivision tree that encloses (some or all of) any of these cubes. _ __ ______ _ __ ' ) ) / ' ) ) /--' __. __ , --/ __ __. _. o ____ _, / / _ , , , _ / \_(_/|_/ (_/_ (_/ / (_(_/|_(__<_/ / <_(_)_ / (_ "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 ------------------------------------------------------------------------ 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. Efficiency Tricks, by Eric Haines --------------------------------- 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. ------------------------------------------ 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]. --------------------------------------------------------------------------- USENET roundup: 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" From: David F. Rogers 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 ________________________________________________________________________ END OF RTNEWS