Share
I min tidigare handledning om kollisionsdetektering mellan en cirkel och en linje täckte jag projektionen på en rad med hjälp av punktens produkt av en vektor. I denna handledning ska vi titta på den vinkelräta punktprodukten och använda den för att förutse skärningspunkten för två linjer.
Låt oss ta en titt på det slutliga resultatet vi kommer att arbeta för. Använd vänster och höger piltangenter för att styra skeppet (triangeln) och tryck på för att öka hastigheten tillfälligt. Om den projicerade framtida kollisionspunkten ligger på väggen (linjen), kommer en röd punkt att målas på den. För en kollision som "redan" hände (det vill säga skulle ha hänt tidigare, baserat på nuvarande riktning) kommer en röd punkt fortfarande att målas men är lätt genomskinlig.
Du kan också klicka med musen och dra de svarta punkterna för att flytta väggen. Observera att vi inte bara förutsäger kollisionsplatsen utan även tiden.
Innan vi kommer in i ämnet, låt oss göra en del revision. Här är punktproduktekvationen (tidigare täckt här):
Och här är den vinkelrätta punktproduktdefinitionen som extraherad från Wolfram:
Nu för att hjälpa oss att bilda en mental bild, har jag förberett bilden nedan. Jag är övertygad om att du kan härleda vertikala och horisontella komponenter i en vektor så att komponenterna med sinus och cosinus inte ska vara en utmaning.
Låt oss ersätta båda komponenterna med motsvarande. Jag har använt A med en hatt för att representera enhetsvektorn av A (det vill säga en vektor som pekar i samma riktning som A men har en magnitud på exakt 1). En annan detalj är att den vinkelrätta av B faktiskt är den normala av B - mer på normala nästa steg.
Från diagrammet ovan kan vi se att projiceringen av B på A kommer att producera | B | * cos (theta). Men varför skulle projiceringen av B: s normala produktion | B | * sin (theta)?
För att bättre förstå detta har jag tagit med en Flash-demo nedan. Klicka och dra det svarta pilhuvudet. När du rör dig försiktigt så märker du att dess vinkelrät axel också följer. När de vänder, kommer de djärva röda linjerna också att animeras. Observera att dessa två längder är desamma - därav ekvationen för vinkelrätt punktprodukt.
Normaler ligger per definition på en vinkelrät linje som skär din intresse. Låt oss försöka föreställa oss dessa linjer på ett geometriskt plan.
Det kartesiska koordinatsystemet används i diagrammet ovan. B är vänster normal och C är rätt normal. Vi ser att x-komponenten i B är negativ (eftersom den pekar mot vänster) och y-komponenten i C är negativ (eftersom den pekar ner).
Men kolla in likheterna mellan B och C. Deras x- och y-komponenter är desamma som A: s, förutom swizzled. Skillnaden är bara teckenets position. Så vi når en slutsats av bilden nedan.
Observera att vi specifikt hänvisar till cartesianska koordinatsystem i detta exempel. Y-axeln av Flashs koordinatutrymme är en återspegling av den i Cartesian, vilket resulterar i en byte mellan vänster och höger normal.
För att räkna ut kollisionspunkten för vektor k på planet A, ska vi länka upp svans av k med en godtycklig punkt på planet A först. För fallet nedan är vektorn j länkvektorn; då får vi den vinkelräta utskjutningen av k och j på planet A.
Den röda pricken på bilden nedan är kollisionspunkten. Och jag hoppas att du kan se den liknande triangeln i diagrammet nedan.
Således med tanke på de tre komponenterna ovan kan vi använda begreppet förhållande för att härleda längden mellan de röda och blåa punkterna. Slutligen sätter vi storleken på vektorn k till nämnda längd och vi har vår kollisionspunkt!
Så här kommer ActionScript-implementeringen. Jag har tagit med en demo nedan. Försök flytta pilhuvudena så att båda linjerna skärs. En liten svart punkt markerar skärningspunkten för linjerna. Observera att dessa segment inte nödvändigtvis skär varandra, men de oändliga linjerna de representerar är.
Här är manuset som gör beräkningarna. Checka ut Basic.as i källans nedladdning för hela skriptet.
omräkning av privata funktioner (): void reorient (); / * Förklara: * v1 och v2 är vektorer för att representera båda linjesegmenten * v1 förenar set1b (svans) till set1a (huvud) - analog med vektor k i diagram * v2 sammanfogar set2b (svans) till set2a (huvud) * tillV2b är vektor analog med det för vektor j i diagram * / var perp1: Number = v1.perpProduct (v2.normalise ()); var toV2b: Vector2D = ny Vector2D (set2b.x - set1b.x, set2b.y - set1b.y); var perp2: Number = toV2b.perpProduct (v2.normalise ()); / * Förklara: * Längden beräknas från samma trianglar-förhållande * Det används senare som storleksordning för en vektor * som pekar i v1s riktning * / var längd: Number = perp2 / perp1 * v1.getMagnitude (); var length_v1: Vector2D = v1.clone (); length_v1.setMagnitude (längd); / * Förklara * sträcka för att hitta den exakta platsen för kollisionspunkten * / intersec.x = set1b.x + length_v1.x; intersec.y = set1b.y + length_v1.y;
Så jag hoppas att det första sättet jag presenterat var lätt att förstå. Jag förstår prestanda när det gäller att korsningspunkten är viktig, så nästa kommer jag att tillhandahålla alternativa tillvägagångssätt, även om det kommer att kräva några matematiska revisioner. Stå ut med mig!
Låt oss först tala om linjekvationer. Det finns flera former av linjekvation men vi berör bara två av dem i denna handledning:
Jag har tagit med bilden nedan för att hjälpa dig att återkalla. De som är intresserade av detta kan hänvisa till denna post på Wikipedia.
Innan vi utför några manipuleringar på två linjeläkningar måste vi härleda dessa linjekvationer först. Låt oss överväga det scenario där vi ges koordinater för två punkter p1 (a, b). och p2 (c, d). Vi kan bilda en linjekvation som förbinder dessa två punkter från gradienterna:
Med hjälp av denna ekvation kan vi härleda konstanterna A, B och C för standardformen:
Därefter kan vi fortsätta att lösa samtidiga linjekvationer.
Nu när vi kan bilda linjekvationer, kan vi fortsätta att ta två linjeläkningar och lösa dem samtidigt. Med tanke på dessa två linjekvationer:
Jag ska tabell dessa koefficienter enligt den allmänna formen Ax + By = C.
| en | B | C |
| E | F | G |
| P | Q | R |
För att få värdet av y gör vi följande:
| en | B | C | Multiplicera med |
| E | F | G | P |
| P | Q | R | E |
Och vi kommer fram till följande tabell.
| en | B | C |
| EP | FP | GP |
| PE | QE | RE |
När vi subtraherar två ekvationer ut anländer vi till:
Fortsätter för att få x:
| en | B | C | Multiplicera med |
| E | F | G | Q |
| P | Q | R | F |
Vi kommer fram till följande tabell
| en | B | C |
| EQ | FQ | GQ |
| PF | QF | RF |
När vi subtraherar de två ekvationerna kommer vi fram till:
Låt oss omorganisera y.
Så vi anländer till korsningspunkten för x och y. Vi märker att de delar samma nämnare.
Nu när vi har utarbetat matematikoperationen och fått resultatet, plockar vi bara in värden och vi har skärningspunkten.
Här är ActionScript-implementeringen. Så alla vektoroperationer reduceras till enkel aritmetik men det kommer att kräva några algebraarbeten i början.
omräkning av privata funktioner (): void reorient (); var E: Number = set1b.y - set1a.y; var F: Number = set1a.x - set1b.x; var G: Number = set1a.x * set1b.y - set1a.y * set1b.x; var P: Number = set2b.y - set2a.y; var Q: Number = set2a.x - set2b.x; var R: Number = set2a.x * set2b.y - set2a.y * set2b.x; var nämnare: Number = (E * Q - P * F); intersec.x = (G * Q-R * F) / nämnare; intersec.y = (R * E-G * P) / nämnare;
Naturligtvis är det samma resultat som tidigare demo, bara med mindre inblandade matriser, och utan användning av Vector2D klass.
Ett annat alternativ till att lösa detta problem är med hjälp av matrismatris. Återigen bjuder jag intresserade läsare att dyka in i Prof. Wildbergers föreläsning om linjeledningar. Här kommer vi bara att bläddra igenom konceptet snabbt.
Enligt prof Wildberger finns det två ramar som vi kan anta:
Låt oss gå igenom den Cartesian en först. Kolla in bilden nedan.
Observera att matrisen T och S innehåller konstanta värden. Vad som är kvar är okänt A. Det är därför som omarrangerar matrisekvationen i form av A kommer att ge oss resultatet. Vi måste emellertid få den inverse matrisen av T.
Här är implementeringen av ovanstående med ActionScript:
omräkning av privata funktioner (): void reorient (); var E: Number = set1b.y - set1a.y; var F: Number = set1a.x - set1b.x; var G: Number = set1a.x * set1b.y - set1a.y * set1b.x; var P: Number = set2b.y - set2a.y; var Q: Number = set2a.x - set2b.x; var R: Number = set2a.x * set2b.y - set2a.y * set2b.x; var T: Matris = ny matris (E, P, F, Q); T.invert (); var S: Matrix = ny matris (); S.a = G; S.b = R; S.concat (T); // multiplicera matrisen intersec.x = S.a; intersec.y = S.b;
Slutligen finns det den parametriska formen av linjekvationen, och vi ska försöka lösa det genom matrismatematik igen.
Vi skulle vilja få korspunkten. Med all information utom för u och v som vi försöker hitta, ska vi skriva om båda ekvationerna i matrisform och lösa dem.
Så igen utför vi matrismanipuleringar för att komma fram till vårt resultat.
Så här är implementeringen av matrisformen:
rivatfunktion omräkning (): void reorient (); / * Förklara: * r, s refererar faktiskt till komponenter av v2 normaliserad * p, q refererar faktiskt till komponenter av v1 normaliserade * / var norm_v2: Vector2D = v2.normalise (); var norm_v1: Vector2D = v1.normalise (); var a_c: Number = set1b.x - set2b.x; var b_d: Number = set1b.y - set2b.y; var R: Matrix = ny Matrix; R.a = norm_v2.x; R.c = norm_v1.x; R.b = norm_v2.y; R.d = norm_v1.y; R.invert (); var L: Matrix = ny Matrix; L.a = a_c; L.b = b_d; L.concat (R); intersec.x = set2b.x + L.a * norm_v2.x; intersec.y = set2b.y + L.a * norm_v2.y;
Vi har täckt fyra sätt att lösa detta lilla problem. Så vad sägs om prestanda? Tja, jag tror att jag bara lämnar denna fråga till läsare att döma, även om jag tror att skillnaden är försumbar. Känn dig fri att använda denna prestanda test sele från Grant Skinner.
Så nu när vi har fått denna förståelse, vad är nästa? Applicera det!
Antag att en partikel rör sig i en väg som är bunden att kollidera med en vägg. Vi kan beräkna tiden för påverkan av den enkla ekvationen av:
Hastighet = Förskjutning / Tid
Tänk dig att du är inuti denna orange runda partikel och för varje passande ram och meddelandet görs på tiden för att kollidera med väggen. Du hör:
"Tid för påverkan: 1,5 ramar" - Ram 1
"Tid för påverkan: 0,5 ramar" - Ram 2
"Tid för påverkan: -0,5 ramar" - Ram 3
När vi når ram 3 har kollision med rad redan hänt (som indikeras av negativt tecken). Du måste spola tillbaka tiden för att nå kollisionspunkten. Självfallet kollision ska hända någon gång mellan ramar 2 och 3, men Flash rör sig i enkla steg steg. Så om kollision inträffade halvvägs mellan ramar, kommer en flip av tecknet till negativ att indikera att kollisionen redan har hänt.
För att få negativ tid använder vi vektorpunktsprodukten. Vi vet att när vi har två vektorer och riktningen av en inte ligger inom 90 grader från varandra, kommer de att producera en negativ punktprodukt. Dotprodukten är också ett mått på hur parallella två vektorer är. Så när kollision redan har hänt kommer hastigheten och riktningen för en vektor till en punkt på väggen att vara negativ - och vice versa.
Så här är manuset (ingår i CollisionTime.as). Jag har också lagt till kollisionsdetektering inom linjesegmentet här. För dem som tycker det är obekant, hänvisa till min handledning om kollisionsdetektering mellan en cirkel och ett linjesegment, steg 6. Och för hjälp med att styra fartyg, här är en annan referens.
Accentsconagua
// bestämmer om inom väggsegmentet var w2_collision: Vector2D = ny Vector2D (collision.x - w2.x, collision.y - w2.y); collision.alpha = 0; // när fartyget går till vänster om väggen om (w2_collision.dotProduct (v1) < 0) t.text = "Ship is heading to left of wall"; else //when ship is heading to right of wall if (w2_collision.getMagnitude() > v1.getMagnitude ()) t.text = "Ship är på väg mot väggen" // när fartyget går till vägsegmentet annat var ship_collision: Vector2D = new Vector2D (collision.x - ship.x, collision. y - ship.y); varförskjutning: Number = ship_collision.getMagnitude (); om (ship_collision.dotProduct (velo) < 0) displacement *= -1; //showing text var time:Number = displacement / velo.getMagnitude(); t.text = "Frames to impact: " + time.toPrecision(3) + " frames.\n"; time /= stage.frameRate; t.appendText("Time to impact: " + time.toPrecision(3) + " seconds.\n"); //drop down alpha if collision had happened if (displacement > 0) kollision.alpha = 1; annars collision.alpha = 0.5; t.appendText ("Kollisionen hade redan hänt.") Så här är en demonstration av vad du kommer fram till. Använd vänster och höger piltangenter för att styra skeppet (triangeln) och tryck på Upp för att öka hastigheten tillfälligt. Om den förutspådda framtida kollisionspunkten ligger på väggen (linjen), kommer en röd punkt att målas på den. För kollision som "redan" har hänt, kommer en röd punkt fortfarande att målas men är lätt transparent. Du kan också dra de svarta prickarna på vardera sidan av väggen för att flytta den.
Så jag hoppas att denna handledning har varit informativ. Dela om du faktiskt har tillämpat den här idén på andra ställen än den jag har nämnt. Jag planerar en kortfattad skrivning om att applicera den för att måla lasermål - vad tycker du? Tack för att du läste och låt mig veta om det finns några fel.
