Fr0stbyte's Development Log

so will variable detail mean 1 chunk = 1 pixel when its farther away (sorta like mip-mapping)? i'm quite excited to test Copernicus on some ships i have that are to large for zeppelin. keep up the awesome work and thanks for keeping us updated!

Do a youtube search for "marching cubes" and you will get the general idea.

fr0stbyte124 wrote:

Do a youtube search for "marching cubes" and you will get the general idea.

I don't get it.... Anyway, I have a question. How many polygons does a single face of a block require? 2? Would ommiting the texture help increase generation speed and decrease the strain on the computer per visible polygon?

A block face uses one OpenGL quad and texture should be shrunk or removed completely at sufficient distance.

I was going to talk more about this in the Space thread, but I'll say a bit here, too. Marching cubes is a fast algorithm for extracting surface meshes from a field of voxels. One advantage of doing this is that you can change the resolution on the fly to reduce the geometry on the screen, something not possible with cubes.

There are a few disadvantages, though, and they come from the fact that Minecraft has a distinctive look due its use of cubes. First is the geometry. Marching cubes smooths things out. Most of the time you are using voxels that's a good thing, but not here. Minecraft is terraced, and the surfaces look different from different perspectives, especially grass. It would be possible to recreate the blocky geometry with hardware tessellation but that requires the use of OpenGL 4.0 (equivalent of DX11) compatible graphics cards, which most people, myself included, aren't going to have. The other problem is texture. Normally, you would have a much larger texture for all the ground terrain, to be shared over multiple polygons and blend smoothly together. Can't do that in minecraft because the transitions are distinct and decidedly square. Then there is the problem of how to make grass look right. Like I said before it looks different on the top and sides, and the proportion of one to the other depends on the angle you look at it. To reproduce something like that, you would have to use custom shaders, possibly repurposed parallax mapping I don't know.

It's a long road towards getting this stuff to look good, but we have the advantage of finite planets and no need to do all this in realtime. In any case I'm not working on it until after space. Maybe I'll have a better plan by then.

fr0stbyte124 wrote:

A block face uses one OpenGL quad and texture should be shrunk or removed completely at sufficient distance.

I was going to talk more about this in the Space thread, but I'll say a bit here, too. Marching cubes is a fast algorithm for extracting surface meshes from a field of voxels. One advantage of doing this is that you can change the resolution on the fly to reduce the geometry on the screen, something not possible with cubes.

There are a few disadvantages, though, and they come from the fact that Minecraft has a distinctive look due its use of cubes. First is the geometry. Marching cubes smooths things out. Most of the time you are using voxels that's a good thing, but not here. Minecraft is terraced, and the surfaces look different from different perspectives, especially grass. It would be possible to recreate the blocky geometry with hardware tessellation but that requires the use of OpenGL 4.0 (equivalent of DX11) compatible graphics cards, which most people, myself included, aren't going to have. The other problem is texture. Normally, you would have a much larger texture for all the ground terrain, to be shared over multiple polygons and blend smoothly together. Can't do that in minecraft because the transitions are distinct and decidedly square. Then there is the problem of how to make grass look right. Like I said before it looks different on the top and sides, and the proportion of one to the other depends on the angle you look at it. To reproduce something like that, you would have to use custom shaders, possibly repurposed parallax mapping I don't know.

It's a long road towards getting this stuff to look good, but we have the advantage of finite planets and no need to do all this in realtime. In any case I'm not working on it until after space. Maybe I'll have a better plan by then.

Ok, now it makes a little more sense, ty.

Offtopic, I was thinking of starting the script for a Futurecraft trailer for later on when the mod is more completed. Do you think it would be a good idea?

off topic: I think it's a little premature for that. At least wait till we have a solid list of features. Also you should pick out the music first and foremost.

No visual aids this time, and on top of that, this is reasonably high-level stuff. So, sorry about that.

=========================
Wednesday, November 9, 2011
=========================

Collision is still taking longer than I would like, mostly self-inflicted. But I said I would talk about it so that's what I am doing.

First, why do we need new collision? I discussed it in my very first post, but I'll do it again here. Originally Copernicus handled entity-ship collision by interrupting the existing entity collision method, transporting the entity into ship coordinates with corrected orientation, performing collision again, and transporting it back. And theoretically, that would be good enough. The problem though, was in the way collision is handled. Normally, you have the entity bounding box, you determine where its current velocity will take it, and check for other bounding boxes in that area. If the entity bounding box does not currently overlap with the terrain bounding box, but it will after this tick, adjust the entity's translation along that axis to make the two perfectly flush after the tick, and kill the velocity.

The problem comes when there is overlap. If there was even a millionth of a meter overlap between the two bounding boxes they will pass though one another like air. And that's exactly what would happen when I introduced rotation to the mix. Floating point multiplication introduces minuscule, but unavoidable error. It's kind of hard to say exactly how much error, but it was something around 10^-9.
Therefore (A * B) / B ≠ A. It's very, very close, but anything less than perfect will break the existing code. My temporary solution was to add a tolerance thresholds to everything, about 0.1m to collision boundaries, and 0.000001 everywhere else. It's ugly but it got the job done.

But Copernicus will do more than simple box vs. box collision, rotated about a single axis. It will support a variety of different shapes separated across different world spaces, and for that we need an entirely new collision model. This model is based on the Separating Axis Theorem (SAT), which states that two convex shapes intersect if and only if their projections intersect across every possible axis. Fortunately for us, there's only a handful of axes we actually need to test.

--------------------------------
Separating Axis Theorem
--------------------------------
I won't talk too much about it. This site does a fantastic job of explaining the algorithm with examples and everything. Be sure to give it a read.

Essentially, everything is reduced to single dimension projections. Two axis-aligned squares in a 2D space require two projections, one along their shared X axis and one along the Y, to determine if they intersect. If either projection fails to overlap then the two can't possibly be touching. Two oriented squares require 4 projections, two along the primary axes of the first square and two along the axes of the second. 3D gets a bit more complicated. For two axis-aligned boxes you only need projections along the X, Y, and Z axis, or pretty much what Minecraft does already. However, for two oriented boxes you need to check a whopping 15 axes. 3 for the primary axes of the first block, 3 for the axes of the second, and 3*3 for the cross products between the two sets of axes. That last set describes the 9 edge-on-edge cases. That sounds like a lot, and it is, but the great thing about SAT is that all of the projections have to overlap, so if any don't you can immediately stop checking.

--------------------
Optimizations
--------------------
Fixed and Indeterminate Orientations:
You can walk around in the game and rotate about, but your bounding box remains axis-aligned. Your orientation is not actually important. So, if you were on a rotated ship, you might as well align your bounding box to the ship axes like it would be in the normal world. In doing so, you can limit the axes you need to check Assuming you can walk normally on a ship (artificial gravity and all), that's just 3 axes instead of 15. Same goes for other entities which share at least partial alignment with the world axes.

Block Clusters:
By far the largest source of collision checks will come from ships themselves colliding with terrain. Ideally this will be kept to a minimum, but worst case scenario could involve thousands of collision checks every tick, so every optimization counts. The easiest thing to do is determine if terrain is anywhere near a ship. Make a ship-aligned bounding box around the ship and a world-aligned box around that. You can easily track the occupancy of terrain blocks within that box, or ideally check against the height map. If there are blocks inside the field, there is a chance they can collide with the ship. At this point is it no cheaper to check collision against the internal bounding box than it is to check directly against the ship blocks themselves, so might as well bite the bullet and do it all at once. Transformation into ship coordinates (or vice versa) is done with 4x4 matrix multiplication. This matrix combines the rotation matrix generated by the quaternion stuff with two translations to get the points into the right spot. This matrix only needs to be generated once per tick per flying object.

Also, for the sake of speed, all blocks with collision will be treated as cubes, regardless of their normal shape. This opens up a whole new set of optimizations. If you know it is cube on cube, you can precalculate nearly everything. You know which 15 axes to test, as it is the same for all block oriented the same way. You know the projection footprint of a cube along all 15 axes, as that is invariant to the position of the block. The scales will vary, but we only deal with inequalities, so even that won't matter. A rotated terrain block can only intersect blocks up to 1 away from its current position, for a total region of 3*3*3 potential cubes.

So this is what we do: First, treat the terrain block as a single point, and add its projection contribution to the projections of the other 27 blocks (26 actually, see below). Then we make a simple occupancy table, 2 bits for every cube in the ship's space, one for whether the space is occupied, and one for whether any of the 26 surrounding spaces are occupied. We make a second look-up table for the 26 surrounding blocks which stores the projections for that cube added to the projection of the terrain cube (above). We can keep reusing this as it will be the same for all cube collisions sharing that particular pair of orientations.

When the terrain point is moved into ship-space, check which grid element it resides in against the occupancy table. If occupied, you can immediately assume collision. If neither it or the surrounding points are occupied, you can immediately assume no collision. Otherwise, you do the main collision check.

First you need to do the dot product projection for the 15 axes to know where the terrain cube center exists along that particular axis (3 multiplications and 2 additions per dot product). But since we reduced the cube to a point, there is only 1 vector to project rather than 8. Also you are doing it in coordinates relative to the center of the ship-oriented cube (so that the 26 block look-up table remains generalized). From there you just perform inequalities against the 26 cubes. If one of the cubes is unoccupied, it is immediately disqualified from the running. It will also be disqualified for failing any of the inequality tests. If all 26 cubes are disqualified, report back no collision, otherwise there was a collision, and you can even return which blocks collided.

Further optimization can be had by tweaking this routine further, such as doing all checks with one axis first before moving on to the next, which lets you sometimes avoid doing all the dot products. Or you could sort the order of checks by how much each block overlaps the center space so as to statistically eliminate blocks as fast as possible (more complicated but only has to be done once). I guess if even that was too slow, you could further speed things up by sacrificing resolution, subdivide the center cube region into 2*2*2 or 3*3*3 and precalculate which blocks collide in each sector. Of course if you are doing 3*3*3, you need to be avoiding at least 27 collision checks to break even (though if it's just 27 it's inconsequential).

Matrix-vector multiplications still require 9 floating-point multiplications and 12 additions, which I don't think we can get around aside from hardware acceleration like SSE (don't know if it is possible or justified in Java).

----------------------------------
Collision testing happens once per tick. If a ship is moving faster than 1m/tick (a little more than twice as fast as a minecart) it is possible for a small object to pass straight through a 1 block thick wall undisturbed. This can be avoided by adding an additional collision box to cover the distance between itself and its prior position when the relative motion between the two objects is sufficiently fast. This is more expensive, so it would likely be reserved for entities, where the problem is most pronounced.

--------------------------------
Early Warning
--------------------------------
Most of the time, though, there will be no terrain collision checks whatsoever, as the higher level collision checks will cull them all out. Because of that, it become possible to run more than one set of checks in a single tick. This becomes useful for two things. First, you could have an alert which could warn you not only of immanent collision, but also how long until the crash and where along the terrain and ship it will happen. You could then adjust course to avoid it, or let an autopilot work around it.

The other thing, which is potentially even more interesting, is to precalculate what will happen in the event of a crash. When you can simulate how a ship is going to crash into the side of a mountain, for instance, you can also calculate the kind of destruction it is going to do over time. Since it's figured this out, probably several seconds ahead of time, you have a relative eternity to get it all figured out; spawn a designated thread, calculate the damage to the ship and terrain from the impact over time, calculate explosions, and even load the affected render chunks into VBOs and make a timeline of all the changes to be loaded each tick. When the time comes for the actual event, everything has already been planned out to the last detail and can be updated instantly, including the redrawing part, which likewise wouldn't suffer from lag regardless of your distance to the impact site.

You could extend the prediction system to really anything that updates the world: shadows cast on the ground by ships, which requires updating chunks, really big explosions which have a really fancy fluid-based explosion footprint, or transferring to another region which hasn't been loaded yet. All it takes is some way of knowing an event will happen before it does or some other way of hiding the lag, and you can do all sorts of cool stuff.


==================
So that's all the fun theory and stuff. Implementation will divide collision into 5 different tiers, each more accurate than (and entirely encompassed by) the one preceding:

5: Axis Aligned bounding box encompassing the entire ship.
4: Oriented bounding box, which is axis aligned to the the ship's frame of reference. The outer corners of 4 define the dimensions of 5.
3: Each block in the world and the ship is treated physically as spheres. Intersection is simply distance from one to the other.
2: Each block is treated as cubes.
1: Each block uses whatever collision model is specified for that block.

This basically covers what I mentioned earlier. Ship-World uses 5->2, Ship-Ship uses 5->4->2, Entity-World uses 1, Entity-Ship uses 5->4->3->1, Entity-Entity is unmodified, and World-World is just silly. In every case, should a collision fail one of the higher tests, there is no reason to attempt the lower tests. In the case of Entity-Ship, should an entity collide once with the ship, it will continue to move along with the ship until it fails 4 (or maybe slightly outside 4). This would allow you to fly around with a ship without getting thrown off, kind of like the Zeppelin mod.

==================

Like I said before, I'm focusing on Ship-Entity collision for right now so I can keep this project moving along. World-Ship and Ship-Ship will come along after pocket dimensions. And even then, initially it's just going to be type 5 or maybe 5->4 checks for the time being. Need to make up lost time if we are ever going to get to space.

fr0stbyte124 wrote:

*snip, for the love of god*

Its good to know everything is going normally even though you lost some work earlier.

Edit: oh.... yeah now that I look back on it I should REALLY stop qouteing huge qoutes....

Anyway, im also looking into trailer music like you suggested earlier.

Gonna take a few-days break from Copernicus to help out our new friends at MineUp! and Gravity Craft with that occlusion culling technique I mentioned earlier.

Aside from not putting in all the hours I need to be, ships are coming along well. Actually it's going so well I am beginning to suspect something is horribly wrong.
Working on pocket worlds now. Or will be, when I come back to it.

fr0stbyte124 wrote:

Gonna take a few-days break from Copernicus to help out our new friends at MineUp! and Gravity Craft with that occlusion culling technique I mentioned earlier.

Aside from not putting in all the hours I need to be, ships are coming along well. Actually it's going so well I am beginning to suspect something is horribly wrong.
Working on pocket worlds now. Or will be, when I come back to it.

Certainly know the feeling. Keep up the good work!

Finally figured out a decent line-of-sight algorithm for the Occlusion Culling technique. It makes more passes through the chunk than I wanted, but the individual checks are cheap and the whole thing can be aggressively inlined. I expect the algorithm can be taken further, and certainly made to be more stringent, but this will probably be good enough for the time being.

I'm aiming for a release of just the Occlusion Culling for this weekend as a standalone mod. If it proves to be stable I'll port it over to MineUp, and then it'll be back to ship development.
Full explanation of the Occlusion Culling algorithm coming this weekend.

WOO HOO! gotta love that occlusion culling! so its will up the fps?

Significantly.

fr0stbyte124 wrote:

Finally figured out a decent line-of-sight algorithm for the Occlusion Culling technique. It makes more passes through the chunk than I wanted, but the individual checks are cheap and the whole thing can be aggressively inlined. I expect the algorithm can be taken further, and certainly made to be more stringent, but this will probably be good enough for the time being.

I'm aiming for a release of just the Occlusion Culling for this weekend as a standalone mod. If it proves to be stable I'll port it over to MineUp, and then it'll be back to ship development.
Full explanation of the Occlusion Culling algorithm coming this weekend.

Did you port it over?

MCP isn't ready for 1.0 yet.

fr0stbyte124 wrote:

MCP isn't ready for 1.0 yet.

I meant to Mineup.

There's still some bugs, but I won't have much time to work on it, or general development, until after Thanksgiving.

It's been a while since my last post. A big part of that is me getting distracted from development. The other part is that due to some mistakes in my initial logic, occlusion culling wasn't working like I thought it would. I think I've got it figured out now, so we'll see what happens next. For now I'll just talk about it some.

Occlusion culling is the removal of geometry which cannot be seen from the camera's point of view. Minecraft's "advanced opengl" feature does this by comparing every chunk against every quad primitive. While it succeeds in reducing geometry, most of the performance boost is lost to the overhead of performing the culling in the first place. What we need is a compromise. Maybe something not as discriminating but much faster. That's the goal of this new occlusion culling method.

The strategy is simple, rather than figuring out which chunks are visible from a specific point, figure out the visibility from every possible point. Obviously this is impossible so we'll generalize the problem to cube faces. If a chunk cannot be seen through the 1-3 chunks in front of it, then it can be safely culled. If visibility between two faces of a chunk are precalculated, then this evaluation is incredibly inexpensive. Additionally, for separating the surface and below-ground chunks, this method would perform comparably to the vanilla occlusion culling.

I don't really know how best to explain it, so I'm going to start off with my internal notes. It's probably not going to make sense:

There are 15 pairs of faces on a cube, so 15 bits are allocated to describe the connectivity between faces:
111112222333445
234563456456566

Each 16^3 chunk then has two 16-bit shorts associated with it: paths and source. Paths is a map of all the face combinations which light can pass between, 1 where unobstructed and 0 where obstructed. Source will track which faces rays pass through, initialized to 0.

Face.opposite: using dice rules, opposites are 1-6, 2-5, 3-4
Face.key: a constant specific to a particular face showing which slots that face is present on. For instance Face2.key = 100001111000000 going off the table above.
List: a ring buffer of sufficient size (size requirement deterministic, based on draw distance). Holds chunks. Initially only holds chunk containing the camera.
getRule(face) returns a map of which face pathways are visible from the current vantage point. Rather complicated

Evaluation:

Code:

Chunk.Flag(Face){
if (Chunk.source == 0)
   List.append(Chunk);
Chunk.source = Chunk.source | (Face.opposite).key;  //your face 2 is the next chunk's face 5
}

**This is saying that in the flagging process (below), the flagged chunk will be appended to the list if and only if it has not been encountered yet. This keeps duplicates from appearing while maintaining order invariance. Either way, the source map is updated to reflect the new ray passing through.**

main loop:

Code:

while (List.size > 0){
   Chunk = List.next;
   if(Chunk.empty == false) //empty if entirely air
      Chunk.visible = true; //chunk will be rendered if and only if visible is set to true.

   //for real version, this will be unrolled
   for face = 1 to 6
   {
      if(chunk.source & chunk.paths & chunk.getRule(face))
      {
        (chunk.neighbor(face)).flag(face);
      }
   }
   
   List.remove(chunk);
}

**That's it. For each chunk being evaluated, you check which sides have light traveling through them against which side combinations are visible from the viewpoint and which side combinations are obstructed. If it is possible for light to pass through, flag the respective neighboring chunk.**

This method of flagging works only if all contributing chunks are evaluated before the flagged chunk. Because expansion is exclusively outward, I do not think this will be an issue, but I'm not sure how to actually prove it. If it is a problem there will have to be separate lists for ever layer, to be evaluated in turn.

chunk.getRule(face) is quite complicated, due to heavy optimization. It utilizes a lot of bitwise operations and magic numbers. Essentially, for validating face A to one of the other five face Bs, there is one A-specific rule and one B-specific rule relating to the relative position of the camera residing chunk. There are 9 comparisons in total and each face A uses 6 of them. So, to save cyles, the 9 comparisons are overlayed and mapped into 30 bits of a 32-bit workspace (1 bit per face B so 5 bits per face A or 30 bits total). Then you hard-code six 32-element (2^5) arrays of 16-bit shorts as lookup tables. These tables contain the correct masks for that particular face A. When you are ready to use them, shift bits off the 32-bit workspace five at a time to use as indexes.


Well this is getting too abstract. I'll have to think about another way to illustrate it. Anyway, moving on for now.


Occlusion Testing:

This actually runs first, whenever a chunk is redrawn. The occlusion results are stored to chunk.paths.
I've gone through a number of different algorithms trying to strike a balance between speed and accuracy. The best method I've found so far is a sort of cellular expansion. You start in an empty cell against one of the chunk faces, then move once block outwards towards the opposite side. If that cell is empty and untagged, tag it and add it to a stack. Whether it's tagged or not, if that cell is empty, tag the four perpendicular cells. What you end up with is a sort of 3 dimensional T shape, assuming there were no obstructions. Then pull the next tagged cell off the stack and repeat. If you get to one of the other sides, mark it in chunk.paths. Keep going until you run out of cells or hit all 5 faces. Then repeat for the other faces.

The reason for doing this is that it gives you something akin to line-of-sight but with low overhead. It expands at 45 degrees to the normal, which should finish faster. The perpendicular faces will take care of the line-of-sight angles which are too shallow for the first search. Using a stack produces a depth-first behavior, which has a chance of completing earlier for mostly empty chunks. If a chunk is completely empty this step can be skipped entirely.

Evaluation is really fast; fast enough you could run it every frame. But you only have to run it when you move to another chunk. Even then it can be further optimized by only partially updating the grid along the modified axes. It also needs to be run whenever a chunk is redrawn, which is unfortunately all the time, but this part can, too, be optimized by only modifying the affected chunks behind it, and only if the occlusion profile was altered(almost never).

I'm going to do some more work elaborating on this post. It's important that it makes sense, since this will likely be used by other people.

Nice work. Is this your first stand alone mod to be released, or have you made others?

As far as public releases go, this will be my first.

*edit*
Did some number crunching and got the magic numbers.
Using the coordinate system NSEW + UD where
N = -Z
S = +Z
E = +X
W = -X
U = +Y
D = -Y

Connection Table:
_111112222333445
_234563456456566
----------------
_NNNNNSSSSEEEWWU
_SEWUDEWUDWUDUDD

Code:

Workspace

 00 NNNNN SSSSS EEEEE WWWWW UUUUU DDDDD outgoing
 --------------------------------------
 00 SEWUD NEWUD NSWUD NSEUD NSEWD NSEWU incoming
 00 11111 11111 11111 11111 11111 11111
 3FFFFFFF

dz = current chunk z - camera chunk Z

dZ>0
T00 00000 11111 11111 11111 11111 11111
F00 11111 01111 01111 01111 01111 01111
1FFFFFF
3EF7BDEF


dZ<0
T00 11111 00000 11111 11111 11111 11111
F00 01111 11111 10111 10111 10111 10111
3E0FFFFF
1FFBDEF7

dX<0
T00 11111 11111 00000 11111 11111 11111
F00 10111 10111 11111 11011 11011 11011
3FF07FFF
2F7FEF7B


dX>0
T00 11111 11111 11111 00000 11111 11111
F00 11011 11011 11011 11111 11101 11101
3FFF83FF
37BDFFBD


dY<0
T00 11111 11111 11111 11111 00000 11111
F00 11101 11101 11101 11101 11111 11110
3FFFFC1F
3BDEF7FE

dY>0
T00 11111 11111 11111 11111 11111 00000
F00 11110 11110 11110 11110 11110 11111
3FFFFFE0
3DEF7BDF


Xmaj: |dy| <= |dx| && |dz| <= |dx|
F00 11111 11111 11011 11011 11111 11111
3FFDEFFF

ymaj: |dx| <= |dy| && |dz| <= |dy|
F00 11111 11111 11111 11111 11110 11110
3FFFFFDE

zmaj: |dx| <= |dz| && |dy| <= |dz|
F00 01111 01111 11111 11111 11111 11111
1EFFFFFF


North Set
111110000000000
---------------
000000000000000
000010000000000
000100000000000
000110000000000
001000000000000
001010000000000
001100000000000
001110000000000
010000000000000
010010000000000
010100000000000
010110000000000
011000000000000
011010000000000
011100000000000
011110000000000
100000000000000
100010000000000
100100000000000
100110000000000
101000000000000
101010000000000
101100000000000
101110000000000
110000000000000
110010000000000
110100000000000
110110000000000
111000000000000
111010000000000
111100000000000
111110000000000
{0x0,0x400,0x800,0xC00,0x1000,0x1400,0x1800,0x1C00,0x2000,0x2400,0x2800,
0x2C00,0x3000,0x3400,0x3800,0x3C00,0x4000,0x4400,0x4800,0x4C00,0x5000,
0x5400,0x5800,0x5C00,0x6000,0x6400,0x6800,0x6C00,0x7000,0x7400,0x7800,0x7C00}




South Set
100001111000000
---------------
000000000000000
000000001000000
000000010000000
000000011000000
000000100000000
000000101000000
000000110000000
000000111000000
000001000000000
000001001000000
000001010000000
000001011000000
000001100000000
000001101000000
000001110000000
000001111000000
100000000000000
100000001000000
100000010000000
100000011000000
100000100000000
100000101000000
100000110000000
100000111000000
100001000000000
100001001000000
100001010000000
100001011000000
100001100000000
100001101000000
100001110000000
100001111000000
{0x0,0x40,0x80,0xC0,0x100,0x140,0x180,0x1C0,0x200,0x240,
0x280,0x2C0,0x300,0x340,0x380,0x3C0,0x4000,0x4040,0x4080,
0x40C0,0x4100,0x4140,0x4180,0x41C0,0x4200,0x4240,0x4280,0x42C0,
0x4300,0x4340,0x4380,0x43C0}


East Set
010001000111000
---------------
000000000000000
000000000001000
000000000010000
000000000011000
000000000100000
000000000101000
000000000110000
000000000111000
000001000000000
000001000001000
000001000010000
000001000011000
000001000100000
000001000101000
000001000110000
000001000111000
010000000000000
010000000001000
010000000010000
010000000011000
010000000100000
010000000101000
010000000110000
010000000111000
010001000000000
010001000001000
010001000010000
010001000011000
010001000100000
010001000101000
010001000110000
010001000111000
{0x0,0x8,0x10,0x18,0x20,0x28,0x30,0x38,0x200,0x208,0x210,0x218,0x220,
0x228,0x230,0x238,0x2000,0x2008,0x2010,0x2018,0x2020,0x2028,0x2030,
0x2038,0x2200,0x2208,0x2210,0x2218,0x2220,0x2228,0x2230,0x2238}



West Set
001000100100110
---------------
000000000000000
000000000000010
000000000000100
000000000000110
000000000100000
000000000100010
000000000100100
000000000100110
000000100000000
000000100000010
000000100000100
000000100000110
000000100100000
000000100100010
000000100100100
000000100100110
001000000000000
001000000000010
001000000000100
001000000000110
001000000100000
001000000100010
001000000100100
001000000100110
001000100000000
001000100000010
001000100000100
001000100000110
001000100100000
001000100100010
001000100100100
001000100100110
{0x0,0x2,0x4,0x6,0x20,0x22,0x24,0x26,0x100,0x102,0x104,0x106,0x120,
0x122,0x124,0x126,0x1000,0x1002,0x1004,0x1006,0x1020,0x1022,0x1024,
0x1026,0x1100,0x1102,0x1104,0x1106,0x1120,0x1122,0x1124,0x1126}


Up Set
000100010010101
---------------
000000000000000
000000000000001
000000000000100
000000000000101
000000000010000
000000000010001
000000000010100
000000000010101
000000010000000
000000010000001
000000010000100
000000010000101
000000010010000
000000010010001
000000010010100
000000010010101
000100000000000
000100000000001
000100000000100
000100000000101
000100000010000
000100000010001
000100000010100
000100000010101
000100010000000
000100010000001
000100010000100
000100010000101
000100010010000
000100010010001
000100010010100
000100010010101
{0x0,0x1,0x4,0x5,0x10,0x11,0x14,0x15,0x80,0x81,0x84,0x85,0x90,0x91,0x94,
0x95,0x800,0x801,0x804,0x805,0x810,0x811,0x814,0x815,0x880,0x881,0x884,
0x885,0x890,0x891,0x894,0x895}


Down Set
000010001001011
---------------
000000000000000
000000000000001
000000000000010
000000000000011
000000000001000
000000000001001
000000000001010
000000000001011
000000001000000
000000001000001
000000001000010
000000001000011
000000001001000
000000001001001
000000001001010
000000001001011
000010000000000
000010000000001
000010000000010
000010000000011
000010000001000
000010000001001
000010000001010
000010000001011
000010001000000
000010001000001
000010001000010
000010001000011
000010001001000
000010001001001
000010001001010
000010001001011
{0x0,0x1,0x2,0x3,0x8,0x9,0xA,0xB,0x40,0x41,0x42,0x43,0x48,0x49,
0x4A,0x4B,0x400,0x401,0x402,0x403,0x408,0x409,0x40A,0x40B,0x440,
0x441,0x442,0x443,0x448,0x449,0x44A,0x44B}

Workspace is the 32-bit integer mentioned before, which stores the 6 5-bit indexes plus 2 leftover bits. It is initialized to FFFFFFFF and each comparison runs a new bitwise AND filter over the integer. The T line is if the conditional is true, the F is for false. dx, dy, and dz, are the relative location of the current chunk to the chunk housing the camera.

With the 6 sets, the first line of numbers is the binary key. You can see their relation to the list at the top. The 32 lines proceeding that are all the relevant permutations for the lookup table.

Well then we have reason to celebrate!

Is someone smoking, or is that just my braincells? I understood about half of it and from what I can tell the rest only people more familiar with the foundations of games and computers can understand. Good job though Frostbyte, glad to see you back!

Yeah sorry about that, both the confusing and the disappearing.
For the first thing, if this works like I think it will, I'll do something nice to demonstrate it.
For the second I dunno man. I tasted freedom and it's a hard thing to forget :p

Here, I made something.


Fig 1 shows how a ray might enter a chunk from a certain point. It could enter from one to three faces depending on the position of the camera. In this case, three faces are exposed, so a ray might pass through one of the other three chunks (also from one of three faces).

Fig 2 shows the rules of propagation from chunk to chunk for the 2D version. This is what it would look like if every space were empty. Add some obstacles and some of the paths my be obstructed. If a chunk has zero inputs due to obstructions, it will neither be rendered nor propagate the next layer. Actually the system is complicated a bit further by additional rules for not just which faces rays can enter and exit, but which faces are allowed to connect to one another (separate from obstruction), also determined by the camera position.

Rather than doing the logic each time, all the rules are hard coded into a bunch of look-up tables for speed. Specifically the ones I posted the other day.

Fig 3 shows the spread pattern for the occlusion testing routine. It spreads at a 45 degree angle outward, which is optimal for discovering the opposite side. The angles shallower than 45 degrees are covered going the other way from the side faces, achieving 100% cover that way. Pay special attention to the third pass, where South falsely connects to East. We can tell it is a false positive, but had the bottom left obstacle been a different shape, it could have easily been correct. Here, accuracy is secondary to speed. More importantly it will always err on the side of inclusion, which is what we want. On the side, you can see the 6 bits connection table in chunk.paths. The real thing is actually 15 bits since there are 6 sides instead of 4.

So that's basically it, I think. It's a pretty simple strategy by modern game development standards, but the real beauty of it comes from the level of optimization that can be applied. The main loop can be entirely inlined and unrolled and most of the branching removed. Lookup tables replace all logic and all the indexes are made in a single pass.

Watch out everyone; we have a MS Paint wizard in our presence. (Just Kidding)