Polygon-Collision-Separating Axis Theorem

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:

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 ::slight_smile:

thx for help
best regards Phibedy

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

thx for immediate help.
The tut is really great :smiley:
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 :slight_smile:

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

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:


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 )

I will write it on my own, I am not programming it, to get it finished, I wanna improve my programming-skills :slight_smile:
If I stuck, I will have a look at it :smiley:
However I like your programming-style, it’s like mine, maybe more efficient but without comments :smiley:
Now I got a point where I can start programming, thx for help :smiley:
I will try to beat your 220 ns per object :smiley:

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.

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

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. :slight_smile:

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 :smiley:


protected final Vec2[] verticesCached;
protected Rect aabb;
protected Circle circBounds;

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 :slight_smile:


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:

thx ;D
Now I should know what I have to consider :slight_smile:

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

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:


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:


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:


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 (fucking) is worth it :wink:

thx :slight_smile:
It doesn’t seem to be to complecated.
best regards Phibedy

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 :’(

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

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 :slight_smile:

Thx :slight_smile:
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 :slight_smile:

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 :slight_smile:

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:


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:


boolean pressedCloseButton = Display.isCloseRequested();

If you really want to render into a AWT Frame / Swing JFrame:


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())

Ok ;D
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. :slight_smile: