I'm programming something that needs super efficient collision detection...

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?

Other urls found in this thread:

bulletphysics.org/wordpress/
panda3d.org/manual/index.php/Bullet_Continuous_Collision_Detection
toptal.com/game/video-game-physics-part-ii-collision-detection-for-solid-objects
youtu.be/8jGZv1YYe2c
twitter.com/AnonBabble

>anime picture

Haha, no.

Sage goes on both fields guys, remember.

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?

>t. cuck

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.

Approximate your non-spherical shapes with packed spheres.

Says the dude posting pictures of a man handling a cock

>t. cock

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.

Check out open dynamics engine ODE

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.

>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.

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.

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.

You can represent objects as spheres and turn on more traditional collision detection only when their bounding spheres intersect.

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?

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

I don't see OP saying that they're gayme devving it up anywhere

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.

>rectangle
you mean circles, that's the easiest for collision

Just use Bullet. You are not going to do better than Bullet:
bulletphysics.org/wordpress/

axis-aligned rectangles are pretty easy too, and have better performance (since they don't require multiplications)

I am, but I like to use good practices, so good accuracy would be nice.
Speed is most important though.

you are an idiot and a pleb

The most realistic way to do it:

treat everything as a sphere and make a billiards simulator. Do n^2 collision detection.

Then, you make it so an object can have multiple spheres and you'll have the bare minimum

Now you can build off of this and you can compare other systems to it

No sir, you are. You are not going to do better than Bullet. It is currently the best open source collision detection engine out there.

So you know how OP wants to use velocity and acceleration to figure out when objects collide? Well Bullet can do that, it's called continuous collision detection:
panda3d.org/manual/index.php/Bullet_Continuous_Collision_Detection

toptal.com/game/video-game-physics-part-ii-collision-detection-for-solid-objects

Having a good broadphase collision detection algorithm tends to work better though

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

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.

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

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.

have you tried making it so that if something collides it gets recorded? it would seem simple enough

What?

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.

if you understand the math, it shouldnt be to bad, right?

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.

>if 2 spheres are not colliding, the 2 object are NOT colliding

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.

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.

physics != collision detection, idiot

and using a library for whatever your specific situation is tells me you are a pleb

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.

How can I find out what algorithms Bullet uses?

read the source code

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