Fr0stbyte's Development Log

Whoops, made a few errors on the logic lookup charts. On the plus side the rules make a lot more sense now that they are consistent. For instance, if the camera is to the right of a chunk's rightmost face, it is impossible for that face to be an output (because the camera ray passing through would be going the wrong way), whereas if the camera is to the left of the rightmost face, it is impossible for that face to be an input. It should also be mentioned that the left of the rightmost face is not the same as being to the left of the leftmost face (the difference between dx<=0 and dx<0) because if the camera is in-between the two, then both faces can be outputs and neither can be an input. That's why we have a separate mask for !(X<0) and (X>0). Just thought I would clarify that. The table's been updated.

In any case, I'm running more tests and messing around with the data structure (I use the term liberally as it is just an array). Rather than storing block information of the chunk occlusion testing to a 3-dimensional matrix, the whole thing is stored within a 4096 bin single-dimension array. The reason for this is that java is a little inefficient in handling multi-dimensional arrays, which makes sense if you know anything about Java. Multi-dimension arrays are nice to work with and all you have to do is define the dimensions and it will work, compared to C++ where they are a nightmare if you are avoiding vector arrays. But in order to make them easy to use, Java does extra behind the scenes processing to parse the data, which while imperceptible by itself, adds up quickly over large sets of data. 6 passes over 4096 bins is not really a major deal, but since the occlusion testing is an entirely new process every cycle spent evaluating counts against our quota.


Can't say for sure when this will all be done, but development is moving along smoothly and more importantly the theory behind it is rock-solid now that my logic tables are corrected, so I'm not expecting any serious obstacles with implementation. As far as implementation, this will require two hooks in the base class RenderGlobal. Unfortunately, that alone is going to conflict with lots of other engine mods. To resolve this, I'll be releasing the whole thing as open source so that other modders can incorporate it into their own code.

*edit*
Oh yeah, I did the proof to verify layer segregation, though probably no one cares. I still think it's cool as a computer scientist. Basically, you first prove that with no obstructions, every node in layer N will be explored before any node in layer N+1 regardless of the traversal order. Then you prove that while obstacles can affect the ordering of nodes within a layer, that cannot affect the relative order of nodes between layers. Because of this, it is safe to store the search space within a single ring buffer, which is nice and elegant from a graph search standpoint. I also did the math, and with far rendering being (I think) ±16 chunks from the center chunk the ring buffer needs to be 1632 elements large, peaking at layer 26/49 assuming full freedom along the Y axis (utilizing cubic chunks) or a mere 464 peaking at layer 20/40 with the standard 8-high chunk world.

Well Frost, I'm impressed with the way the engine is looking so far. Your logic seems sound and makes sense but what I find really interesting is, as you stated, the beauty of it is the sheer simplicity of the logic. I also think using the logic tables makes a lot of sense. I'm quite eager to see this bad boy in operation.

First draft of the optimized chunk occlusion test is done, and I have a benchmark. On average a full occlusion evaluation takes 0.020 milliseconds.

Just gonna let that soak in for a moment...

We'll put it this way: as this process runs at most one time per frame (chunk rendering is capped at once per frame) if you normally had, for instance, a framerate of 100 fps, this process will drop you down to 99.8 fps. My processor is quite powerful, but that's a pretty good indication of what one can expect.
The other part, culling, is even faster and runs less frequently. I am quite pleased with these results. I knew it would be fast but this is beyond my expectations.

0.02 MS? Wow. That's.... well... fast. Like really fast, like it takes longer for the letters I'm typing to appear on my screen than that. That's pretty awesome that you've gotten it down that low, a .2 FPS drop isn't going to be noticeable. I think we've got a good chance of making this thing awesome provided everything comes together and the occlusion stuff isn't effected by any content (which I couldn't see why it would be).

Excellent work there my friend.

The culling routine is also done now, or I think it is anyway. If any of my tables are still wrong, this is going to be a pain to debug.
All that's left now is hooking it into the 1.0.0 code and it will be ready for beta testing.

fr0stbyte124 wrote:

The culling routine is also done now, or I think it is anyway. If any of my tables are still wrong, this is going to be a pain to debug.
All that's left now is hooking it into the 1.0.0 code and it will be ready for beta testing.

My reaction pictures are ready for the monumental event.

tonyri..... your pictures make me cry a little on the inside

Excellent.

The hooks appear to work, doing more tests to make sure. This isn't really the ideal unit testing platform.

I've got this nagging concern, though. In early flight tests with Copernicus I wanted to see how far a small ship could travel from its original chunks before getting overwritten. Turns out it could go many kilometers before any displaylists got overwritten (displaylists are the precompiled render instructions which allow the game to redraw chunks so quickly). At the time I thought that meant there was a massive number of pre-allocated displaylists available, but that's not the case. Every 33rd or so worldrenderer along a particular axis shares the same displaylist. That's just enough distance so that no two visible chunks will share the same list. Going off of that, the test ship should have vanished immediately after the original ship was out of sight. But that's not the case.

As far as I can tell, a displaylist will get overwritten if and only if they pass through the function WorldRenderer.updateRenderer(). That is currently where my occlusion test hook is located. But if there are empty worldRenderers not passing through, which looks to be the case, that is an unreliable place for the hook. I need to discover the secret of these differed chunks and make sure it won't be a problem down the road. I'm working on that tonight.

Oh, and if anyone was wondering, I'll be allocating a new set of displaylists for each world/pocket space, so they won't have a problem with conflicts like they do now. I should probably check if there is a limit to how many can be made...

fr0stbyte124 wrote:

The hooks appear to work, doing more tests to make sure. This isn't really the ideal unit testing platform.

I've got this nagging concern, though. In early flight tests with Copernicus I wanted to see how far a small ship could travel from its original chunks before getting overwritten. Turns out it could go many kilometers before any displaylists got overwritten (displaylists are the precompiled render instructions which allow the game to redraw chunks so quickly). At the time I thought that meant there was a massive number of pre-allocated displaylists available, but that's not the case. Every 33rd or so worldrenderer along a particular axis shares the same displaylist. That's just enough distance so that no two visible chunks will share the same list. Going off of that, the test ship should have vanished immediately after the original ship was out of sight. But that's not the case.

As far as I can tell, a displaylist will get overwritten if and only if they pass through the function WorldRenderer.updateRenderer(). That is currently where my occlusion test hook is located. But if there are empty worldRenderers not passing through, which looks to be the case, that is an unreliable place for the hook. I need to discover the secret of these differed chunks and make sure it won't be a problem down the road. I'm working on that tonight.

Oh, and if anyone was wondering, I'll be allocating a new set of displaylists for each world/pocket space, so they won't have a problem with conflicts like they do now. I should probably check if there is a limit to how many can be made...

Sounds... complicated. How long did it take Notch to make this complex system? Months? It sure sounds like it.

Ever get too close to a problem and then fail to see the obvious? Well that's what happened this time.

I was looking so hard for what might be preventing updateRenderer() from being called that I never considered that updateRenderer() might itself be the culprit. Well it turns out that is exactly what is going on. The resident display list of a worldrenderer is only regenerated once the algorithm comes in contact with the first non-air block. If the chunk is entirely air, the display list is never accessed and remains whatever it was before, hence the ship not disappearing. Instead the worldrenderer sets some flags which tell the draw routine not to run that display list.

It was a dumb oversight on my part, but on the plus side, this is actually ideal behavior for my occlusion testing, as the worldrenderer is aware of whether or not the chunk is empty. Saves me having to test for it.

Figured out another cool trick I can do. By re-weighing chunks to account for visibility in addition to proximity as they are selected for rendering, you can prioritize rendering visible chunks over occluded chunks. Not only does this mean the world appears to load faster (on top of more renders per second from decreased rendering burden), but it also eliminates most of the rendering starvation I mentioned in a previous post.

Rendering starvation is when things happen which require the chunk to be redrawn (redstone, fire, vines growing, water/lava spreading) happen so frequently that more distant chunks can't be drawn at all (chunks are prioritized by proximity, which is why things look more laggy the farther away you get). With this change, everything visible up to the draw distance above ground will be handled before anything underground is even considered, and vice versa when you are underground. The result is a noticeably smoother loading time, at least from what you can see.

For a singleplayer client it involves adjusting how chunks are initially chosen to be loaded, and is a little bit more complicated than what's there now, but not much. On a multiplayer server, though, it's even better. Theoretically, you should be able to run the occlusion algorithm on the server and serve up chunk updates to a vanilla client as 16^3 cubes rather than a whole chunk at a time. Essentially this means unmodded clients playing on the modded server will get the same benefit as if they were running the mod themselves.

Another thought I had was predictive analysis, guessing at what direction you are heading and what changes will be considered before you get there for a more seamless experience. In any case, this sort of thing will be introduced after the initial alpha release. Plus I need to get back to work on Copernicus and the ship modding. I never expected occlusion culling to take this long.

Goddamn. This stuff, this is getting into the kind of thing that would revamp the whole game. Might be worthwhile to drop Jeb a line and see if you can get that baseframework-level stuff into vanilla, for the good of all.

Damn dude! Have you considered applying for a job at Mojang? With the amount of stuff you've been doing they would be foolish NOT to hire you!

Fr0stbyte, I actually understood your previous post, which is a first. I'm not too sure about the prediction aspect though; wouldn't it use enough memory making the calculation that it isn't worth having it?

With this occlusion culling scheme, do you think that a "very far" render distance will be viable?

Also, what about rendering in space, where pretty much all chunks are empty, and we need to be able to render ships that are dozen of kilometers apart (so they can see each other)?

Dr. Mackeroth wrote:

Fr0stbyte, I actually understood your previous post, which is a first. I'm not too sure about the prediction aspect though; wouldn't it use enough memory making the calculation that it isn't worth having it?

With this occlusion culling scheme, do you think that a "very far" render distance will be viable?

Also, what about rendering in space, where pretty much all chunks are empty, and we need to be able to render ships that are dozen of kilometers apart (so they can see each other)?

We are using Cubic Chunks aren't we?

In CC, when a chunk is composed of only air, its not there at all. So in theory we could render a entire solar system depending on how we render planets. Especially since Frostbyte could always force the engine to always display all ship World Renderers.

Drawing objects at a distance is not a problem. The only thing that matters is the amount of geometry on screen. Occlusion culling should eliminate a decent chunk of it, but I can't say for sure what this will mean for draw distance just yet. By itself, it won't fix the problem, but I've got some other ideas on the drawing board.

In space, each independent object is a Copernicus entity. The empty space between them is just that: empty. This isn't as difficult as it sounds, as most of the world interfaces don't have to be adjusted beyond the initial Copernicus setup. We will probably be using Cubic Chunks. I need to look at it more closely to make sure it works, but it would give us a lot more flexibility in building planets and other very large structures.

Also I'm in the final stretch of implementing occlusion culling. The individual parts all appear to be working correctly, but there are still some inexplicable oddities where it interfaces with Minecraft. Once I resolve them I can release an alpha.

Not quite what I had in mind, but at least it's fast.

Fr0stbyte; I have faith in you. Once your Alpha is released, I will finally be able to put the render distance on far without the game crashing.

fr0stbyte124 wrote:

Not quite what I had in mind, but at least it's fast.

I don't know what you're talking about. Looks good to me It's very fast. Way better than opti-fine.

On the plus side, I found my stronghold.

fr0stbyte124 wrote:

On the plus side, I found my stronghold.

I was just about to ask why that oddly shaped swastika thing was underground on the left side of the screen. Yea it must be a stronghold.

Well, you should all be very pleased to know that the video doesn't work on my phone. Could someone explain what happened?

I really wish I could.

Dr. Mackeroth wrote:

Well, you should all be very pleased to know that the video doesn't work on my phone. Could someone explain what happened?

The terrain loaded very fast, much faster than with optifine or any let's player's computer. But random chunks would disappear and reappear in no particular order, so it would be like seeing chunk errors in a checkerboard, if you have ever seen chunk errors on multi-player.

P.S. When I say randomly, I mean randomly for me. Frostbyte probably knows why some render and others don't.