Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (601) Games in Android Showcase (171) games submitted by our members Games in WIP (649) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Polygon-Collision-Separating Axis Theorem  (Read 5859 times) 0 Members and 1 Guest are viewing this topic.
Phibedy

Senior Devvie

Medals: 9

 « Posted 2012-11-25 17:39:49 »

Hi, I would like to check some Polygones if they intersect and get the point, where the collide. [polygon].intersects([polygon] doesn't work. It needs a rectangle instead of a polygon.
http://www.codeproject.com/Articles/15573/2D-Polygon-Collision-Detection
http://www.java-gaming.org/topics/polygon-collision-detection/5606/view.html

I wondering about how to handle concave polygons.
I found that collision detection and liked it, but I can't find out, how it is done: http://www.win.tue.nl/~speckman/demos/kcdsp/index.html

I addition I would like to check "ellipse intersects polygon". At the moment I would transform the ellipse to an polygon.
Maybe I just miss some important points, but I don't know how to go on. I already thought about writing an own Polygon-object and intersection-method but I think, that it would be quite inefficient

thx for help
best regards Phibedy
matheus23

JGO Kernel

Medals: 122
Projects: 3

You think about my Avatar right now!

 « Reply #1 - Posted 2012-11-25 17:45:37 »

Concave vs anything:
Just transform the Concave polygon into multiple convex polygons and finally test them.

Ellipse vs Polygon:
You have to calculate the Vector from the mid of the ellipse to the surface of the ellipse and then twice this, use the vector from evey vertex from the polygon trough the mid of the ellipse as axis and finally project the ellipse onto this axis.

EDIT: Also, the probably IMO best tutorial of how SAT works and is implemented is shown here:
http://www.codezealot.org/archives/55

See my:
My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Phibedy

Senior Devvie

Medals: 9

 « Reply #2 - Posted 2012-11-25 19:40:48 »

thx for immediate help.
The tut is really great
Do you have any tut about convex decomposition, I would solve it with checking 2 Vectors Point A->B->C; next step B->C->D etc.

Would you prefere SAT or the way it was said in this topic? http://www.java-gaming.org/topics/polygon-collision-detection/5606/view.html
I haven't done anything with Areas at the moment, so I don't know if it solves my problem or not

Should I use the Polygon offered by native java or should I write my own Polygon Object?
best regards Phibedy
matheus23

JGO Kernel

Medals: 122
Projects: 3

You think about my Avatar right now!

 « Reply #3 - Posted 2012-11-25 19:48:58 »

In the topic you linked it says, that Area operations would be very slow... So I guess you shouldn't use them
I haven't used them myself, soo....

And no, currently I don't know any Polygon decomposition algorithms, but checking 2 vectors again and again is the right thing. Google will help you there for sure.

And I guess you should either write your own Polygon Object or use a library.
I did this about a week ago too, here is the code I wrote:
https://github.com/matheus23/Utils/tree/master/Utils/src/org/matheusdev/util/collision
The important parts are Collision.java and projecting Convex polygons on given axes. It's pretty fast and gives no errors.
The advantage of my "Utils" library is, that it does not need natives, nor another java library, so you can just use it.

See my:
My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Phibedy

Senior Devvie

Medals: 9

 « Reply #4 - Posted 2012-11-25 21:25:25 »

I will write it on my own, I am not programming it, to get it finished, I wanna improve my programming-skills
If I stuck, I will have a look at it
However I like your programming-style, it's like mine, maybe more efficient but without comments
Now I got a point where I can start programming, thx for help
I will try to beat your 220 ns per object
deepthought
 « Reply #5 - Posted 2012-11-26 03:40:23 »

I don't have anything to check this with on my tablet right now, but you should be able to decompose a polygon into triangles by:

1. Choose a point
2. Get the 2 points connected to it. This will form your first triangle.
3. Get the next point from the whichever point you got second to last. That point will form your next triangle with the last 2
4. Repeat step 3 as necessary

There might be a faster way, but this is what I can think of right now.

jocks rule the highschools. GEEKS RULE THE WORLD MWAHAHAHA!!
captain failure test game
Phibedy

Senior Devvie

Medals: 9

 « Reply #6 - Posted 2012-11-26 14:22:58 »

Got a fancy way of checking, what part of the polygon is concave.
I got 4 points A, B, C, D, but I haven't figuered out, what's the best way to split it.
-> if vec AC crosses the Vec BD the Poly isn't concave from A to D
@ matheus23. How do you render your custom polygons?

best regards Phibedy
matheus23

JGO Kernel

Medals: 122
Projects: 3

You think about my Avatar right now!

 « Reply #7 - Posted 2012-11-26 15:53:32 »

@ matheus23. How do you render your custom polygons?

Pretty vauge question... In the demo I render them via glBegin(GL_LINE_LOOP); but I don't even know if you use LWJGL.

The fun thing about my Polygons is that they're completly independent to rendering. They're another story One could render them with LWJGL, JogAmp, AWT, SWT, or anything else, if you want to. You need to implement it yourself, but you aren't tied to any library, which is the basic Idea of this "Utils" lib.

See my:
My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Phibedy

Senior Devvie

Medals: 9

 « Reply #8 - Posted 2012-11-26 16:37:44 »

I am not unsing any lib, I try to do everything on my own. I have enough time and don't care about about perfect performance. I just try to understand it
[CODE]
protected final Vec2[] verticesCached;
protected Rect aabb;
protected Circle circBounds;[CODE]
that's a quote from your poly.class
What do you store in verticesCached, aabb and in the circle?
aabb stores the bounds of the polygon, which you check collision first?
You don't have to tell me secrects of your code, if you don't want to.
thx for help [/code][/code]
matheus23

JGO Kernel

Medals: 122
Projects: 3

You think about my Avatar right now!

 « Reply #9 - Posted 2012-11-26 17:20:29 »

Yes AABB is the clostest Axis aligned bounding box of the polygon. You simply get it with calculating the minimal and maximal x and y values from all vertices.

Actually it's not used anymore, because I don't use AABB vs AABB as pre-collision checks. I now use Circle vs Circle, because that's much faster (Rect.java is an AABB class, btw.).

And yeah, circBounds is the closest bounding circle, simply calculated: The center of the circle is the center of the polygon. The radius is the maximum distance from the center to a vertex. This is the code

And finally, about those verticesCached, this is more complicated.
In this class I also have a "Mat4 mat" class, which is the transformation matrix for the given vertices of the polygon.
This transformation matrix is responsible for for example rotating, scaling, or translating the polygon.

Now, the problem is, I need to keep the "old", or better: original vertices too, in case I would want to "reset" the matrix and start off the original polygon again, and rotate that one.

For that I have the vertices and the verticesCached. VerticesCached are the transformed vertices.

Another reason (and the reason of the "Cached"-suffix) is that you don't always change the matrix and transformation of the polygon. Take for example a table in a top-down game. You would want to create the table at the beginning of the game, and then rotate it to fit into your world somehow. Then at some moment your player kicks the table, and it's rotation changes.

In the time between the creation of the table and the kick is probably an hour playtime. To not make the table's vertices be re-calculated each frame, I cache the transformed vertices after the first creation of the table. In case the table's orientation changes, just call updateFromMatrix() again.

The last reason is, that it could cause floating point problems when I would always transform the previously transformed vertices. Mind that when adding floats 1f + 1f + 1f + 1f ... n times is probably not n, but (n-1).999999999999999[...].

Also, I don't mind sharing "secrets" of my code. The code is open source, it's ment to be open

See my:
My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Phibedy

Senior Devvie

Medals: 9

 « Reply #10 - Posted 2012-11-26 21:43:07 »

thx
Now I should know what I have to consider
Phibedy

Senior Devvie

Medals: 9

 « Reply #11 - Posted 2012-11-30 15:47:24 »

Most of it is working so far, but I got another question
At he moment I am rendering it with awt. I create shapes from my Objects and then use g.draw([...]).
I think, that this method is quite inefficient because everytime I am moveing the Object, I have to update the location of the Object and the shape. In addition I have to store the shape inside the object.
Does anyone know a better way of drawing custom-objects?
How is it solved in lwjgl? Haven't used it, but if it's worth it, I will
best regards
matheus23

JGO Kernel

Medals: 122
Projects: 3

You think about my Avatar right now!

 « Reply #12 - Posted 2012-11-30 16:06:41 »

LWJGL is something completly different than AWT. When we are talking about LWJGL, we are (in this case) talking about OpenGL, which is a library specification for a 3D hardware pipeline.

AWT uses can use OpenGL, but can also switch to software rendering, if needed.

OpenGL is usually used from C / C++, since it's written in C (usually... It's only a specification, so it's actually implemented by your drivers...), and therefore we have LWJGL, which wraps OpenGL and makes it accessible in Java.

You can use LWJGL just like any other Java library but with natives (native libraries (C libs)). In LWJGL you setup a window like this:

 1  2  3  4  5  6 `try {    Display.setDisplayMode(new DisplayMode(800 /* Display width */, 600 /* Display height */));    Display.create();} catch (LWJGLException e) {    e.printStackTrace();}`

Then you initialize your OpenGL code like this:

 1  2  3  4  5  6  7  8  9  10  11 `public void resize(int width, int height) {    glViewport(0, 0, width, height);    glMatrixMode(GL_PROJECTION);    glLoadIdentity();    glOrtho(0, width, height, 0, -1, 1);    glMatrixMode(GL_MODELVIEW);}// Init:glLoadIdentity();resize(Display.getWidth(), Display.getHeight());`

And finally you draw your Polygon like this:

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15 `public void render() {    // Assume you have your polygon's vertices stored in a "Vec2[]".    // Use GL_POLYGON if you don't want to stroke the polygon,    // but fill the polygon with a color. To set the filling color    // use "glColor3f(1, 1, 1)" (= white).    glBegin(GL_LINE_LOOP);    for (int i = 0; i < poly.vertices.length; i++) {        glVertex2f(poly.vertices[i].x, poly.vertices[i].y);    }    // This call will "calculate" the geometry:    glEnd();    // This call will render the geometry using all your GPU Power:    Display.update(); // Call this once a frame}`

This is only to show you how using LWJGL would look like. (to use all those methods you need to static-import the class GL11. This is done by writing this to the imports: static import org.lwjgl.opengl.GL11.*;)

Get more information and the library itself, at the LWJGL website or at it's wiki page.

There is also a forum, but personally I've found this forum to be more helpful in LWJGL-related questions...

Also, you don't need to use LWJGL. There are game engines and libraries written on top of LWJGL. Just google for libGDX, Slick2D or the (not very famous) JRabbit engine, for example. There are many more.

And: There is another wrapper for OpenGL for java out there: JOGL, also known as the JogAmp project. I don't suggest using this library, since it's pretty complicated for newbies, but you could consider moving to JOGL when having more experience with Java, or especially OpenGL.

And yes. It [size=4pt](f**king)[/size] is worth it

See my:
My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Phibedy

Senior Devvie

Medals: 9

 « Reply #13 - Posted 2012-11-30 20:20:34 »

thx
It doesn't seem to be to complecated.
best regards Phibedy
Phibedy

Senior Devvie

Medals: 9

 « Reply #14 - Posted 2012-12-01 12:19:47 »

deepthought
 « Reply #15 - Posted 2012-12-01 16:05:01 »

jocks rule the highschools. GEEKS RULE THE WORLD MWAHAHAHA!!
captain failure test game
matheus23

JGO Kernel

Medals: 122
Projects: 3

You think about my Avatar right now!

 « Reply #16 - Posted 2012-12-01 17:31:14 »

I always download the sources of open-source-projects. This makes everything easier, and Javadoc is then included too

See my:
My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Phibedy

Senior Devvie

Medals: 9

 « Reply #17 - Posted 2012-12-01 19:33:03 »

Thx
I am now comfortable with "standard" 2D rendering of lwjgl, I really prefere the lwjgl functions to java2D.
Google told me, that it's usefull to draw the lwjgl on a canvas on a jframe.
I think I read a lot of bullshit about it and that's why I am a little bit confused about it.
1. With lwjgl I render something on a canvas, a canvas can be placed on a jframe?
2. If I put it on a jframe, most of the jframe listeners doesn't work anymore, because of the canvas?
3. It is possible to use awt-compontents on a canvas that's placed on a jframe?

I would like to use a Jframe because I wanna use the resize-function + awt components + custom-components made with them.
If there's another/better way to do that feel free to criticize

Sry for asking simple question again, but if I google it, I always get posts like "Use java2D, use C++ instead of java, you will damage your computer, that's not worth it, need help - nothing is working etc." and no solution.

thx for help
matheus23

JGO Kernel

Medals: 122
Projects: 3

You think about my Avatar right now!

 « Reply #18 - Posted 2012-12-01 19:39:18 »

In the beginning I wouldn't rely on JFrames in LWJGL.
If you want a more solid Windowing library use JogAmp
(Still not a reason to change actually)

LWJGL should give you everything you need:

If you want to detect window resizing:
 1  2  3  4 `boolean resized = Display.wasResized();// Getting the sizes (you already know that):int w = Display.getWidth();int h = Display.getHeight();`

If you want to detect, whether the user has pressed the "X" of the window:
 1 `boolean pressedCloseButton = Display.isCloseRequested();`

If you really want to render into a AWT Frame / Swing JFrame:
 1  2  3  4 `Frame frame = [...];Canvas canvas = [...];// This does the magic:Display.setParent(canvas);`

I think this should help you. Remember that the last code snipped is not really needed. You only need to do this, if you want to have window maximize/minimize listeners and setters. (frame.setMaximized(...), frame.getMaximized())

See my:
My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Phibedy

Senior Devvie

Medals: 9

 « Reply #19 - Posted 2012-12-01 20:08:13 »

Ok
But how do I resize it?
Do I have to write the border, where I can grab the window on my own? I would like to have these arrows to resize it.
matheus23

JGO Kernel

Medals: 122
Projects: 3

You think about my Avatar right now!

 « Reply #20 - Posted 2012-12-01 20:14:31 »

Oh, sorry didn't got you were after that

 1 `Display.setResizable(true);`

See my:
My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Phibedy

Senior Devvie

Medals: 9

 « Reply #21 - Posted 2012-12-01 20:16:54 »

THX
Never believe google, it said, that "lwjgl-frames" can't be resized that way

Edit:
"glVertex2f"
glVertex = Vertex
2 = 2-Dimensions?
f = type, like float, double etc.

thx for little help again
matheus23

JGO Kernel

Medals: 122
Projects: 3

You think about my Avatar right now!

 « Reply #22 - Posted 2012-12-01 22:38:16 »

2 does not really mean 2 dimensional.
2f = 2 arguments of type float.

there are also:
ub = unsigned byte
s = short
i = int
l = long
f = float
d = double

and there is even more cruel stuff then 3ub:
glUniformMatrix4x3, which takes a 4 x 3 matrix as argument, and updates the given uniform... but thats another story.

That's just how the naming in OGL works.

See my:
My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Phibedy

Senior Devvie

Medals: 9

 « Reply #23 - Posted 2012-12-01 23:34:59 »

thx  for explanation

Edit: I am a little bit in trouble with the Rendering of concave Polygons. Picture: http://s7.directupload.net/file/d/3092/7mye7nhz_jpg.htm
I am using "GL_POLYGON" for the white, but I would like to render what's inside the blue line.
I thought about splitting the concave polygon into some convex ones and render them, but I think there has to be something that's more effective
thx for helping again
matheus23

JGO Kernel

Medals: 122
Projects: 3

You think about my Avatar right now!

 « Reply #24 - Posted 2012-12-02 15:03:28 »

thx  for explanation

Edit: I am a little bit in trouble with the Rendering of concave Polygons. Picture: http://s7.directupload.net/file/d/3092/7mye7nhz_jpg.htm
I am using "GL_POLYGON" for the white, but I would like to render what's inside the blue line.
I thought about splitting the concave polygon into some convex ones and render them, but I think there has to be something that's more effective
thx for helping again

You don't have to edit your post. Just doublepost, if it makes sense.

Yep. GL_POLYGON does only render convex polygons.
And no, sorry, there is nothing more effective than splitting the concave polygon into convex ones.

See my:
My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Phibedy

Senior Devvie

Medals: 9

 « Reply #25 - Posted 2012-12-02 15:08:32 »

ok I will do it next time
Would you split the Polygon into a bunch of triangles or split it in bigger parts?
matheus23

JGO Kernel

Medals: 122
Projects: 3

You think about my Avatar right now!

 « Reply #26 - Posted 2012-12-02 15:20:29 »

ok I will do it next time
Would you split the Polygon into a bunch of triangles or split it in bigger parts?

Simply splitting it into a bunch of triangles won't help you, unless you do this with kind of an algorithm. I'd go with splitting it into bigger parts.
I never wrote those splitters myself, I guess google can help out the most here

See my:
My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Pages: [1]
 ignore  |  Print

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

 Jesse (12 views) 2015-07-29 04:35:27 Riven (35 views) 2015-07-27 16:38:00 Riven (18 views) 2015-07-27 15:35:20 Riven (20 views) 2015-07-27 12:26:13 Riven (11 views) 2015-07-27 12:23:39 BurntPizza (30 views) 2015-07-25 00:14:37 BurntPizza (41 views) 2015-07-24 22:06:39 BurntPizza (24 views) 2015-07-24 06:06:53 NoxInc (27 views) 2015-07-22 22:16:53 NoxInc (18 views) 2015-07-22 22:13:39
 wessles 47x theagentd 45x basil_ 35x orangepascal 28x KaiHH 27x ags1 19x Riven 19x mooman219 17x KudoDEV 13x princec 13x bornander 13x klaus 11x Jesse 10x philfrei 9x Zaneris 9x deepthought 8x
 List of Learning Resourcesby gouessej2015-07-09 11:29:36How Do I Expand My Game?by bashfrog2015-06-14 11:34:43List of Learning Resources2015-05-31 05:37:30Intersection Methodsby Roquen2015-05-29 08:19:33List of Learning Resources2015-05-05 10:20:32How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21
 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