feat(geom-sdf): major update: combinators, modifiers, shape support

- support more shapes (and conversions) in asSDF() - update/extend SDFAttribs - add new SDF combinators (chamfer, round, step) - add higher order combinators defOp(), defParamOp() - add support for combinator params to be spatial - update asSDF() to support more shape types and auto-convert to poly/line - add domain modifiers, update `sample2d()` to support domain mods - update various distance functions (incl. uniform arg order, minimize allocs) - add docstrings
thi-ng · Jun 23, 2022 · 4ffbc86 · 4ffbc86
1 parent 303128b
commit 4ffbc86
Show file tree

Hide file tree

Showing 12 changed files with 688 additions and 239 deletions.
diff --git a/packages/geom-sdf/package.json b/packages/geom-sdf/package.json
@@ -41,6 +41,8 @@
         "@thi.ng/geom": "^3.3.0",
         "@thi.ng/geom-api": "^3.2.0",
         "@thi.ng/geom-isoline": "^2.1.14",
+        "@thi.ng/geom-poly-utils": "^2.2.7",
+        "@thi.ng/geom-resample": "^2.1.15",
         "@thi.ng/math": "^5.3.3",
         "@thi.ng/transducers": "^8.3.5",
         "@thi.ng/vectors": "^7.5.6"
@@ -89,6 +91,9 @@
         "./api": {
             "default": "./api.js"
         },
+        "./as-polygons": {
+            "default": "./as-polygons.js"
+        },
         "./as-sdf": {
             "default": "./as-sdf.js"
         },
@@ -98,6 +103,9 @@
         "./dist": {
             "default": "./dist.js"
         },
+        "./domain": {
+            "default": "./domain.js"
+        },
         "./ops": {
             "default": "./ops.js"
         },
@@ -110,6 +118,12 @@
     },
     "thi.ng": {
         "parent": "@thi.ng/geom",
+        "related": [
+            "distance-transform",
+            "geom-isoline",
+            "pixel",
+            "shader-ast-stdlib"
+        ],
         "status": "alpha",
         "year": 2022
     }

diff --git a/packages/geom-sdf/src/api.ts b/packages/geom-sdf/src/api.ts
@@ -4,7 +4,7 @@ import type { ReadonlyVec } from "@thi.ng/vectors";
 /**
  * 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 ∞.
+ * used for bounding hierarchies). `minD` defaults to positive ∞.
  */
 export type SDFn = (p: ReadonlyVec, minD?: number) => number;
 
@@ -23,12 +23,22 @@ export type FieldCoeff<T = number> = Fn<ReadonlyVec, T>;
  */
 export interface SDFAttribs {
     /**
-     * If true (default: false), only the absolute (unsigned) distance will be
-     * used.
+     * If true, only the absolute (unsigned) distance will be used. For closed
+     * shapes the default is false, for lines/curves the default is true (since
+     * there's no real interior).
      *
      * @defaultValue false
      */
     abs: boolean;
+    /**
+     * Advanced usage only. If true (default: false), the SDF will be wrapped
+     * with a bounding box pre-check.
+     *
+     * @remarks
+     * Currently only supported by some shape types and only usable in some
+     * circumstances, hence disabled by default.
+     */
+    bounds: boolean;
     /**
      * Only used for `groups()`. Specifies the type of operation used for
      * combining child SDFs. If {@link SDFAttribs.smooth} is != zero, smoothed
@@ -45,13 +55,13 @@ export interface SDFAttribs {
      */
     flip: boolean;
     /**
-     * Subtracts given value from actual distance, thereby creating a rounded
+     * Subtracts given value from actual distance, thereby creating an
      * 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;
+    offset: number | FieldCoeff;
     /**
      * Coefficient for smooth union, intersection, difference ops (only
      * supported for `group()` shapes). If given as function, it will be called
@@ -61,4 +71,35 @@ export interface SDFAttribs {
      * @defaultValue 0
      */
     smooth: number | FieldCoeff;
+    /**
+     * Radius coefficient for chamfered 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
+     */
+    chamfer: number | FieldCoeff;
+    /**
+     * Radius coefficient for rounded 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
+     */
+    round: number | FieldCoeff;
+    /**
+     * Coefficient tuple of `[radius, num]` used for stepped 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).
+     */
+    steps?: [number, number] | FieldCoeff<[number, number]>;
+    /**
+     * If given, this value is used to control the number of samples used for
+     * converting the original geometry to a polygon or polyline. See
+     * {@link asSDF} for more details.
+     */
+    samples?: number;
 }
diff --git a/packages/geom-sdf/src/as-polygons.ts b/packages/geom-sdf/src/as-polygons.ts
@@ -0,0 +1,59 @@
+import type { NumericArray } from "@thi.ng/api";
+import { isFunction } from "@thi.ng/checks/is-function";
+import type { Polygon } from "@thi.ng/geom";
+import type { AABBLike } from "@thi.ng/geom-api";
+import { isolines, setBorder } from "@thi.ng/geom-isoline";
+import { simplify } from "@thi.ng/geom-resample/simplify";
+import { polygon } from "@thi.ng/geom/polygon";
+import { comp } from "@thi.ng/transducers/comp";
+import { map } from "@thi.ng/transducers/map";
+import { mapcat } from "@thi.ng/transducers/mapcat";
+import { push } from "@thi.ng/transducers/push";
+import { transduce } from "@thi.ng/transducers/transduce";
+import type { ReadonlyVec } from "@thi.ng/vectors";
+import { add2 } from "@thi.ng/vectors/add";
+import { div2 } from "@thi.ng/vectors/div";
+import type { SDFn } from "./api.js";
+import { sample2d } from "./sample.js";
+
+/**
+ * Extract contour polygons from given SDF at specified `distances`. The SDF can
+ * be either given as distance function or as pre-discretized image (e.g. as
+ * result of {@link sample2d}). The SDF will be sampled in the given bounding
+ * rect and resolution (if SDF was given as image, resolution MUST be the
+ * same!).
+ *
+ * @remarks
+ * If `distances` are not given, only the original boundary (i.e. distance=0)
+ * will be extracted. By default all resulting polygons will be simplified using
+ * Douglas-Peucker with a threshold of `eps`. By default this will only remove
+ * co-linear vertices, but more agressive settings are possible/recommended.
+ *
+ * @param sdf
+ * @param bounds
+ * @param res
+ * @param distances
+ * @param eps
+ */
+export const asPolygons = (
+    sdf: NumericArray | SDFn,
+    bounds: AABBLike,
+    res: ReadonlyVec,
+    distances: Iterable<number> = [0],
+    eps = 1e-6
+) => {
+    const $sdf = isFunction(sdf) ? sample2d(sdf, bounds, res) : sdf;
+    const { pos, size } = bounds;
+    const [resX, resY] = res;
+    setBorder($sdf, resX, resY, 1e6);
+    const scale = div2([], size, [resX - 1, resY - 1]);
+    return transduce(
+        comp(
+            mapcat((iso) => isolines($sdf, resX, resY, iso, scale)),
+            map((pts) => pts.map((p) => add2(null, p, pos))),
+            map((pts) => polygon(eps >= 0 ? simplify(pts, eps, true) : pts))
+        ),
+        push<Polygon>(),
+        distances
+    );
+};
diff --git a/packages/geom-sdf/src/as-sdf.ts b/packages/geom-sdf/src/as-sdf.ts
@@ -1,28 +1,43 @@
+import type { Fn, Fn2 } from "@thi.ng/api";
 import type { MultiFn1 } from "@thi.ng/defmulti";
 import { DEFAULT, defmulti } from "@thi.ng/defmulti/defmulti";
+import { assert } from "@thi.ng/errors/assert";
 import { unsupported } from "@thi.ng/errors/unsupported";
 import type {
     Circle,
     Ellipse,
     Group,
     Line,
+    Path,
     Points,
     Polygon,
     Polyline,
     Quadratic,
     Rect,
 } from "@thi.ng/geom";
 import type { Attribs, IShape } from "@thi.ng/geom-api";
+import { asPolygon } from "@thi.ng/geom/as-polygon";
+import { asPolyline } from "@thi.ng/geom/as-polyline";
+import { simplify } from "@thi.ng/geom/simplify";
 import { __dispatch } from "@thi.ng/geom/internal/dispatch";
 import { add2 } from "@thi.ng/vectors/add";
 import { mulN2 } from "@thi.ng/vectors/muln";
-import type { SDFAttribs, SDFn } from "./api.js";
+import type { FieldCoeff, SDFAttribs, SDFn } from "./api.js";
 import {
-    difference,
-    intersection,
-    smoothDifference,
-    smoothIntersection,
+    chamferDiff,
+    chamferIsec,
+    chamferUnion,
+    diff,
+    isec,
+    roundDiff,
+    roundIsec,
+    roundUnion,
+    smoothDiff,
+    smoothIsec,
     smoothUnion,
+    stepDiff,
+    stepIsec,
+    stepUnion,
     union,
 } from "./ops.js";
 import {
@@ -38,6 +53,14 @@ import {
     withSDFAttribs,
 } from "./shapes.js";
 
+/** @internal */
+interface ParametricOps {
+    chamfer: Fn2<number | FieldCoeff, SDFn[], SDFn>;
+    round: Fn2<number | FieldCoeff, SDFn[], SDFn>;
+    smooth: Fn2<number | FieldCoeff, SDFn[], SDFn>;
+    steps: Fn2<[number, number] | FieldCoeff<[number, number]>, SDFn[], SDFn>;
+}
+
 /**
  * Takes an {@link @thi.ng/geom-api#IShape} instance (possibly a tree, e.g. via
  * {@link @thi.ng/geom#group}) and converts it into a {@link SDFn}.
@@ -46,14 +69,22 @@ import {
  * Currently supported shape types:
  *
  * - circle
+ * - cubic (auto-converted to polyline)
  * - ellipse
  * - group
  * - line
+ * - path (auto-converted to polygon/polyline)
  * - points
  * - polygon
  * - polyline
  * - quadratic bezier
  * - rect
+ *
+ * For shapes which need to be converted to polygons/polylines, the
+ * {@link SDFAttribs.samples} attribute can be used to control the resulting
+ * number of vertices. If not specified {@link @thi.ng/geom-api#DEFAULT_SAMPLES}
+ * will be used (which can be globally set via
+ * {@link @thi.ng/geom-api#setDefaultSamples}).
  */
 export const asSDF: MultiFn1<IShape, SDFn> = defmulti<any, SDFn>(
     __dispatch,
@@ -66,46 +97,68 @@ export const asSDF: MultiFn1<IShape, SDFn> = defmulti<any, SDFn>(
 
         circle: ($: Circle) => circle2($.pos, $.r, __sdfAttribs($.attribs)),
 
+        cubic: ($: IShape) =>
+            asSDF(
+                simplify(
+                    asPolyline($, (__sdfAttribs($.attribs) || {}).samples),
+                    0
+                )
+            ),
+
         ellipse: ($: Ellipse) => ellipse2($.pos, $.r, __sdfAttribs($.attribs)),
 
         group: ($: Group) => {
             const { attribs, children } = $;
-            const $attribs = { ...DEFAULT_ATTRIBS, ...__sdfAttribs(attribs) };
+            const attr = { ...DEFAULT_ATTRIBS, ...__sdfAttribs(attribs) };
+            __validateAttribs(attr);
             const $children = children.map(asSDF);
             let res: SDFn;
             if ($children.length > 1) {
-                switch ($attribs.combine) {
+                switch (attr.combine) {
                     case "diff":
-                        res =
-                            $attribs.smooth !== 0
-                                ? smoothDifference($attribs.smooth, $children)
-                                : difference($children);
+                        res = __selectCombineOp(attr, $children, diff, {
+                            chamfer: chamferDiff,
+                            round: roundDiff,
+                            smooth: smoothDiff,
+                            steps: stepDiff,
+                        });
                         break;
                     case "isec":
-                        res =
-                            $attribs.smooth !== 0
-                                ? smoothIntersection($attribs.smooth, $children)
-                                : intersection($children);
+                        res = __selectCombineOp(attr, $children, isec, {
+                            chamfer: chamferIsec,
+                            round: roundIsec,
+                            smooth: smoothIsec,
+                            steps: stepIsec,
+                        });
                         break;
                     case "union":
                     default: {
-                        res =
-                            $attribs.smooth !== 0
-                                ? smoothUnion($attribs.smooth, $children)
-                                : union($children);
+                        res = __selectCombineOp(attr, $children, union, {
+                            chamfer: chamferUnion,
+                            round: roundUnion,
+                            smooth: smoothUnion,
+                            steps: stepUnion,
+                        });
                     }
                 }
             } else if ($children.length) {
                 res = $children[0];
             } else {
-                return $attribs.flip ? () => -Infinity : () => Infinity;
+                return attr.flip ? () => -Infinity : () => Infinity;
             }
-            return withSDFAttribs(res, $attribs);
+            return withSDFAttribs(res, attr);
         },
 
         line: ({ points: [a, b], attribs }: Line) =>
             line2(a, b, __sdfAttribs(attribs)),
 
+        path: ($: Path) => {
+            const n = (__sdfAttribs($.attribs) || {}).samples;
+            return asSDF(
+                simplify($.closed ? asPolygon($, n) : asPolyline($, n), 0)
+            );
+        },
+
         points: ($: Points) => points2($.points, __sdfAttribs($.attribs)),
 
         poly: ($: Polygon) => polygon2($.points, __sdfAttribs($.attribs)),
@@ -125,3 +178,25 @@ export const asSDF: MultiFn1<IShape, SDFn> = defmulti<any, SDFn>(
 /** @internal */
 const __sdfAttribs = (attribs?: Attribs): Partial<SDFAttribs> =>
     attribs ? attribs.__sdf : null;
+
+const OPS = <const>["chamfer", "round", "smooth", "steps"];
+
+const __validateAttribs = (attribs: SDFAttribs) =>
+    assert(
+        OPS.filter((x) => attribs[x]).length < 2,
+        "only 1 of these options can be used at once: chamfer, round, smooth"
+    );
+
+const __selectCombineOp = (
+    attribs: SDFAttribs,
+    children: SDFn[],
+    op: Fn<SDFn[], SDFn>,
+    paramOps: ParametricOps
+) => {
+    for (let k of OPS) {
+        if (attribs[k]) {
+            return paramOps[k](<any>attribs[k], children);
+        }
+    }
+    return op(children);
+};