Is it possible that a FOR loop is split across threads?... just wondering

[Ben1]

@pspeed said: Not trying to pick on you but your optimization strategy took a wrong turn at the very beginning and it’s sometimes hard to get off later.

Oh wow, OK, well could you elaborate on that because as it sits now it’s extremely fast. I would not even have considered making it even faster. I have zero lag when changing terrain chunks since everything is done in an asynchroneous fashion from this other thread we’ve been talking about in the last 2 days. It’s instantaenous when I attach all of those geometries because it’s done progressively by smaller batches, one for each simpleUpdate() loop until everything is attached. I have tested this on a 4 years old graphics card-less laptop [not that it would actually matter anyways, but it’s still an old ass CPU too and only 4GB of RAM] and there’s still no lag for around 3000 props on the terrain. I’m very curious as to how exactly you would have done that any better. You’re fast to point the finger, but to date, you have not brought any real concrete coding solutions on the table.

To answer your question: I have moved all collision checks on the same thread and I’m now 100% free of those exceptions. It works just as fine, it was just a matter of splitting my code into different classes, that’s all.

[pspeed]

@.Ben. said: Oh wow, OK, well could you elaborate on that because as it sits now it's extremely fast. I would not even have considered making it even faster. I have zero lag when changing terrain chunks since everything is done in an asynchroneous fashion from this other thread we've been talking about in the last 2 days. It's instantaenous when I attach all of those geometries because it's done progressively by smaller batches, one for each simpleUpdate() loop until everything is attached. I have tested this on a 4 years old graphics card-less laptop [not that it would actually matter anyways, but it's still an old ass CPU too and only 4GB of RAM] and there's still no lag for around 3000 props on the terrain. I'm very curious as to how exactly you would have done that any better. You're fast to point the finger, but to date, you have not brought any real concrete coding solutions on the table.

Nice. You’re right. I never contribute any code to anyone. Nor have I ever discussed in great detail several times how to do this sort of object to object collision thing. Seriously?

Whatever man. I just didn’t want to waste my time spelling out a different approach if you already weren’t interested. I have better things to do with my time.

Is your current approach basically to check every spatial against every other one?

[Ben1]

Dude. Yeah seriously. Please read my posts without and attitude and it will all make more sense to you, I promise.

I never said you don’t contribute to anyone. I said: “You’re fast to point the finger, but to date, you have not brought any real concrete coding solutions on the table.” and that means, in plain english, that for 3 days straight, all you did is accuse me of having poor coding skills but never actually put up some code snippets to help me to fix the issue, it’s all abstract concepts and JME3 core obviousness to you that a beginner like me can’t understand or does not have time to invest in comprehending. I’m using JME3 because those basic problems should be taken care by skilled programmers like (probably) you and other JME developpers. Before you go rage and accuse me that I lost YOUR own valuable spare time, I should repeat that as it stands since yesterday, I do not need code examples anymore. I FIXED THE PROBLEM and it’s working perfectly now. I even +1’ed you yesterday in sign of appreciation!

I don’t know what else you want from me by continually posting here, also greatly defocusing on the original problem. Please let’s all stay polite and for god’s sake, please stop your sarcasm and negative criticism. I can understand if your life is unsatisfying or maybe you’re having a rough time at the moment, but I do not need this from you. Nobody does. *** I do consider everything you and other people posted here and I fixed my issue based on various information you and other people provided, so you’re responsible in part for the success of the problem solving! Now, the case is now closed.

Also, out of curiosity, if you don’t like to post here and noobies with poor coding skills like me make you aggressive, why don’t you use your spare time to do something else more enjoyable instead? What do you expect? Skilled programmers mostly won’t use JME3, they will make their own SDK or code directly from scratch and certainly not in Java. I’m a beginner and I’ve been learning JME3 only for a couple of months PART TIME. For christ’s sake, look at what I made! You should be proud that the community of guys like me invest their own time into your platform and produce stuff like this! I’m enjoying it and I would have figured you’d be proud of us making these apps with your platform! Let’s all be friends and be happy, no? BE PROUD OF YOURSELF MAN. You’re part of this success!!

[t0neg0d]

@.Ben.
Hey… this idea is probably a little late in the conversation as you fixed the issue…

But have you considered placing items via the mesh triangles instead of ray casting or geometry collision?

The general idea is to get a random triangle from the mesh and use the the 3 verts + the triangle normal to place the plant/rock/tree etc.

It can be done multithreaded as the is no collision involved.

If you are interested in the possibility, the Emitter System I posted out here uses this technique… and the Test Project I uploaded recently shows an example of using it to place static leaves on a tree.

It is REALLY easy to implement and would likely be about 1000% faster.

EDIT: On a side note… you could just use the Emitter to place everything for you (for each type of plant/rock) As long as they have a common material, it will hand you back a single static mesh with everything in place. So you thousands of geometries… would likely become 10’s of geometries.

[Ben1]

@t0neg0d said: EDIT: On a side note... you could just use the Emitter to place everything for you (for each type of plant/rock) As long as they have a common material, it will hand you back a single static mesh with everything in place. So you thousands of geometries... would likely become 10's of geometries.

I am interested in trying what you described, altough I am unaware of how this works, I’ll have to take a look at it later on. What I’m currently doing yields very good performance tough.

I have around 25 different plant types, 25 different trees and currently 2 rocks. They all use just ONE material all together via an in house texture atlasing technique I developped based a little bit on what is described in the tutorials. After positionning all the geometries and colliding them to make sure trees don’t grow on top of rocks and so forth, I’m actually batching them all down so that they become just ONE geometry. So in the end I have just 1 geometry and 1 material. I’m using the buffers to send them their sizes, position, texture atlas ID and so forth.

I’m even able to make 100% culled boxes on top of EACH of those thousands of geometries so that when the player clicks a plant, they can pick it up via a collideWith().

As you can see on screenshots, I’m getting between 100fps and 150fps for up to 10000 visible wind waving billboards along with their own projected shadows on the terrain, etc… and this for a 3000+ frustum far rendering distance. It’s actually not that bad and I’m not done optimizing.

We’re really off topic here tough. Let’s wrap this up. Thanks everybody for all your suggestions.

[t0neg0d]

@.Ben. said: I am interested in trying what you described, altough I am unaware of how this works, I'll have to take a look at it later on. What I'm currently doing yields very good performance tough.

I have around 25 different plant types, 25 different trees and currently 2 rocks. They all use just ONE material all together via an in house texture atlasing technique I developped based a little bit on what is described in the tutorials. After positionning all the geometries and colliding them to make sure trees don’t grow on top of rocks and so forth, I’m actually batching them all down so that they become just ONE geometry. So in the end I have just 1 geometry and 1 material. I’m using the buffers to send them their sizes, position, texture atlas ID and so forth.

I’m even able to make 100% culled boxes on top of EACH of those thousands of geometries so that when the player clicks a plant, they can pick it up via a collideWith().

As you can see on screenshots, I’m getting between 100fps and 150fps for up to 10000 visible wind waving billboards along with their own projected shadows on the terrain, etc… and this for a 3000+ frustum far rendering distance. It’s actually not that bad and I’m not done optimizing.

We’re really off topic here tough. Let’s wrap this up. Thanks everybody for all your suggestions.

Since the topic is closed… how are you sectioning these? Per terrain tile? i.e. To make use of camera frustum culling.

[pspeed]

@pspeed said: Anyway, I still think your overall approach may be flawed. Hard to say but I've never need to have a pool of threads performing collision checks before.

Here was my hint that there might be a better way to do what you are doing.

In a thread where I’ve been basically repeating myself since my second response… over and over (*)… coming up with different ways to phrase the same things… it’s hard not to get frustrated. Someone less patient would have probably given up a long time ago.

So when I repeated that there is probably a better way to do what you are doing, I was less nice about it than I could have been.

If you are ever curious to improve what you are doing… things to look into are:
-just doing radius checks instead of involving JME’s collision system… it will be exponentially faster.
-“sparse grids” as a way of indexing the objects to avoid having to perform many collisions at all. Instead of the 1000th object having to hit every other object it may hit none or only 2-3 objects.

You could probably get the placement of 1000 objects down to a 1 or 2 milliseconds this way.

Anyway, good luck with your game.

• • oh, except for the side conversation where you as much as said our engine design was stupid. I wonder why I got frustrated.

Edit: and by the way, now that we have a clear picture of what you are actually doing on a separate thread it makes total sense to do it that way… as a thread pool I mean.

[Ben1]

@t0neg0d said: Since the topic is closed... how are you sectioning these? Per terrain tile? i.e. To make use of camera frustum culling.

Oh yeah, it’s definitely 1 batch geometry per terrain quad. Of course, else the fps would drop substantially because of the [lack of] frustum culling, it would be unplayable, especially with 49 terrain quads, so more than half of those are culled that way. On laptops I bring this down to 9 terrain quads. Of course later on when I’ll be very focused on optimization, I’ll have to test if subdividing these even more would help or not. I think not, but who knows, I haven’t tried yet. All I know is at one point, the more subdivisions, the slower.

I’m liking that idea to use of the terrain quad’s triangles to place vegetation tough, because the triangles have everything I need to place my trees: a position, a normal for the slope, etc… the only thing it doesn’t have is if there’s a rock on it or not… collisions on rocks are inevitable I think.

@pspeed said: -just doing radius checks instead of involving JME's collision system... it will be exponentially faster.

Please elaborate on this suggestion if possible.

@pspeed said: -"sparse grids" as a way of indexing the objects to avoid having to perform many collisions at all. Instead of the 1000th object having to hit every other object it may hit none or only 2-3 objects.

You could probably get the placement of 1000 objects down to a 1 or 2 milliseconds this way.

I’m not colliding each geometry against all geometries, as I posted a couple days ago in this thread, I’m colliding with a SELECTION of geometries and that means sometimes 4 or 5 only. So in total it’s like maximum 4000 or 5000 collision checks for the whole thing (not 1000999998997996… oh no, trust me my computer would be hanging way before it reaches even half of those!). I do agree it would be even better to divide these by grids tough so that a far away rock will not be tested against closer trees, but I’m wondering if the time it takes to do the IF checks to actually see if the collisions are necessary for each geometry will take even longer than actually doing those collisions, not sure, would have to test this. I’m thinking maybe if I just do that roughly like:

1. for each rock, put it in one of those lists: “first half of terrain quad” or “second half of terrain quad”
2. for each tree in first half collide with “first half of terrain quad”
3. for each tree in second half collide with “second half of terrain quad”

Just like that I may be saving half of the collisions. BUT… then again, I mean this is optimization… I’m not there yet, I do agree there are so many better ways of doing what I want to do, but I’m just at the idea exploration stage if you will… I’m so going to rewrite the whole application when I’ll be finally decided on what game exactly I’ll be doing.

TOUGH, I have profiled a somewhat typic chunk’s computation time and I’m getting this:
PROFILE: Raycast Grass Billboards Layer for 4000 objects = 691 ms (0,172ms per collision)
PROFILE: Raycast Tree Billboards Layer for 393 objects = 14 ms (0,035ms per collision)

Not quite sure why ray tracing the grass patches take magnitudes more time than trees… that seems odd but anyhow it’s still not “1 or 2 milliseconds” that you’re saying could be achieved with the technique you’re talking about, so I’m quite interested by that actually.

@pspeed said: * – oh, except for the side conversation where you as much as said our engine design was stupid. ;) I wonder why I got frustrated.

Never said that either. I said it was counter-intuitive and not thread-safe, which personnally I think is something that could be improved (even tough Empire Phoenix seems to think it’s not possible because it would be too slow), but ANYWAY the point is by that post, you were ALREADY telling me to “post the stack trace or get the fuck out” or bursting sarcasm on all your replies. I did post the stack trace and I did tell you I was sorry, I was tired and simply forgot to do it… I didn’t mean to upset you or anybody else, but man, you have got to drop that attitude, I’m a beginner and I’m still trying to understand JME3, I don’t have a PhD and I don’t do that as a professional job, this is like my new hobby, nothing more for now I’m sure you guys are losing a lot of people because of this kind of aggressiveness towards noobs. It’s just unnecessary. Don’t expect newbies to learn JME3 in a month or two. This platform is HUGE and thanks to that, it’s appealing to beginners like me. But we’re still beginners, you know what I’m saying? I can feel the same thing when a client makes me lose my time with stupid questions or does not do what I tell them to fix their issue, but… they’re still computer unsavvy and it’s my job to stay calm and help them, even if they’re stupid or slow or even if it takes 2 hours to help them setup their Outlook and then they call you back the day after because they erased their account and lost all their emails (lol). Anyway, I think you get the point and again I’m sorry if I made you go mad, but let’s stay calm about it. I really appreciate your support and everybody else’s support too.

@pspeed said: Anyway, good luck with your game.

Thanks.

@pspeed said: Edit: and by the way, now that we have a clear picture of what you are actually doing on a separate thread it makes total sense to do it that way... as a thread pool I mean.

Smelling troll here I’m serious, at this point I’m not sure if you’re messing with me or not. BUT if you’re serious about this, please could you give me a general idea of why that could have been wrong and what I could have done instead? You talked about the scheduler that was not looking like the appropriate choice… why? And what else could one be using instead of this? I took this approach in a [very limited] JME3 tutorial found around here. I do not know anything else to use in its place, but I can tell you it works quite well tough. My goal is to set a thread, continue executing my app and every like 100ms, check if the thread has finished and when it has, execute some more code like attach geometries on the sceneGraph and such (that cannot be done from a thread of course). So that’s why I’m doing it like this.

Thx for reading both of you I +1’ed again both of you, because I like those ideas you suggested and I’ll try to implement this later on. [damnit, I +1’ed the wrong post from you @t0neg0d oh well, you got a freebie then as I can’t remove it :P]

[pspeed]

ScheduledThreadPool is for running a set of tasks over and over at some fixed interval. It seemed like you were just running jobs and getting the results.

Your earlier explanations did not really explain why you were performing all of these collision checks so we had to guess at possible reasons. Your final explanation would have been excellent in the first post. For example, you could have been trying to get collision checks for some AI or something in which case this is probably not the best approach.

I don’t remember getting sarcastic until the end. I just kept having to repeat that multiple threads were hitting the same mesh instance… because that was fact. It was irrefutable… but there we were repeating the same argument when we could have been trying to figure out why or how you were sharing meshes when you didn’t think you were. I thought I was being quite patient all things considered… certainly more than some of the other posters on this thread.

Considering that by rights the exceptions should have been in the first post, having to ask twice is very frustrating. In the future, I think I will not even bother to drill into these. They turn nasty too quickly.

Edit: forgot to answer your other questions. Will reply again for that.

[pspeed]

re: Radius checks. It sounded like you were doing bounding shape to mesh checks or something. In general this is a lot of work to answer a simpler problem. It may seem like it’s more accurate in the beginning but for many cases it actually turns out to be the opposite.

For example, trees, rocks, etc. the meshes will all be BoundingBoxes even though they would be way better represented by cylinders or spheres.

If you know the radius of your objects and could somehow store it with them (as user data or otherwise), then you can perform really simple distance checks. You can actually even avoid doing the sqrt on them. Given your scenario you might even be better off doing this only in 2D space but I can’t be sure.

xDist = loc2.x - loc1.x;
zDist = loc2.z - loc1.z;
distSq = xDist * xDist + zDist * zDist;
if( distSq < squaredThreshold ) {
// they collide
}

This would also let you treat the trees as just their trunks for things like rock collisions or full tree radius for tree to tree collisions.

re: sparse grids

If done properly there really isn’t an “if check”. Just math.

int xCell = (int)(loc.x / cellSize);
int zCell = (int)(loc.z / cellSize);

(note: care has to be take if x or z can be negative)

Then when placing an object you only have to check a 1 cell radius around the plopped cell for collisions. Furthermore, having your nodes binned in this way could be useful for other checks you might need later.

If your world is large then the “sparse” part is that you don’t actually need a full array of cells as you can turn the xCell and zCell into a hashmap key and then you will only have entries for the cells that actually exist. HashMap lookups are near “constant time” so it’s not much worse than a straight array lookup. (in the best case it’s identical)

On the other side, if this is for tree, rock, etc. placement as it sounds like, sometimes it can be better to flip it upside down. I’m not sure of your actual algorithm but given that you are performing collision checks it sounds like maybe you are randomly picking a position and then rejecting/recalculating if you get a collision? (Or are you somehow shifting the objects apart… which ends up being a nasty multidimensional problem.)

If so, it can often be better to just iterate over a grid of all potential locations and randomly decide what should go there. Noise can then be added to the locations to hide the grid without causing collisions (half grid size noise or whatever).

Because if the assumption of “generate point, possibly reject it” is true then one problem is that it’s unpredictable. If you end up with a lot of random hits in the same locations then you waste time rejecting them and it can’t be predicted how often this can happen.

Also, a grid-seeded approach also works well with planting algorithms and so on… where certain areas are more likely to have grass or trees or rocks for whatever reason.

I place the blades of grass in the Marching Cubes demo using this approach. Blade placement is based on how “up” the surface is facing, etc… The roughness of my terrain means that randomly picking points and seeing if they are valid would lead to a lot of misses.

[Ben1]

Those sound like good ideas to me.

@pspeed said: I’m not sure of your actual algorithm but given that you are performing collision checks it sounds like maybe you are randomly picking a position and then rejecting/recalculating if you get a collision? (Or are you somehow shifting the objects apart… which ends up being a nasty multidimensional problem.)

Tree to tree collisions cannot happen with the way I set this up and as a matter of fact, vegetation to vegetation cannot happen at large either. What actually happens is I iterate on for x = 0 to 16641 (which is BlockSize ^2) so only 1 element can be on a X position and I shift their positions slightly (but not enough for 2 rows to actually cross on each other) BUT rocks can be huge, like take 100 squared positions if you will, so that’s why they’re the type of props that I want to check the trees against… because big trees cannot grow on rocks basically. If rocks were as small as the other vegetation props, I would never even need to check collisions at all. Sparse grids sound like a good improvement for a start and it will not take long to integrate this to my current code. I’ll start with a simple grid of 2x2 per terrain quad and that will effectively already cut the calculations by a factor of 4… at that will take probably less time to implement this than it took me to write this paragraph of text lol

@pspeed said: Also, a grid-seeded approach also works well with planting algorithms and so on… where certain areas are more likely to have grass or trees or rocks for whatever reason.

I think I’m doing something completely different, at least if I get you right. What I do is I have a noise map and depending on values, there is a certain type of vegetation or rock on that point. It’s quite simple and effective and gives quite smooth transition results. It accounts for rarity and diversity too. I quite like how my vegetation generation method is done. It’s 100% seedable and looks like real world possibilities.

[pspeed]

@.Ben. said: Those sound like good ideas to me.

Tree to tree collisions cannot happen with the way I set this up and as a matter of fact, vegetation to vegetation cannot happen at large either. What actually happens is I iterate on for x = 0 to 16641 (which is BlockSize ^2) so only 1 element can be on a X position and I shift their positions slightly (but not enough for 2 rows to actually cross on each other) BUT rocks can be huge, like take 100 squared positions if you will, so that’s why they’re the type of props that I want to check the trees against… because big trees cannot grow on rocks basically. If rocks were as small as the other vegetation props, I would never even need to check collisions at all. Sparse grids sound like a good improvement for a start and it will not take long to integrate this to my current code. I’ll start with a simple grid of 2x2 per terrain quad and that will effectively already cut the calculations by a factor of 4… at that will take probably less time to implement this than it took me to write this paragraph of text lol

I think I’m doing something completely different, at least if I get you right. What I do is I have a noise map and depending on values, there is a certain type of vegetation or rock on that point. It’s quite simple and effective and gives quite smooth transition results. It accounts for rarity and diversity too. I quite like how my vegetation generation method is done. It’s 100% seedable and looks like real world possibilities.

I think that actually sounds like what I’m talking about.

How big is a terrain quad? There may be an even better approach to all of this if “for x = 0 to 16641” means what I think it means.

If it does mean what I think it means, any reason you do 0 to 16641 instead of two nested loops of 0 to width, 0 to height?

[Ben1]

Well… no particular reason no, it’s just because it’s 1 loop instead of 2, but it could be done with 2 loops, not sure why it would be better or not, I didn’t ask myself this question yet. But you do understand 0 to 16641 is actually because it’s:

row #0: 0 to 128, then
row #1: 129 to 256, then
row #2: 257 to 384… etc…

[pspeed]

@.Ben. said: Well... no particular reason no, it's just because it's 1 loop instead of 2, but it could be done with 2 loops, not sure why it would be better or not, I didn't ask myself this question yet. But you do understand 0 to 16641 is actually because it's:

row #0: 0 to 128, then
row #1: 129 to 256, then
row #2: 257 to 384… etc…

Yeah, I understood. I just didn’t get why.

Two loops is a more maintainable approach in the long run. There’s also less to get wrong. There is no downside either, really.

[pspeed]

So, if you are iterating over a fixed set of cells (0…128, 0…128) then you could just create a grid to mark where you’ve already put stuff. So when you put rocks in there, you mark many cells of the grid that roughly approximates the rock shape. (or just block it out as a square if you like). Subsequent objects need only look to see if there is already something in the cell.

boolean[][] taken = new boolean[128][128];

[Ben1]

The rock is round tough, so that would be a really blurry approximation… Seen from the top, it would look a lot “square”… By using the collideWith() function, it’s accounting for very very precise marks, allowing trees to grow really on the edge of the rocks.

[pspeed]

@.Ben. said: The rock is round tough, so that would be a really blurry approximation... Seen from the top, it would look a lot "square"... By using the collideWith() function, it's accounting for very very precise marks, allowing trees to grow really on the edge of the rocks.

What are you colliding with it? The bounding shape of the tree or something else?

Are all the rocks basically the same size or does it vary? How many ‘cells’ wide are they?

[Ben1]

Tree (trunk) quad to rock model (I’m sure there are faster ways, but this is precise which makes it more realistic… altough it’s not that much realistic in the end but oh well… haha…). Every single geometry in my project is varying in size. It’s not a bloxel engine or a Minecraft clone, nothing is “cell-wide” or blocky.

[pspeed]

@.Ben. said: Tree (trunk) quad to rock model (I'm sure there are faster ways, but this is precise which makes it more realistic... altough it's not that much realistic in the end but oh well... haha...). Every single geometry in my project is varying in size. It's not a bloxel engine or a Minecraft clone, nothing is "cell-wide" or blocky.

(another vote for radius checks over box → mesh collisions then… your trunk could get right up next to the rock in that case)

I mean, there is probably some grid size that could still work for a “filled” state but I agree that the more your objects vary in size the less efficient it will be… especially as they vary in size relative to density. In other words, if the number of cells you’d have to have largely dwarfs the number of objects you are placing then it isn’t worth it.

In the case, using the earlier approach, a grid size roughly equal to around two or three times the largest object’s radius is probably optimal. The binning is basically free so the constraints are to pick a grid size that limits the number of cells you’d have to check while also limiting the number of comparisons you might have to do in a cell. Probably a ‘rock sized’ cell in your case would be optimal. Rocks would only ever have to check 4 cells and most things would only have to check one. On the other hand, if there are very few rocks but tons of other stuff then an even smaller cell size could be warranted.

Anyway, if you split your ‘chunk’ four ways as you mentioned then it should be easier to try different split sizes later, I guess.