jfid@warwick.UUCP (James Fidell) (05/13/88)
For my third year project, I have implemented a ray tracer in C on a Sun 3/60. It does constructive solid geometry on a few simple primitive solids (spheres, cubes, pyramids, cones etc. ), objects in the scene being specified as combinations of rotations, enlargements and translations of these. All arithmetic is done using doubles. When I wrote the cone primitive I had problems because the code which found the intersection points between a ray (specified in vector form r = x + lambda d) and the curved surface of the cone, would sometimes fail, or generate erroneous intersections, because it gave solution values which were only very close to zero ( ie 10^-15 ) when, in fact, they should be exactly zero (I am sure my code is correct :-) I know that this might happen because of rounding or some other inherent representational error, but my knowledge of what could happen in this area is somewhat thin. Does anybody know of a solution to this ? My only work-around was to fudge the code so that values close to zero would be assumed zero. Another related problem - how does one guarantee that a given intersection point is really *on* a surface, and not just a little way above or below it - as might happen with the above case ? Finally, does anyone know of a standard/commonly used notation for defining scenes ? I am thinking of a format which could perhaps be passed through a filter to produce a suitable input format for a polygon modeller, or a different filter to produce input for a CSG ray tracer etc. Thanx, James -- "I walk down the street, | uk: jfid@uk.ac.warwick.uu there's no-one there, | usa: ...seismo!mcvax... though the pavement is one huge crowd" | eur: ..mcvax!ukc!warwick!jfid Eric Clapton / Cream | James Fidell
saponara@batcomputer.tn.cornell.edu (John Saponara) (05/16/88)
In article <639@ubu.warwick.UUCP> jfid@warwick.UUCP (James Fidell) writes about his ray tracer: > >All arithmetic is done using doubles. When I wrote the cone primitive I >had problems because the code which found the intersection points between a >ray (specified in vector form r = x + lambda d) and the curved surface of the >cone, would sometimes fail, or generate erroneous intersections, because >it gave solution values which were only very close to zero ( ie 10^-15 ) >when, in fact, they should be exactly zero (I am sure my code is correct :-) >I know that this might happen because of rounding or some other inherent >representational error, but my knowledge of what could happen in this area >is somewhat thin. Does anybody know of a solution to this ? My only >work-around was to fudge the code so that values close to zero would be >assumed zero. Attached is a section from my notes for the upcoming "Introduction to Ray Tracing" SIGGRAPH '88 course. I've edited these for inclusion here (mainly, I took out the diagram). This section was done with a focus on sphere intersection, but applies to most primitives. I still don't have a real great solution to your problem (and so am looking forward to other people's responses), but these notes cover my attempts to solve this problem. Eric Haines ("the man who is not John Saponara") Precision Problems Doing floating-point calculations is like moving piles of sand around. Every time you move a pile you lose a little sand and pick up a little dirt [DUFF84]. Imprecision can cause a number of errors which must be addressed. A discussion of general numerical problems in computer graphics appears in [DUFF84]. What follows is a brief discussion of a common problem to all ray tracing intersection routines. In ray tracing often the origin of the ray is a point on the sphere itself. Theoretically, distance "t" = 0 for these points, which are ignored by testing for this condition. However, in practice, calculational imprecision will creep in and throw these tests off. This imprecision will cause rays shot from the surface to hit the surface itself. Computationally what occurs is that t's are found which are very close to, but not necessarily equal to, zero. If uncorrected, those larger than zero will be considered valid intersections. The result is the nonsensical situation in which a small surface area is shadowed by itself. The practical effect of this imprecision is a case of "surface acne". The surface will sometimes shadow itself, causing blotches and spots to appear. Some method of coping with this imprecision is necessary to clean up this problem. The discussion below also applies to any other primitive intersected, as all surfaces have this potential problem. One method to avoid imprecision is to pass a flag telling whether the origin is actually on the sphere. In ray tracing, the last intersection point is known, so the procedure can be informed that the ray starts on the surface. However, if the sphere is a transmitter some testing must be done to allow refraction rays to pass through the sphere and hit its other side. The same problem arises with reflections from the inside of the sphere. In these cases the second intersection point along the ray is the valid answer. A simple solution is to check if "t" is within some tolerance. For example, if abs(t)~<~0.00001, then that "t" describes the origin as being on the sphere. Scaling this tolerance to the size of the environment is advisable. For example, if the spheres were atoms and the radii were expressed in meters, 0.00001 meters would be much larger than any atom. Choosing these tolerances can be done empirically or, more accurately, by numerical methods for error analysis. For example, the tolerance could also be based on the radius of the sphere intersected. Root polishing methods may also be useful in solving imprecision problems. For example, say a ray is traced and the "t" of the closest object (i.e. the object the ray first hits) is found. Find this intersection point and use this as the origin of a new ray which uses the same direction. By intersecting the sphere with this new ray and accepting the solution for "t" closest to zero (even if "t" is negative), a more accurate intersection point can be found. While "t" is greater than some given tolerance this procedure is repeated. This method does not eliminate the need for a tolerance factor, but it does allow the programmer to be confident that the intersection point is within a certain distance of the surface. A fourth solution is to move the intersection point outside or inside the sphere as needed. That is, when the intersection point is found and new rays are spawned, assure that the new origins are on the proper sides of the surface. This can be done by moving each new ray's origin along the normal until it is found to be on the proper side of the sphere. This involves testing if the point is inside or outside by substituting the intersection point into the sphere equation and checking on which side of the surface the point lays (which is done by checking the sign of the surface expression). If not on the desired side, the point is moved by some tolerance along the normal, then tested again. Note that reflection and shadow rays will always move positively along the normal, refraction rays negatively. This method assures that the origin of the spawned ray will be on the correct side of the sphere, so that the ray will not intersect the sphere. All of the above methods will work to varying degrees. If possible, the first method should be implemented as it is practically foolproof (almost tangent rays can sometimes have problems; however, these are rare). For spheres and other quadrics this is possible. If not, then some design decisions have to be made to chose the solution proper to the application.