Sphere collisions with BSP
neuco1
>>Anyone know a quick and dirty way to determine if a sphere at point A,
>>with radius R, traveling to point B, collides with a BSP tree?
>>
>>Brian
Brian - Since it is a sphere, just compute the distance of the center(oid) of the
circle to each of the surfaces. It is a SINGLE check for each sphere
(you can ignore all of it's faces since you are using a sphere approximation)
Peter Kovach
Jim Bucher
>
> Anyone know a quick and dirty way to determine if a sphere at point A,
> with radius R, traveling to point B, collides with a BSP tree?
How about
if B dot planeNormal + R > planeDistance then it collided
Brian Hook
This is only checking against a single plane. Sure, I can go through and do a brute
force check on each plane, but that gets rid of the biggest advantage of BSP trees,
that being they allow for a quick method of determing what region a point is in. The
hard part is going from a point to a sphere (whose centroid can be in one region but
whose extents can extend into others).
Not only that, but I don't need to see if a single sphere is colliding, I have to see
if the PATH the sphere creates (a cylindrical volume with hemispherical ends) collides
with anything during travel.
Not as trivial a problem as I would like.
Brian
Brian Hook
> circle to each of the surfaces. It is a SINGLE check for each sphere
> (you can ignore all of it's faces since you are using a sphere approximation)
This is only checking against a single plane at a time. Sure, I can go through and do a
brute force check on each plane, but that gets rid of the biggest advantage of BSP trees,
that being they allow for a quick method of determing what region a point is in. The
hard part is going from a point to a sphere (whose centroid can be in one region but
whose extents can extend into others).
Not only that, but I don't need to see if a single sphere is colliding, I have to see if
the PATH the sphere creates (a cylindrical volume with hemispherical ends) collides with
anything during travel.
Brian
Tim Sweeney
>center(oid) of the circle to each of the surfaces. It is a SINGLE
>check for each sphere (you can ignore all of it's faces since you are
>using a sphere approximation)
Though this seems to be the correct solution at first glance, it's only
an approximation. It overstates collision with convex edges. To get an
exact solution, you need to either use spherical subdivision or handle
convex volume edges and vertices. A better approach is probably "Don't
try to do that". :-)
-Tim
Brian Hook
>
> In article <31D19E...@netcom.com>, Brian Hook <b...@netcom.com> wrote:
> >Anyone know a quick and dirty way to determine if a sphere at point A,
> >with radius R, traveling to point B, collides with a BSP tree?
> >
>
> This is more dirty than quick, but traverse the tree with A, then with B.
> if the traversals are different, there is an intersection.
This won't work. For starters, just because two points are in different regions doesn't
necessarily imply a collision (eg. they can have a splitting plane between them that doesn't
have any polygons in the line of intersection). It also doesn't tell you WHERE the collision
occured, which is important.
Brian
Steve Keith Capell
The technique that Brian is after is actually quite doable as long as
there are mechanisms in place to avoid performing the heavy calculations
on each polygon (the BSP tree is a step in the right direction).
To find collisions between the hotdog shaped moving sphere (following
a linear path) and a polygon (the way I do it anyway) there are three cases.
a) The sphere hits the polygon tangent to the plane.
b) The sphere hits an edge, tangent to the edge.
c) The sphere hits a vertex.
Note that a -> !b & !c, which speeds things up a bit.
Otherwise you have to look at the collisions from b and c and sort them
out in time.
All three of these cases involve finding the roots of a quadratic
equation in t. There are also geometric solutions but it is harder to
find the exact time of collision using these techniques (as far as I know).
All three equations are of the form d(t) = D = distance squared from object.
Deriving (c) is the easiest. Case (a) involves thinking about what is
going on in the dimension normal to the plane. Case (b) involves thinking
about what the projection of the center of the sphere on the edge is doing.
Case (a) requires that, once you've found a collision with the plane,
you see if the collision point is inside the polygon, for which there
are fast algorithms used in ray tracing etc.
The roots of d(t) - D are the times of or contact that are of interest, of
which only the first is probably relevant.
Using this scheme with BSP is straight-forward. Use the above technique
on each node. If there is a collision, you'll have to traverse both
children to look for earlier collisions. If there is no collision
see which side of the plane the hotdog is on (testing the initial position
of the sphere will suffice) and traverse that subtree.
Of course if you have a large BSP tree you'll want better culling mechanisms.
BTW, I've implemented this in a real time game (not on the shelves yet though).
The important thing is to not do very much of the heavy math. I use a lot
of bounding box tests to make sure that very few quadratics must be solved
per frame.
Hope this helps!
Steve Capell.
--
-Steve Keith Capell (cap...@cc.gatech.edu)
Bretton Wade
# have to see
# if the PATH the sphere creates (a cylindrical volume with hemispherical
# ends) collides
# with anything during travel.
#
# Not as trivial a problem as I would like.
Want a really non-trivial answer?
In order to make this problem a simple ray intersection problem, as it
seems most people would like to do, you have to CONVOLVE the world with
the shape you want to collide against. In this case, you have to convolve
the world with a sphere.
Obviously, convolving a bsp tree with a sphere does not yield pretty
geometry, but it's not as bad as you might think at first. You have three
cases to deal with:
1. Planes
2. Vertices
3. Edges
Planes are easy. Move them out along the normal vector the radius of the
sphere. This has already been suggested at least three times here.
Vertices are also fairly easy, but may require some additional
preprocessing. To intersect a sphere with a vertex, you change to problem
to a ray/sphere intersection. The time of intersection will be the same in
either case. The additional preprocessing you have to do is to find the
convex vertices, because concave vertices will never be hit before a
plane, edge, or convex vertex. This will save you work in the long run.
Edges are an extension of the vertex problem. Now you do a ray/cylinder
intersection, where the cylinder is oriented on the axis defined by the
edge. Again, only convex edges need be considered.
After you have tested all three of these cases, and kept the one with the
first intersection time, you have found the intersection time of the
sphere and the world.
The problem is similar if you just want to test for containment, but
probably not quite as hairy, overall.
neuco1
Since he stated it was a sphere, there could NOT be any overstating of
convex edges since since there are none on a sphere. If he wants to NOT use a
sphere approximation, which goes against what was originally stated, I agree that
this would not be the desirable solution.
In <31D31D...@epicgames.com>, Tim Sweeney <t...@epicgames.com> writes:
>> Brian - Since it is a sphere, just compute the distance of the
>>center(oid) of the circle to each of the surfaces. It is a SINGLE
>>check for each sphere (you can ignore all of it's faces since you are
>>using a sphere approximation)
>
>Though this seems to be the correct solution at first glance, it's only
>an approximation. It overstates collision with convex edges. To get an
>exact solution, you need to either use spherical subdivision or handle
>convex volume edges and vertices. A better approach is probably "Don't
>try to do that". :-)
>
>-Tim
Andrea Griffini
Brian Hook <b...@netcom.com> wrote:
>> Brian - Since it is a sphere, just compute the distance of the center(oid) of the
>> circle to each of the surfaces. It is a SINGLE check for each sphere
>> (you can ignore all of it's faces since you are using a sphere approximation)
>This is only checking against a single plane at a time. Sure, I can go through and do a
>brute force check on each plane, but that gets rid of the biggest advantage of BSP trees,
>that being they allow for a quick method of determing what region a point is in. The
>hard part is going from a point to a sphere (whose centroid can be in one region but
>whose extents can extend into others).
You can use the following logic
1) k=dot(point,normal)-distance
2) if k<-r go only int the negative tree
3) if k>r go only in the positive tree
4) else check this node polygons and the recurse both
>Not only that, but I don't need to see if a single sphere is colliding, I have to see if
>the PATH the sphere creates (a cylindrical volume with hemispherical ends) collides with
>anything during travel.
That is more much complex imo... i resorted to use a different
approach for collision detection that needs only sphere tests
>Brian
~~~~~~~~~~~~~~~~~~~\
Andrea Griffini \ agr...@ix.netcom.com
programmer \ http://www.netcom.com/~agriff
\________________________________