feat(geom-sdf): add bounds pre-checks, update SDFAttribs, ops

- update `SDFn` signature, add opt. min dist param - add `withBoundingCircle/Rect()` SDF wrappers - update shape fns (points2, polygon2, polyline2) - update SDF combinators (union, isec, diff etc.) - update `asSDF()` group impl - update `SDFAttribs`, allow `round` & `smooth` opts to be field based - add docstrings
thi-ng · Jun 21, 2022 · ddf0a6e · ddf0a6e
1 parent 2f9ff9a
commit ddf0a6e
Show file tree

Hide file tree

Showing 6 changed files with 259 additions and 65 deletions.
diff --git a/packages/geom-sdf/package.json b/packages/geom-sdf/package.json
@@ -92,6 +92,9 @@
         "./as-sdf": {
             "default": "./as-sdf.js"
         },
+        "./bounds": {
+            "default": "./bounds.js"
+        },
         "./dist": {
             "default": "./dist.js"
         },

diff --git a/packages/geom-sdf/src/api.ts b/packages/geom-sdf/src/api.ts
@@ -1,14 +1,64 @@
 import type { Fn } from "@thi.ng/api";
 import type { ReadonlyVec } from "@thi.ng/vectors";
 
-export type SDFn = Fn<ReadonlyVec, number>;
+/**
+ * Signed Distance Field function. Computes distance from given point `p`,
+ * optionally taking into account an already computed `minD` min distance (e.g.
+ * used for bounds hierarchies). `minD` defaults to positive ∞.
+ */
+export type SDFn = (p: ReadonlyVec, minD?: number) => number;
 
 export type SDFCombineOp = "union" | "isec" | "diff";
 
+export type FieldCoeff<T = number> = Fn<ReadonlyVec, T>;
+
+/**
+ * Options object to customize geometry -> SDF conversions. Given as value to
+ * the special `__sdf` shape attribute.
+ *
+ * @example
+ * ```ts
+ * const sdf = asSDF(circle(100, { __sdf: { abs: true } }));
+ * ```
+ */
 export interface SDFAttribs {
+    /**
+     * If true (default: false), only the absolute (unsigned) distance will be
+     * used.
+     *
+     * @defaultValue false
+     */
+    abs: boolean;
+    /**
+     * Only used for `groups()`. Specifies the type of operation used for
+     * combining child SDFs. If {@link SDFAttribs.smooth} is != zero, smoothed
+     * versions of the operators will be used.
+     *
+     * @defaultValue "union"
+     */
     combine: SDFCombineOp;
-    smooth: number;
+    /**
+     * If true (default: false), the sign of the resulting distance will be
+     * flipped. Useful for boolean operations.
+     *
+     * @defaultValue false
+     */
     flip: boolean;
-    abs: boolean;
-    round: number;
+    /**
+     * Subtracts given value from actual distance, thereby creating a rounded
+     * offsetting effect. If given as function, it will be called with the
+     * current SDF query point and the return value will be used as param.
+     *
+     * @defaultValue 0
+     */
+    round: number | FieldCoeff;
+    /**
+     * Coefficient for smooth union, intersection, difference ops (only
+     * supported for `group()` shapes). If given as function, it will be called
+     * with the current SDF query point and the return value will be used as
+     * param. Ignored if zero (default).
+     *
+     * @defaultValue 0
+     */
+    smooth: number | FieldCoeff;
 }
diff --git a/packages/geom-sdf/src/as-sdf.ts b/packages/geom-sdf/src/as-sdf.ts
@@ -68,35 +68,30 @@ export const asSDF: MultiFn1<IShape, SDFn> = defmulti<any, SDFn>(
 
         ellipse: ($: Ellipse) => ellipse2($.pos, $.r, __sdfAttribs($.attribs)),
 
-        group: ({ attribs, children }: Group) => {
+        group: ($: Group) => {
+            const { attribs, children } = $;
             const $attribs = { ...DEFAULT_ATTRIBS, ...__sdfAttribs(attribs) };
-            const $children = <[SDFn, ...SDFn[]]>children.map(asSDF);
+            const $children = children.map(asSDF);
             let res: SDFn;
             if ($children.length > 1) {
                 switch ($attribs.combine) {
                     case "diff":
                         res =
                             $attribs.smooth !== 0
-                                ? smoothDifference(
-                                      $attribs.smooth,
-                                      ...$children
-                                  )
-                                : difference(...$children);
+                                ? smoothDifference($attribs.smooth, $children)
+                                : difference($children);
                         break;
                     case "isec":
                         res =
                             $attribs.smooth !== 0
-                                ? smoothIntersection(
-                                      $attribs.smooth,
-                                      ...$children
-                                  )
+                                ? smoothIntersection($attribs.smooth, $children)
                                 : intersection($children);
                         break;
                     case "union":
                     default: {
                         res =
                             $attribs.smooth !== 0
-                                ? smoothUnion($attribs.smooth, ...$children)
+                                ? smoothUnion($attribs.smooth, $children)
                                 : union($children);
                     }
                 }

diff --git a/packages/geom-sdf/src/bounds.ts b/packages/geom-sdf/src/bounds.ts
@@ -0,0 +1,70 @@
+import { boundingCircle, bounds2 } from "@thi.ng/geom-poly-utils/bounds";
+import type { ReadonlyVec } from "@thi.ng/vectors";
+import { addmN2 } from "@thi.ng/vectors/addmn";
+import { sub2 } from "@thi.ng/vectors/sub";
+import { submN2 } from "@thi.ng/vectors/submn";
+import type { SDFn } from "./api.js";
+import { distBox2 } from "./dist.js";
+
+/**
+ * Augments given distance function with a bounding circle pre-check. The circle
+ * can be either given as `[centroid, radius]` tuple or can be auto-computed
+ * from given array of points. When the returned function is called it first
+ * computes the distance to the bounding circle and *only* if that is less then
+ * the current (already computed) min distance (default: positive ∞), the
+ * original (wrapped) `sdf` function is called. If the distance to the bounding
+ * circle is > `minD`, the presumably more costly `sdf` is skipped and `minD`
+ * returned.
+ *
+ * @remarks
+ * Currently used for {@link polygon2}, {@link polyline2}, {@link points2}.
+ *
+ * @param sdf
+ * @param pts
+ */
+export function withBoundingCircle(sdf: SDFn, pts: ReadonlyVec[]): SDFn;
+export function withBoundingCircle(
+    sdf: SDFn,
+    centroid: ReadonlyVec,
+    r: number
+): SDFn;
+export function withBoundingCircle(sdf: SDFn, ...args: any[]): SDFn {
+    let [[cx, cy], r] =
+        args.length === 1
+            ? boundingCircle(args[0])
+            : <[ReadonlyVec, number]>args;
+    r *= r;
+    return (p, minD = Infinity) => {
+        if (minD === Infinity) return sdf(p, minD);
+        const dx = p[0] - cx;
+        const dy = p[1] - cy;
+        return dx * dx + dy * dy - r < minD * minD ? sdf(p, minD) : minD;
+    };
+}
+
+/**
+ * Similar to {@link withBoundingCircle}, but using a bounding rect (defined via
+ * `min`/`max` or computed from an array of points).
+ *
+ * @param sdf
+ * @param pts
+ */
+export function withBoundingRect(sdf: SDFn, pts: ReadonlyVec[]): SDFn;
+export function withBoundingRect(
+    sdf: SDFn,
+    min: ReadonlyVec,
+    max: ReadonlyVec
+): SDFn;
+export function withBoundingRect(sdf: SDFn, ...args: any[]): SDFn {
+    const [min, max] =
+        args.length === 1 ? bounds2(args[0]) : <[ReadonlyVec, ReadonlyVec]>args;
+    const centroid = addmN2([], min, max, 0.5);
+    const hSize = submN2([], max, min, 0.5);
+    const t = [0, 0];
+    return (p, minD = Infinity) => {
+        if (minD === Infinity) return sdf(p, minD);
+        return distBox2(sub2(t, p, centroid), hSize) < minD
+            ? sdf(p, minD)
+            : minD;
+    };
+}
diff --git a/packages/geom-sdf/src/ops.ts b/packages/geom-sdf/src/ops.ts
@@ -1,59 +1,111 @@
+import { isFunction } from "@thi.ng/checks/is-function";
 import { clamp01, mix } from "@thi.ng/math";
-import type { SDFn } from "./api.js";
+import type { FieldCoeff, SDFn } from "./api.js";
 
 export const abs =
     (sdf: SDFn): SDFn =>
-    (p) =>
-        Math.abs(sdf(p));
+    (p, minD?: number) =>
+        Math.abs(sdf(p, minD));
 
 export const flip =
     (sdf: SDFn): SDFn =>
-    (p) =>
-        -sdf(p);
+    (p, minD?: number) =>
+        -sdf(p, minD);
 
-export const round =
-    (sdf: SDFn, r: number): SDFn =>
-    (p) =>
-        sdf(p) - r;
+export const round = (sdf: SDFn, r: number | FieldCoeff): SDFn =>
+    isFunction(r)
+        ? (p, minD?: number) => sdf(p, minD) - r(p)
+        : (p, minD?: number) => sdf(p, minD) - r;
 
 export const union =
     (children: SDFn[]): SDFn =>
-    (p) =>
-        children.reduce((acc, f) => Math.min(acc, f(p)), Infinity);
+    (p, minD = Infinity) => {
+        let res = Infinity;
+        for (let i = children.length; i-- > 0; ) {
+            const d = children[i](p, minD);
+            if (d < minD) minD = d;
+            res = Math.min(res, d);
+        }
+        return res;
+    };
 
 export const intersection =
     (children: SDFn[]): SDFn =>
-    (p) =>
-        children.reduce((acc, f) => Math.max(acc, f(p)), -Infinity);
+    (p, minD = Infinity) => {
+        let res = -Infinity;
+        for (let i = children.length; i-- > 0; ) {
+            const d = children[i](p, minD);
+            if (d < minD) minD = d;
+            res = Math.max(res, d);
+        }
+        return res;
+    };
 
 export const difference =
-    (a: SDFn, ...children: SDFn[]): SDFn =>
-    (p) =>
-        children.reduce((acc, f) => Math.max(acc, -f(p)), a(p));
-
-export const smoothUnion =
-    (k: number, a: SDFn, ...children: SDFn[]): SDFn =>
-    (p) =>
-        children.reduce((acc, f) => {
-            const d = f(p);
-            const h = clamp01(0.5 + (0.5 * (d - acc)) / k);
-            return mix(d, acc, h) - k * h * (1 - h);
-        }, a(p));
-
-export const smoothIntersection =
-    (k: number, a: SDFn, ...children: SDFn[]): SDFn =>
-    (p) =>
-        children.reduce((acc, f) => {
-            const d = f(p);
-            const h = clamp01(0.5 - (0.5 * (d - acc)) / k);
-            return mix(d, acc, h) + k * h * (1 - h);
-        }, a(p));
-
-export const smoothDifference =
-    (k: number, a: SDFn, ...children: SDFn[]): SDFn =>
-    (p) =>
-        children.reduce((acc, f) => {
-            const d = f(p);
-            const h = clamp01(0.5 - (0.5 * (acc + d)) / k);
-            return mix(acc, -d, h) + k * h * (1 - h);
-        }, a(p));
+    (children: SDFn[]): SDFn =>
+    (p, minD = Infinity) => {
+        let res = children[0](p, minD);
+        if (res < minD) minD = res;
+        for (let i = 1, n = children.length; i < n; i++) {
+            const d = children[i](p, minD);
+            if (d < minD) minD = d;
+            res = Math.max(res, -d);
+        }
+        return res;
+    };
+
+export const smoothUnion = (k: number | FieldCoeff, children: SDFn[]): SDFn => {
+    const kfield = __asField(k);
+    return (p, minD = Infinity) => {
+        const $k = kfield(p);
+        let res = children[0](p, minD);
+        if (res < minD) minD = res;
+        for (let i = 1, n = children.length; i < n; i++) {
+            const d = children[i](p, minD);
+            if (d < minD) minD = d;
+            const h = clamp01(0.5 + (0.5 * (d - res)) / $k);
+            res = mix(d, res, h) - $k * h * (1 - h);
+        }
+        return res;
+    };
+};
+
+export const smoothIntersection = (
+    k: number | FieldCoeff,
+    children: SDFn[]
+): SDFn => {
+    const kfield = __asField(k);
+    return (p, minD = Infinity) => {
+        const $k = kfield(p);
+        let res = children[0](p, minD);
+        if (res < minD) minD = res;
+        for (let i = 1, n = children.length; i < n; i++) {
+            const d = children[i](p, minD);
+            if (d < minD) minD = d;
+            const h = clamp01(0.5 - (0.5 * (d - res)) / $k);
+            res = mix(d, res, h) + $k * h * (1 - h);
+        }
+        return res;
+    };
+};
+
+export const smoothDifference = (
+    k: number | FieldCoeff,
+    children: SDFn[]
+): SDFn => {
+    const kfield = __asField(k);
+    return (p, minD = Infinity) => {
+        const $k = kfield(p);
+        let res = children[0](p, minD);
+        if (res < minD) minD = res;
+        for (let i = 1, n = children.length; i < n; i++) {
+            const d = children[i](p, minD);
+            if (d < minD) minD = d;
+            const h = clamp01(0.5 - (0.5 * (res + d)) / $k);
+            res = mix(res, -d, h) + $k * h * (1 - h);
+        }
+        return res;
+    };
+};
+
+const __asField = (k: number | FieldCoeff) => (isFunction(k) ? k : () => k);