Fidget : bibliothèque d’évaluation de grandes expressions mathématiques

 (mattkeeter.com)
3 points par GN⁺ 2025-01-09 | 1 commentaires | Partager sur WhatsApp
  • Fidget est une bibliothèque Rust pour représenter, compiler et évaluer des expressions mathématiques composées de centaines à des milliers de termes arithmétiques, principalement destinée aux backends de surfaces implicites
  • Les surfaces implicites distinguent l’intérieur et l’extérieur via une fonction de distance de la forme $f(x,y,z) \rightarrow d$, ce qui se prête bien aux opérations CSG et à l’évaluation parallèle
  • Le frontend fournit un pipeline allant des scripts Rhai à des arbres mathématiques, des DAG, des bandes SSA, puis à un bytecode fondé sur des registres réutilisables
  • Le backend propose un interpréteur et un compilateur JIT, avec prise en charge de l’évaluation en point unique, des tableaux SIMD, de la différentiation automatique en mode direct et de l’arithmétique d’intervalles
  • Sur une évaluation brute force en 1024² de 7 867 expressions, le JIT fait passer le temps de 5,8 s à 182 ms, mais sur un rendu optimisé l’écart se resserre à environ 25 %, avec 6 ms contre 4,6 ms

Objectifs de Fidget et surfaces implicites

  • Fidget est une bibliothèque conçue pour représenter, compiler et évaluer de grandes expressions mathématiques
    • Elle vise des expressions comportant de centaines à des milliers de termes arithmétiques
    • Son usage principal est comme backend de surfaces implicites, mais elle peut aussi servir à d’autres fins
  • Une surface implicite est une expression de la forme $f(x, y, z) \rightarrow d$ qui renvoie une unique valeur de distance $d$
    • Si $d$ est positif, le point $(x,y,z)$ se trouve à l’extérieur du modèle
    • Si $d$ est négatif, le point est à l’intérieur du modèle
    • Une sphère de rayon 1 peut être représentée par $\sqrt{x^2 + y^2 + z^2} - 1$
  • Fidget se concentre sur les surfaces implicites fermées qui construisent leurs expressions à partir d’opérations arithmétiques de base
    • Cela contraste avec l’approche consistant à calculer la distance à l’aide de programmes turing-complets, comme en GLSL dans un pixel shader
    • Ce type de fonction ressemble moins à quelque chose que l’on écrit à la main qu’à un « langage assembleur des formes » facile à cibler depuis une représentation de plus haut niveau

Là où les surfaces implicites sont avantageuses

  • Les surfaces implicites sont compactes et adaptées à l’évaluation parallèle
    • Elles conviennent à l’évaluation massivement parallèle via des instructions SIMD ou le GPU
  • Les opérations CSG deviennent simples
    • Des opérations comme l’union ou l’intersection, difficiles sur des maillages ou des NURBS, peuvent être exprimées facilement
    • L’union de deux cylindres se recouvrant exactement s’exprime par min(a, b)
  • Les équations fermées créent des opportunités d’optimisation
    • Fidget peut capturer une trace d’exécution indiquant quelle branche a été choisie pendant l’évaluation
    • Cette trace sert ensuite à simplifier l’expression et à réduire le coût des évaluations suivantes

Pourquoi repartir de zéro après libfive

  • Fidget est une nouvelle bibliothèque créée pour remplacer le noyau existant de libfive
    • libfive se compose d’environ 40 K lignes de code, en grande majorité en C++
    • Même pour son auteur d’origine, il était difficile à modifier, et le simple fait de recompiler quelques mois plus tard cassait souvent le build, imposant de bricoler CMake
  • La nouvelle implémentation sert aujourd’hui de base pour expérimenter des questions intéressantes
    • Trouver une API adaptée à un noyau implicite, y compris en acceptant de casser la compatibilité
    • Expérimenter la compilation JIT native pour améliorer les performances sans passer au GPU
    • Cross-compiler vers WebAssembly et créer une démo web facile d’accès
  • Fidget est écrit en Rust
    • Il se compile avec un simple cargo build
    • Il se cross-compile naturellement vers WebAssembly
    • Le système de types robuste de Rust et sa sûreté mémoire rendent les refactorings plus fiables

Frontend : du script au bytecode

  • Le frontend de Fidget fournit un pipeline allant du script d’entrée jusqu’au bytecode
    • L’utilisateur n’est pas obligé de suivre tout ce flux : la bibliothèque peut être utilisée à n’importe quelle étape intermédiaire

  • Scripting Rhai

    • Fidget inclut des bindings pour Rhai, un langage de scripting embarqué pour Rust
    • Grâce à la surcharge d’opérateurs, les expressions mathématiques peuvent être construites dans le script
    • La valeur transmise à draw est un arbre mathématique représentant l’expression créée par le script

  • Arbres, graphes et bandes SSA

    • L’arbre mathématique est converti en graphe orienté acyclique (DAG) après élimination des doublons
    • Un tri topologique permet d’aplatir le graphe en code linéaire
    • Ce code est sous forme SSA (single static assignment)
    • Il comporte un nombre arbitraire de pseudo-registres rX, chacun écrit une seule fois
    • La bande SSA peut aussi être évaluée, mais elle passe mal à l’échelle car chaque opération nécessite un emplacement mémoire
    • Cela vient du fait que les pseudo-registres ne sont pas réutilisés

  • Bytecode et allocation de registres

    • Pour améliorer l’efficacité d’évaluation, les pseudo-registres sont mappés vers des registres physiques réutilisables
    • La bande SSA d’exemple peut être compressée en 6 registres réutilisables
    • L’allocation de registres utilise le simple algorithm présenté précédemment
    • C’est un algorithme en un seul passage qui privilégie la vitesse et le déterminisme à l’efficacité
    • L’interpréteur de bytecode utilise 256 registres
    • Les index de registres sont stockés dans des u8
    • En cas de manque de registres, l’allocateur insère des LOAD et STORE pour écrire dans une mémoire auxiliaire indexée en u32

Backend : modes d’évaluation et simplification

  • Le backend de Fidget est séparé du frontend via les traits Function, TracingEvaluator et BulkEvaluator
    • Les algorithmes ne sont pas couplés étroitement à l’implémentation de l’arbre mathématique et peuvent cibler un Function générique
    • Il n’existe actuellement aucune implémentation non basée sur un arbre mathématique du trait Function
  • Il existe actuellement deux modes d’évaluation pour les arbres mathématiques
    • L’interpréteur de bytecode
    • Les fonctions compilées en JIT

  • Modes d’évaluation

    • Fidget propose quatre modes d’évaluation
      • Évaluation en point unique
      • Évaluation SIMD sur tableaux
      • Différentiation automatique en mode direct
      • Arithmétique d’intervalles
    • En évaluation bulk, l’utilisateur fournit des tableaux d’entrée et reçoit des tableaux de sortie
    • Le backend JIT génère du code SIMD qui traite 4 éléments à la fois sur AArch64 et 8 sur x86-64

  • Différentiation automatique en mode direct

    • L’évaluateur différentiel calcule la valeur et jusqu’à 3 dérivées partielles
    • Pour les surfaces implicites, on calcule généralement $(f, \partial f/\partial x, \partial f/\partial y, \partial f/\partial z)(x,y,z)$
    • Sur la surface, quand $f(x,y,z)=0$, les dérivées partielles fournissent une bonne approximation de la normale de surface
    • Cette valeur peut être utilisée pour le shading
    • L’évaluation repose sur la différentiation automatique en mode direct
    • On attache des valeurs différentielles aux registres et on applique la règle de la chaîne à chaque étape
    • L’évaluateur JIT place la valeur et 3 dérivées dans un seul registre 4 x f32

  • Arithmétique d’intervalles

    • L’arithmétique d’intervalles évalue une plage de valeurs d’entrée plutôt qu’une seule valeur
    • Par exemple, on peut utiliser $1 \le x \le 5$ au lieu de $x=1$
    • La sortie devient elle aussi un intervalle, par exemple $2 \le f(x,y,z) \le 20$
    • Le résultat de l’arithmétique d’intervalles est conservatif
      • Il peut ne pas envelopper étroitement la plage réelle de la fonction
      • Mais il inclut toutes les sorties possibles à l’intérieur de l’intervalle d’entrée donné
    • Dans l’évaluation des surfaces implicites, l’arithmétique d’intervalles est un composant essentiel
    • Si, en évaluant une région de l’espace sous forme d’intervalles sur $x,y,z$, l’intervalle de sortie est clairement supérieur à 0, alors toute la région est à l’extérieur de la forme et il n’est pas nécessaire d’aller plus loin

  • Simplification basée sur les traces

    • L’évaluateur en arithmétique d’intervalles capture également une trace d’exécution
    • Dans min(a,b), si $0 \le a \le 1$ et $4 \le b \le 5$, alors a est toujours plus petit, ce qui permet de simplifier l’expression en a
    • Chaque opération min et max enregistre l’argument qui influence le résultat
    • Le choix est noté comme gauche, droite ou les deux
    • Cette sélection est ensuite utilisée pour simplifier la fonction d’origine
    • Fidget prend en charge la simplification de min et max utilisés en CSG, ainsi que des opérations logiques and et or
    • Les formes sans CSG ni logique ne tirent pas parti de cette simplification
    • Elles conservent néanmoins l’avantage de l’arithmétique d’intervalles pour ignorer les régions vides ou complètement pleines

Combinaison de l’arithmétique d’intervalles et de la simplification de tape

  • La combinaison de l’arithmétique d’intervalles et de la simplification de tape est une technique clé pour rendre les grandes expressions plus faciles à manipuler
    • Elle permet d’ignorer les régions spatiales inactives et de réduire aussi le coût d’évaluation des régions actives restantes
  • La simplification de tape consiste à calculer des expressions simplifiées valides uniquement dans une région spatiale donnée
    • Contrairement aux structures d’accélération classiques du ray tracing, cela revient à construire dynamiquement une structure d’accélération pendant l’évaluation
  • En rastérisation, le coût de l’évaluation par intervalles est amorti sur plusieurs pixels
    • L’évaluation par intervalles d’une zone de $N \times N$ pixels est en $O(T)$, proportionnellement à la longueur de tape $T$
    • Elle ne dépend pas du nombre de pixels
  • Lorsqu’on descend vers de petites régions puis qu’on passe à une évaluation pixel par pixel, on utilise une tape devenue beaucoup plus courte
    • Dans une zone de $M \times M$, le coût est de $O(T' \times M \times M)$
    • Ici, $T' < T$
  • Dans l’exemple de rendu 2D hello, world en 256×256, la tape d’origine contient 254 clauses
    • 64 tuiles de 32×32 pixels sont évaluées par intervalles
      • Les zones vides sont ignorées et il reste 47 tuiles actives
      • La longueur moyenne de tape des tuiles actives descend à 73 clauses
    • Chaque tuile est subdivisée en 16 tuiles de 8×8 pixels
    • 752 tuiles de 8×8 pixels sont évaluées par intervalles
      • Les zones vides sont ignorées et il reste 351 tuiles actives
      • La longueur moyenne de tape des tuiles actives descend à 20 clauses
    • Les 351 tuiles 8×8 restantes sont ensuite évaluées pixel par pixel
  • Au moment de l’évaluation pixel par pixel, la tape est devenue plus de 10 fois plus courte que sa longueur d’origine

Compilation JIT

  • L’interpréteur de bytecode est une boucle serrée, mais avec un surcoût inévitable
    • Le dispatch des instructions repose sur une branche unique difficile à prédire
    • Chaque instruction lit et écrit en mémoire via les slots de registres de l’évaluateur VM
  • Pour obtenir des performances maximales, Fidget inclut un compilateur JIT qui abaisse le bytecode en code machine
    • Les instructions machine forment un code linéaire sans dispatch
    • Elles utilisent directement les registres physiques, ce qui réduit les lectures et écritures mémoire
  • L’entrée du JIT est la même tape de bytecode qu’auparavant
    • Au lieu des 255 registres par défaut de la VM, la planification se fait pour 12 registres physiques sur x86-64 et 24 sur AArch64
    • Le mapping se fait vers v8-31 sur AArch64 et xmm4-15 sur x86-64
  • Des snippets d’assembleur sont écrits à la main pour chaque combinaison opcode × type de données × architecture
    • Les registres physiques voulus sont patchés dans les snippets, puis ceux-ci sont copiés dans une zone mémoire allouée via mmap
  • Au niveau Rust, la mémoire générée est convertie en pointeur de fonction puis appelée
    • Les entrées et sorties sont passées en convertissant des slices Rust en raw pointers

  • Chiffres de performance

    • Dans un exemple complexe composé de 7 867 expressions, l’évaluation brute force sur 1024² pixels bénéficie fortement du JIT
    • Interpréteur de bytecode : 5,8 secondes
    • Backend JIT : 182 ms
    • Gain de vitesse : 31×
    • Le brute force n’utilise ni l’arithmétique d’intervalles ni la simplification de tape
    • Avec des algorithmes plus intelligents, l’écart se réduit
    • L’implémentation de rendu optimisée de Fidget produit la même image en 6 ms avec l’interpréteur de bytecode et en 4,6 ms avec le backend JIT
    • Dans ce cas, le gain est d’environ 25 %

Rendu et génération de maillage

  • Rendu

    • Tous les rendus de modèles utilisent l’algorithme de fidget::render
    • Le rendu repose sur l’algorithme central du papier SIGGRAPH
    • Les grandes régions spatiales sont rendues avec l’arithmétique d’intervalles
    • Une tape raccourcie est générée par traçage
    • Les régions ambiguës sont subdivisées et traitées récursivement
    • En rendu 3D, les normales sont calculées par dérivées partielles
    • Les modèles sont transformés pendant le rendu via des matrices homogènes 4×4
    • Les transformations en perspective sont prises en charge
    • Le résultat du rendu est généralement constitué de deux images : une heightmap et des normales par pixel
    • Le résultat peut être affiché avec des techniques standard de rendu différé comme la SSAO

  • Génération de maillage

    • Pour la génération de maillage, Fidget implémente Manifold Dual Contouring
    • Cette implémentation doit toujours produire un maillage avec les propriétés suivantes
      • watertight
      • manifold
      • préservation des arêtes et coins vifs
      • caractère adaptatif avec une faible densité de triangles dans les zones majoritairement planes
    • Des défauts connus existent aussi
      • les détails fins ne sont pas forcément préservés
      • le maillage résultant peut contenir des auto-intersections
      • le placement des sommets est vulnérable aux adversarial cases
    • La bonne génération de maillage pour des surfaces implicites arbitraires reste un problème non résolu
    • Manifold Dual Contouring n’est pas parfait, mais représente un compromis entre simplicité et performances

Démos et interface web

  • Le repository Fidget inclut plusieurs demos
    • L’interface web est présentée comme la démo la plus intéressante
    • Il existe aussi fidget-cli, une simple CLI, ainsi que fidget-viewer, un visualiseur de scripts natif
  • La démo web combine plusieurs technologies web
    • L’interface est écrite en TypeScript
    • Le crate Fidget est utilisé comme bibliothèque et ne pilote pas la boucle d’événements
    • L’éditeur de texte utilise CodeMirror
    • Un bundler était nécessaire pour utiliser des modules Node, et le choix s’est porté sur webpack
    • L’évaluation des scripts et le rendu sont effectués dans un web worker afin de ne pas bloquer la boucle d’événements principale
    • Pour contourner l’absence de std::thread dans le navigateur, le rendu est parallélisé avec wasm-bindgen-rayon
    • Le worker et la boucle d’événements principale partagent la mémoire
    • Quand l’utilisateur fournit une nouvelle entrée, un drapeau Arc<AtomicBool> partagé avec le worker permet d’annuler les rendus trop longs
  • Faire fonctionner ensemble tous ces composants a été difficile
    • Chaque composant avait des exemples fonctionnels, mais les bundlers, configurations et serveurs différaient tous
    • Une correction récente de bug dans wasm-bindgen a modifié le comportement nécessaire à wasm-bindgen-rayon, ce qui a obligé à figer une ancienne version
  • La démo web fonctionne aussi sur téléphone
    • Elle utilise des événements souris et ne prend donc pas en charge le contrôle de la caméra

La tension entre démo et bibliothèque

  • Fidget est avant tout une bibliothèque
    • L’usage prévu est que les utilisateurs l’intègrent comme infrastructure dans leurs propres projets, plutôt que d’utiliser la démo comme un véritable outil de CAO
  • Mais il y a bien plus de personnes qui manipulent la démo que de personnes qui créent des outils avec la bibliothèque
    • Certaines vont jusqu’à utiliser la démo pour du travail de conception
    • Il existe donc une tension entre améliorer la démo pour une base d’utilisateurs plus large, ou améliorer la bibliothèque pour un groupe plus restreint de créateurs d’outils
  • Maintenir à la fois le noyau et une interface de CAO complète était difficile, et le périmètre de la démo s’est progressivement réduit
    • Même une démo « minimale » comme l’éditeur web reste un projet conséquent
  • Le plan suit trois directions
    • continuer à suivre ses centres d’intérêt pour garder motivation et concentration
    • accueillir les suggestions des utilisateurs d’outils, tout en gardant des attentes raisonnables
    • idéalement, donner la priorité aux retours des créateurs d’outils qui réduisent la charge liée aux démos

Possibilités à venir

  • Backend GPU

    • Le backend GPU est une extension naturelle
    • Il existe déjà des articles SIGGRAPH sur le sujet
    • Une implémentation existe déjà dans la branche wgpu-bytecode
    • Sur un portable Apple M1 Max, les performances ne sont pas particulièrement séduisantes
    • La boucle de l’interpréteur de bytecode semble très inefficace
    • La cause fondamentale est toujours en cours d’investigation

  • Meilleure génération de maillage

    • Pour les utilisateurs sérieux de la bibliothèque, la génération de maillage est un enjeu majeur
    • Fidget utilise la même stratégie de génération de maillage que libfive, mais sans les nombreux ajustements fins qui rendent le comportement de libfive plus robuste
    • Comme les options actuellement disponibles ne sont pas satisfaisantes, beaucoup de temps n’a pas été consacré à ce point
    • L’objectif est d’implémenter un algorithme de maillage bulletproof plutôt que de rafistoler le dual contouring
    • Il n’existe pas encore de méthode issue de la littérature ni d’alternative maison qui réponde aux exigences
    • Quelques ajustements pourront être faits selon la demande des utilisateurs, mais l’idée est aussi de continuer à chercher de meilleures options

  • Bibliothèque standard de shapes et de transformations

    • Sur plusieurs générations de logiciels, la bibliothèque standard de shapes de Fab Modules a été portée vers de nouveaux outils
    • Ce travail est fastidieux, mais fournit une base relativement standard pour la modélisation de haut niveau
    • Dans libfive, chaque shape était écrite en C++, et des bindings C, Python et Scheme étaient générés automatiquement depuis les fichiers d’en-tête
    • Le README explique que libfive_stdlib.h est à la fois un en-tête C et une documentation structurée analysée par des scripts utilitaires
    • L’approche de Fidget est encore en discussion
    • Les discussions en cours se trouvent dans fidget#145
    • Il est possible d’intégrer la bibliothèque de shapes Fab en Rust
    • Un code plus élégant exploitant les vecteurs GLSL, comme dans la bibliothèque de primitives d’Inigo Quilez, sert aussi de référence

  • Bindings pour des langages de plus haut niveau

    • Fidget ne propose actuellement que des bindings Rhai
    • Rhai a été choisi car c’est l’un des langages de scripting Rust-first les plus matures
    • Il était facile à intégrer et présente l’avantage d’être compilable en WebAssembly
    • Beaucoup d’utilisateurs préféreront peut-être des bindings Python ou Node
    • La manière de proposer ces bindings reste aussi une question ouverte
    • Une API C permettrait de s’appuyer sur les bibliothèques FFI de chaque langage, mais dans une conception Rust-first, cela donne l’impression de descendre d’un niveau
    • Une fois la bibliothèque standard disponible, il serait souhaitable qu’elle soit exposée automatiquement dans chaque binding avec une ergonomie adaptée, comme des docstrings et des arguments par défaut

Statut de publication et mode d’emploi

  • Le README de Fidget décrivait son état depuis la publication initiale comme « quietly public »
    • 19 versions ont été publiées sur crates.io
    • Certains utilisateurs ont déjà commencé à construire des choses sur Fidget
  • Fidget passe désormais à l’étape « loudly public »
  • Le code source est disponible sur Github
    • Il peut être ajouté à un projet Rust avec cargo add fidget
    • La licence est la MPL 2.0, un copyleft faible
    • Elle est présentée comme une licence compatible à la fois avec l’open source et les usages commerciaux

À lire aussi

1 commentaires

 
GN⁺ 2025-01-09
Avis de Hacker News

  • Bonjour, c’est mon projet :)
    Ce que j’aime particulièrement dans ce domaine de l’informatique, c’est qu’il y en a pour tout le monde. On y trouve des structures de données et algorithmes, du travail de performance bas niveau, des compilateurs, du rendu/graphisme informatique, de l’UI/UX pour outils de design, de la programmation GPGPU, etc.
    Je répondrai aux questions qui apparaissent dans le fil, mais vous pouvez aussi suivre les prochaines mises à jour via les réseaux sociaux (https://mattkeeter.com/links/) ou le flux RSS du blog (https://mattkeeter.com/atom.xml)

    • En parcourant le blog, je suis tombé là-dessus et j’ai trouvé ça vraiment excellent : https://www.mattkeeter.com/projects/machined-pen/the_plan.jp...
      Cela illustre bien une idée que j’ai en tête depuis longtemps. Et si le processus même de conception de ce plan de fabrication devenait une API CAD orientée utilisateur ? Quand on traite des problèmes de « fabrication » comme la menuiserie, la plomberie, la fabrication métallique ou l’usinage, on pense naturellement aux matières premières, aux outils disponibles et à la séquence d’opérations permettant d’obtenir le résultat souhaité.
      Or les API CAD actuelles, qu’il s’agisse d’outils CAD par code ou d’interfaces traditionnelles à la souris, ne fonctionnent pas ainsi : elles poussent à se concentrer sur la représentation de la forme finale plutôt que sur la manière dont on va réellement la fabriquer. Au bout du compte, l’important est de fabriquer l’objet, et la modélisation n’est qu’un outil pour y parvenir, mais cet outil prend trop de place au premier plan.
      Un flux de modélisation davantage ancré dans le réel semble avoir beaucoup d’avantages ; avec votre bien plus grande expérience du CAD, pensez-vous que ce concept ait un avenir, ou est-ce une impasse ?
      Pour ajouter aussi un retour sur le stylo : on pourrait serrer la barre dans un mandrin 3 mors, la tourner à une dimension adaptée à une pince, découper dans cette barre mise à dimension une ébauche pour le capuchon et deux pour le corps, puis effectuer le reste des opérations en la maintenant avec la pince afin de conserver la concentricité. En revanche, si les dimensions finales diffèrent de celles de la pince, cela entraîne un peu de gaspillage de matière.
    • Matt, j’ai une petite question. Je n’ai pas cherché très en profondeur, donc désolé si elle est trop générale ou naïve.
      Sur le plan des fonctionnalités, en quoi Fidget diffère-t-il de libfive ou d’Ao ?
    • Super ! Je me souviens avoir contribué au code de l’analyseur d’expressions des travaux de Knoll et al. 2009 cités dans l’article SIGGRAPH.
      Ce code ne faisait que transformer une expression unique conviviale en appels de fonctions imbriqués pour une bibliothèque IA en GLSL, sans aucune optimisation. Là, on va beaucoup plus loin.

  • Par hasard, j’étais justement en train de lire un autre excellent article de l’auteur : https://www.mattkeeter.com/projects/constraints/

  • Waouh, ça m’aurait été extrêmement utile quand j’ai créé mon propre moteur de rendu de surfaces implicites.
    Mon approche était similaire sur certains points (arithmétique d’intervalles) et différente sur d’autres. Elle était moins optimisée, et je générais directement du GLSL pour le fragment shader.
    Honnêtement, j’ai presque envie de tout jeter et de réimplémenter ça pour le remplacer. Je ne sais pas si je dois m’en réjouir ou m’en attrister.

    • Vous pouvez vous en réjouir ! Vous travaillez dans un domaine où l’on peut à la fois créer ses propres outils et utiliser ceux des autres.
      Vous pouvez reprendre des idées, ou utiliser cet outil tout en contribuant au projet. Dans tous les cas, c’est une bonne chose.

  • C’est formidable de voir apparaître un nouveau noyau CAD open source ! À la lecture de l’article, je n’ai pas compris s’il prend en charge l’export vers des formats courants comme STEP.
    Si c’est possible, ou si ça le devient, cela pourrait constituer une excellente base pour plusieurs bibliothèques CAD open source.

    • Malheureusement, l’export STEP n’est pas pris en charge. Les fichiers STEP utilisent une représentation interne complètement différente.
      La plupart des fichiers STEP représentent la géométrie comme un ensemble de surfaces, par exemple des NURBS rognées. Ces surfaces doivent former une variété sans trous, que l’on peut alors traiter comme un volume solide.
      Pour que cela fonctionne réellement, il faut un noyau de représentation par frontières (b-rep), et non les représentations fonctionnelles (f-reps) de Fidget. Écrire un tel noyau est un problème beaucoup plus difficile. Par exemple, l’intersection de deux surfaces NURBS n’a pas toujours une représentation sous forme fermée.
      En discutant avec quelqu’un du secteur, on m’a estimé que même pour une équipe l’ayant déjà fait auparavant, il faudrait environ 6 ingénieurs pendant 1 an pour produire un noyau b-rep correct.
      Si vous voulez en savoir plus, il se trouve que j’ai aussi écrit un visualiseur de fichiers STEP, qui inclut un noyau b-rep très loin d’un niveau industriel : https://www.mattkeeter.com/projects/foxtrot/

  • « Si l’on évalue par force brute 1024² pixels, l’interpréteur de bytecode prend 5,8 s, tandis que le backend JIT prend 182 ms, soit un facteur 31 plus rapide »
    « Avec un algorithme plus intelligent, le gain de vitesse est moins spectaculaire. L’approche par force brute n’exploite ni l’arithmétique d’intervalles ni la simplification de tape. L’implémentation de rendu optimisée de Fidget dessine cette image en 6 ms avec l’interpréteur de bytecode et en 4,6 ms avec le backend JIT ; l’amélioration n’est donc que d’environ 25 % »
    J’aime le fait que l’accent soit mis ici sur le fait que le backend JIT devient moins important après l’optimisation algorithmique, plutôt que sur le fait que l’optimisation algorithmique apporte un facteur 1000 en bytecode et 40 avec le JIT

  • Il y a quelques années, à l’université, j’ai un peu travaillé sur un simulateur de physique nucléaire, quelque chose comme de la modélisation de réacteurs nucléaires
    Le modèle géométrique reposait sur des surfaces implicites, en particulier les R-functions. min(x,y) en est aussi un exemple, avec des propriétés intéressantes, comme le fait d’être différentiable partout
    Une bonne introduction est celle-ci. C’est peut-être même la seule ressource en anglais : https://ecommons.cornell.edu/items/35ae0f68-1af5-4f28-8b8b-7...
    Cela fait un bon moment que j’ai quitté le domaine nucléaire, mais je suppose qu’on y utilise encore beaucoup de vieux code Fortran pour la modélisation. Fidget a un potentiel intéressant comme noyau pour de nouveaux packages de simulation

  • C’est un peu hors sujet, mais je cherche le meilleur logiciel de CAO basée sur le code
    J’ai essayé CadQuery, mais j’ai rencontré quelques problèmes. Y a-t-il quelque chose que vous recommanderiez pour l’impression 3D ?

    • J’ai fait une présentation sur la CAO basée sur le code et j’y ai couvert pas mal d’options
      https://youtu.be/0wn7vUmWQgg?si=9Rc1tvbiQgQDgQzd&t=2766
      J’en développe aussi une en Rust, mais il est encore difficile de dire qu’elle est prête
    • Il y a aussi build123d
      https://github.com/gumyr/build123d
    • Pour ceux qui ne veulent pas ouvrir la vidéo, voici la liste mentionnée dans un autre commentaire / dans la vidéo
      OpenSCAD, DSLCAD, CadQuery, Build123d, Cascade Studio, Declaracad, Replicad
    • replicad

  • Intéressant. J’avais déjà vu des articles et des démos sur ce type de surfaces implicites. C’était peut-être même le travail de l’auteur
    C’est impressionnant de voir quels modèles on peut créer avec un peu d’imagination, mais j’aimerais voir quelque chose de plus ambitieux que des exemples jouets
    Par exemple, est-il possible d’extruder des surfaces comme on peut le faire dans un noyau b-rep, ou d’importer du SVG / des polices pour en faire des solides ?
    J’aimerais vraiment voir un noyau open source rapide, qui prenne en charge ce genre de fonctionnalités tout en se parallélisant bien

  • Cela me fait beaucoup penser à https://bauble.studio/ d’Ian Henry

  • Moi aussi, j’avais envie d’essayer quelque chose de similaire avec des SDF, en manipulant un arbre abstrait pour générer des surfaces
    L’idée serait d’avoir un maillage ou un nuage de points cible, puis de chercher, par hill climbing / annealing, l’arbre qui correspond le mieux à la forme voulue

    • « A Unified Differentiable Boolean Operator with Fuzzy Logic » pourrait être intéressant
      https://arxiv.org/abs/2407.10954
      Il combine des feuilles différentiables (quadriques) au moyen d’opérations de type booléen différentiables pour construire un arbre CSG, ce qui permet de faire du hill climbing sur la forme entière