[C++] Terrein generator

[Verwijderd]

Hello,

Ik werk momenteel aan een random terrein generator in C++ en vroeg me af welke features nog ontbreken om meerdere types van landschappen in te bouwen. Bijvoorbeeld:
- wat voor soorten ruis kan ik gebruiken? (maar dan niet zomaar random ruis)
- wat voor soorten heuvels/dallen
- ...

Ik vraag niét voor foto's ofzo - want die kan ik zelf ook opzoeken - maar voor programmeer-technieken/tips. Je mag natuurlijk wél een foto posten als je vind dat het je algoritme verduidelijkt.

Voorlopig kan je hier al een demo zien:
http://users.pandora.be/k...code/Terraingenerator.exe
Nieuw linkje
't is slechts 8kb groot en omvat de generator én de 3d 'engine' in OpenGL.

[ Voor 13% gewijzigd door Verwijderd op 10-01-2005 22:23 . Reden: Link update ]

[Janoz]

Wat gebruik je nu? Het midpoint displacement algoritme is IMHO 1 van de betere voor het genereren van landschappen. Persoonlijk vind ik de gegenereerde landschappen niet zo heel erg mooi... Daarnaast doet ie er eigenlijk ook veel te lang over

Ff plaatje van mijn eigen landschapgenerator (was practicum) Hierbij hebben bepaalde hoogtes ook hun eigen kleur (erg simpel ) De perspectief instelling klopt niet helemaal, maar dit was het enige plaatje dat ik nog kon vinden

[ Voor 37% gewijzigd door Janoz op 09-01-2003 11:39 ]

[Zoijar]

Hoe ik het ooit heb gedaan (weet niet of je er iets aan hebt)

- begin met een vierkant
- subdivide alle vierkanten in 4 nieuwe vierkanten
- op het midden van elke edge displace dat punt in de ricthing van de normaal. Als offset gebruik je een normaal verdeelde waarde om 0, met variantie = |lengte edge in kwadraat| verheven tot de macht (2 - fractal_dimension)
- en recurse

Die fractal dimension bepaald de ruigheid van het terrein. Waardes tussen de 1.2 en 1.7 doen het wel goed. Dan kan je daarna al die vierkanten gebruiken als control points voor spline patches (nurbs patches ofzo)

[Janoz]

Zoals ik al zei.. midpoint displacement algoritme ..

Kleine toevoeging op zoijar:
Neem de hoekpunten van het eerste vierkant random (ander zitten die altijd op dezelfde hoogte)
Het punt hoeft niet in de richtin gvan de normaal verplaatst worden. Het is uiteindelijk makkelijker om gewoon de z value te varieren waardoor de x en y stapg grootte altijd gelijk blijft.

Belangrijk onderdeel van het algoritme is dat de verschuiving van het punt afhangt van de oppervlakte van het vierkant. Hierdoor zijn er over grote afstanden grote hoogte verschillen terwijl dit over kleine afstanden veel minder is.

[DaCoTa]

Spherical Landscapes: Dit is een van de mooiste resultaten die ik ken voor landscape generation. Dit is volgens mij ook te vertalen naar een plat vlak, maar wat voor resultaat dat geeft, weet ik niet.

Kijk verder ook eens op Artificial Terrain Generation.

Toevoeging: de plasma fractal generation algoritmen geven vaak erg lelijke artefacten op de eerste splitsingen. Ik zou sterk afraden om daarmee aan de slag te gaan.

[ Voor 18% gewijzigd door DaCoTa op 09-01-2003 12:25 ]

[Zoijar]

DaCoTa schreef op 09 januari 2003 @ 12:24:
Toevoeging: de plasma fractal generation algoritmen geven vaak erg lelijke artefacten op de eerste splitsingen. Ik zou sterk afraden om daarmee aan de slag te gaan.

Daarom gebruik je ze niet rechtstreeks maar als control points voor patches. Werkt best aardig, maar toegegeven is het niet de beste/meest realistische techniek

[SWfreak]

Nog een ander voorbeeld a la spherical landscapes: www.robot-frog.com/3d/

[.oisyn]

Ik heb voor een computergraphics casus bij ons op school ook gebruik gemaakt van het midpoint-displacement algoritme:

(klik voor een grote versie )


Alleen met alleen dat algoritme ben je er nog niet, het terrein zal of te ruig zijn, of juist niet waardoor er in het geheel weinig hoogteverschil is. Wat je eraan kunt dun is een paar blur filters eroverheen gooien. Hierboven is geloof ik alles onder en boven de rotsen geblurred, en alles onder het gras ook nog eens een keer. Vervolgens wordt alles beneden een bepaalde waarde op die waarde gezet (water dus)

Voor coloring of texturing kun je gebruik maken van een samenstelling van verschillende lagen. De lagen die hierboven gebruikt zijn zijn zand, gras, rots en sneeuw. De factoren van die lagen zijn afhankelijk van de hoogte en de steilheid van een stuk land. Steile stukken zijn voornamelijk rots: er blijft geen sneeuw op liggen, er groeit geen tot weinig gras op, en er is geen strand aan de voet van de berg

Voor occlusion culling is een quadtree uitermate geschikt. Gewoon de view frustum testen met de nodes in de quadtree en je kunt zo zien wat gerenderd kan worden en wat niet.

Voor LODding zou je ROAM kunnen gebruiken, maar is over het algemeen te CPU intensief. Ik denk dat het handigst is als je gewoon de patches in de leafs van je quadtree downsamplet (hoeveel engelse woorden passen er in een nederlandse zin? ), zeg maar het tegenovergestelde van subdivision. Wel opletten dat een patch die naast een andere patch ligt maar 1 LOD lager is goed aansluit bij de randen.
Dat kun je doen door de vertex van de andere patch die in het midden van de rand ligt op goede hoogte te zetten, maar dit kan zorgen voor gaten omdat de edges niet goed aansluiten door afrondingsfouten e.d.
Een andere optie is om die vertex gewoon te verwijderen, of er juist een aan te maken in de patch die van lagere kwaliteit is

[killercow]

als je zoekt naar "isometric engine" in google kom je enkele zeer makkenlijke map generator algoritmen tegen die via 3 verschillende algoritmen mooi hoogtemaps kunnen maken welke niet te stijle drops en steeps hebben.

En anders gewoon de photoshop clouds filter uitpluizen die is ook erg mooi om hoogtemaps te maken. deze gebruik ik voor mijn isometrische engine in php .

[Zoijar]

Na dat gezien te hebben van die spherical generator dacht ik er ineens aan om marching cubes te gebruiken. Ik weet niet of dit werkt, nooit geprobeerd eigenlijk maar het kan een idee zijn. Je maakt zeg maar steeds "blobs" met varierende straal en positie. Denk dat het er ongeveer hetzelfde uitziet als bij de spherical gen, maar het leuke van blobs is dat ze elkaar aantrekken en het geheel er dus wat "smoother" uitziet. Weet niet of het werkt, was zo maar een ideetje.

[.oisyn]

Zoijar schreef op 09 January 2003 @ 15:26:
Na dat gezien te hebben van die spherical generator dacht ik er ineens aan om marching cubes te gebruiken. Ik weet niet of dit werkt, nooit geprobeerd eigenlijk maar het kan een idee zijn. Je maakt zeg maar steeds "blobs" met varierende straal en positie. Denk dat het er ongeveer hetzelfde uitziet als bij de spherical gen, maar het leuke van blobs is dat ze elkaar aantrekken en het geheel er dus wat "smoother" uitziet. Weet niet of het werkt, was zo maar een ideetje.

blobs worden ook vaak gebruikt om vloeistof te simuleren. Dus niet druppels, maar echt een oppervlak dat wordt gevormd door miljoenen kleine particles. Nadeel van een dergelijk algoritme is dat het behoorlijk veel tijd kost om uit te rekenen

Een voordeel hiervan is weer wat dat het er realistisch uitziet, en bovendien zijn er dingen als pilaren en natuurlijke bruggen mogelijk (je kunt eigenlijk 'sculpturen' in 3D)

[Verwijderd]

Thanks voor de hulp!

Ik werk momenteel volgens dit principe: er worden een aantal opgevulde cirkels getekend, die omgezet in 3d een soort halve bol vormen in het landschap. Ook zijn een soort van pyramides mogelijk (in de demo worden beide gebruikt). Daarna wordt het geheel een 100-tal keer geblurd en wordt er wat 'random' 'ruis' over geplaatst.
Maar de techniek om telkens de vierkant in kleinere delen te verdelen en dan deze met een algoritme dan een hoogte te geven lijkt me een goed idee. Oorspronkelijk was ik dat ook van plan, maar ik wist niet of het sneller zou zijn totdat ik zag dat m'n huidige algoritme redelijk traag werkt. Het algoritme zal gebruikt worden voor een 64kb demo, dus de laad-tijden doen er niet echt toe. Ik ga dus dit algoritme behouden voor een soort van golf-terrein-achtig landschap te maken en dat andere om een ander effect te verkrijgen.

Heel erg bedankt!

[Punksmurf]

DaCoTa schreef op 09 January 2003 @ 12:24:
Spherical Landscapes: Dit is een van de mooiste resultaten die ik ken voor landscape generation. Dit is volgens mij ook te vertalen naar een plat vlak, maar wat voor resultaat dat geeft, weet ik niet.

ik ben er zelf ook mee bezig en ik vond dit wel interesant dus ik heb snel een algortmetje gebouwd dat dit doet (maar wat al 10x sneller kan merkte ik toen hij eenmaal draaide :P:P maar t ging maar om proef ) en na 10 minuten en 10k iterations kreeg ik het volgende effect, het ziet er niet onaardig uit maar het moet nog wel wat geblurred worden want zo zitten er veel pieken in...




*die ruis in de achtergrond staat er alleen maar omdat ik ut leuk vond om dat zo te doen...t iz geen bug

edit:k heb er ook 1 texture overheen gekwakt dus dat geeft geen supereffect *working on it...*
terrain is opgebouwd uit 4000 triangles, das wat te weinig omdat het zoveel piekt dus vandaar dat het wat verder weg een stuk vlakker is... als je m ook draait of inzoomd komen er ineens allemaal pieken uit het water tevoorschijn

[ Voor 16% gewijzigd door Punksmurf op 09-01-2003 23:57 . Reden: update info ]

[DaCoTa]

Voor afwerking kun je kijken op de pagina die SWfreak aangaf: RobotFrog.

edit:
Ziet er al best goed uit, alleen een beetje lange runtime inderdaad

[ Voor 29% gewijzigd door DaCoTa op 10-01-2003 07:47 ]

[SWfreak]

Kewl plaatje Punksmurf.

offtopic:
Hoe krijg je dat water voor elkaar?

Kwam trouwens nog een artikeltje tegen op Gamasutra:
http://www.gamasutra.com/features/20000427/martin_01.htm
(vereist registratie)

[ Voor 48% gewijzigd door SWfreak op 10-01-2003 09:32 ]

[Punksmurf]

DaCoTa schreef op 10 January 2003 @ 07:46:
Voor afwerking kun je kijken op de pagina die SWfreak aangaf: RobotFrog.

edit:
Ziet er al best goed uit, alleen een beetje lange runtime inderdaad

is idd interessante url..niet voor afwerking maar het is een mooi terrain dat hij ermee maakt.
runtime is nu gehalveerd maar das me nog steeds te lang

SWfreak schreef op 10 januari 2003 @ 09:27:
Hoe krijg je dat water voor elkaar?

water is een platgeslagen kubus, texure geload met alpha blending, alpha voor die kubus is 0.7, shininess 0.5

code:

Global water_tex=LoadTexture("water.bmp",3 )
ScaleTexture water_tex,.2,.2
water=CreateCube()
ScaleEntity water,1000,0.01,1000
EntityTexture water,water_tex
PositionEntity water,0,20,0
EntityAlpha water,.7
EntityShininess water,.5

een mooie animatie van het water is vrij makkelijk door de uv van de texture elke loop te updaten (zodat de texture over die kubus scrollt en dus een stromend effect geeft) en de hoogte van het water met een sinusfunctie te bewegen. Je zou ook met die sinus functie de uv van de texture kunnen bepalen dan krijg je een beetje het idee dat het een soort aanspoelt, net als op t strand maar dan zonder golven
niet superrealistisch maar t ziet er best oké uit.

tnx voor de complimenten maar ik ben er zelf nog allerminst tevreden mee

offtopic:
ik gebruik btw geen c++ maar blitzbasic... et zou moeten compilen naar machinecode maar t is wel vrij traag toch. Gelukkig wordt er nog steeds aan de compiler gewerkt Gebruikt dx7 en is iig een stuk sneller dan darkbasic en de IDE werkt ook een stuk prettiger. En ik kan nix anders dan basic

[ Voor 4% gewijzigd door Punksmurf op 10-01-2003 10:19 . Reden: toegegeven dat ik nix beters dan basic kan :P ]

[Verwijderd]

Hello,

ik sta al een stuk verder dankzij jullie. momenteel gebruik ik mid point displacement.
je kan het hier irl testen: [voor nieuwe URL: zie startpost].

[ Voor 23% gewijzigd door Verwijderd op 10-01-2005 22:26 . Reden: Verwijzing nr startpost vr URL ]

[DaCoTa]

Ik loop al een tijdje met het idee om niet alleen de heightmap, maar daaran ook de invulling van een landschap automatisch te laten verlopen. Dus om versneld een volledige evolutie van een wereld uit te rekenen. Denk hierbij aan een initiele landscape generatie zoals de TS bedoeld. Daarna een geologische analyse en invulling voor verschillende soorten grond, eventueel gerelateerd aan de locatie en een gegenereerd globaal weersysteem (e.g. waar is er woestijn, waar is er eeuwige sneel/poolijs, wat zit waar in de grond). Vervolgens een economische analyse van de wereld, waar zouden het eerst settlements gebouwd worden, hoe lopen de verbindingslijnen tussen die settlements, hoe snel groeien die settlements, etc, etc. Dit kan een interessante manier zijn om bijvoorbeeld een groeiende wereld te maken voor - pas op, hypewoord - een MMORPG te hosten.

De ontwikkeling van zo'n systeem is waarschijnlijk even veeleisend als een handmatig ontworpen wereld, maar het is misschien met beperkte middelen best wel redelijk te maken. Iemand andere ideeen over zoiets?

[Verwijderd]

Je brengt me op ideeen!! M'n bedoeling is om een 64kb intromovie te maken met een morphend landschap. Die suggesties van jou zijn echt cewl om daarin te verwerken. bvb:

- de ondergrond veranderd naargelang de stijlheid van de grond (bvb los zand zakt af bij stijle wanden)
- landschappen laten veranderen door erosie : bergen die afzakken door regen omdat ze te stijl zijn.
- de meest interessante plaats zoeken om huizen te kunnen bouwen
- ....

Dit zijn berekeningen die je volgens mij snel kunnen worden gedaan met c++
De generatie van m'n landschap duurt trouwens slechts een fractie van een seconde.

[ Voor 11% gewijzigd door Verwijderd op 10-01-2003 14:15 ]

[DaCoTa]

Het grootste probleem bij zo'n generator is om een goede balans tussen alle opties te vinden. Het gevaar bij zo'n generator is feature creap: 'Oh gaaf, dit kan ik er ook nog wel even bijzetten' . Als je het ver doortrekt, kun je zelfs een volledige moderne wereld laten ontstaan, dus met huizen, dorpen, wegen, treinverbindingen, vliegvelden, sloppenwijken, villawijken, verkeersborden, stoplichten, autoverkeer, etc. etc. etc.

Als je de opbouw van zo'n wereld visueel kunt maken, dan heb je volgens mij al een behoorlijke 64K demo, iig iets wat - volgens mij - nog niet eerder getoond is.

[Verwijderd]

DaCoTa schreef op 10 January 2003 @ 15:44:
Het grootste probleem bij zo'n generator is om een goede balans tussen alle opties te vinden. Het gevaar bij zo'n generator is feature creap: 'Oh gaaf, dit kan ik er ook nog wel even bijzetten' . Als je het ver doortrekt, kun je zelfs een volledige moderne wereld laten ontstaan, dus met huizen, dorpen, wegen, treinverbindingen, vliegvelden, sloppenwijken, villawijken, verkeersborden, stoplichten, autoverkeer, etc. etc. etc.

Als je de opbouw van zo'n wereld visueel kunt maken, dan heb je volgens mij al een behoorlijke 64K demo, iig iets wat - volgens mij - nog niet eerder getoond is.

Thanks a lot! Das een héél goed id van je! Dát ga ik dan ook proberen doen! Het voordeel ervan is dat de huizen e.d. geen hoog detail hoeven te hebben, en dus makkelijk te tekenen zijn met slechts een handvol polygonen. Ook is het heel eenvoudig om hiervoor kleine wiskunde textures aan te maken, alhoewel ik denk dat dat niet nodig is. Je kan bvb de huizen een random kleur geven tussen 2 bepaalde waarden (tussen rood en bordeaux ofzo) en vanuit deze waarde dan de rest van de benodigde kleuren voor dat huis te verkrijgen.

M'n engine (versie 1) is momenteel volledig klaar:
- de midpoint displacement werkt goed en ik heb 2 variaties erop
- bug uit kleurovergangen gehaald
-> polygon detail dat 16x kleiner is geeft
geen zichtbare overgangslijnen op de polygonen
- sneller berekenen
- overtollige code eruitgehaald (alhoewel ik het nog verder ga optimaliseren)
- realtime landscape rendering (hij maakt elke x seconden een nieuwe aan)

[Janoz]

Verwijderd schreef op 10 januari 2003 @ 17:38:
- bug uit kleurovergangen gehaald
-> polygon detail dat 16x kleiner is geeft
geen zichtbare overgangslijnen op de polygonen

Euhm, bedoel je hiermee dat, waneer je grotere polygonen gebruikt de scheidings lijn tussen beide polygonen te zien is? Geef je de polygonen in het geheel een kleur of geef je de vertices kleuren?

Daarnaast kan het berekenen en gebruiken van de normalen ook het realisme enorm vergroten.

[Verwijderd]

Janoz schreef op 10 January 2003 @ 20:30:

[...]


Euhm, bedoel je hiermee dat, waneer je grotere polygonen gebruikt de scheidings lijn tussen beide polygonen te zien is? Geef je de polygonen in het geheel een kleur of geef je de vertices kleuren?

Daarnaast kan het berekenen en gebruiken van de normalen ook het realisme enorm vergroten.

Inderdaad, vroeger was de scheidingslijn zichtbaar omdat er een bug zat in m'n kleurberekening.
Hoe maak ik die normalen? En hoe implementeer ik dat?