Java-Gaming.org Hi !
 Featured games (83) games approved by the League of Dukes Games in Showcase (539) Games in Android Showcase (132) games submitted by our members Games in WIP (603) 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 3040 times) 0 Members and 1 Guest are viewing this topic.
wessles

JGO Wizard

Medals: 77
Projects: 4
Exp: 3 years

 « 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!=-
opiop65

JGO Kernel

Medals: 161
Projects: 7
Exp: 4 years

JumpButton Studios

 « 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: 7
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: 310
Projects: 11
Exp: 3 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

wessles

JGO Wizard

Medals: 77
Projects: 4
Exp: 3 years

 « Reply #7 - Posted 2013-11-21 03:56:53 »

@jmguillemette
I am not using JBullet. I am just toying with the idea of a physics engine (small, albeit).

Nothing much. Just was working on implementing Newton's 3 Laws. I got the #3, and realized I need to be able to detect collision! I tried box-colliding, and it just is not good enough. I have been looking around though!

@opiop65
I realize that this is a big undertaking. I just thought I would give it a try. In the end, I probably will go to JBullet, but so far it has been fun, and taught me some!

@Tim_wilson
Thanks for the convex tippet!

@Heroesgravedev
I can still learn a lot from creating some basic physics. Nothing like rotational momentum or anything, but simple stuff like bounciness(need collision, which brings us to this thread), friction (done), and velocity(done).

I plan to use JBullet, but it would be nice to toy with this idea. I have no hopes of making something close to the scale of JBullet. Also:
Quote
Just saying it's not worth learning unless you are going to use it.
I hope that you mean:
Quote
Just saying that it's not worth learning unless what you learnt applies elsewhere.

If not, I disagree.

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.

Now I have to go to bed. Seeya all later!

quew8

JGO Coder

Medals: 33

 « Reply #8 - 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 #9 - 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 #10 - 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.
wessles

JGO Wizard

Medals: 77
Projects: 4
Exp: 3 years

 « Reply #11 - Posted 2013-11-22 01:42:03 »

Thanks for the book, but I do not have any way to buy stuffs online, unfortunately  .

Quote
Learn that one just don't write robust, fast, generic physics engines themself.
I have said it a million times in this thread, and I'll say it again: I do not plan to use this! I will use a physics engine! I am just toying with physics, because it has been fun so far, and I want to see how far I could go!

When I am done (or more, burnt out) with this, I will move on to using a physics engine. As nerb put it: "Learning for the sake of learning."

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

A little hard work never hurt anyone!

opiop65

JGO Kernel

Medals: 161
Projects: 7
Exp: 4 years

JumpButton Studios

 « Reply #12 - 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: 310
Projects: 11
Exp: 3 years

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

 « Reply #13 - 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)

wessles

JGO Wizard

Medals: 77
Projects: 4
Exp: 3 years

 « Reply #14 - Posted 2013-11-24 04:08:40 »

YES. Thanks for this explaination. Nice to know that my goal is not possible. Give closure on the subject.

I decided to quit on this experiment, since I have some other things to do, like adding physics to MERCury, or re-doing Horde(lost source code AGAIN). I learned a lot while doing it, but it is done. Thanks for the help everyone!

lcass
 « Reply #15 - 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.
opiop65

JGO Kernel

Medals: 161
Projects: 7
Exp: 4 years

JumpButton Studios

 « Reply #16 - 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 #17 - 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!
opiop65

JGO Kernel

Medals: 161
Projects: 7
Exp: 4 years

JumpButton Studios

 « Reply #18 - 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
 « Reply #19 - 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 #20 - 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

You cannot reply to this message, because it is very, very old.

 Add your game by posting it in the WIP section, or publish it in Showcase. The first screenshot will be displayed as a thumbnail.
 rwatson462 (36 views) 2014-12-15 09:26:44 Mr.CodeIt (29 views) 2014-12-14 19:50:38 BurntPizza (61 views) 2014-12-09 22:41:13 BurntPizza (98 views) 2014-12-08 04:46:31 JscottyBieshaar (58 views) 2014-12-05 12:39:02 SHC (74 views) 2014-12-03 16:27:13 CopyableCougar4 (76 views) 2014-11-29 21:32:03 toopeicgaming1999 (136 views) 2014-11-26 15:22:04 toopeicgaming1999 (127 views) 2014-11-26 15:20:36 toopeicgaming1999 (37 views) 2014-11-26 15:20:08
 Rayvolution 40x basil_ 31x HeroesGraveDev 27x LiquidNitrogen 27x kpars 19x BurntPizza 19x kevglass 17x appel 17x Gibbo3771 15x gouessej 14x princec 13x NegativeZero 11x SHC 11x Ecumene 11x Riven 10x Spasi 9x
 Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27Resources for WIP games2014-08-01 16:20:17Resources for WIP games2014-08-01 16:19:50List of Learning Resources2014-07-31 16:29:50
 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