Most efficient method for particle-triangle intersection?

Raytracing will give you a good approximation, but if you're using acceleration/deceleration forces it won't be accurate, not that it really needs to be.

http://www.gamedev.n...sion-detection/

There really isn't much point implementing a physics engine to handle this, unless there is one you need to use for the rest of your game and it happens to support this feature, so just get coding on your own lonesome.

To accurately test the collision however, you need to map the path of the particle as a closed form solution, find the collision point of the particle against the surface on the spline generated by that closed form solution, use the derivative of that solution and get the direction/speed at the time the particle hits the surface, and then handle your particle from there.

http://en.wikipedia....form_expression

Basically a closed form solution is: rather than changing the velocity based off an acceleration, you have an equation that sets the position of the particle as a function of a t-delta, where the equation takes into account the velocity and acceleration of the particle.

When I've used a closed form solution in the past, I just used the position and the derivative to do a ray test. I haven't tried using this on a particle system, but if I were doing a particle system with collisions I would use the closed form solution and all the math to find the proper collision point instead of a position/velocity ray test, but only when the camera was close up, for quality reasons.

I've tried Bullet, but I believe it uses an AABB tree for detection, and I had a hard time getting it to work. Seems like a uniform grid or KD-tree would be a better fit? I don't know though thanks!

What's your problem? If the scene is static, a SAP-based algorithm will work better. See broadphase benchmarks. Bullet also has a raytracer example implemented on top of their raycasting systems. It's relatively well performing in my opinion but in general, massive amounts of queries must be run on the GPU.

Thanks all for the responses.

@Krohm:

What's your problem?
[/quote]
Unfortunately after much testing and stepping through the Bullet code, I determined Bullet never got to the leaf nodes of the AABB tree and hence I couldn't process any of the triangles. I probably was doing something wrong but I couldn't determine what.

If the scene is static, a SAP-based algorithm will work better. See broadphase benchmarks. Bullet also has a raytracer example implemented on top of their raycasting systems. It's relatively well performing in my opinion but in general, massive amounts of queries must be run on the GPU.[/quote]

SAP sounds interesting, unfortunately my triangle mesh is concave, also it sounds like SAP is for convex mesh-to-mesh collisions so would SAP still work for particles against a concave mesh?

@Kyal: Thanks, yeah I couldn't seem to find any other pre-built code that did exactly what I needed.

To accurately test the collision however, you need to map the path of the particle as a closed form solution, find the collision point of the particle against the surface on the spline generated by that closed form solution, use the derivative of that solution and get the direction/speed at the time the particle hits the surface, and then handle your particle from there.
[/quote]
This is a new idea to me, but I'm having a hard time understanding it. So would the spline created from the particle path come from its position and velocity? Then it would be revolved to create something like a capsule shape? Any chance there is a geometric interpretation I might be able to see? I can understand math better visually.

My current plan is to tweak the math used inside the SPH fluid library (currently it only supports simple collision against a box) and change it so the triangle normal was returned instead of the box normal, but maybe I'm oversimplifying the additional complexity added by triangles vs a simple box? I should add that this is a 3rd party SPH library and that I only have a rudimentary knowledge of the math it's using. Thanks for the help I appreciate it!

This is a new idea to me, but I'm having a hard time understanding it. So would the spline created from the particle path come from its position and velocity? Then it would be revolved to create something like a capsule shape? Any chance there is a geometric interpretation I might be able to see? I can understand math better visually.

From it's position that is a function of spawn location and velocity, where velocity is a function of initial velocity and acting forces, it's essentially a spline, and then if you do a spline vs triangle test you get what you want. It's just something to do with accuracy, which isn't that important, it's just a matter of processing cost vs quality desired. I'm not sure where some interpretations could be found though, conceptually just think of it as spline passing through a plane, and if that spline is determined by original position, original velocity, displacement due to velocity at T-value and acceleration due to forces at T-value, you have the most accurate method for determining when and where a particle is going to pass through or collide with some geometry. On another note, depending on whether you're using geometry for collision testing that is 'static' in the scope of the particle system, if you can get the math for this, you should be able to calculate the intersection when the particle is created, so you don't have to do ray tests every frame for each particle, and then you set an event on the particle at time T which is the time you know the particle will collide, to handle the collision response.

I'm don't know the math on how to get that intersection point, but I'm hoping that when I get around to doing my own particle system I'll be able to figure that out.

Unfortunately after much testing and stepping through the Bullet code, I determined Bullet never got to the leaf nodes of the AABB tree and hence I couldn't process any of the triangles. I probably was doing something wrong but I couldn't determine what.[/quote]There could be a variety of issues. Generic trimesh collision however is widely proven to work.

SAP sounds interesting, unfortunately my triangle mesh is concave, also it sounds like SAP is for convex mesh-to-mesh collisions so would SAP still work for particles against a concave mesh?[/quote]I don't understand where are you getting those facts. Broadphase in Bullet is independent of collision mesh. Using trimeshes by the gimpact solver will just work.
FYI: all broadphase work on AABB as far as I understand.

maybe I'm oversimplifying the additional complexity added by triangles vs a simple box?[/quote]I've seen some presentations about using a set of spheres/ellipsoids instead of a box. In general, using triangles is not going to be feasible for realtime. Using a simplified collision mesh is also in widespread use for realtime.

I don't understand where are you getting those facts. Broadphase in Bullet is independent of collision mesh. Using trimeshes by the gimpact solver will just work.
FYI: all broadphase work on AABB as far as I understand.[/quote]
I apologize, when I said that I was looking at SAT (separating axis theorum) instead of SAP (I must have been tired that day...) SAP makes sense.

I've seen some presentations about using a set of spheres/ellipsoids instead of a box. In general, using triangles is not going to be feasible for realtime. Using a simplified collision mesh is also in widespread use for realtime.[/quote]

That makes sense, but my collision shape is tricky because it can be arbitrary but it will be round, i.e. think of filling a wine glass with fluid. Any ideas how test against something like that besides triangles? I guess I could do something like this:

- In general treat the collision as a cylinder/ellipsoid test
- test particles Y value, as it gets lower (i.e. towards the bottom of the wine glass) decrease the radius of the cylinder which should simulate the change in curvature

Maybe that would work? Any chance you remember the names of those presentations? It would be cool if I could take say a cubic spline to define the curvature then use the particles Y value and "lookup" the correct value on the spline, I'm not sure what the math would be though.

@Kyall:

Thanks for the explanation that is a neat idea. My shape will be dynamic so I'm not sure how I could always predict where each particle would end up at a given time delta.

It's probably section 23.2.2. I've searched for others but I couldn't find them.

For your case, I might try to encode two ellipsoids. In general, using quadratics is going to be good. Your example is pretty much nightmare for everything I know. Knowing your needs, it might eventually make sense to use a trimesh. I'm afraid you'll have to find this out yourself in the painful way.

use AABB TREE and TBB