I have been toying with the idea of writing a real-time 3D terrain engine for a while now, but have so far resisted the temptation to throw myself into thousands of lines of code in favour of thorough research, analysis, and design. I know, I know, boring eh, but I have learnt my lessons over the past and I'm pretty sure that, for a project of this scope, I am doing the right thing.
I thought I'd kick off a discussion here in the hope of getting advice and gaining knowledge, etc. You all seem like knowledgeable, talented people, so I think I'm in the right place.
Before I start rambling about my own ideas, here's a link to an upcoming game made by a Swedish game studio, Avalanche, called http://www.justcausegame.com. It looks pretty sweet. My ultimate aim would be an engine of comparable quality. I have a video of this game, but for some reason, it isn't on that website; but one does exist!
Now then, I have played a little with heightmaps, and my basic idea was to write a program to generate heightmaps and edit them. Then optimise to reduce the number of polygons. Create some sort of an editor to allow decent texturing and basic editing of the map. Now then, to create a truly huge terrain (such as in in the forthcoming S.T.A.L.K.E.R. or, to an even greater extent, Just Cause), you will surely require some sort of caching system and God knows what else - it is currently beyond me).
I'll quit rambling now. Looking forward to hearing your thoughts
The problem with outdoor terrain is that your line of sight is so much further and, generally, nothing much obscures the view,
Unlike indoor settings, where walls and doors and ceilings obscure the line of sight and therefore present loads of opportunities for optimising that polygon count down and implement some neat caching techniques.
I came up with a neat caching idea for an indoor setting (not outdoor but it might be in some way still useful, if modified a little), where the map is naturally divided into "rooms".
The engine would have a chunk of memory, which would be the "room cache". The current room - that the player's character starts in - would, of course, be loaded into the "room cache".
But then, in the map data, every "room" would contain a list of other rooms that it's connected with - its neighbours - and then the engine would load up all of those rooms into the "room cache" (background loading). These rooms would themselves also each have another list of other of more rooms and those would be prefetched into the cache too.
Note that though, generally, the rooms would be connected spatially - the rooms are physically next to each other - the definition is delibrately more generic that, say, if one room contains a "teleporter" that takes the player over to the other side of the map then it would be in the "neighbours" list and be prefetched into the "room cache" in the background, irrespective of its spatial positioning. Of course, for your average game, all neighbours would be the spatial neighbours but it's flexible to account for teleporters and other weird non-spatial relationships between "rooms" that a particular game might have.
A background thread fills up the "room cache" - prefetches room data - so that all the loading of the rooms doesn't actually get in the way of gameplay.
When the player moves from room to room, the "room cache" is appropriately updated to dump the "furthest from current room" (in terms of links, which may or may not be the furthest room spatially) to make room for the new rooms.
The theory being that all the possible "rooms" that the player might choose to go to from the current one are already prefetched into the "room cache". This creates a "buffer" that the engine is always one or two rooms ahead of the actual player's position. When they walk into a new room, it updates this by dumping the rooms from the cache which are now the most distant (in terms of room links) to make space for the new rooms.
Room prefetching / caching is done on a background thread. The neat thing to remember is that the player will take time to run across a room from one door to the next door. This - plus the fact that it's working a few rooms in advance of the current postion - should give plenty of time for the background loading that it should always be ready by the time the player reaches the room (one can be sneaky in the map design, anyway, and delibrately make a room really long when there's a lot of complexity in the room after it, so that the player has to run further, giving us more time to load the more complex rooms. This naturally suits a "room - corridor - room - corridor" architectural style perfectly).
This method would then allow a theoretically infinite number of rooms - as large a map as you like - and you can wander it freely without any "loading" messages and pauses required.
The other neat thing is that rooms can actually be more complex because only the current room and its immediate neighbours are in RAM at any one time. The "room cache" size can also be scaled nicely according to the user's RAM too (if they have lots of RAM then it can buffer well ahead and be scaled to load more rooms in one go less often because the "buffer" created by the room cache allows that but, at the same time, a more modest RAM size can still be used but it just runs the whole thing closer to the wire).
The map editor can precalculate which rooms connect to which other rooms automatically and just save it into some "room header" information that the room data has. Note that spatial neighbours might not necessarily be neighbours in terms of links - two rooms might be next to each other but there's no way to get from one to the other except by passing through other rooms first - and this method takes account of that and doesn't needlessly load the other room which the player can't get to yet (that's why I defined the way I did that it works logically, rather than spatially, to be slightly more efficient for things like that and also for "teleports" or "magic mirrors" or anything else where the player might suddenly be transported half-way across the map. The "neighbours" here are logical rather than spatial neighbours that this doesn't cause a hiccup in the way the algorithm works).
This could also be used for outdoor terrain too (the concept of a "room" does not need to be bounded by four walls and a ceiling but that's just what makes sense in an indoor setting. You could more generally think of "room" in this context as a division of the volume of space) but it would prove less optimal but that's because of the nature of outdoor terrain that you're line of sight is further (not many walls obscuring things, as a rule).
If you're thinking of indoor and outdoor settings simultaneously (e.g. you can drive around outside in the city, get out of the car and just walk up the stairs into the city hall with a single pause or "loading" message or delay), this algorithmic idea proves nice because it naturally wouldn't care about such things.
For the outdoor scene, the real problem is because the line of sight is typically gigantic (stand on the top of the mountain and you can see everything in all directions to the horizon, including - gulp - looking down over a cityscape that you're technically rendering the entire city!! Unoptimised polygon count? Gargantuanly silly!!), you need ways to keep it reasonable.
Conveniently, perspective is your friend. Things further away are smaller. Things really far away are so small on screen that they are just a few pixels in size. No point rendering a fully detailed model at that distance: you wouldn't be able to see it.
Which brings in the idea of "level of detail". The further an object is away from the player, the less detail they'll be able to see. Therefore, substitute less and less detailed models of the object, the further away they are.
Up close, the skyscraper has a lot of detail but when the player is on the mountain miles away looking at it, it's a single polygon for each side (and the texture on it is "faking" the detail. It's too far away for parallax to be visible on those details, so no-one's going to notice that you're rendering them flat).
To incorporate one idea with the other, each "room" and each object in each "room" has LOD applied to it. Spatially distant rooms can be loaded at a low level of detail. As they come closer, load in some more detail (and drop the detail on the rooms now disappearing out of sight).
If you could use scalable models then this could be rather neatly done. That is, a model at full detail has 5000 vertices and then, to drop the LOD, you're just dropping that count to 2500 and re-arranging the surfaces to make it look as acceptably like the 5000 vertex version as you can with 2500 vertexes. There's some examples of this kind of thing in the DirectX SDK examples, I recall, to do with "meshes" with a tiger model).
Then, for each object, stick the most important vertices first (for the lowest level of detail model first). Then follow with the next most important vertices and continue right up to the full detail model. Render the object with the appropriate amount of detail according to how far away it is.
Combining that idea with the "room cache" idea, it's even conceivable of loading just the low detail models when a room is distant. Then, if it comes closer, load in more detail. Until when the player is in that "room", it's a full detail model.
Might be a bit complicated to work that all out but the two ideas do neatly fit together - now that I think about it - and the LOD needed for outside terrain could actually be used to make the "room prefetching" idea more efficient to not even bother to load the full detail models until you actually get close enough to justify that.
LOD shouldn't make an ounce of difference to the earlier indoor setting (except it might even make the loading more efficient) and, therefore, we might just have a neat algorithmic idea which should suit indoor or outdoor just the same that we could be really cool and have the player wander around the city and then just walk straight into the buildings - indoors - without hesitation (and, nicely, by the "room cache" idea, the lobby of the building is prefetched and the immediate rooms around it when they're standing outside but not the entire building. "Rooms", by the way, which I should have mentioned already are logical divisions and have no fixed size or shape unless you really want them to).
Another thing with gigantic maps is simply the time issue. Drawing models to map an entire world? That's very time-consuming to say the least.
You know, you need to press a button in the map editor and it creates you a bunch of "random mountains" or "complex coastline". The natural terrain - mountains, coastlines, trees, shrubs, whatever - can be mostly knocked up by some "random fractal landscape generator" thing. Then, you know, manually flatten a section then put your city there.
But if you think along the lines of "descriptive terrain" then you can both simplify things and have reasonable storage. An uncompressed "heightmap" for an entire huge world? That's a big disk file you're going to have there. Pointlessly so, really, because a mountain, in simplistic rerms, is just a bunch of curves, a plain is mostly just flat, ditches are upside-down moutains (in "heightmap" terms) and so on.
Making it descriptive is more effort, I grant you, but it makes a lot of sense for a "big map" game that you work in "broad strokes". If for no other reason than saving time building this gigantic "world" model with its mountains and cities and what-not. It also would keep the storage sensible and might help out making some kind of "random terrain generator" easier to deal with.
The idea is to look at, say, a mountain as being defined by curves. Instead of storing individual points, store the general shape of that curve and you can derive the points from that shape. Comparable to storing a circle as a position and a radius then working out where all the pixels for the circle will be from that, instead of a bitmap of the circle.
From a distance, at least, a skyscraper is just a cube. And a cube is a regular shape. You really only need to specify width, breadth, height and the fact that it's a cube. From that, you can work out where the vertices should go.
It's a natural form of compression (so it'll keep the disk space down for storing this gigantic map) and it's working in "broad strokes" (so you can imagine that you create a cityscape by just plonking down a bunch of cubes in a regular grid and then randomly tugging them to different heights. Alacazam, the Manhattan skyline in half the time). You could also more easily code some kind of "some city generator" which creates you a city at the touch of a button, then just refine the model for the important buildings the player can actually walk inside or whatever).
Descriptive could even help with the LOD aspect. A skyscraper at the lowest detail level is just "elongated cube". As the player walks close, it's "elongated cube with little bit sticking out here and there". As the player walks right up to it, it's "elongated cube with loads more bits sticking out of it" to the maximum level. If you see what I mean there.
Of course, throwing all of these ideas together is not remotely "overnight work" but you say you want to work up to something like that "Just cause" and, for something like that, there is a lot of work involved.
That's, of course, why even the commercial companies with armies of programmers at their disposal still take the easier route of just buying an engine from John Carmack or whoever and don't make their own one from scratch.
If you were more concerned for making a game - especially if it's just you alone working on this - then I'd say don't bother and use someone else's engine. Building a good, flexible 3D engine from scratch is no simple task (especially if you want results similar to the commercial releases). It's not quite writing your own operating system, perhaps, but it's approaching that league.
But you seem to want to make the engine more than anything and, therefore, obviously "use someone else's engine" defeats the point of what you want to do here. As long as you realise what you're in for and that's what you want to do then good luck to you. But it is a lot of work that it would be remiss of me - on the unlikely off-chance you didn't already fully know this and thought it'd be "easy as pie" and you'd have it all done overnight - not to mention that at some point here.
"Words ought to be a little wild - for they are assaults of thought on the unthinking."
- John Maynard Keynes
If the world to be rendered is in fact an 2d-array containing heights, then the rendering can be done quite efficiently via standard heightmap rendering approaches, even if the world is really huge. But you'll always need some kind of LOD (as KlaxonCow underlined very rightly).
It gets a bit more difficult if you have real 3d-worlds, though...
I did some experimenting on rendering of really huge worlds, and I'm deeply convinced, that any rendering algorithm that starts from the objects in the world will not be feasible (for the reasons already given by KlaxonCow). You have to start from the viewpoint instead. Which means that you have to incorporate some kind of raytracing approach (even if you draw polygons the standard way in the end).
KlaxonCow's rooms idea shows the right direction, I think. Though you have to take it a little further: for it helps not very much if you simply uniformly divide the world model into same-sized rooms. All you can gain by that (in terms of speed and storage efficiency or whatever) is proportional to a constant factor, agreed? And that's not enough (I tell you).
So, why stop with one level of (let's call them) KlaxonCow Rooms (KCRs)?
Why not divide the world into some KCRs, and then go on and divide these KCRs even further? Rooms of rooms of rooms. And so on. If you want you can stop at some level you like.*
The result would be a hierarchie of KCRs (or volume elements). You can represent this hierarchie in an octree, for instance.
Then go and raytrace it.
DISCLAIMER: All ideas given in this post shall by no means insinuate that I ever managed it to write a huge-world renderer which ran in something like real-time and looked good. My last approach was a probabilistic hybrid octree raytracer with backprojection... uh, it looked shite.
Fascinating topic, though.
*well, or even never stop. Fractal worlds with infinite depths. The difference is 'only' that you work no longer on trees but on graphs, *shudder*
>take off sunglasses
Seamen and fishermen alike swear to have heard voices in the rising tide. Inhuman screams, some of them say.
Welcome, Jaguar, to this place of huge worlds and fluffy raytracers.
Enjoy your stay and have a sheep.
Just Cause looks real good. I think the important adjective for its graphics engine is hybrid. Heightmaps mixed with polygon objects and an efficient spatial representation scheme (plus water plus trees, bushes and grass and sky and whatnot). Would be interesting to look under the hood of that engine.
EDIT: Hm, the first question to ask would be: does Just Cause use a precalculated (huge) heightmap or does it do the (fractal) calculations on-the-fly and in realtime as part of the rendering process? The latter could be quite interesting, with integrated LOD and everything. Well, even if it does, it needs an efficient spatial scheme anyway for all the additional poly-objects, which lie on the warped but infact flat landscape.
>take off sunglasses
Seamen and fishermen alike swear to have heard voices in the rising tide. Inhuman screams, some of them say.
KlaxonCow & Dvorak: thankyou both for such detailed replies
Well, that's certainly given me some more to think about! I actually bought a book on this subject - "Real-time 3D terrain engines with C++ & DirectX", and it concentrates on heightmaps for terrain generation and doesn't cover fractal techniques or bezier surfaces (?). It does mention the ROAM technique for storing the data but in all honesty, a lot of it went straight over my head.
What about oct- or quad-tree based techniques? The aforementioned book uses a quad-tree approach. From what i can gather, an oct-tree is more suited to 3D, but because terrain is generally more 'across' than 'up and down' (forgive my crude wording!), the book said a quad-tree is ok. I was sceptical.
When I was at uni and asked one of my teachers about heightmaps, he pointed out that they create a lot of triangles and that large ones will almost certainly need triangle-reduction methods applied to them. Also they're not good at handling sudden, large changes in height.
I did think about doing a Bezier surface, or similar, as this was covered in one of our subjects, but it's not really as simple as a heightmap (certainly not get to started on - I am a bit of a noob after all!). However, I can see the attraction in terms of LoD - it is much more suited to that. Which, thinking about it, is probably crucial.
And fortunuately, I am rather passionate about fractals, so I will probably check out generating terrain with fractals on my own. I've had a look at a demo or two and was quite impressed. Perlin Noise is rather cool too, I saw a very sweet little cloud cover demo that used Perlin Noise 'on the fly' so to speak. Will try and find links.
Talking of which, I uploaded the Just Cause video to my website fo your enjoyment!
And the general idea of a system of caching the surrounding area relative to the player, and so on, seems to be unavoidable. The LoD algorithms will probably be tricky, I think. Especially to prevent any really noticeable popping (which is 'orrible!).
Hmm. Think I might have bitten off more than I can chew. Might have to stick with puzzles and nice, simple, 2D games But I would really love to write this engine, and I'm pretty confident that I am capable. Just need to get it all sorted in my head first and do some good design work, cos otherwise I just know I will end up re-writing code, which in this case would prob mean tens of thousands of lines. Can't think of a single program I've ever written where I didn't have to rewrite a lot of code that could probably have been prevented had I thought about it more
The other issue i can think of is creating middleware to edit the maps. And how to texture them convincingly, etc. Argh.
If I was wearing a hat, I'd take it off to those guys at Avalanche
Welcome, Jaguar, to this place of huge worlds and fluffy raytracers.
Enjoy your stay and have a sheep.
Just Cause looks real good. I think the important adjective for its graphics engine is hybrid. Heightmaps mixed with polygon objects and an efficient spatial representation scheme (plus water plus trees, bushes and grass and sky and whatnot). Would be interesting to look under the hood of that engine.
EDIT: Hm, the first question to ask would be: does Just Cause use a precalculated (huge) heightmap or does it do the (fractal) calculations on-the-fly and in realtime as part of the rendering process? The latter could be quite interesting, with integrated LOD and everything. Well, even if it does, it needs an efficient spatial scheme anyway for all the additional poly-objects, which lie on the warped but infact flat landscape.
Thanks Dvorak I'm liking it here already!
'hybrid' is probably the word, yes. Personally I reckon it is one huge heightmap, or at least, lots of smaller ones seamlessly interwoven (It is supposed to be about 1200 square miles of terrain). Some procedural kind of techniques are probably used as well though. I really don't know enough about the subject to speculate, but it is is obvious that it has excellent LoD techniques.
Definitely gonna have to upgrade my pooter to play it! It started to struggle a bit when F.E.A.R. came along!
The problem with large out door areas is not drawing the ground. The problem is putting things into the world to make it interesting. The first thing I would say is despite my own personal fascination with fractally generating topography - however the world is initially created you should load it into a modeller of some kind and edit it, to give the groundscape some gameplay features.
Secondly, think very hard about how you are going to fill the world with objects. Even if you dont use LOD on the ground you still wont actually use all that many polygons, the real problem is stuff you put to screen.
I have experimented with a number of different methods, the only one i've been fully satisfied with thus far because it gives both good object population density and allows objects to cast dynamic lighting and makes use of portalised collision, is to break the world up into regions and repeat objects within each region. My stack of object meshes becomes completely independant of the world data and often world objects have no idea which mesh they are using to draw, in a forest it doesnt matter what mesh in RAM is depicting which tree entity in the world, what matters is that trees being drawn and handled in your graphics pipeline are the ones that are visible to the player.
Last time I did a landscape I used simple fixed quadtrees which were pre-computed in a little tool I did and it all worked pretty well. Never bothered too much with LOD because I was assured that if you were reasonably sensible about the high-level culling then anyhting else would burn more power than it saved. not sure if it was definately true back then and not 100% if it applies right now - suspect its more likely to be though.
currently trying to tie together model rendering, landscape rendering, BSPs, etc. into a nice felixable scenegraph arrangement in some code I'm writing to give me a reasonable 3D engine.
I think creating a map editor will be one of the trickiest things because as Becky Rose points out, terrain is relatively easy to generate but actually populating that terrain with trees, bushes, scrub, grass, water, buildings, etc - that is a big task in itself.
Also, texturing the area. You could texture it according to height to give the tops of mountains snow caps etc, but that's not really the best way to do it. To get control you need a map editor.
I did do some weird terrorism game thing a while back with the landscape broken up into sectors generated from bezier patches, and it developed several different LOD models for each sector, so you could keep the poly count down the further away in the view from the camera.
Objects (whether static or moving objects) had meshes, but these were approximated by 'imposters' at a distance which are pre-rendered sprite billboards. All the objects in the game were procedurally developed, so not only did it make it easy on the artistic skills, but the computer could decide how complex a model would suit the graphics hardware without a lot of editing of data.
The collision mesh for the sectors was the same whether near or far for the player object, bullets and enemies, so even it something was firing rather far away, it would still interact with the landscape properly, even if a very cheap rendering method from the player perspective.
IIRC, I was trying to change this terrain system, so that it could be modified - if a player blew up a building, or constructed others, or remodeled the landscape by digging a strip mine, or demolishing skyscrapers, or making a huge bomb crater in the ground, then it would do all this on the fly when things weren't busy..but it proved much more difficult than I originally thought - in rebuilding the collision information in real-time based on a dynamic world..
"Observation is the path to understanding. Self-observation is the path to self-understanding."
At a sufficient distance, you don't even need to render polygons for objects. You can instead create billboards and render them as textures on a plane surface at an LOD threshold. Billboards don't need to be updated very often, and in the case of static environmental details, they can even be prerendered.
To create a map editing tool that can create terrain using heightmaps, fractals, or bezier patches/surfaces. It can then save the vertex/triangle data as a binary file for the engine to load.
Then gradually implement texturing techniques and the ability to load other objects into the binary file, such as trees and buildings.
Whilst at the same time updating the engine to support rendering each new feature/object.
Then it would be a question of implementing LoD algorithms into the engine and optimise for speed. Triangle reduction etc.
Any other ideas/advice? Greatly appreciate all your input so far