linear algebra की मदद से interactive diagram editor बनाने का एक उदाहरण

 (medium.com/@ivan.ishubin)
2 पॉइंट द्वारा GN⁺ 2024-12-19 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Schemio में shapes को hierarchy में व्यवस्थित करने और एक-दूसरे से attach करने की क्षमता बढ़ने के साथ local coordinates और world coordinates के बीच transformation editor की मुख्य समस्या बन गई
  • parent chain का पालन करते हुए formulas को सीधे apply करने वाला शुरुआती तरीका scaling और pivot point जुड़ने के बाद maintain करना मुश्किल हो गया
  • translation, rotation, scaling को 3×3 transformation matrix में एकीकृत करने पर कई transformations को एक में compose किया जा सकता है और hierarchy में accumulated transformations भी एकसमान तरीके से calculate किए जा सकते हैं
  • world coordinates को object-based local coordinates में वापस बदलते समय पूरे transformation matrix के inverse A⁻¹ का उपयोग करके click position या connector attachment point को सटीक रूप से निकाला जाता है
  • किसी object को दूसरे parent पर mount या unmount करते समय screen पर उसकी position और rotation को बनाए रखने के लिए नए local values फिर से calculate करने पड़ते हैं, ताकि अचानक उछलने जैसी movement से बचा जा सके

Schemio के hierarchical editor में expand होने पर सामने आई समस्या

  • Schemio की शुरुआत एक interactive diagram editor के रूप में हुई थी, जो shape creation, movement, resizing और rotation को support करता है
  • हर shape में x, y, w, h, r से बना area structure होता है
    • x, y: world coordinates के आधार पर position
    • w, h: width और height
    • r: rotation angle
  • shapes को एक-दूसरे से attach करने और complex interactions बनाने के लिए हर object में childItems array जोड़ा गया और item hierarchy structure लाई गई
  • सामान्य vector graphics editor के group feature की तरह एक object को move करने पर उससे जुड़े object भी साथ चल सकते हैं, लेकिन Schemio का लक्ष्य diagram editor और game engine के मिश्रण जैसा animation और custom behavior देना है

केवल SVG rendering से हल न होने वाली coordinate calculation

  • SVG में elements को nest करने पर browser rendering stage पर parent-child transformation को संभाल सकता है
  • लेकिन Schemio को rendering के अलावा connector attachment, object mount-unmount और custom interaction भी सीधे calculate करने पड़ते हैं
  • इन features के लिए object के local coordinates और पूरे scene के world coordinates के बीच transformation की जरूरत होती है
  • शुरुआत में parent chain को traverse करते हुए simple formulas से transformation apply किया गया, बाद में parent transformations को cache करके optimization किया गया
  • scaling और pivot point जुड़ने के बाद केवल translation और rotation को मानकर बनाई गई formula composition अपनी सीमा पर पहुंच गई

scaling और pivot point से बढ़ी complexity

  • scaling object size को dynamically adjust करने की सुविधा है, और Schemio में external diagrams को dynamically load करने में इसकी महत्वपूर्ण भूमिका है
  • pivot point object के rotation center को define करता है
  • object के area में चार properties और जोड़ी गईं
    • px, py: width और height के सापेक्ष pivot point
    • sx, sy: x-axis और y-axis दिशा में scaling factors
  • pivot point को relative value रखने से user जब shape का size बदलता है तो pivot भी उसी के साथ adjust होता है
  • translation, rotation, scaling और pivot correction को सीधे combine करने का तरीका requirements बढ़ने के साथ manage करना कठिन होता गया

2D transformation को matrix से एकीकृत करना

  • 2D और 3D graphics में translation, rotation और scaling सभी को matrix से व्यक्त किया जा सकता है
  • 2D point को 3×1 matrix और transformation को 3×3 matrix के रूप में लिया जाता है
  • 3×3 transformation matrix और 3×1 point matrix को multiply करने पर transformed 3×1 point मिलता है
  • basic transformation matrices इस तरह विभाजित होते हैं
    • identity matrix: कोई transformation नहीं करता
    • translation matrix: position को move करता है
    • rotation matrix: angle के अनुसार rotate करता है
    • scaling matrix: size को adjust करता है
  • कई transformations को जोड़ने के लिए transformation matrices को multiply करके एक transformation बनाया जाता है

hierarchy structure में transformations को accumulate करने का तरीका

  • object का final transformation सिर्फ उसके अपने transformation तक सीमित नहीं होता, बल्कि parent objects के transformations भी शामिल करता है
  • hierarchy के साथ चलते हुए हर object के transformation matrix को multiply करने पर current object का complete transformation matrix बनाया जा सकता है
  • अगर current object के transformation matrix को Ai और parent object के transformation matrix को A(i-1) माना जाए, तो hierarchical transformation parent transformation और current object transformation के गुणन से accumulate होता है
  • पूरे formula में object को pivot point के आधार पर move करना, rotation और scaling apply करना, और फिर वापस shift करना—इस क्रम का सही होना महत्वपूर्ण है
  • pivot को ध्यान में न रखने पर object ऐसा दिखेगा जैसे वह चुने गए pivot के बजाय ऊपरी-बाएँ कोने के आसपास rotate हो रहा हो
  • pivot correction को scaling matrix के बाद apply करना चाहिए, तभी scaling भी pivot point के आधार पर होती हुई दिखेगी

world coordinates और local coordinates के बीच calculation

  • local coordinates से world coordinates में जाने के लिए complete transformation matrix को point पर multiply किया जाता है
  • इसके उलट world coordinates को object के local coordinates में बदलने के लिए complete transformation matrix के inverse का उपयोग किया जाता है
  • यदि complete transformation को matrix A माना जाए, तो world point को A और local point के गुणन के रूप में व्यक्त किया जा सकता है
  • matrix division नहीं होती, लेकिन बाईं ओर से A⁻¹ multiply करने पर A⁻¹A identity matrix बन जाता है और local point मिल जाता है
  • यह transformation तब जरूरी होता है जब user transformed object पर क्लिक किए गए बिंदु को object के ऊपरी-बाएँ कोने के सापेक्ष ढूंढना चाहता हो, या connector को सही स्थान पर attach करना हो

mount और unmount में position को बनाए रखना

  • hierarchy feature में कठिन समस्याओं में से एक object का mount और unmount था
  • किसी object को दूसरे object से attach करने के दो तरीके हैं
    • scene में object को drag करके दूसरे object पर drop करना
    • Item Selector panel में hierarchy को rearrange करना
  • केवल hierarchy बदलने पर object की position नए parent के coordinate basis में interpret होती है, जिससे screen पर उसका ऊपर-नीचे उछलना जैसी समस्या आती है
  • इससे बचने के लिए dragged object की नई position और rotation फिर से calculate करनी पड़ती है

  • चरण 1: पुरानी world position सहेजना

    • सबसे पहले move से पहले object के ऊपरी-बाएँ कोने की world position सहेजी जाती है
    • example code में worldPointOnItem(0, 0, item) से object के ऊपरी-बाएँ कोने के world coordinates निकाले जाते हैं
    • worldPointOnItem को ऊपर निकाले गए matrix transformation formula से implement किया गया है

  • चरण 2: rotation correction

    • object की rotation parent के आधार पर define होती है, इसलिए parent बदलने पर dragged object की rotation भी correct करनी पड़ती है
    • worldAngleOfItem function object के ऊपरी-बाएँ और ऊपरी-दाएँ कोनों को world coordinates में transform करके यह calculate करता है कि object का local x-axis, world x-axis से कितना angle बनाता है
    • पुराने parent के world rotation angle और नए parent के world rotation angle की तुलना करके object rotation को adjust किया जाता है
    • item.area.r += previousParentWorldAngle - newParentWorldAngle
    • इस calculation से parent बदलने पर भी object की screen पर दिखाई देने वाली rotation बनी रहती है

  • चरण 3: position को बनाए रखना

    • object को नए parent के नीचे ले जाने के बाद भी उसे screen पर उसी position पर बनाए रखने के लिए नए local coordinates calculate करने होते हैं
    • findTranslationMatchingWorldPoint function यह calculate करता है कि किसी खास local point को इच्छित world point से match कराने के लिए कितनी translation चाहिए
    • यदि calculated result मिले, तो object के area.x, area.y को नए values से update किया जाता है
    • इस तरीके से object को drag करके किसी दूसरे object के नीचे hierarchy बदलने पर भी उसकी screen position बनी रहती है

inverse matrix से नई translation value निकालना

  • नई translation value खोजने की समस्या यह है कि world point Pw और local point PL दिए होने पर object के translation matrix At को ढूंढा जाए
  • पहले से ज्ञात parent transformation, pivot, rotation और scaling matrices को एक matrix A में जोड़ा जा सकता है
  • parent transformation matrix के inverse का उपयोग करके formula को व्यवस्थित किया जाता है, लेकिन 3×1 matrix square matrix नहीं होती, इसलिए उसी तरीके से inverse apply नहीं किया जा सकता
  • इसके बजाय determinant को expand करके जरूरी x, y translation components को अलग किया जाता है
  • इस calculation को apply करने पर dragged object नए parent के पास जाते समय अपनी position और rotation को स्वाभाविक रूप से बनाए रखता है, और अजीब jump या distortion से बचा जा सकता है

code और demo

  • Schemio का implementation GitHub repository ishubin/schemio में देखा जा सकता है
  • सीधे इस्तेमाल करने के लिए schem.io पर interactive diagrams या app prototypes बनाए जा सकते हैं
  • Schemio में matrix transformation के अलावा Bézier curves, differential calculation और performance optimization के लिए quadtrees जैसे और भी mathematical topics हैं

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-12-19
Hacker News की राय

  • Schemio के बारे में पहली बार सुना, बढ़िया लगा: https://schem.io/
    दिखने और इस्तेमाल करने में बहुत स्मूद है, और भले ही इसे बहुत जोर से प्रचारित नहीं किया गया, यह open source है: https://github.com/ishubin/schemio

    • Schemio, https://schem.io के backend हिस्से को छोड़कर open source के रूप में उपलब्ध है
      frontend code पूरी तरह खुला है और आप खुद server भी host कर सकते हैं। हालांकि उस स्थिति में storage के लिए सिर्फ file system इस्तेमाल होता है, इसलिए database या user management नहीं होता
    • ज्यादा विस्तृत diagram में zoom in करके फिर आसानी से zoom out कर पाने का तरीका अच्छा है
      Obsidian में मैं इसी तरह की सुविधा चाहता था, लेकिन वह Schemio जितनी स्मूद नहीं थी

  • transformation matrices को 1980 के दशक में Adobe PostScript ने लोकप्रिय बनाया था, और SVG ने PostScript के imaging model से काफी कुछ उधार लिया है
    PostScript में 2D matrices के उपयोग के लिए नीचे की सामग्री देखें
    https://personal.math.ubc.ca/~cass/graphics/text/old.pdf/las...
    https://scientificgems.wordpress.com/2014/11/28/mathematics-...

    • यह कहना कि Adobe ने इसे लोकप्रिय बनाया, थोड़ा अजीब लगता है; transformation matrices तो बस algebra में पढ़ी जाने वाली चीज नहीं हैं क्या

  • homogeneous coordinates भी देखना अच्छा रहेगा: https://en.wikipedia.org/wiki/Homogeneous_coordinates

    • लेखक के तौर पर, सुझाव के लिए धन्यवाद
      समय मिलने पर जरूर पढ़ूंगा, और जल्दी से देखने पर लगता है कि इसमें उन transformation matrices से जुड़ा section भी है जिन्हें मैं इस्तेमाल कर रहा था

  • editor बनाने की प्रक्रिया का अच्छा सारांश है, और linear algebra के summary के रूप में भी अच्छा है
    लेकिन क्या सभी editors linear algebra का इस्तेमाल नहीं करते?

    • तकनीकी तौर पर कहा जा सकता है कि सभी graphics editors कई उद्देश्यों के लिए linear algebra पर निर्भर करते हैं
      लेकिन जो व्यक्ति पहली बार ऐसी चीज develop कर रहा हो, उसे सभी समस्याएं obvious नहीं लगतीं, इसलिए मैं math के नजरिए से आई चुनौतियां साझा करना चाहता था। मैं पहले से linear algebra इस्तेमाल कर रहा था, लेकिन मुख्य बात यह थी कि matrices ने calculations को कितना सरल बना दिया
      इसके अलावा, अगर आप SVG rendering पर निर्भर रहते हैं, तो संबंधित math पर गहराई से सोचे बिना सिर्फ code से भी काम चल सकता है। उदाहरण के लिए, अगर मैंने object hierarchy introduce नहीं की होती, तो शायद math की लगभग चिंता ही नहीं करनी पड़ती। SVG सभी transformations संभाल देता, और यह जानने की भी जरूरत नहीं होती कि matrices मौजूद हैं या उन्हें SVG objects पर 1:1 इस्तेमाल किया जा सकता है। hierarchy के बिना object drag करना भी बहुत आसान होता; SVG transform attribute के अंदर सिर्फ translate(x,y) बदलना काफी होता

  • QGraphicsView framework देखने लायक है: https://doc.qt.io/qt-6/graphicsview.html
    मैंने जितने graphics frameworks इस्तेमाल किए हैं, उनमें यह सबसे शक्तिशाली में से एक है। object hierarchy सहित scene-object transformations के अलावा, यह complex और interactive scenes render करने के लिए कई powerful tools देता है
    अफसोस कि web पर मुझे QGVF जितना अच्छा काम करने वाला alternative नहीं मिला

  • Schemio अच्छा दिख रहा है
    मैं Claude से कई flowcharts बना रहा हूं, और Claude Mermaidjs में output देता है और browser में render करता है। flow से sequence तक zoom in/out होने वाला feature ज्यादा अच्छा लगता है, इसलिए Schemio में भी कुछ वैसा करके देखना चाहता हूं

  • 2D translation के लिए 3x3 homogeneous matrix इस्तेमाल करने पर यह बात कमाल लगती है कि 2D translation असल में z = 1 plane के साथ चलने वाला 3D shear है
    https://youtu.be/AheaTd_l5Is?t=263

  • इससे संबंधित https://webglfundamentals.org/webgl/lessons/webgl-scene-grap... और पूरा https://webglfundamentals.org पढ़ने लायक है, और transformation hierarchy की शुरुआत के लिए भी मजबूत सामग्री है

  • लेख और software दोनों बहुत दिलचस्प हैं
    निजी तौर पर मैं diagrams के लिए मजबूत open source software ढूंढ रहा था, लेकिन अजीब बात है कि Schemio कभी मेरे radar पर आया ही नहीं
    transformations और animations के लिए linear algebra की तुलना में geometric algebra इस्तेमाल करना शायद ज्यादा intuitive लगेगा, ऐसा महसूस होता है
    [1] Projective Geometric Algebra:
    https://projectivegeometricalgebra.org/

  • अगर बहुत सारे children वाले object को move किया जाए, तो हर frame के बीच सभी children के A(i-1) terms update करने होंगे, और grandchildren तक recursively नीचे जाना होगा; सोच रहा हूं कि क्या cost बहुत ज्यादा नहीं बढ़ जाएगी
    या फिर ठीक-ठाक आकार के shapes में यह बहुत बुरा नहीं होता?

    • किसी भी ancestor की movement हो, उसके नीचे मौजूद सभी children की transformation matrices हर बार update करनी पड़ती हैं
      फिर भी अब तक कोई नजर आने वाली performance degradation नहीं है। फिलहाल यह सिर्फ जरूरत पड़ने की स्थिति के लिए calculation करके रखने जैसा है, और असली SVG elements पर असर नहीं डालता, इसलिए SVG elements update करने की जरूरत नहीं होती। इन transformation matrices को फिर से calculate करने की वजह यह है कि attached connectors को readjust करते समय या position-based logic संभालते समय किसी खास object के local-world coordinates जानने पड़ सकते हैं