Skip to content

SolidField.kt

src/jvmMain/kotlin/afield/lang/solidsl/SolidField.kt · 521 lines

@file:afield.runtime.completion.CompletionCategory("Graphics")

package afield.lang.solidsl

import afield.geometry.spatial.AxisAlignedBoundingBox3D
import afield.geometry.mesh.ScalarField3D
import afield.geometry.mesh.TriMesh
import afield.math.linalg.Vec3
import afield.geometry.mesh.marchingCubes
import kotlin.math.abs
import kotlin.math.cos
import kotlin.math.hypot
import kotlin.math.max
import kotlin.math.min
import kotlin.math.sin
import kotlin.math.sqrt

Lowering (a): a SolidExpr as a signed distance field, so everything mesh_sdf.kt, marchingCubes and Solid.levelSetOf already do keeps working unchanged.

val mesh = (cuboid(2, 2, 1) - cylinder(3, 0.3)).march(resolution = 96)

This lowering always succeeds

Unlike exactSolid, this lowering always succeeds. Every node in the algebra has a field form — that is where the algebra came from. What it does not always have is an exact distance function, and the difference matters to a ray marcher (which steps by the field's value and overshoots if the value is an overestimate) even though it does not matter to a marching cubes (which only reads signs). fieldNotes enumerates the places where the field is sign-correct but not metric-correct, so the gap is a fact rather than a surprise.

It is thread-safe, where the sdf… family is not

mesh_sdf.kt is explicit that a ScalarField3D "must read the vector it is handed and not write to it", and its own combinators capture a single scratch Vec3 to transform into. That makes them fast and single-threaded.

This lowering does not do that. Internally it builds a tree of Field3 — a fun interface over three primitive Doubles, so there is no boxing and nothing to alias — and only wraps a Vec3 at the very top, in toScalarField. So the field is re-entrant and safe to call from any thread.

fun interface Field3

A scalar field over three primitive doubles.

A fun interface rather than (Double, Double, Double) -> Double because the latter is Function3<Double, Double, Double, Double> on the JVM and boxes all four. At the tens of millions of evaluations a convergence sweep does, that is the difference between seconds and minutes.

fun at(x: Double, y: Double, z: Double): Double

fun interface Field2

A scalar field over two primitive doubles — Field3's 2D counterpart, for Profile.

fun at(x: Double, y: Double): Double

fun SolidExpr.toScalarField(): ScalarField3D

This shape as a ScalarField3D, negative inside — the convention sdfSphere and friends use, so this composes straight into sdfUnion, marchingCubes and Solid.levelSetOf.

fun SolidExpr.toScalarField(): ScalarField3D {
    val f = toField3()
    return { p -> f.at(p.x.toDouble(), p.y.toDouble(), p.z.toDouble()).toFloat() }
}

fun SolidExpr.toLevelSetField(): Field3

This shape's field in the sign convention Manifold's levelSet wants — positive inside — and over primitive doubles, so no Vec3 is ever constructed.

Solid.levelSetOf exists to flip the sign for a ScalarField3D; this one is already flipped, so pass it straight to Solid.levelSet(bounds, edge, field = expr.toLevelSetField()::at).

fun SolidExpr.toLevelSetField(): Field3 {
    val f = toField3()
    return Field3 { x, y, z -> -f.at(x, y, z) }
}

fun SolidExpr.march

marchingCubes on toScalarField, with the shape's own bounds as the window.

fun SolidExpr.march(
    resolution: Int = 64,
    bounds: AxisAlignedBoundingBox3D? = null,
    margin: Double = 0.0,
): TriMesh {
    val window = bounds ?: this.bounds()?.expandedBy(margin)
        ?: error(
            "this shape is unbounded (it contains a Gyroid, or a Union with one) so there is no " +
                "window to march — intersect it with something bounded, or pass `bounds` explicitly",
        )
    return marchingCubes(toScalarField(), window, resolution)
}

fun SolidExpr.fieldNotes(): List<String>

Every place in this expression where the field lowering is sign-correct but not a true distance function, in the order they appear.

Marching cubes only reads signs, so none of these affect march beyond the accuracy of its linear crossing interpolation. A ray marcher steps by the field's value, so a note here is a place where a toGlsl preview needs a step multiplier below 1. Empty is the good case and is common.

body — 76 lines, from line 106
fun SolidExpr.fieldNotes(): List<String> {
    val out = mutableListOf<String>()
    fun visit(e: SolidExpr) {
        when (e) {
            is SolidExpr.Sphere, is SolidExpr.Cuboid, is SolidExpr.Cylinder, SolidExpr.Empty -> {}
            is SolidExpr.Gyroid ->
                out += "Gyroid is a trigonometric field, not a distance function; its gradient is not unit length"
            is SolidExpr.Extrude -> {
                visitProfile(e.profile, out)
                if (e.twistDegrees != 0.0) out += "Extrude(twistDegrees=${e.twistDegrees}) shears space, so the field over-estimates distance near the axis"
                if (e.scaleTop != 1.0) out += "Extrude(scaleTop=${e.scaleTop}) tapers space, so the field is only sign-correct"
            }
            is SolidExpr.Revolve -> {
                visitProfile(e.profile, out)
                if (e.degrees != 360.0) out += "Revolve(degrees=${e.degrees}) is cut by two half-spaces, exact only away from their intersection"
            }
            is SolidExpr.Translate -> visit(e.child)
            is SolidExpr.Rotate -> visit(e.child)
            is SolidExpr.Mirror -> visit(e.child)
            is SolidExpr.Scale -> {
                if (e.x != e.y || e.y != e.z) out += "Scale(${e.x}, ${e.y}, ${e.z}) is non-uniform; distances are scaled by the smallest axis, so the field under-estimates"
                visit(e.child)
            }
            is SolidExpr.Round -> visit(e.child)
            is SolidExpr.Shell -> visit(e.child)
            is SolidExpr.Union -> e.children.forEach(::visit)
            is SolidExpr.Intersect -> {
                out += "Intersect is a pointwise max, which over-estimates the distance outside a concave corner"
                e.children.forEach(::visit)
            }
            is SolidExpr.Difference -> {
                if (e.children.size > 1) out += "Difference is a pointwise max, which over-estimates the distance outside the cut"
                e.children.forEach(::visit)
            }
            is SolidExpr.SmoothUnion -> { visit(e.a); visit(e.b) }
            is SolidExpr.SmoothDifference -> {
                out += "SmoothDifference is built on a smooth max, which over-estimates outside the cut"
                visit(e.a); visit(e.b)
            }
        }
    }
    visit(this)
    return out
}

private fun visitProfile(p: Profile, out: MutableList<String>) {
    when (p) {
        is Profile.Circle, is Profile.Rect, Profile.Empty -> {}
        is Profile.Polygon -> {}
        is Profile.Offset -> {
            // `sdf - delta` is the exact offset only where `sdf` is exact, and a boolean of profiles
            // is not exact on the side the max was taken on.
            val inner = mutableListOf<String>()
            visitProfile(p.child, inner)
            if (inner.isNotEmpty()) {
                out += "Offset(${p.delta}) of a profile whose own field is inexact inherits that inexactness"
            }
            out += inner
        }
        is Profile.Translate -> visitProfile(p.child, out)
        is Profile.Rotate -> visitProfile(p.child, out)
        is Profile.Scale -> {
            if (p.x != p.y) out += "Profile.Scale(${p.x}, ${p.y}) is non-uniform, so the 2D field under-estimates"
            visitProfile(p.child, out)
        }
        is Profile.Union -> p.children.forEach { visitProfile(it, out) }
        is Profile.Intersect -> {
            out += "Profile.Intersect is a pointwise max, exact inside and an over-estimate outside"
            p.children.forEach { visitProfile(it, out) }
        }
        is Profile.Difference -> {
            if (p.children.size > 1) out += "Profile.Difference is a pointwise max, exact inside and an over-estimate outside"
            p.children.forEach { visitProfile(it, out) }
        }
    }
}

The lowering itself

How far outside everything SolidExpr.Empty reads. Finite, so a min with it never yields NaN.

private const val FAR = 1e18

fun SolidExpr.toField3(): Field3

This shape as a Field3, negative inside. The compiled form both other entry points share.

body — 170 lines, from line 191
fun SolidExpr.toField3(): Field3 = when (this) {

    is SolidExpr.Sphere -> {
        val r = radius
        Field3 { x, y, z -> sqrt(x * x + y * y + z * z) - r }
    }

    is SolidExpr.Cuboid -> {
        val hx = x / 2; val hy = y / 2; val hz = z / 2
        Field3 { px, py, pz -> sdBox3(px, py, pz, hx, hy, hz) }
    }

    // One code path for cylinder, cone and frustum. iq's capped cone reduces *exactly* to the
    // cylinder when the two radii agree — the `cb` term collapses to (r - |xy|, 0) — so there is no
    // second implementation to keep in step with this one.
    is SolidExpr.Cylinder -> {
        val h = abs(height) / 2; val r1 = radiusLow; val r2 = radiusHigh
        Field3 { px, py, pz -> sdCappedConeZ(px, py, pz, h, r1, r2) }
    }

    is SolidExpr.Extrude -> {
        val p2 = profile.toField2()
        val h = height
        val twist = Math.toRadians(twistDegrees)
        val taper = scaleTop
        Field3 { px, py, pz ->
            val u = (pz / h).coerceIn(0.0, 1.0)
            val s = 1.0 + (taper - 1.0) * u
            // Undo the sweep: the profile at height u has been turned by `twist * u` and scaled by
            // `s`, so the point is turned back and divided before the profile is asked about it.
            val a = -twist * u
            val ca = cos(a); val sa = sin(a)
            val qx = (ca * px - sa * py) / s
            val qy = (sa * px + ca * py) / s
            // Times `s` to keep the value a distance in the *unscaled* frame rather than the
            // profile's own; without it a tapered extrusion's field is wrong by the taper.
            val d2 = p2.at(qx, qy) * s
            val dz = max(-pz, pz - h)
            min(max(d2, dz), 0.0) + hypot(max(d2, 0.0), max(dz, 0.0))
        }
    }

    // Revolution is about **Z**, with the profile's x becoming the radius in the XY plane and the
    // profile's y becoming z. That is measured, not read: `Section.revolved`'s own KDoc says "about
    // the Y axis", and `SolidSLConventionProbe` shows a 0.6-square offset to x = 1.2 revolving to
    // bounds ((-1.5, -1.5, -0.3), (1.5, 1.5, 0.3)) — a ring in the XY plane, of half-thickness 0.3
    // in z. Point-membership against `Solid.contains` then agrees on 100% of samples, which it does
    // not for any other axis assignment.
    is SolidExpr.Revolve -> {
        val p2 = profile.toField2()
        val sweep = degrees
        if (sweep >= 360.0) {
            Field3 { px, py, pz -> p2.at(hypot(px, py), pz) }
        } else {
            // A partial revolve is the full one cut by a wedge. Manifold sweeps counter-clockwise
            // from +X, so the kept region is `0 <= atan2(y, x) <= sweep`: the intersection of two
            // half-planes while the wedge is convex, and their *union* once it is reflex.
            val a = Math.toRadians(sweep)
            val sa = sin(a); val ca = cos(a)
            val reflex = sweep > 180.0
            Field3 { px, py, pz ->
                val body = p2.at(hypot(px, py), pz)
                // Inward normals (0, 1) and (sin a, -cos a); a half-space's field is -(n . p).
                val d0 = -py
                val d1 = -(sa * px - ca * py)
                val wedge = if (reflex) min(d0, d1) else max(d0, d1)
                max(body, wedge)
            }
        }
    }

    is SolidExpr.Gyroid -> {
        val s = scale; val t = thickness
        Field3 { x, y, z ->
            val gx = x * s; val gy = y * s; val gz = z * s
            abs(sin(gx) * cos(gy) + sin(gy) * cos(gz) + sin(gz) * cos(gx)) - t
        }
    }

    SolidExpr.Empty -> Field3 { _, _, _ -> FAR }

    is SolidExpr.Translate -> {
        val f = child.toField3(); val tx = x; val ty = y; val tz = z
        Field3 { px, py, pz -> f.at(px - tx, py - ty, pz - tz) }
    }

    is SolidExpr.Rotate -> {
        val f = child.toField3()
        // Evaluating the child at R⁻¹p rotates the *shape* by R. For a rotation the inverse is the
        // transpose, and `eulerMatrix` is the single place the X-then-Y-then-Z order is written down.
        val m = transpose3(eulerMatrix(x, y, z))
        Field3 { px, py, pz ->
            f.at(
                m[0] * px + m[1] * py + m[2] * pz,
                m[3] * px + m[4] * py + m[5] * pz,
                m[6] * px + m[7] * py + m[8] * pz,
            )
        }
    }

    is SolidExpr.Scale -> {
        val f = child.toField3()
        require(abs(x) > 1e-12 && abs(y) > 1e-12 && abs(z) > 1e-12) { "a scale factor must not be zero, got ($x, $y, $z)" }
        val sx = x; val sy = y; val sz = z
        // The smallest axis, so the result is a conservative *under*-estimate of distance and a ray
        // marcher using it cannot overshoot. Exact when the scale is uniform.
        val k = min(abs(sx), min(abs(sy), abs(sz)))
        Field3 { px, py, pz -> f.at(px / sx, py / sy, pz / sz) * k }
    }

    is SolidExpr.Mirror -> {
        val f = child.toField3()
        val (nx, ny, nz) = normalize3(x, y, z)
        // A reflection is its own inverse, so the same expression serves both directions.
        Field3 { px, py, pz ->
            val d = 2.0 * (px * nx + py * ny + pz * nz)
            f.at(px - d * nx, py - d * ny, pz - d * nz)
        }
    }

    is SolidExpr.Round -> {
        val f = child.toField3(); val r = radius
        Field3 { px, py, pz -> f.at(px, py, pz) - r }
    }

    is SolidExpr.Shell -> {
        val f = child.toField3(); val t = thickness
        Field3 { px, py, pz -> abs(f.at(px, py, pz)) - t }
    }

    is SolidExpr.Union -> {
        val fs = children.map { it.toField3() }.toTypedArray()
        if (fs.isEmpty()) Field3 { _, _, _ -> FAR }
        else Field3 { px, py, pz ->
            var v = FAR
            for (f in fs) v = min(v, f.at(px, py, pz))
            v
        }
    }

    is SolidExpr.Intersect -> {
        val fs = children.map { it.toField3() }.toTypedArray()
        if (fs.isEmpty()) Field3 { _, _, _ -> FAR }
        else Field3 { px, py, pz ->
            var v = -FAR
            for (f in fs) v = max(v, f.at(px, py, pz))
            v
        }
    }

    is SolidExpr.Difference -> {
        val fs = children.map { it.toField3() }.toTypedArray()
        if (fs.isEmpty()) Field3 { _, _, _ -> FAR }
        else Field3 { px, py, pz ->
            var v = fs[0].at(px, py, pz)
            for (i in 1 until fs.size) v = max(v, -fs[i].at(px, py, pz))
            v
        }
    }

    is SolidExpr.SmoothUnion -> {
        val fa = a.toField3(); val fb = b.toField3(); val kk = max(k, 1e-9)
        Field3 { px, py, pz -> smoothMin(fa.at(px, py, pz), fb.at(px, py, pz), kk) }
    }

    is SolidExpr.SmoothDifference -> {
        val fa = a.toField3(); val fb = b.toField3(); val kk = max(k, 1e-9)
        Field3 { px, py, pz -> smoothMax(fa.at(px, py, pz), -fb.at(px, py, pz), kk) }
    }
}

fun Profile.toField2(): Field2

This region as a Field2, negative inside.

body — 81 lines, from line 363
fun Profile.toField2(): Field2 = when (this) {

    is Profile.Circle -> {
        val r = radius
        Field2 { x, y -> hypot(x, y) - r }
    }

    is Profile.Rect -> {
        val hx = x / 2; val hy = y / 2
        Field2 { px, py -> sdBox2(px, py, hx, hy) }
    }

    is Profile.Polygon -> {
        if (points.size < 3) Field2 { _, _ -> FAR } else {
            val n = points.size
            val xs = DoubleArray(n) { points[it].x }
            val ys = DoubleArray(n) { points[it].y }
            Field2 { px, py -> sdPolygon(xs, ys, px, py) }
        }
    }

    // `Section.offset(d, JoinType.ROUND)` is the Minkowski sum with a disc of radius d, and for a
    // true distance field that is exactly `sdf - d`. This is the one place in the package where the
    // two lowerings agree for a *reason* rather than to a tolerance.
    is Profile.Offset -> {
        val f = child.toField2(); val d = delta
        Field2 { px, py -> f.at(px, py) - d }
    }

    is Profile.Translate -> {
        val f = child.toField2(); val tx = x; val ty = y
        Field2 { px, py -> f.at(px - tx, py - ty) }
    }

    is Profile.Rotate -> {
        val f = child.toField2()
        val a = Math.toRadians(-degrees)
        val c = cos(a); val s = sin(a)
        Field2 { px, py -> f.at(c * px - s * py, s * px + c * py) }
    }

    is Profile.Scale -> {
        val f = child.toField2()
        require(abs(x) > 1e-12 && abs(y) > 1e-12) { "a profile scale must not be zero, got ($x, $y)" }
        val sx = x; val sy = y
        val k = min(abs(sx), abs(sy))
        Field2 { px, py -> f.at(px / sx, py / sy) * k }
    }

    is Profile.Union -> {
        val fs = children.map { it.toField2() }.toTypedArray()
        if (fs.isEmpty()) Field2 { _, _ -> FAR }
        else Field2 { px, py ->
            var v = FAR
            for (f in fs) v = min(v, f.at(px, py))
            v
        }
    }

    is Profile.Intersect -> {
        val fs = children.map { it.toField2() }.toTypedArray()
        if (fs.isEmpty()) Field2 { _, _ -> FAR }
        else Field2 { px, py ->
            var v = -FAR
            for (f in fs) v = max(v, f.at(px, py))
            v
        }
    }

    is Profile.Difference -> {
        val fs = children.map { it.toField2() }.toTypedArray()
        if (fs.isEmpty()) Field2 { _, _ -> FAR }
        else Field2 { px, py ->
            var v = fs[0].at(px, py)
            for (i in 1 until fs.size) v = max(v, -fs[i].at(px, py))
            v
        }
    }

    Profile.Empty -> Field2 { _, _ -> FAR }
}

The closed forms

internal fun sdBox3(px: Double, py: Double, pz: Double, hx: Double, hy: Double, hz: Double): Double

Exact signed distance to an origin-centred box of half-extents (hx, hy, hz).

internal fun sdBox3(px: Double, py: Double, pz: Double, hx: Double, hy: Double, hz: Double): Double {
    val qx = abs(px) - hx; val qy = abs(py) - hy; val qz = abs(pz) - hz
    val ox = max(qx, 0.0); val oy = max(qy, 0.0); val oz = max(qz, 0.0)
    return sqrt(ox * ox + oy * oy + oz * oz) + min(max(qx, max(qy, qz)), 0.0)
}

internal fun sdBox2(px: Double, py: Double, hx: Double, hy: Double): Double

Exact signed distance to an origin-centred rectangle of half-extents (hx, hy).

internal fun sdBox2(px: Double, py: Double, hx: Double, hy: Double): Double {
    val qx = abs(px) - hx; val qy = abs(py) - hy
    return hypot(max(qx, 0.0), max(qy, 0.0)) + min(max(qx, qy), 0.0)
}

internal fun sdCappedConeZ(px: Double, py: Double, pz: Double, h: Double, r1: Double, r2: Double): Double

Exact signed distance to a capped cone along Z, half-height h, radius r1 at z = -h and r2 at z = +h — Inigo Quilez's sdCappedCone, with the axis swapped from Y to Z.

internal fun sdCappedConeZ(px: Double, py: Double, pz: Double, h: Double, r1: Double, r2: Double): Double {
    val qx = hypot(px, py)
    val qy = pz
    val k1x = r2; val k1y = h
    val k2x = r2 - r1; val k2y = 2.0 * h
    val cax = qx - min(qx, if (qy < 0.0) r1 else r2)
    val cay = abs(qy) - h
    val k2dot = k2x * k2x + k2y * k2y
    val t = if (k2dot < 1e-30) 0.0 else (((k1x - qx) * k2x + (k1y - qy) * k2y) / k2dot).coerceIn(0.0, 1.0)
    val cbx = qx - k1x + k2x * t
    val cby = qy - k1y + k2y * t
    val s = if (cbx < 0.0 && cay < 0.0) -1.0 else 1.0
    return s * sqrt(min(cax * cax + cay * cay, cbx * cbx + cby * cby))
}

internal fun sdPolygon(xs: DoubleArray, ys: DoubleArray, px: Double, py: Double): Double

Exact signed distance to a closed simple polygon — Inigo Quilez's sdPolygon.

The sign comes from a crossing-parity test, which is winding-independent: a clockwise polygon and its reversal give the same field. That is not true of the exact lowering, where Clipper decides holes by winding, which is why Profile.Polygon is normalised to counter-clockwise on that side rather than here.

internal fun sdPolygon(xs: DoubleArray, ys: DoubleArray, px: Double, py: Double): Double {
    val n = xs.size
    var d = (px - xs[0]) * (px - xs[0]) + (py - ys[0]) * (py - ys[0])
    var s = 1.0
    var j = n - 1
    for (i in 0 until n) {
        val ex = xs[j] - xs[i]; val ey = ys[j] - ys[i]
        val wx = px - xs[i]; val wy = py - ys[i]
        val e2 = ex * ex + ey * ey
        val t = if (e2 < 1e-30) 0.0 else ((wx * ex + wy * ey) / e2).coerceIn(0.0, 1.0)
        val bx = wx - ex * t; val by = wy - ey * t
        d = min(d, bx * bx + by * by)
        val c1 = py >= ys[i]
        val c2 = py < ys[j]
        val c3 = ex * wy > ey * wx
        if ((c1 && c2 && c3) || (!c1 && !c2 && !c3)) s = -s
        j = i
    }
    return s * sqrt(d)
}

internal fun smoothMin(a: Double, b: Double, k: Double): Double

The polynomial smooth minimum — sdfSmoothUnion's, in Double.

internal fun smoothMin(a: Double, b: Double, k: Double): Double {
    val h = (0.5 + 0.5 * (b - a) / k).coerceIn(0.0, 1.0)
    return b + (a - b) * h - k * h * (1.0 - h)
}

internal fun smoothMax(a: Double, b: Double, k: Double): Double

The polynomial smooth maximum — sdfSmoothIntersect's, in Double.

internal fun smoothMax(a: Double, b: Double, k: Double): Double {
    val h = (0.5 - 0.5 * (b - a) / k).coerceIn(0.0, 1.0)
    return b + (a - b) * h + k * h * (1.0 - h)
}