Moebius Engine [Update 2]

Hi Everyone,



just uploaded a new video of my game engine:



http://www.youtube.com/watch?v=KeRoXpsuebQ



I still have some issues with the performance of the sectors - caused by jbullet (because CollisionShape needs to be instantiated synchroniously to the rendering thread or the physic engine will sometimes crash) and due to the ambient occlusion. Soon I’ll try to calculate the occlusion wihtin the shader to find out if this is possible at all. Maybe this will finally increase the speed :slight_smile:

3 Likes

@entrusc

Ah, I see. Pretty cool idea.

sweetness!

Nice. How are you doing the lighting and shadowing?

@zarch said:
Nice. How are you doing the lighting and shadowing?

It looks like vertex color, but i can be wrong
@zarch said:
Nice. How are you doing the lighting and shadowing?

I use a 3D-Texture to store the shadow values that are precalculated in Java. But as you can see in the video a sector of 32x32x128 takes about 1,09 sec to complete (including tesselation, block light calculations and collision shape creation).

It gives a nice effect though.

So you store the lighting level per corner of each square in a 3d texture and you compute all those values in the CPU? I can see how that would be slow to generate but fast to render.



Have you considered GPU generating the texture and/or updating the lightmap in a background thread?

@zarch said:
So you store the lighting level per corner of each square in a 3d texture and you compute all those values in the CPU? I can see how that would be slow to generate but fast to render.

Have you considered GPU generating the texture and/or updating the lightmap in a background thread?

Yes I have - it is not really possible to do the calculation in a shader because the data can only be calculated iterative - meaning that I can't parallelize the calculation - hence not really possible on GPU. But maybe there is another way to calculate the lightmap? Basically I iterate over x and z axis start to put light from top to bottom as long as there is no obstacle in the way. When I encounter a solid block I stop and continue with the next x,z coordinate. Next step (the light update) is to smear the values by checking if the sourrounding blocks are less lit then the current block's (lightness-1) if that is not the case I set the lightness of these blocks to (lightness-1) and do the same smearing to this block. Eventually this will terminate and leave me with a nice lightmap. But it takes quite long to calculate ;)

And yes the lightmap is calculated in a thread - in fact moebius is designed to be massive concurrent if possible. There are (CPU-1) Threads working on the sector generation.

Here you can see a benchmark showing that the problem is in fact the light updating and the mesh tesselation (which is not perfect because it uses too many lookups resulting in a lot of perlin calculations)

[java]
light maps (daylight + blocklight) 108,74ms 108,74ms
mesh tesselation 644,18ms 535,44ms
- getting block from terrain 62,07ms
- adding block mesh 222,87ms
- determining sourrounded state 189,30ms
- adding physics block mesh 27,56ms
- init items 18,12ms
opaque geometry construction 656,94ms 12,76ms
transparent geometry construction 657,27ms 0,33ms
attatch nodes 657,39ms 0,11ms
physic construction 1 661,12ms 3,74ms
physic construction 2 662,16ms 1,04ms
physic construction 3 662,50ms 0,34ms
physic construction 4 663,59ms 1,08ms
physic construction 5 664,85ms 1,26ms
physic construction 6 665,18ms 0,34ms
physic construction 7 665,51ms 0,33ms
physic construction 8 669,54ms 4,03ms
physic construction 9 674,25ms 4,71ms
physic construction 10 675,47ms 1,22ms
physic construction 11 677,72ms 2,25ms
physic construction 12 679,00ms 1,28ms
physic construction 13 680,72ms 1,73ms
physic construction 14 683,72ms 3,00ms
physic construction 15 688,33ms 4,62ms
physic construction 16 693,59ms 5,26ms
node update 693,60ms 0,01ms
light update 1125,23ms 431,62ms
Overall 1125,23ms
[/java]

I’m not sure what you are trying to achieve with the smearing?



Your description only covers 2 dimensions and I don’t really follow how you avoid wrapping around obstacles and filling in shadow by accident.

I think the smearing is that the light propagates outward a little after hitting a block. ie when the light went into the hut he made.

@zarch said:
I'm not sure what you are trying to achieve with the smearing?

Your description only covers 2 dimensions and I don't really follow how you avoid wrapping around obstacles and filling in shadow by accident.


@entrusc said:
[...] Basically I iterate over x and z axis start to put light from top to bottom as long as there is no obstacle in the way. When I encounter a solid block I stop and continue with the next x,z coordinate.


I think this algorithm is a bit to complex to write it down in just one sentence ;) - so this would translate to the following pseudocode:

[java]
for (int x = 0; x < 32; ++x) {
for (int z = 0; z < 32;++z) {

for (int y = 127; y >= 0; --y) {
if (getBlockAt(x, y, z).isSolid()) {
break;
}
setLight(x, y, z, FULL_BRIGHTNESS);
}

}
}
[/java]

And then I would "smear" it like that:

[java]

for (int x = 0; x < 32; ++x) {
for (int z = 0; z < 32; ++z) {
for (int y = 0; y < 32; ++y) {
spreadBrightness(getBlockAt(x, y, z));
}
}
}

void spreadBrightness(Block block) {
int brightness = getBlockBrightness(block);
if (brightness <= 1) return;
for (Block souroundingBlock : getSouroundingBlocksOf(x, y, z)) {
if (!souroundingBlock.isSolid() && getBlockBrightness(sourroundingBlock) < brightness - 1) {
setLight(souroudingBlock, brightness - 1);
spreadBrightness(sourroundingBlock);
}
}
}

[/java]

I hope that made it more clear. But still that way of calculating the brightnesses has a complexity of at least O(2n^3).
@entrusc said:
I think this algorithm is a bit to complex to write it down in just one sentence ;) - so this would translate to the following pseudocode:

[java]
for (int x = 0; x &lt; 32; ++x) {
for (int z = 0; z &lt; 32;++z) {

for (int y = 127; y &gt;= 0; --y) {
if (getBlockAt(x, y, z).isSolid()) {
break;
}
setLight(x, y, z, FULL_BRIGHTNESS);
}

}
}
[/java]


How does this make shadows in more than one direction or from multiple light sources though?
@zarch said:
How does this make shadows in more than one direction or from multiple light sources though?

This is only the calculation for sun light directly from above. But the other lights, I call them "blocklights" are calculated by a quite similar approach: you just put light with setLight() somewhere and smear it using the spreadBrightness() method. The removal of the light on the other hand is a bit more tricky - but also doable :).

And the shadows are created by the smearing algorithm - if the block is solid the light is not distributed anymore - so the blocks behind solid blocks that have no direct sight line to the sky remain dark. Maybe I have to add that you initialize the block's light with 0. If you don't believe me just test the algorithm in 2D and see for yourself ;)

Lets say we have (hope the ascii art looks ok, these characters are the same size on my browser but yours may vary):



#####

##_

_________



If you put a light



#####

__#L#

_________



Then the light spreads



#####

#_LL#

__LLL



I can see that being mostly fine - but it’s only lit the right hand side of the room. If you spread it again:



#####

_#LLL#L

__LLLLL



Now the light is travelling around the wall (ok dimmer by now but it is effectively shining through the wall).

@zarch said:
Lets say we have (hope the ascii art looks ok, these characters are the same size on my browser but yours may vary):

__#####__
__#___#__
_________

If you put a light

__#####__
__#__L#__
_________

Then the light spreads

__#####__
__#_LL#__
____LLL__

I can see that being mostly fine - but it's only lit the right hand side of the room. If you spread it again:

__#####__
__#LLL#L_d
___LLLLL_

Now the light is travelling around the wall (ok dimmer by now but it is effectively shining through the wall).


That's exactly how the algorithm works. The values if started with say 5 would look like that:


__#####__
__#345#1_
__1234321

So now you have minimal light around the corner - and that's okay because light might be reflected somewhere. After all it's just an approximation of light rays. But in the game it looks quite correctly - makes the light glowing a bit ;). I tried to build your case in the engine and it looks like that:

http://files.darkblue.de/moebius%20screenshot%2000066.png

But with just one more layer of walls it looks like that:

http://files.darkblue.de/moebius%20screenshot%2000067.png
1 Like

I actually like the look and internal working of the algorithm.



What if you mix in the lightcolor a bit of the color of the last field? Maybe it would give an even better feeling for bouncing light…

How costly would it be to check if there is a solid block between the current box and the light? If there is, maybe reducing the lightfactor twice as fast would look good.

The cost for checking line of sight between blocks would be bounded by the maximum radius of the light. If the light radius is 10 then only ten blocks would have to be sampled to determine if the light is visible or not (if I’m not thinking terrible wrong).

Actually it would be worse than that - since you are sampling those extra blocks for each light and for each block effected by the light - and also you need to know where those lights come from.





I actually sketched out a similar algorithm to yours a while ago, but with a couple of differences that both make it real time and handle the shadowing problem. It’s just a rough concept at the moment so I’ve no idea how well it would work but here it is:



Have the cells initially all set to black. Each cell stores an array of photons inside it.



This algorithm would work in parallel so if a suitable way to store the data was found (for example limit it to X photons per square and store it in a texture) then you could do all of this lighting work on the graphics card. I’d probably experiment with the algorithm first in java though and get it working first.



Each photon has:

ColorRGBA brightness (rgb is colour, a is intensity)

Enum direction (-z, z, x, -x, etc - could also store this in a vector, or whatever 6 main directions + 16 diagonals gives 24 I think)

float spread



Each frame

  1. For each cell move the photon in the direction of the light.

    1.1. If the spread factor is >0 then split the photon, brightness*(1-spread) goes in the direction specified, the remainder gets brightness*(spread)/8 and sent in the 8 adjacent locations with a new direction.

    1.2. Identical photons (direction & spread) get their light merged

    1.3. Photons with a brightness < some threshold get thrown away
  2. For each light emitter generate a photon with the correct settings



    The entire top of the field would have a light emitter generating a photon direction -z, brightness(1,1,1,1), spread 0.



    Walls would have an absorption amount from 0-1. 1 is perfect reflector, 0 is complete absorption, in practice I would limit the best value for reflection so it always absorbs at least some energy. Any photon hitting a wall gets its brightness multiplied by the absorption amount and then is flipped so it leaves at the same angle it came in.



    Something like a red glowing panel in a wall might have direction -x, brightness(1,0,0,0.5f), spread 0.5. This would cause it to glow most strongly against the wall directly opposite it but also spread out into the area around, bouncing off the wall and down passages to give the area around a red glow but never teleporting through walls.





    Advantages:



    (Almost) constant time runs - it doesn’t matter how many lights you add, the load does not increase massively as each cell is being processed anyway

    Proper shadowing/occlusion/etc so lights one side of a wall never penetrate it.

    Could be done massively parallel



    Disadvantages:

    Quite a lot of work processing photons (should be possible to offload to GPU)

    Slow speed of light - light always moves one cell per frame (should still be faster than the eye can see at reasonable framerates - and even when visible might give cool effects with light sweeping across the scene)







    Essentially to do it on the GPU I would use three textures. One stores last frame, one next frame, one light sources. The last/next textures would be swapped each frame. The data for each cell is packed into the textures and the GPU just goes through processes each one to the next (for each cell in dest, read the data from surrounding cells in source then add in the data from light sources).



    Once that is done the main rendering can just go ahead reading the data from each cell to know what light is present in each cell and what direction that light is going in.

nice algorithm - I myself had some plans to do the calculating on GPU. But the algorithm you describe is also iterative - that’s why the light only traveles with the fps. An important aspect is also to have an inverse to that algorithm so you can remove the light again if the light block is removed.



I recently saw a game that uses block lighting for the general light and normal phong lighting with a “solid” map (that has 1 for solid and 0 for non solid blocks at each position) for light calculations - but of course all the phong lighting was then done in shader in every frame - so the amount of light sources was kept low. But that still gave a nice effect :slight_smile:




@zzuegg said:
I actually like the look and internal working of the algorithm.

What if you mix in the lightcolor a bit of the color of the last field? Maybe it would give an even better feeling for bouncing light..
How costly would it be to check if there is a solid block between the current box and the light? If there is, maybe reducing the lightfactor twice as fast would look good.

Problem with colors in general is that it increases the computing time by a factor of three (for each color) because it has to be reversable (you basically have a brightness value for each color). And the light values in my game are currently only in the range [0-7] which would result in only 8^3 = 512 possible colors.