Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!mips!apple!vsi1!daver!versatc.versatec.COM!ritter
From: ritter@versatc.versatec.COM (Jack Ritter)
Newsgroups: comp.graphics
Subject: Re: Ray Tracing in 3D space
Message-ID: <20490@versatc.versatec.COM>
Date: 17 Mar 90 03:21:58 GMT
References: <14440@phoenix.Princeton.EDU>
Organization: Versatec, Santa Clara, Ca. 95051
Lines: 56

in article <14440@phoenix.Princeton.EDU>, markv@gauss.Princeton.EDU (Mark VandeWettering) says:
> 
> You might instead want to implement general quadrics as a primitive, or 
> choose any one of a number of different ways of doing the above.  Homogenous
> coordinates might make this simpler actually.... Hmmm.... And there is a
> geometric argument that can also be used to derive algorithms like this.
> 
> Think about it.  It shouldn't be that difficult.
> 
> Mark

I do general ntersections in image space, by using the general quadric locus:

  a1*x^2 + a2*y^2 + a3*z^2 + b1*x*y + b2*x*z * b3*y*z + c1*x * c2*y + c3*z +d = 0 .

This represents every class of quadric at any location/orientation/scale.

To compute the (0,1, or2) intersections in image space, substitute
the componants of the ray (Ox,Oy,Oz) -> (Rx,Ry,Rz) for the x's y's and z's
in the general locus. You will get a (very complex) 2nd degree polynomial
in t. Do the factoring and rearranging, to compute the a,b, and c coefficients
of the reduced polynomial: a*t^2 + b*t + c = 0.
Now solve this quadratic equation to get your t's. Only positive t's
are valid, usually the smallest is the 1 you want (closest intersection if there are 2).
The intersection point, from your final t, is of course (Ox,Oy,Oz) + t*(Rx,Ry,Rz).
You now have the intersection point without even knowing what kind of
quadric it is! 
  To go along with this scheme, you must instantiate your quadrics algibraically.
This method allows saddle surfaces, hyperboloids of 1 sheet, etc, in addition
to the usual spheres, cones, etc. It also allows squashed quadrics, not just
symetrical ones (eg, an elliptical cylinder).
  Then there is boundary testing. I have a scheme that desribes a CSG type
cluster of quadric surfaces. To do boundary testing, I transform the image space
intersection point into the object space of the bounding surface(s) in that cluster.
I then compare the point with the topological boundary constraint(s)
imposed on the surface by its fellow bounder(s).
  In all of this, you still never really have to know what type of quadric you have hit!!
The draw back of this general scheme is the compute time it takes to produce
the a,b,c of the t polynomial. With the conventional way of transforming the ray
back to the object's cannonical space, most of the coefficients of the quadric locus
(eg, the a's,b's,c's and d of the locus above) are zero or 1.
However, I'm happy with my method, because I do lots of ray rejection tricks, to make the
computation less (but then who doesnt?)
-- 
   Versatec, Inc.
   Jack Ritter, M.S. 1-7
   2710 Walsh Ave.
   P.O. Box 58091
   Santa Clara, CA 95052-8091
   (408)982-4332, or (408)988-2800 X 5743
   UUCP:  {ames,apple,sun,pyramid}!versatc!ritter

   --( / __ - .. ((  /
   / / -- ) . \ \ // . (
	/ ** ) // _*_ // * ..
	) (( . \ / . * ) //