Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (753) Games in Android Showcase (228) games submitted by our members Games in WIP (842) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Perfect 'Per-Vertex' Collision Algorithms?  (Read 10993 times) 0 Members and 1 Guest are viewing this topic.
wessles
 « Posted 2013-11-21 00:25:58 »

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?
jmguillemette
 « Reply #1 - Posted 2013-11-21 03:38:24 »

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

-=Like a post.. give the author a medal!=-
Opiop
 « Reply #2 - Posted 2013-11-21 03:40:16 »

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!

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

Senior Devvie

Medals: 8
Projects: 1

 « Reply #3 - Posted 2013-11-21 03:42:49 »

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!
HeroesGraveDev

JGO Kernel

Medals: 382
Projects: 11
Exp: 4 years

┬─┬ノ(ಠ_ಠノ)(╯°□°)╯︵ ┻━┻

 « Reply #4 - Posted 2013-11-21 03:44:52 »

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.

jmguillemette
 « Reply #5 - Posted 2013-11-21 03:53:41 »

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.

Other than that JBullet has been awesome..

-=Like a post.. give the author a medal!=-
Agro
 « Reply #6 - Posted 2013-11-21 03:55:39 »

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

quew8

JGO Knight

Medals: 53

 « Reply #7 - Posted 2013-11-21 20:33:06 »

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.
nerb
 « Reply #8 - Posted 2013-11-21 22:51:45 »

Before I started coding, I was into hobbyist electronics. I quit due to it being way to expensive for me (cirquit boards aren't cheap!), but I left with valuable experience in audio-work, electricity, and wiring, which has helped me many of times in my computer-endeaveurs. Was taking up this hobby useless because I never made anything useful? No! I learnt a lot with it, most of which has helped me since. It definetely was worth learning basic circuitry.

I will NOT use this little experiment, but I will take more experience in vectors, etc. out of it.

I like this. Learning for the sake of learning. Good on you.
pitbuller
 « Reply #9 - Posted 2013-11-22 01:26:45 »

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.
Opiop
 « Reply #10 - Posted 2013-11-22 01:48:57 »

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!
HeroesGraveDev

JGO Kernel

Medals: 382
Projects: 11
Exp: 4 years

┬─┬ノ(ಠ_ಠノ)(╯°□°)╯︵ ┻━┻

 « Reply #11 - Posted 2013-11-22 02:58:58 »

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)

lcass
 « Reply #12 - Posted 2013-11-28 20:14:56 »

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.
Opiop
 « Reply #13 - Posted 2013-11-28 22:27:56 »

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.
pitbuller
 « Reply #14 - Posted 2013-11-28 22:55:52 »

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!
Opiop
 « Reply #15 - Posted 2013-11-28 23:01:29 »

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

JGO Kernel

Medals: 517

 « Reply #16 - Posted 2013-11-29 08:22:26 »

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.
lcass
 « Reply #17 - Posted 2013-12-01 22:34:17 »

I know its about bounding boxes and its easier and more efficient to do them on polygons.
Pages: [1]
 ignore  |  Print

 ivj94 (580 views) 2018-03-24 14:47:39 ivj94 (44 views) 2018-03-24 14:46:31 ivj94 (371 views) 2018-03-24 14:43:53 Solater (60 views) 2018-03-17 05:04:08 nelsongames (107 views) 2018-03-05 17:56:34 Gornova (147 views) 2018-03-02 22:15:33 buddyBro (690 views) 2018-02-28 16:59:18 buddyBro (90 views) 2018-02-28 16:45:17 xxMrPHDxx (492 views) 2017-12-31 17:17:51 xxMrPHDxx (728 views) 2017-12-31 17:15:51
 Java Gaming Resourcesby philfrei2017-12-05 19:38:37Java Gaming Resourcesby philfrei2017-12-05 19:37:39Java Gaming Resourcesby philfrei2017-12-05 19:36:10Java Gaming Resourcesby philfrei2017-12-05 19:33:10List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org