5 replies to this topic

[goruka]

hi! I am trying to implement collision detection against a BSP tree (for now a point, later I will try dynamic plane shifting for more complex objects)

I've already read this:
http://www.melax.com/bsp/

and pretty much all articles in here.

i already can create a BSP tree out of a legal object without much issues, and doing the simple "point inside/outside bsp" test works fine.

However, i want to check when a point is about to enter a BSP and stop it just before it is inside. This is proving to be very difficult so far... i have:

-current position
-attempted next position

i create a ray (segment) with this, and find an intersection against the BSP,

Once I get the intersection, I dont really know what to do,
-if i place the object in the collision, it ends up inside the BSP (in the plane)
-if i try to make the object go back a bit, it can either still be inside the BSP (due to epsilon-test value for inside a plane and the angle against that same colliding plane) or it can go back too much (if the value is too big) and visually bounce. Trying to find an intermediate "go back amount" seems to hackish..

Keep in mind I'm doing this as a hobby project for the nintendo DS, so I really can't use anything that is too CPU intensive.

Cheers, and thanks a lot!

[Reedbeta]

What you want to do is find the intersection point with the plane and then slide the object along the plane from there. One way to do it is to see if the endpoint of the segment is in solid space (i.e. behind the plane) and if so, project it to the nearest point on the plane surface. You have to be careful with thin walls though, as a fast moving object could have its endpoint on the other side of the wall in free space. Also, corners are tricky with this approach.

[goruka]

Reedbeta said:

What you want to do is find the intersection point with the plane and then slide the object along the plane from there.

I thought about this, but then I realized it can be very difficult in a situation like this object (moving in arrow direction, and arrow is outside the BSP and about to crash witht he upper wall)

\
--> \
--------

If i slide along the collision plane, it will push me against another wall (the bottom wall in this case), that is no good.. I'd have to do the check again against that other wall, which may also push me back against the other wall.... is there any simple way to fix this?

[goruka]

goruka said:

\
--> \
--------

Sorry, forgot that html strips spaces.. I guess to simplify, something like this:

-->\
-----

[Reedbeta]

Like I said, corners are tricky. One thing you can do is iteration. Push the object out of one wall, then push it out of the other, then repeat the process some number of times or until the object's not in either wall. I think this is actually guaranteed to converge given certain conditions. Take a look at some of the papers by David Baraff, as he has done a lot of work on computational rigid body mechanics.

[goruka]

Reedbeta said:

Like I said, corners are tricky. One thing you can do is iteration. Push the object out of one wall, then push it out of the other, then repeat the process some number of times or until the object's not in either wall.

Hmm this kind of sucks, performance-wise , although i really see for now no other way to do it... as said, my priority is that it runs on a DS..
maybe i can just "sum" the pushback-vectors or something, so it's enough with one iteration.. ?

My other alternative, as I saw in a few papers, was binary-like search for the no-collision moment.. but this is also a CPU hog :\