EUROGRAPHICS 2020 / U. Assarsson and D.

Panozzo Volume 39 (2020), Number 2

(Guest Editors)

Interactively Modifying Compressed Sparse Voxel Representations

†
V. Careil1,2 , M. Billeter1 , E. Eisemann1
1 Delft University of Technology, The Netherlands
2 Université de Rennes, France

Figure 1: To test and demonstrate our method for editing large sparse voxel geometries, we have implemented an interactive prototype
application with support for interactive editing operations. The left image shows a copy operation in the Epic Citadel scene, voxelized at a
resolution of (128k)3 . The statue inside this building contains about 170k voxels. The middle image shows larger scale edits, copying an entire
building (order of 80M voxels). The right images illustrate tools to add and delete voxels, as well as paint voxel color attributes. The bottom
right image uses the San Miguel model, voxelized at (64k)3 , where we first solidified, then carved a hole in a column.

Abstract
Voxels are a popular choice to encode complex geometry. Their regularity makes updates easy and enables random retrieval of
values. The main limitation lies in the poor scaling with respect to resolution. Sparse voxel DAGs (Directed Acyclic Graphs)
overcome this hurdle and offer high-resolution representations for real-time rendering but only handle static data. We introduce
a novel data structure to enable interactive modifications of such compressed voxel geometry without requiring de- and
recompression. Besides binary data to encode geometry, it also supports compressed attributes (e.g., color). We illustrate the
usefulness of our representation via an interactive large-scale voxel editor (supporting carving, filling, copying, and painting).
CCS Concepts
• Computing methodologies → Volumetric models;

1. Introduction [KSA13, JMG16, KRB∗ 16] to achieve significant compression

rates. Kämpe et al. [KSA13] demonstrate (128k)3 resolutions at
Compressed sparse voxel structures have gained popularity as an
less than 1GB, while still enabling real-time rendering of this
alternative representation for highly-detailed geometry. Voxel-based
compressed form. Originally, such DAG (directed acyclic graph)-
approaches encode the scene as a high-resolution grid, where cells
based structures only encoded solid geometry; however, later works
(“voxels”) hold information to define the scene. While naively
[DKB∗ 16, DSKA18] extend the methods to include compressed
storing such grids is infeasible for large resolutions, hierarchi-
per-voxel attributes, such as color.
cal representations can exploit sparsity [Mea82] and similarity
Until now, sparse voxel DAG structures are pre-built in a separate,
often off-line, construction step, which limits their use to static ele-
† [email protected]; {m.j.billeter;e.eisemann}@tudelft.nl ments. We introduce a solution to dynamically modify sparse voxel

© 2020 The Author(s)

Computer Graphics Forum © 2020 The Eurographics Association and John
Wiley & Sons Ltd. Published by John Wiley & Sons Ltd.
V. Careil, M. Billeter & E. Eisemann / Modifying Compressed Voxel Representations

DAGs in the compressed domain. It enables interactive geometry The original sparse voxel DAGs only encode geometry.
edits, and paves the way to many applications requiring dynamic Dado et al. [DKB∗ 16] and Dolonius et al. [DSKA18] show how
changes to a compressed DAG. Furthermore, our data structure is additional information, such as colors and other attributes (e.g.,
compatible to existing attribute-compression schemes [DSKA18]. normals), can be compressed alongside a sparse voxel DAG. Our
We demonstrate interactive color manipulations as an example. method is compatible with such approaches, and we demonstrate the
Specifically, we make the following contributions: use of colors, employing the compression method of Dolonius et al.
• A method for modifying sparse voxel DAGs in their compressed A sparse voxel DAG can be built efficiently from a sparse voxel
form, i.e., without decompression/recompression; octree [ABD∗ 18,SKOA14]. Many methods for building sparse voxel
• A novel data structure to enable interactivity and ensure little octrees exist, including out-of-core approaches [BLD13]. Neverthe-
impact on compression/rendering/traversal performance; less, while these aim at efficient ground-up builds, we focus on
• A natural recording of changes to enable undo/redo operations efficient online modifications of a sparse voxel DAG structure.
and associated garbage collection to free memory, when needed.

3. Method
2. Related Work
Modifying uncompressed voxel structures is straight-forward (and
Voxels are used in many applications to represent complex geometry. indeed one of its strengths). However, compressed structures, such
The regularity of voxel structures makes them appealing if opting as Voxel DAGs, are largely considered static. The reason is that any
for dynamic modifications, as in editing tools [3DC, SVR], as well node in a DAG may be referenced by multiple parents. Thus, naively
as games [Mc, Ast]. Nevertheless, uncompressed voxel structures changing an existing node potentially affects many parts of the
grow rapidly in size with increasing resolution. scene. To avoid this problem, our method keeps the original structure
Compressing voxel volumes is an option for reducing the mem- intact but attaches additional information to indicate modifications.
ory costs. While several rendering algorithms have been pro- These additions are light-weight as they take place directly in the
posed [BRGIG∗ 14], solutions for fast editing of large volumes compressed domain, while maintaining an efficient traversal (and,
are lacking. Our work focuses on the modification of sparse struc- thus, rendering) performance. Further, this encoding keeps track of
tures that can, e.g., arise when converting solid geometries into very all modifications, which can then be naturally un- and redone.
high-resolution voxel data. To explain our method, we first describe the principle of modify-
Sparse voxel octrees [Mea82] (SVOs) encode sparse volumes ing the geometry in a DAG (Section 3.1) without discussing imple-
efficiently by employing a hierarchy. Meagher [Mea82] encodes mentation details. We then introduce our data structure to achieve
geometry in an octree, where leafs are either filled or empty, while interactive performance (Sec.3.2). Next, we cover several extensions,
inner nodes are either empty or contain at least one pointer to a including the use of attributes, demonstrated with color manipula-
non-empty child node on the next level. By only storing non-empty tions, e.g., for painting applications (Sec.3.3). At all time, geometry
parts of the structure, SVOs deal very well with sparse data (as and color data remain compressed but the DAG is augmented with
their name indicates). SVOs can be directly traversed without de- information in each modification step. A garbage collection is used
compression and efficiently rendered via ray tracing [LK10], which to trim this information, when memory is required (Sec.3.5).
made them suitable for many applications, including indirect il-
lumination [CNS∗ 11], multi-scale editing [SVR] and out-of-core
3.1. Modifying DAG Geometry
rendering [CNLE09, CNSE10, GMI08].
We assume that modifications take place within a bounding volume
Kämpe et al. [KSA13] show that the compression rates of SVOs
(e.g., brush). Independent of the applied operation, we, thus, first
can be increased significantly by also exploiting similarities in the ac-
identify the voxel locations that require changes. To do so, our
tual geometric data. Their method identifies identical subtrees in an
method traverses the DAG structure in a depth-first manner. If a
SVO and removes duplicates by changing all references to point to
node is not affected by the change, we stop the traversal, otherwise,
a single instance of the subtree. This transforms the octree into a di-
we descend into the children. During this traversal, it is possible to
rected acyclic graph (DAG). Using this method, Kämpe et al. encode
descend into nodes that did not exist in the original DAG structure
volumes with resolutions of up to (128k)3 , while remaining compact
and will be added and compressed on the fly. An example that
(e.g., the structures fit fully into GPU memory) and maintaining real-
requires a full descent would be a single voxel that is added at the
time rendering performance. Later work increases compression rates
highest resolution level. If a larger region is filled, an earlier stop
by exploiting additional similarities [JMG16, JMG17], but we base
might be possible when an entire subtree is filled.
our method on the simpler (but still very compact) original sparse
voxel DAGs. Sparse voxel DAGs have found various applications, Once the necessary depth and location for the manipulation is
including shadows [SKOA14], many-view rendering [KBLE19], reached, we create a node representing the newly modified geometry
and time-varying geometry [KRB∗ 16]. In the latter, Kämpe et al. (following Kämpe et al. [KSA13], DAG leafs are 43 = 64 subvol-
use DAGs with multiple roots. Following a different root results in umes encoded in bits of a 64-bit integer). At this point, we need to
a different geometric representations, while identical data is still integrate the new node into the DAG. There are two cases; there
shared. The total compression increases significantly compared to already exists an identical leaf-subvolume node somewhere in the
storing separate DAGs. We use a similar insight to store multiple DAG, which means that we can use the existing version instead, or
states (before and after edits) efficiently. we need to append a new node to the DAG (without invalidating

© 2020 The Author(s)

Computer Graphics Forum © 2020 The Eurographics Association and John Wiley & Sons Ltd.
V. Careil, M. Billeter & E. Eisemann / Modifying Compressed Voxel Representations

Figure 2: Overview of the editing process. (Left) Original voxel data and the corresponding DAG. We wish to fill the region highlighted in red.
(Children are shown in counter-clockwise order, starting top-left.) (Center-left) We traverse the DAG structure and identify the leaf nodes
affected by the modification (highlighted in orange and purple in the voxel data). The purple leaf already exists in the DAG, so we find it and
return a pointer to the existing node. The orange leaf is new, so we append it to the leaf level. (Center-right) We propagate the pointers to the
parent node, and construct it. The DAG does not contain such a node yet, so we create a new one. (Right) We propagate the new pointer to its
parent (the root). Three of the parent’s children are unmodified, and we copy the corresponding values from the old instance. The fourth child
is our modified node. The new node does not exist either, and becomes a new root node that represents the modified volume. The old root is
kept (unless trimmed later) and traversing the old root returns the original voxel data.

existing nodes). In both cases, we obtain a pointer to a node within nodeptr edit( editOp, lvl, center, node )
the DAG that contains the modified geometry. The pointer is then {
passed to the parent. In the special case, where a node ends up empty, if( !editOp.affects_volume_at( center, lvl ) )
we propagate a special (reserved) pointer value to the parent node. return NodeUnchanged;
This instructs the parent to omit the node in its child mask and to if( lvl == DAGDepth-2 )
indicate its absence (no pointer needs to be stored). For each parent, return edit_leaf(editOp, lvl, center, node);
once its children have been processed, we again create a new node childMask = 0; childPtrs[8] = { EmptyNode, ... };
that reflects the changes. Such interior nodes consist of a bit-mask if( node != EmptyNode )
identifying non-empty children (eight bits) and a set of pointers (one childMask = get_child_mask( node );
per non-empty child). As in the previous case, the same two options childPtrs = unpack_child_pointers( node );
exist: the same node already exists, and we use it instead, or we add for( i = 0; i < 8; ++i )
the new node to the DAG. Again, either choice results in a pointer newChild = edit( editOp, lvl+1,
to a node in the DAG with the correctly-modified geometry, which position_of_child( center, lvl, i ),
childPtrs[i] );
is then passed again to the parent.
if( newChild != NodeUnchanged )
The procedure is repeated until reaching the root of the DAG, childPtrs[i] = newChild;
where we create a new root node. It represents the modified DAG, if( newChild != EmptyNode )
including the geometric changes. Please note that the trees attached childMask |= (1<<i); // set bit i to one
to the previous root node reflect the previous version of the DAG, else
childMask &= ∼(1<<i); // clear bit i
which enables un- and redo operations by storing such previous
roots and starting traversals from them. Section 3.5 will show how if( childMask == 0 )
to remove this unnecessary data, if needed. We illustrate the entire return EmptyNode;
editing process in Figure 2. Listing 1 includes pseudo code for the childPtrs = pack_child_pointers( childPtrs );
recursive editing function. The efficiency of our method hinges on p = find_node( lvl, childMask, childPtrs );
two operations: finding a node in the DAG and inserting new nodes. if( p == NodeNotFound )
p = append_node( lvl, childMask, childPtrs );
The next section describes how to achieve these tasks efficiently. return p;
}

3.2. The HashDAG structure

Listing 1: Recursive editing function. The editOp defines the
Our data structure, the HashDAG, uses two main components: hash- editing operation (i.e., encodes what changes should be made). Its
ing for efficient finding of nodes and virtual memory to manage method, affects_volume_at(), determines if the edit affects a
the overall memory usage. The DAG data structure contains many certain volume, defined by node size at a specific level and position.
pointers, which would be impractical to update. We therefore design Leaf levels are handled separately (edit_leaf(), not shown,
the HashDAG such that its data does not need to be moved. We computes a 43 leaf volume and finds/inserts it in the DAG). The key
achieve this through a setup that uses fixed, predetermined memory operations find_node() and append_node() are detailed
addresses. The address space is managed with a standard virtual further in Section 3.2.
memory setup, i.e., where fixed-size pages are mapped to com-

© 2020 The Author(s)

Computer Graphics Forum © 2020 The Eurographics Association and John Wiley & Sons Ltd.
V. Careil, M. Billeter & E. Eisemann / Modifying Compressed Voxel Representations

node can be accessed via its virtual address v, computed by combin-

ing the hash, h, and the offset in the bucket i (see Figure 4):

v = levelBaseAddr + h × 2P + i.

The base address of the level, levelBaseAddr, is precomputed based

on the selected distribution of the memory regions for the different
levels in address space (i.e, from the N` ). If the node is not found,
Figure 3: One level of the HashDAG. In the figure, the level’s buck- it is appended to the corresponding bucket. Normally, the node is
ets correspond to rows in the table. The index inside the bucket is simply placed at the word following the final element of the last
given by the column. The level contains four nodes (colored differ- node in the bucket (or at index zero if no nodes are present yet).
ently). Each node starts with the child mask, immediately followed However, we ensure that nodes do not span across multiple pages:
by the child pointers. The number of child pointers is equal to the if a node does not fully fit into the remaining space of the last page
number of set bits in the child mask. In this illustration, we use a 16- of the bucket, we allocate a new page, and move the node to the
bit address space. Each bucket spans 256 consecutive 16-bit words. beginning of that page. The remaining words in the old page are set
Combining the 8-bit address of a bucket (leftmost column) with the to zero. The counter of the bucket is incremented by the amount of
index (upper and lower bytes, respectively) in the bucket (top row) potentially skipped words plus the size of the node.
creates a virtual address. Nodes are identified by the address of their
child mask. For example, the first node (0101, p0 , p1 ) has address Since nodes cannot span multiple pages, we only need to per-
0x3200, and the third (0100, r0 ) receives 0x3303. form one address translation per node during traversal. Similarly,
during editing, the translated address is needed as part of the
get_child_mask() and unpack_child_pointers() op-
pact ranges of addresses via an address translation table. Pages are erations and could be performed just once for both accesses.
only allocated when the memory at the corresponding addresses
is needed. The HashDAG has no special requirements regarding A key property of the HashDAG is that the hashing is only per-
the page size, making it compatible with, e.g., hardware supported formed when editing the structure. During traversal, however, no
virtual memory/“sparse resources”. hashes need to be computed, limiting the overhead of the HashDAG
to that arising from the extra indirection due to the virtual memory.
The HashDAG allocates a fixed address space for the whole DAG.
The size of the address space is linked to the size of the pointers
in the DAG structure. In our case, we rely on 32-bit pointers, and 3.3. Attribute encoding
consequently use a 32-bit address space. Note that addressing is
performed on a 32-bit word granularity, meaning that the address Our method maintains the structure and topology of the DAG, which
space spans 16GB of memory. Each node occupies a number of keeps it compatible to previous methods that integrate attributes,
consecutive 32-bit words: a node starts with a word containing the such as colors. Attributes are typically stored as a supplementary
child mask at the first address (the 8-bit child mask is padded to array that is compressed independently and each node in the DAG
32-bits), and is followed by k words containing the child pointers. makes use of its index (which is computed during a depth first traver-
Here, k is equal to the number of non-empty children of that node, sal) to look up the corresponding attribute. Several of the proposed
reflected by the number of set bits in the child mask. attribute compression schemes are relatively efficient when involv-
ing few attributes but can become costly for larger sizes. To avoid
Each level in the DAG receives a predetermined portion of the
these costs, we split our scene in chunks of a fixed size (correspond-
address space. Varying the size per level allows us to allocate less of
ing to subtrees of the DAG at a fixed depth, e.g., 10). The attribute
the address space close to the root (which contain fewer nodes) and
compression can then be applied to each of these subtrees inde-
use more of it for the levels that typically contain a large number of
pendently. Consequently, a local change only requires us to locally
nodes. By doing so, we maintain a more even distribution of nodes
update the corresponding subtree (see Figure 5). The calculation of
per amount of address space overall. In our implementation, we
node indices is compatible with our geometry-modification method,
decided to keep these memory regions to sizes of a power of two.
as we also rely on a depth-first traversal.
We denote the size of the memory region at level ` as 2N` .
To exemplify the possibility of manipulating attributes, we em-
We further subdivide the regions of each level into fixed-size
ployed the color compression method by Dolonius et al. [DSKA18].
buckets of size 2M . Hence, a level ` contains 2P buckets, where
The compressed color data is stored for each subtree of fixed depth.
P = N` − M. We track the number of used 32-bit bit words for each
When traversing the DAG, we first find the corresponding color
bucket in a counter. Nodes are always placed in the bucket at the
chunk and then decode the color as in [DSKA18]. When editing, the
index given by a P-bit hash of the node’s contents. The hash is
affected color chunks are rebuilt entirely: color data from unchanged
computed using a standard hash function [App16], taking the child
voxels in the same subtree is transferred to the new chunk in com-
mask and associated child pointers (each of which is just a 32-bit
pressed form (and voxel indices are updated as needed), as well
value) as input. Figure 3 illustrates the address layout of a level.
as colors from new voxels that are added into the color chunk. For
When searching for a node during editing (to check for its exis- details on the actual compression technique, which relates in parts
tence or to find its address), we compute the hash of the node, and to block compression methods such as S3TC/DXT/BCn [BC18], the
perform a linear search within the bucket identified by the hash. A interested reader is referred to their original article.

© 2020 The Author(s)

Computer Graphics Forum © 2020 The Eurographics Association and John Wiley & Sons Ltd.
V. Careil, M. Billeter & E. Eisemann / Modifying Compressed Voxel Representations

Figure 4: Editing with the HashDAG structure. The figure illustrates the process at Level N; this is the same level as shown in Figure 3. The
edit updates the structure shown there. Level N receives the child pointers p0,1 and t0 from Level N + 1 (c.f. recursive calls in Listing 1). We
construct the child masks by checking the returned pointer values. For each of the three non-empty nodes, we hash the child mask and the
pointers. This identifies the buckets in which the nodes will reside. The first and third nodes (blue) are identical and a linear search will find
them at index 0x00 of the hash table. Combining the bucket’s address (0x32) with the index gives the virtual address of the node, 0x3200.
The second node (orange) is not found in bucket 0x34, so we append it to the first possible location, index 0x02 here. The final virtual
address becomes 0x3402. The virtual addresses are returned to Level N − 1, where the process repeats.

Our implementation supports rudimentary multithreading. We

perform a single-threaded traversal until the color chunk depth. Any
continued traversals become independent jobs that are handed over
to a thread pool of fixed size. For the HashDAG structure, we use a
mutex per bucket. Color updates do not need synchronization, since
each color chunk is being rebuilt by a single job.

3.5. Garbage collection

As indicated in earlier sections, each modification adds new data
to the DAG structure, while the old versions of the DAG structure
remain valid. While this may be useful in some applications, the
Figure 5: We subdivide the scene into chunks that correspond recovery memory by removing the old versions may be desirable in
to subtrees of the geometry DAG at a fixed depth (=1 in this some cases.
figure). Each chunk applies the color compression of Dolo-
We apply a garbage collection method to trim the information.
nius et al. [DSKA18] independently. The compressed color chunks
We start with a list of root nodes that we wish to keep (for example,
are stored in a separate SVO. The figure shows the color data un-
the root node representing the state after the latest modification). We
compressed for simplicity; we refer to the original publication for
iterate over the nodes and extract a list of unique child pointers to
details on the compression.
the next level. We repeat this procedure with the new list, until we
reach the leaf level. By creating the unique list for each level, the
method scales with the number of DAG nodes that we want to keep,
3.4. Optimizations and implementation details and thus remains relatively efficient.
We noticed that many manipulations lead to locally constant voxel Next, we iterate over the DAG levels, starting at the leaf level.
volumes. A special handling of these cases leads to a significant in- We compact each level to only contain the nodes identified in the
crease in performance when adding or clearing large solid volumes. previous step, while maintaining a mapping from the original index
Specifically, during initial loading, we ensure that a node represent- to the new index in the compacted list. The mapping is used at the
ing a completely full subtree exists at all levels (this adds at most next higher level to update the child pointers to their new values.
one node to each level of the DAG structure), and keep track of its
location. During editing, we perform an additional test that checks
4. Results and Discussion
whether or not the modification would completely fill or empty the
node in question. If it is completely filled, we simply return the To illustrate our approach, we produced a prototype, in which users
pointer of the well-known full-subtree node of the corresponding can load and interactively edit an existing voxel DAG model. Our
level. If it is empty, we already handle the situation efficiently, as implementation performs modifications on the CPU and renders the
the empty volume is simply recorded by indicating an absent child DAG structures on the GPU, using CUDA. We ran measurements
node in the parent’s child mask. A similar optimization also works on an Intel Core i7-8700K CPU (6 cores with 2× hyperthreading)
for solid colors, but varying colors require the generation of the with 16GB of DDR4 memory and a NVIDIA GeForce RTX 2080
corresponding compressed color data. GPU under Linux.

© 2020 The Author(s)

Computer Graphics Forum © 2020 The Eurographics Association and John Wiley & Sons Ltd.
V. Careil, M. Billeter & E. Eisemann / Modifying Compressed Voxel Representations

(64k)3 - Large (128k)3 - Large

(64k)3 - Small (128k)3 - Small

Figure 6: Overheads from the virtual memory and the color SVO.
We show the rendering performance in a short predefined fly-through
through each of the scenes, for our custom DAG structure as well as
a standard DAG without virtual memory. The top row shows results
for the Epic Citadel scene, at a (128k)3 resolution. The bottom row
shows the San Miguel scene, at (64k)3 . Rendering performance is
on average about 1.5× slower due to the virtual memory, with a
worst case of about 2× slowdown. Resolving colors adds overheads
of similar magnitude. Tracing geometry and resolving colors are
separate passes, the full rendering time is the sum of both. Note that
the irregular tree model in San Miguel is quite expensive to render,
making it more expensive despite the lower resolution.

Figure 6 compares the traversal performance of our HashDAG

structure with the original DAG implementation. Our virtual mem- Small Large
ory scheme introduces an overhead of 1.5× to 2× for the raytracing
of the geometry (although the performance already varies greatly for Figure 7: Performance of geometry and color modifications w.r.t.
different scenes). Resolving attributes requires an additional traver- size of the modification in voxels, using varying numbers of threads.
sal of an SVO to locate the chunk associated with the intersected We present data from two separate editing sequences, both in the
node. In case of our implemented solution for colors, it introduces an Epic Citadel scene at (64k)3 and (128k)3 resolutions. The first
overhead of similar magnitude. We believe the raytracing overhead sequence includes smaller modifications (< 350k voxels in (64k)3
could be mitigated by using sparse resources [Vk19] - hardware and < 2.5M in (128k)3 ). The second sequence performs larger
support for user-controlled virtual memory mappings. However, at modifications affecting up to 350M voxels in (64k)3 and 3G in
the time of writing, sparse resources are unsupported in CUDA and (128k)3 , respectively. The images at the bottom show the scenes
such an implementation remains future work. after the modifications from the sequences (small edits to the left,
large to the right).
Our prototype includes several editing tools; copying parts of the
existing voxel structure, adding and removing (carving) voxels in
regions of different shapes, painting colors and a non-optimized source). Figure 7 shows the performance of modifications of varying
tool for filling hollow spaces (see Figure 1). We added the latter sizes. We include results from two test sequences at two resolutions,
only for visualization purposes because voxel DAG structures are (64k)3 and (128k)3 . The two test sequences are repeated for both
often created from traditional meshes resulting in thin shells, as only resolutions such that sizes of the modifications in world space are
the surfaces are voxelized. Filling such shells before carving into maintained (i.e., the same operation will affect many more voxels in
them ended up being useful for visual purposes (Figure 1, bottom the higher resolution scene). The first test focuses on small modi-
right). To solidify such objects, we perform a flood fill operation fications (affecting up to 350k and 2.5M voxels, respectively), the
that marches over the voxel grid from the user selected position. second on large edits, affecting up to 350M and 3G voxels.
To evaluate the performance of our method, we focus on sim- Figure 8 repeats the same tests, albeit for geometry only (i.e.,
ple editing operations and group the edits by the number of voxels the color updates are omitted). Here, the effect of the full-subtree
they change. More complex operations (such as copies) carry over- optimization (Section 3.4) becomes obvious, as the time required
heads unrelated to the presented method (e.g., traversing the copy’s for modifications of increasing sizes scales sublinearly. For large

© 2020 The Author(s)

Computer Graphics Forum © 2020 The Eurographics Association and John Wiley & Sons Ltd.
V. Careil, M. Billeter & E. Eisemann / Modifying Compressed Voxel Representations

(64k)3 - Large (128k)3 - Large (64k)3 (128k)3

(64k)3 - Small (128k)3 - Small

Figure 9: Performance of copy operations with different source
volume (“template”) sizes (top row). In contrast to the modifications
from Figure 7 that add solid volumes, the copy operations operate
on very sparse (but irregular) templates (bottom row). Thus, very
few voxels actually change, and most of the time is spent on evaluat-
ing the template. The copies become entirely CPU bound. (Right)
Together the operations construct the tower to the right.

Note that the source volume’s colors are decompressed in phase

one as well. We do not optimize the copies by transferring already
Figure 8: Performance of geometry-only modifications w.r.t. size of
compressed color data, again with the goal of demonstrating the effi-
the modifications in voxels, using varying numbers of threads. The
cient manipulation, not an efficient tool. For variants on the editing
edit-sequences are identical to those in Figure 7.
operations and additional tests, we refer the interested reader to the
supplementary material.
edits, our method scales well with additional threads up to a cer-
Both page size and the number of buckets per HashDAG level
tain limit (four on our machine), at which point adding additional
affect performance. By default, we use a page size of 512 together
threads yields only minor increases in performance. We suspect
with 216 buckets on lower levels (≥ 10) of the DAG. Levels close to
that the method becomes memory bound at that point. For small
the root need fewer buckets (we use 1024), which allows us to reduce
edits, multithreading helps little, as the edits are smaller than the
memory demands. In Figure 10, we show performance with respect
subtrees we parallelize over (and any small gains are likely offset
to page size and bucket count. In general, increasing either page size
by additional overheads related to the multithreading).
or bucket count improves performance, but comes at the cost of a
The combination of geometry and color modification is more higher memory overhead. The memory overhead stems from allo-
costly than geometry-only edits. For color edits, we also observe cated but only partially filled pages. A larger page size increases the
a much larger variation in performance. This is a consequence of unused space for each partially filled page, and a larger bucket count
varying workload. When adding a new voxel in empty space with increases the number of partially filled pages. The exact memory
no pre-existing surrounding geometry, the new color chunk only overhead varies over time. However, immediately after loading the
contains the color of the added voxel. However, if the voxel is added HashDAG structure (Epic Citadel at (64k)3 , weighing in at 380MB
in the vicinity of other geometry, building the color chunk involves of data), we observed memory overheads of approx. 105MB (128
transferring existing color data from the surrounding geometry and word page size), 260MB (256 words) and 550MB (512), using the
adding the new colors as well. default bucket count of 216 . Tests with increasing bucket counts
use a page size of 128, as to conserve memory and enable large
Figure 9 displays results from a sequence of copy-operations.
bucket counts. Overheads are approx. 105MB (216 buckets), 480MB
The goal of this tool is to emulate sparse and highly irregular edit
(218 ) and 1165MB (220 ). Additional memory overheads from page
operations (in itself it is not intended to be a very efficient imple-
padding to avoid placing nodes in multiple pages are negligible in
mentation of a copy tool). The copy operations are implemented in
comparison (. 20MB for (128k)3 with 216 buckets and page size
two phases. First, we create a template by decompressing the source
128, which is the worst case for the page padding in our set of tests).
volume. Second, we apply our method, using the template as a guide
with which voxels are modified or left as-is (empty voxels in the The quality of hash functions is also critical to the performance
source are left as is). We only measure performance for the second of the HashDAG. Uneven distribution of nodes across the buckets
phase. For instance, the full- and empty-subtree optimizations never would quickly lead to problems, first negatively impacting perfor-
apply, as we do not store hierarchical information in the template. mance, and ultimately filling up some buckets completely, prevent-

© 2020 The Author(s)

Computer Graphics Forum © 2020 The Eurographics Association and John Wiley & Sons Ltd.
V. Careil, M. Billeter & E. Eisemann / Modifying Compressed Voxel Representations

As indicated in the description of our method, old states of the

structure remain valid and accessible via alternate root nodes (we
optionally keep historical color data as well). In Figure 11, we
show the memory usage over time, with an increasing number of
changes (represented by the cumulative number of voxels changed
so far). Additionally, we show the minimum size of the data, as
if the garbage collection method were run after each modification.
Memory usage still grows, which is to be expected, as new geome-
try is added with each modification. Historical color data, needed
to support undo/redo operations, is relatively expensive. A limi-
Figure 10: Performance for different page sizes and bucket counts tation of our current implementation prevents us from freeing up
(geometry only, for the large edits sequence from Figure 7). Page the initial color data (≈1.2GB), compressed using the method of
size and bucket count are two of the main variables that control the Dolonius et al. [DSKA18], even as parts of it are replaced with new
performance of the HashDAG. We show both unthreaded (left figure color chunks generated on the fly.
of each pair) and threaded (right figures) performance. Performance
increases with larger page sizes, but this also results in a larger The garbage collection implementation is currently unoptimized,
unused memory overhead from partially filled pages. Increasing the and doing a garbage collection in the Epic Citadel scene at (64k)3
number of buckets has a similar impact (the test was performed with takes 25 seconds, of which 18 seconds are spent on the lower levels
page size equal to 128). (≥ 12). The performance can certainly be improved, and we have
identified significant overheads related to our usage patterns of
standard containers (mainly std::unordered_{set,map}).

Our implementation suffers from other overheads that we have

not presently addressed, and that are unrelated to our method. For
example, transferring modified data from the CPU to the GPU for
rendering is currently very expensive (order of tens of milliseconds),
as it is implemented with a large number of small cudaMemcpy
Figure 11: Memory use over the large edits sequence (Figure 7) operations. A better approach would be to collect all small changes
for the Epic Citadel scene at (64k)3 . (Left) Memory usage by the resulting from a single modification into a single buffer, transfer it,
geometry. The graph includes total memory usage with and without and use a CUDA kernel to distribute the small modifications to the
garbage collection (GC), as well as performing partial garbage GPU’s copy of the data. However, this remains future work.
collection of levels zero to the specified number. (Right) Memory
usage for color data in the same sequence. We show usage both with It is noteworthy that our solution requires only compute time in
and without keeping historical data for undo/redo support. the order of milliseconds for scenes with 1015 voxels and edits of
the size of several million voxels, including updates to an additional
attribute in the form of color. We invite the reader to watch the
ing further nodes from being added there. For interior nodes, we rely accompanying video to experience an interactive editing session.
on the MurmurHash3 [App16] function. For leaf nodes, we simply
use the bit mixing step of the MurmurHash3. For high levels, e.g.
≤ 5, many buckets are empty (and non-empty buckets contain on
average very few nodes, typically in single digits). For lower levels 5. Conclusion and Future Work
of the HashDAG, we have always observed a normal distribution of
Our solution enables interactive editing of an unprecedented scale.
the node counts per bucket. For example, at (64k)3 with 216 buckets,
We efficiently modify very high resolution compressed sparse voxel
we have observed the following: buckets in level 12 (the level with
structures, while avoiding de- and recompression cycles. This pos-
the most nodes in this instance) contain on average approx. 600
sibility is enabled via our HashDAG, a compressed structure that
32-bit words of data (∼120 nodes), with a standard deviation of 60
can be modified on the fly and is relatively easy to implement. Our
words. The smallest bucket has 327 words, and the largest 903 - that
prototype editor allows users to perform modifications to existing
is less than half of the maximum bucket size that we have reserved
voxel structures at many different scales interactively on commodity
in this configuration (2048 words per bucket).
hardware, while even keeping track of changes at a low additional
The reserved bucket size is a hard upper limit: we cannot change memory cost. It maintains the traversal mechanism and access pos-
the size of the buckets’ reserved address space at runtime. It is sibilities of existing hierarchical voxel grids, which makes it easy
therefore necessary to ensure that the reserved space is large enough to integrate the solution in other applications, while offering ad-
to enable future edits (up until a garbage collection step clears ditional compression and modification capabilities. One example
unused nodes). For very large data sets ( (128k)3 ) or for very could be a large-scale procedural-world generation, inspired by the
large amounts of changes, it is possible to use a full 32-bit address work of Peytavie et al. [PGMG09], that allows for directly influenc-
space per level, or even switch to a larger address space (and thus ing the high-resolution terrains. The possibility of testing visibility
larger pointers), in order to ensure that there is sufficient space efficiently in a voxel grid could also make it interesting to use the
available in each bucket. editor for performance-sensitive scene design [ED07].

© 2020 The Author(s)

Computer Graphics Forum © 2020 The Eurographics Association and John Wiley & Sons Ltd.
V. Careil, M. Billeter & E. Eisemann / Modifying Compressed Voxel Representations

Acknowledgements [ED07] E ISEMANN E., D ECORET X.: Visibility sampling on GPU and
applications. Computer Graphics Forum (Proc. of Eurographics) 26, 3
We would like to thank Dan Dolonius and colleagues for pro- (2007). doi:10.1111/j.1467-8659.2007.01076.x. 8
viding the software to create the initial compressed DAG geom-
[GMI08] G OBBETTI E., M ARTON F., I GLESIAS G UITIÁN J.: A single-
etry and attributes from source meshes. The source scenes, San
pass GPU ray casting framework for interactive out-of-core rendering
Miguel [McG17] and Epic Citadel, were created by Guillermo M. of massive volumetric datasets. The Visual Computer 24, 7-9 (2008).
Leal Llaguno and Epic Games, respectively. doi:10.1007/s00371-008-0261-9. 2
This work was partially funded by the Swiss National Science Foun- [JMG16] JASPE A., M ARTON F., G OBBETTI E.: SSVDAGs: Symmetry-
dation (Advanced Postdoc Mobility Project 174321) and the VIDI aware sparse voxel DAGs. In Proceedings of the 2016 ACM SIGGRAPH
NextView, funded by NWO Vernieuwingsimpuls. Symposium on Interactive 3D Graphics and Games (2016), I3D ’16.
doi:10.1145/2856400.2856420. 1, 2
[JMG17] JASPE A., M ARTON F., G OBETTI E.: Symmetry-aware sparse
References
voxel DAGs (SSVDAGs) for compression-domain tracing of high-
[3DC] 3DCoat. https://3dcoat.com/, accessed 2020-02-26. 2 resolution geometric scenes. Journal of Computer Graphics Techniques
(JCGT) 6, 2 (2017). http://jcgt.org/published/0006/02/
[ABD∗ 18] A SSARSSON U., B ILLETER M., D OLONIUS D., E ISEMANN
01/. 2
E., JASPE A., S CANDOLO L., S INTORN E.: Voxel DAGs and Multires-
olution Hierarchies: From Large-Scale Scenes to Pre-computed Shad- [KBLE19] KOL T. R., BAUSZAT P., L EE S., E ISEMANN E.: MegaViews:
ows. In EG 2018 - Tutorials (2018), The Eurographics Association. Scalable many-view rendering with concurrent scene-view hierarchy
doi:10.2312/egt.20181028. 2 traversal. Computer Graphics Forum 38, 1 (2019), 235–247. doi:
10.1111/cgf.13527. 2
[App16] A PPLEBY A.: MurmurHash3, 2016. https:
//github.com/aappleby/smhasher/wiki/MurmurHash3, [KRB∗ 16] K ÄMPE V., R ASMUSON S., B ILLETER M., S INTORN E.,
accessed 2020-02-26. 4, 8 A SSARSSON U.: Exploiting coherence in time-varying voxel data. In
Proceedings of the 2016 ACM SIGGRAPH Symposium on Interactive
[Ast] Astroneer - A Game of Aerospace Industry and Interplanetary Ex-
3D Graphics and Games (2016), I3D ’16. doi:10.1145/2856400.
ploration. https://astroneer.space/, accessed 2020-02-26. 2
2856413. 1, 2
[BC18] Block compression (Direct3D 10), 2018. https:
[KSA13] K ÄMPE V., S INTORN E., A SSARSSON U.: High resolution
//docs.microsoft.com/en-us/windows/win32/
sparse voxel DAGs. ACM Transactions on Graphics 32, 4 (2013). doi:
direct3d10/d3d10-graphics-programming-guide-
10.1145/2461912.2462024. 1, 2
resources-block-compression, accessed 2020-02-26. 4
[LK10] L AINE S., K ARRAS T.: Efficient sparse voxel octrees. In Proceed-
[BLD13] BAERT J., L AGAE A., D UTRÉ P H .: Out-of-core construction
ings of the 2010 ACM SIGGRAPH Symposium on Interactive 3D Graphics
of sparse voxel octrees. In Proceedings of the 5th High-Performance
and Games (2010), I3D ’10. doi:10.1145/1730804.1730814. 2
Graphics Conference (2013). doi:10.1145/2492045.2492048.
2 [Mc] Minecraft. https://www.minecraft.net/en-us/, ac-
cessed 2020-02-26. 2
[BRGIG∗ 14] BALSA RODRÍGUEZ M., G OBBETTI E., I GLESIAS G UI -
TIÁN J., M AKHINYA M., M ARTON F., PAJAROLA R., S UTER S.: State- [McG17] M C G UIRE M.: Computer graphics archive, 2017. https:
of-the-art in compressed GPU-based direct volume rendering. Computer //casual-effects.com/data. 9
Graphics Forum 33, 6 (2014). doi:10.1111/cgf.12280. 2 [Mea82] M EAGHER D.: Geometric modeling using octree encoding.
[CNLE09] C RASSIN C., N EYRET F., L EFEBVRE S., E ISEMANN E.: Gi- Computer Graphics and Image Processing 19, 1 (1982), 85. doi:
gavoxels: Ray-guided streaming for efficient and detailed voxel rendering. 10.1016/0146-664X(82)90128-9. 1, 2
In Proceedings of the 2009 ACM SIGGRAPH Symposium on Interactive [PGMG09] P EYTAVIE A., G ALIN E., M ERILLOU S., G ROSJEAN J.:
3D Graphics and Games (2009), I3D ’09. doi:10.1145/1507149. Arches: a Framework for Modeling Complex Terrains. Computer Graph-
1507152. 2 ics Forum (Proc. of Eurographics) 28, 2 (2009). doi:10.1111/j.
[CNS∗ 11] C RASSIN C., N EYRET F., S AINZ M., G REEN S., E ISEMANN 1467-8659.2009.01385.x. 8
E.: Interactive indirect illumination using voxel cone tracing: A preview. [SKOA14] S INTORN E., K ÄMPE V., O LSSON O., A SSARSSON U.: Com-
In Proceedings of the 2011 ACM SIGGRAPH Symposium on Interactive pact precomputed voxelized shadows. ACM Transactions on Graphics
3D Graphics and Games (2011), I3D ’11. doi:10.1145/1944745. 33, 4 (2014). doi:10.1145/2601097.2601221. 2
1944787. 2
[SVR] SculptVR - Build your world with friends in ScultVR. http:
[CNSE10] C RASSIN C., N EYRET F., S AINZ M., E ISEMANN E.: Efficient //www.sculptrvr.com/, accessed 2020-02-26. 2
rendering of highly detailed volumetric scenes with gigavoxels. In GPU
Pro, Engel W., (Ed.). A K Peters, 2010, ch. X.3. http://maverick. [Vk19] Vulkan 1.1.123 - A Specification - Chapter 31 - Sparse Resources,
inria.fr/Publications/2010/CNSE10. 2 2019. https://www.khronos.org/registry/vulkan/
specs/1.1-extensions/html/vkspec.html, accessed
[DKB∗ 16] DADO B., KOL T. R., BAUSZAT P., T HIERY J.-M., E ISE - 2020-02-26. 6
MANN E.: Geometry and attribute compression for voxel scenes. Com-
puter Graphics Forum (Proc. of Eurographics) 35, 2 (2016). doi:
10.1111/cgf.12841. 1, 2
[DSKA18] D OLONIUS D., S INTORN E., K ÄMPE V., A SSARSSON U.:
Compressing color data for voxelized surface geometry. IEEE Trans-
actions on Visualization and Computer Graphics 25, 2 (2018). doi:
10.1109/TVCG.2017.2741480. 1, 2, 4, 5, 8

© 2020 The Author(s)

Computer Graphics Forum © 2020 The Eurographics Association and John Wiley & Sons Ltd.