On this page of the documentation 
http://www.povray.org/documentation/view/116/

It says "Solving T from that is rather trivial math. ", but after hours 
of working on it I can't figure it out.  I haven't ever had a class in 
linear algebra, but usually I can figure stuff out on my own, and this 
time I just can't.  Maybe it is that when you multiply everything out it 
turns into way too many terms for me to handle, but that never stopped 
me in calculus class so why should it stop me now.  I got pretty much 
the same thing in my ray tracing book, so I assume it is well known, and 
  I am tottaly confident it is the right result, but it just naggs at me 
that I don't really know why.

I understand the basic strategy for solving it is to get it into the 
form A*t^2 + B*t + C = 0, and then just using the quadratic formula on 
it.  My book shows this step where the POV-Ray documentation page skips 
it.

A = D.D
B = P.D
C = P.P - R^2

Here "." is the dot product

When I work out the math I figured out what "A" is.  I'm not totally 
sure why you can substitute "V" for "P", and <X0,Y0,Z0>, but when I do I 
get the result for "C".  And last I always get a 2 in "P.D" for the "B" 
coefficient.

Anyone know where I can find all the math worked out in detail?  I'm not 
a fan of writing proofs, but I sleep better after reading them.

Post a reply to this message

> I'm not totally
> sure why you can substitute "V" for "P", and <X0,Y0,Z0>, but when I do I
> get the result for "C".

V, in the link you provided, is the beginning of the intersecting ray *with
respect to the sphere's location*. So, it's like, if you move the sphere to
the origin and the ray along with it, then the ray's new position will be V.
If the sphere is already centered at the origin, then V = P. It's just that
the intersection code has to be able to assume that the sphere is centered
on the origin, so it calculates V and it can then make that assumption.

> And last I always get a 2 in "P.D" for the "B"
> coefficient.


What they have done is considered D2 to be 1/2*B, and then used the
quadratic formula but replacing every occurance of B with 2*D2. The 2's end
up cancelling out with other 2's and 4's in the quadratic formula. So in
other words, they left out the 2 because it allows them to leave out more
coefficients later on (which would cancel out the 2), resulting in less
work.

With that in mind, it seems like you are well on your way to figuring out
this intersection algorithm.


By the way: I'd like to point out that this:
    #local T1 = (-DV+SQ)/D2;
    #local T2 = (-DV-SQ)/D2;
    #local Result = (T1<T2 ? T1 : T2);

can be safely replaced with this:
    #local Result = (-DV-SQ)/D2;

The reason being that we know that SQ is positive (we checked to make sure
it was earlier), So T2 will *always* be less than T1. Unless, of course, D2
is negative, but that can't be the case because D2 is the dot product of a
vector with itself (always >= zero).

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message

The notation is hard to read.  I think that maybe I would have 
understood what was going on if it was written in MathML.  I found 
http://biokyb.dyndns.org/aknet/cg/ray_sphere_intersect_algebraic/ this 
workout of the problem, and it pretty much matched my own calculations, 
so I decided the book was wrong, and that the POV-Ray code matches what 
is in the link I found.  I'm still not sure if the psudocode explanation 
makes sense.  But I found an overlooked math fact that leads to multiple 
optimizations  If D is actually a unit vector like it is supposed to be 
then D.D has to be "1".  Thus...

The line starting with #local D2 can be removed.  The next line will now 
  be.

#local SQ = DV*DV - (vdot(V,V) - R*R);

And

#local T2 = (-DV-SQ);

Post a reply to this message

Daniel Patrick Johnson <zap### [at] hotmailcom> wrote:
> If D is actually a unit vector like it is supposed to be 

  It isn't. The macro does not assume that the direction vector of the
ray (D) is a unit vector, and it usually isn't.

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message

Slime <fak### [at] emailaddress> wrote:
> By the way: I'd like to point out that this:
>     #local T1 = (-DV+SQ)/D2;
>     #local T2 = (-DV-SQ)/D2;
>     #local Result = (T1<T2 ? T1 : T2);

> can be safely replaced with this:
>     #local Result = (-DV-SQ)/D2;

  You are right. I didn't think of that.

  Actually the "#local SQ = sqrt(SQ);" line can be removed too, so it
becomes:

  #if(SQ < 0)
    #local Result = -1;
  #else
    #local Result = (-DV-sqrt(SQ))/D2;
  #end

  This probably speeds up the "raytracing" a bit.

  The reason why this can be reduced so much is that the macro always
returns the smallest 'T', regardless of whether it is the correct one
or not (meaning that if the camera is inside a sphere, it will not
raytrace it).
  For a correct raytracer, where you can have the camera inside the objects
or, moreover, you can have semi-transparent objects, this is not enough,
but I didn't want to go too far into raytracing for this simple tutorial.
(In this case you also must advance along the ray by a distance of epsilon
before you actually compute the ray-object intersection or else you'll be
sometimes hitting the object itself from which the reflected/refracted ray
was shot.)

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message

Warp wrote:

>>If D is actually a unit vector like it is supposed to be 
> 
> 
>   It isn't. The macro does not assume that the direction vector of the
> ray (D) is a unit vector, and it usually isn't.
> 

I guess you are right.

       Trace(-z*3, <CoordX, CoordY, 3>, 1);

With that 3 in there in what eventually gets thrown into D it clearly 
won't be normalized.  Since the code actually does the ray intersection 
test in this code with every sphere in the scene it might run faster if 
this line did normalize it.

       Trace(-z*3, vnormalize(<CoordX, CoordY, 3>), 1);

But that has a sqrt funtion in it so I'm not sure if the three 
optimizations that run with every ray test will be worth it for the 
number of spheres.

I might get around to testing it later.

Post a reply to this message

In article <407e28a2$1@news.povray.org>,
 Daniel Patrick Johnson <zap### [at] hotmailcom> wrote:

> But that has a sqrt funtion in it so I'm not sure if the three 
> optimizations that run with every ray test will be worth it for the 
> number of spheres.

With languages that ultimately get compiled to native code, or some 
which get interpreted on a VM, the square root may be significant. In 
the case of POV script, a simplification in the parsing of the code is 
more likely to help...the cost of the square root is likely lost in the 
noise.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: <chr### [at] tagpovrayorg>
http://tag.povray.org/

Post a reply to this message

> (In this case you also must advance along the ray by a distance of epsilon
> before you actually compute the ray-object intersection or else you'll be
> sometimes hitting the object itself from which the reflected/refracted ray
> was shot.)

Yeah, tell me about it! I had fun just getting shaddow tests to work... 
(In the end, I just excluded the shape itself from the test. Works great 
for a sphere - it can't cast a shaddow on itself - but if I ever manage 
to make a torus or something... *sigh*)

Andrew.

Post a reply to this message