I'm programming something that needs super efficient collision

>anime picture

Haha, no.

Sage goes on both fields guys, remember.

>>8852662
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?

File: 000afff9078446c2140faf736b8d409c.jpg (350KB, 1000x1000px) Image search: [Google]

350KB, 1000x1000px

>>8852663
>t. cuck

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

>>8852669
Says the dude posting pictures of a man handling a cock

File: 1492638752701.jpg (18KB, 720x519px) Image search: [Google]

18KB, 720x519px

>>8852669
>t. cock

I'm interested in this too anon. 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.

>>8852662
Check out open dynamics engine ODE

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

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

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

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

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

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

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

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

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

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

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

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

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

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

>>8853645

you are an idiot and a pleb

>>8852662

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

>>8855170
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:
https://www.panda3d.org/manual/index.php/Bullet_Continuous_Collision_Detection

https://www.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 >>8852965
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

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

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

>>8855583
What?

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

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

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

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

>>8855550

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.

>>8855345

physics != collision detection, idiot

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

>>8858265
Anon, 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.
https://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.

>>8858382
How can I find out what algorithms Bullet uses?

>>8858963
read the source code

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