Một trường hợp xây dựng trình chỉnh sửa sơ đồ tương tác bằng đại số tuyến tính

• Khi Schemio bổ sung thêm các tính năng phân cấp hình dạng và gắn chúng với nhau, việc chuyển đổi giữa tọa độ cục bộ và tọa độ thế giới trở thành bài toán cốt lõi của trình chỉnh sửa
• Cách làm ban đầu là áp dụng trực tiếp công thức theo chuỗi cha, nhưng khi xuất hiện scaling và pivot point thì việc bảo trì trở nên khó khăn
• Nếu thống nhất dịch chuyển, xoay và scaling bằng ma trận biến đổi 3×3, có thể hợp nhất nhiều phép biến đổi thành một và cũng tính toán nhất quán phép biến đổi tích lũy trong cấu trúc phân cấp
• Khi cần đưa tọa độ thế giới về lại tọa độ theo đối tượng, dùng ma trận nghịch đảo A⁻¹ của toàn bộ ma trận biến đổi để xác định chính xác vị trí click hoặc điểm nối connector
• Khi mount hoặc unmount một đối tượng sang cha khác, cần tính lại các giá trị cục bộ mới để giữ nguyên vị trí và góc xoay trên màn hình, tránh hiện tượng nhảy vị trí

---

Vấn đề phát sinh khi Schemio mở rộng thành trình chỉnh sửa phân cấp

• Schemio khởi đầu là một trình chỉnh sửa sơ đồ tương tác hỗ trợ tạo hình, di chuyển, thay đổi kích thước và xoay
• Mỗi hình có một cấu trúc area gồm x, y, w, h, r
  • x, y: vị trí theo tọa độ thế giới
  • w, h: chiều rộng và chiều cao
  • r: góc xoay
• Để gắn các hình với nhau và tạo ra các tương tác phức tạp, tác giả đã thêm mảng childItems cho mỗi đối tượng và đưa vào cấu trúc phân cấp item
• Giống tính năng group trong các trình chỉnh sửa đồ họa vector thông thường, khi di chuyển một đối tượng thì các đối tượng được liên kết cũng có thể di chuyển cùng, nhưng Schemio hướng tới các animation và hành vi tùy biến, như sự kết hợp giữa trình chỉnh sửa sơ đồ và game engine

Tính toán tọa độ không thể giải quyết chỉ bằng SVG rendering

• Trong SVG, nếu lồng các phần tử thì trình duyệt có thể xử lý phép biến đổi cha-con ở giai đoạn rendering
• Nhưng Schemio ngoài rendering còn phải tự tính toán việc nối connector, mount/unmount đối tượng và các tương tác tùy biến
• Những tính năng này cần các phép chuyển đổi qua lại giữa tọa độ cục bộ của đối tượng và tọa độ thế giới của toàn bộ scene
• Ban đầu, tác giả duyệt theo chuỗi cha và áp dụng phép biến đổi bằng các công thức đơn giản, sau đó tối ưu bằng cách cache phép biến đổi của cha
• Khi scaling và pivot point được thêm vào, cách ghép công thức vốn chỉ giả định dịch chuyển và xoay đã chạm tới giới hạn

Độ phức tạp tăng lên do scaling và pivot point

• Scaling là tính năng điều chỉnh kích thước đối tượng một cách động, và trong Schemio nó đóng vai trò quan trọng khi tải động các sơ đồ bên ngoài
• Pivot point xác định tâm xoay của đối tượng
• Trong area của đối tượng, bốn thuộc tính mới được thêm vào
  • px, py: pivot point tương đối theo chiều rộng và chiều cao
  • sx, sy: hệ số scaling theo trục x và trục y
• Khi dùng pivot point dưới dạng giá trị tương đối, nếu người dùng thay đổi kích thước hình thì pivot cũng được điều chỉnh theo
• Cách tự kết hợp thủ công dịch chuyển, xoay, scaling và hiệu chỉnh pivot ngày càng khó quản lý khi yêu cầu tiếp tục tăng

Thống nhất biến đổi 2D bằng ma trận

• Trong đồ họa 2D và 3D, dịch chuyển, xoay và scaling đều có thể biểu diễn bằng ma trận
• Điểm 2D được biểu diễn bằng ma trận 3×1, còn phép biến đổi được biểu diễn bằng ma trận 3×3
• Khi nhân ma trận biến đổi 3×3 với ma trận điểm 3×1, ta nhận được điểm 3×1 sau biến đổi
• Các ma trận biến đổi cơ bản được chia như sau
  • Ma trận đơn vị: không thực hiện biến đổi nào
  • Ma trận dịch chuyển: thay đổi vị trí
  • Ma trận xoay: xoay theo góc
  • Ma trận scaling: điều chỉnh kích thước
• Khi kết hợp nhiều phép biến đổi, chỉ cần nhân các ma trận biến đổi để gộp chúng thành một phép biến đổi duy nhất

Cách tích lũy biến đổi trong cấu trúc phân cấp

• Phép biến đổi cuối cùng của một đối tượng không chỉ gồm biến đổi của chính nó mà còn bao gồm cả biến đổi của các đối tượng cha
• Đi dọc theo phân cấp và nhân các ma trận biến đổi của từng đối tượng sẽ tạo ra ma trận biến đổi tổng của đối tượng hiện tại
• Nếu gọi ma trận biến đổi của đối tượng hiện tại là Ai, và của đối tượng cha là A(i-1), thì biến đổi trong phân cấp được tích lũy bằng tích của ma trận cha và ma trận hiện tại
• Trong công thức tổng thể, thứ tự đưa đối tượng về pivot point, áp dụng xoay và scaling rồi đưa ngược trở lại là rất quan trọng
• Nếu không xét đến pivot, đối tượng sẽ trông như đang xoay quanh góc trên bên trái thay vì pivot đã chọn
• Hiệu chỉnh pivot phải được áp dụng sau ma trận scaling thì scaling mới có cảm giác diễn ra quanh pivot point

Tính toán chuyển đổi giữa tọa độ thế giới và tọa độ cục bộ

• Khi đi từ tọa độ cục bộ sang tọa độ thế giới, ta nhân điểm với ma trận biến đổi tổng
• Ngược lại, để đổi tọa độ thế giới về tọa độ cục bộ của đối tượng, dùng ma trận nghịch đảo của ma trận biến đổi tổng
• Nếu gộp toàn bộ phép biến đổi vào ma trận A, thì điểm thế giới được biểu diễn bằng tích của A và điểm cục bộ
• Dù không có phép chia ma trận, ta có thể nhân A⁻¹ ở bên trái để A⁻¹A trở thành ma trận đơn vị và thu được điểm cục bộ
• Phép chuyển đổi này cần thiết để tìm tọa độ tính từ góc trên bên trái của đối tượng tại vị trí người dùng click trên một đối tượng đã bị biến đổi, hoặc để gắn connector đúng chính xác vào vị trí mong muốn

Giữ nguyên vị trí khi mount và unmount

• Một trong những bài toán khó của tính năng phân cấp là mount và unmount đối tượng
• Có hai cách gắn một đối tượng vào đối tượng khác
  • Kéo đối tượng trong scene rồi thả lên trên một đối tượng khác
  • Sắp xếp lại phân cấp trong bảng Item Selector
• Nếu chỉ thay đổi phân cấp, vị trí của đối tượng sẽ bị diễn giải theo hệ tọa độ của cha mới, dẫn tới hiện tượng nó nhảy lên xuống trên màn hình
• Để tránh điều này, cần tính lại vị trí và góc xoay mới của đối tượng được kéo

• Bước 1: Lưu vị trí thế giới hiện có

  • Trước tiên lưu vị trí thế giới của góc trên bên trái đối tượng trước khi di chuyển
  • Trong ví dụ mã, worldPointOnItem(0, 0, item) được dùng để lấy tọa độ thế giới của góc trên bên trái đối tượng
  • worldPointOnItem được cài đặt bằng công thức biến đổi ma trận đã suy ra trước đó

• Bước 2: Hiệu chỉnh góc xoay

  • Góc xoay của đối tượng được định nghĩa theo đối tượng cha, nên khi cha thay đổi thì góc xoay của đối tượng được kéo cũng phải được hiệu chỉnh
  • Hàm worldAngleOfItem chuyển góc trên bên trái và góc trên bên phải của đối tượng sang tọa độ thế giới, rồi tính góc giữa trục x cục bộ của đối tượng với trục x thế giới
  • So sánh góc xoay thế giới của cha cũ với góc xoay thế giới của cha mới để điều chỉnh góc xoay của đối tượng
  • item.area.r += previousParentWorldAngle - newParentWorldAngle
  • Nhờ phép tính này, dù cha thay đổi thì góc xoay hiển thị của đối tượng trên màn hình vẫn được giữ nguyên

• Bước 3: Giữ nguyên vị trí

  • Sau khi đối tượng được chuyển sang dưới cha mới, cần tính lại tọa độ cục bộ mới để nó vẫn nằm ở đúng vị trí cũ trên màn hình
  • Hàm findTranslationMatchingWorldPoint tính giá trị dịch chuyển cần thiết để một điểm cục bộ cụ thể khớp với điểm thế giới mong muốn
  • Nếu có kết quả, cập nhật area.x, area.y của đối tượng thành giá trị mới
  • Với cách này, ngay cả khi kéo một đối tượng sang đối tượng khác để đổi phân cấp, vị trí hiển thị trên màn hình vẫn được giữ nguyên

Tìm giá trị dịch chuyển mới bằng ma trận nghịch đảo

• Bài toán tìm giá trị dịch chuyển mới là bài toán tìm ma trận dịch chuyển At khi đã biết điểm thế giới Pw và điểm cục bộ PL
• Các ma trận đã biết như biến đổi của cha, pivot, xoay và scaling có thể gộp lại thành một ma trận A
• Có thể biến đổi công thức bằng cách dùng ma trận nghịch đảo của ma trận biến đổi cha, nhưng ma trận 3×1 không phải ma trận vuông nên không thể áp dụng nghịch đảo theo cùng cách
• Thay vào đó, tác giả khai triển định thức để tách riêng các thành phần dịch chuyển x, y cần tìm
• Áp dụng phép tính này giúp đối tượng được kéo giữ vị trí và góc xoay một cách tự nhiên khi chuyển sang cha mới, tránh các cú nhảy hoặc biến dạng kỳ lạ

Mã nguồn và demo

• Có thể xem phần cài đặt của Schemio trong kho GitHub ishubin/schemio
• Nếu muốn dùng trực tiếp, bạn có thể tạo sơ đồ tương tác hoặc prototype ứng dụng tại schem.io
• Ngoài biến đổi ma trận, Schemio còn có nhiều chủ đề toán học khác như đường cong Bézier, tính vi phân và quadtrees để tối ưu hiệu năng

[GN⁺]

Các ý kiến trên Hacker News

• Lần đầu nghe đến Schemio, trông rất hay: https://schem.io/
  Nhìn và dùng rất mượt, và dù không quảng bá rầm rộ nhưng nó là mã nguồn mở: https://github.com/ishubin/schemio

  • Schemio được mở nguồn, ngoại trừ phần backend của https://schem.io
    Mã frontend hoàn toàn mở và bạn cũng có thể tự host server. Tuy nhiên trong trường hợp đó, nó chỉ dùng hệ thống tệp làm kho lưu trữ nên không có cơ sở dữ liệu hay quản lý người dùng
  • Tôi thích cách có thể phóng to vào một sơ đồ chi tiết hơn rồi dễ dàng thu nhỏ trở lại
    Đây là tính năng tôi từng muốn có trong Obsidian, nhưng nó không mượt được như Schemio

• Ma trận biến đổi được Adobe PostScript phổ biến vào thập niên 1980, và SVG vay mượn rất nhiều từ mô hình imaging của PostScript
  Có thể xem các tài liệu dưới đây về cách PostScript dùng ma trận 2D
  https://personal.math.ubc.ca/~cass/graphics/text/old.pdf/las...
  https://scientificgems.wordpress.com/2014/11/28/mathematics-...

  • Nói Adobe phổ biến nó thì có vẻ hơi quá; chẳng phải ma trận biến đổi chỉ là nội dung học trong đại số sao?

• Có lẽ cũng nên tìm hiểu tọa độ thuần nhất: https://en.wikipedia.org/wiki/Homogeneous_coordinates

  • Với tư cách tác giả bài viết, cảm ơn vì gợi ý
    Khi có thời gian tôi nhất định sẽ đọc, và lướt nhanh thì có vẻ có cả phần liên quan đến ma trận biến đổi mà tôi đang dùng

• Bài viết tóm tắt tốt quá trình làm editor, và cũng là bản tóm tắt hay về đại số tuyến tính
  Nhưng chẳng phải mọi editor đều dùng đại số tuyến tính sao?

  • Về mặt kỹ thuật, có thể nói mọi editor đồ họa đều dựa vào đại số tuyến tính cho nhiều mục đích
    Tuy nhiên với người lần đầu phát triển thứ như thế này, không phải vấn đề nào cũng hiển nhiên, nên tôi muốn chia sẻ những khó khăn đã gặp từ góc nhìn toán học. Tôi vốn đã dùng đại số tuyến tính rồi, nhưng điểm chính là ma trận đã làm phép tính đơn giản đi nhiều đến mức nào
    Ngoài ra, nếu dựa vào việc render SVG thì có thể bỏ qua nhiều thứ chỉ bằng code mà không cần nghĩ sâu về phần toán liên quan. Ví dụ nếu tôi không đưa vào cấu trúc phân cấp đối tượng, có lẽ gần như không cần bận tâm đến toán học. SVG sẽ xử lý mọi phép biến đổi, và bạn thậm chí không cần biết rằng ma trận tồn tại hay có thể dùng 1:1 với đối tượng SVG. Kéo đối tượng không có phân cấp cũng dễ hơn nhiều; chỉ cần thay translate(x,y) trong thuộc tính transform của SVG là được

• Đáng xem framework QGraphicsView: https://doc.qt.io/qt-6/graphicsview.html
  Đây thuộc nhóm framework đồ họa mạnh nhất mà tôi từng dùng. Ngoài các biến đổi scene-object có cả phân cấp đối tượng, nó còn cung cấp nhiều công cụ mạnh để render các scene phức tạp và có tính tương tác
  Đáng tiếc là trên web tôi chưa tìm được lựa chọn thay thế nào hoạt động tốt như QGVF

• Schemio trông có vẻ tốt
  Tôi đang tạo nhiều flowchart bằng Claude; Claude xuất ra Mermaidjs rồi render trong trình duyệt. Tính năng phóng to/thu nhỏ từ luồng sang sequence trông còn hay hơn, nên tôi cũng muốn thử làm thứ tương tự bằng Schemio

• Khi dùng ma trận thuần nhất 3x3 cho phép tịnh tiến 2D, điều thú vị là tịnh tiến 2D thực ra là một phép shear 3D đi dọc theo mặt phẳng z = 1
  https://youtu.be/AheaTd_l5Is?t=263

• Liên quan đến chủ đề này, https://webglfundamentals.org/webgl/lessons/webgl-scene-grap... và toàn bộ https://webglfundamentals.org đều rất đáng đọc, đồng thời cũng là phần nhập môn vững chắc về cấu trúc phân cấp biến đổi

• Cả bài viết lẫn phần mềm đều rất thú vị
  Cá nhân tôi đang tìm một phần mềm mã nguồn mở vững chắc cho sơ đồ, vậy mà lạ là trước giờ Schemio chưa từng xuất hiện trong tầm radar của tôi
  Tôi cũng có cảm giác rằng với biến đổi và animation, dùng đại số hình học có lẽ sẽ trực quan hơn đại số tuyến tính
  [1] Projective Geometric Algebra:
  https://projectivegeometricalgebra.org/

• Tôi tò mò liệu khi di chuyển một đối tượng có nhiều con, mỗi frame có phải cập nhật hạng A(i-1) của mọi con rồi lặp tiếp xuống cả các cháu không, và như vậy chi phí có lớn không
  Hay với các hình có kích thước vừa phải thì không quá tệ?

  • Với bất kỳ chuyển động nào của một tổ tiên, ma trận biến đổi của tất cả đối tượng con bên dưới đều phải được cập nhật mỗi lần
    Dù vậy cho đến nay chưa có suy giảm hiệu năng đáng chú ý. Hiện tại tôi chỉ tính sẵn để phòng khi cần, và nó không ảnh hưởng đến các phần tử SVG thực tế nên không cần cập nhật phần tử SVG. Lý do tính lại ma trận biến đổi này là vì khi điều chỉnh lại các connector gắn kèm hoặc xử lý logic dựa trên vị trí, có thể cần biết tọa độ local-world của một đối tượng cụ thể