How can I create a collision detection routine? More specifically, what
do I look at to determine if two objects have collided in pov-space ? I
can figure it out with...say... unit spheres, that is easy, but what
about rotated cubes and more oddly shaped objects??

thank you


paul
-- 



--------------------------------------------------}
Paul Daniel Jones
The Pennslyvania State University

pdj### [at] psuedu
http://research.chem.psu.edu/glassgrp/paul

       C            The way is near, but men
     // \           seek it afar. It is in the
    N    N          easy things, but men seek it
    |    ||         in the difficult things.
    C    C          -Menicius
     \\  /
       C
--------------------------------------------------}

Post a reply to this message

Paul Jones wrote:
> 
> How can I create a collision detection routine? More specifically, what
> do I look at to determine if two objects have collided in pov-space ? I
> can figure it out with...say... unit spheres, that is easy, but what
> about rotated cubes and more oddly shaped objects??
> 

In general that's a very difficult task, one method would be doing a lot
of tests with 'trace'.  

Finding out whether two boxes collide could for example be done by
'tracing' along all their edges.  

Christoph

-- 
Christoph Hormann <chr### [at] gmxde>
IsoWood include, radiosity tutorial, TransSkin and other 
things on: http://www.schunter.etc.tu-bs.de/~chris/

Post a reply to this message

On Thu, 22 Feb 2001 16:27:45 +0100, Christoph Hormann wrote:
>In general that's a very difficult task, one method would be doing a lot
>of tests with 'trace'.  

In general, it's an impossible task.  The best you can do is an 
approximation.  For example, try to determine whether the intersection 
of two complex CSG objects is nonempty.

>Finding out whether two boxes collide could for example be done by
>'tracing' along all their edges.  

Even that wouldn't see the special case where one box is entirely enclosed
by the other box.

-- 
Ron Parker   http://www2.fwi.com/~parkerr/traces.html
My opinions.  Mine.  Not anyone else's.

Post a reply to this message

Christoph Hormann wrote:
> 
> Paul Jones wrote:
> >
> > How can I create a collision detection routine? More specifically, what
> > do I look at to determine if two objects have collided in pov-space ? I
> > can figure it out with...say... unit spheres, that is easy, but what
> > about rotated cubes and more oddly shaped objects??
> >
> 
> In general that's a very difficult task, one method would be doing a lot
> of tests with 'trace'.
> 
> Finding out whether two boxes collide could for example be done by
> 'tracing' along all their edges.

You can limit the number of traces necessary if you first find the
min_extent and max_extent of your objects.  If these don't overlap, then
your objects don't touch one another.  If they do, then you have to
start tracing along the side(s) where the bounding boxes overlap.

Note: You need MegaPOV to do this.

-- 
Francois Labreque |   //\\    Wear an ASCII ribbon!
    flabreque     |  ||  ||   
        @         |   \\//    Support the campain
   videotron.ca        \\     against HTML e-mail
                      //\\    and news!

Post a reply to this message

In article <slr### [at] fwicom>, ron### [at] povrayorg 
wrote:

> Even that wouldn't see the special case where one box is entirely enclosed
> by the other box.

But you could use eval_pattern() with the object pattern to catch this 
case...you would still need to use trace() though, because there are 
cases when two boxes intersect but all of their corners are outside.

And if you use a similar method to do collision with meshes, you could 
tesselate (almost) any object with the tesselation patch and use the 
resulting mesh for collision testing. It would be slow (a patch might be 
needed to get a useable speed, like a "objects_intersect(ObjectA, 
ObjectB, ...ObjectX) function), but you could speed it up a little by 
using low-resolution meshes, either as a bounds test or for the actual 
collision detection.

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

Ron Parker wrote:
> 
> In general, it's an impossible task.  The best you can do is an
> approximation.  For example, try to determine whether the intersection
> of two complex CSG objects is nonempty.

As long as the shapes are basic mathematical objects (like sphere,
cylinder, box, etc.) it is possible to find an precise solution.  Of
course if the objects are approximated themselves (like isosurfaces) it is
not.

> 
> >Finding out whether two boxes collide could for example be done by
> >'tracing' along all their edges.
> 
> Even that wouldn't see the special case where one box is entirely enclosed
> by the other box.
> 

All right, as Chris Huff mentioned you could use eval_pattern and the
object pattern (maybe it would be a good idea to make the Inside_Object()
function available in POV script just like trace()).

Christoph

-- 
Christoph Hormann <chr### [at] gmxde>
IsoWood include, radiosity tutorial, TransSkin and other 
things on: http://www.schunter.etc.tu-bs.de/~chris/

Post a reply to this message

On Thu, 22 Feb 2001 11:06:32 -0500, Chris Huff wrote:
>And if you use a similar method to do collision with meshes, you could 
>tesselate (almost) any object with the tesselation patch and use the 
>resulting mesh for collision testing. It would be slow (a patch might be 

But that is, as I said, an approximation.

-- 
Ron Parker   http://www2.fwi.com/~parkerr/traces.html
My opinions.  Mine.  Not anyone else's.

Post a reply to this message

On Thu, 22 Feb 2001 17:19:18 +0100, Christoph Hormann wrote:
>As long as the shapes are basic mathematical objects (like sphere,
>cylinder, box, etc.) it is possible to find an precise solution.  Of
>course if the objects are approximated themselves (like isosurfaces) it is
>not.

Isosurfaces can be viewed as basic mathematical objects for the sake of
this exercise, since the approximation is purely visual.  The problem
of determining whether two "basic mathematical objects" overlap reduces
to a simple matter of solving a set of simultaneous equations and looking
for solutions within given ranges.  Unfortunately, the equations you're
solving aren't necessarily linear or even polynomial.  Presumably it's
possible to solve such a system for any given combination of objects
(though not necessarily) but it's either impossible or ridiculously 
difficult to automate the process for any two arbitrary objects.

-- 
Ron Parker   http://www2.fwi.com/~parkerr/traces.html
My opinions.  Mine.  Not anyone else's.

Post a reply to this message

Ron Parker wrote:
> 
> Isosurfaces can be viewed as basic mathematical objects for the sake of
> this exercise, since the approximation is purely visual.  The problem
> of determining whether two "basic mathematical objects" overlap reduces
> to a simple matter of solving a set of simultaneous equations and looking
> for solutions within given ranges.  Unfortunately, the equations you're
> solving aren't necessarily linear or even polynomial.  Presumably it's
> possible to solve such a system for any given combination of objects
> (though not necessarily) but it's either impossible or ridiculously
> difficult to automate the process for any two arbitrary objects.
> 

Seems you are right if you want to make it work for any CSG.  Anyway if
you only need the objects themselves (or unions) it could be reduced to a
set of independent equations.  

After all, whether you need a numerical approximation to solve the problem
is not important in this case.  

Christoph

-- 
Christoph Hormann <chr### [at] gmxde>
IsoWood include, radiosity tutorial, TransSkin and other 
things on: http://www.schunter.etc.tu-bs.de/~chris/

Post a reply to this message

Chris Huff wrote:
> 
> And if you use a similar method to do collision with meshes, you could
> tesselate (almost) any object with the tesselation patch and use the
> resulting mesh for collision testing. It would be slow (a patch might be
> needed to get a useable speed, like a "objects_intersect(ObjectA,
> ObjectB, ...ObjectX) function), but you could speed it up a little by
> using low-resolution meshes, either as a bounds test or for the actual
> collision detection.
> 

One could also use the brute force method using eval_pattern on the object
patterns of the two objects in a fine parallel raster...

I'm not even sure if that's slower, because tesselation is not needed.  

Christoph

-- 
Christoph Hormann <chr### [at] gmxde>
IsoWood include, radiosity tutorial, TransSkin and other 
things on: http://www.schunter.etc.tu-bs.de/~chris/

Post a reply to this message