Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (481)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (548)
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  
  Polygon-Collision-Separating Axis Theorem  (Read 3934 times)
0 Members and 1 Guest are viewing this topic.
Offline Phibedy

Senior Member


Medals: 8



« 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.
I read:
- about Separating Axis Theorem
http://www.codeproject.com/Articles/15573/2D-Polygon-Collision-Detection
- about working with shapes/areas
http://www.java-gaming.org/topics/polygon-collision-detection/5606/view.html

of course I read more about it, but I haven't marked every link.

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  Roll Eyes

thx for help
best regards Phibedy
Offline matheus23

JGO Kernel


Medals: 106
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
Offline Phibedy

Senior Member


Medals: 8



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

thx for immediate help.
The tut is really great Cheesy
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 Smiley

Should I use the Polygon offered by native java or should I write my own Polygon Object?
best regards Phibedy
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline matheus23

JGO Kernel


Medals: 106
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 Wink
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.
(I should provide a .jar download =S )

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

Senior Member


Medals: 8



« 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  Smiley
If I stuck, I will have a look at it Cheesy
However I like your programming-style, it's like mine, maybe more efficient but without comments Cheesy
Now I got a point where I can start programming, thx for help Cheesy
I will try to beat your 220 ns per object Cheesy
Offline 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
Offline Phibedy

Senior Member


Medals: 8



« 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
Offline matheus23

JGO Kernel


Medals: 106
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 Wink 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. Smiley

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

Senior Member


Medals: 8



« 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 Cheesy
[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 Smiley[/code][/code]
Offline matheus23

JGO Kernel


Medals: 106
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 Wink

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Phibedy

Senior Member


Medals: 8



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

thx  Grin
Now I should know what I have to consider Smiley
Offline Phibedy

Senior Member


Medals: 8



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

Most of it is working so far, but I got another question Smiley
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 Smiley
best regards
Offline matheus23

JGO Kernel


Medals: 106
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 Wink

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

Senior Member


Medals: 8



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

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

Senior Member


Medals: 8



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

Does someone know where to download javadoc for lwjgl?
http://lwjgl.org/download.php doesn't contain it?  persecutioncomplex
I added it via link "http://lwjgl.org/javadoc/" but I don't always have inet access  Cry
Offline deepthought
« Reply #15 - Posted 2012-12-01 16:05:01 »

here you go!
http://sourceforge.net/projects/java-game-lib/files/Official%20Releases/LWJGL%202.8.5/

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

JGO Kernel


Medals: 106
Projects: 3


You think about my Avatar right now!


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

I'd suggesst downloading the LWJGL-source anyways Wink
I always download the sources of open-source-projects. This makes everything easier, and Javadoc is then included too Smiley

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

Senior Member


Medals: 8



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

Thx Smiley
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  Smiley

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 Smiley
Offline matheus23

JGO Kernel


Medals: 106
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 persecutioncomplex Wink
(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
Offline Phibedy

Senior Member


Medals: 8



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

Ok  Grin
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. Smiley
Offline matheus23

JGO Kernel


Medals: 106
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 Wink

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

Senior Member


Medals: 8



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

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

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

thx for little help again Smiley
Offline matheus23

JGO Kernel


Medals: 106
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
Offline Phibedy

Senior Member


Medals: 8



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

thx  for explanation Smiley

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  Undecided
thx for helping again  Smiley
Offline matheus23

JGO Kernel


Medals: 106
Projects: 3


You think about my Avatar right now!


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

thx  for explanation Smiley

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  Undecided
thx for helping again  Smiley

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

Senior Member


Medals: 8



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

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

JGO Kernel


Medals: 106
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  Grin
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 Smiley

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.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

atombrot (26 views)
2014-08-19 09:29:53

Tekkerue (25 views)
2014-08-16 06:45:27

Tekkerue (23 views)
2014-08-16 06:22:17

Tekkerue (14 views)
2014-08-16 06:20:21

Tekkerue (22 views)
2014-08-16 06:12:11

Rayexar (61 views)
2014-08-11 02:49:23

BurntPizza (39 views)
2014-08-09 21:09:32

BurntPizza (30 views)
2014-08-08 02:01:56

Norakomi (37 views)
2014-08-06 19:49:38

BurntPizza (67 views)
2014-08-03 02:57:17
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

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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!