Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (513)
Games in Android Showcase (120)
games submitted by our members
Games in WIP (577)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Perfect 'Per-Vertex' Collision Algorithms?  (Read 2918 times)
0 Members and 1 Guest are viewing this topic.
Offline wessles

JGO Wizard


Medals: 67
Projects: 4
Exp: 3 years


Profile picture isn't relevant.


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

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

JGO Kernel


Medals: 156
Projects: 7
Exp: 3 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! Tongue

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

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Tim_Wilson
« 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!
Offline HeroesGraveDev

JGO Kernel


Medals: 269
Projects: 11
Exp: 2 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.

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

Other than that JBullet has been awesome..


-=Like a post.. give the author a medal!=-
Offline 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

Gilbert–Johnson–Keerthi distance algorithm might help you

Offline wessles

JGO Wizard


Medals: 67
Projects: 4
Exp: 3 years


Profile picture isn't relevant.


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

Offline quew8

JGO Coder


Medals: 31



« 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.
Online 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.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline 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.
Offline wessles

JGO Wizard


Medals: 67
Projects: 4
Exp: 3 years


Profile picture isn't relevant.


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

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

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!

Offline opiop65

JGO Kernel


Medals: 156
Projects: 7
Exp: 3 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!

Offline HeroesGraveDev

JGO Kernel


Medals: 269
Projects: 11
Exp: 2 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)

Offline wessles

JGO Wizard


Medals: 67
Projects: 4
Exp: 3 years


Profile picture isn't relevant.


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

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

JGO Kernel


Medals: 156
Projects: 7
Exp: 3 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.

Offline 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!
Offline opiop65

JGO Kernel


Medals: 156
Projects: 7
Exp: 3 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!

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

Longarmx (52 views)
2014-10-17 03:59:02

Norakomi (43 views)
2014-10-16 15:22:06

Norakomi (33 views)
2014-10-16 15:20:20

lcass (37 views)
2014-10-15 16:18:58

TehJavaDev (68 views)
2014-10-14 00:39:48

TehJavaDev (67 views)
2014-10-14 00:35:47

TehJavaDev (60 views)
2014-10-14 00:32:37

BurntPizza (73 views)
2014-10-11 23:24:42

BurntPizza (45 views)
2014-10-11 23:10:45

BurntPizza (86 views)
2014-10-11 22:30:10
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!