Ray Sphere or Ray Box.. which is faster to test?

[johnsa]

Hey,

I've been looking for some different intersection tests, and I basically need two variations, one which simply tests if a given ray intersects a bounding volume at all (for BVH) and one that returns the actual x/y/z of the intersection once it gets right down to a primitive.
I'm trying to see which is faster, sphere or bounding boxes, given that the bulk of the operations will be simple yes/no tests..

I have this so-far for a sphere:

Code Select Expand


        movaps xmm7,(Ray3D PTR [esi]).direction

        movaps xmm0,xmm7
movaps xmm1,(Sphere3D PTR [edi]).center
subps xmm1,(Ray3D PTR [esi]).origin ; xmm1 = EO
dpps xmm0,xmm1,11110001b ; xmm0 = v = EO.V
dpps xmm1,xmm1,11110001b ; xmm1 = EO.EO
mulps xmm0,xmm0 ; xmm0 = v^2
subss xmm1,xmm0 ; xmm1 = ((EO.EO) - v^2)
movss xmm2,(Sphere3D PTR [edi]).rsqr
subss xmm2,xmm1 ; r^2 - ((EO.EO) - v^2)


which should return xmm2 < 0 then no intersection...
I'm not sure if thats 100% right, or if a box test would be faster, possibly for when the actual intersection points are required..

[vanjast]

I'd think a ray-sphere would be quicker as a ray-box requires a fair amount of point rotations and plane intersect testing, whereas with a sphere all you need is the radius vector and a distance test - just thinking aloud  :bg

[FORTRANS]

Hi,

   Axis aligned bounding boxes (AABB) are fast to test.  They
also have the advantage that they can be asymmetric which
can save time on oddly shaped objects.  Finding the intercepts
is easier than that for spheres.

   As vanjast says, testing for a hit on a sphere should be easy.

Regards,

Steve N.

[johnsa]

Thanks,

For what I'm doing i'm favouring speed of the hit test over false-positive hits, it's basically for a BVH which could go down 10-15 levels deep. So for 90% of the tests I only need to know if it's an intersection or not, and only at the very end get the actual intersection point, so I'd think bounding spheres would be the best option.

My major query really around the sphere tests is there seem to be a number of different methods, theres the full algebraic solution with discrimant, then there's a vector projection/take the perpendicular component and see if the sqr. distance is greater than r^2, then there's the method i posted which is based on:

EO = vector from ray origin to sphere center
V = Ray direction
v = dot_product( EO, V )
disc = r^2 - ((dot_product( EO, EO ) - v^2)
if (disc < 0) no intersection
else
d = sqrt(disc)
P = E + (v-d) * V  ; the actual point of intersection

This last method seems to be the least intensive computationally.. and we can avoid the entire else block for the normal intersection tests... I wonder though if the normal algebraic solution is faster though when you want the actual intersection point

[xanatose]

It has being a long time, but if I remember correctly the faster is ray-sphere, followed by ray-aligned_elipsoid  and then ray-AABB.

Better yet, have a treee of spheres (Bigger spheres encompasingg a group of smaller spheres). That way you can reject a lot of objects on one sweep.  Of course, at the end, you will need something that will best represent the form of the object that the ray will be colliding with. OBB, cylinders and elipsoids are good for this.