I couldn’t find a map that showed where all of NYC passenger trains went, so I threw one together. It includes the subway (including the under construction 7 line extension and 2nd ave line), the LIRR, Metro North, PATH, and NJ Transit, though only in a very localized area around New York City.
For comparison, here’s the map with only the existing subway routes:
I’m way behind on blogging about this, but in April 2014 I spent a month making a plugin for Unreal Engine 4 for rendering and interacting with Minecraft-style voxel worlds, along with a simple game called BrickGame to demonstrate it.
I released the source code for the plugin and game on Github. You can of course see how it all works by looking at the code, but there are some tradeoffs I made that deserve some explanation.
Regions and components
In BrickGame, the world is divided into regions, and regions into smaller render and collision components which correspond to UE4 PrimitiveComponents. Regions are generated, and render/collision components created in some radius around the player. The benefit to the different granularity of procedural brick generation and render components is that a region can span the whole Z axis of the world, which allows the procedural generation to only sample 2D noise functions once for each XY, but still divide the world into multiple render components on the Z axis for finer grained visibility culling and dynamic geometry updates.
Collision components are still smaller than the render components, and only created in a much smaller radius around the player than you can see. The small size is to avoid hitches when creating new collision components, and the small radius is to avoid limits in the total number of PhysX box elements. Since I wrote this code, UE4 added support for PhysX triangle mesh collision created at runtime, which would avoid the small radius problem, but would probably negatively affect performance and memory.
The render components create a vertex buffer and an index buffer on the CPU. I don’t do anything to merge adjacent coplanar faces. I do use two tricks to minimize the amount of vertex data:
UVs are derived from the world-space position using a single, planar projection that is 45 degrees off the axes that the face normals are on.
I render faces with different normals in separate draw calls, and use a separate vertex stream with a stride of 0 to provide a single tangent basis for all those faces.
Each vertex consumes 4 bytes, with an 8-bit/component XYZ in the render component’s coordinate system, and an 8-bit ambient occlusion factor. A separate draw call is made for each face direction in a render component that may be visible with the vertex tangent basis bound to a zero-stride vertex stream.
This is tuned to minimize the cost of recreating the vertex and index buffers when a render component is modified or first becomes visible. As the player moves around and modifies bricks, render components must be created and updated. To maintain a smooth framerate, the amount of time it will spend doing so each frame is limited. Reducing the amount of time to create the vertex and index data allows either more components to be updated each frame, or the use of larger components that improve rendering efficiency.
The component sizes are configurable, but the settings I used for BrickGame use large components to minimize per-component CPU and GPU overhead, and enable large view distances. BrickGame uses 32x32x128 regions, 32x32x32 render components, and 16x16x32 collision components.
Global Illumination and Emissive Bricks
BrickGame uses UE4’s Light Propagation Volumes for both Global Illumination and emissive bricks. It’s more expensive than it needs to be for a voxel world, but it was easy and mostly just works. However, I ran into problems with the reflective shadow map rendering time spiking when the sun reached the horizon, and disabling the sun’s directional light disables LPV, which causes the emissive bricks to stop working. My workaround was to add a moon that is always above the horizon, and switch the directional light to it once the sun approaches the horizon. This keeps the directional light at a high enough angle that performance is good, and keeps the emissive bricks working.
Adding a moon required modifying UE4’s starter sky blueprint and material. I added the moon to the material, and added a directional light component to the blueprint that it uses for either the sun or the moon, depending on how high the sun is above the horizon. The moon simply circles high enough above the horizon to avoid the performance problems with the reflective shadow maps.
While I was modifying the sky material, I took the opportunity to add volumetric clouds. The clouds are ray-traced by discrete steps through a parametric noise function. It uses only four samples to determine opacity, and four to determine lighting. This is helped greatly by jittering the samples in cooperation with UE4’s temporal AA. Without the jittering, discrete cloud layers are very obvious, and with the jittering it looks smooth. I think the result is good, but by the time I was done I regretted the distraction from the brick-rendering part of the project.
The BrickGame code will work with completely stock UE4 code, but there are some engine changes necessary for it to work well:
When I initially wrote BrickGame, I decided to compute the ambient occlusion on the CPU, pass it to the material through a vertex attribute, and output it from the material where “baked” ambient occlusion would be output. The goal was to avoid the need to modify the engine (which is so far required if you want to change any shaders). However, I eventually realized that I wanted to make this baked ambient occlusion only affect ambient lighting, not bounced lighting from LPVs, which I implemented with a one line shader change in the engine. Ironically, later versions of UE4 removed support for material-driven ambient occlusion, and so to make my approach work at all requires (small) changes to the engine code. Once it’s possible to add shaders without modifying the engine, it would be nice to come up with a GPU-based ambient occlusion solution.
Given that it eventually became necessary to modify the engine to make the CPU-based ambient occlusion work, and the amount of effort required to make the LPV-based emissive bricks work, it would have been better to just do GPU-based lighting.
The second engine change I made was later in the project, when I was focused on performance. I discovered that doing some large-scale culling of backfaces on the CPU reduces the GPU cost substantially. To do that within the UE4 renderer’s fast path for static meshes required some changes to the engine. Epic has since then added similar functionality to the engine, but it’s not exactly what I need. I’m hoping to eventually submit a pull request to Epic with a change that merges the functionality of our similar static mesh culling changes.
After spending April intensely focused on BrickGame, I have been focused on my programming language and my non-programming projects. I’ve updated BrickGame and my engine changes to new versions of UE4 a few times, but each time it has been incredibly painful to integrate the engine changes. This is mostly an issue with my tools (and likely my lack of understanding of them): I could have done these merges in 15 minutes using P4+Araxis, but using SourceTree/Git to merge simply doesn’t work in ways that I haven’t yet figured out an explanation for. To summarize, I have a fork of Epic’s UE4 Github repository, and a branch within that fork which contains my changes on top of version N of UE4. When I try to UE4 merge version N+1 into that branch:
Git reports merge conflicts in thousands of files I’ve never touched
Using SourceTree to manually “accept theirs” on the conflicts doesn’t work if any of the conflicts are new files from Epic’s repo (yes, that’s apparently a conflict). So I have to manually accept thousands of files in small chunks
Hunks being merged from Epic’s repo that are simple deletions aren’t merged (e.g. deleting a file, or deleting some lines of code without any nearby added lines)
This should be a very simple merge, so there has GOT to be something I’m doing wrong. If anybody has any ideas, please let me know.
I recently changed my comment syntax to allow multi-line comments through indentation, which you can see an example of in the below code. If a line comment is followed by indented lines, then the comment continues until the indentation level returns to the initial level.
This approach supports nesting, doesn’t require an explicit terminal symbol, and is also useful for string literal parsing.
There were two hard parts to implement it:
I previously translated leading tabs into indent/outdent tokens after the lexer turned the input string into tokens. Since comments and string literals are parsed by the lexer, I had to move that translation to happen before lexing. However, I cannot strip white-space until after lexing, so these new indentation-aware components of the lexer needed to explicitly handle superfluous white-space. The indentation-aware components of the parser don’t need to do so, since it occurs after white-space is stripped.
It was tricky to make syntax highlighting in Sublime Text handle the new syntax. The problem is that it just uses a set of regexes to classify subsequences of the buffer. However, it does support nested regexes, so I ended up writing code to generate the syntax highlighting definition file, and use that to nest the indentation-dependent classifications within an explicitly enumerated regex for each indentation level.