Fidget: Bibliothek zur Auswertung großer mathematischer Ausdrücke

 (mattkeeter.com)
3 Punkte von GN⁺ 2025-01-09 | 1 Kommentare | Auf WhatsApp teilen
  • Fidget ist eine Rust-Bibliothek zum Darstellen, Kompilieren und Auswerten mathematischer Ausdrücke mit Hunderten bis Tausenden arithmetischer Terme; der wichtigste Einsatzbereich ist ein Backend für implizite Flächen
  • Implizite Flächen unterscheiden Innen und Außen über eine Distanzfunktion der Form $f(x,y,z) \rightarrow d$ und eignen sich gut für CSG-Operationen und parallele Auswertung
  • Das Frontend bietet eine Pipeline, die von Rhai-Skripten über mathematische Bäume, DAGs und SSA-Tapes bis hin zu wiederverwendbaren registernbasierten Bytecode führt
  • Das Backend stellt einen Interpreter und einen JIT-Compiler bereit und unterstützt Auswertung einzelner Punkte, SIMD-Arrays, automatische Differenzierung im Vorwärtsmodus sowie Intervallarithmetik
  • Bei einer Brute-Force-Auswertung von 7867 Ausdrücken mit 1024² reduzierte JIT die Laufzeit von 5,8 Sekunden auf 182 ms; beim optimierten Rendering schrumpfte der Unterschied jedoch auf etwa 25 %, mit 6 ms gegenüber 4,6 ms

Ziele von Fidget und implizite Flächen

  • Fidget ist eine Bibliothek zum Darstellen, Kompilieren und Auswerten großer mathematischer Ausdrücke
    • Sie zielt auf Ausdrücke mit Hunderten bis Tausenden arithmetischer Terme ab
    • Der wichtigste Einsatzbereich ist ein Backend für implizite Flächen, sie kann aber auch für andere Zwecke genutzt werden
  • Eine implizite Fläche ist ein Ausdruck der Form $f(x, y, z) \rightarrow d$, der einen einzelnen Distanzwert $d$ zurückgibt
    • Ist $d$ positiv, liegt der Punkt $(x,y,z)$ außerhalb des Modells
    • Ist $d$ negativ, liegt der Punkt innerhalb des Modells
    • Eine Kugel mit Radius 1 lässt sich als $\sqrt{x^2 + y^2 + z^2} - 1$ darstellen
  • Fidget konzentriert sich auf geschlossene implizite Flächen, deren Ausdrücke aus grundlegenden arithmetischen Operationen aufgebaut sind
    • Das steht im Gegensatz zu Ansätzen, bei denen der Distanzwert wie in GLSL-Pixel-Shadern mit einem Turing-vollständigen Programm berechnet wird
    • Solche Funktionen ähneln eher einer „Assembly Language für Shapes“, auf die höhere Repräsentationen abzielen können, als etwas, das man von Hand schreibt

Wo implizite Flächen Vorteile haben

  • Implizite Flächen sind kompakt und gut parallel auswertbar
    • Sie passen zu massiv paralleler Auswertung per SIMD-Instruktionen oder GPU
  • CSG-Operationen werden einfacher
    • Operationen wie union und intersection, die bei Meshes oder NURBS schwierig sind, lassen sich leicht ausdrücken
    • Die Vereinigung zweier exakt überlappender Zylinder wird als min(a, b) dargestellt
  • Geschlossene Gleichungen schaffen Optimierungsmöglichkeiten
    • Fidget kann einen Ausführungs-Trace erfassen, der zeigt, welcher Zweig während der Auswertung gewählt wurde
    • Mit diesem Trace lässt sich der Ausdruck vereinfachen und der Aufwand künftiger Auswertungen reduzieren

Warum nach libfive eine Neuentwicklung entstand

  • Fidget ist eine neu entwickelte Bibliothek, die den bisherigen libfive-Kernel ersetzen soll
    • libfive besteht aus rund 40K Zeilen, überwiegend C++-Code
    • Selbst für den ursprünglichen Autor war er schwer zu ändern; nach einigen Monaten erneutes Kompilieren führte häufig zu kaputten Builds, sodass CMake angefasst werden musste
  • Die neue Implementierung dient als Grundlage, um aktuell interessante Fragen zu untersuchen
    • Eine passende API für einen impliziten Kernel finden und dabei auch Breaking Changes in Kauf nehmen
    • Mit nativer JIT-Kompilierung experimentieren, um die Performance zu erhöhen, ohne auf die GPU zu wechseln
    • Nach WebAssembly cross-kompilieren und leicht zugängliche Web-Demos erstellen können
  • Fidget ist in Rust geschrieben
    • Es lässt sich mit einem einzigen cargo build kompilieren
    • Cross-Kompilierung nach WebAssembly funktioniert auf natürliche Weise
    • Rusts starkes Typsystem und Speichersicherheit erhöhen das Vertrauen beim Refactoring

Frontend: vom Skript zum Bytecode

  • Das Fidget-Frontend bietet eine Pipeline vom Eingabeskript bis hinunter zum Bytecode
    • Nutzer müssen diesem gesamten Ablauf nicht zwingend folgen; die Bibliothek kann an jeder Zwischenstufe verwendet werden

  • Rhai-Scripting

    • Fidget enthält Bindings für Rhai, eine eingebettete Skriptsprache für Rust
    • Per Operator-Overloading lassen sich mathematische Ausdrücke im Skript aufbauen
    • Der an draw übergebene Wert ist ein mathematischer Baum, der den vom Skript erzeugten Ausdruck repräsentiert

  • Bäume, Graphen und SSA-Tapes

    • Der mathematische Baum wird nach Deduplizierung in einen gerichteten azyklischen Graphen (DAG) umgewandelt
    • Durch topologische Sortierung wird der Graph zu linearem Code abgeflacht
    • Dieser Code liegt in SSA-Form (single static assignment) vor
    • Es gibt eine beliebige Anzahl von Pseudoregistern rX, und jedes Register wird nur einmal geschrieben
    • Auch das SSA-Tape kann ausgewertet werden, skaliert aber schlecht, weil jede Operation eine Speicherposition benötigt
    • Der Grund ist, dass Pseudoregister nicht wiederverwendet werden

  • Bytecode und Registerallokation

    • Um die Auswertung effizienter zu machen, werden Pseudoregister auf wiederverwendbare physische Register abgebildet
    • Ein beispielhaftes SSA-Tape lässt sich auf 6 wiederverwendbare Register komprimieren
    • Die Registerallokation verwendet den zuvor vorgestellten simple algorithm
    • Es ist ein Single-Pass-Algorithmus, der Geschwindigkeit und Determinismus über Effizienz stellt
    • Der Bytecode-Interpreter verwendet 256 Register
    • Registerindizes werden in u8 gespeichert
    • Reichen die Register nicht aus, fügt der Allokator LOAD und STORE ein und schreibt in Hilfsspeicher mit u32-Indizes

Backend: Auswertungsarten und Vereinfachung

  • Das Fidget-Backend ist über die Traits Function, TracingEvaluator und BulkEvaluator vom Frontend getrennt
    • Algorithmen müssen nicht eng an die Implementierung mathematischer Bäume gekoppelt sein, sondern können auf allgemeine Functions abzielen
    • Derzeit gibt es keine Nicht-Mathebaum-Implementierungen des Function-Traits
  • Aktuell gibt es zwei Arten, mathematische Bäume auszuwerten
    • Bytecode-Interpreter
    • JIT-kompilierte Funktion

  • Auswertungsmodi

    • Fidget bietet vier Auswertungsmodi
      • Auswertung eines einzelnen Punkts
      • Array-basierte SIMD-Auswertung
      • Automatische Differenzierung im Vorwärtsmodus
      • Intervallarithmetik
    • Bei der Bulk-Auswertung stellt der Nutzer Arrays mit Eingabewerten bereit und erhält ein Ausgabearray
    • Das JIT-Backend erzeugt SIMD-Code, der auf AArch64 4 Elemente und auf x86-64 8 Elemente gleichzeitig verarbeitet

  • Automatische Differenzierung im Vorwärtsmodus

    • Der Differenzierungs-Evaluator berechnet den Wert und bis zu 3 partielle Ableitungen
    • Bei impliziten Flächen berechnet man üblicherweise $(f, \partial f/\partial x, \partial f/\partial y, \partial f/\partial z)(x,y,z)$
    • Wenn auf der Fläche $f(x,y,z)=0$ gilt, sind die partiellen Ableitungen eine gute Näherung der Oberflächennormale
    • Dieser Wert kann fürs Shading verwendet werden
    • Die Auswertung erfolgt per automatischer Differenzierung im Vorwärtsmodus
    • An Registerwerte werden Ableitungswerte angehängt, und in jedem Schritt wird die Kettenregel angewendet
    • Der JIT-Evaluator legt Wert und 3 Ableitungen in einem einzelnen 4 x f32-Register ab

  • Intervallarithmetik

    • Intervallarithmetik wertet statt einzelner Eingabewerte Bereiche von Eingabewerten aus
    • Beispielsweise kann statt $x=1$ auch $1 \le x \le 5$ verwendet werden
    • Auch die Ausgabe wird dann zu einem Intervall, etwa $2 \le f(x,y,z) \le 20$
    • Ergebnisse der Intervallarithmetik sind konservativ
      • Sie umschließen den tatsächlichen Wertebereich der Funktion möglicherweise nicht eng
      • Sie enthalten aber alle möglichen Ausgaben innerhalb des gegebenen Eingabeintervalls
    • In der Auswertung impliziter Flächen ist Intervallarithmetik ein zentraler Baustein
    • Wenn bei der Auswertung eines Raumbereichs als $x,y,z$-Intervalle das Ausgabeintervall eindeutig größer als 0 ist, liegt der gesamte Bereich außerhalb der Form und muss nicht weiter betrachtet werden

  • Trace-basierte Vereinfachung

    • Der Intervallarithmetik-Evaluator erfasst auch einen Trace der Ausführung
    • Wenn bei min(a,b) gilt: $0 \le a \le 1$ und $4 \le b \le 5$, dann ist a immer kleiner, sodass der Ausdruck zu a vereinfacht werden kann
    • Jede min- und max-Operation zeichnet auf, welches Argument das Ergebnis beeinflusst
    • Als Auswahl wird links, rechts oder beide aufgezeichnet
    • Diese Auswahl wird zur Vereinfachung der ursprünglichen Funktion genutzt
    • Fidget unterstützt die Vereinfachung von min/max für CSG sowie der logischen Operationen and/or
    • Formen ohne CSG oder Logik profitieren nicht von der Vereinfachung
    • Der Vorteil, auf Basis der Intervallarithmetik leere oder vollständig gefüllte Bereiche zu überspringen, bleibt trotzdem erhalten

Kombination von Intervallarithmetik und Tape-Vereinfachung

  • Die Kombination von Intervallarithmetik und Tape-Vereinfachung ist eine zentrale Technik, um große Ausdrücke handhabbar zu machen
    • Sie überspringt inaktive Raumbereiche und macht auch die Auswertung der verbleibenden aktiven Bereiche günstiger
  • Tape-Vereinfachung berechnet vereinfachte Ausdrücke, die nur in einem bestimmten Raumbereich gültig sind
    • Anders als bei üblichen Beschleunigungsstrukturen fürs Raytracing wird die Beschleunigungsstruktur gewissermaßen dynamisch während der Auswertung erzeugt
  • Beim Rastern werden die Kosten der Intervallauswertung auf mehrere Pixel verteilt
    • Die Intervallauswertung eines Pixelbereichs von $N \times N$ ist $O(T)$, proportional zur Tape-Länge $T$
    • Sie hängt nicht von der Pixelanzahl ab
  • Wenn nach dem Abstieg bis in kleine Bereiche pixelweise ausgewertet wird, kommt ein deutlich kürzeres Tape zum Einsatz
    • In einem Bereich von $M \times M$ betragen die Kosten $O(T' \times M \times M)$
    • Dabei gilt $T' < T$
  • Im Beispiel eines 256×256-2D-Renderings von hello, world umfasst das ursprüngliche Tape 254 Anweisungen
    • 64 Pixel-Kacheln von 32×32 werden per Intervall ausgewertet
      • Leere Bereiche werden übersprungen, 47 aktive Kacheln bleiben übrig
      • Die durchschnittliche Tape-Länge der aktiven Kacheln sinkt auf 73 Anweisungen
    • Jede Kachel wird in 16 Pixel-Kacheln von 8×8 unterteilt
    • 752 Pixel-Kacheln von 8×8 werden per Intervall ausgewertet
      • Leere Bereiche werden übersprungen, 351 aktive Kacheln bleiben übrig
      • Die durchschnittliche Tape-Länge der aktiven Kacheln sinkt auf 20 Anweisungen
    • Für die verbleibenden 351 Kacheln von 8×8 wird pixelweise ausgewertet
  • Zum Zeitpunkt der pixelweisen Auswertung ist das Tape mehr als 10-mal kürzer als ursprünglich

JIT-Kompilierung

  • Der Bytecode-Interpreter ist zwar eine enge Schleife, hat aber unvermeidbaren Overhead
    • Der Instruction-Dispatch ist ein einzelner, schwer vorhersagbarer Branch
    • Jede Instruktion liest und schreibt Speicher über Register-Slots des VM-Evaluators
  • Für maximale Performance enthält Fidget einen JIT-Compiler, der Bytecode zu Maschinencode absenkt
    • Maschineninstruktionen sind geradliniger Code ohne Dispatch
    • Da physische Register direkt verwendet werden, sinkt die Zahl der Speicherlese- und -schreibzugriffe
  • Eingabe für den JIT ist dasselbe Bytecode-Tape wie zuvor
    • Statt der standardmäßigen 255 VM-Register wird für x86-64 mit 12 und für AArch64 mit 24 physischen Registern geplant
    • Auf AArch64 werden sie auf v8-31, auf x86-64 auf xmm4-15 abgebildet
  • Für jede Kombination aus Opcode × Datentyp × Architektur werden Assembly-Snippets von Hand geschrieben
    • Die gewünschten physischen Register werden in das Snippet gepatcht, anschließend wird es in einen per mmap angelegten Speicherbereich kopiert
  • Auf Rust-Ebene wird der erzeugte Speicher in einen Funktionszeiger gecastet und aufgerufen
    • Ein- und Ausgaben werden als Rust-Slices in Raw Pointer gecastet und übergeben

  • Performance-Zahlen

    • In einem komplexen Beispiel mit 7867 Ausdrücken profitiert eine Brute-Force-Auswertung von 1024² Pixeln stark vom JIT
    • Bytecode-Interpreter: 5,8 Sekunden
    • JIT-Backend: 182 ms
    • Beschleunigung: 31-fach
    • Brute Force nutzt weder Intervallarithmetik noch Tape-Vereinfachung
    • Mit einem intelligenteren Algorithmus wird der Abstand kleiner
    • Fidgets optimierte Rendering-Implementierung zeichnet dasselbe Bild mit dem Bytecode-Interpreter in 6 ms und mit dem JIT-Backend in 4,6 ms
    • In diesem Fall beträgt die Verbesserung etwa 25 %

Rendering und Mesh-Erzeugung

  • Rendering

    • Das Rendering aller Modelle verwendet die Algorithmen von fidget::render
    • Das Rendering nutzt den Kernalgorithmus aus dem SIGGRAPH-Paper
    • Große Raumbereiche werden mit Intervallarithmetik gerendert
    • Auf Tracing-Basis wird ein verkürztes Tape erzeugt
    • Mehrdeutige Bereiche werden unterteilt und rekursiv verarbeitet
    • Beim 3D-Rendering werden Normalen über partielle Ableitungen berechnet
    • Modelle werden im Rendering-Prozess mit einer homogenen 4×4-Matrix transformiert
    • Perspektivische Transformationen werden unterstützt
    • Das Rendering-Ergebnis besteht üblicherweise aus zwei Bildern: einer Heightmap und pixelweisen Normalen
    • Das Ergebnis kann mit Standardtechniken des Deferred Renderings wie SSAO gezeichnet werden

  • Mesh-Erzeugung

    • Fidget implementiert Manifold Dual Contouring zur Mesh-Erzeugung
    • Diese Implementierung sollte stets Meshes mit folgenden Eigenschaften erzeugen
      • watertight
      • manifold
      • Erhaltung scharfer Edges und Corners
      • adaptive Eigenschaften mit geringerer Dreiecksdichte in überwiegend flachen Bereichen
    • Es gibt auch bekannte Mängel
      • Dünne Merkmale werden nicht unbedingt erhalten
      • Das resultierende Mesh kann Selbstüberschneidungen enthalten
      • Die Platzierung der Vertices ist anfällig für adversarial cases
    • Gute Mesh-Erzeugung für beliebige implizite Flächen ist weiterhin ein ungelöstes Problem
    • Manifold Dual Contouring ist nicht perfekt, liegt aber an einem guten Kompromisspunkt zwischen Einfachheit und Performance

Demos und Web-GUI

  • Das Fidget-Repository enthält mehrere Demos
    • Die Web-GUI wird als interessanteste Demo vorgestellt
    • Außerdem gibt es das einfache CLI fidget-cli und den nativen Skript-Viewer fidget-viewer
  • Die Web-Demo kombiniert mehrere Webtechnologien
    • Die GUI ist in TypeScript geschrieben
    • Die Fidget-Crate wird als Bibliothek genutzt und steuert nicht den Event Loop
    • Der Texteditor verwendet CodeMirror
    • Für Node-Module war ein Bundler nötig; gewählt wurde webpack
    • Skriptauswertung und Rendering laufen in einem Web Worker, damit der Haupt-Event-Loop nicht blockiert wird
    • Um das Fehlen von std::thread im Browser zu umgehen, wird das Rendering mit wasm-bindgen-rayon parallelisiert
    • Worker und Haupt-Event-Loop teilen sich Speicher
    • Wenn Nutzer neue Eingaben machen, kann ein lang laufendes Rendering über ein mit dem Worker geteiltes Arc<AtomicBool>-Flag abgebrochen werden
  • Es war schwierig, die verschiedenen Komponenten zusammen zum Laufen zu bringen
    • Für jede Komponente gab es funktionierende Beispiele, aber Bundler, Konfigurationen, Server usw. unterschieden sich jeweils
    • Ein aktueller Bugfix in wasm-bindgen änderte das von wasm-bindgen-rayon benötigte Verhalten, weshalb eine ältere Version gepinnt werden musste
  • Die Web-Demo funktioniert auch auf Smartphones
    • Da sie Maus-Events verwendet, wird die Kamerasteuerung nicht unterstützt

Spannung zwischen Demo und Bibliothek

  • Fidget ist in erster Linie eine Bibliothek
    • Der beabsichtigte Einsatz ist, dass Nutzer sie als Infrastruktur in eigene Projekte einbetten, statt die Demo als echtes CAD-Tool zu verwenden
  • Allerdings gibt es deutlich mehr Menschen, die die Demo ausprobieren, als solche, die mit der Bibliothek Werkzeuge bauen
    • Einige nutzen die Demo sogar für Entwurfsarbeiten
    • Es besteht eine Spannung zwischen der Verbesserung der Demo für die größere Demo-Nutzerschaft und der Verbesserung der Bibliothek für die kleinere Gruppe von Tool-Entwicklern
  • Kernel und vollständiges CAD-UI gleichzeitig zu pflegen war schwierig, und der Umfang der Demo wurde nach und nach reduziert
    • Selbst eine „Minimal“-Demo wie der Web-Editor ist ein beträchtliches Projekt
  • Geplant sind drei Stoßrichtungen
    • Weiter den eigenen Interessen folgen, um Motivation und Fokus zu erhalten
    • Vorschläge von Tool-Nutzern annehmen, die Erwartungen aber realistisch setzen
    • Idealerweise Feedback von Tool-Entwicklern priorisieren, das die Demo-Last verringert

Künftige Möglichkeiten

  • GPU-Backend

    • Ein GPU-Backend ist eine naheliegende Erweiterung
    • Es gibt bereits ein zugehöriges SIGGRAPH-Paper
    • Im Branch wgpu-bytecode ist es bereits implementiert
    • Auf einem Apple-M1-Max-Laptop ist die Performance nicht besonders attraktiv
    • Die Interpreter-Schleife für Bytecode wirkt sehr ineffizient
    • Die eigentliche Ursache wird weiter untersucht

  • Bessere Mesh-Erzeugung

    • Für ernsthafte Nutzer der Bibliothek ist die Mesh-Erzeugung ein großes Thema
    • Fidget verwendet dieselbe Mesh-Erzeugungsstrategie wie libfive, hat aber nicht die vielen feinen Tunings, die libfive robuster machen
    • Da die derzeit verfügbaren Optionen nicht zufriedenstellen, wurde bisher nicht viel Zeit in diesen Bereich investiert
    • Statt dual contouring weiter auszubessern, soll lieber ein bulletproof Mesh-Algorithmus implementiert werden
    • Es gibt noch keine Methode aus der Literatur oder eigene Alternative, die die Anforderungen erfüllt
    • Je nach Nutzernachfrage können einige Tunings vorgenommen werden, gleichzeitig soll aber weiter nach besseren Optionen gesucht werden

  • Bibliothek für Standard-Shapes und -Transforms

    • Über mehrere Software-Generationen hinweg wurde die Standard-Shape-Bibliothek der Fab Modules auf neue Tools portiert
    • Diese Arbeit ist mühsam, bietet aber eine einigermaßen standardisierte Grundlage für High-Level-Modellierung
    • In libfive wurde jede Shape in C++ geschrieben; aus den Header-Dateien wurden C-, Python- und Scheme-Bindings automatisch erzeugt
    • Das README beschreibt, dass libfive_stdlib.h zugleich ein C-Header und ein strukturiertes Dokument ist, das von Helper-Skripten geparst wird
    • Der Ansatz von Fidget wird noch diskutiert
    • Die laufende Diskussion findet sich in fidget#145
    • Eine Möglichkeit wäre, die Fab-Shapes-Bibliothek nach Rust zu holen
    • Auch eleganterer Code mit GLSL-Vektoren, wie in Inigo Quilez’ Primitives-Bibliothek, dient als Referenzpunkt

  • High-Level-Sprach-Bindings

    • Fidget bietet derzeit nur Rhai-Bindings
    • Rhai wurde gewählt, weil es eine der ausgereiften Rust-first-Skriptsprachen ist
    • Die Integration war einfach, und ein Vorteil ist, dass es nach WebAssembly kompiliert
    • Viele Nutzer könnten Python- oder Node-Bindings bevorzugen
    • Auch die Art der Bindings ist noch offen
    • Eine C-API würde es ermöglichen, die FFI-Bibliotheken der jeweiligen Sprachen zu nutzen, fühlt sich bei einem Rust-first-Design aber wie ein Schritt nach unten an
    • Sobald es eine Standardbibliothek gibt, wäre es wünschenswert, sie mit passender Nutzbarkeit wie Docstrings und Standardargumenten automatisch in den jeweiligen Bindings verfügbar zu machen

Veröffentlichungsstatus und Nutzung

  • Das README von Fidget bezeichnete den Status seit der ersten Veröffentlichung als „quietly public“
    • Auf crates.io wurden 19 Versionen veröffentlicht
    • Einige Nutzer haben bereits begonnen, auf Fidget etwas aufzubauen
  • Jetzt wechselt Fidget in die Phase „loudly public“
  • Der Quellcode liegt auf Github
    • Zu Rust-Projekten kann es mit cargo add fidget hinzugefügt werden
    • Die Lizenz ist die schwache Copyleft-Lizenz MPL 2.0
    • Sie wird als Lizenz dargestellt, die sowohl Open Source als auch kommerzielle Nutzung gut unterstützt

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-01-09
Hacker-News-Meinungen

  • Hallo, das ist mein Projekt :)
    Was mir an diesem Bereich der Informatik besonders gefällt: Es ist für alle etwas dabei. Datenstrukturen und Algorithmen, Low-Level-Performance-Arbeit, Compiler, Rendering/Computergrafik, UI/UX für Design-Tools, GPGPU-Programmierung und mehr kommen hier zusammen.
    Ich beantworte Fragen, die im Thread auftauchen, aber weitere Updates könnt ihr auch über Social Media (https://mattkeeter.com/links/) oder den RSS-Feed des Blogs (https://mattkeeter.com/atom.xml) verfolgen.

    • Beim Durchstöbern des Blogs bin ich darauf gestoßen, und es hat mir wirklich gut gefallen: https://www.mattkeeter.com/projects/machined-pen/the_plan.jp...
      Das veranschaulicht gut einen Gedanken, den ich schon länger im Kopf habe: Was wäre, wenn der Prozess, mit dem dieser Fertigungsplan entworfen wurde, selbst zur nutzerseitigen CAD API würde? Wenn man „Making“-Probleme wie Holzbearbeitung, Klempnerei, Metallfertigung oder Zerspanung angeht, denkt man ganz natürlich über Rohmaterial, verfügbare Werkzeuge und die Reihenfolge der Arbeitsschritte nach, mit denen man zum gewünschten Ergebnis kommt.
      Aktuelle CAD-APIs funktionieren aber nicht so – weder Code-CAD-Tools noch traditionelle mausbasierte Interfaces. Sie bringen einen dazu, sich darauf zu konzentrieren, wie man die fertige Form darstellt, statt darauf, wie man sie tatsächlich herstellt. Am Ende geht es darum, Dinge zu bauen; Modellierung ist nur ein Werkzeug dafür, aber dieses Werkzeug drängt sich viel zu sehr in den Vordergrund.
      Ein stärker realitätsbasierter Modellierungsablauf scheint viele Vorteile zu haben. Aus deiner Sicht mit deutlich mehr CAD-Erfahrung: Hat dieses Konzept Entwicklungspotenzial, oder ist es eine Sackgasse?
      Noch ein Feedback zum Stift: Wenn man das Stangenmaterial in ein 3-jaw chuck spannt, es auf ein zum collet passendes Maß dreht, aus dem passend gedrehten Stab einen Rohling für die Kappe und zwei für den Body abschneidet und die restlichen Arbeiten dann im collet spannt, lässt sich die Konzentrizität erhalten. Wenn das Endmaß allerdings vom collet-Maß abweicht, entsteht etwas Materialverschnitt.
    • Matt, eine kurze Frage. Ich habe nicht gründlich genug gesucht, also entschuldige bitte, falls sie zu allgemein oder dumm ist.
      Worin unterscheidet sich Fidget funktional von libfive oder Ao?
    • Cool! Ich erinnere mich, dass ich zum Expression-Parser-Code der Arbeit von Knoll et al. 2009 beigetragen habe, die im SIGGRAPH-Paper zitiert wird.
      Dieser Code hat lediglich eine nutzerfreundliche einzelne Expression in verschachtelte Funktionsaufrufe für die IA-Bibliothek in GLSL übersetzt, ganz ohne Optimierung. Das hier geht sehr viel weiter.

  • Zufällig habe ich gerade auch einen anderen hervorragenden Artikel des Autors gelesen: https://www.mattkeeter.com/projects/constraints/

  • Wow, das wäre unglaublich nützlich gewesen, als ich meinen eigenen Renderer für implizite Flächen gebaut habe.
    Mein Ansatz war in mancher Hinsicht ähnlich (Intervallarithmetik), in anderer Hinsicht anders. Er war weniger optimiert, und ich habe GLSL für den fragment shader direkt erzeugt.
    Ehrlich gesagt bekomme ich Lust, alles wegzuwerfen, das hier neu zu implementieren und es zu ersetzen. Ich weiß nicht, ob ich mich freuen oder traurig sein soll.

    • Freu dich ruhig! Du arbeitest in einem Bereich, in dem man eigene Tools bauen und gleichzeitig Tools anderer nutzen kann.
      Du kannst Ideen übernehmen, oder du kannst dieses Projekt nutzen und dazu beitragen. So oder so ist das großartig.

  • Dass ein neuer Open-Source-CAD-Kernel erschienen ist, ist großartig! Aus dem Artikel konnte ich nicht erkennen, ob Export in gängige Formate wie STEP unterstützt wird.
    Falls ja – oder falls das möglich wird –, könnte das eine hervorragende Grundlage für viele Open-Source-CAD-Bibliotheken sein.

    • Leider wird STEP-Export nicht unterstützt, weil STEP-Dateien eine völlig andere interne Repräsentation verwenden.
      Die meisten STEP-Dateien beschreiben Geometrie als Sammlung von Flächen, zum Beispiel trimmed NURBS. Diese Flächen müssen eine lückenlose Mannigfaltigkeit bilden; dann kann sie als Volumenkörper behandelt werden.
      Damit das in der Praxis funktioniert, braucht man keinen Funktionsrepräsentations-Ansatz (f-reps) wie bei Fidget, sondern einen Boundary-Representation-Kernel (b-reps). Einen solchen Kernel zu schreiben, ist ein deutlich schwierigeres Problem. Zum Beispiel hat die Schnittkurve zweier NURBS-Flächen nicht immer eine geschlossene Darstellung.
      Als ich mit jemandem aus der Branche gesprochen habe, schätzte er, dass selbst ein Team, das so etwas schon einmal gemacht hat, für einen brauchbaren b-rep-Kernel etwa sechs Ingenieure und rund ein Jahr bräuchte.
      Falls du mehr wissen willst: Zufällig habe ich auch einen STEP-Datei-Viewer geschrieben, der einen b-rep-Kernel enthält, der allerdings weit von industrieller Qualität entfernt ist: https://www.mattkeeter.com/projects/foxtrot/.

  • „Wenn man 1024² Pixel per Brute Force auswertet, braucht der Bytecode-Interpreter 5,8 Sekunden, das JIT-Backend 182 ms und ist damit 31-mal schneller“
    „Mit einem intelligenteren Algorithmus fällt die Beschleunigung weniger spektakulär aus. Der Brute-Force-Ansatz nutzt weder Intervallarithmetik noch Tape-Vereinfachung. Fidgets optimierte Rendering-Implementierung zeichnet dieses Bild mit dem Bytecode-Interpreter in 6 ms und mit dem JIT-Backend in 4,6 ms; die Verbesserung beträgt also nur etwa 25 %“
    Mir gefällt, dass hier der Fokus darauf liegt, dass das JIT-Backend nach der algorithmischen Optimierung weniger wichtig ist, und nicht darauf, dass die algorithmische Optimierung beim Bytecode eine 1000-fache und beim JIT eine 40-fache Verbesserung bringt.

  • Vor ein paar Jahren habe ich an der Uni ein wenig an einem Simulator für Kernphysik gearbeitet, also an so etwas wie Reaktormodellierung.
    Das Geometriemodell basierte auf impliziten Flächen, insbesondere R-functions. min(x,y) ist ebenfalls ein Beispiel dafür; sie haben interessante Eigenschaften, etwa dass sie überall differenzierbar sind.
    Eine gute Einführung ist diese hier. Vielleicht ist es sogar das einzige Material dazu auf Englisch: https://ecommons.cornell.edu/items/35ae0f68-1af5-4f28-8b8b-7...
    Ich bin schon eine ganze Weile aus der Kernphysik raus, aber ich vermute, dass für die Modellierung immer noch viel alter Fortran-Code verwendet wird. Fidget hat interessantes Potenzial als Kernel für neue Simulationspakete.

  • Etwas anderes Thema, aber ich suche nach der besten codebasierten CAD-Software.
    CadQuery habe ich ausprobiert, hatte damit aber ein paar Probleme. Gibt es etwas, das ihr für 3D-Druck empfehlen könnt?

    • Ich habe einen Vortrag über codebasiertes CAD gehalten und dabei ziemlich viele Optionen behandelt.
      https://youtu.be/0wn7vUmWQgg?si=9Rc1tvbiQgQDgQzd&t=2766
      Ich entwickle auch selbst eines in Rust, aber ich würde noch nicht sagen, dass es bereit ist.
    • Es gibt auch build123d.
      https://github.com/gumyr/build123d
    • Für alle, die das Video nicht öffnen wollen: Die Liste aus anderen Kommentaren/dem Video lautet:
      OpenSCAD, DSLCAD, CadQuery, Build123d, Cascade Studio, Declaracad, Replicad
    • replicad

  • Interessant. Ich habe früher schon Paper und Demos zu solchen impliziten Flächen gesehen. Vielleicht war das sogar Arbeit des Autors.
    Es ist beeindruckend, welche Modelle man mit etwas Fantasie erstellen kann, aber ich würde gern etwas Größeres als Spielzeugbeispiele sehen.
    Kann man zum Beispiel Flächen extrudieren, wie es in einem B-rep-Kernel möglich ist, oder SVGs/Schriften importieren und daraus Solids machen?
    Ich würde wirklich gern einen schnellen Open-Source-Kernel sehen, der solche Funktionen unterstützt und sich außerdem gut parallelisieren lässt.

  • Ich muss sehr an Ian Henrys https://bauble.studio/ denken.

  • Ich wollte auch einmal etwas Ähnliches mit SDFs machen, bei dem man einen abstrakten Baum zur Flächenerzeugung bearbeitet.
    Die Idee ist, ein Ziel-Mesh oder eine Punktwolke zu haben und per Hill Climbing/Annealing einen Baum zu finden, der möglichst gut zur gewünschten Form passt.

    • „A Unified Differentiable Boolean Operator with Fuzzy Logic“ dürfte interessant sein.
      https://arxiv.org/abs/2407.10954
      Dabei werden differenzierbare Leaves (Quadriken) mit differenzierbaren Boolean-ähnlichen Operationen zu einem CSG-Baum kombiniert, sodass man über die gesamte Form Hill Climbing durchführen kann.