Re: [Algorithms] Kinematic Collision

[Pierre T. <pie...@gm...>]

>
> Requiring a seperate query to test for initial intersection seems very
> wasteful, since you are going to have to traverse the
> broadphase/midphase structures twice as often as otherwise.


Well it depends on a lot of things, including "irrelevant" bits like
implementation details. For example:

- if this is really only used (and useful) for the "initial intersection",
then it doesn't really matter that you traverse the BP structure twice. At
least you pay the price only once when it is useful, rather than all the
time "just in case" somebody needs the results.

- with the implementation we had, providing a correct depenetration vector
*was* more expensive than not doing so. Hence, we decided not to run that
often-useless-code all the time.

Anyway I don't think there is a real clear best answer here, as usual with
middleware. Best approach depends on your game\usage patterns\etc, and
approach A will please a group of people and piss off another group, which
would prefer approach B.


> Also I think the depenetration vector is the important part... I guess
> you could perform some sort of binary search to depenetrate but that
> seems error prone and expensive.
>

No, binary searches suck for this. In our case there was clearly a set of
functions missing from the API.

The depenetration vector is the important part... sometimes :) Again, it
really depends on your game requirements. I would say it's the important
part to expose in a middleware because that's the part which would be
difficult for users to re-implement, in any case!


>
> I dont think it is terribly difficult to provide depenetration results,
> the way I do it is detect initial penetration and if detected compute
> the direction of least penetration and perform another sweep(with just
> the relevant parts of the objects) to determine the depentration
> distance. It probably amounts to 50 lines of code per sweep test, which
> could be easily disabled with a flag if not needed.
>

Unless something really changed in the 2 years I spent outside of the
physics world, computing a good depenetration vector was not so easy. I mean
last time I checked, EPA was bloody painful to implement and not terribly
reliable, SAT-based approaches were easy to implement but not very fast or
scalable, and anything involving arbitrary triangle meshes was a nightmare
because "simply" computing depenetration vectors for each triangle
individually was next to useless. Maybe I'm missing something here. In any
case *not* running any of those algorithms was certainly faster than doing
so, in the context of a character controller. So that's what we did.

(I'm travelling atm so I may have missed a few posts. Brb!)