Jump to content

  • Log In with Google      Sign In   
  • Create Account


Indoor rendering


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
45 replies to this topic

#1 xynapse   Members   -  Reputation: 151

Like
0Likes
Like

Posted 26 October 2011 - 04:10 AM

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.
perfection.is.the.key

Sponsor:

#2 xynapse   Members   -  Reputation: 151

Like
0Likes
Like

Posted 26 October 2011 - 12:41 PM

Really nobody ?

Is it that secret?
perfection.is.the.key

#3 Molle85   Members   -  Reputation: 172

Like
0Likes
Like

Posted 26 October 2011 - 02:05 PM

Unless you just want to batch your entire level then yes, that is still the preferred way to do it.

#4 Vilem Otte   Crossbones+   -  Reputation: 1343

Like
1Likes
Like

Posted 26 October 2011 - 06:02 PM

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).


My current blog on programming, linux and stuff - http://gameprogrammerdiary.blogspot.com


#5 Hodgman   Moderators   -  Reputation: 26958

Like
2Likes
Like

Posted 26 October 2011 - 06:14 PM

Portals are still used and BSPs are still used too.

#6 Krypt0n   Crossbones+   -  Reputation: 2269

Like
4Likes
Like

Posted 26 October 2011 - 11:15 PM

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.












#7 xynapse   Members   -  Reputation: 151

Like
0Likes
Like

Posted 27 October 2011 - 02:42 AM

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




That explains a lot!


perfection.is.the.key

#8 xynapse   Members   -  Reputation: 151

Like
0Likes
Like

Posted 27 October 2011 - 03:24 AM

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:






Posted Image




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 ?
perfection.is.the.key

#9 bwhiting   Members   -  Reputation: 617

Like
0Likes
Like

Posted 27 October 2011 - 03:39 AM

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 ;)

#10 xynapse   Members   -  Reputation: 151

Like
0Likes
Like

Posted 27 October 2011 - 04:03 AM

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..








perfection.is.the.key

#11 bwhiting   Members   -  Reputation: 617

Like
0Likes
Like

Posted 27 October 2011 - 04:26 AM

While I'm not sure what position your in with regards to moulding how this goes but I often find if I approach the powers that be with some cold hard facts supporting an idea they often respond the right way.

i.e. propose a few solutions one of them being, doors that close automatically and with this small alteration/addition they get faster build time, a much more simple to update system, highly scalable with no extra effort for designers etc...

when you lay it out like that it will make your solution much more tempting, all those benefits and just from coding in some doors mechanics (which aren't that uncommon)

but this might not be possible for you as I don't know your full brief or what your client and managers are like.

good luck Posted Image

#12 xynapse   Members   -  Reputation: 151

Like
0Likes
Like

Posted 27 October 2011 - 04:52 AM

While I'm not sure what position your in with regards to moulding how this goes but I often find if I approach the powers that be with some cold hard facts supporting an idea they often respond the right way.

i.e. propose a few solutions one of them being, doors that close automatically and with this small alteration/addition they get faster build time, a much more simple to update system, highly scalable with no extra effort for designers etc...

when you lay it out like that it will make your solution much more tempting, all those benefits and just from coding in some doors mechanics (which aren't that uncommon)

but this might not be possible for you as I don't know your full brief or what your client and managers are like.

good luck Posted Image

I would really love to have a chance to propose new approaches in the area but as you probably know - i meet the escalation path, and people above stand hard as rock without even trying to hear what are some 'new better solutions'. So it always comes back with : "Client requirements are more important than our proposals".


And at the end of the day it's all about: meetings, reports and feedbacks.

Argh, you probably know all of that ;)







perfection.is.the.key

#13 Krypt0n   Crossbones+   -  Reputation: 2269

Like
0Likes
Like

Posted 27 October 2011 - 10:02 AM

if the basic level geometry is really made from boxes, you could calculate the bounding box for them, then calculate a PVS (as you said they are static).

all the other objects can be sorted into those bounding boxes, it's also easy to check where the player is.






#14 xynapse   Members   -  Reputation: 151

Like
0Likes
Like

Posted 28 October 2011 - 11:48 AM

Bad news are, that they client pointed out something about BSP during the meeting, and it seems we will have to go that way..

BSP, PORTAL + PVS - is what will satisfy them.

Now as it turned out into something i wouldn't expect, seems like right now i should be looking for a good class / info of how to convert a level that is a mesh to a working BSP +PORTALS+PVS solution..


So the scheme would now look like:




3ds max level -> goes via exporter to the engine that loads this model and 'does' bsp + portals + pvs on it..



Damn.. Anyone can point me to something worth studying, or maybe you guys already have something working so i could have a look to find myself in this and understand how it really works ...?
perfection.is.the.key

#15 carangil   Members   -  Reputation: 485

Like
0Likes
Like

Posted 28 October 2011 - 02:16 PM

Actually, with today's hardware, does traversing the BSP tree make sense? If you have portals + PVS, then you've solved most of the visibility issues.

Based on the player's position, for each set of polygons that's visible, just draw the whole set. All these buffers are static VBOs, stored probably on the graphics card. The graphics card will just claw through the polygons faster than you can traverse the BSP tree to figure out exactly what is visible. Note, I'm assuming a desktop system with a non-ancient card; if this is for a mobile device, maybe BSP is faster.

I'm using a dead-simple system in my project: Draw whats in the player's current room, recurse into rooms who's door is open and the door is in the frustum. While recursing, 'shrink' the frustum to fit the door.


#16 Codarki   Members   -  Reputation: 462

Like
0Likes
Like

Posted 28 October 2011 - 02:30 PM

A mixed hybrid of CPU and GPU occlusion checks. Build a model of the world, a bit like physics, but occlusion world that is contained within every entity in game. You might want to google how Umbra does stuff.

#17 Krypt0n   Crossbones+   -  Reputation: 2269

Like
0Likes
Like

Posted 29 October 2011 - 02:58 AM

Bad news are, that they client pointed out something about BSP during the meeting, and it seems we will have to go that way..

BSP, PORTAL + PVS - is what will satisfy them.


sounds like not an engineering, but a communication problem, as you shall propose the best solution for the clients ;)


the world of engineers developed a solution for that called 'overpriced consultant', he will ask your team what you think is best, will present that to your clients next to his bill and they'll tell you to do as he said.

</joking>

I suggest, you to first check out some open source bsp compiler, maybe one of their license fits you and you'll save tons of work.( you don't have to deliver the bsp compiler with your software, I guess).

There are quite some paper about automatic portal placement in bsp trees, I think last time I was reading bout it was in http://www.amazon.com/3D-Games-Real-Time-Rendering-Technology/dp/0201619210






#18 xynapse   Members   -  Reputation: 151

Like
0Likes
Like

Posted 30 October 2011 - 05:54 AM

Success, it is up to me now to decide what to use to get this game going, so i have 5 days ( till Friday ) to figure out finally what to choose.

Luckily we can forget about that BSP scary thing - this method always looked for me like overcomplicated...




I liked DracoLacertae's idea, have a bunch of objects as the map - each representing separate room ( sector ) and additional place portals within editor for later culling.

Theoretically a single VBO/IBO or just VAO per sector can do the thing when it comes to render the room with a single call.







Now when it comes to design - this is something i would like to ask you, as you guys have an experience and your engines are already up and running.

Also i know that a good design leads to better development and there is no need to do any rollbacks later on - thus i will try to go into details of: "How to generate the sectors and manipulate them".




I always say it's better to see something and speak about it than to spend a time figuring out what the heck are we talking about so,

Let's have a look at the first level ( this is the official level one map mesh/scheme )




Posted Image




Posted Image







Eventual portal positions

Posted Image




Now as level designers will place portals manually ( i think there is nothing wrong with doing it 'by hand' what do you think?) - and i will probably export them as a separate list of faces -

how do i know which portal leads to which sector ? So when testing visibility i will know that

Portal[x]->Leads To Sector Y

I am kinda worried when thinking that this information would have to be provided 'by hand' somewhere and would love to have this a bit confronted with what you do.




Knowing that a level is made of objects - each being a separate sector, how do i handle data within a Portal face, that informs what sector that Portal leads me to ?




















perfection.is.the.key

#19 RobMaddison   Members   -  Reputation: 636

Like
0Likes
Like

Posted 30 October 2011 - 11:13 AM

Surely this is very simple logic...? If you give each sector an id - I'm sure all your static objects have an id - each portal has two ids, one links to one sector and the other links to the other. Does it need to be any more complicated than that?

#20 carangil   Members   -  Reputation: 485

Like
0Likes
Like

Posted 30 October 2011 - 12:56 PM

Surely this is very simple logic...? If you give each sector an id - I'm sure all your static objects have an id - each portal has two ids, one links to one sector and the other links to the other. Does it need to be any more complicated than that?


Yeah thats all you really need. In my system, my portals are single-directional. Each sector has a list of portals, and each portal has a target. So to connect room A to room B, room A has a portal to B and room B has a portal to A. This lets me do weird things like have a 1-way doorway; like a teleporter or something.

Also, my portal implementation is very simplistic at the moment. I considered using fancier occlusion tests, but I'm getting good results with a bunch of cheats. For instance, my culling 'frustum' is really just a cone.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS