Quad-tree culling

Efter mycket slit och mycket fel har jag skapat en fungerande quad-tree till min terräng. den fungerar enligt följande:

1: Terrängen skapar sig själv utifrån en höjdmap skapar jag ett rutnät av vertices med med textur-coordinater. Sen med hjälp av mina vertices skapar jag ett "temporärt index" för hela terrängen. det används sedan för att beräkna mina normaler.

2: Terrängen delar upp sina vertices i fyra noder
Varje nod är en egen instans av klassen quad-node och innehåller specifik data
såsom en egen vertex och index-buffert, bredd, höjd och en boolean som är true om noden är en "leaf-node"

3: Varje nod kommer i sin tur dela upp sig i fyra nya noder och vidare i fyra noder osv, tills varje nod har fått en lämlig storlek. Man kan se detta som ett släktträd att varje nod har fyra barn som i sin tur får fyra barn.
En definierad variabel "2Dvektor max_size" bestämmer hur stor en nod får vara, om noden är mindre eller lika med max_size så är det en leaf-node och kommer skapa en egen index-buffert och vertex-buffert.

4: Varje nod kommer även ha en funktion för att "känna av" om den befinner sig innanför kamerans synvinkel dvs om den är synlig.

Jag har byggd lite hjälpfunktioner bla skapat en funktion för att skapa en bounding-box som precis innesluter alla vertices i en nod.

5: Ca 60 ggri sekunden kommer varje nod att "känna" om den fortfarande befinner sig innanför kamerans vy.

Gör den det kommer att "fråga" sina barn om de befinner sig innanför kamerans vy.

Låt oss säga att två av barnen finns i kamerans vy och två inte gör det. De två som befinner sig i kamerans vy kommer i sin tur fråga sina barn om de befinner sig i kamerans vy osv.
Om inte noden har några barn så kommer noden att beräkna sig själv och måla sig vacker med bergsformationer och gräs och ljus-sättning!

Som sagt allt detta sker ca 60 ggr i sekunden och kan verkas vara väldigt omständigt men tvärt-om spar man många beräkningar

Resultatet:



Som ni ser har jag beräknat lite fel. Men koden fungerar i alla fall. Resultatet av detta skulle bli att de noder dvs terrängpartier som inte finns i kameran vy inte skulle beräkna sig själva.
Nu verkar mina noder vara beräkna fel eftersom vissa av dem "tror" att de inte befinner sig i kamerans vy fast de igentligen gör det. Hur som helst fungerar grund-principen i koden och jag återkommer med en lösning för mina noder...

För debug-synpunkt har jag en funktion som renderar linjer utifrån de fyra hörnen på en bounding-box. Det verkar som om terrängen åtminståne partitionerar upp sig korrekt så problemet inte i skapandet av terrängen utan i renderingen där den visst kalkulerar fel nånstans.

En intelligent terräng2

En dator är dum dum burk men med stor potensial. Det kluriga med realtids-3d-programmering är att allt ska gå fort. För att det ska gå fort ska inte datorn beräkna massa onödiga beräkningar på sånt som inte är synligt i skärmen för tillfället. dvs. regel nummer ett:
Allt som inte syns ska INTE finnas!
Detta kallas CULLING.

Min terräng måste vara intelligent dvs, bara de delar av terrängen som för tillfället syns på skärmen ska beräknas och renderas! Detta är inte så lätt som det låter eftersom en terräng är som ett stort rutnät av trianglar som man inte bara kan klippa i hur som helst.

CULLING är A och O i spelprogrammering eftersom det är avgörande för om ett spel kommer bli spelbart i slutändan.

Den teknik jag ska använda för culling heter Quad-Tree culling, dvs terrängen kommer från början dela upp sig i 4 mindre terräng-partitioner som i sin tur delar upp sig i 4 partitioner var så det blir 16, som i sin tur delar sig osv.

Till slut kommer terrängen bestå av en jäkla massa små partitioner i lämplig storlek.

Varför? JO istället för en stor terräng så skapar jag en massa mindre terräng-partitioner som är självtänkande men ändå sammarbetar med varnadra. Varje partition ska känna av om den befinner sig i synfältet och beräkna sig själv om den gör det. Annars ska den INTE beräkna sig själv.

Resultatet blir att bara de partitioner som finns i synfältet kommer beräkna sig själva och skapa en terräng inte EXISTERAR bakom kameran. Coolt va? Det är inget som en spelare märker med är fullständigt nödvändigt för att ett spel ska fungera

läs mer om quadtree-culling: http://en.wikipedia.org/wiki/Quadtree

En intelligent terräng

Det var ett tag sen jag skrev. Under de senaste tiden har jag jobbat på att utvecklat min terräng rejält.

En rödfärgad terräng är inte speciellt snyggt utan jag har utvecklat mer realistiska terräng-material såsom berg och gräs, Sådana material ligger som en yta på terrängen och kallas texturer

Min terräng är helt och hållen ritat med triangle-strip som grund, triangle-list skulle vara enklare men tar mer plats i index-bufferten. Här är strukturen för min terrain-vertex. Den har för tillfället givetivs en vector3 position i värld-matrisen, en textur-koordinat.

Jag tog bort stödet för normaler eftersom terrängen ska vara statisk, ev läsa in normaler från en normalmap.

Arrayen med vertexellement är nödvändig för till ex vertex-deklaration, och när vertexen ska läsas i en ström.

den har också en statisk variabel för sin egen storlek i bytes.


public struct TerrainVertex
{
public Vector3 Position;
public Vector2 TextureCoordinate;
public static readonly VertexElement[] VertexElements =
{
new VertexElement(0,0,VertexElementFormat.Vector3,VertexElementMethod.Default,VertexElementUsage.Position,0),
new VertexElement(0,sizeof(float)* 3,VertexElementFormat.Vector2,VertexElementMethod.Default,VertexElementUsage.TextureCoordinate,0)
};
public static readonly int SizeInBytes = sizeof(float) * (3 + 2 );
}

eftersom terrängen kommar ha mellan 6 till 10 texturer (om jag får bestämma) med olika blendweights så är det inte att föredra att kasta runt massa texturer i parametrar. jag har därför också skapat en enklare textur inehållande terrängen alla material:


//En struktur för ett material med 4 texturer;
public struct TerrainMaterial
{
public Texture2D texture1;
public Texture2D texture2;
public Texture2D texture3;
public Texture2D texture4;
public Texture2D mipMap1;
public float scale;
}

HöjdMapp

Jag har även skapat en funktion för att räkna ut höjpunkter på min terräng utifrån en höjdmapp d.v.s. en vanlig bildfil där varje pixel motsvarar en vertex i terrängen. pixeln's ljusstyrka bestämmer sedan höjden där. färgen vit (255,255,255) är hösta punkt och svart (0,0,0) är lägsta. Här använder jag en egenskriven shader som ger färg till terrängen utifrån höjd-skillnad. fullkommligt värdelös shader men ändå:P

Nosie shaded

Min noise-terräng med standard-Shader. En sak att tillägga är att jag även skapat en funktion som räkanar ut normalen för varje vertex d.v.s. riktingen dit vertexen pekar. Normalen behövs för att beräkna en enkel sljussättning och är beräknad på kors-produkten mellan "kanterna" på varje triangel. Korsprodukten är en funktion som är super som jag inte orkar förklara här för min blogg skulle bli oändlig men läs om den här: http://en.wikipedia.org/wiki/Cross_product

Jag lägger på en färg och skickar mina vertex till en för-definierad "Shader" som simulerar ljus-riktning. Den kommer jag inte använa sen utan jag kommer skapa men egen målare :P men den är bra för att se resultat. höjden är beräknad efter en sinus funktion efter vertexens x-poisition.

Lite kullar i landskapet

Jag låter en slump generator positionera ut olika höjder till mina vertex för att få lite höjd-skillnader: