 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
I have a "fully" working path tracer under development. The next thing
to implement is transformations (at least translate and rotate). What is
the best (fastest) way to do it?
Let's take box for example. Now I have a method for calculating
axis-aligned box intersections. So if I rotate the box how should I
proceed?
I was thinking that maybe I should not rotate the box, but rotate the
ray so that I can use the fast AABox intersection routines. And then I
get intersection point and surface normal, which I rotate back to world
space?
Am I missing something here and is the the best way to do it?
Thanks.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Severi Salminen escribió:
> I have a "fully" working path tracer under development. The next thing
> to implement is transformations (at least translate and rotate). What is
> the best (fastest) way to do it?
>
> Let's take box for example. Now I have a method for calculating
> axis-aligned box intersections. So if I rotate the box how should I
> proceed?
>
> I was thinking that maybe I should not rotate the box, but rotate the
> ray so that I can use the fast AABox intersection routines. And then I
> get intersection point and surface normal, which I rotate back to world
> space?
>
> Am I missing something here and is the the best way to do it?
As far as I know, the way POV-Ray does it (and probably most others) is
by creating a transformation matrix of all the individual
transformations, then inversing it, and using it to transform *rays*
before doing the intersection calculations.
But don't trust me on this. I still haven't managed to solve the
ray-sphere intersection equation...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Nicolas Alvarez wrote:
> As far as I know, the way POV-Ray does it (and probably most others) is
> by creating a transformation matrix of all the individual
> transformations, then inversing it, and using it to transform *rays*
> before doing the intersection calculations.
I believe that is correct. (Transforming the object equation would be
much harder...)
> But don't trust me on this. I still haven't managed to solve the
> ray-sphere intersection equation...
Suppose you have a sphere with center C [a vector] and radius r [a
scalar]. The equation for this is
(P - C)^2 - r^2 = 0
(Where squaring a vector *really* means taking the dot product of the
vector with itself.) Here P is your unknown - but it's a vector. If we
replace that with the ray equation
Ray(t) = Dt + S
then we obtain
(Dt + S - C)^2 - r^2 = 0
If we set V = S - C then we have
(Dt + V)^2 - r^2 = 0
and expanding we find
D^2t^2 + 2VDt + V^2 - r^2 = 0
Writing "#" to explicitly mean "dot product", what I really mean is
(D # D) t^2 + 2 (V # D) t + (V # V) - r^2 = 0
Notice this is a quadratic in one unknown - t, a scalar. In fact, what
we have is
a t^2 + b t + c = 0
where
a = D # D
b = 2 (V # D)
c = (V # V) - r^2
Solving this yields a value for t which satisfies the equation. If you
substitute this t back into the original ray equation, it gives you a
point in space for the intersection.
Notice that if you compute multiple intersections, the one with the
lowest value for t is guaranteed to be the "front" one [assuming that S
is the "start point" of the ray. Oh, and if t is negative, the
intersection is "behind" the camera or whatever, and you should ignore
that intersection...]
Any clearer? ;-)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 wrote:
>> As far as I know, the way POV-Ray does it (and probably most others)
>> is by creating a transformation matrix of all the individual
>> transformations, then inversing it, and using it to transform *rays*
>> before doing the intersection calculations.
>
> I believe that is correct. (Transforming the object equation would be
> much harder...)
Ok, then I was on the right tracks. I only have to transform the ray
using conventional point and vector transformations. Thanks!
>> But don't trust me on this. I still haven't managed to solve the
>> ray-sphere intersection equation...
There is neat method also Pov-Ray uses. I used almost identical but
Pov's version had (IIRC) simpler form with 1-2 less arithmetic
operations. Here is my implementation:
"position" is the center of the sphere
"origin" and "direction" specify the ray
"nearestPointDistance" is the distance from origin to a point where the
ray is closest to the sphere
"halfCord2" is the square of...well...half of the cord the ray creates
inside the sphere :)
If you draw this on a paper it is very simple approach and quite fast,
too. It returns the distance to the closest intersection point.
double Mass::intersect(Vector origin, Vector direction) const
{
Vector relPosition = position - origin;
double radius2 = radius * radius;
double nearestPointDistance = relPosition*direction;
double halfChord2 = radius2 - relPosition*relPosition +
nearestPointDistance*nearestPointDistance;
if(halfChord2 > 0.0)
{
double nearPoint = nearestPointDistance - sqrt(halfChord2);
double farPoint = nearestPointDistance + sqrt(halfChord2);
if(nearPoint > EPSILON)
return nearPoint;
else
return farPoint;
}
else
return -1.0;
}
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 escribió:
> Any clearer? ;-)
Thanks; shows I'm still too noob for this kind of things.
(that's a no)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Nicolas Alvarez <nic### [at] gmail isthebestcom> wrote:
> As far as I know, the way POV-Ray does it (and probably most others) is
> by creating a transformation matrix of all the individual
> transformations, then inversing it, and using it to transform *rays*
> before doing the intersection calculations.
That's the reason why you can't, for example, scale something by 0.
Inverting that matrix would result in a division by 0.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> double Mass::intersect(Vector origin, Vector direction) const
> {
> Vector relPosition = position - origin;
> double radius2 = radius * radius;
> double nearestPointDistance = relPosition*direction;
>
> double halfChord2 = radius2 - relPosition*relPosition +
> nearestPointDistance*nearestPointDistance;
>
> if(halfChord2 > 0.0)
> {
> double nearPoint = nearestPointDistance - sqrt(halfChord2);
> double farPoint = nearestPointDistance + sqrt(halfChord2);
> if(nearPoint > EPSILON)
> return nearPoint;
> else
> return farPoint;
> }
> else
> return -1.0;
> }
Is this what POV-Ray actually uses for the intersection of a ray and a
sphere? I just spent half an hour working out both the geometrical
interpretation of this and its equivalence to the result of the quadratic
equation with the coefficients that Andrew posted, and I'm really impressed
at how simple it is. And annoyed at the fact that I never could have come up
with it myself =)
- Slime
[ http://www.slimeland.com/ ]
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Severi Salminen <sev### [at] notthissaunalahtifiinvalid> wrote:
> double nearPoint = nearestPointDistance - sqrt(halfChord2);
> double farPoint = nearestPointDistance + sqrt(halfChord2);
Perhaps you shouldn't rely on the ability of the compiler to realize
that the exact same sqrt() is being performed here, and instead calculate
it only once into a variable. That way you remove the risk of the
code actually calculating the slow sqrt() twice for no reason.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> That's the reason why you can't, for example, scale something by 0.
> Inverting that matrix would result in a division by 0.
Presumably it would also result in an invisible object too though. ;-)
Does POV-Ray actually apply all the matricies and invert only the final
one? Or does it construct them in inverted form in the first place?
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> Perhaps you shouldn't rely on the ability of the compiler to realize
> that the exact same sqrt() is being performed here, and instead calculate
> it only once into a variable. That way you remove the risk of the
> code actually calculating the slow sqrt() twice for no reason.
>
Good point, thanks for the suggestion. I checked the assembly output and
g++ produces better results with a temporary variable. Less code and
less jumps. Few questions:
1. I understand that sqrtsd takes the square root. What does "call sqrt"
do? Calls a subroutine called "sqrt"? Why on earth are they both needed?
The version with temp variable used one "call sqrt" and the original
version used 2 calls. And both had one sqrtsd.
2. What does "ucomisd %xmm0, %xmm0" effectively do? It compares the same
register.
(Last time I really programmed assembly was 10 years ago when I did a
burning flame demo program..."
Anyway, this was the best version:
double halfChord = sqrt(halfChord2);
double a = nearestPointDistance - halfChord;
if(a > EPSILON)
return a;
else
return nearestPointDistance + halfChord;
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Slime wrote:
> Is this what POV-Ray actually uses for the intersection of a ray and a
> sphere? I just spent half an hour working out both the geometrical
> interpretation of this and its equivalence to the result of the quadratic
> equation with the coefficients that Andrew posted, and I'm really impressed
> at how simple it is. And annoyed at the fact that I never could have come up
> with it myself =)
Yeah, Pov uses the exact same method. It is very simple and fast method.
Pov also has one additional check, which I'm not sure is worth it. POV
also returns both hits always. I only return the hit in front of the
ray. I have no use for the other.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Severi Salminen wrote:
> Yeah, Pov uses the exact same method. It is very simple and fast method.
> Pov also has one additional check, which I'm not sure is worth it. POV
> also returns both hits always. I only return the hit in front of the
> ray. I have no use for the other.
It's used for CSG. (E.g., if you "difference" the sphere against
something else, the "back" intersection might actually be where the
solid surface begins.)
[Mutters something about Haskell and lazy evaluation...]
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] devnull> wrote:
> Warp wrote:
> > That's the reason why you can't, for example, scale something by 0.
> > Inverting that matrix would result in a division by 0.
> Presumably it would also result in an invisible object too though. ;-)
Not if you scale by 0 on only one axis.
> Does POV-Ray actually apply all the matricies and invert only the final
> one? Or does it construct them in inverted form in the first place?
IIRC it calculates the inverted matrices when parsing and uses them
when rendering.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Presumably it would also result in an invisible object too though. ;-)
>
> Not if you scale by 0 on only one axis.
Ah, good point...
>> Does POV-Ray actually apply all the matricies and invert only the final
>> one? Or does it construct them in inverted form in the first place?
>
> IIRC it calculates the inverted matrices when parsing and uses them
> when rendering.
I thought that would be the case.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Fri, 14 Mar 2008 11:41:35 +0200, Severi Salminen wrote:
> 2. What does "ucomisd %xmm0, %xmm0" effectively do? It compares the same
> register.
Checks whether the low double precision floating point value
in the register is (non-)zero.
In the SSE architecture, an instruction such as "por" does not affect
the flags, so the familiar x86 way of "or eax, eax" to set flags would
not work on SSE.
--
Joel Yliluoma - http://iki.fi/bisqwit/
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> It's used for CSG. (E.g., if you "difference" the sphere against
> something else, the "back" intersection might actually be where the
> solid surface begins.)
Hmm. I still don't get it. Why should I ever need to trace the ray in
the "wrong direction"?
The ray starts at camera and goes forward. If anything interesting is
found, it is in front of the ray, right? And the only exception is if
the camera is inside an object. But even then: shouldn't it be enough to
trace forward. Please enlighten me :)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Severi Salminen wrote:
> Invisible wrote:
>
>> It's used for CSG. (E.g., if you "difference" the sphere against
>> something else, the "back" intersection might actually be where the
>> solid surface begins.)
>
>
> Hmm. I still don't get it. Why should I ever need to trace the ray in
> the "wrong direction"?
>
> The ray starts at camera and goes forward. If anything interesting is
> found, it is in front of the ray, right? And the only exception is if
> the camera is inside an object. But even then: shouldn't it be enough to
> trace forward. Please enlighten me :)
You will never need an intersection from *behind* the camera.
However, a ray typically intersects a sphere in two places. POV-Ray
generates both points of intersection because you might need them both.
(E.g., if the object is transparent, you'll want to trace a ray out of
it. If the object is involved in CSG with other objects, the "back"
surface might actually be the first visible surface. etc.)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 wrote:
> However, a ray typically intersects a sphere in two places. POV-Ray
> generates both points of intersection because you might need them both.
> (E.g., if the object is transparent, you'll want to trace a ray out of
> it. If the object is involved in CSG with other objects, the "back"
> surface might actually be the first visible surface. etc.)
Ok, but I guess that you can still handle all cases with an intersection
routine that only returns the point in front of the ray?
1. If the object is transparent, you first enter the object and then exit.
2. In CSG the same applies: you still have to first enter all the
participating objects to calculate the outcome.
So this is not something that is mandatory but a convenience?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Severi Salminen wrote:
> So this is not something that is mandatory but a convenience?
Pretty much, yes.
(Although if you're bothering to compute the coefficients of a quadratic
equation, it seems a shame to compute them all over again to find the
second point of intersection...)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 wrote:
> (Although if you're bothering to compute the coefficients of a quadratic
> equation, it seems a shame to compute them all over again to find the
> second point of intersection...)
Well, I use the simplified form I posted to this thread. It is
computationally quite simple. So it all boils down to how often you
actually need the "unneeded" intersection and what is the net effect. I
haven't measured it.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Nicolas Alvarez wrote:
> Orchid XP v7 escribió:
>> Any clearer? ;-)
>
> Thanks; shows I'm still too noob for this kind of things.
>
>
>
> (that's a no)
OK, well because I'm feeling bored, let me try again...
Light travels in essentially straight lines. If we assume a ray starts
at position S and travels parallel to the vector D, we can write
R(t) = Dt + S
That is, the vector D scaled by the scalar t, plus the vector S.
A sphere is the set of all points within a specific distance of a
certain point. So if C is the center of our sphere, and r is the radius
of the sphere, then the sphere consists of all points less than r units
from the point C. We're interested in the *surface* of the sphere, which
is the set of all points *exactly* r units away from C. We can write that as
|P - C| = r
Solving this equation for any vector P gives us the surface coordinates.
But that's not what we're trying to do. We want to know whether any
point in space lines on the surface of the sphere *and* on a given ray.
In other words, solve simultaneous equations. Non-linear ones!
But we'll get to that in a second. First, notice that the dot product of
a vector with itself is equal to the length of that vector squared. In
oter words,
vlength(V) = sqrt(V # V)
That means we can write
sqrt((P - C) # (P - C)) = r
Alternatively, we can avoid the expensive square root operation by
(P - C) # (P - C) = r^2
Finally, with a tiny bit of rearranging, we have
((P - C) # (P - C)) - r^2 = 0
(If the thing on the left *equals* the thing on the right, then
subtracting one from the other must logically result in zero.)
I'm going to be fanciful and write the above in shorthand:
(P - C)^2 - r^2 = 0
It's a slight abuse of notation, but it's less typing.
Now if we replace our unknown point P with our ray equation R(t) we get
(Dt + S - C)^2 - r^2 = 0
If I put X = S - C, we get
(Dt + X)^2 - r^2 = 0
Opening the brackets as per the standard binomial theorum, we have
D^2 t^2 + 2 D X t + X^2 - r^2 = 0
By which of course I actually mean
(D # D) t^2 + 2 (D # X) t + (X # X) - r^2 = 0
This matches the form of the standard quadratic
a t^2 + b t + c = 0
if we set
a = D # D
b = 2 (D # X)
c = (X # X) - r^2
We can now apply the usual formula
t = (-b +/- sqrt(b^2 + 4ac)) / 2a
Assuming that the square root part (the "determinant") is strictly
positive, we obtain two purely-real solutions. These are the values for
t where the ray "enters" and "leaves" the sphere. If the determinant is
negative, that basically means the ray doesn't touch the sphere at all.
Assuming we *do* have an intersection, just calculate
Dt + S
for the two values of t to obtain the actual points of intersection.
Is *that* any clearer? ;-)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
