   Theoretical Project Help (Full Scenario Provided)
  I did start another thread a couple of days ago but feel it was badly titled and instead of bumping it again, I figured I would start a new thread.( Old Thread )Project ScenarioI am working with a research group who model all different sorts of evacuation procedures. For the purposes of this scenario we will assume that only building evacuation exists. One of their applications, as well as displaying evacuations in 2D space, has the ability to save two different files to disk which are as follows: Geometry File - This file contains the locational data of all your standard different sorts of objects you would associate with a building (i.e. floors, walls and stairs) Simulation File - This file specifies the amount of people and their exact movement throughout the simulation between 'nodes'. So far as we are concerned these nodes are merely 2D cordinates (no height as this is specified by the heights of different 'floors' and what 'floor' they are currently on) which specify where a person should be at any given point in time of the simulation.There might be only 25-30 people in a particular simulation, however there might be upwards of 10,000 people!Some of the viewports will be moving around above the people looking down at them.A reasonable frame rate will be required for this simulation (at least 25FPS).I will be using unmanaged C++ and unmanaged DirectX for the project.Considerations Noted AlreadyIt has become apparent that a decent LOD (level of detail) system will be required. After some background research it appears that a static-mesh-substitution approach will probably be the best way to go as the effect of 'popping' will probably be minimal due to the fact that even the characters with a high importance value (those which are close to the viewport and thus want to be created with maximum detail) will be fairly low-poly-meshes.The use of imposters for characters with a low importance value (those far away) sounds like a good idea (point masses). Not too sure about what should go inbetween/how many different meshes for people should be developed.Culling will play a big role (view-frustrum and occlusion) however I am still not sure which is supposedly the best way to implement these (oct-trees?).CommentsI am getting quite desparate to start segmenting this problem so that I can get on with designing the first iteration, so the more comments/help the better.Thanks for you time, it really is appreciated!Alex.(editted for typos)   
  Note that this really has nothing to do with DirectX specifically and probably belongs in the Game Programming forum.  It seems you're looking for suggestions as to general optimization techniques to make the simulation perform better.  This is a game play issue and not really a DirectX thing.  But I'll try to give you some suggestions.Quote:Original post by CHTHONICIt has become apparent that a decent LOD (level of detail) system will be required. After some background research it appears that a static-mesh-substitution approach will probably be the best way to go as the effect of 'popping' will probably be minimal due to the fact that even the characters with a high importance value (those which are close to the viewport and thus want to be created with maximum detail) will be fairly low-poly-meshes.The use of imposters for characters with a low importance value (those far away) sounds like a good idea (point masses). Not too sure about what should go inbetween/how many different meshes for people should be developed.This really depends on how detailed the original character models are and what you consider to be acceptable levels of detail.  I assume that the main purpose of this application is the simulation and it's not all that important that the graphical output be very fancy.As a first step, I would just try to use the original mesh up close and switch to imposters or billboards when you get a little bit away from the camera.  Once that works, perhaps add in one or two lower-poly versions of the original mesh.  That should be more than sufficient for this kind of application.  Commercial games usually use no more than 5.Quote:Original post by CHTHONICCulling will play a big role (view-frustrum and occlusion) however I am still not sure which is supposedly the best way to implement these (oct-trees?).This will probably be the most important part of your implementation in order to achieve acceptable performance when you're working with a large data set.  A search in the Game Programming or Graphics Programming & Theory forum will give you a lot of info on different occlusion schemes.An octree occlusion system would be a pretty good choice since you're dealing with a large amount of 3D data.  One thing to keep in mind, however, is that dynamic data is difficult to deal with in an octree implementation.  With an octree, meshes or sometimes even individual polygons need to be split apart if the cross a node boundary.  The octree would be a good structure to use for your building walls, desks, and other static objects because no update of the octree structure is necessary.For dynamic objects (the people in your simulation) another data structure might be a better fit.  Some kind of bounding volume hierarchy would be best here.  Updating this structure is just an exercise in pointer reassignment.  The mesh for each person would be enclosed in a some kind of 3D volume that would simplify testing for collisions/occlusions.  Spheres, cubes, and cylinders are common choices for this 3D volume.  Keep in mind that you don't need to actually render this 3D volume; it only exists to help determine which objects should be rendered.neneboricua   ;  What sort of technology are you aiming at? Reasonably powerful CPU's and GPU's, or laptops?I ask, because the sort of rendering you're talking about is well suited to geometry instancing which is primarily still a high-end 3D feature.Also, two other general questions?1. The realism of the people - how important is it? if it's just a representative simulation then we can get away with less detail and cut some corners2. If we're dealing mostly with buildings, can we assume that there will be a lot of images generated from inside corridors/rooms?I would give some serious thought to thinking about the algorithm temporally - that is, across a number of frames. I've had some seriously huge speed ups by being a bit "lazy" here. Sure, it's not always a 100% accurate but it's good enoughLazy evaluation: Only update all culling when the camera moves. If a single person/object moves then update only that object.Only update after a certain delta. Something I found with shadow volumes is that (at a high frame rate) a "move" event might be 0.00001 degrees (for example) which, if updated, is too small to have a visual result.Consider updating the data structures in a different thread where possible.Quote:Quote:Original post by CHTHONICCulling will play a big role (view-frustrum and occlusion) however I am still not sure which is supposedly the best way to implement these (oct-trees?).This will probably be the most important part of your implementation in order to achieve acceptable performance when you're working with a large data set.I 2nd this. Invest your design/planning time in the data structures and algorithms. Leave the actual Direct3D implementation details for a while.With reference to #2 above, you might want to add "PVS" - Potentially Visible Set - and portal culling to your list. I've not personally implemented it, but I have read about it. You should (with suitable pre-processing) be able to discard entire rooms/floors quite quickly using this technique - which will in turn allow you to  reduce the amount of potential rendering elements quite quickly.When it comes to the Direct3D implementation, also give thought to duplicating data - you don't have to work on the D3D-formatted vertex/geometry data! it might be more CPU-efficient to make a SYSRAM copy of only the bits of information you need and in a form that best suits your algorithms. With modern systems, you can almost certainly afford to trade a bit of additional memory storage for a possible speed-up.Finally, back to #1 above - if realism isn't paramount, then you might be able to get away with really low resolution meshes and lighting - which can only help with the final D3D implementation.hthJack   ;  First off, sorry for posting this in the wrong section! Secondly thanks for the responses. neneboricua19 Quote:Original post by neneboricua19This really depends on how detailed the original character models are and what you consider to be acceptable levels of detail. I assume that the main purpose of this application is the simulation and it's not all that important that the graphical output be very fancy.Correct. Obviously it would be nice to have detailed characters, but this is obviously not possible with thousands of dynamic objects (people). The objective is first and foremost an acceptable frame rate (30FPS+).Quote:Original post by neneboricua19This will probably be the most important part of your implementation in order to achieve acceptable performance when you're working with a large data set.  A search in the Game Programming or Graphics Programming & Theory forum will give you a lot of info on different occlusion schemes.An octree occlusion system would be a pretty good choice since you're dealing with a large amount of 3D data.  One thing to keep in mind, however, is that dynamic data is difficult to deal with in an octree implementation.  With an octree, meshes or sometimes even individual polygons need to be split apart if the cross a node boundary.  The octree would be a good structure to use for your building walls, desks, and other static objects because no update of the octree structure is necessary.For dynamic objects (the people in your simulation) another data structure might be a better fit.  Some kind of bounding volume hierarchy would be best here.  Updating this structure is just an exercise in pointer reassignment.  The mesh for each person would be enclosed in a some kind of 3D volume that would simplify testing for collisions/occlusions.  Spheres, cubes, and cylinders are common choices for this 3D volume.  Keep in mind that you don't need to actually render this 3D volume; it only exists to help determine which objects should be rendered.So you would suggest building an octree after loading all static geometry, then giving all dynamic objects (just people for now) a bounding volume for testing them against view-frustum visible and occluders (i.e. build the list of occluders first). I do not have to worry about collision detection because the system that outputs the the two files (Geometry and Simulation - see first post) guarantees the non-collision of people (that is part of their contract anyway!).jollyjeffersQuote:Original post by jollyjeffersWhat sort of technology are you aiming at? Reasonably powerful CPU's and GPU's, or laptops?A variety of computers. However assume that the target hardware is that of an average workstation computer that you would go out and buy from a computer store today (3ghz P4, 1GB RAM, latest or latest but one generation graphics card).Quote:Original post by jollyjeffers1. The realism of the people - how important is it? if it's just a representative simulation then we can get away with less detail and cut some corners2. If we're dealing mostly with buildings, can we assume that there will be a lot of images generated from inside corridors/rooms?As I mentioned in response to neneboricua19, the first objective is to get a decent frame rate and thus initially consider it a representative simulation (i.e. low-poly-counts). Your second question is a good one. Yes there will be a lot of people inside corridors/rooms. However, some walls will be made slighty transparent to allow the visibility of people from the other side of them.Quote:Original post by jollyjeffersI would give some serious thought to thinking about the algorithm temporally - that is, across a number of frames. I've had some seriously huge speed ups by being a bit "lazy" here.Yes, this makes sense. However the viewports (yes there is likely to be multiple viewports displayed concurrently) will be moving about a lot. But the concept still stands true, only update expensive objects when it will make a visual difference to the viewer.Quote:Original post by jollyjeffersWith reference to #2 above, you might want to add "PVS" - Potentially Visible Set - and portal culling to your list. I've not personally implemented it, but I have read about it. You should (with suitable pre-processing) be able to discard entire rooms/floors quite quickly using this technique - which will in turn allow you to  reduce the amount of potential rendering elements quite quickly.I found a nice article by Mikko Laakso regarding PVS/Portal Culling. If you have not already read it here is the linkI know I did not mention the transparent geometry (walls/floors) before, but because of this PVS does not sound like I could benefit my scenario much. However it is a very interesting idea and I shall bare it in mind for future projects.Quote:Original post by jollyjeffersWhen it comes to the Direct3D implementation, also give thought to duplicating data - you don't have to work on the D3D-formatted vertex/geometry data! it might be more CPU-efficient to make a SYSRAM copy of only the bits of information you need and in a form that best suits your algorithms. With modern systems, you can almost certainly afford to trade a bit of additional memory storage for a possible speed-up.Yup, have already thought about this!Quote:Original post by jollyjeffersFinally, back to #1 above - if realism isn't paramount, then you might be able to get away with really low resolution meshes and lighting - which can only help with the final D3D implementation.Define really in terms of a polygon count per person.Thanks again for your help guys,Alex.   ;  I'll let Francisco answer his part [smile]Quote:Original post by CHTHONICjollyjeffersQuote:Original post by jollyjeffersWhat sort of technology are you aiming at? Reasonably powerful CPU's and GPU's, or laptops?A variety of computers. However assume that the target hardware is that of an average workstation computer that you would go out and buy from a computer store today (3ghz P4, 1GB RAM, latest or latest but one generation graphics card).Okay, that sounds fine... but in all honesty a lot of the "workstation" machines I've seen in a regular office haven't had particularly fancy graphics cards. Onboard/integrated graphics still seem to be fairly popular with bulk office deals.Quote:Original post by CHTHONICQuote:Original post by jollyjeffers1. The realism of the people - how important is it? if it's just a representative simulation then we can get away with less detail and cut some corners2. If we're dealing mostly with buildings, can we assume that there will be a lot of images generated from inside corridors/rooms?As I mentioned in response to neneboricua19, the first objective is to get a decent frame rate and thus initially consider it a representative simulation (i.e. low-poly-counts). Your second question is a good one. Yes there will be a lot of people inside corridors/rooms. However, some walls will be made slighty transparent to allow the visibility of people from the other side of them.Are we talking about artificial transparency - as in, you're making the walls semi-transparent on purpose? or are we talking about actual windows in the walls?Quote:Original post by CHTHONICQuote:Original post by jollyjeffersI would give some serious thought to thinking about the algorithm temporally - that is, across a number of frames. I've had some seriously huge speed ups by being a bit "lazy" here.Yes, this makes sense. However the viewports (yes there is likely to be multiple viewports displayed concurrently) will be moving about a lot. But the concept still stands true, only update expensive objects when it will make a visual difference to the viewer.With regards to multiple viewports, I'd give some serious thought into trying to share the culling/LOD/whatever between them. I'm not sure it'll be possible, but it can't hurt to look into it [smile]Quote:Original post by CHTHONICQuote:Original post by jollyjeffersWith reference to #2 above, you might want to add "PVS" - Potentially Visible Set - and portal culling to your list. I've not personally implemented it, but I have read about it. You should (with suitable pre-processing) be able to discard entire rooms/floors quite quickly using this technique - which will in turn allow you to  reduce the amount of potential rendering elements quite quickly.I found a nice article by Mikko Laakso regarding PVS/Portal Culling. If you have not already read it here is the linkI know I did not mention the transparent geometry (walls/floors) before, but because of this PVS does not sound like I could benefit my scenario much. However it is a very interesting idea and I shall bare it in mind for future projects.Fair enough I suppose... although, I think it's been mentioned, but occlusion culling might well be a good option - even with translucent walls.Quote:Original post by CHTHONICQuote:Original post by jollyjeffersFinally, back to #1 above - if realism isn't paramount, then you might be able to get away with really low resolution meshes and lighting - which can only help with the final D3D implementation.Define really in terms of a polygon count per person.less than a 100 triangles. Think of a stick-person but a little bit more "solid". Instead of two lines for the (upper/lower) leg you could have a cube/rectangular object to give it a bit of volume.Another trick to play with LOD is to disable lighting - render them with an approximated ambient value instead. That combined with some decent batching and even your most pathetic hardware should still be able to tear through 100's of them...Just out of curiosity... you're on an industrial placement in London? which university you from? I just returned to UoN from a placement with IBM...Jack   ;  Thanks Jack,Quote:Original post by jollyjeffersAre we talking about artificial transparency - as in, you're making the walls semi-transparent on purpose? or are we talking about actual windows in the walls?Semi-Transparent on purpose.Quote:Original post by jollyjeffersWith regards to multiple viewports, I'd give some serious thought into trying to share the culling/LOD/whatever between them. I'm not sure it'll be possible, but it can't hurt to look into it.Sounds unlikely that this is possible, but like you say, worth considering... another to cut down on redundant culling.Quote:Original post by jollyjeffersFair enough I suppose... although, I think it's been mentioned, but occlusion culling might well be a good option - even with translucent walls.Very possible as people tend to jam together when waiting for an exit and hence obscuring one another.Quote:Original post by jollyjeffersless than a 100 triangles. Think of a stick-person but a little bit more "solid". Instead of two lines for the (upper/lower) leg you could have a cube/rectangular object to give it a bit of volume.100 triangles, including a face of sorts? That might be pushing it a bit.Quote:Original post by jollyjeffersAnother trick to play with LOD is to disable lighting - render them with an approximated ambient value instead. That combined with some decent batching and even your most pathetic hardware should still be able to tear through 100's of them...Funny you should say that. I read that elsewhere and have already messed about with it.Quote:Original post by jollyjeffersJust out of curiosity... you're on an industrial placement in London? which university you from? I just returned to UoN from a placement with IBM...IBM Hursley? I was there a while back for the 21st BCS Programming Competition (this year - 2005). Nice place. I would rather not disclose which university I am from or other personal details! :PThanks again,Alex.;Quote:Original post by CHTHONICQuote:Original post by jollyjeffersWith regards to multiple viewports, I'd give some serious thought into trying to share the culling/LOD/whatever between them. I'm not sure it'll be possible, but it can't hurt to look into it.Sounds unlikely that this is possible, but like you say, worth considering... another to cut down on redundant culling.If you implement a tree-based culling system then you might well be able to do the visibility by traversing the tree once (but checking each node against all viewports) rather than traversing it once-per-viewport.Quote:Original post by CHTHONICQuote:Original post by jollyjeffersless than a 100 triangles. Think of a stick-person but a little bit more "solid". Instead of two lines for the (upper/lower) leg you could have a cube/rectangular object to give it a bit of volume.100 triangles, including a face of sorts? That might be pushing it a bit.Well thats sort of the idea - to push it [smile] If you just need something to represent a person then you really don't need that much detail. Heck, even a cube for a head might suffice...Quote:Original post by CHTHONICQuote:Original post by jollyjeffersJust out of curiosity... you're on an industrial placement in London? which university you from? I just returned to UoN from a placement with IBM...IBM Hursley? I was there a while back for the 21st BCS Programming Competition (this year - 2005). Nice place.Yup, thats the one. Several other placement people I worked with helped out at the competition. I was busy that day [smile]It was a very nice place to work at, but most of it is just regular office-space rather than the really nice stately home in the middle [lol]Jack   ;  Yes we had our own room in the really nice stately home if i recall.Alex.   ;Quote:Original post by CHTHONICCorrect. Obviously it would be nice to have detailed characters, but this is obviously not possible with thousands of dynamic objects (people). The objective is first and foremost an acceptable frame rate (30FPS+).For something like this, I would really recommend that the people all be just the same model generic model.  Things like facial features, hair, etc... are not important when the whole point is to simulate evacuation procedures.As Jack has mentioned in his reply, you could even get away with 100 poly models.  Programmer art "4 teh win!" you could say.  The model could be a cube for the head, another for the torso, each of the limbs could be made of 2 or 3 cubes each.  Heck, you may not even need to animate them at all.Quote:Original post by CHTHONICSo you would suggest building an octree after loading all static geometry, then giving all dynamic objects (just people for now) a bounding volume for testing them against view-frustum visible and occluders (i.e. build the list of occluders first).Pretty much.  At load time, you distinguish between static and dynamic objects.  You can throw static objects into an octree.  For the dynamic objects, build a bounding volume hierarchy.  This hierarchy could then be used for view-frustum testing and other optimizations.neneboricua   ;  Hey guys,Just had a couple of thoughts on the matter, one regarding culling and one regarding the people in the simulation.CullingIt is striking me as I am messing about with some abstract designs in UML that occlusion culling itself might actually be pointless and even possibly detrimental. All the static objects are going to have such low polygon counts (walls, floors, even staircases are going to be primitive and not have that many) that checking if they are occluded by a non-transparent object could cost more computational time than just rendering them anyway. It be better just to stick to Frustrum Culling. Any thoughts on the matter? (Please remember that walls are likely to all be semi-transparent although this is yet to be confirmed).PeopleI have been informed that person characters need to be more detailed than 100 poly-counts. I am not designing the meshes for them, but does this affect anythingThanks for your continued help,Alex.   