csg: subtracting solids in webgl

Suppose that, having two 3D objects, we need to render the mesh that is obtained by subtracting one from the other. That is, we take one object, and remove from it the points belonging intersection between itself and the other object. For concretness, if we have a rectangular mesh B, and a shpere A, as in the drawing below, then the red outline corresponds to the set of points B - A.

This way of obtaining new solids via a sequence of set-operations on other solids is usually called constructive solid geometry, or csg. Such sequence is usually represented by a hierarchical tree. But let’s keep things very simple here and consider only one operation, subtraction, on a pair of solids.

I’m not really interested here in obtaining the solid’s set of points, or even it’s representative data structure, but only in rendering a representation of the final solid obtained by the operations.

In other words, given solids A and B, how do we render the resulting solid B - A?

Well, as one would imagine, a lot of different methods to achieve this were developed along the years. Some more, some less suited for real-time rendering; on top of that, webgl does not have the same tools as more advanced OpenGL specifications, which restricts our range even more. Let’s then take a look at a couple of CSG algorithms and implement a small demonstration — the simple case of CSG subtraction above — using threejs to make things easier (maybe not much easier tough…).

The goldfeather algorithm

So, let’s say we have a primitive A and a sequence of other primitives P₁, P₂,..., Pₙ which we would like to subtract from A. The goldfeather algorithm for this subtraction proceeds roughly by rendering the front surface of A (into a temporary depth buffer), clipping out of A all intersecting back-surfaces of all the P, and saving the results in the final depth-buffer; then, for each one of the subtracting primitives, draw the relevant back-surface parts into the temporary depth-buffer, and composite them into the final depth buffer; finally, we can render the front of A and the back of all the P using something like gl.depthFunc(gl.EQUAL) and have the final result.

In pseudo code:

begin renderGoldfeatherSubtract(A, P₁, P₂,…, Pₙ) 
do 
    for each primitive P in (A, P₁, P₂,…, Pₙ)
        if P == A
            draw front of P into Zₜₑₘₚ
        else
            draw back of P into Zₜₑₘₚ
        for each Q ≠ P in A, P₁, P₂,…, Pₙ
            parityClip(Q, Zₜₑₘₚ, P ≠ A)
        merge Zₜₑₘₚ buffer into Zₒᵤₜ (where Zₜₑₘₚ < Zₒᵤₜ)
        set depthFunc to EQUAL
        draw front of A
        draw back of P₁, P₂,…, Pₙ
begin parityClip(S, Z, isSubtracted) 
do  
    clear stencil to 0
    disable face culling
    for all fragments of S
        if (Zₛ < Z)
            stencil += 1
    for all pixels
        if (isSubtracted)
            if stencil is odd
                Z = Zfₐᵣ
        else
            if stencil is even
                Z = Zfₐᵣ

It’s a little convoluted, but maybe the drawing below can give a better idea of the process:

As implementation goes, it’s hard to do this in webgl (vanilla WebGL 1 at least), since it requires two depth buffers and there is no way to do that, as far as I know, without WebGL2 or some extension like EXT_frag_depth which, sadly only has a 22% availability according to WebGL Stats.

Luckly, there is a method which allows us to implement CSG operations without the use of two depth buffers. In fact, it’s the method used by the popular OpenCSG library, the SCS CSG Rendering Algorithm.

The SCS algorithm

The slightly modified SCS algorithm utilized in the OpenCSG library utilizes a numeric ID encoded in the alpha channel instead of a second depth buffer, to transfer the depth information used to create the final depth buffer output.

Basically what we do is assign each surface an integer ID; calculate the visibility of each surface at each pixel utilizing the stencil buffer and depth testing, and store the ID of the visible surface at a given pixel in the alpha channel; and, at the end, we draw each surface again (the front of A and backs of all the P₁, P₂,…, Pₙ), but only where the alpha value corresponds to that surface’s ID.

The pseudo-code is:

begin renderSCSSubtract(A, P₁, P₂,..., Pₙ) 
do 
    draw front of A to Z buffer
    stencilRef = 0
    id = 1 
    for each P in P₁, P₂,..., Pₙ
        stencilRef++
        id++
        for all front fragments of P
            if Zₚ < Z
                stencil = stencilRef
        
        for all back fragments of P
            if stencil == stencilRef and Zₚ > Z
                Z = Zₚ
    for all back fragments of A
        if Zₐ < Z
            alpha = 0
    
    id = 1
    for all front fragments of A
        if alpha == id
            draw fragment
    for each P in P₁, P₂,..., Pₙ
        id++
        for all back fragments of P
            if alpha == id
                draw fragment

This can be implemented on webgl by using to framebuffers, one for the passes where we store the alpha channel IDs, and the other for the rendering passes where we read the alpha channel IDs.

Bellow a schematic of the alpha values for a scene where a sphere is subtracted from a cuboid solid.

You can see the demo that I wrote using threejs running and it’s code bellow. We have a plane, three moving spheres that are subtracted to it, and two other spheres that just sit there. I warn you that it’s quite messy and un-optimized still : )

With this I also found out that threejs is maybe not the best tool to use if you need fine-tuned access to the webgl state and other low-level stuff… It’s not very easy for instance to render a single mesh that is inside a given scene.

Originally published at www.danielfortes.com.