Guys,

i can't find any good information on what to use when it comes to render indoor areas only.




We all know BSP but do we use it those days ?


BSP ? Portals ? Octrees ? Quadtrees ? BVH?

What should i pick if i think of an engine rendering only indoor areas ?





There are of course tons about BSP (and that quake old school stuff around) - but i can't imagine that in this century..




I need to achieve a flexible solution so that people doing level editing just export the mesh from the 3DS MAX and...

and yeah, what is the tech i should use to render efficiently indoor levels?




Thanks for any input into this.

Really nobody ?

Is it that secret?

Well...

I've been recently working with high-performance BVHs in my scene management subsystem in my engine and actually it works a bit better than BSP (because it can dynamically handle fully dynamic environment). View frustum culling is at very low price (giving a bit of boost to performance), but Occlusion culling is not giving that much boost (depends on scene) - it's price is really a lot higher than frustum culling test.

As far as I can tell - try BVHs, you won't get as good results as with BSPs (in terms of speed), but you'll be able to handle scene fully dynamically (BVHs can be built/rebuilt in realtime quite quickly).

Portals are still used and BSPs are still used too.

all of those accelerator structures give similar results, from that point of view it doesn't really matter. the decision is usually done based on what 'extra' you want and how you will handle the limitations.

BSP just work for very low poly static scenes, in source, quake etc. engines it's used for the rough level brush, all detailed objects are sorted in as special cases. BSP are nowadays still good for collision detection, but I doubt anyone is still using them to compose a level mesh out of polys to render it, it's way faster to work in chunks of brushes. the draw back is the compile time of the BSP, which can take a while even nowadays, as every face adds to the complexity (if you want a high quality BSP), this makes the stuff not flexible, you also need some kind of editor that level designer can work with, as every BSP compiler has issues and humans need to work around them, just exporting a level after it's done from a modelling tool will result in a lot of broken BSPs. There are still some games who did it that way, e.g. MDK. I wrote like 2 or 3 BSP compiler in my life, it's a lot of fun from a programmer's point of view, but it's also a lot of debugging work that you could spend in another area.

BVH like AABBs are very flexible, creating a good one can still be a bit slow imagin a 10k object car in the center of a stadium composed of 100 objects, you would like to have that car as just one node in the tree of 101parts that compose the stadium. but it's very easy to get this working on a basic level and you'll have good results already. it also copes well with nowadays thinking to not touch every triangle, but compose even indoor scenes of parts (e.g. check out the repeating parts in dead space). you can still have some trouble to handle dynamic object, you either expand the AABBs where the dynamic objects are sorted in, which can result in a tree that becomes slower and slower (won't be dramatic tho), or you try to sort the dynamic objects into the tree, which can result in all dynamic objects being sorted at (near) the root level, e.g. players in a stadium.

Octree are probably the easiest to construct, as there is a simple rule of halving the space, independent of the objects, it's very fast, so most engines do that during runtime, the bad sides about them are, that you can end up with a lot of objects, that cross borders, will be sorted to some parent nodes, which can result in the root node having most objects, the tree can also become artificially deep at some areas, imaging a bird flying in a open world level spanning some km, the bird up in the sky might create a tree 20 level deep, most of them just linking to one valid child node until you reach the bird, and when it moves, you have to update that all.

you can use KD-trees, it's the simple form of BSPs, while it is not as fast as solid-bsp when it comes to ray-casts, it is still faster than all the other structs I mentioned (and nowadays the most common way to accelerate raytracers). it is quite easy to contruct them, the usage is nearly the same as with BSPs, although some people keep space extends to 'virtual AABBs' to help with e.g. frustum culling. They are very memory saving, with some squeezing you can end up with as few as 24-64bits, which can have a big impact if you do a lot of raycasts (e.g. visibility checks for AI), as most of the kd-tree fits into the cache. again, it's a bit unflexible and you have to find ways to deal with dynamic objects, there are paper that show how to create kd-trees in realtime, tho.

it might sounds stupid, but I always start with those, and they are plain-arrays of objects. up to maybe 10k objects, you probably won't notice them in your profiler. compared to the sorting of objects for good state management and sending drawcalls, it's extremely cheap. I run those on mobile devices with barely any impact. implementation time for a simple interface that allows you to "Add" and "Remove" objects is a 2h work at maximum. and it's easy to replace that implementation with anyone above. The big advantage of adding a acceleration struct later on is that you have real world profiling data, which allows you to make a better decision on what to choose.

an extension to this, and often used in space games is sweep&prune, it's your plain array that is sorted, you sort in your 'begin' and 'end' of objects on one axis, if you e.g. want to query all possibly visible objects, you start at the "begin" entry of your camera and collect all objects until the "end" entry of your camera. sorting is done with bubble-sort, as the scene barely changes between frames. there are multi dimensional implementations of this, due to the coherence between frames, it's also sometimes used in physics-engines (as they have sometimes sub-millisecond step sizes).

and there is also portal culling, which is quite efficient, but can be a bit cumbersome to setup and to handle special cases, e.g. what happens if two portals (or chain of portals) lead to the same area? if you use marker, how do you deal with multi-threaded queries? you also need a realtime visualization (editor), as the setup is done by level designers and they are not that technically skilled in those abstract things (e.g. does it make it faster if you split some corridor into two zones or keep it one? )




occlusion culling is actually quite fast, if you have a good lib or you know how to implement it, but if you never did one before, you will probably end up with something less performant than without occlusion culling. but there are some low hanging fruits for indoor rendering, 1st is to have a near far-distance plane in your camera setup, for indoor it means that you cull most of the level, while it costs you second to implement this. now you cull 99% of the level. Occlusion culling can still help you to deal with objects behind walls etc. but you could also try to precalculate a PVS e.g. a grid that you create offline, calculation which entry of the grid is visible from which other entry (isn't that different to a PVS in BSPs, but simpler to implement.

This is great, thanks for all your posts - especially Krypt0n.




That explains a lot!

I decided to go on with this thread a little bit and explain you guys what is the engine characteristics in terms of choosing the right algorithm from those listed above.

I Found your answers very helpful and just need to pick the right option here, but before that i just want to be fair with you and let you know the game specs - as i know that deciding about something without even looking at the presentation is a hard stuff to do.




From the game specs:

i read that the requirement is to implement the static objects mainly, so we'll have to manage animations more often than objects to traverse between rooms.

I see a 'level' is to be made max from 3 rooms which would be basically separated by doors that are to be opened when 'something is done' - so a typical approach,

you're stuck in a room until you find out the clue how to get out of there ( find a key somewhere and use it on the doors ).




Lights - max 2 lights per room which isn't that much




Shadow casters - 1 main shadow caster (omni) + eventual spot light shadows from player's lamp




Here's a drop from the already-being-built level area - it might explain more and help choosing the right algorithm for this game:











that is all they ask for.




As far as i go with the docs i find it more simple,

a player walking around, finding out clues in a one room, 3 clues found in 1 room lead him to the doors that can be opened and player moves to another room -

but can always come back to the first, and second one - so as i said 3 rooms within a level is what they are talking about.

To make it scalable - let's say they need 10 rooms ( in case they'll change the plan ) .




I would like to pick the most optimal level management option for this game and focus on 'loosing' fps for special effects and lighting instead of thinking when it's too late 'why did i choose that?'.







So what do you think now guys ?

will doors between rooms close again?

if you make it so that doors close themselves you have an automatic solution... if all doors to a room are closed and the player isn't in it... then don't render the room.
so even unlocked doors still close themselves after a short time or once the player moves away from them by a certain distance or something.

using this approach you could have looooads of rooms ;)

will doors between rooms close again?

if you make it so that doors close themselves you have an automatic solution... if all doors to a room are closed and the player isn't in it... then don't render the room.
so even unlocked doors still close themselves after a short time or once the player moves away from them by a certain distance or something.

using this approach you could have looooads of rooms ;)

Unfortunately nope, when doors are opened they stay opened and you see other room/s, you can of course close them.

My manager says that there might be a situation that doors can be auto-closed when a 'trigger' happens, but it is not a common thing - so we need to build a generic indoor engine here.




That door's system leads me to think i need to have Portals solution in place, but still want to confront that with your suggestions..