Liikkuvan viivan leikkaaminen liikkuvan pisteen kanssa

3 marraskuun, 2021

Liikkuvan viivan leikkaaminen liikkuvan pisteen kanssa
Pääte
Intuitio
Malli
Ratkaisu
Yleistäminen
Yhteenveto
Keskustele Redditissä
Archive

julkaissut Craig Gidney 5. helmikuuta 2013

Yritän liittää mukaan esimerkkiprojekteja, kun julkaisen kirjastoja. Pilaantuvien kokoelmien tapauksessa näyteprojekti oli itse asiassa yksinkertainen peli, joka perustui viivojen leikkaamiseen hiiren osoittimella:

Osana näytteen kirjoittamista minun oli ratkaistava ongelma, joka koski sen määrittämistä, onko hiiren osoitin pyyhkäissyt viivan poikki (tai päinvastoin), milloin ja missä. Tavallinen viitteeni geometria-algoritmeista ei sisältänyt ratkaisua, joten kehitin sellaisen itse.

Tässä viestissä selitän analyyttisen ratkaisun ongelmaan. Ratkaisu on toteutettu pienessä määrässä lähdekoodia (noin 150 riviä, kun lasketaan kommentit ja tukevat metodit/tyypit), joka on saatavilla myös githubissa.

Pääte

Kävi ilmi, että ”leikkasiko hiirenosoitin liikkuvan viivan?” on yksi niistä maagisista matemaattisista ongelmista, jotka alkavat joillakin verrattain simppeleillä reunaehdoilla, ja sitten ne näyttäisivät muuttuvan ratkaisun edetessä varsin monimutkaisiksi, mutta sitten melkeinpä kaikki kumoaa tai yhdistyy muutamilla viimeisillä askeleilla, ja lopputuloksena on jotakin aivan absurdin yksinkertaista. (Sitten, kun palaat takaisin katsomaan ratkaisua, käy ilmi, että koko ajan oli olemassa helppo polku.)

Viitteen ja motivaation vuoksi jätän toteutuksen lihan tähän, ennen kuin selitän sen. Alleviivatut sanat ovat linkkejä vastaavaan koodiin githubissa.

public static IEnumerable<Sweep> WhenLineSweepsPoint(LineSegment pathOfLineStartPoint, LineSegment pathOfLineEndPoint, Point point) {var a = point - pathOfLineStartPoint.Start;var b = -pathOfLineStartPoint.Delta;var c = pathOfLineEndPoint.Start - pathOfLineStartPoint.Start;var d = pathOfLineEndPoint.Delta - pathOfLineStartPoint.Delta;return from t in QuadraticRoots(b.Cross(d), a.Cross(d) + b.Cross(c), a.Cross(c)) where t >= 0 && t <= 1 let start = pathOfLineStartPoint.LerpAcross(t) let end = pathOfLineEndPoint.LerpAcross(t) let s = point.LerpProjectOnto(new LineSegment(start, end)) where s >= 0 && s <= 1 orderby t select new Sweep(timeProportion: t, acrossProportion: s);}

En tiedä sinusta, mutta se, että yllä oleva koodi ratkaisee ongelman, hämmästyttää minua. Se vaikuttaa liian suoraviivaiselta ja silti liian irralliselta. Eikö siinä pitäisi olla vaikka kulmatapauksia? Lisäksi, mistä nuo yksinkertaiset ristikkäistuotteet tulivat? Miten niiden syöttäminen kvadraattiseen polynomiin auttaa? Tämä… kaipaa selitystä.

Intuitio

Aloitetaan pohtimalla joitakin tapauksia, joita saatamme kohdata, jotta saamme intuitiivisen tuntuman ongelmaan. Alla oleva animaatio näyttää useita erilaisia mahdollisia viivan liikkeitä:

Yksinkertainen: molemmat päätepisteet liikkuvat samalla nopeudella ja vain viivan normaalivektoria pitkin.
Sivusuunnassa: degeneroitunut tapaus, jossa viiva liikkuu omaa pituuttaan pitkin.
Nostaminen: toinen päätepiste liikkuu vaakasuoraan, kun taas toinen liikkuu pystysuoraan (”nostetaan” ja lasketaan viivaa).
Sukellus: toinen päätepiste liikkuu diagonaalisesti (’sukeltaa’ keskeltä läpi), kun taas toinen liikkuu pystysuunnassa.

Vaihtelevia pyyhkäisytapauksia

Huomaa, että viiva voi pyyhkäistä pisteen 0, 1 tai 2 kertaa, kun sen päätepisteet liikkuvat vakionopeudella kohdasta toiseen. Tapaus ’Raise’ sisältää kätevästi kaikki kolme mahdollisuutta. Tämän vuoksi ratkaisuun liittyy intuitiivisesti kvadraattinen yhtälö (jolla voi olla 0, 1 tai 2 erillistä reaalijuurta).

Toinen hyödyllinen oivallus on, että jotkin tapaukset, kuten vakionopeudella liikkuva tai paikallaan seisova viiva, vastaavat degeneroituneita kvadraattisia yhtälöitä, joissa korkeimman kertaluvun kerroin on nolla (esim. tai jopa ). Meidän on otettava tällaiset tapaukset mukaan testeihin.

Malli

Jotta suoran segmentti ja väliltä ja välille sisältäisi pisteen , on kahden ehdon täytyttävä. Ensinnäkin ”offset”-vektorin ja välillä on oltava yhdensuuntainen ”delta”-vektorin ja välillä. Tämä voidaan esittää matemaattisesti vaatimalla, että niiden ristitulo on nolla: $(c-p) \times (q-p) = 0$ . Tämä takaa, että on suoralla, jonka saa jatkamalla suorasegmenttiä molempiin suuntiin (tai että kyseessä on degeneroitunut yhden pisteen suorasegmentti). Toiseksi offset-vektorin skalaariprojektio delta-vektoriin on oltava oikealla alueella: $0 \leq s = \frac{(c-p) \cdot (q-p)}{(q-p)^2}} \leq 1$ . Tämä takaa, että ei ole kummankaan segmentin päätepisteen ohi.

Kun aika kulkee :stä :iin, viivasegmenttimme on pyyhkäissyt pisteen , jos ja vain jos on olemassa aika , jolloin nykyinen viivasegmentti sisältää . Koska viivasegmenttimme päätepisteet liikkuvat vakionopeudella, myös niiden kulkema polku on viivasegmentti. Päätepiste, joka liikkuu pisteestä pisteeseen , on lineaarisesti interpoloidussa pisteessä $lerp(p_0, p_1, t) = p_0 + (p_1 - p_0) \cdot t$ hetkellä . Huomaa, että lyhennän muotoon tilan säästämiseksi. Liittämällä liikkuvat pisteemme ’viivasegmentti sisältää pisteen’ -kaavoihin saamme selville, että meidän on löydettävä , joka täyttää $0 \leq t \leq 1$ ja $(c - (p_0 + p_d \cdot t)). \times ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t)) = 0$ ja $0 \leq s = \frac{(c-(p_0 + p_d \cdot t)) \cdot ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))}{((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))^2}} \leq 1$ .

Huomaa, että ”jonkin ristitulon on oltava yhtä suuri kuin 0″ ei ole ainoa tapa muotoilla ongelma. On myös järkevää ajatella sitä niin, että etsitään ja , jotka molemmat ovat välillä , siten, että on tulos siitä, että molempien päätepisteiden polun poikki lerpataan ja sitten päätepisteiden välissä lerpataan . Matemaattisesti tämä tarkoittaa . Muuttujat ja vastaavat karkeasti ”milloin” ja ”missä” leikkaus tapahtuu. Ongelman ratkaiseminen tässä muodossa on kuitenkin vaikeampaa, koska ei ole aluksi eristetty, joten käytän ristitulon kehystämistä (toisin kuin ensimmäisellä kerralla…).

Ratkaisu

Ristitulolla ja pistepotentiaalilla on joitain erittäin mukavia ominaisuuksia, jotka helpottavat :n eristämistä. Ensinnäkin ne jakavat yhteenlaskun, eli $u \times (v + w) = u \times v + u \times w$ ja $u \cdot (v + w) = u \cdot v + u \cdot w$ . Toiseksi skaalaus voidaan tehdä ennen tai jälkeen kumpaakin tuotetta, eli $(c \cdot u) \times v = c \cdot (u \times v)$ ja $(c \cdot u) \cdot v = c \cdot (u \cdot v)$ , missä on reaaliluku. Lopuksi, pistetuotto on kommutatiivinen eli $u \cdot v = v \cdot u$ , kun taas ristituotto on antikommutatiivinen eli $u \times v = -v \times u$ .

Soveltamalla tätä produktiotietämystä ja käyttämällä hieman jälkikäteen tietoa siitä, että osaamme käsitellä tiettyjä alilausekkeita yksittäisinä muuttujina, voimme muuttaa ristiproduktio-on-nolla -yhtälömme kvadraattiseksi yhtälöksi:

$\begin{align*} 0 =(c - (p_0 + p_d \cdot t)) \times ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t)) \\= ((c - p_0) - p_d \cdot t) \times ((q_0 - p_0) - (q_d - p_d) \cdot t) \\\= (a + b \cdot t) \times (c + d \cdot t) \\\\;\;\;\;\;\;\;\;\;\;\;missä\;\; a = c - p_0 \\\;\;\;\;\;\;\;\;\;\;missä\;\; b = -p_d \\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;jossa\;\; d = -(q_d - p_d) \\\= a \ kertaa c + a \ kertaa d \cdot t + b \ kertaa c \cdot t + b \ kertaa d \cdot t \cdot t \cdot t \\\= t^2 \cdot (b \ kertaa d) + t \cdot (a \times d + b \times c) + (a \times c) \end{align*}$

(Tämä on hauskasti yksinkertaisempi kuin reitti, jonka valitsin ensimmäisellä kerralla.)

Ah, nyt on selvää, mistä koodin ratkaisun muoto tuli. Lähdimme liikkeelle nollan suuruisesta ristitulosta (väittäen, että suoran ja pisteen välinen vektori oli samansuuntainen suoran kanssa) ja jouduimme jakamaan tulon, jotta saimme eristettyä sellaisten termien summat, jotka sisältävät :n eri potensseja. Näin saadaan luonnollisesti kvadraattinen yhtälö, jonka kertoimet sisältävät ristitulon. Siistiä!

Huomaa, että tämä on hyvin ”tukeva” yhtälö, koska emme koskaan olettaneet mitään vektoreista tai skalaareista matkan varrella. Emme esimerkiksi koskaan jaa (tai implisiittisesti kumoa) muuttujalla, joten emme ole ottaneet käyttöön mitään piileviä nollasta poikkeavia ehtoja.

Yhtälön mahdollisten arvojen määrittäminen yksinkertaistetulla yhtälöllä on vain tavallista ”ratkaise kvadraattinen polynomi” -juttua. Meidän on käsiteltävä kulmatapauksia nollilla, mikä tekee koodista hieman monimutkaisemman, mutta se on vain tylsää tapauskohtaista juttua, joten linkitän vain siihen.

Kun tiedämme :n mahdollisen arvon, voimme selvittää tarkalleen, missä törmäys tapahtui käyttämällä aiemmin mainittua plug-t-into-line-segmentti-pisteen-sulkeutumisen kaavaa: $s = \frac{(c-(p_0 + p_d \cdot t)) \cdot ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))}{((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))^2}$ . Kutsun tätä kaavaa :n ”lerp-projektioksi” suoralle hetkellä , koska se palauttaa osuuden , jolla lerpataan suoran alkupisteestä sen loppupisteeseen, jotta saadaan takaisin. Se on kätevä pieni menetelmä uuttaa:

public static double LerpProjectOnto(this Point point, LineSegment line) { var b = point - line.Start; var d = line.Delta; return (b * d) / (d * d); // when d == 0, result is +-infinity or NaN}

Viimeiseksi, kun meillä on ja , meidän on tarkistettava, että ne ovat välillä . Jos on alueen ulkopuolella, törmäystä ei tapahdu nykyisen aika-askeleen aikana. Jos on alueen ulkopuolella, törmäys tapahtuu jatketulla viivalla, mutta ei viivasegmentillä. Koska ja kuvaavat, kuinka paljon pitää lerpata, jotta löydetään milloin/missä törmäys tapahtui, se on myös hyödyllistä tietoa, joka palautetaan kutsujalle.

Yleistäminen

Tärkeä yksityiskohta, jota en ole vielä maininnut, on se, että liikkuva hiiren osoitin ei selvästikään vastaa pistettä. Onneksi voimme vain kumota hiiren osoittimen liikkeen viimeisen aika-askeleen aikana (olettaen, että se on lineaarinen) vähentämällä sen viivasegmentin liikkeestä. Tämä ei ainoastaan vähennä järjestelmää ratkaistavaksi, vaan tuloksena saadut – ja -arvot ovat voimassa ilman minkäänlaista käänteismuunnosta. Käyttö näyttää tältä:

// time goes from t0 to t1// line segment endpoint 1 moves from p0 to p1// line segment endpoint 2 moves from q0 to q1// point moves from c0 to c1var results = from hit in WhenLineSweepsPoint(new LineSegment(p0 - c0, p1 - c1), new LineSegment(q0 - c0, q1 - c1), new Point(0, 0)) let hitPos = new LineSegment(c0, c1).LerpAcross(hit.TimeProportion) let hitTime = t0 + (t1-t0)*hit.TimeProportion select new { p = hitPos, t = hitTime }foreach (var result in results) { System.Diagnostics.Debug.WriteLine(string.Format("Hit at p={0}, t={1}", result.p, result.t);}

Potentiaalinen komplikaatio on degeneroituneet viivasegmentit, joilla ei ole pituutta (joissa molemmat päätepisteet ovat yhtä pitkiä). Koodi ei käsittele tätä tapausta eksplisiittisesti, mutta toimii ikään kuin viivan, joka on itse asiassa piste, leikkaaminen olisi mahdotonta. Laskettaessa , jos se saavutetaan, se jaetaan nollalla. Tulos (joko – ääretön, + ääretön tai NaN) ei läpäise vaihteluvälin tarkistusta.

Toinen näkökohta, jota en ole käsitellyt, on ’leikkauskulma’. Eri tapauksia esittävässä animaatiossa punaiset leikkaukset on suunnattu lerppaamalla kahden päätepisteen nopeuksia :lla (kun tuloksena oleva nopeus on 0, valitaan satunnainen kulma). Olen kuitenkin käyttänyt myös vaihtoehtoisia lähestymistapoja, kuten ”leikkauskulma on pisteen nopeus”. Periaatteessa kyse on siitä, että käytetään sitä, mikä näyttää hyvältä ja tuntuu luonnolliselta sen sijaan, että yritetään selvittää ”leikkauskulman” todellinen merkitys.

Yhteenveto

Tämä ongelma muuttuu triviaaliksi heti, kun sovelletaan hieman tietoa lineaarialgebrasta. Se ei kai ole kovin yllättävää, sillä lineaarialgebraa (ja polynomeja) esiintyy kaikkialla, erityisesti geometriassa.

Tämän ongelman luonnollinen yleistys on sisällyttää siihen paksuudet. Ruudulle piirretyt viivat eivät loppujen lopuksi ole äärettömän ohuita. Paksuuden ottaminen mukaan on myös hyvä tapa vähentää liukulukuvirheiden vaikutusta, kun ne pyöristyvät eri suuntiin eri aika-askeleiden aikana. Toinen hyödyllinen muutos olisi kyky käsitellä parabolisia polkuja, koska peliobjektit ovat usein vapaassa pudotuksessa. Toisaalta on varmaan helpompaa käsitellä ’paksuja viivoja’ polygoneina vakionopeuksisilla aika-askeleilla.

–

Keskustele Redditissä

–

Twisted Oak Studios tarjoaa konsultointia ja kehitystyötä interaktiivisissa korkean teknologian projekteissa. Tutustu portfolioon tai huuda meille, jos sinulla on jotain, jonka kanssa joidenkin todella radikaalien insinöörien pitäisi mielestäsi auttaa sinua.

Savage Rose

Liikkuvan viivan leikkaaminen liikkuvan pisteen kanssa | Twisted Oak Studios -blogi