Large voxel terrains may contain millions of polygons. Rendering such terrains at a uniform scale is both inefficient and can lead to aliasing of distant objects. As a result, many game engines choose to implement some form of level of detail based rendering, so that distant terrain is rendered with less geometry.
In this post, I’ll talk about a simple technique based on vertex clustering with some optimizations to improve seam handling. The specific ideas in this article are applied to Minecraft-like blocky terrain using the same clustering/sorting scheme as POP buffers.
M. Limper, Y. Jung, J. Behr, M. Alexa: “The POP Buffer: Rapid Progressive Clustering by Geometry Quantization“, Computer Graphics Forum (Proceedings of Pacific Graphics 2013)
Review of POP buffers
Progressively Ordered Primitive (POP) buffers are a special case of vertex clustering, where for each level of detail we round the vertices down to the previous power of two. The cool thing about them is that unlike other level of detail methods, they are implicit, which means that we don’t have to store multiple meshes for each level detail on the GPU.
When any two vertices of a cell are rounded to the same point (in other words, an edge collapse), then we delete that cell from that level of detail. This can be illustrated in the following diagram:
Suppose that each vertex 
This determines a filtration on the vertices,
Which extends to triangles 
And so it follows that,
Each of the sets 
Using this property, we can encode the different levels of detail by sorting the primitives of the mesh from coarse-to-fine and storing a table of offsets:
To render the mesh at any level of detail we can adjust the vertex count, and round the vertices in the shader.
Building POP buffers
To construct the POP buffer, we need to sort the quads and count how many quads are in each LOD. This is an ideal place to use counting sort, which we can do in-place in O(n) time, illustrated in the following psuedo-code:
// Assume MAX_LOD is the total number of levels of detail
// quadLOD(...) computes the level of detail for a quad
function sortByLOD (quads) {
const buckets = (new Array(MAX_LOD)).fill(0)
// count number of quads in each LOD
for (let i = 0; i < quads.length; ++i) {
buckets[quadLOD(quads[i])] += 1
}
// compute prefix sum
let t = 0;
for (let i = 0; i < MAX_LOD; ++i) {
const b = buckets[i]
buckets[i] = t
t += b
}
// partition quads across each LOD
for (let i = quads.length - 1; i >= 0; --i) {
while (true) {
const q = quads[i]
const lod = quadLOD(q)
const ptr = buckets[lod]
if (i < ptr) {
break;
}
quads[i] = quads[ptr]
quads[ptr] = q
buckets[lod] += 1
}
}
// buckets now contains the prefixes for each LOD
return buckets
}
The quadLOD() helper function returns the coarsest level of detail where a quad is non-degenerate. If each quad is an integer unit square (i.e. not the output from a greedy mesh), then we can take the smallest corner and compute the quad LOD in constant time using a call to count-trailing zeroes. For general quads, the situation is a bit more involved.
LOD computation
For a general axis-aligned quad, we can compute the level of detail by taking the minimum level of detail along each axis. So it then suffices to consider the case of one interval, where the level of detail can be computed by brute force using the following algorithm:
function intervalLOD (lo, hi) {
for (let i = 0; i <= 32; ++i) {
if ((lo >> i) === (hi >> i)) {
return i
}
}
}
We can simplify this if our platform supports a fast count-leading-zeroes operation:
function intervalLOD (lo, hi) {
return countLeadingZeroes(lo ^ hi)
}
Squashed faces
The last thing to consider is that when we are collapsing faces we can end up with over drawing due to rounding multiple faces to the same level. We can remove these squashed faces by doing one final pass over the face array and moving these squashed faces up to the next level of detail. This step is not required but can improve performance if the rendering is fragment processing limited.
Geomorphing, seams and stable rounding
In a voxel engine we need to handle level of detail transitions between adjacent chunks. Transitions occur when we switch from one level of detail to another abruptly, giving a discontinuity. These can edges be hidden using skirts or transition seams at the expense of greater implementation complexity or increased drawing overhead.
In POP buffers, we can avoid the discontinuity by making the level of detail transition continuous, similar to 2D terrain techniques like ClipMaps or CLOD. Observe that we can interpolate between two levels of detail using vertex morphing,
In the original POP buffer paper, they proposed a simple logarithmic model for selecting the LOD parameter as a function of the vertex coordinate 
Where 
The authors of the original POP buffer paper proposed modifying their algorithm to place vertices along the boundary at the lowest level of detail. This removes any cracks in the geometry, but increases LOD generation time and the size of the geometry.
Instead we can solve this problem using a stable version of LOD rounding. Let 
In practice 2-3 iterations is usually sufficient to get a stable solution for most vertices. This iteration can be implemented in a vertex shader and unrolled, giving a fast seamless level of detail selection.
As an aside, this construction seems fairly generic. The moral of the story is really that if we have geomorphing, then we don’t need to implement seams or skirts to get crack-free LOD.
World space texture coordinates
Finally, the last issue we need to think about are texture coordinates. We can reuse the same texturing idea from greedy meshing. For more info see the previous post.
algorithm in the obvious way. While it is not efficient for large problem sizes, it performs pretty well up to few hundred points.
boxes was generated, and then sent to each library to compute a checksum of the set of pairs of intersections. Because different libraries expect their inputs in different formats, as a preprocessing step the boxes are converted into whatever data type is expected by the library. This conversion step is not counted towards the total running time. Note that the preparation phase does not include any time required to build associated data structures like search trees or grids; these timings are counted toward the total run time.
, in order to avoid measuring the reporting time for each method.
while constraining the boxes to remain within the unit hypercube, ![[0,1]^d](https://s0.wp.com/latex.php?latex=%5B0%2C1%5D%5Ed&bg=ffffff&fg=1a1a1a&s=0&c=20201002)
. A typical sample from this distribution looks like this,
, but due to the constants involved is still far too slow. As it took too long and there were 2 other representatives of the r-tree data structure in the benchmark, I decided to drop it from larger tests. Moving on to 10k boxes,
growth, however because the constants involved are so large they were also dropped from the large problem size.
time of box-intersect. An explanation for this phenomenon would be that box-intersect enjoys better cache locality (scaling linearly with block size), while hashing causes 
indirect main memory accesses for each box. If the size of a cache line is 
, then the cross over point should occur when 
in 2D. This is illustrated in the following chart which carries out the experiment to 250k boxes,
grid at each level of the tree along the quantiles. In the case of a uniform distribution of boxes, this reduces to uniform grid giving a query time of 
, which for finite 
gives means that rbush will find all intersections in 
time. As a result, we can expect that once 
, rbush-bulk should eventually surpass box-intersect in performance (though this did not occur in my benchmarks). This also suggests another way to interpret the OMT heuristic: it is basically a hedged version of the uniform grid. While not quite as fast in the uniform case, it is more adaptive to sparse data.
penalty, while adding robustness against sparse data.
performance, as predicted.
-axis by a factor of 
or 
, then it would have been possible to increase their running times to some arbitrarily large value. In this benchmark, rbush also grows though by a much slower 
. Continuing out to 100k boxes, eventually rbush also fails,
performance no matter what type of input you throw at it. It is even faster than grids for uniform distributions at small problem sizes(<10k) due to superior cache performance.![[x_{min}, x_{max}] \times [y_{min}, y_{max}]](https://s0.wp.com/latex.php?latex=%5Bx_%7Bmin%7D%2C+x_%7Bmax%7D%5D+%5Ctimes+%5By_%7Bmin%7D%2C+y_%7Bmax%7D%5D&bg=ffffff&fg=1a1a1a&s=0&c=20201002)
).
![[x_0-r_0, x_0+r_0], [x_1-r_1, x_1+r_1]](https://s0.wp.com/latex.php?latex=%5Bx_0-r_0%2C+x_0%2Br_0%5D%2C+%5Bx_1-r_1%2C+x_1%2Br_1%5D&bg=ffffff&fg=1a1a1a&s=0&c=20201002)
,![[x_0-r_0, x_0+r_0] \cap [x_1-r_1, x_1+r_1] \neq \emptyset \Longleftrightarrow |x_0 - x_1| \leq r_0 + r_1](https://s0.wp.com/latex.php?latex=%5Bx_0-r_0%2C+x_0%2Br_0%5D+%5Ccap+%5Bx_1-r_1%2C+x_1%2Br_1%5D+%5Cneq+%5Cemptyset+%5CLongleftrightarrow+%7Cx_0+-+x_1%7C+%5Cleq+r_0+%2B+r_1&bg=ffffff&fg=1a1a1a&s=0&c=20201002)
![[l_0, h_0], [l_1, h_1]](https://s0.wp.com/latex.php?latex=%5Bl_0%2C+h_0%5D%2C+%5Bl_1%2C+h_1%5D&bg=ffffff&fg=1a1a1a&s=0&c=20201002)
,![[l_0, h_0] \cap [l_1, h_1] \neq \emptyset \Longleftrightarrow l_0 \leq h_1 \wedge l_1 \leq h_0](https://s0.wp.com/latex.php?latex=%5Bl_0%2C+h_0%5D+%5Ccap+%5Bl_1%2C+h_1%5D+%5Cneq+%5Cemptyset+%5CLongleftrightarrow+l_0+%5Cleq+h_1+%5Cwedge+l_1+%5Cleq+h_0&bg=ffffff&fg=1a1a1a&s=0&c=20201002)
, then the amortized cost of looping over the events is 
. Therefore, the total running time of this algorithm is in 
.
, then insert each of the boxes into the cells they overlap. Boxes which share a common grid cell are tested for overlaps:
cells and that each cell contains at most 
(using a grid or hash table), or 
for sorted lists, which for small 
is effectively an optimal 
time, where 
.
time, then it uses at least 
bits.
time per query. Therefore, the worst case time complexity of bvhIntersect is slower than,
.
time using 
and gave a construction which effectively matches this bound,
, and for 3D 
.
. Situations where the complexity degenerates to 
tend to be rare, and in practice applications can be designed to avoid them. Moreover, because R-trees have small space overhead and support fast updates, they are relatively cheap to maintain as an index. This has lead to them being used in many GIS applications, where the problem sizes make conserving memory the highest priority.
barrier in the worst case (with the exception of 1D interval sweeping and a brief digression into Shamos & Hoey’s algorithm). To the best of my knowledge, all efficient approaches to this problem make some essential use of 
time using 
space (these results can be improved somewhat using 
time.
. This approach is described in the following paper by Zomorodian and Edelsbrunner,
is a n-by-d matrix
is a m-by-d matrix
is equivalent to the 
linear inequalities in 
time, which for fixed dimension is just 
. The dependence on 
using a more sophisticated data structure,
. If this volume is 
, then the shapes collide. One way to compute this volume is to rewrite it as an integral. Let 
denote the 
in some basis, (for example, as Fourier waves), then we can use that to approximate this volume. If we do this expansion carefully, then with enough work we can show that the resulting approximation preserves something of the original geometry. For more details, here is a paper I wrote:
(for comparison based algorithms) by reduction to the 
time using a 
, this is a big improvement over naive brute force. This technique can also be adapted to compute intersections in sets of general convex polygons by decomposing them into segments, and then building a secondary point location data structure to handle the case where a polygon is completely contained in another.
called a 
= frequency of updates
= the size of the game state
bits/(second * player) or 
total bits. Clients have a downstream bandwidth of 
. Assuming a shared environment where every player sees the same state, then 
. This leaves us with two independent parameters, 
. Increasing 
.
possible US phone numbers, and so any such number can be encoded in 
bits, or a little under 4 bytes. In general, given more type information it is possible to achieve smaller encodings.
. 
be the dimension of space and let 
denote a 
dimensional real vector space. In the 
into a spatial component 
and a 
. Now l
be the maximum velocity any object can travel (aka the 
. In this convention, causal vectors 
is a 
we say that 
causally precedes 
(written 
) if 
is future-directed causal or zero.
is space-time consistent if for all 
, 
.
determines a pair of closed regular sets called its causal future and causal past, respectively:
. Conversely, events in 
. 
is the light cone of 
,
.
,
.
which is the point in space-time at which it most recently received an input from its remote controller. Let 
be the set of all these events. We call the causal future 
the 
. Consequently, these events can be predicted by dead-reckoning. On the other hand, events inside 
-dimensional collection of world lines in space-time into a 
,
.
.
determines a Cauchy surface is answered by the following theorem:
if and only if the subgradient of 
is bounded by 
.
intersects the surface only once. To show that the curve crosses at least once, recall proposition 1 implies that 
and 
, and that the curve begins in the causal past of 
be a point of intersection between the curve and the surface. Then the entire future of the curve is contained in the open cone 
. Similarly, because 
, no other points on 
. Ditto for all the points in the causal past, and so any intersection must be unique. To show necessity, take any Cauchy surface 
as shown above. Suppose that there is some point 
and unit vector 
where 
. Without loss of generality, assume 
. Then there exists some 
where 
. Construct the time-like curve 
. By the intermediate value theorem, 
be the time of the oldest-most recent input from a remote player. Then define a constant Cauchy surface,
.
be the time that the most recent local input was processed. Then the optimistic Cauchy surface is,
.
, is the time that an event is rendered for a local user.
varying as function of local time. We want to compute the time dilation experienced by an object with a coordinate time parameterized world line, 
. In this situation, define the mapping 
, that relates local time to the particle’s coordinate time,
.
.
, then objects will stop or possibly move backwards in time. This condition produces jitter, and it is important that we avoid it in all circumstances. Fortunately, it is not hard to derive a set of sufficient conditions to ensure that this is the case for all time-like paths:
and 
, then for any time-like particle the time dilation is strictly positive.
, then for all 
, 
.
, then for all 
, 
where 
where,
.
the horizon. If the last locally processed input was at 
, then the minimum input delay of the local perception filter is,
.
is a function of the last acknowledged position and ping of all remote players. If 
, then we can respond to local inputs immediately. This leads to the following theorem which gives necessary conditions for a local input to be processed immediately:
and their last acknowledged position is 
, then in order for a local perception filter to process a local input without lag, we must require that:
distance from each other, then local perception filters completely eliminate input lag.
.
is the time of the local player. Some other options would be to use a smoother surface or some offset of the true horizon. At any rate, this surface seems to give acceptable results but I fully expect that it could be improved drastically with more careful consideration.
be the edges of a connected graph on 
we assign a weight 
which is the latency of the edge in seconds. In the network we assume that players only communicate with those whom are adjacent in 
. The bandwidth required by active replication over a peer-to-peer network is 
per client, since each client must broadcast to every other client, or 
total.
. The total bandwidth consumed is 
per client and 
for the server.
, then we could conclude that peer-to-peer replication is overall more efficient. However, in practice this is not quite true for several reasons. First, in passive replication it is not necessary to replicate the entire state each tick, which results in a lower total bandwidth cost. And second, it is possible for clients to eagerly process inputs locally thus lowering the perceived latency. When applied correctly, these optimizations combined with the fact that it is easier to secure a client-server network against cheating means that it is in practice a preferred option to peer-to-peer networking.
0 FPS 
