   Rendering City Environments
  I''ve been thinking about writing a city renderer for a while now, here are a couple of ideas I''ve had in my head that I''d like to run by some people.  I want it to be relatively easy to edit and build cities, so right now I''m thinking about using premodeled buildings, objects and roads and just placing them on top of a height map.  This seems to make things nice for both editing and rendering. The thing is, the geometry could get repetitive (not that real cities don''t have a good amount of repitition), so maybe it''s a better idea to just load a polygon soup. This seems to make certain things more difficult though. I''m not sure about the rendering spatial structure.  Right now I''m thinking either an octree or a quadtree and storing objects or groups of objects (so I don''t end up with a lot of small batches) in it.  It may be a good idea to break the buildings into sections in this case because they''re pretty large and I would lose some of the benefits of the spatial structure.  For occlusion culling I want something that''s not too complex and not too much editing work.  Because buildings are for the most part large boxes I''m thinking I could use  geometric occlusion culling or anti-portals behind the walls and be done with it.  It may be a better idea to portalize the city blocks, which would probably be done by selecting portals and sectors (groups of buildings\streets) manually. The issue with portalization is I would like to support rooftop\aerial viewpoints also, and I''m thinking I''d lose some of the advantages of portals at this perspective.   Interiors would be done with portals, maybe as separate levels (i.e., you "teleport" inside of buildings at the door like in GTA or Morrowind) or maybe with some contribution culling. LOD would be nice when buildings are far away.  Right now I think chunking multiple buildings together with lower polygon counts and packed textures would work well.  I''d only have a few (2-4) levels of LOD, really I think it''d only be useful when you have very far viewing distances and are looking at large buildings.Any comments or suggestions are greatly appreciated. I expect the size of the "city" to be smaller than GTA but much higher detail (500+ polygon buildings), with 100 or so buildings in the level.  
  I think your best bet is to create a design document which lays out exactly the features you want to support, and also outlines the limitations to the engine that you are willing to impose to make this thing a reality. Since you are still in the design phase this will help you to actually make this thing a reality. Then when programming you can account for all features at the beginning so no surprises later on, and STICK to the design as far as limitations go or the thing will never get done.You said you would use portalized city blocks, however you want to support aerial views so out goes that idea. Well... WHY do you want to support aerial views??? because it would be nice?? Why not USE your portal idea and simply place a limitation on your engine that the camera must be near ground level? This will make your job a lot easier, and every team that has ever made an engine has done this as well. There is no perfect one-size-fits-all engine out there because to actually produce something there will have to be limitations on what it can do.If you don''t choose to go with the portals, I suggest an octtree since it fits a city layout nicely. ;quote:Original post by y2kiah   I think your best bet is to create a design document which lays out exactly the features you want to support, and also outlines the limitations to the engine that you are willing to impose to make this thing a reality. Since you are still in the design phase this will help you to actually make this thing a reality. Then when programming you can account for all features at the beginning so no surprises later on, and STICK to the design as far as limitations go or the thing will never get done.I plan to do this eventually. Right now I'm just throwing out some ideas for feasibility testing.  quote:You said you would use portalized city blocks, however you want to support aerial views so out goes that idea. Well... WHY do you want to support aerial views??? because it would be nice?? Why not USE your portal idea and simply place a limitation on your engine that the camera must be near ground level? This will make your job a lot easier, and every team that has ever made an engine has done this as well. There is no perfect one-size-fits-all engine out there because to actually produce something there will have to be limitations on what it can do. For the type of game I plan to do this, some rooftop views would be necessary, and I may have characters that can fly.  This of something in between the outdoor levels of the Spiderman games and GTA3. This current idea is still pretty limited because it doesn't handle interiors very well. It's very far from a general purpose engine.Another thing I'm not sure of at this point is lighting.  Maybe simple vertex lighting will be good enough, but I doubt it.  Using lightmaps, spherical harmonics, or any other technique that requires unique per vertex data would get ride of the advantages of instanced objects.  Right now I'm thinking about using diffuse and environment cube maps for lighting, maybe along with shadow maps.  I'm thinking there would be a lot of quality issues with shadows maps though, maybe perspective shadowmaps would be a good idea, I'm not sure how well they work.    [edited by - impossible on July 30, 2003 5:27:11 PM];  Not many responses, eh?  Lucky there is a thread on gdalgorithms that just started yesterday that addresses a lot of my questions.  Apparently GTA3 doesn''t have any occlusion culling at all and is instead heavily dependent on LOD.  Every building has a high-poly version and a low poly version that fits under the high-poly version and they use alpha to blend smoothly between the two LODs.  They also have a very rough version of the whole island to render large buildings that are very far away, to give the illusion of extremely far draw distances. Maybe doing something like this, along with some simple geometric occlusion culling for larger buildings will work well. Understandably they recommend optimizing for the worst case and my worse case (rooftop\aerial views) doesn''t benefit from portalization and gets minimum benefit from occlusion culling. ;  yeah I think that if you want aerial views frustum culling (with an oct-tree) will be neccesary and give good results of course. It''s really too bad because an aerial view essentially means you are no longer in the "city environment" so you lose out on all of the advantages to being in one. Those being HUGE potential for extremely efficient occlusion culling, portals, etc. ;  I have been thinking a lot about all the questions. A good city engine should have a very far zmax and a dense geometry. - frustrum culling : Definitely a quadtree, or even a simple grid. Why use big nodes and a tree if the density is homogenous. Octree is wasting CPU and memory. Box/frustrum costs the same as Sphere frustrum (6 dots max). I already gave the trick several times here. Use local octrees only if you want to enter into the buildings. But probably it''d be better to use portals or BSPs inside.- backface culling : try to find good algos to backface cull groups. Intuitively one would certainly separate the 5 visible sides of a building.Efficiency : *2 roughly - occlusion culling : seriously I think it would be possible to use a full geometric scheme for cities. If you use separate occluders, (that''s what you call antiportal I suppose) occlusion culling perfs will surely be very variable which makes it nearly irrelevant as it''s the lowest FPS in the scene that counts not the max. Find a virtual BSP of your city or a Voronoi like graph. The goal is only to have a quick and reliable front to back order from any viewpoint. Have simplified occluding geometries for the buildings and the biggest elements : example boxes. This must be conservative, the occluder must be inside the geometry. Then make a kind of vectorial renderer that will be able to merge countours. Test occludees bboxes first. Project their countour and test if it''s fully hidden by the vectorial map.Note that the same idea could be terribly simplified. When you''re close to the ground, that''s where you have the max geometry. Aerial views dont cost much coz of LOD. But here you have a crazy advantage. Use a simple maze occlusion culling à la Doom. It would be long to explain in details here. But basically this reduces the problem to merging 1 dimension segments. Nothing can beat this occlusion algo. You''ll be able to cull most of the far buidlings, the cars, the inhabitants very accurately and ultimately fast.Efficiency: *2 or much more- lod, popup artifacts : I suppose you could use morphing between lods to avoid popup. Simply project (following normals?) the hi LOD verts on the lo LOD surface. Then linear interpolate the vertices of your hi LOD. At the right distance I suppose it would not be noticeable. Else classic CLOD technics may be too noticeable for such geometries as buildings. But why not with the same morphing technique.Efficiency  : enormous for the same scene.- Lighting : mix techniques. All depends on a mesh detail/source distance ratio. Separate what''s static and dynamic. Accumulate per vertex when the meshes are far from the source. Use light maps for far and less detailed buildings because you wont have enough vertices and this will look ugly and buggy. You could also compute static shadows on light maps. Or even pre-intersect the geometry with shadow volumes. Dynamic light maps ? Software ? Else maybe bump mapping for what''s near to the viewer and to the lights.. Create a priority sublist of lights per mesh. You can optimize it with a quad tree.With LOD you could afford unique textures with static lightmaps * textures * bump all blended, so you''ll reduce the texture channels required. This works like this with my infinite terrain engine. If you are able to use space/time continuity and smooth dynamic texture production this works. This won''t require too much memory or CPU/GPU, because memory should be of the same order than the screen size. And the texture update rate is roughly the number of new pixels you see between two frames.If you can do it all you''ll be able to render incredibly huge cities at an amazing FPS. If you wish I''d like to collaborate on such a specialized renderer. There is so much to do on this thema, so much to test. ;  Great reply... Charles B, eh? Charles Bloom?  If so your stuff has always impressed me a lot.  Either way thanks for the comments.  quote:Original post by Charles B  I have been thinking a lot about all the questions. A good city engine should have a very far zmax and a dense geometry. - frustrum culling : Definitely a quadtree, or even a simple grid. Why use big nodes and a tree if the density is homogenous. Octree is wasting CPU and memory. Box/frustrum costs the same as Sphere frustrum (6 dots max). I already gave the trick several times here. Use local octrees only if you want to enter into the buildings. But probably it''d be better to use portals or BSPs inside.Sounds good.  It seems like I could get some benefit from culling close buildings vertically, but this could probably be done per building, maybe with some kind of "floor BSP" that hierarchically splits the buidling vertically.  This would only have to be done for a few very close objects as most buildings would be entirely in view. quote:- occlusion culling : seriously I think it would be possible to use a full geometric scheme for cities. If you use separate occluders, (that''s what you call antiportal I suppose) occlusion culling perfs will surely be very variable which makes it nearly irrelevant as it''s the lowest FPS in the scene that counts not the max. Find a virtual BSP of your city or a Voronoi like graph. The goal is only to have a quick and reliable front to back order from any viewpoint. What do you mean by virual BSP exactly?  Like an axis aligned BSP that stores a building\object per leaf for sorting purposes?  Couldn''t I use the already existing spatial structure (quad\octree) to do this?quote:Have simplified occluding geometries for the buildings and the biggest elements : example boxes. This must be conservative, the occluder must be inside the geometry. Then make a kind of vectorial renderer that will be able to merge countours. Test occludees bboxes first. Project their countour and test if it''s fully hidden by the vectorial map.To me it almost seems like occluder fusion isn''t even necessary for a renderer like this.  The most common occlusion case should one big building right in front of the viewport.  This alone would cull a lot of geometry and the entire test could be geometric. The contour merging seems like a good idea though, although I''m not exactly sure how to do that, heh.quote:Note that the same idea could be terribly simplified. When you''re close to the ground, that''s where you have the max geometry. Aerial views dont cost much coz of LOD. But here you have a crazy advantage. Use a simple maze occlusion culling à la Doom. It would be long to explain in details here. But basically this reduces the problem to merging 1 dimension segments. Nothing can beat this occlusion algo. You''ll be able to cull most of the far buidlings, the cars, the inhabitants very accurately and ultimately fast.I definitely need to look into this.  Would it put any kind of weird constraints on the type of geometry I can have, or make tools and\or city editing more difficult?quote:- lod, popup artifacts : I suppose you could use morphing between lods to avoid popup. Simply project (following normals?) the hi LOD verts on the lo LOD surface. Then linear interpolate the vertices of your hi LOD. At the right distance I suppose it would not be noticeable. Else classic CLOD technics may be too noticeable for such geometries as buildings. But why not with the same morphing technique.I kind of like the GTA method, alpha blending between the low and high poly versions. It''s a little cheesy but it seems more hardware friendly than morphing, although it seems like your morphing idea would work in a vertex shader.  One of the other problems with lighting is in a major city day light and night light are completely different.  In the day time you basically have only one light source, and you get a lot of reflections on windows and stuff. I''m thinking a simple environment map with clouds would work for daylight reflections, although technically neighboring buildings get reflected also it''s not really worth generating all those cubemaps.  I''d like to do some kind of area lighting\GI approximation during the day because sunlight isn''t very contrasting.  It could be something as simple as interpolating between two light colors (ground color and sky color) instead of just a dot product. Shadows are also important during the day.Night light on the other hand is very different.  There are hundreds of lights everywhere, shadows aren''t as important, and there is of course no more skylight (well very little.)  Lightmaps could work well in this situation and I may even be able to reuse them for similar building types.  I could also do something like image space glow or just using coronas.  ;  No I am not Charles Bloom. I think he's not french quote:only have to be done for a few very close objects as most buildings would be entirely in view. Think about it : overdraw rate. It's usually close to one in aerial views. With LOD it should not be a big problem. Just use the roofs as occluders maybe.quote:What do you mean by virtual BSP exactly?Well in fact BSP is not the most appropriate because of the intersections issue. In the general case what you need is simply a way to cut your scene into convex cells, these may be simple squares. Thus it would look more like a Voronoi diagram. All you need is a linear algo to z-sort. You may find more simple ways depending on the city topology. If it's like new York, this partition would be based on boxes probably.quote:To me it almost seems like occluder fusion isn't even necessary for a renderer like this.  The most common occlusion case should one big building right in front of the viewport.Well I think the case where you follow a straight boulevard with rows of buildings is quite common. You wont be able to cull the parallel boulevards with separate occluders. But a whole row of buildings will act like a wall. In this case there may be a factor 2 at least between the two occlusion techniques.---- --(*)--  ---  --(*)--    -----    -------  -------> Eye-----    ----   ------  ------  --(*)--  -----  --(*)--(*) all these facades won't be culled without occluder merging.   quote:The contour merging seems like a good idea though, although I'm not exactly sure how to do that, heh.There are some solidly proven algos that do this. They are based on a tree. I have been thinking how it could be speeded up with different structures. Not simple I admit. Still I am certain it could work with simple ocluders. quote:I definitely need to look into this.  Would it put any kind of weird constraints on the type of geometry I can have, or make tools and\or city editing more difficult?You'll have to project the walls cut under a certain height (say 10 meters) and find the inner countour on the ground. This can be automatic. Start with cubes instead of general cylinders maybe, that will be easier to code. This will give you cylinders that will fit inside your buildings. It will be ez to project them on a xperp or yperp screen which in fact will be only a line since your occludees and occluders are just cylinders.You occludees or merged occludees will simply be like that :struct SEGMENT { float xmin, xmax, minProjectedHeight; SEG *pPrev, pNext; };  10 meters of walls near may hide 200 meters buildings far. You could also split high buildings so that you can cull the lower part and just draw the higher part. This will give you a quick merging of occluders and a very quick occludee rejection. BTW think that you'll need that : occludees (cylinders) > shape > occluders. Take my example with facades. This will work very well in a NY style city."Shadows are also important during the day"Yep I think pre intersecting the mesh could be interesting for buildings. Most of em would simply be split in two parts considering sunlight shadows. I don't think it would add many triangles. Then vertex lighting will be enough. For far buildings (basically boxes with two textures : walls + roof ) small lightmaps would be more approriate because. I think it could be possible to have realistic environment maps computed on the fly when the eye is in a given cone for each near window. But that would be overkill certainly. Else coronas may be nuff. A semi specular trick can be easilly computed."Night light ... shadows aren't as important ... I could also do something like image space glow or just using coronas."Right. Use modern TnL capacities near. Glows and coronas for small lights or distant buildings maybe. Occlusion culling and backface culling will help speed up lighting too. Nonetheless if you already have shadows solved for day light this would be ez to precompute static shadows for night time. Remember most of nite lights are static by position at least. So the shadow volume is also static. Only the intensity and cone frustum axis of the light usually changes. For moving light sources, cars, usually it only lights the road nearby with some kind of ellipses. So environment mapping may be nuff. [edited by - Charles B on August 2, 2003 5:45:17 AM] [edited by - Charles B on August 2, 2003 5:58:29 AM];  I stumbled across an interesting SIGGRAPH paper a while back on creating procedural cities. Obviously this mostly deals with generating/modelling cities rather than rendering them, but you might find it interesting depending on what exactly you're aiming to do. Here's the link.   [edited by - NeverSayDie on August 2, 2003 11:12:11 AM]