กรณีศึกษาการสร้างตัวแก้ไขไดอะแกรมแบบอินเทอร์แอคทีฟด้วยพีชคณิตเชิงเส้น

 (medium.com/@ivan.ishubin)
2 คะแนน โดย GN⁺ 2024-12-19 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • เมื่อ Schemio เพิ่มความสามารถในการจัดลำดับชั้นของรูปทรงและยึดติดกัน การแปลงระหว่างพิกัดโลคัลกับพิกัดเวิลด์ จึงกลายเป็นปัญหาหลักของตัวแก้ไข
  • วิธีแรกเริ่มที่ไล่ตามเชนของพาเรนต์แล้วใช้สูตรโดยตรง เริ่มดูแลรักษายากเมื่อมี การสเกล และ จุดพิวอต เข้ามา
  • หากรวมการย้ายตำแหน่ง การหมุน และการสเกลให้เป็น เมทริกซ์แปลง 3×3 จะสามารถประกอบการแปลงหลายรายการให้เป็นรายการเดียว และคำนวณการแปลงสะสมในโครงสร้างลำดับชั้นได้อย่างสอดคล้อง
  • เมื่อต้องแปลงพิกัดเวิลด์กลับเป็นพิกัดอ้างอิงของอ็อบเจ็กต์ จะใช้ เมทริกซ์ผกผัน A⁻¹ ของเมทริกซ์แปลงทั้งหมด เพื่อหาตำแหน่งคลิกหรือจุดเชื่อมต่อคอนเนกเตอร์ได้อย่างแม่นยำ
  • เมื่อเมานต์หรืออันเมานต์อ็อบเจ็กต์ไปยังพาเรนต์อื่น ต้องคำนวณค่าโลคัลใหม่เพื่อคงตำแหน่งและการหมุนบนหน้าจอไว้ จึงจะหลีกเลี่ยง การกระโดดของการเคลื่อนที่ ได้

ปัญหาที่เกิดขึ้นเมื่อ Schemio ขยายเป็นตัวแก้ไขแบบลำดับชั้น

  • Schemio เริ่มต้นเป็นตัวแก้ไขไดอะแกรมแบบอินเทอร์แอคทีฟที่รองรับการสร้าง ย้าย ปรับขนาด และหมุนรูปทรง
  • รูปทรงแต่ละชิ้นมี โครงสร้าง area ที่ประกอบด้วย x, y, w, h, r
    • x, y: ตำแหน่งตามพิกัดเวิลด์
    • w, h: ความกว้างและความสูง
    • r: มุมการหมุน
  • เพื่อให้รูปทรงยึดติดกันและสร้างปฏิสัมพันธ์ที่ซับซ้อนได้ จึงเพิ่มอาร์เรย์ childItems ให้กับแต่ละอ็อบเจ็กต์ และนำ โครงสร้างลำดับชั้นของไอเท็ม เข้ามาใช้
  • คล้ายฟีเจอร์จัดกลุ่มในตัวแก้ไขกราฟิกเวกเตอร์ทั่วไป เมื่อย้ายอ็อบเจ็กต์หนึ่ง อ็อบเจ็กต์ที่เชื่อมอยู่ก็สามารถเคลื่อนตามไปด้วยได้ แต่ Schemio มุ่งไปที่แอนิเมชันและพฤติกรรมที่ผู้ใช้กำหนดเองในรูปแบบที่ผสมระหว่างตัวแก้ไขไดอะแกรมกับเกมเอนจิน

การคำนวณพิกัดที่แก้ไม่ได้ด้วยการเรนเดอร์ SVG เพียงอย่างเดียว

  • ใน SVG หากซ้อนองค์ประกอบกัน เบราว์เซอร์สามารถจัดการการแปลงของพาเรนต์และลูกในขั้นตอนการเรนเดอร์ได้
  • นอกจากการเรนเดอร์แล้ว Schemio ยังต้องคำนวณการเชื่อมต่อคอนเนกเตอร์ การเมานต์·อันเมานต์อ็อบเจ็กต์ และอินเทอร์แอคชันที่ผู้ใช้กำหนดเองโดยตรง
  • ฟีเจอร์เหล่านี้ต้องอาศัยการแปลงไปมาระหว่าง พิกัดโลคัล ของอ็อบเจ็กต์กับ พิกัดเวิลด์ ของฉากทั้งหมด
  • ในช่วงแรกมีการไล่ตามเชนพาเรนต์และใช้สูตรง่าย ๆ เพื่อใช้การแปลง จากนั้นจึงปรับให้เหมาะสมด้วยการแคชการแปลงของพาเรนต์
  • เมื่อเพิ่มการสเกลและจุดพิวอต การผสมสูตรที่ตั้งอยู่บนสมมติฐานว่ามีเพียงการย้ายตำแหน่งและการหมุนก็ชนขีดจำกัด

ความซับซ้อนที่เพิ่มขึ้นจากการสเกลและจุดพิวอต

  • การสเกลคือฟีเจอร์สำหรับปรับขนาดอ็อบเจ็กต์แบบไดนามิก และใน Schemio มีบทบาทสำคัญในการโหลดไดอะแกรมภายนอกแบบไดนามิก
  • จุดพิวอตกำหนด ศูนย์กลางการหมุน ของอ็อบเจ็กต์
  • มีการเพิ่มคุณสมบัติ 4 รายการใน area ของอ็อบเจ็กต์
    • px, py: จุดพิวอต ที่สัมพันธ์กับความกว้างและความสูง
    • sx, sy: ค่าสัมประสิทธิ์การสเกล ในทิศทางแกน x และแกน y
  • หากกำหนดจุดพิวอตเป็นค่าสัมพัทธ์ เมื่อผู้ใช้เปลี่ยนขนาดรูปทรง จุดพิวอตก็จะปรับตามไปด้วย
  • วิธีที่ผสมการย้ายตำแหน่ง การหมุน การสเกล และการชดเชยพิวอตโดยตรงจะยิ่งจัดการยากเมื่อความต้องการเพิ่มขึ้น

รวมการแปลง 2D ให้เป็นเมทริกซ์

  • ในกราฟิก 2D และ 3D การย้ายตำแหน่ง การหมุน และการสเกลทั้งหมดสามารถแทนด้วย เมทริกซ์ ได้
  • จุด 2D จัดการเป็นเมทริกซ์ 3×1 ส่วนการแปลงจัดการเป็นเมทริกซ์ 3×3
  • เมื่อนำเมทริกซ์แปลง 3×3 คูณกับเมทริกซ์จุด 3×1 จะได้จุด 3×1 ที่ถูกแปลงแล้ว
  • เมทริกซ์แปลงพื้นฐานแบ่งได้ดังนี้
    • เมทริกซ์เอกลักษณ์: ไม่ทำการแปลงใด ๆ
    • เมทริกซ์ย้ายตำแหน่ง: ย้ายตำแหน่ง
    • เมทริกซ์หมุน: หมุนตามมุม
    • เมทริกซ์สเกล: ปรับขนาด
  • เมื่อต้องประกอบการแปลงหลายรายการ จะคูณเมทริกซ์แปลงเข้าด้วยกันเพื่อรวมเป็นการแปลงเดียว

วิธีสะสมการแปลงในโครงสร้างลำดับชั้น

  • การแปลงสุดท้ายของอ็อบเจ็กต์ไม่ได้รวมแค่การแปลงของตัวเอง แต่รวมถึงการแปลงของอ็อบเจ็กต์พาเรนต์ด้วย
  • เมื่อไล่ตามลำดับชั้นและคูณเมทริกซ์แปลงของแต่ละอ็อบเจ็กต์ จะสร้าง เมทริกซ์แปลงทั้งหมด ของอ็อบเจ็กต์ปัจจุบันได้
  • หากกำหนดให้เมทริกซ์แปลงของอ็อบเจ็กต์ปัจจุบันเป็น Ai และเมทริกซ์แปลงของอ็อบเจ็กต์พาเรนต์เป็น A(i-1) การแปลงตามลำดับชั้นจะสะสมด้วยผลคูณของการแปลงพาเรนต์และการแปลงของอ็อบเจ็กต์ปัจจุบัน
  • ในสูตรทั้งหมด ลำดับสำคัญคือย้ายอ็อบเจ็กต์โดยอิงจุดพิวอต ใช้การหมุนและการสเกล แล้วจึงย้ายกลับ
  • หากไม่พิจารณาพิวอต อ็อบเจ็กต์จะดูเหมือนหมุนรอบ มุมซ้ายบน แทนที่จะหมุนรอบพิวอตที่เลือกไว้
  • การชดเชยพิวอตต้องถูกนำไปใช้หลังเมทริกซ์สเกล เพื่อให้การสเกลดูเหมือนเกิดขึ้นโดยอิงจุดพิวอตด้วย

การคำนวณไปมาระหว่างพิกัดเวิลด์และพิกัดโลคัล

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

การคงตำแหน่งไว้ระหว่างการเมานต์และอันเมานต์

  • หนึ่งในปัญหายากของฟีเจอร์ลำดับชั้นคือ การเมานต์ และ การอันเมานต์ อ็อบเจ็กต์
  • วิธีติดอ็อบเจ็กต์เข้ากับอ็อบเจ็กต์อื่นมีสองแบบ
    • ลากอ็อบเจ็กต์ในฉากแล้วปล่อยบนอ็อบเจ็กต์อื่น
    • จัดลำดับชั้นใหม่ในพาเนล Item Selector
  • หากเปลี่ยนเฉพาะลำดับชั้น ตำแหน่งของอ็อบเจ็กต์จะถูกตีความเป็นพิกัดอ้างอิงของพาเรนต์ใหม่ ทำให้เกิดปัญหาที่อ็อบเจ็กต์กระโดดขึ้นลงบนหน้าจอ
  • เพื่อหลีกเลี่ยงปัญหานี้ ต้องคำนวณตำแหน่งและการหมุนใหม่ของอ็อบเจ็กต์ที่ถูกลาก

  • ขั้นตอนที่ 1: บันทึกตำแหน่งเวิลด์เดิม

    • ก่อนอื่นให้บันทึก ตำแหน่งเวิลด์ ของมุมซ้ายบนของอ็อบเจ็กต์ก่อนย้าย
    • ในโค้ดตัวอย่าง ใช้ worldPointOnItem(0, 0, item) เพื่อหาพิกัดเวิลด์ของมุมซ้ายบนของอ็อบเจ็กต์
    • worldPointOnItem ถูกอิมพลีเมนต์โดยใช้สูตรการแปลงเมทริกซ์ที่อนุมานไว้ก่อนหน้า

  • ขั้นตอนที่ 2: ชดเชยการหมุน

    • การหมุนของอ็อบเจ็กต์ถูกนิยามโดยอ้างอิงพาเรนต์ ดังนั้นเมื่อพาเรนต์เปลี่ยน การหมุนของอ็อบเจ็กต์ที่ถูกลากก็ต้องถูกชดเชยด้วย
    • ฟังก์ชัน worldAngleOfItem แปลงมุมซ้ายบนและมุมขวาบนของอ็อบเจ็กต์เป็นพิกัดเวิลด์ แล้วคำนวณมุมที่แกน x โลคัลของอ็อบเจ็กต์ทำกับแกน x เวิลด์
    • เปรียบเทียบมุมหมุนเวิลด์ของพาเรนต์เดิมกับมุมหมุนเวิลด์ของพาเรนต์ใหม่ แล้วปรับการหมุนของอ็อบเจ็กต์
    • item.area.r += previousParentWorldAngle - newParentWorldAngle
    • การคำนวณนี้ช่วยให้การหมุนบนหน้าจอของอ็อบเจ็กต์คงเดิมแม้พาเรนต์จะเปลี่ยน

  • ขั้นตอนที่ 3: คงตำแหน่งไว้

    • แม้อ็อบเจ็กต์จะย้ายไปอยู่ใต้พาเรนต์ใหม่แล้ว ก็ต้องคำนวณพิกัดโลคัลใหม่เพื่อให้ยังอยู่ตำแหน่งเดิมบนหน้าจอ
    • ฟังก์ชัน findTranslationMatchingWorldPoint คำนวณค่าการย้ายตำแหน่งที่จำเป็นเพื่อให้จุดโลคัลหนึ่งตรงกับจุดเวิลด์ที่ต้องการ
    • หากมีผลลัพธ์ที่คำนวณได้ จะอัปเดต area.x, area.y ของอ็อบเจ็กต์เป็นค่าใหม่
    • ด้วยวิธีนี้ แม้ลากอ็อบเจ็กต์ไปยังอ็อบเจ็กต์อื่นเพื่อเปลี่ยนลำดับชั้น ตำแหน่งบนหน้าจอก็ยังคงเดิม

การหาาค่าการย้ายตำแหน่งใหม่ด้วยเมทริกซ์ผกผัน

  • ปัญหาการหาค่าการย้ายตำแหน่งใหม่ คือปัญหาการหาเมทริกซ์ย้ายตำแหน่ง At ของอ็อบเจ็กต์ เมื่อกำหนดจุดเวิลด์ Pw และจุดโลคัล PL
  • เมทริกซ์ของการแปลงพาเรนต์ พิวอต การหมุน และการสเกลที่รู้อยู่แล้ว สามารถรวมเป็นเมทริกซ์เดียว A ได้
  • มีการใช้เมทริกซ์ผกผันของเมทริกซ์แปลงพาเรนต์เพื่อจัดรูปสมการ แต่เมทริกซ์ 3×1 ไม่ใช่เมทริกซ์จัตุรัส จึงไม่สามารถใช้เมทริกซ์ผกผันในลักษณะเดียวกันได้
  • จึงใช้การกระจายดีเทอร์มิแนนต์แทน เพื่อแยกองค์ประกอบการย้ายตำแหน่ง x, y ที่ต้องการ
  • เมื่อนำการคำนวณนี้ไปใช้ อ็อบเจ็กต์ที่ถูกลากจะคงตำแหน่งและการหมุนได้อย่างเป็นธรรมชาติเมื่อย้ายไปยังพาเรนต์ใหม่ และหลีกเลี่ยงการกระโดดหรือการบิดเบี้ยวแปลก ๆ ได้

โค้ดและเดโม

  • สามารถดูการอิมพลีเมนต์ Schemio ได้ในรีโพสitory GitHub ishubin/schemio
  • หากต้องการใช้งานเอง สามารถสร้างไดอะแกรมแบบอินเทอร์แอคทีฟหรือโปรโตไทป์แอปได้ที่ schem.io
  • นอกจากการแปลงเมทริกซ์แล้ว Schemio ยังมีหัวข้อทางคณิตศาสตร์อื่น ๆ เช่น เส้นโค้ง Bézier, การคำนวณเชิงอนุพันธ์ และ quadtrees สำหรับการปรับประสิทธิภาพ

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

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

 
GN⁺ 2024-12-19
ความคิดเห็นบน Hacker News

  • เพิ่งเคยได้ยิน Schemio ครั้งแรก ดูเจ๋งดี: https://schem.io/
    รูปลักษณ์และประสบการณ์ใช้งานลื่นมาก และถึงจะไม่ได้โปรโมตหนัก แต่เป็น โอเพนซอร์ส: https://github.com/ishubin/schemio

    • Schemio เปิดเป็นโอเพนซอร์ส ยกเว้นส่วน แบ็กเอนด์ ของ https://schem.io
      โค้ดฝั่งฟรอนต์เอนด์เปิดทั้งหมด และสามารถโฮสต์เซิร์ฟเวอร์เองได้ด้วย แต่ในกรณีนั้นจะใช้แค่ระบบไฟล์เป็นที่เก็บข้อมูล จึงไม่มีฐานข้อมูลหรือการจัดการผู้ใช้
    • ชอบวิธีที่สามารถ ซูมเข้า ไปยังไดอะแกรมที่ละเอียดขึ้น แล้วซูมกลับออกมาได้ง่าย
      นี่เป็นฟีเจอร์ที่อยากได้ใน Obsidian แต่ยังไม่ลื่นเท่า Schemio

  • เมทริกซ์การแปลง ได้รับความนิยมจาก Adobe PostScript ในช่วงทศวรรษ 1980 และ SVG ก็ยืมหลายส่วนมาจากโมเดลการสร้างภาพของ PostScript
    การใช้เมทริกซ์ 2D ใน PostScript ดูได้จากเอกสารด้านล่าง
    https://personal.math.ubc.ca/~cass/graphics/text/old.pdf/las...
    https://scientificgems.wordpress.com/2014/11/28/mathematics-...

    • ถ้าจะบอกว่า Adobe ทำให้เป็นที่นิยม ก็รู้สึกว่าเมทริกซ์การแปลงเป็นเรื่องที่เรียนกันใน พีชคณิต อยู่แล้วไม่ใช่หรือ

  • น่าลองค้นเรื่อง พิกัดเอกพันธ์ ด้วย: https://en.wikipedia.org/wiki/Homogeneous_coordinates

    • ในฐานะผู้เขียน ขอบคุณสำหรับคำแนะนำ
      ถ้ามีเวลาจะอ่านแน่นอน และจากการไล่ดูเร็ว ๆ เหมือนว่าจะมีส่วนที่เกี่ยวกับ เมทริกซ์การแปลง ที่ผมกำลังใช้อยู่ด้วย

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

    • ในเชิงเทคนิคแล้ว เอดิเตอร์กราฟิกทุกตัวน่าจะพึ่งพา พีชคณิตเชิงเส้น เพื่อหลายวัตถุประสงค์
      แต่คนที่พัฒนาสิ่งแบบนี้เป็นครั้งแรกไม่ได้มองเห็นทุกปัญหาอย่างชัดเจนเสมอไป เลยอยากแชร์อุปสรรคที่เจอจากมุมมองทางคณิตศาสตร์ จริง ๆ ก็ใช้พีชคณิตเชิงเส้นอยู่แล้ว แต่ประเด็นสำคัญคือเมทริกซ์ช่วยทำให้การคำนวณง่ายขึ้นมากแค่ไหน
      อีกอย่าง หากพึ่งพาการเรนเดอร์ของ SVG ก็สามารถผ่านไปด้วยโค้ดโดยไม่ต้องคิดลึกเรื่องคณิตศาสตร์ที่เกี่ยวข้องได้ เช่น ถ้าไม่ได้นำโครงสร้างลำดับชั้นของออบเจ็กต์เข้ามาใช้ ก็คงแทบไม่ต้องสนใจคณิตศาสตร์เลย SVG จัดการการแปลงทั้งหมดให้ และไม่จำเป็นต้องรู้ด้วยซ้ำว่ามีเมทริกซ์อยู่ หรือสามารถใช้กับออบเจ็กต์ SVG แบบ 1:1 ได้ การลากออบเจ็กต์ที่ไม่มีลำดับชั้นก็ง่ายกว่ามาก แค่เปลี่ยน translate(x,y) ในแอตทริบิวต์ transform ของ SVG ก็พอ

  • น่าลองดูเฟรมเวิร์ก QGraphicsView: https://doc.qt.io/qt-6/graphicsview.html
    เป็นหนึ่งในเฟรมเวิร์กกราฟิกที่ทรงพลังที่สุดเท่าที่เคยใช้มา ไม่เพียงรองรับการแปลงระหว่างซีนกับออบเจ็กต์รวมถึงลำดับชั้นของออบเจ็กต์ แต่ยังมีเครื่องมือทรงพลังจำนวนมากสำหรับเรนเดอร์ซีนที่ซับซ้อนและโต้ตอบได้
    น่าเสียดายที่บนเว็บยังหาทางเลือกที่ทำงานได้ดีเท่า QGVF ไม่เจอ

  • Schemio ดูดี
    กำลังใช้ Claude สร้าง ผังงาน จำนวนมาก โดย Claude จะเอาต์พุตเป็น Mermaidjs แล้วเรนเดอร์ในเบราว์เซอร์ ฟีเจอร์ซูมเข้า/ออกจากโฟลว์ไปเป็นซีเควนซ์ดูดีกว่า เลยอยากลองทำอะไรคล้าย ๆ กันด้วย Schemio

  • การใช้ เมทริกซ์เอกพันธ์ 3x3 สำหรับการเลื่อนขนาน 2D นั้นเจ๋งตรงที่การเลื่อนขนาน 2D จริง ๆ แล้วคือ shear แบบ 3D ที่เคลื่อนไปตามระนาบ z = 1
    https://youtu.be/AheaTd_l5Is?t=263

  • ที่เกี่ยวข้องกัน https://webglfundamentals.org/webgl/lessons/webgl-scene-grap... และทั้งเว็บ https://webglfundamentals.org อ่านดี และเป็นบทนำเรื่อง ลำดับชั้นการแปลง ที่แน่นด้วย

  • ทั้งบทความและซอฟต์แวร์น่าสนใจมาก
    ส่วนตัวกำลังมองหาซอฟต์แวร์โอเพนซอร์สที่แข็งแรงสำหรับทำไดอะแกรมอยู่ แต่น่าแปลกที่ Schemio ไม่เคยเข้ามาในเรดาร์เลย
    สำหรับการแปลงและแอนิเมชัน รู้สึกว่าใช้ พีชคณิตเรขาคณิต น่าจะเข้าใจได้เป็นธรรมชาติกว่าพีชคณิตเชิงเส้น
    [1] Projective Geometric Algebra:
    https://projectivegeometricalgebra.org/

  • ถ้าขยับออบเจ็กต์ที่มีลูกจำนวนมาก ก็คงต้องอัปเดตเทอม A(i-1) ของลูกทุกตัวในแต่ละเฟรม แล้ววนลงไปถึงหลาน ๆ ด้วย เลยสงสัยว่าต้นทุนจะไม่สูงขึ้นหรือ
    หรือสำหรับรูปทรงขนาดพอเหมาะก็ไม่ได้แย่นัก?

    • ไม่ว่าบรรพบุรุษตัวไหนขยับ เมทริกซ์การแปลง ของลูกทั้งหมดด้านล่างก็ต้องอัปเดตทุกครั้ง
      แต่จนถึงตอนนี้ยังไม่มีประสิทธิภาพตกลงอย่างเห็นได้ชัด ตอนนี้เป็นเพียงการคำนวณเผื่อไว้เมื่อจำเป็น และไม่ได้ส่งผลต่อองค์ประกอบ SVG จริง จึงไม่ต้องอัปเดตองค์ประกอบ SVG เหตุผลที่ต้องคำนวณเมทริกซ์การแปลงนี้ใหม่คือ เมื่อจัดแนวคอนเน็กเตอร์ที่เชื่อมอยู่ใหม่ หรือจัดการลอจิกตามตำแหน่ง อาจจำเป็นต้องรู้ พิกัดโลคัล-เวิลด์ ของออบเจ็กต์ใดออบเจ็กต์หนึ่ง