# Optimize a ray-surface interseccion using spheres

2 replies to this topic

### #1nusuto

New Member

• Members
• 1 posts

Posted 31 August 2005 - 01:44 PM

Hello,

we are trying to modify a ray tracer (PovRay) in order to handle directly with point sets.

At the moment, we have a collection of spheres which have colision with each ray and now, we need to evaluate is there is a ray/point_surface_generated intersection inside each sphere.

This is very slow, because we follow the ray ("posible" spheres are sorted according to the distance to the ray origin) and some times (strongly in zones with flat surfaces) the ray intersecs a lot of spheres, but not the surface (it simply goes very close to the surface).

We know that some spheres are more likely to contain an interseccion (according to the distance between the ray and the center of the sphere), but we can not use this directly because when we find an intersection, is posible that this is not the first one (the visible one) and so, we can not stop the search for the present ray.

Is posible that this problem is something tipycal if you work with flat surfaces and spheres..... Does any one have any idea of how to improve this intersection, studying the minimum number of spheres to find the intersection?

Thank you very much ;-).

Nusuto

### #2durban

New Member

• Members
• 9 posts

Posted 06 September 2005 - 10:48 PM

nusuto said:

Hello,

we are trying to modify a ray tracer (PovRay) in order to handle directly with point sets.

At the moment, we have a collection of spheres which have colision with each ray and now, we need to evaluate is there is a ray/point_surface_generated intersection inside each sphere.

This is very slow, because we follow the ray ("posible" spheres are sorted according to the distance to the ray origin) and some times (strongly in zones with flat surfaces) the ray intersecs a lot of spheres, but not the surface (it simply goes very close to the surface).

We know that some spheres are more likely to contain an interseccion (according to the distance between the ray and the center of the sphere), but we can not use this directly because when we find an intersection, is posible that this is not the first one (the visible one) and so, we can not stop the search for the present ray.

Is posible that this problem is something tipycal if you work with flat surfaces and spheres..... Does any one have any idea of how to improve this intersection, studying the minimum number of spheres to find the intersection?

Thank you very much ;-).

Nusuto

Seperate your level up ie. When a character walks into zone X, only test the intersections in zone X.

### #3Reedbeta

DevMaster Staff

• 5308 posts
• LocationSanta Clara, CA

Posted 07 September 2005 - 03:34 AM

Try using an octree to subdivide your point set. When the ray passes through multiple octree cells, sort the cells by distance and proceed from nearest to farthest cell when testing against the individual spheres. This should help somewhat, although there will still be cases when the ray passes close to a surface and takes a long time to intersect.
reedbeta.com - developer blog, OpenGL demos, and other projects

#### 1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users