Java-Gaming.org
 Featured games (81) games approved by the League of Dukes Games in Showcase (495) Games in Android Showcase (114) games submitted by our members Games in WIP (563) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1] 2
 ignore  |  Print
 Awesome SAT! 7-8 ms for 60k objects.  (Read 5455 times) 0 Members and 1 Guest are viewing this topic.
matheus23

JGO Kernel

Medals: 107
Projects: 3

You think about my Avatar right now!

 « Posted 2012-11-18 10:27:58 »

So I recently implemented SAT (Seperating axis theorem), which is an algorithm for finding out whether objects collide. These objects can be rotated, scaled, can have as much vertices as they want, etc.

The algorithm is mainly this: "Two convex polygons don't intersect, if you are able to draw a straight line in between them."

After about ~10 hours of blindly writing vector math and collision stuff code from online tutorials and own existing code, I got my version running pretty well the first time.

I corrected some lapses, for example not re-calculating the normals after updating the matrix of them or calculating the normals wrong (forgetting to create the left perpendicular of them) and things like that...

So in this screenshot I've got 60k polygons, each having 8 vertices, which are randomly generated. (all convex)

Usually the background is black...
Runs at a somehow steady 30 fps, due to the rendering... the collision tests only take 14-15 milliseconds.
I've got a GTX 550 Ti, 8GB and 3.3 GHz 8-core Xenon cpu running here.

So here the same program is with only 60 polygons:

As you can see the background now is black ( ) and the vertices from the polygons are drawn white, if they're not colliding with the "mouse-quad" and black, if they do.

The program only tests the "mouse-quad" (a 4-vertex polygon, which you can rotate with the mousewheel and move with the mouse) against all avaliable polygons, so the polygons don't test collisions with each other, only with the mouse-quad.

I've got a pretty good pc, I want to see what performance you get

<edit>
I want to see what performance you get
Remember to start via command line to see additional information!
</edit>

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

JGO Kernel

Medals: 107
Projects: 3

You think about my Avatar right now!

 « Reply #1 - Posted 2012-11-18 10:43:27 »

How many objects can your pc handle?

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

JGO Kernel

Medals: 107
Projects: 3

You think about my Avatar right now!

 « Reply #2 - Posted 2012-11-18 12:22:21 »

I further improved this version with using a circle vs. circle pre-collision test instead of a AABB vs AABB collision test.

This now works almost twice as fast!
It takes 7-8 milliseconds to test a quad against 60k 8-sided polygons. This means the demo is actually able to run with 60 frames per second with 60k polygons on my pc.

I'm satisfied now

But I still want to know how far you can get...

See my:
My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
deathpat
 « Reply #3 - Posted 2012-11-18 13:19:08 »

hey,

I tested it, my CPU is an intel i7 2630QM.
I can have 40000 polygons taking 16ms ... your PC is really fast

work in progress : D A E D A L U S
matheus23

JGO Kernel

Medals: 107
Projects: 3

You think about my Avatar right now!

 « Reply #4 - Posted 2012-11-18 15:21:13 »

Wow, at least there are some people trying it

Well, I just built the new version (the link was still the old one...).
Here is ne new version based on Circles as secondary boundaries: ArcEngine_SAT.zip

EDIT: Oh wait... that's a totally other version... fixing this now...

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

JGO Kernel

Medals: 107
Projects: 3

You think about my Avatar right now!

 « Reply #5 - Posted 2012-11-18 15:25:01 »

Okey, now the right version is uploaded

It should be up to 2 times faster for you know, deathpat
(which means 40k would run with about 9 ms per calculation)

See my:
My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
deathpat
 « Reply #6 - Posted 2012-11-18 15:33:22 »

ok just tried it .. and it runs much slower than before
It takes now 32ms with 40000 polygons .. but now all the polygons are rotating + the bounding circle is drawn .. maybe it is just the display that is slow ? (as it is drawing much more things )

work in progress : D A E D A L U S
HeroesGraveDev

JGO Kernel

Medals: 250
Projects: 11
Exp: 2 years

┬─┬ノ(ಠ_ಠノ)(╯°□°)╯︵ ┻━┻

 « Reply #7 - Posted 2012-11-18 20:28:09 »

Now to find a way to implement this in a game...

Seriously, what do you hope to do with this.

A Space Shooter maybe?

ra4king

JGO Kernel

Medals: 345
Projects: 3
Exp: 5 years

I'm the King!

 « Reply #8 - Posted 2012-11-18 21:10:02 »

namrog84

JGO Ninja

Medals: 46
Projects: 4

Keep programming!

 « Reply #9 - Posted 2012-11-18 22:29:33 »

You should edit the first post's link to fix it.

Any way we could get the source? or at least a way to implement it in our own?

I want to test it against my un-optimized version I mucked around with over a year ago

"Experience is what you get when you did not get what you wanted"
Joshua Waring

Senior Member

Medals: 4
Projects: 2

 « Reply #10 - Posted 2012-11-19 01:46:11 »

I got 200K at 33ms

and 1 million at 170ms

I tried 100 million and after a good 10 minutes I got a heap size error

The world is big, so learn it in small bytes.
lhkbob

JGO Knight

Medals: 32

 « Reply #11 - Posted 2012-11-19 02:18:53 »

1 million at 97ms

theagentd
 « Reply #12 - Posted 2012-11-19 04:14:39 »

Around 125k polygons cost 16ms. I'm on an i7 860 @ 3.52 GHz.

Myomyomyo.
ra4king

JGO Kernel

Medals: 345
Projects: 3
Exp: 5 years

I'm the King!

 « Reply #13 - Posted 2012-11-19 05:18:16 »

Ok yay it worked!

I think I win this thread: 175K polygons cost 16ms. Intel Core i7 2600K @ 4.2GHz

namrog84

JGO Ninja

Medals: 46
Projects: 4

Keep programming!

 « Reply #14 - Posted 2012-11-19 06:04:28 »

Ok yay it worked!
I think I win this thread: 175K polygons cost 16ms. Intel Core i7 2600K @ 4.2GHz

I am getting the same 175k at 16ms  on a Core i7 2600k running at 3.4Ghz (Did you overclock yours?)

Which means, that its clearly not the cpu that having the limiting factor anymore?

What videocard do you have? I am running a NVidia Geforce GTX 570

edit:
matheus23, the time we are seeing in the console, is that between each frame(including rendering and collision) or is that only collision?

"Experience is what you get when you did not get what you wanted"
ra4king

JGO Kernel

Medals: 345
Projects: 3
Exp: 5 years

I'm the King!

 « Reply #15 - Posted 2012-11-19 06:23:05 »

Yup overclocked and I'm using a beastly GTX 580

Joshua Waring

Senior Member

Medals: 4
Projects: 2

 « Reply #16 - Posted 2012-11-19 12:32:53 »

It's a challenge, time to turn my water pump speed up and get 4.5ghz
Ram is probably a big factor here though. Guess I shouldn't bother.

The world is big, so learn it in small bytes.
Icecore

Senior Member

Medals: 5

 « Reply #17 - Posted 2012-11-19 13:09:58 »

(core 2 duo)
ps: use multy thread, 99% (here) have more then 1 cpu core
give one half poly check loop - to first thread and second half - to second thread =) (or more threads)
theagentd
 « Reply #18 - Posted 2012-11-19 14:43:17 »

It's a challenge, time to turn my water pump speed up and get 4.5ghz
Ram is probably a big factor here though. Guess I shouldn't bother.
Exactly how does the SAT function work? If it doesn't use any trigonometry, square roots or the likes, it's most likely RAM limited. Multithreading might help up to a point, especially on hyperthreaded computers. Hyperthreading will allow it to quickly switch to another thread if a cache miss occurs (as far as I know).

Myomyomyo.
matheus23

JGO Kernel

Medals: 107
Projects: 3

You think about my Avatar right now!

 « Reply #19 - Posted 2012-11-19 15:55:19 »

Wooooot? This thread somehow was just born
Okey... propably due to the time differences

Anyways:

ok just tried it .. and it runs much slower than before
It takes now 32ms with 40000 polygons .. but now all the polygons are rotating + the bounding circle is drawn .. maybe it is just the display that is slow ? (as it is drawing much more things )

Let's define version numbers: 1 was my first version you tested before, 2 the one you just tested, and 3 the one everyone else after that tested.

Yes, 2 was drawing muuuuch more vertices. But that's not the problem. Let's quickly put in another quote here:
edit:
matheus23, the time we are seeing in the console, is that between each frame(including rendering and collision) or is that only collision?

It's only the time it takes for this code:
 1  2  3  4  5  6  7  8  9 `      long time = (Sys.getTime() * 1_000) / Sys.getTimerResolution();      colliding = false;      for (int i = 0; i < polys.length; i++) {         if (Collision.polyVsPoly(quad, polys[i])) {            collisions[i] = true;            colliding = true;         }      }      System.out.println("Time taken: " + (((Sys.getTime() * 1_000) / Sys.getTimerResolution())-time) + ", axis tested: " + Collision.axesTested + ", objects tested: " + Collision.objectsTested);`

Which means, yeah it's not including rendering time, which is huge here (almost the same time, but slightly less I think...)

Sooo, to come back to quote 1:
In that version I hard-tested the "engine". I rotated each polygon (really each one). And each polygon has 2 sets of vertices: The standard model vertices, and the pre-calculated transformed vertices. Every polygon also references a 4x4 Matrix.
And I was updating each matrix each frame and transforming each vertex of each polygon by it's matrix. And that time was included in the console output...
So this is what made it much slower...

So everyone else now tested the 3rd version:
(core 2 duo)
ps: use multy thread, 99% (here) have more then 1 cpu core
give one half poly check loop - to first thread and second half - to second thread =) (or more threads)
It's a challenge, time to turn my water pump speed up and get 4.5ghz
Ram is probably a big factor here though. Guess I shouldn't bother.
Exactly how does the SAT function work? If it doesn't use any trigonometry, square roots or the likes, it's most likely RAM limited. Multithreading might help up to a point, especially on hyperthreaded computers. Hyperthreading will allow it to quickly switch to another thread if a cache miss occurs (as far as I know).

Yeah. I've already worked with mutithreading (I had a game running simulation and rendering in two different thread one time... I even think it was my first game? Yes it was... intresting... never did it again )

Yeah, even I do have more than 1 core... I've got 8 logical and 4 physical cores, and yeah I've got hyperthreading, and yeah It'd speed everything up... And finally yeah, it would be very nerdy... But intresting..

I don't know how you'd go about doing this... I mean, what exactly would you perform twice or more at the same time?

Splitting up the polygons to check into 2 different threads:
Meeeh... this could give very strange behavior if you want to do something with those collisions, since reactions would be run on 2 different threads (or even more...)... Also, in a real game example each polygon has to calculate collisions with each other polygon, which would give much much harder thread-safety problems...

And I can't think of another way...

How the SAT works:
first check circle vs. circle (not using sqrt().)...
and then: for each axis of the 2 to-check polygons: (axis  = normal)
calculate dot product of each vertex and the normal,

These are all calculations done...
So yeah, trigonometry is calculated, but it's only the dot product, so only + and *...
And finally:
About your threading library: I've already seen it once... I didn't take a look back then, but how exactly does it work, theagentBigDecimal (kidding )?

Anyways, now thank you all for your intrest, I really appreciate this

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

JGO Kernel

Medals: 107
Projects: 3

You think about my Avatar right now!

 « Reply #20 - Posted 2012-11-19 16:01:04 »

Forgot a quote:

Now to find a way to implement this in a game...

Seriously, what do you hope to do with this.

A Space Shooter maybe?

Eh, this is collision detection... You need it in almost every game...

The advantage of this engine is (or better the algorithm: SAT):
You can use any rotated / scaled / translated / however formed polygons, instead of only circles or AABB's (Axis aligned bounding boxes...)

And one more thing I forgot in the last post:
Any way we could get the source? or at least a way to implement it in our own?

I want to test it against my un-optimized version I mucked around with over a year ago

Eehh... It's not really optimized... not sure, why it's that fast

And I already linked the source, it's on github. If you talk about the test project, here is the source on pastebin:
http://www.java-gaming.org/?action=pastebin&id=314

This code class only uses LWJGL and the linked Utils class (see github link).

EDIT: Oh... sorry I just doubleposted...
Forgive me, but it somehow looks like something similar to java.util.concurrent... There are executers in there too

But the stuff with id generation and these atomic integers look intresting again. Is it somehow supposed to at least somehow be similiar to the OpenCL pipeline?

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

JGO Kernel

Medals: 107
Projects: 3

You think about my Avatar right now!

 « Reply #21 - Posted 2012-11-19 20:02:04 »

Eh... Sorry for triple-posting, but this is an update:

I now added Circle vs polygon Collision checking too.

The source is on pastebin.

I'm having 5-6 ms time, but about every second a three times as long GC pause :/ Have to profile this...

See my:
My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
theagentd
 « Reply #22 - Posted 2012-11-19 21:55:43 »

I cleaned out some old functionality (I was missing a Vec2 function in drawCircle() and the SpriteBatch did nothing?) and ran it with the server VM which gave a small performance boost.

Yeah. I've already worked with mutithreading (I had a game running simulation and rendering in two different thread one time... I even think it was my first game? Yes it was... intresting... never did it again )

Yeah, even I do have more than 1 core... I've got 8 logical and 4 physical cores, and yeah I've got hyperthreading, and yeah It'd speed everything up... And finally yeah, it would be very nerdy... But intresting..

I don't know how you'd go about doing this... I mean, what exactly would you perform twice or more at the same time?

Splitting up the polygons to check into 2 different threads:
Meeeh... this could give very strange behavior if you want to do something with those collisions, since reactions would be run on 2 different threads (or even more...)... Also, in a real game example each polygon has to calculate collisions with each other polygon, which would give much much harder thread-safety problems...

And I can't think of another way...

How the SAT works:
first check circle vs. circle (not using sqrt().)...
and then: for each axis of the 2 to-check polygons: (axis  = normal)
calculate dot product of each vertex and the normal,

These are all calculations done...
So yeah, trigonometry is calculated, but it's only the dot product, so only + and *...
And finally:
About your threading library: I've already seen it once... I didn't take a look back then, but how exactly does it work, theagentBigDecimal (kidding )?

Anyways, now thank you all for your intrest, I really appreciate this
Multithreading is easy as long as you avoid all synchronization. For a real game it's easy to do thread the biggest parts of the collision detection/response per object. Just divide the objects into chunks and process each chunk in different threads.

In a real game you might have a flow looking somewhat like this:

2. For each object:
1. Query area around object for other objects.
2. For each neighboring object:
1. Check if they intersect.
2. If they collide, react to the collision.

The first part, building the quad tree is very hard to thread, since we'd need to use a synchronized() block (or some other form of synchronization) every time we modify the same resource from multiple threads, which obviously is for each object. Since the quad tree can only be modified by one thread at a time, it doesn't make much sense to thread it. Hopefully it will not be our main bottleneck, and we might be able to do other things like rendering terrain or updating particles at the same time.

In the first loop, for each object we will query the neighboring area from the quad tree and get a list over the neighbors (bad) or a callback for each neighbor (good). Such a method is inherently thread-safe since it only reads information from the quad tree (though it is possible to screw it up by using instance/static variables to store temporary variables). We then run the collision detection (SAT) against each neighbor. For each collision we need to calculate a collision response. I'm assuming that we're making a 2D physics engine or something here, in which case we calculate a force to apply to both objects. Now, assuming we have eliminated duplicate collisions (X collides with Y, but Y also collides with X) we a concurrency problem. Since we're calculating the force for a collision pair, we need to apply this force to both objects in opposite directions. To write data, we need synchronization since each object can potentially affect every other object, but even synchronization won't help if you want 100% deterministic results. Even with synchronization, the force from multiple collisions with the same object will be applied to the object in a random order, and due to how floating point numbers work, (a + b) + c might not be exactly the same as (b + c) + a. So even if we completely kill parallelism for the collision response, we're still having a certain level of randomness here.

* for example by comparing an ID number between the objects. If X.id > Y.id then run collision detection. When Y detects the same collision, it'll quickly skip that collision check since the Y.id > X.id is not true.

 1  2  3  4  5  6 `for (int i = 0; i < polys.length; i++) {     if (Collision.polyVsPoly(quad, polys[i])) {          collisions[i] = true;          colliding = true;     }}`

I used my threading library for it, so you'll need it in your class path to test it: http://www.java-gaming.org/?action=pastebin&id=316 (look at initMT() and tick() )

Myomyomyo.
matheus23

JGO Kernel

Medals: 107
Projects: 3

You think about my Avatar right now!

 « Reply #23 - Posted 2012-11-19 22:10:58 »

Appreciate him guys!!! Appreciate! He deserved it, seriously

Thank you so much... this just gave me so much information and motivation to continue. Again, thank you so much

Also, judging from this:
Your library sound pretty revolutionary... I mean... in the future we will have 64-core 5GHz cpu's, so...
Also I'm pretty sure this makes Mutithreading and especially designing much easier

One more thing:
I cleaned out some old functionality (I was missing a Vec2 function in drawCircle() and the SpriteBatch did nothing?) and ran it with the server VM which gave a small performance boost.

Yeah... the sprite batch wasn't used later, because it wasn't able to draw line loops...
And the Vec2 function (I guess you are talking about "rotate()"?) should be pushed to github now

See my:
My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
theagentd
 « Reply #24 - Posted 2012-11-19 23:03:35 »

Thanks, I've been trying to convince people to use that library for a while... >_>

It's not really revolutionary. It's just promoting a scalable way of multithreading games. You still have to code according to that way of thinking. It doesn't just magically cause everything to run on different cores, nor does it ensure any synchronization whatsoever. The library just does what you tell it to do with the Tasks it gets. YOU have to ensure that the Tasks are thread safe and won't crash.

EDIT:
Here's a benchmark of your code vs my hacked in multithreading on my hyperthreaded quad-core. It's not really optimal, some things like clearing the buffers and all is still single-threaded.

100 000 objects: Single: 12ms, 8 threads: 4ms.
500 000 objects: Single: 59-60ms, 8 threads: 18-19ms.

Around 3x performance for just around 20 lines of extra code to setup everything.

Myomyomyo.
ClickerMonkey

JGO Coder

Medals: 20

Game Engineer

 « Reply #25 - Posted 2012-11-20 01:38:10 »

Perhaps we should make a competition with this... given a set of scenarios... who can create the best spatial database?

Metrics
• Speed
• Memory Usage
Factors
• Speed of moving objects
• Percent of moving vs stationary objects
Functionality
• search( Shape, Offset, entity types to test against, callback )
• nearest( Shape, Offset, maximum entities, OR maximum distance, entity types to test against, callback )

Huh, huh, huh?

ra4king

JGO Kernel

Medals: 345
Projects: 3
Exp: 5 years

I'm the King!

 « Reply #26 - Posted 2012-11-20 05:55:03 »

theagentd, you're just a god aren't you.

namrog84

JGO Ninja

Medals: 46
Projects: 4

Keep programming!

 « Reply #27 - Posted 2012-11-20 07:30:26 »

I'm gonna try and integrate this into the game I am currently working on!
good job

"Experience is what you get when you did not get what you wanted"
theagentd
 « Reply #28 - Posted 2012-11-20 10:20:03 »

I'm gonna try and integrate this into the game I am currently working on!
good job

Thanks! There's a new version up on the project page now with slightly better performance and some new features. If you have any questions you know where to find me. =S I still haven't got exactly how Google Code works; the SVN trunk isn't updated and I couldn't find out how to make it host the Javadoc online. There's a .rar for the Javadoc though (and it's available from Eclipse since the source code is in the .jar library file).

Myomyomyo.
sproingie

JGO Kernel

Medals: 202

 « Reply #29 - Posted 2012-11-20 16:55:27 »

Between 13 and 20 for 175,000 objects.  Cranked it up to a million, averaged about 110ms

i7 3770 3.5GHz (no OC for me here), GTX690

Pages: [1] 2
 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.
 Dwinin (26 views) 2014-09-12 09:08:26 Norakomi (57 views) 2014-09-10 13:57:51 TehJavaDev (71 views) 2014-09-10 06:39:09 Tekkerue (37 views) 2014-09-09 02:24:56 mitcheeb (57 views) 2014-09-08 06:06:29 BurntPizza (41 views) 2014-09-07 01:13:42 Longarmx (27 views) 2014-09-07 01:12:14 Longarmx (34 views) 2014-09-07 01:11:22 Longarmx (33 views) 2014-09-07 01:10:19 mitcheeb (40 views) 2014-09-04 23:08:59
 BurntPizza 33x princec 23x Riven 20x Rayvolution 17x ags1 16x basil_ 15x KevinWorkman 14x kevglass 12x theagentd 12x nsigma 11x LiquidNitrogen 10x SHC 8x HeroesGraveDev 7x The Lion King 7x cylab 6x EgonOlsen 6x
 List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27Resources for WIP games2014-08-01 16:20:17Resources for WIP games2014-08-01 16:19:50List of Learning Resources2014-07-31 16:29:50List of Learning Resources2014-07-31 16:26:06List of Learning Resources2014-07-31 11:54:12HotSpot Optionsby dleskov2014-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