Hi !
Featured games (91)
games approved by the League of Dukes
Games in Showcase (805)
Games in Android Showcase (239)
games submitted by our members
Games in WIP (868)
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 13941 times)
0 Members and 1 Guest are viewing this topic.
Offline 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?
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 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! 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

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

JGO Kernel

Medals: 383
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.

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 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.
Offline 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.
Offline pitbuller
« Reply #9 - Posted 2013-11-22 01:26:45 »

1. Read Realtime collision detection book.
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.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline 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!
Offline HeroesGraveDev

JGO Kernel

Medals: 383
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)

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

JGO Kernel

Medals: 518

« 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: (  I'm logically using a Minkowski sum to reduce computation.
Offline 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  

Riven (585 views)
2019-09-04 15:33:17

hadezbladez (5526 views)
2018-11-16 13:46:03

hadezbladez (2407 views)
2018-11-16 13:41:33

hadezbladez (5788 views)
2018-11-16 13:35:35

hadezbladez (1228 views)
2018-11-16 13:32:03

EgonOlsen (4667 views)
2018-06-10 19:43:48

EgonOlsen (5685 views)
2018-06-10 19:43:44

EgonOlsen (3200 views)
2018-06-10 19:43:20

DesertCoockie (4102 views)
2018-05-13 18:23:11

nelsongames (5118 views)
2018-04-24 18:15:36
A NON-ideal modular configuration for Eclipse with JavaFX
by philfrei
2019-12-19 19:35:12

Java Gaming Resources
by philfrei
2019-05-14 16:15:13

Deployment and Packaging
by philfrei
2019-05-08 15:15:36

Deployment and Packaging
by philfrei
2019-05-08 15:13:34

Deployment and Packaging
by philfrei
2019-02-17 20:25:53

Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04:08 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‑
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!