Binær rumopdeling er en metode til rekursiv opdeling af det euklidiske rum i konvekse mængder og hyperplaner . Som et resultat er objekterne repræsenteret som en datastruktur kaldet et BSP-træ .
BSP-træet bruges til effektivt at udføre følgende operationer i 3D -computergrafik :
BSP-træer blev først brugt af LucasArts i begyndelsen af 80'erne. De vandt popularitet blandt udviklere takket være id Software , som udviklede Doom ( 1993 ) og Quake ( 1996 ) motorerne.
I et BSP-træ er hver knude forbundet med en opdelingslinje eller et plan i henholdsvis 2D- eller 3D-rum. I dette tilfælde tilhører alle objekter, der ligger på forsiden af planet, det forreste undertræ, og alle objekter, der ligger på bagsiden af planet, tilhører det bagerste undertræ. For at afgøre, om et objekt hører til for- eller bagsiden af en splitlinje eller et plan, er det nødvendigt at undersøge placeringen af hvert af dets punkter. Et punkts position i forhold til planet bestemmes af skalarproduktet af normalen af planet og punktets koordinater i homogene koordinater . Tre tilfælde er mulige:
Hvis skalarproduktet for alle punkter af objektet er større end 0, så hører det til det frontale undertræ. Hvis skalarproduktet for alle punkter af objektet er mindre end 0, så hører det til det omvendte undertræ. Hvis skalarproduktet for alle punkter af et objekt er lig med 0, så er det lige meget, hvilket undertræ det tilhører. Hvis skalarprodukterne for punkterne på et objekt har et andet fortegn, skæres det af splitplanet, så de resulterende objekter kun ligger på forsiden eller kun på bagsiden. For hver underknude i BSP-træet er ovenstående udsagn sand, med den undtagelse, at kun de objekter, der hører til for- eller bagsiden af opdelingsplanet for moderknuden, er genstand for overvejelse.
Ovenstående definition beskriver kun egenskaberne for et BSP-træ , den siger ikke, hvordan det skal bygges. Som regel er et BSP-træ bygget til et sæt segmenter på et plan eller polygoner i rummet, der repræsenterer en bestemt figur eller scene. Overvej algoritmen til at konstruere et BSP-træ for et sæt polygoner i rummet:
Spaltningsplanet er valgt på en sådan måde, at træet balanceres, det vil sige, at antallet af polygoner i for- og bagundertræet er omtrent det samme:
min(|N(Fi) - N(Bi)|)
hvor N(Fi) er antallet af polygoner på forsiden af et splitplan i, N(Bi) er antallet af polygoner på bagsiden af splitplanet i.
Ved sortering af objekter i rækkefølge for fjernelse fra observatøren, ved hjælp af BSP-træet, undersøges de relative positioner af vektoren og observationspunktet ( POV ) og normalerne for de brydeplaner. Hvis normalen af splitplanet og observationsvektoren er co -directed , så er det forreste undertræ længere fra observatøren end det omvendte, ellers er det omvendte undertræ længere fra observatøren end det forreste. I dette tilfælde, hvis opdelingsplanet er bag observatøren, så er selve flyet, såvel som det forreste eller bagerste undertræ muligvis ikke fuldt synligt. Den rekursive algoritme til sortering af polygoner ved hjælp af et BSP-træ er som følger:
Procedure BypassNode(Node) Hvis Node <> NULLPointer Hvis vektorer er co-dirigeret (observationsvektor, node.normal for splitplan) Hvis DotProduct(ObservationPoint, Node.Normal for SplitPlane) >= 0 // Flyet er bagved observatøren, observatøren ser kun det forreste undertræ TraverseNode(Node.FrontSubtree); Ellers // Flyet er foran observatøren, // forreste undertræ er længere end bagerste undertræ TraverseNode(Node.FrontSubtree); AddPolygonToDisplayList(Node.Polygon); TraverseNode(Node.ReverseSubtree); Afslut Hvis; Ellers Hvis DotProduct(ObservationPoint, Node.Normal for SplitPlane) >= 0 // Flyet er foran observatøren, // bagerste undertræ er længere end det forreste undertræ TraverseNode(Node.ReverseSubtree); AddPolygonToDisplayList(Node.Polygon); TraverseNode(Node.FrontSubtree); Ellers // Flyet er bagved observatøren, observatøren ser kun det omvendte undertræ TraverseNode(Node.ReverseSubtree); Afslut Hvis; Afslut Hvis; Afslut Hvis; Ende;Denne algoritme kan optimeres, hvis vi tager højde for, at træet for et bestemt sæt polygoner har en degenereret struktur, i det tilfælde, hvor for hver polygon fra dette sæt alle de resterende polygoner kun ligger på forsiden eller kun på bagsiden. Det er præcis, hvad John Carmack gjorde i DOOM -motoren . .
Algoritmen til at fremskynde fra rekursiv kan konverteres til iterativ.
Klipning af usynlige overflader implementeres ved at indføre yderligere information i BSP-træet , såsom rammer (afgrænsningsfelter, afgrænsningssfærer). Rammer er rektangler eller parallelepipeder, cirkler eller kugler, der begrænser området, hvor polygonerne i et bestemt undertræ er placeret. Hver node har således to rammer. Undertræet er garanteret usynligt, medmindre den visuelle pyramide skærer det afgrænsende objekt. Det omvendte er ikke sandt. En direkte erklæring er dog tilstrækkelig til at afskære behandlingen af et betydeligt antal genstande.
Valget af geometriske objekter, der repræsenterer rammer, kommer fra enkelheden af algoritmen til at kontrollere skæringspunktet mellem den visuelle pyramide og rammen.
Når man søger efter kollisioner, bruges BSP-træet til at finde det fly, der er tættest på objektet. Oftest er grænserne for et objekt givet af en afgrænsende kugle (eller cirkel) for at forenkle beregninger. BSP-træet krydses fra roden til det plan, der er tættest på objektet. I dette tilfælde, hvis der ikke detekteres nogen skæringer af den afgrænsende sfære med noget plan, er der ingen kollision, ellers er der det.
Eksempel:
Collision Finder-procedure (knude, objekt) Hvis Node <> NULLPointer If Distance(Knot.Plane, Object.BoundingSphereCenter) > Object.BoundingSphereRadius Hvis DotProduct(Object.BoundingSphereCenter, SplitPlaneNode.Normal) >= 0 // Objektet er på forsiden af brydeplanet, // kryds kun det forreste undertræ FindCollision(Node.FrontSubtree, Object); Ellers // Objektet er på bagsiden af splitplanet, // kryds kun det omvendte undertræ FindCollision(Node.ReverseSubtree, Object); Afslut Hvis; Ellers Retur er kollision; Afslut Hvis; Ellers Returner ingen kollision; Afslut Hvis; Ende;Algoritmen til at fremskynde fra rekursiv kan konverteres til iterativ.
| Træ (datastruktur) | |
|---|---|
| Binære træer | |
| Selvbalancerende binære træer |
|
| B-træer | |
| præfiks træer |
|
| Binær opdeling af rummet | |
| Ikke-binære træer |
|
| At bryde rummet op |
|
| Andre træer |
|
| Algoritmer |
|