 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> 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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> 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
|
|
| |
| |
|
|
|
|
| |
