Perfect 'Per-Vertex' Collision Algorithms?

So, I am experimenting with physics, and have got a little fun ‘applyForce()’ demo along.
Now I want to know how to detect collision no matter how many vertices there are.

I want to be able to find collision with:
* Convex and concave objects (looking at you, Hyperplane Seperation Thereom)
* Works no matter how many vertices there are

Any bright ideas?

in your code so far how have you been doing your physics?
are you leveraging JBullet?

He is creating an engine from scratch, so I’m guessing he would rather no use JBullet. To be honest wessles, this might be a really big undertaking, and you might be better off using JBullet. Even I (the person who hates using others’ code) think its a good idea! :stuck_out_tongue:

But good luck if you’re going to create your own!

Any polygon can be created through the use of triangles. If you can separate the polygon into individual triangles, the amount of vertices doesn’t matter.

Are you sure you want to write physics algorithms without a pre-constructed library? I like to do all my physics myself, but I’m just a math geek!

Even if/when you could understand all the collision detection and physics, libraries like JBullet or whatever have been refined for a long time, and contain all the neccessary features.

There is no valid reason why anyone would choose your physics/collision detection over JBullet/equivalent.

It’s not to say you shouldn’t learn it.
Just saying it’s not worth learning unless you are going to use it.

well all i can say is good luck and I mean that honestly.

JBullet is nice but its clearly a C code port… and for that reason it makes for some dam ugly java code.

I would happily consider a more pure java library (in format and syntax) than feeling like im using a retrofitted one.

For my code i ended up writting a wrapper around jbullet to hide the C’ness from my java code. :stuck_out_tongue:

Other than that JBullet has been awesome…

if your gonna implement it by yourself youd want to use some good algorithm. hopefully all or most of your shapes will be convex(other wise the hst wouldnt work sometimes), but look into some more trig and stuff

Gilbert–Johnson–Keerthi distance algorithm might help you

I use the GJK algorithm personally. There’s some complex vector maths involved but it’s quite an easy concept to visualize and understand which always helps. There is a really good video (albeit long) talking through an implementation of GJK on the Molly Rocket site. I watched this once, taking notes, and never needed to look anywhere else again.

There’s an extension (sort of) to the GJK called EPA (expanding polytope algorithm) which can work out the point of collision as well, which may or may not be necessary for your requirements). I currently use this but it has it’s limits and I’ll be moving away from it soon.

I like this. Learning for the sake of learning. Good on you.

  1. Read Realtime collision detection book. http://realtimecollisiondetection.net/books/rtcd/
  2. Play with code. Learn that stuff is hard.
  3. Read it again. Now you start to understand how complex things are.
  4. Play with code. After lot of work you have physic “engine” and you understand how things are done.
  5. Learn that one just don’t write robust, fast, generic physics engines themself.
  6. Start to use physic engine.

Collision detection is fun and one should understand how these things work but its a lot of work.

I completely agree with you. While you may not make the next JBullet, it’s still good to know how the math behind it all works. Learning rarely ever hurts!

Collision detection is dirty work.

For example, you can spend ages getting a system working that detects collisions for any shapes, but then you have an object travelling at huge speeds and have to get around that as well.

Perfect collision detection is not something that can be ‘perfectly’ done with a computer. It is one of several things that only work in the real world.
And even close-to-perfect requires lots of work, and is slow for any real use cases.

Collision detection algorithms are really just “How can I cut out as much time as possible while still getting the same results”.

By all means, learn it if you must, but don’t expect it to be perfect or clean.

Finally, a thing to note is that 99% of players won’t be able to notice the difference between complex polygon-polygon collision and simple AABB-AABB collision. (You may of course need to put multiple AABBs together for each model)

I would firstly give an object a square bounding box that begins calling a collision detection system. Then I would check if points on the line touch simple enough. You could take it a lot further but starting with that is a good way to build a framework.

OP said he’s not going to continue on with this?

That and what you’re describing is very vague and isn’t pixel perfect collision, that’s the basics of a bounding box algorithm and is nowhere near what OP was asking for.

OP was asking perfect vertex based collision not pixel!

Well, yeah that. I was just trying to tell Icass that what he’s talking about is bounding boxes, just so he knows!

I’d suggest just understanding why they work and not bother implementing any of them. Separating (hyper)planes is a easy (and why it’s popular) but not very efficient. The Minkowski sum methods are much more interesting. The implementation details aren’t very important…knowing that the methods exist is sufficient (and perhaps how the allow you to skip actually performing a full sum). This is useful because there are other (or special case) problems which the techniques can be applied. Like here: (http://www.java-gaming.org/topics/vectors-what-s-the-point/24307/msg/225743/view.html#msg225743) I’m logically using a Minkowski sum to reduce computation.

I know its about bounding boxes and its easier and more efficient to do them on polygons.