Is it possible the write a code that tells wether two CSG objects intersect
or not? (min_extent and max_extent dont work on CSG objects)
Think of a "wireframe" cube with a little sphere in the middle. Normally
they do not intersect, so their intersection supposed to be the void object
or something the like. So, how do you test if they intersect or not?

Post a reply to this message

archie <arc### [at] hotmailcom> wrote:
> Is it possible the write a code that tells wether two CSG objects intersect
> or not?

  Nope.

  Intersection testing is one of the big problems in CG. You can
make approximations, but an exact method for any object can be
extremely difficult, if not impossible.

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

archie wrote:
> 
> Is it possible the write a code that tells wether two CSG objects intersect
> or not? 

Not in the general case.  You can of course test it in some special
situations (simplest being the test whether two spheres intersect).

(min_extent and max_extent dont work on CSG objects)

That's not true, min_extent and max_extent work for all finite objects. 
Of course they won't help you finding out if the objects actually
intersect.

> Think of a "wireframe" cube with a little sphere in the middle. Normally
> they do not intersect, so their intersection supposed to be the void object
> or something the like. So, how do you test if they intersect or not?

Simply doing 'trace()' along the edges of the wireframe on the sphere
should be sufficient in this case (assuming that the wireframe lines are
very thin).

Christoph

-- 
POV-Ray tutorials, IsoWood include,                 
TransSkin and more: http://www.tu-bs.de/~y0013390/  
Last updated 13 Aug. 2002 _____./\/^>_*_<^\/\.______

Post a reply to this message

Yeah, thank you guys. I actually need to calculate the fractal dimension
(Hausdorf-Besicovich dimension) of a 3D object, so I need to divide a 3D
object (ANY object) in smaller and smaller cubes, and test the intersection
of the object with the cubes. I need that (badly) for a project at school.
I thought it would be easy to do it in pov-ray, but life is'nt so easy...

Post a reply to this message

In article <web.3d8cf65cb7cda85de1d0c2220@news.povray.org>,
 "archie" <arc### [at] hotmailcom> wrote:

> Yeah, thank you guys. I actually need to calculate the fractal dimension
> (Hausdorf-Besicovich dimension) of a 3D object, so I need to divide a 3D
> object (ANY object) in smaller and smaller cubes, and test the intersection
> of the object with the cubes. I need that (badly) for a project at school.
> I thought it would be easy to do it in pov-ray, but life is'nt so easy...

If edge intersection is fine, use trace() along each edge of the cube. 
If trace() returns an intersection closer than the length of the edge, 
the shape intersects the cube.

If you need to detect cases where the shape penetrates a cube face but 
not an edge, you can't do it exactly, but you can approximate it by 
tracing rays along each face of the cube. This will be slow, so you 
probably will want to check if the bounding boxes interpenetrate first.

This leaves cases where the shape entirely contains the cube or where 
the cube entirely contains the shape. Assuming the surface of the shape 
contains a single volume (shapes such as isosurfaces, blobs, meshes, or 
CSG don't necessarily have this property), just check the corners of the 
shape's bounding box for insideness with the cube, and the corners of 
the cube for insideness with the shape. If the shape surface doesn't 
intersect the cube surface, it must either be entirely inside the cube 
or containing it, so checking a single corner from the cube should do.

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

On Sat, 21 Sep 2002 18:45:05 EDT, "archie" <arc### [at] hotmailcom>
wrote:

>Yeah, thank you guys. I actually need to calculate the fractal dimension
>(Hausdorf-Besicovich dimension) of a 3D object, so I need to divide a 3D
>object (ANY object) in smaller and smaller cubes, and test the intersection
>of the object with the cubes. I need that (badly) for a project at school.
>I thought it would be easy to do it in pov-ray, but life is'nt so easy...

Maybe using an object_pattern can solve your problem?


Peter Popov ICQ : 15002700
Personal e-mail : pet### [at] vipbg
TAG      e-mail : pet### [at] tagpovrayorg

Post a reply to this message

On Sat, 21 Sep 2002 12:05:42 EDT, "archie" <arc### [at] hotmailcom> wrote:
> Is it possible the write a code that tells wether two CSG objects intersect
> or not? (min_extent and max_extent dont work on CSG objects)
> Think of a "wireframe" cube with a little sphere in the middle. Normally
> they do not intersect, so their intersection supposed to be the void object
> or something the like. So, how do you test if they intersect or not?

Others already answered You that there is no general solution. But there is
also another method not mentioned yet. Since months I have this solution
bookmarked to be written some day as include macro, perhaps as part of iso_csg
library. There are a few algorithms of finding minimum of function based on
sampling of function. So when you can write your csg as iso_csg combination
then you can use one of those optimized algorithms to find location of
minimum. Then you can check value of this minimum and answer if it is lower
than zero which means inside of csg object.

ABX

Post a reply to this message