September 30, 2018

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…).

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:

beginrenderGoldfeatherSubtract(A, P₁, P₂,…, Pₙ)dofor 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ₙ

beginparityClip(S, Z, isSubtracted) 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 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:

beginrenderSCSSubtract(A, P₁, P₂,..., Pₙ)dodraw 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.

written by danielfortes. tweet this.