Re: [Algorithms] Colliding against polygon soup

[Conor S. <cs...@tp...>]

Just remembered the mathmatical way of doing the sphere collision tests.

But, anyway, the first thing to do is test if the destination and starting
point (+ the length of the radius in each direction) of the sphere are on
seperate sides of the plane.

The way to find the first collision of a sphere in to a plane is simple.

First we find the value 't' which is the parametric value for the point on
the line between the two end points (the start and destination) in your
collision test (lets call these a and b).

This value t, given the radius r, normal n, scalar d and a and b is

t = (r - n dot a + d)/(n dot (b-a))

Then your new sphere centre point is p = a + t(b-a)

If this point is within the set of planes perpindicular to both the triangle
and on the line of an edge on the triangle, then your collision has occured
and that point is kept.

If not you also find the point where the line p = a + t(b-a) collides with
the triangles plane. Then you test to see if it is within less than radius
distance of any of the planes we tested against before, and if so, you use
centre point generated using the t = (r - n dot a + d)/(n dot (b-a))
equation.

Conor Stokes

> > Boy's gotta make a living.  And since I'm a one man show these days, I
> > can't rely on someone else to handle the icky stuff I've avoided during
my
> > life.  Like collision detection =)
>
> Well, thats understandable. Collision detection is something that a lot of
> people neglect when doing an engine. I know most of the engines I wrote
just
> to show graphics stuff off never bothered with it.
>
> > Sounds pretty straight forward.  Subdivide the soup so that you can
> quickly
> > find a "potentially collidable set", then collide against that set.  The
> > collision against the subset can usually be as simple as a sphere test
> (for
> > a simple environment) vs each triangle I assume?
>
> Yes, thats pretty much the one. Sphere or bounding box.
>
> The hierachy tests are very quick, and remove the majority of the set
> quickly. (This is also a good grounds for visibility).
>
> >
> > Do people sweep the sphere or do they just test the desired destination
> and
> > back off until it no longer penetrates?
>
> Well, a sweep can be used - Another way is a binary style test, where you
> have a set of spheres on the line, and you test the middle sphere point,
and
> see if it collides, and what side of the triangle it is on, and you use
that
> to refine the search for the closest sphere. When you find a sphere that
> collides at all with the triangle, you write a pushing algo. (pushing is a
> nice name for it :)
>
> You take the closest vector between the centre of the sphere, and the
point
> where it intersects the triangle, normalise the vector, then multiply it
by
> the negative length of the radius. The new centre of your sphere is the
> closest point on the triangle from before, plus that vector. You can
> actually hack finding the closest vector by simply making it the closest
on
> the plane. This is a bit of a hack, but much easier than doing a full
test.
>
> Although, the sweep may be better. I've got to remember the maths for that
> now :)
>
> >
> > Yes yes, I'm quite the neophyte, bear with me. =)
>
> Will Do.
>
> Conor Stokes
>