A novel GPU-optimized CSG ray-tracing approach is presented that is fast and accurate, and allows achieving real-time frame rates at full-screen resolutions. It has no limitations on the maximum number of primitives, and produces final image in a single pass. We propose an efficient procedure to transform an input CSG tree into equivalent spatially coherent and well-balanced form. Through various experiments, we show that our solution allows interactive rendering of CSG models consisting of more than a million CSG primitives on consumer graphics cards.
In general, there are two basic approaches to render a CSG model. The first one is based on
precomputing of the boundary of a CSG shape which can be tessellated into a triangular mesh and then
rendered using conventional graphics methods. Since evaluation of CSG boundary is computationally
expensive, these algorithms are mainly limited to static models and do not allow interactive editing.
The second approach involves so-called image-based algorithms which generate just the image of a
CSG model without expensive computation of the full shape geometry. Most of these algorithms are
designed for graphics hardware and based on multi-pass, view-specific techniques making extensive
use of depth and stencil buffers. The typical algorithms in this class are Goldfeather algorithm [1, 2]
and the Sequenced Convex Subtraction (SCS) algorithm [
An alternative approach has been proposed in the later work [4]. The so-called Blister algorithm
does not require a conversion to the sum-of-products form. Instead, it converts an arbitrary Boolean
combination of primitives into the Blist form [
The above algorithms can achieve interactivity for relatively complex CSG shapes (thousands of
primitives). However, all these techniques use many rendering passes, and thus are bandwidth limited.
For many years, GPU memory bandwidth grows slower than computing performance, resulting in a
data transfer bottleneck for many GPU-accelerated applications. A completely different approach was
adopted in [
Ray-tracing of the entire CSG tree is possible and used quite widely. However, most approaches
to render CSG scenes require computing all intersections of a ray with a primitive. The ray is broken
into intervals corresponding to the intersected primitives. After that the Boolean operations are applied
to find out the first interval that is actually inside a CSG object. Due to a large amount of computation
and significant memory consumption this approach can be extremely expensive. Moreover, it is poorly
suited for a GPU, the effective use of which requires tens of thousands of threads running in parallel.
Since GPU hardware resources are divided among threads, low resource usage is crucial to support a
plurality of simultaneously-active threads. However, the implementation of interval CSG ray-tracer on
the GPU is still possible as shown in [
function INTERSECT(node, min) minL ← min minR ← min (tL,NL) ← INTERSECT(L(node), minL) (tR,NR) ← INTERSECT(R(node), minR) stateL ← CLASSIFY(tL, NL) stateR ← CLASSIFY(tR, NR) while true do actions ← table[stateL, stateR] if Miss ∈ actions then return miss if RetL ∈ actions or (RetLIfCloser ∈ actions and tL ≤ tR) then return (tL, NL) if RetR ∈ actions or (RetRIfCloser ∈ actions and tR ≤ tL) then if FlipR ∈ actions then NR ← −NR return (tR, NR) else if LoopL ∈ actions or (LoopLIfCloser ∈ actions and tL ≤ tR) then minL ← tL (tL, NL) ← INTERSECT(L(node), minL) stateL ← CLASSIFY(tL, NL) else if LoopR ∈ actions or (LoopRIfCloser ∈ actions and tR ≤ tL) then minR ← tR (tR, NR) ← INTERSECT(R(node), minR) stateR ← CLASSIFY(tR, NR) else return miss
A quite different approach based on single-hit ray-tracing (finding only nearest intersection) has been proposed in [8]. The algorithm uses a concept of state machine to calculate the intersection with a CSG model. The only limitation is that the basic CSG primitives should be closed (can be relaxed to handle orientable surfaces), non-self-intersecting and have consistently oriented normals. This elegant idea makes it quite easy to integrate CSG rendering into existing ray-tracing systems. Although the paper does not contain any characteristics of the algorithm, it looks suitable for the GPU and inspired our work. In the remainder of this section, we outline the main steps of this algorithm and point out some inaccuracies in the original state tables.
Let T be a CSG tree, and let L(T) and R(T) be the left and right sub-tree of T. To find the nearest intersection of ray R and tree T the ray is shot at sub-trees L(T) and R(T), and then the intersection with the each sub-tree is classified as one of entering, exiting or missing it. Based upon the combination of these two classifications, one of several actions is taken: (a) returning a hit; (b) returning a miss; (c) changing the starting point of ray R for one of sub-trees and then shooting this ray again, classifying next intersection. In latter case, the state machine enters a new loop (see Figure 1). Kensler proposed 3 state tables (one for each Boolean operation) needed to ray-trace a CSG shape. Unfortunately, these state tables are not complete and lead to incorrect visualization. In this paper we provide refined state tables allowing correct visualization in all cases (see Table 1). Kensler’s algorithm is recursive and poorly suited for a GPU. While recursion is supported on CUDA-enabled GPUs, the iterative version with a manually-managed state stack provides a much better performance, and can be implemented in the environment without recursion support (e.g., OpenGL, OpenCL). However, transforming of the algorithm into iterative form is not trivial due to a large number of parameters and local variables.
As our main contribution, we propose the iterative CSG ray-tracing algorithm that uses minimal state and is optimized for massively parallel architectures with limited (per thread) memory resources like GPUs. For that purpose we define a high-level state machine that manages the execution of the original algorithm in the iterative manner (see Figure 2).
The use of state tables for each Boolean operation (let us call them CSG tables) is based on
precomputed intersections with child objects of the current CSG node. Thus, all of the states of high-level
pushdown automata are divided into two categories: (a) calculation of intersections with child objects,
and (b) applying CSG tables for classification of the processed CSG node. The first category includes
the states GotoLft (finding the intersection with the left sub-tree), GotoRgh (finding the intersection
with the right sub-tree), and SaveLft (storing the intersection parameters with the left sub-tree and
then execution of GotoRgh). The last state is needed since the processing of the right sub-tree leads
to trashing local variables. The second category includes the following states: Compute (applying
CSG tables), LoadLft (loading intersection data for the left sub-tree and then execution of Compute),
LoadRgh (loading intersection data for the right sub-tree and then execution of Compute). General
scheme of transition between the states is shown in Figure 3. Here the GoTo() function (see Figure 4)
calculates intersection points with left and right sub-trees, while the Compute() function (see Figure
4) classifies these points in order to detect the first intersection of a ray with the actual boundary of
CSG shape. Note that GoTo() function enables the use of bounding boxes to improve the performance
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)
agora.guru.ru/pavt
of intersection function. Such bounds are calculated for each node of CSG tree to obtain a bounding
volume hierarchy [
tmin ← 0 node ← V // virtual root whose left subtree is the real root (tL, NL) ← invalid (tR, NR) ← invalid PUSHACTION(Compute) action ← GotoLft while true do if action ≡ SaveLft then tmin ← POPTIME() PUSHPRIMITIVE(tL, NL) action ← GotoRgh if action ∈ {GotoLft, GotoRgh} then GOTO() if action ∈ {LoadLft, LoadRgh, Compute} then COMPUTE()
It is obvious that the performance of our algorithm greatly depends on the topology of CSG tree that affects spatial coherence of primitives and height of the tree. However, the creation of a balanced, unbalanced, or a perfect CSG tree depends generally on the user. Thus, it is necessary to transform an input tree T into an equivalent well-balanced tree T of roughly the same size as T.
We propose an efficient pipeline for optimizing CSG trees that runs in four phases: (a) converting the input tree T to a positive form; (b) spatial optimization of tree topology; (c) minimizing height of the tree; (d) reverse converting to a general form giving the output tree T.
A CSG tree T is represented in the positive form using only and operations and negation of leaf nodes. This conversion can be easily done using the following transformations: ∪ = ∩ , ∩ = ∪ , − = ∩ The above transformations are applied to the tree in a pre-order traversal, and thus all complements are propagated to the leaf nodes. The reverse conversion to general form can be performed using a postorder traversal (in this case all negations are first removed from the children of each node).
For optimal performance, the tightness bounds of CSG tree nodes should be used which minimize the probability of ray intersection. For this purpose, we propose the spatial optimization procedure allowing minimizing the bounds of CSG nodes. Let us define treelet as the collection of immediate descendants of the given CSG tree node. Our optimization procedure is based on repeatedly selecting of treelets consisting of nodes with the same Boolean operation and their subsequent restructuring (in positive form, we are free to change the order of treelet nodes). Treelets are constructed during a preorder traversal of CSG tree by expanding child nodes that have the same Boolean operation as the treelet root. The resulting treelet is reorganized by means of surface area heuristic (SAH), widely used for construction of accelerating structures such as k-d tree or Bounding Volume Hierarchy (BVH). Thereafter, the traversal of CSG tree continues with the outer treelet nodes.
The restructuring of treelet is based on the same binned technique as is used for construction of
BVH [
Our algorithm evaluates intersection point in iterative manner by maintaining a stack. However, on massively parallel architectures like GPUs managing full per-ray stacks leads to significant storage and bandwidth costs. To reduce the traversal state size we desire a well-balanced CSG tree. Our next optimization stage is aimed to address this problem by minimizing the height of CSG tree using local transformations. At this stage, two types of treelets are considered. For brevity, let us call the child node with a greater height (in the whole tree T) the heavy child. The first type is formed of treelets which have the same Boolean operation ( or ) in root node N1 and its heavy child N2 (see Figure 5a). Let T3 be a heavy child of the node N2. Obviously if h(T3) > h(T1) + 1 it is beneficial to transpose these subtrees. As with the rotations for binary search trees these result in elevating subtree T3 and demoting subtree T1. Thus, the height of the treelet, rooted at N1, is decreased by one.
The second type of treelets corresponds to the case where the operations in the root node N1, its heavy child N2 and heavy grandchild N3 are interleaved (i.e. −− or −−). Let us consider the −− sequence (see Figure 5b). In this case, the treelet rooted at N1 can be described by expression: T1 (T2 T3 T4) = (T1 T2) (T1 T3 T4). Let T4 be a heavy child of the node N3. Therefore, if h(T4) > h(T1) + 2, then the normalization of the given treelet allows reducing its height by one. Please note that this normalization is localized, and thus has no effect on other tree nodes. However, even this optimization is undesirable because it results in duplication of the subtree T1. For this reason we use such transformations only when optimizations of the first type have been exhausted. We use the multipass scheme, where at each pass a CSG tree is traversed in post-order, and appropriate restructuring patterns are applied.
For this study, all results have been measured using an NVIDIA GeForce GTX 680, AMD Radeon HD 7870 and Intel HD 4000 GPUs. All timings correspond to rendering in a 1280 × 720 window. The first test scene shows a CSG model of the city at different scales (see Figure 6). In all below cases the whole City scene is modeled as a single CSG tree. In a simple configuration (a), the model contains 3385 primitives. More complex configurations (b and c) contain 343K and 987K CSG primitives correspondingly. Scene b from upper row shows the case with extreme number of depth layers that is rather challenging for other approaches. Therefore, this test allows analyzing the performance depending on the complexity of the CSG model. For each GPU results are represented by two columns (see Table 2): left one corresponds to measured FPS without spatial optimization (−), and the right one was obtained with enabled spatial optimization (+). N/A markers shown were performance clearly cannot be considered to be interactive. − 7 1.8 2.3 0.4 N/A N/A 5 2.8 2.5
Intel 4000
The second test scene represents a procedural Swiss cheese CSG model with the holes of varying radius (see Figure 6). Number of holes increases from 1000 (left) to 8000 (middle), and then to 32000 (right ) resulting in a larger number of overlapped primitives and greater depth complexity. Thus, unlike the City model, the performance of the Swiss cheese model is affected greatly by spatial optimization.
The third test scene demonstrates a large number of satellites orbiting a planet (see Figure 8). In this case, each satellite is represented by a separate CSG tree. A plurality of independent satellites are placed into the scene as outer nodes of high-level BVH. Since we are able to interactively rebuild accelerating structure each frame (at least for tens of thousands of objects), we can arbitrarily modify transformations of particular CSG trees. As a result, it becomes possible to edit the scene or to animate arbitrary shapes. In our test case, the satellites move across the planet along randomly selected orbital tracks.
We found that our implementation scales well with increasing the GPU clock speed (Figure 7 shows linear dependence on clock speed). Therefore, we can expect further performance increase on later generations of GPUs. In contrast, the memory clock does not affect performance, which confirms the assumption that the algorithm is not memory-bound.
From practical point of view, there are several factors which can affect the rendering performance. The first one is screen resolution as for over ray-tracing methods. The frame rate decreases almost linearly increasing the total number of processed pixels. The second important factor is the number of primitives, but however, it does not affect performance directly. Experiments show that we can easily render City scene containing more than 1 million CSG primitives while having trouble with 32K Swiss cheese model. This is due to extensive overlaps between the primitives in cheese model which force the algorithm to iterate over the CSG sub-trees intensively in order to classify intersection points. Moreover, the efficiency of spatial optimizer also suffers from a large number of overlapped primitives. However, even in this stress scenario, we can show near linear performance degradation depending on the number of primitives.
GF680
GF680 500 700 900 1100 2400 2600 2800 3000 3200
Given that our solution is based on ray-tracing, it can be naturally extended to produce various visual effects such as transparency, shadows, reflections, refractions, etc. Using OpenGL/GLSL as the main API for GPU computations allows seamless interoperability between CSG rendering engine and standard OpenGL pipeline. For that purpose we calculate the depth value for each processed fragment, based on the intersection time and camera projection matrix. For example, the rendering can be extended with text annotations, axes, or generic triangulated objects drawn by OpenGL. Finally, our solution allows implementing the hardware-accelerated selection mechanism. To this end, we write unique IDs of intersected objects into a separate texture allowing to identify a CSG primitive, or even its particular face, which lies under the given pixel.
a) b) c)
We proposed a GPU-optimized CSG rendering approach, which is fast and accurate, and allows achieving real-time frame rates at full-screen resolutions. Unlike alternative image-based CSG algorithms, our solution is more compute-bound than bandwidth-bound, and does not impose restrictions on the maximum number of CSG primitives being limited only by available GPU memory. We also proposed the efficient pre-processing stage to convert an input CSG tree into equivalent spatially coherent and well-balanced form. As a result, our CSG rendering system provides interactive or even real-time performance for CSG models consisting of more than a million CSG primitives on consumer graphics cards.
35 30 SP25 F 20 15 1.
Kensler A. Ray tracing CSG objects using single hit intersections URL: http://xrt.wdfiles.com/local--files/doc%3Acsg/CSG.pdf.