   Writing engine for large environments
  I''m writing a project for school that renders large environments with acceptable frame-rates.  The requirements are pretty vague, so I have pretty much free reign to do it the way that I want.  After some research (I still have more to do).  I decided to go with the following...-Large outdoor environment; Gothic 1/2, Battlefield 1942 as inspiration.-Octrees-Hierchical View Frustrum Culling using Bounding Volumes (using the Octrees data structure)-Detail Culling for some objects while in motion-Distance-based LOD with furthest object being a Billboard imposter.-Bump-mapping on impostersOK, here''s my deal.  I have until mid-May to design and code this so I want some input to ensure that I''m not making any obvious bad decisions from the get-go.  I work about 50-60 hours a week, so I''ll be coding this mostly during late-nights and weekends.  Right now all I have is a engine that does 3d-viewing with mouse and keyboard and is time-based (hey the semester just began).  My experience is some openGL, but never any real engine technology stuff.My questions:1) Does what I''ve mentioned below sound good?  All the topics listed above are new to me, so I will have to learn them.  Am I biting off more than I can chew given the time constraints (3 months)?  I know this question is kind of subjective, but I''d like to hear people''s experiences.2) I didn''t list occlusion culling because I don''t think that I''ll have time for it.  But if I do end up having time for it, will it work within the given "design" listed above if I try to implement it as an afterthought... or will NOT having occlusion culling make my framerate unacceptable for something like a scene in Gothic?3) Terrain - I haven''t researched terrain yet, but I may have to implement it to get the scene the way I want.  Any terrain suggestions, or am I biting off more than I can chew?Note, I will not be implementing any collision detection, except for maybe some trivial hack to keep the viewer in a certain area.  Collision detection isn''t a requirement right now.  Also, this doesn''t have to be beautiful (although I would like it to be kinda cool-looking), but the technology has to work.Thanks in advance,-Wil 
  I can''t really say if you''ve bit off more then you can chew. Depends on your learning speed. But I will say when doing your terrain portion of the engine skip the LOD code. Go straight for HSR (quad tree is simple to implement but I think you want to go oct tree?) in the beginning. Then implement LOD if you have time later, I had a project with terrain under the same time constraints and I ended up wasting too much time on the terrain details when I could''ve been coding other portions of the engine.~Wave ;quote:Original post by DeepCover  -Large outdoor environment; Gothic 1/2, Battlefield 1942 as inspiration.-Octrees-Hierchical View Frustrum Culling using Bounding Volumes (using the Octrees data structure)-Detail Culling for some objects while in motion-Distance-based LOD with furthest object being a Billboard imposter.-Bump-mapping on impostersi had to do something similiar and the first advice: small steps. planning is good, but spending weeks with designing and being halfway implementing it to stumble across problems you didnt expect can be a nasty surpriseyou might reconsider octrees for terrain, because its basically still flat (except you dont use heightmaps and have something special in mind). unless you have extreme air traffic octrees might not be worth it.culling is good and with a few thousand or more patches/tests a tree will start to make up for its overhead (up to 4000 the tree was slower, due to the frustum test taking more time to seperate completely included from partially included).reducing details for moving objects sound ok, but.. you should be able to handle them if they dont move, so this shouldnt be a critical feature maybe added later on.quote:My experience is some openGL, but never any real engine technology stuff.then start asking others that might use your part of the engine what interfaces they need (from obvious stuff like getting height and normal at a certain point to some you might not even think that anyone needs it).quote:My questions:1) Does what I''ve mentioned below sound good?  All the topics listed above are new to me, so I will have to learn them.  Am I biting off more than I can chew given the time constraints (3 months)?  I know this question is kind of subjective, but I''d like to hear people''s experiences.that depends. getting for example simple geo mipmapping working is doable, finding a decent lod scheme to optimize the ratio polygons/popping can be a pain and you should think about how youre going to load new areas. are you using single heightmaps with hard transitions (walls with gates, caves, water or high mountains as border etc.) or if you want to load new heightmaps while you go (so you''d need anything between 4 or more parts of the terrain around the players position). one thing to keep in mind: just the vertex buffer for a 2048 heightmap will eat up 50mb, so it should be obvious that you cant keep a huge world completely in memory and might need to load new data FAST.quote:2) I didn''t list occlusion culling because I don''t think that I''ll have time for it.  But if I do end up having time for it, will it work within the given "design" listed above if I try to implement it as an afterthought... or will NOT having occlusion culling make my framerate unacceptable for something like a scene in Gothic?dont. if you dont plan real mountain ranges you might end up wasting more time for occlusion culling than not rendering a few hundred triangles might be worth. im using a pretty sick way with occlusion rectangles and tracing a patch to every patch that doesnt fail frustum culling. on machines with slow cards it will make a big difference, on fast cards its slower than not doing it. if you really find you need it, store additional data for your segments (for example the horizon height for a dozen angles etc.) or see if just sorting front to back will help (with all the hype about hyper-z and whatnot one would hope so).quote:3) Terrain - I haven''t researched terrain yet, but I may have to implement it to get the scene the way I want.  Any terrain suggestions, or am I biting off more than I can chew?all i said is about terrain. one important point: dont start pushing the envelope in high geometry details and creative texture blending. i have a 1500x1500 area with one unit representing one meter, 4 detail textures + base texture per tile and per pixel lighting. guess what, compared to far cry its looking empty, ugly and small and they just use a simple 1024 heightmap. vegetation will add much more than highly detailed geometry or blending a dozen textures for the ground.quote:Note, I will not be implementing any collision detection, except for maybe some trivial hack to keep the viewer in a certain area.  Collision detection isn''t a requirement right now.  Also, this doesn''t have to be beautiful (although I would like it to be kinda cool-looking), but the technology has to work.i dont know if the time is enough for that, but start small. take a simple 256 heightmap (you can render it brute force for a start), divide it up (just a grid or a tree, depending on your preference and plans), add culling (but keep it flexible so you wont have to rewrite everything once you want bigger maps.. its temping to just hardcode patch sizes of 16 and use 256 all over the place "for now" and hating yourself for it a week later).add vegetation and a skyboy/sphere/dome/whatever, ask yourself "do i want a moving sun", because NOT doing that will make it a lot easier. vertex lighting sucks and its even worse with lod, because it will make popping even more obvious. a static scene could use a base texture including lighting and self shadowing. a dynamic scene either needs to update this texture a lot, use multiple textures or even do real lighting/shadowing. while per pixel lighting isnt that much of a performance killer it will require a normal map. shadows will still be a problem and i guess updating a shadow texture over a bunch of frames might work well (if your sun isnt moving too fast, else the changes might be too obvious and you might need to blend between old and new, using yet another texture unit).what im trying to say: start it small and add new stuff later on (always keeping a copy of the last working version). if you dont know how long you will take that way you will always have something that at least works, which is better than saying "oh, ehm.. well.. im still.. eh.. maybe it will be usable in about half a year". others might rely on it and having a small and basic and ugly environment is better than not being able to continue because an important module just isnt working.that also means: keep your interfaces (dont do that crap like ms does with directx all the time and change half of the function prototypes once a week). others should be able to just plug in your new version without changing anything (or not too much at least). default parameters can be handy for added functionality.example: you just added a skybox and for whatever reason it should be loaded along with the heightmap.old: int LoadMap(char* heightmap)new: int LoadMap(char* heightmap, char* skybox)so now everyone using your terrain would have to change every call to loadmap. if you doint LoadMap(char* heightmap, char* skybox="defaulbox.box")they dont need any changes in their code unless they want to use the new skybox with someone else but the default.sorry, if this is all obvious to you already ,-) ;  I would say you may have quite a load conceptually, but if you''re just looking for flat out implimentation, and not really caring about understanding, then you can get most of that up and running within a weekend.Gametutorials.com has terrain loading, along with octree/quadtree generation, and frustum culling. That''s half your project right there.Any LOD system requires that the calculations be the base of your geometry. IE for GeoMipMaps or CLOD you need to distinguish how a given patch should interact with other patches. I think if you''re just starting out with this process, skip the LOD system for now, it''s somewhat metaphysical. (?)If you''re just doing a terrain engine, there''s not much else you need to do on the side of polygon pushing. Unless you''re really worried about occlusion culling, stay away from it. I took about 4 months of intensive research to finish my honors paper on the topic, and IMHO it''s the most complex set of visibility determination in it''s realm. (BSP/PVS are in another realm)hope that helps~Main ==Colt "MainRoach" McAnlisProgrammerwww.badheat.com/sinewave ;  Thank you very much for the replies.  I read them through a few times.  Thanks Trienco for the lengthy reply, it was full of valuable info.  It''s sounding to me that Occlusion Culling is a project all on its own and what I need to be doing now is getting my terrain rendered first asap.  Then add more stuff little by little.I''ll be studying/implementing terrain rendering hardcore this week and will try to have something by the end of next week that I can build off of. One question, Trienco.  You seemed to not care for octrees that much.  What would you suggest instead?  I downloaded your terrain demo off of your homepage and I thought it was great.  Was the collision detection of the ground hard to do?duhroach, I''ll check out those octree tutorials for learning purposes.  Thanks for the info.  LOD isn''t an option for me, it''s a requirement.  So I have to implement some kind of LOD technology - whether it be on objects in the scene or the terrain itself.Thanks again for the responses.  Any other advise would be greatly appreciated.-Wil ;  I''ve been doing alot of work with terrain recently, so I thought I''d add my thoughts:Quadtrees are generally better than octrees for terrain, since terrain is usually created as a height map.  Because there''s no overlap, there''s no need to do visibility testing on the terrain in 3 dimensions.  Plus, there are a ton of LOD algorithms that use quadtrees.  I''d suggest googling for Chunked LOD, as it''s one of the most GPU-friendly algorithms I''ve seen.  You may also just look into Geo-mipmapping, which is not quite as good as chunked LOD but it may end up being easier in implementation.  They''re pretty close though, so if you think you can swing it I highly recommend doing Chunked LOD.  Also, Chunked LOD is better for out-of-core paging, so if you have a large, large data set, you can load in the low level(s) of detail for the terrain that''s distant, and only bother to load the higher levels from disk when you start to need them.As a sort of case-study for you, what I did when writing my terrain was get the display of ONE patch of terrain running first.  Then I did the calculations for each level of detail (I ended up using Bintrees like ROAM does to generate the levels of detail, though you could also use something like progressive meshing or even just removing every other row/column of points), and added keyboard commands to switch between them in my engine (so I could make sure they looked correct).  Then I whipped in the actual LOD selection.  After that, the blending between detail levels.  Finally, I handled the lighting/texturing (though that should have been an earlier step...it was a pain to add after-the-fact).As far as the other portions of your question:Frustum culling is very important, and relatively quick to do with the quadtree.  Any time a quadtree box is not inside the frustum, none of the nodes inside of it need to be checked.I agree that occlusion mapping is a royal pain in the butt.  I''d do something more like using a PVS (Precalculated Visible Set, if I remember correctly), which states what terrain nodes/leaves are potentially visible from a given point on the terrain.  This is more useful if the player is stuck to the ground.Basic visibility would then be something like:QuadtreeNode::Render()  If (Is In Frustum)    If(Is Visible According To PVS) If (Is Leaf Node)   This.Mesh.Render()  // This passed visibility tests - render it Else   For Each Child Node // At most 4 - it''s a quadtree!Child.Render()   End For End If    End If  End IfEnd Function  One last thing: Don''t underestimate the effects of aerial perspective.  This is the effect where objects get more blueish as they get farther away, due to the light-scattering properties of air.  There are a bunch of good resources on this, though they''re a bit tricky to understand and implement.  All I do is have a nice skybox that contains just the sky color, then fade it in (exponentially) as the distance increases.  Much like a basic distance fog, though I use the effect much less (it''s not one of those stop-your-view-four-feet-in-front-of-your-face fogs) than normal.  But it''s amazing how much better and more natural a landscape looks using the light scattering than it did without.  I''d highly suggest looking at the ATI light scattering papers, and trying to rig something up that way.  There''s alot of "playing with numbers" to get it to look right, though, as the values are not entirely well-documented (or even documented at all).Here are a few pics of what I mean by aerial perspective under various conditions (pic 1 is a normal low-haze day, pic 2 is during a sunset, and pic 3 is in heavy fog).  Ignore the ugly ground texture, these pics don''t have the final texturing method that I''ve ended up using.Sky Picture 1 - Sky Picture 2 - Sky Picture 3Hope this helps! ;quote:Original post by DeepCover  I wold like to add some thoughts to those written above:1. Definitely go for geomipmapping and combine it with per-vertex geomorphing, using vertex shaders. That will remove popping, and will solve 98% of the cracks between patches (just geomorph to a bit higher vertex in the nearer patch).2. Use 2.5 quadtrees, with AABB in each node. That way you can include static objects inside the quadtree, precompile AABB for each patch + its static objects. That way AABB-s of neighbour nodes may overlap, but since parent node will enslose them all it will be just the same hierarchical frustum culling.3. Try to texture with terrain types. Each terrain type is one or more very detailed textures. Do texture splatting in the near patches, and far ones texture with single texture (we talk about diffuse texture only) made by burning texture splats offline and create one large texture for the whole terrain. For low-end cards just use that texture + detail one.4. If you want HSR, you can try something like that. All patches are treated as potential occluders, and are traversed by quadtree front to back. For each patch, we compute four occluders for its AABB - they are this AABB sides, with height - the minimal height of the terrain in that side of AABB. When traversing, get the bounding rect of each AABB, and test it with the current occluders and if it passed the test, add the four occluders to the buffer and continue. The buffer may be done like in the ''Driving through urban scenery'' (did I cited it correctly) paper - it divides screenspace into rectangles with depth each of them. First it divides the X-axis, then it cuts each vertical column into pieces, thus producing rectangles.Of course you may use only nearest occluders or those with relatively big screen projection, and limit this system by time used each frame - if time used is more that X ms, just draw all subsequent patches without HSR test.5. Impostors. Consider using sprites instead - just render each model from 8 directions into texture and use that like billboard for distant objects. Use normal map to light it correctly, by rendering the model 8 times, but not its texture, but surface normals into normal map. Its rather tricky for leaves...Group nearby impostors into larger buffers (like particles), fade them by distance and replace them by the original mesh, when they''re close enough. Since there are lots of them in single buffer, removing single one from the buffer is better done in the VS itself - if vertices are close enough, just collapse them into (0,0,0), else just expand them into billboard. ;  of course there''s always this: Focus on terrain Programming ~Main   ==Colt "MainRoach" McAnlisProgrammerwww.badheat.com/sinewave ;  I''m working on a non-heightmapped LOD engine... the test level is a city. The way I''ve done it is the level specifies each detail level exactly, instead of the engine generating them. This allows for optimal framerates and is good for structures. The disadvantage is you''d either have to specify the geometry in text or create a world editor -- there''s no good way to use existing level/model formats.   ~CGameProgrammer( ); -- Post screenshots of your projects. 100+ posts already in the archives. ;quote:Original post by CGameProgrammer  The way I''ve done it is the level specifies each detail level exactly, instead of the engine generating them. This allows for optimal framerates and is good for structures.And how do you switch LODs? Directly, or by geomorphing? 