Fidget: ไลบรารีสำหรับประเมินนิพจน์คณิตศาสตร์ขนาดใหญ่

 (mattkeeter.com)
3 คะแนน โดย GN⁺ 2025-01-09 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • Fidget เป็นไลบรารี Rust สำหรับแทนค่า คอมไพล์ และประเมินนิพจน์คณิตศาสตร์ที่ประกอบด้วยอนุประโยคทางคณิตศาสตร์หลายร้อยถึงหลายพันรายการ โดยการใช้งานหลักคือเป็นแบ็กเอนด์สำหรับ พื้นผิวโดยนัย
  • พื้นผิวโดยนัยแยกด้านในกับด้านนอกด้วยฟังก์ชันระยะทางในรูป $f(x,y,z) \rightarrow d$ และเหมาะกับการดำเนินการ CSG รวมถึงการประเมินผลแบบขนาน
  • ฟรอนต์เอนด์มีไปป์ไลน์จากสคริปต์ Rhai ลงไปเป็น tree ทางคณิตศาสตร์, DAG, เทป SSA และ bytecode ที่ใช้รีจิสเตอร์ซ้ำได้
  • แบ็กเอนด์มี interpreter และคอมไพเลอร์ JIT และรองรับการประเมินผลแบบจุดเดียว, อาร์เรย์ SIMD, automatic differentiation แบบ forward-mode และ interval arithmetic
  • ในการประเมินผลแบบ brute force ขนาด 1024² ของนิพจน์ 7,867 รายการ JIT ลดเวลาจาก 5.8 วินาทีเหลือ 182ms แต่ในการเรนเดอร์แบบปรับแต่งแล้ว ความต่างแคบลงเหลือราว 25% คือ 6ms เทียบกับ 4.6ms

เป้าหมายของ Fidget และพื้นผิวโดยนัย

  • Fidget เป็นไลบรารีสำหรับ แทนค่า คอมไพล์ และประเมิน นิพจน์คณิตศาสตร์ขนาดใหญ่
    • มุ่งเป้าไปที่นิพจน์ที่จัดการกับอนุประโยคทางคณิตศาสตร์หลายร้อยถึงหลายพันรายการ
    • การใช้งานหลักคือเป็นแบ็กเอนด์สำหรับ พื้นผิวโดยนัย แต่ก็ใช้กับงานอื่นได้เช่นกัน
  • พื้นผิวโดยนัยคือนิพจน์ในรูป $f(x, y, z) \rightarrow d$ ที่คืนค่าระยะทางค่าเดียว $d$
    • ถ้า $d$ เป็นบวก จุด $(x,y,z)$ จะอยู่นอกโมเดล
    • ถ้า $d$ เป็นลบ จุดจะอยู่ภายในโมเดล
    • ทรงกลมรัศมี 1 สามารถแทนได้ด้วย $\sqrt{x^2 + y^2 + z^2} - 1$
  • Fidget โฟกัสที่ พื้นผิวโดยนัยแบบ closed-form ซึ่งประกอบนิพจน์จากการดำเนินการเลขคณิตพื้นฐาน
    • ต่างจากวิธีคำนวณค่าระยะทางด้วยโปรแกรมที่ Turing-complete อย่าง GLSL ใน pixel shader
    • ฟังก์ชันลักษณะนี้ใกล้เคียงกับ “assembly language ของ shape” ที่ representation ระดับสูงกว่า target ได้ง่าย มากกว่าจะเป็นสิ่งที่เขียนด้วยมือโดยตรง

จุดที่พื้นผิวโดยนัยได้เปรียบ

  • พื้นผิวโดยนัย กระชับและเหมาะกับการประเมินผลแบบขนาน
    • เหมาะกับการประเมินผลขนานขนาดใหญ่โดยใช้คำสั่ง SIMD หรือ GPU
  • การดำเนินการ CSG ง่ายขึ้น
    • สามารถแทนการดำเนินการอย่าง union และ intersection ซึ่งทำได้ยากใน mesh หรือ NURBS ได้ง่าย
    • union ของทรงกระบอกสองอันที่ซ้อนทับกันพอดีแทนได้ด้วย min(a, b)
  • สมการแบบ closed-form สร้างโอกาสในการปรับแต่ง
    • Fidget สามารถจับ execution trace ที่แสดงว่าเลือก branch ใดระหว่างการประเมินผลได้
    • ใช้ trace นี้เพื่อทำให้นิพจน์ง่ายขึ้นและลดต้นทุนการประเมินผลในภายหลัง

เหตุผลที่สร้างใหม่หลัง libfive

  • Fidget เป็นไลบรารีที่สร้างขึ้นใหม่เพื่อแทนที่เคอร์เนล libfive เดิม
    • libfive ประกอบด้วยโค้ดส่วนใหญ่เป็น C++ ประมาณ 40K บรรทัด
    • แม้แต่ผู้เขียนเดิมก็แก้ไขได้ยาก และมักเกิดกรณีที่พอกลับมาคอมไพล์ใหม่หลังผ่านไปไม่กี่เดือนแล้ว build พังจนต้องไปปรับ CMake
  • การ implement ใหม่นี้เป็นฐานสำหรับทดลองคำถามที่น่าสนใจในปัจจุบัน
    • ค้นหา API ที่เหมาะกับ implicit kernel และเปิดโอกาสถึงขั้นเปลี่ยนแบบ breaking compatibility
    • ทดลอง native JIT compilation เพื่อเพิ่มประสิทธิภาพโดยไม่ย้ายไป GPU
    • สามารถ cross-compile เป็น WebAssembly และสร้างเว็บเดโมที่เข้าถึงง่ายได้
  • Fidget เขียนด้วย Rust
    • คอมไพล์ได้ด้วย cargo build เพียงคำสั่งเดียว
    • cross-compile เป็น WebAssembly ได้อย่างเป็นธรรมชาติ
    • ระบบชนิดข้อมูลที่เข้มงวดและ memory safety ของ Rust ช่วยให้มั่นใจในการ refactor มากขึ้น

ฟรอนต์เอนด์: จากสคริปต์ถึง bytecode

  • ฟรอนต์เอนด์ของ Fidget มีไปป์ไลน์จากสคริปต์อินพุตลงไปถึง bytecode
    • ผู้ใช้ไม่จำเป็นต้องเดินตาม flow ทั้งหมดนี้เสมอไป และสามารถใช้ไลบรารีที่ขั้นกลางใดก็ได้

  • การสคริปต์ด้วย Rhai

    • Fidget รวม binding สำหรับ Rhai ซึ่งเป็นภาษา embedded scripting สำหรับ Rust
    • สามารถสร้างนิพจน์คณิตศาสตร์ในสคริปต์ได้ด้วย operator overloading
    • ค่าที่ส่งให้ draw คือ tree ทางคณิตศาสตร์ ที่แทนนิพจน์ที่สคริปต์สร้างขึ้น

  • Tree, graph และเทป SSA

    • tree ทางคณิตศาสตร์จะถูกกำจัดความซ้ำซ้อนแล้วแปลงเป็น directed acyclic graph (DAG)
    • ใช้ topological sort เพื่อ flatten graph ให้เป็นโค้ดเส้นตรง
    • โค้ดนี้อยู่ในรูป SSA(single static assignment)
    • มีรีจิสเตอร์จำลอง rX จำนวนเท่าใดก็ได้ และแต่ละรีจิสเตอร์ถูกเขียนเพียงครั้งเดียว
    • เทป SSA ก็สามารถประเมินผลได้ แต่แต่ละ operation ต้องใช้ตำแหน่งหน่วยความจำ ทำให้ขยายสเกลได้ไม่ดี
    • เพราะรีจิสเตอร์จำลองไม่ถูกนำกลับมาใช้ซ้ำ

  • Bytecode และการจัดสรรรีจิสเตอร์

    • เพื่อเพิ่มประสิทธิภาพการประเมินผล จะ map รีจิสเตอร์จำลองไปยัง รีจิสเตอร์จริง ที่ใช้ซ้ำได้
    • เทป SSA ตัวอย่างสามารถบีบอัดให้เหลือรีจิสเตอร์ที่ใช้ซ้ำได้ 6 ตัว
    • การจัดสรรรีจิสเตอร์ใช้อัลกอริทึม simple algorithm ที่เคยแนะนำไว้ก่อนหน้านี้
    • เป็นอัลกอริทึมแบบ single pass และให้ความสำคัญกับความเร็วและ determinism มากกว่าประสิทธิภาพ
    • bytecode interpreter ใช้รีจิสเตอร์ 256 ตัว
    • index ของรีจิสเตอร์เก็บใน u8
    • หากรีจิสเตอร์ไม่พอ ตัวจัดสรรจะใส่ LOAD และ STORE เพื่อเขียนลงหน่วยความจำเสริมที่ใช้ index แบบ u32

แบ็กเอนด์: วิธีประเมินผลและการทำให้ง่าย

  • แบ็กเอนด์ของ Fidget แยกจากฟรอนต์เอนด์ด้วย trait Function, TracingEvaluator, และ BulkEvaluator
    • อัลกอริทึมไม่ต้องผูกแน่นกับ implementation ของ tree ทางคณิตศาสตร์ และสามารถทำงานกับ Function ทั่วไปได้
    • ปัจจุบันยังไม่มี implementation ของ trait Function ที่ไม่ใช่ tree ทางคณิตศาสตร์
  • ตอนนี้วิธีประเมินผล tree ทางคณิตศาสตร์มีสองแบบ
    • bytecode interpreter
    • ฟังก์ชันที่คอมไพล์ด้วย JIT

  • โหมดการประเมินผล

    • Fidget มีโหมดการประเมินผลสี่แบบ
      • ประเมินผลจุดเดียว
      • ประเมินผลแบบ SIMD ที่อิงอาร์เรย์
      • automatic differentiation แบบ forward-mode
      • interval arithmetic
    • ในการประเมินผลแบบ bulk ผู้ใช้ให้ array ของค่าอินพุตและรับ array ของเอาต์พุต
    • แบ็กเอนด์ JIT สร้างโค้ด SIMD เพื่อประมวลผลครั้งละ 4 องค์ประกอบบน AArch64 และครั้งละ 8 องค์ประกอบบน x86-64

  • Automatic differentiation แบบ forward-mode

    • evaluator สำหรับอนุพันธ์คำนวณค่าและอนุพันธ์ย่อยได้สูงสุด 3 ค่า
    • สำหรับพื้นผิวโดยนัย โดยทั่วไปจะคำนวณ $(f, \partial f/\partial x, \partial f/\partial y, \partial f/\partial z)(x,y,z)$
    • เมื่ออยู่บนพื้นผิวและ $f(x,y,z)=0$ อนุพันธ์ย่อยเป็นค่าประมาณที่ดีของ surface normal
    • ค่านี้สามารถใช้กับ shading ได้
    • การประเมินผลทำด้วย automatic differentiation แบบ forward-mode
    • แนบค่าอนุพันธ์เข้ากับค่ารีจิสเตอร์และใช้ chain rule ในแต่ละขั้น
    • JIT evaluator เก็บค่าและอนุพันธ์ 3 ค่าไว้ในรีจิสเตอร์ 4 x f32 หนึ่งตัว

  • Interval arithmetic

    • interval arithmetic ประเมินช่วงของค่าอินพุตแทนค่าอินพุตเดี่ยว
    • ตัวอย่างเช่น ใช้ $1 \le x \le 5$ แทน $x=1$ ได้
    • เอาต์พุตก็จะเป็นช่วงเช่น $2 \le f(x,y,z) \le 20$
    • ผลลัพธ์ของ interval arithmetic เป็นแบบ conservative
      • อาจไม่ครอบช่วงจริงของฟังก์ชันได้แนบสนิท
      • แต่จะรวมเอาต์พุตที่เป็นไปได้ทั้งหมดภายในช่วงอินพุตที่กำหนดไว้
    • ในการประเมินผลพื้นผิวโดยนัย interval arithmetic เป็นองค์ประกอบสำคัญ
    • เมื่อประเมินพื้นที่เชิงปริภูมิเป็นช่วง $x,y,z$ แล้วช่วงเอาต์พุตมากกว่า 0 อย่างชัดเจน ทั้งพื้นที่นั้นอยู่นอกรูปทรง จึงไม่จำเป็นต้องดูต่อ

  • การทำให้ง่ายตาม trace

    • evaluator ของ interval arithmetic จับ trace การทำงานได้ด้วย
    • ใน min(a,b) หาก $0 \le a \le 1$ และ $4 \le b \le 5$ แล้ว a เล็กกว่าเสมอ จึงทำให้นิพจน์ง่ายเหลือ a ได้
    • operation min และ max แต่ละตัวจะบันทึกอาร์กิวเมนต์ที่มีผลต่อผลลัพธ์
    • บันทึกการเลือกเป็นหนึ่งใน ซ้าย, ขวา, หรือทั้งคู่
    • ใช้การเลือกนี้ในการทำให้ฟังก์ชันเดิมง่ายขึ้น
    • Fidget รองรับการทำให้ง่ายของ min·max ที่ใช้ใน CSG และ operation เชิงตรรกะ and·or
    • รูปทรงที่ไม่มี CSG หรือตรรกะจะไม่ได้ประโยชน์จากการทำให้ง่าย
    • ถึงอย่างนั้นก็ยังมีข้อดีจากการข้ามพื้นที่ว่างหรือพื้นที่ที่เต็มแน่นโดยอิง interval arithmetic

การผสาน interval arithmetic กับการทำให้เทปเรียบง่าย

  • การผสาน interval arithmetic กับการทำให้เทปเรียบง่ายเป็นเทคนิคสำคัญที่ทำให้นิพจน์ขนาดใหญ่จัดการได้ง่ายขึ้น
    • ข้ามบริเวณของพื้นที่ที่ไม่ active และยังทำให้การประเมินบริเวณ active ที่เหลือมีต้นทุนถูกลงด้วย
  • การทำให้เทปเรียบง่ายคือวิธีคำนวณ นิพจน์ที่ถูกทำให้ง่าย ซึ่งใช้ได้เฉพาะในบริเวณของพื้นที่หนึ่ง ๆ
    • ต่างจากโครงสร้างเร่งความเร็ว ray tracing ทั่วไป ตรงที่เหมือนกับสร้างโครงสร้างเร่งความเร็วแบบไดนามิกระหว่างการประเมิน
  • ในการ rasterization ต้นทุนของการประเมินแบบ interval จะถูกกระจายไปยังหลายพิกเซล
    • การประเมิน interval ของพื้นที่พิกเซล $N \times N$ เป็น $O(T)$ ซึ่งแปรผันตามความยาวเทป $T$
    • ไม่ขึ้นกับจำนวนพิกเซล
  • เมื่อไล่ลงไปถึงพื้นที่ขนาดเล็กแล้วประเมินรายพิกเซล จะใช้เทปที่สั้นลงมาก
    • ในพื้นที่ $M \times M$ ต้นทุนคือ $O(T' \times M \times M)$
    • โดยที่ $T' < T$
  • ตัวอย่างการเรนเดอร์ hello, world แบบ 2D ขนาด 256×256 มีเทปต้นฉบับ 254 ข้อ
    • ประเมิน interval กับไทล์พิกเซล 32×32 จำนวน 64 ไทล์
      • ข้ามพื้นที่ว่าง เหลือไทล์ active 47 ไทล์
      • ความยาวเทปเฉลี่ยของไทล์ active ลดลงเหลือ 73 ข้อ
    • แบ่งย่อยแต่ละไทล์เป็นไทล์พิกเซล 8×8 จำนวน 16 ไทล์
    • ประเมิน interval กับไทล์พิกเซล 8×8 จำนวน 752 ไทล์
      • ข้ามพื้นที่ว่าง เหลือไทล์ active 351 ไทล์
      • ความยาวเทปเฉลี่ยของไทล์ active ลดลงเหลือ 20 ข้อ
    • ไทล์ 8×8 ที่เหลือ 351 ไทล์จะประเมินแบบรายพิกเซล
  • ณ จุดที่ประเมินรายพิกเซล เทปจะ สั้นกว่าความยาวเดิมมากกว่า 10 เท่า

การคอมไพล์ JIT

  • bytecode interpreter เป็นลูปที่แน่น แต่มี overhead ที่หลีกเลี่ยงไม่ได้
    • การ dispatch คำสั่งเป็น branch เดียวที่คาดการณ์ได้ยาก
    • แต่ละคำสั่งอ่านและเขียนหน่วยความจำผ่านช่อง register ของตัวประเมิน VM
  • Fidget มี JIT compiler ที่ลดระดับ bytecode เป็น machine code เพื่อประสิทธิภาพสูงสุด
    • คำสั่งเครื่องเป็นโค้ดเส้นตรงที่ไม่มีการ dispatch
    • ใช้ physical register โดยตรง จึงลดการอ่าน·เขียนหน่วยความจำ
  • อินพุตของ JIT คือเทป bytecode แบบเดิม
    • แทนที่จะใช้ register 255 ตัวพื้นฐานของ VM จะวางแผนให้เข้ากับ physical register 12 ตัวบน x86-64 และ 24 ตัวบน AArch64
    • บน AArch64 จะ map ไปที่ v8-31 และบน x86-64 จะ map ไปที่ xmm4-15
  • เขียน snippet assembly เองสำหรับแต่ละชุดผสมของ opcode × ชนิดข้อมูล × สถาปัตยกรรม
    • patch physical register ที่ต้องการลงใน snippet แล้วคัดลอกไปยังพื้นที่หน่วยความจำที่ mmap ไว้
  • ในระดับ Rust จะ cast หน่วยความจำที่สร้างขึ้นเป็น function pointer แล้วเรียกใช้
    • อินพุตและเอาต์พุตจะถูกส่งโดย cast Rust slice เป็น raw pointer

  • ตัวเลขประสิทธิภาพ

    • ในตัวอย่างซับซ้อนที่ประกอบด้วยนิพจน์ 7867 รายการ การประเมินแบบ brute force ที่ 1024² พิกเซลได้ประโยชน์จาก JIT มาก
    • bytecode interpreter: 5.8 วินาที
    • JIT backend: 182ms
    • เร็วขึ้น: 31 เท่า
    • brute force ไม่ได้ใช้ interval arithmetic หรือการทำให้เทปเรียบง่าย
    • หากใช้อัลกอริทึมที่ฉลาดขึ้น ความต่างจะลดลง
    • implementation การเรนเดอร์แบบปรับแต่งแล้วของ Fidget วาดภาพเดียวกันด้วย bytecode interpreter ใน 6ms และด้วย JIT backend ใน 4.6ms
    • กรณีนี้ปรับปรุงได้ประมาณ 25%

การเรนเดอร์และการสร้าง mesh

  • การเรนเดอร์

    • การเรนเดอร์โมเดลทั้งหมดใช้อัลกอริทึมของ fidget::render
    • การเรนเดอร์ใช้อัลกอริทึมหลักจากบทความ SIGGRAPH
    • เรนเดอร์พื้นที่ขนาดใหญ่ด้วย interval arithmetic
    • สร้างเทปที่สั้นลงบนพื้นฐานการติดตาม
    • พื้นที่ที่กำกวมจะถูกแบ่งย่อยและประมวลผลแบบ recursive
    • ในการเรนเดอร์ 3D จะคำนวณ normal ด้วย partial derivative
    • โมเดลถูกแปลงด้วยเมทริกซ์ homogeneous 4×4 ระหว่างกระบวนการเรนเดอร์
    • รองรับ perspective transform
    • ผลลัพธ์การเรนเดอร์โดยทั่วไปคือภาพสองภาพ: heightmap และ normal รายพิกเซล
    • ผลลัพธ์สามารถวาดด้วยเทคนิค deferred rendering มาตรฐานอย่าง SSAO ได้

  • การสร้าง mesh

    • Fidget implements Manifold Dual Contouring สำหรับการสร้าง mesh
    • implementation นี้ควรสร้าง mesh ที่มีคุณสมบัติต่อไปนี้เสมอ
      • watertight
      • manifold
      • รักษา edge และ corner ที่คมไว้
      • มีคุณสมบัติ adaptive ที่ทำให้ความหนาแน่นของสามเหลี่ยมต่ำลงในบริเวณที่ค่อนข้างเรียบเป็นส่วนใหญ่
    • ยังมีข้อบกพร่องที่ทราบอยู่ด้วย
      • ไม่ได้รักษาฟีเจอร์ที่บางไว้เสมอไป
      • mesh ผลลัพธ์อาจมีการตัดกันเอง
      • การจัดวาง vertex เปราะบางต่อ adversarial cases
    • การสร้าง mesh ที่ดีสำหรับ implicit surface ใด ๆ ยังคงเป็นปัญหาที่ยังแก้ไม่ตก
    • Manifold Dual Contouring ไม่สมบูรณ์แบบ แต่อยู่ที่จุดสมดุลระหว่างความเรียบง่ายกับประสิทธิภาพ

เดโมและเว็บ GUI

  • Fidget repository มี demos หลายรายการ
    • เว็บ GUI ถูกนำเสนอเป็นเดโมที่น่าสนใจที่สุด
    • ยังมี fidget-cli ซึ่งเป็น CLI เรียบง่าย และ fidget-viewer ซึ่งเป็น native script viewer
  • เว็บเดโมผสานเทคโนโลยีเว็บหลายอย่างเข้าด้วยกัน
    • GUI เขียนด้วย TypeScript
    • Fidget crate ถูกใช้เป็นไลบรารี โดยไม่ได้เป็นตัวขับ event loop
    • text editor ใช้ CodeMirror
    • ต้องใช้ bundler เพื่อใช้ Node module จึงเลือก webpack
    • การประเมินสคริปต์และการเรนเดอร์ทำใน web worker เพื่อไม่ให้บล็อก main event loop
    • ใช้ wasm-bindgen-rayon เพื่อทำให้การเรนเดอร์เป็น parallelization สำหรับหลีกเลี่ยงการไม่มี std::thread ในเบราว์เซอร์
    • worker กับ main event loop แชร์หน่วยความจำกัน
    • เมื่อผู้ใช้ป้อนข้อมูลใหม่ สามารถยกเลิกการเรนเดอร์ที่ใช้เวลานานได้ด้วย flag Arc<AtomicBool> ที่แชร์กับ worker
  • กระบวนการทำให้หลายองค์ประกอบทำงานร่วมกันนั้นยาก
    • แต่ละองค์ประกอบมีตัวอย่างที่ทำงานได้ แต่ bundler, การตั้งค่า, server ฯลฯ ต่างกัน
    • bug fix ล่าสุดของ wasm-bindgen เปลี่ยนพฤติกรรมที่ wasm-bindgen-rayon ต้องใช้ จึงต้อง pin เวอร์ชันเก่าไว้
  • เว็บเดโมทำงานบนโทรศัพท์มือถือได้ด้วย
    • เนื่องจากใช้ mouse event จึงไม่รองรับการควบคุมกล้อง

ความตึงเครียดระหว่างเดโมกับไลบรารี

  • Fidget เป็น ไลบรารี เป็นหลัก
    • รูปแบบการใช้งานที่ตั้งใจไว้คือให้ผู้ใช้ embed เป็น infrastructure ในโปรเจกต์ของตนเอง มากกว่าจะใช้เดโมเป็นเครื่องมือ CAD จริง
  • แต่คนที่ลองเล่นเดโมมีจำนวนมากกว่าคนที่สร้างเครื่องมือด้วยไลบรารีมาก
    • บางคนถึงขั้นใช้เดโมในงานออกแบบ
    • จึงมีความตึงเครียดระหว่างการปรับปรุงเดโมเพื่อกลุ่มผู้ใช้เดโมที่ใหญ่กว่า กับการปรับปรุงไลบรารีเพื่อกลุ่มผู้สร้างเครื่องมือที่เล็กกว่า
  • การดูแลทั้ง kernel และ CAD UI เต็มรูปแบบพร้อมกันเป็นเรื่องยาก และขอบเขตของเดโมก็ค่อย ๆ ลดลง
    • แม้แต่เดโมแบบ “ขั้นต่ำ” อย่างเว็บ editor ก็ยังเป็นโปรเจกต์ขนาดไม่น้อย
  • แผนมีสามทิศทาง
    • ติดตามสิ่งที่สนใจต่อไปเพื่อรักษาแรงจูงใจและสมาธิ
    • รับข้อเสนอแนะจากผู้ใช้เครื่องมือ แต่ตั้งความคาดหวังให้อยู่ในระดับสมเหตุสมผล
    • ในอุดมคติ จะให้ความสำคัญกับ feedback จากผู้สร้างเครื่องมือที่จะช่วยลดภาระของเดโม

ความเป็นไปได้ในอนาคต

  • แบ็กเอนด์ GPU

    • แบ็กเอนด์ GPU เป็นการต่อยอดที่เป็นธรรมชาติ
    • มีงานวิจัย SIGGRAPH ที่เกี่ยวข้องอยู่แล้ว
    • มีการทำไว้แล้วในบรานช์ wgpu-bytecode
    • เมื่อวัดบนแล็ปท็อป Apple M1 Max ประสิทธิภาพไม่ได้ดึงดูดเป็นพิเศษ
    • ลูปของตัวแปล bytecode ดูไม่มีประสิทธิภาพอย่างมาก
    • ยังอยู่ระหว่างตรวจสอบสาเหตุรากเหง้าต่อไป

  • การสร้างเมชที่ดีกว่าเดิม

    • สำหรับผู้ใช้ไลบรารีอย่างจริงจัง การสร้างเมชเป็นปัญหาใหญ่
    • Fidget ใช้กลยุทธ์การสร้างเมชแบบเดียวกับ libfive แต่ไม่มีการปรับจูนรายละเอียดหลายอย่างที่ทำให้ libfive ทำงานได้ทนทานกว่า
    • เนื่องจากไม่พอใจกับตัวเลือกที่มีอยู่ในปัจจุบัน จึงไม่ได้ใช้เวลากับส่วนนี้มากนัก
    • ต้องการใช้อัลกอริทึมสร้างเมชที่ bulletproof มากกว่าการทาสีทับบน dual contouring
    • ยังไม่มีวิธีในเอกสารวิชาการหรือทางเลือกที่พัฒนาขึ้นเองซึ่งตอบโจทย์ข้อกำหนด
    • อาจปรับจูนบางส่วนตามความต้องการของผู้ใช้ แต่ก็มีแผนจะค้นหาตัวเลือกที่ดีกว่าต่อไป

  • ไลบรารี shape และ transform มาตรฐาน

    • ตลอดซอฟต์แวร์หลายรุ่นที่ผ่านมา ได้พอร์ตไลบรารี shape มาตรฐานของ Fab Modules ไปยังเครื่องมือใหม่ ๆ
    • งานนี้น่าเบื่อ แต่ให้รากฐานที่ค่อนข้างเป็นมาตรฐานสำหรับการทำโมเดลระดับสูง
    • ใน libfive แต่ละ shape เขียนด้วย C++ และสร้าง binding สำหรับ C, Python, Scheme โดยอัตโนมัติจากไฟล์ header
    • README อธิบายว่า libfive_stdlib.h เป็นทั้ง C header และเอกสารแบบมีโครงสร้างที่ helper script ใช้ parse
    • แนวทางของ Fidget ยังอยู่ระหว่างการหารือ
    • การหารือที่กำลังดำเนินอยู่ดูได้ที่ fidget#145
    • มีความเป็นไปได้ที่จะนำไลบรารี Fab shapes มาไว้ใน Rust
    • โค้ดที่สง่างามกว่าโดยใช้ GLSL vector อย่างเช่น ไลบรารี primitives ของ Inigo Quilez ก็เป็นจุดอ้างอิงเช่นกัน

  • binding สำหรับภาษาระดับสูง

    • ปัจจุบัน Fidget มี binding สำหรับ Rhai เท่านั้น
    • Rhai ถูกเลือกเพราะเป็นหนึ่งในภาษา scripting แบบ Rust-first ที่มีความ成熟แล้ว
    • มีข้อดีคือผสานรวมได้ง่ายและคอมไพล์เป็น WebAssembly ได้
    • ผู้ใช้จำนวนมากอาจชอบ binding สำหรับ Python หรือ Node มากกว่า
    • วิธีทำ binding ก็ยังเป็นคำถามที่เหลืออยู่
    • C API ช่วยให้ใช้ไลบรารี FFI ของแต่ละภาษาได้ แต่ในงานออกแบบแบบ Rust-first จะให้ความรู้สึกเหมือนถอยลงไปหนึ่งระดับ
    • หากมีไลบรารีมาตรฐานแล้ว คงดีถ้าสามารถ expose ไปยังแต่ละ binding โดยอัตโนมัติพร้อม usability ที่เหมาะสม เช่น docstring และอาร์กิวเมนต์ค่าเริ่มต้น

สถานะการเปิดเผยต่อสาธารณะและวิธีใช้งาน

  • README ของ Fidget อธิบายสถานะหลังเปิดตัวช่วงแรกว่าเป็น “quietly public”
    • มีการเผยแพร่ 19 เวอร์ชันบน crates.io
    • ผู้ใช้บางรายเริ่มสร้างบางอย่างบน Fidget แล้ว
  • ตอนนี้ Fidget เปลี่ยนเข้าสู่ขั้น “loudly public” แล้ว
  • ซอร์สโค้ดอยู่บน Github
    • ในโปรเจกต์ Rust สามารถเพิ่มได้ด้วย cargo add fidget
    • ไลเซนส์เป็น MPL 2.0 ซึ่งเป็น copyleft แบบอ่อน
    • ถูกนำเสนอว่าเป็นไลเซนส์ที่เป็นมิตรต่อทั้ง OSS และการใช้งานเชิงพาณิชย์

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2025-01-09
ความคิดเห็นจาก Hacker News

  • สวัสดีครับ นี่เป็นโปรเจกต์ของผมเอง :)
    เหตุผลที่ผมชอบสาขานี้ใน CS เป็นพิเศษ คือมันมีองค์ประกอบที่เหมาะกับทุกคนอยู่ครบ ทั้ง โครงสร้างข้อมูลและอัลกอริทึม, งานประสิทธิภาพระดับล่าง, คอมไพเลอร์, การเรนเดอร์/คอมพิวเตอร์กราฟิกส์, UI/UX สำหรับเครื่องมือออกแบบ, การเขียนโปรแกรม GPGPU และอื่น ๆ
    ผมจะตอบคำถามที่เห็นในเธรดนี้ แต่ถ้าอยากติดตามอัปเดตเพิ่มเติมก็ติดตามได้ทางโซเชียลมีเดีย (https://mattkeeter.com/links/) หรือฟีด RSS ของบล็อก (https://mattkeeter.com/atom.xml)

    • ผมไปเจอสิ่งนี้ระหว่างอ่านบล็อก แล้วชอบมาก: https://www.mattkeeter.com/projects/machined-pen/the_plan.jp...
      มันแสดงแนวคิดที่ผมมีอยู่ในหัวมานานได้ดีมาก จะเป็นอย่างไรถ้ากระบวนการออกแบบแผนการผลิตนี้เองกลายเป็น CAD API สำหรับผู้ใช้? เวลาเราจัดการปัญหาเรื่อง “การทำของ” อย่างงานไม้ งานท่อ งานโลหะ หรือการกลึงกัด เรามักจะคิดอย่างเป็นธรรมชาติถึงวัตถุดิบ เครื่องมือที่มี และลำดับงานเพื่อให้ได้ผลลัพธ์ที่ต้องการ
      แต่ CAD API ปัจจุบัน ไม่ว่าจะเป็นเครื่องมือ CAD แบบเขียนโค้ดหรืออินเทอร์เฟซแบบดั้งเดิมที่ใช้เมาส์ ไม่ได้ทำงานแบบนี้ และกลับทำให้เราโฟกัสที่การแสดงรูปทรงสำเร็จรูปมากกว่าว่าจะสร้างมันขึ้นมาจริง ๆ อย่างไร สุดท้ายสิ่งสำคัญคือการทำชิ้นงานขึ้นมา ส่วนการโมเดลเป็นเพียงเครื่องมือช่วยเท่านั้น แต่เครื่องมือนั้นกลับเด่นออกมามากเกินไป
      เวิร์กโฟลว์การโมเดลที่ ยึดโยงกับโลกจริงมากกว่า ดูเหมือนจะมีข้อดีมากมาย ในฐานะคนที่มีประสบการณ์ด้าน CAD มากกว่ามาก คุณคิดว่าแนวคิดนี้มีทางพัฒนาต่อได้ไหม หรือเป็นทางตัน?
      ขอเสริมฟีดแบ็กเรื่องปากกาด้วย: ถ้าจับแท่งวัสดุด้วย 3-jaw chuck แล้วกลึงให้ได้ขนาดที่พอดีกับ collet จากนั้นตัด blank สำหรับฝา 1 ชิ้นและตัวด้าม 2 ชิ้นจากแท่งที่ปรับขนาดแล้ว แล้วใช้ collet จับงานที่เหลือ ก็จะรักษาความร่วมศูนย์ได้ แต่ถ้าขนาดสุดท้ายต่างจากขนาด collet ก็จะมีวัสดุเหลือทิ้งเพิ่มขึ้นเล็กน้อย
    • Matt ขอถามสั้น ๆ หน่อยครับ ผมอาจยังค้นมาไม่พอ ถ้าคำถามนี้กว้างหรือโง่เกินไปก็ขออภัย
      ในแง่ฟีเจอร์ Fidget แตกต่างจาก libfive หรือ Ao อย่างไร?
    • เจ๋งมากครับ! ผมจำได้ว่าเคยมีส่วนร่วมกับ โค้ด expression parser ของงาน Knoll et al. 2009 ที่ถูกอ้างในเปเปอร์ SIGGRAPH
      โค้ดนั้นแค่แปลงนิพจน์เดี่ยวที่เป็นมิตรกับผู้ใช้ให้เป็นการเรียกฟังก์ชันซ้อนกันสำหรับไลบรารี IA ใน GLSL โดยไม่มีการเพิ่มประสิทธิภาพใด ๆ เลย อันนี้ไปไกลกว่านั้นมาก

  • บังเอิญว่าผมเพิ่งกำลังอ่านบทความดี ๆ อีกชิ้นของผู้เขียนอยู่พอดี: https://www.mattkeeter.com/projects/constraints/

  • ว้าว ถ้าผมรู้จักสิ่งนี้ตอนทำ implicit surface renderer ของตัวเองคงมีประโยชน์มหาศาล
    แนวทางของผมก็คล้ายกันในบางแง่ (interval arithmetic) และต่างกันในบางแง่ มันถูกปรับแต่งประสิทธิภาพน้อยกว่า และผมสร้าง GLSL สำหรับ fragment shader โดยตรง
    พูดตามตรง ผมยังรู้สึกอยากทิ้งของเดิมทั้งหมดแล้วนำอันนี้ไปอิมพลีเมนต์ใหม่แทนเลย ไม่รู้ว่าควรดีใจหรือเสียใจดี

    • ดีใจได้เลยครับ! เพราะคุณกำลังทำงานในสาขาที่ทั้งสร้างเครื่องมือเองได้และใช้เครื่องมือที่คนอื่นสร้างได้
      คุณจะหยิบไอเดียไปใช้ หรือใช้สิ่งนี้พร้อมกับมีส่วนร่วมกับโปรเจกต์ก็ได้ ไม่ว่าทางไหนก็ยอดเยี่ยมทั้งนั้น

  • การมี CAD kernel โอเพนซอร์สตัวใหม่ออกมานี่สุดยอดมาก! อ่านจากบทความอย่างเดียวผมยังไม่แน่ใจว่ารองรับการส่งออกเป็นฟอร์แมตทั่วไปอย่าง STEP หรือไม่
    ถ้าทำได้ หรือถ้าทำได้ในอนาคต ก็น่าจะเป็นรากฐานที่ยอดเยี่ยมสำหรับไลบรารี CAD โอเพนซอร์สหลายตัว

    • น่าเสียดายที่ไม่รองรับ การส่งออก STEP ครับ เพราะไฟล์ STEP ใช้การแทนภายในที่ต่างออกไปโดยสิ้นเชิง
      ไฟล์ STEP ส่วนใหญ่แทนรูปทรงเป็นชุดของพื้นผิว เช่น trimmed NURBS พื้นผิวเหล่านี้ต้องประกอบกันเป็นแมนิโฟลด์ที่ไม่มีช่องว่าง แล้วจึงสามารถถือเป็นปริมาตรของแข็งได้
      ถ้าจะทำให้ใช้งานได้จริง จะต้องมี เคอร์เนล boundary representation (b-reps) ไม่ใช่การแทนด้วยฟังก์ชัน (f-reps) ของ Fidget การเขียนเคอร์เนลแบบนี้เป็นปัญหาที่ยากกว่ามาก ตัวอย่างเช่น จุดตัดของพื้นผิว NURBS สองผืนก็ไม่ได้มีรูปแบบการแทนแบบ closed form เสมอไป
      ตอนคุยกับคนในอุตสาหกรรม เขาประเมินว่าแม้จะเป็นทีมที่เคยทำมาก่อน ก็ต้องใช้วิศวกร 6 คนประมาณ 1 ปีเพื่อทำ b-rep kernel ที่ดีพอ
      ถ้าอยากรู้เพิ่มเติม บังเอิญว่าผมเคยเขียนตัวดูไฟล์ STEP ด้วย ซึ่งมี b-rep kernel ที่ยังห่างไกลจากระดับใช้งานอุตสาหกรรมรวมอยู่ด้วย: https://www.mattkeeter.com/projects/foxtrot/

  • “ถ้าประเมินแบบ brute force สำหรับพิกเซล 1024² ตัว bytecode interpreter จะใช้เวลา 5.8 วินาที ส่วน JIT backend ใช้เวลา 182ms จึงเร็วขึ้น 31 เท่า”
    “ถ้าใช้อัลกอริทึมที่ฉลาดขึ้น ความเร็วที่เพิ่มขึ้นจะไม่หวือหวาเท่าเดิม วิธี brute force ไม่ได้ใช้ interval arithmetic หรือ tape simplification การเรนเดอร์ที่ปรับให้เหมาะสมของ Fidget วาดภาพนี้ได้ใน 6ms ด้วย bytecode interpreter และ 4.6ms ด้วย JIT backend ดังนั้นการปรับปรุงจึงมีเพียงราว 25%”
    ผมชอบตรงที่เน้นว่า JIT backend มีความสำคัญน้อยลงหลังจากปรับอัลกอริทึมแล้ว แทนที่จะไปเน้นว่าการปรับอัลกอริทึมช่วยให้ bytecode ดีขึ้น 1000 เท่า และ JIT ดีขึ้น 40 เท่า

  • เมื่อหลายปีก่อน สมัยอยู่มหาวิทยาลัย ผมเคยทำงานเล็กน้อยกับซิมูเลเตอร์ฟิสิกส์นิวเคลียร์ หรือพูดอีกอย่างคือพวกการจำลองโมเดลเตาปฏิกรณ์นิวเคลียร์
    โมเดลเรขาคณิตนั้นอิงกับ พื้นผิวโดยนัย โดยเฉพาะ R-functions ตัวอย่างหนึ่งคือ min(x,y) ซึ่งมีคุณสมบัติน่าสนใจ เช่น หาอนุพันธ์ได้ทุกจุด
    เอกสารแนะนำที่ดีคืออันนี้ บางทีอาจเป็นเอกสารเดียวที่เป็นภาษาอังกฤษด้วยซ้ำ: https://ecommons.cornell.edu/items/35ae0f68-1af5-4f28-8b8b-7...
    ผมออกจากวงการนิวเคลียร์มานานแล้ว แต่คิดว่างาน modeling น่าจะยังใช้ โค้ด Fortran เก่า ๆ กันอยู่มาก Fidget มีศักยภาพที่น่าสนใจในฐานะเคอร์เนลสำหรับแพ็กเกจซิมูเลชันรุ่นใหม่

  • ขอเปลี่ยนประเด็นนิดหน่อย ผมกำลังมองหาซอฟต์แวร์ CAD แบบเขียนโค้ดที่ดีที่สุดอยู่
    เคยลอง CadQuery แล้วเจอปัญหาบางอย่าง มีตัวไหนแนะนำสำหรับงานพิมพ์ 3D ไหม?

    • ผมเคยนำเสนอเรื่อง CAD แบบเขียนโค้ด และพูดถึงตัวเลือกไว้ค่อนข้างมาก
      https://youtu.be/0wn7vUmWQgg?si=9Rc1tvbiQgQDgQzd&t=2766
      ผมกำลังพัฒนาตัวหนึ่งด้วย Rust อยู่เหมือนกัน แต่ยังพูดได้ยากว่าพร้อมใช้งานแล้ว
    • ยังมี build123d ด้วย
      https://github.com/gumyr/build123d
    • สำหรับคนที่ไม่อยากเปิดวิดีโอ รายชื่อที่มาจากคอมเมนต์/วิดีโออื่นมีดังนี้
      OpenSCAD, DSLCAD, CadQuery, Build123d, Cascade Studio, Declaracad, Replicad
    • replicad

  • น่าสนใจครับ ผมเคยเห็นเปเปอร์และเดโมเกี่ยวกับ พื้นผิวโดยนัย แบบนี้มาก่อน บางทีอาจเป็นงานของผู้เขียนคนนี้ก็ได้
    ถ้าใช้จินตนาการก็ประทับใจว่ามันสร้างโมเดลอะไรได้บ้าง แต่ผมอยากเห็นอะไรที่ใหญ่กว่าตัวอย่างเล่น ๆ
    เช่น จะ extrude พื้นผิวได้เหมือนที่ทำได้ใน b-rep kernel หรือจะนำเข้า SVG/ฟอนต์แล้วทำเป็น solid ได้ไหม?
    ผมอยากเห็น kernel โอเพนซอร์สที่เร็ว รองรับความสามารถแบบนี้ และ parallelize ได้ดีจริง ๆ

  • ทำให้นึกถึง https://bauble.studio/ ของ Ian Henry มาก

  • ผมเองก็เคยอยากลองทำอะไรคล้าย ๆ กัน คือใช้ SDF จัดการกับ abstract tree สำหรับสร้างพื้นผิว
    แนวคิดคือมี mesh หรือ point cloud เป้าหมาย แล้วใช้ hill climbing/annealing เพื่อค้นหา tree ที่เข้ากับรูปทรงที่ต้องการได้ดี

    • “A Unified Differentiable Boolean Operator with Fuzzy Logic” น่าจะน่าสนใจ
      https://arxiv.org/abs/2407.10954
      โดยนำ leaf ที่หาอนุพันธ์ได้ (พื้นผิวกำลังสอง) มาประกอบกันด้วยการดำเนินการคล้าย Boolean ที่หาอนุพันธ์ได้ เพื่อสร้าง CSG tree และทำให้สามารถทำ hill climbing กับรูปทรงทั้งหมดได้