I'm programming something that needs super efficient collision detection, and figured that rather than checking collision per-frame, I could use the velocity and acceleration of objects to create parametric functions that show when and if those objects collide. However, it only works for collisions of spheres, because I'm finding when the distance between the spheres is r1+r2..
I hear there's similar stuff that works for non-spheres, can someone educate me on this?
Collision detection is inherently expensive, and there will always be a trade off between accuracy and speed.
What's the specific application you're developing it for?
Bentley Sanchez
>t. cuck
Isaiah Rivera
There isn't a tradeoff between accuracy and speed. In fact, accuracy and speed are arguably proportional to each other.
If you check for intersection every frame, it's inefficient and inaccurate. If you mathematically calculate the exact moment of collision, it's fast and accurate.
The hard part is programming it.
Ryder Bennett
Approximate your non-spherical shapes with packed spheres.
Nolan Bennett
Says the dude posting pictures of a man handling a cock
Aiden Ward
>t. cock
Juan Turner
I'm interested in this too user. My solution was going to be turning their centers path into a line, calculating where they are closest and seeing if it's closer than the sum of their furthest from center points. Only if it is would more expensive collision detection get done. I may also do bounding boxes around their traveled distance to see if they are even close enough to do the line calculating, but not sure it would help.
James Williams
Check out open dynamics engine ODE
Cooper Bailey
Don't calculate where they are closest; that requires calculus, and the closest approach between the two objects could have them well inside each other. Just find the distance where they might be touching, and calculate when they're that distant from each other.
Usually when someone tells me to check out something and doesn't explain about it at all, it turns out to be a huge waste of time because my requirements were misunderstood.
Nicholas Ortiz
>Distance they're might be touching But that's a range, unless the objects are spheres. It would be even harder to calculate. Besides, most objects at any given time are not colliding, so u want to spend the least amount of time to decide given objects are not colliding, and then you can focus a bunch more calculation once you determine there's any chance that they will.
Colton Baker
It's really easy though.
d(t) = sqrt((xA+xB)^2+(yA+yB)^2+(zA+zB)^2) xA = xAi + t * xAv + t^2 * xAa/2 Then similar for yA, zA, xB, yB, zB
xAi = initial X position of A xAv = X velocity of A xAa = X acceleration of A (this is optional, but will drastically improve performance in any scenario with constant gravity, or if something has a constant thrust. Variable thrust may be possible, but would make factorising the equation harder since it won't factorise the same way each time)
So you just do the horrifically complicated task of somehow factorising it (maybe not so easy after all!) so that you can easily determine at which value(s) of t the distance is equal to rA+rB, the radii of the spheres you're simulation collisions for.
This is what I talk about in the OP, but I don't like that it's restricted to spheres.
Nicholas Thompson
How many objects do you have in the scene? If most of the objects don't collide, it might be useful to divide the space into some sort of quadtree so that you know that some objects are so far apart that it's pointless to even calculate if they intersect. Then there are bounding spheres/boxes to speed it up further. Generally, I think that analytically finding intersection time is pointless, as objects may change their parameters at any time (either by user interaction or interaction with other objects). tl;dr I dunno, I'm sure there are SIGGRAPH papers on it.
Brandon Williams
You can represent objects as spheres and turn on more traditional collision detection only when their bounding spheres intersect.
Adrian Thompson
Sure, they might change their parameters at any time, but it's still infinitely-precise collision detection and as long as things aren't changing all the time it's incredibly efficient.
I need to think of a way to have it so that objects only try to predict at close range if they change a lot.
Sounds like the only way to do it, but what should the close-range method be?
Ian Bell
Just treat everything as a rectangle amd save yoursef from all the other circlejerking math garbage mumbo jumbo in the thread.
T. Actual game programmer
Jason Smith
I don't see OP saying that they're gayme devving it up anywhere
Isaiah Williams
if they're convex polygons then use minkowski sum. they intersect iff 0 is in A - B.
otherwise split them into convex polygons, there's no way you're dealing with something more complicated.
Landon Ward
>rectangle you mean circles, that's the easiest for collision
Having a good broadphase collision detection algorithm tends to work better though
Jackson Anderson
We did a thing like this in one of the coursera courses, short answer is to use a priority queue data structure with a pre-emptive collision detection type thingo, then you only need update ones that bump
Caleb Cooper
OP, you really need to use broad-phase collision detection (spheres or axis-aligned bounding boxes) for your broad-phase, like said.
Also, what are you doing for spatial paritioning? If you use quadtrees/kd-trees/octrees/etc you can often get O(logn) performance instead of O(n) for a query.
Oliver Jenkins
Any shape can be represented as a radius function, you just take the radius value at specific angle and then detect collision exactly as you would with spheres Sphere is just the simplies form of it where radius function is the same at any angle
Owen Collins
I toyed with that idea, but it sounds like it quickly becomes nightmarishly complicated as polygons are added. I wouldn't even have a clue how to do a radius function for just a tetrahedron.
Leo Ward
have you tried making it so that if something collides it gets recorded? it would seem simple enough
Cameron Murphy
What?
Henry Taylor
You could use a predictive model to detect when collision are likely to happen and then switch to a more precise algorithm to compute the actual collision mechanics.
Andrew Robinson
if you understand the math, it shouldnt be to bad, right?
Carson Ward
You put every object in a containing sphere, if 2 spheres are not colliding, the 2 object are colliding, if 2 spheres are colliding the object are maybe colliding, and you do the frame per frame thing only on the potentially colliding objects.
Jordan Williams
>if 2 spheres are not colliding, the 2 object are NOT colliding
Adrian Morris
What are you making that needs such efficient (at runtime, I doubt your implementation would have a fast startup time) that requires this? It seems overly complicated for complex movements.
It sounds like it'd be better to use an quad/oct tree or even just simple spatial partitioning if you don't have a lot of objects with massively different sizes in one location.
It depends on what you're trying to make, OP.
Blake Price
Just do AABBs then. You can just take the minimum/maximum X/Y/Z values of each point in the polygon, then build a box around that. Super easy, plus quick to check whether two axis-aligned bounding boxes intersect. Then only if they intersect do you do your expensive detection.
This is called broad-phase collision detection.
Basically any sane game will do this.
Hudson Cox
physics != collision detection, idiot
and using a library for whatever your specific situation is tells me you are a pleb
Cooper Price
user, in order to simulate rigid body dynamics one must do collision detection. The rest is just figuring out constraints, forces, and integrating them. One can use Bullet's collision detection features with or without dynamics.
You are not going to do better than bullet. Bullet has been shown to simulate 110k bodies at 15-30 fps, IE more or less realtime, with a radeon 7970. youtu.be/8jGZv1YYe2c
Don't reinvent the wheel. However, should you desire to reinvent the wheel, bullet's code base is useful resource for your endeavor.
Camden Sullivan
How can I find out what algorithms Bullet uses?
Hunter Gonzalez
read the source code
Eli Sullivan
and your stupid shit tells me you're /g/ay >hurr durr libraries are for morons you should solve solved problems to be hardcore like me