Archived

This topic is now archived and is closed to further replies.

JoshG

Rendering a Scene/Map

Recommended Posts

Ok, I''ve read allot of articles about how to draw things to the screen and different ways that make it fast to draw terrains etc... However, I have never found an article that discuses ways in which a game engine should draw an entire scene. naturally this involves drawing both the terrain and the objects that appear in the scene, however if you have a large scene then this would be rather slow. Is there anyone out there who would be willing to discuss this or even point me in the direction of an article they have read? I''m wondering in what way i should structure the information describing a map, ie...do I have one structure to list all the Objects in the map and one structure to describe the terrain of the map? For the structure listing the objects is there any particular type of structure that allows the engine to quickly decide which objects currently need drawing or not? (ie are they in view or within a particular range?) Thanks! --Josh

Share this post


Link to post
Share on other sites
octrees are good, they can really quickly occlude stuff. if the circumstances are right, you can cull 7/8ths of the level in one bounding box test. if its mostly indoors, take a look at BSPs

Share this post


Link to post
Share on other sites
The other problem is that some objects in the scene will move over time...If I were to use an octree or a Quad tree, how would I be able to calculate what the next quad/oct it should be placed into is?

Share this post


Link to post
Share on other sites
after you build the octree, once things are moving don''t make any new nodes. so if an object moves, start in the root node, and check which child node its in. then find out which child node it is in of those, until you reach a node without any children (leaf). if the object intersects two node borders, put it in the lowest parent that encloses both the borders, even if that means it gets stuck in the root node.

Share this post


Link to post
Share on other sites
ok then. I''m beginning to understand how this is going to work then, it''s making more and more sense.

Generally would an engine also have a list of all the objects within the map so that it could perform routine operations on it every frame...

Actually, one way of doing it would be to let every dynamic (moving or otherwise changing) object to have a time associated to it indicating the last time that it was processed using the physics enging (ie for rotate functions or something) in that way you could simply process JUST the objects within view and the others would still have moved by the time you turn back to view them...

Am I getting this do you think? do you know of anyone doing this before? is this common?

Share this post


Link to post
Share on other sites
Well, if you leave things for too long before you process them again, you run into a lot of trouble when there are many objects that could potentially interact. Say you have 100 balls bouncing around that are outside of the viewing frustum, and so not being processed. Then, suddenly the camera turns and they *are* in the frustum, and the last 10 seconds needs to be processed all at once. There are obvious problems with multiple collisions, etc etc. It might be better to implement some form of that idea in moderation, say, only process the objects out of the view 5-10 times per second instead of every frame. Neat idea ;o

Share this post


Link to post
Share on other sites
Yes, I was thinking about that idea a little more and thought that If the objects were moving then their movement wouldn''t be processed when you arn''t looking at them, meanwhile the object may be supposed to be moving into the viewing area. I guess that''d be a large problem in it, however for things like Periodic rotation of an object and things like that then it shouldn''t affect the way the scene works too much then.

I just read in an article that Octrees are expensive at runtime (I can imagine that they are) and that they are better suited to static models.
(http://www.gamasutra.com/features/19991109/moller_haines_02.htm)

If this is the case then what is a "better" method of culling for dynamic models?

Share this post


Link to post
Share on other sites
wait a sec, are ALL the things in your scene dynamic? with an octree, you have to build the octree on loading/level compile or something, and then in the game when thigns are moving around, don''t create/delete new nodes like when you compile the octree.

Share this post


Link to post
Share on other sites
No...Not ALL things in the scene are dynamic...
It''s an outdoors engine, So you have trees, the terrain, buildings etc that remain in the same place, (however they may dissapear or their state changes (that wouldn''t affect the way in which the octree functions though would it?) then you also have your dynamic objects...ie cars/buses/planes/animals/people that sort of thing

Share this post


Link to post
Share on other sites
then here is what you do. when you load the level (or compile it if you have an editor), put everything into it, creating nodes as necessary. once its loaded, and things are moving, don''t mess with the nodes at all, just move the things around in it, but without creating new nodes. you only need to calculate which node its in if it moves, so the only things that would be finding a new node to be in are things that are moving.

Share this post


Link to post
Share on other sites
Is there a reason as to why I wouldn''t create new nodes whilst in an octree?

the way I am thinking at the moment is that each cube that a node in the octree represents has a list of objects contained in it, those objects listed within the node in the octree will be drawn if that node is visible. If I wanted to create a new object say a new car then couldn''t I just add to the list of obejcts in that node?

Share this post


Link to post
Share on other sites
ah, ok then, that is a good point, I wasn''t thinking of doing that but it does open up another area to think about. How far would I go about subdividing the areas. I suppose I would be dividing it by a set amount then...

What exactly is wrong with making another subdivision if decided it is needed at runtime? what are the problems associated with it?

Share this post


Link to post
Share on other sites
its not necessarily actually making them thats the problem as it is check to see if a node needs to be created/deleted. like when your object leaves a node, are you going to check to see if there aren''t any objects left in it? or if you enter a node, are you going to recurse through the whole tree to see if its a node of minimum size?

Share this post


Link to post
Share on other sites
my method is a bsp tree build into an octree

i do frustrum culling for the octree and then i render the polygons of the octrees as normal bsp trees


the only problem is you need to splitt your polygons so they fit into the octrees

thats way my octree size is 512 and the player is 72 units big
that reduces the split faces a lot and makes it a really fast method to draw you can even link the bsp trees of the individual octrees to check whether they are visible or not

Share this post


Link to post
Share on other sites
ok then, thanks,
I suppose I''ll read more about BSP trees now,
I was thinking that I would use a Hybrid between an Octree and a Quadtree so I can have CLOD terrain..
does anyone use an Octree and still have a CLOD?
any suggestions on doing it?

Share this post


Link to post
Share on other sites
in the game i''m working on my plan is to use a bsp for polygons and ONLY polygons. then use a big octree for the world and only for all the game objects, decoration meshes, and the terrain. hopefully that way i can get a more seamless transition from indoor/outdoor without a loading time.

what you would do (i think), i''ve never thought about it, but you would store the vertices in patches, like 16x16. you would store those patches in the octree/quadtree, and then when you build the terrain with CLOD, you could easily find which patches to use in building the vertex buffer/array. but thats only if i''m thinking of the right thing, i don''t know much about CLOD. its where you rebuild the vertices every frame right?

Share this post


Link to post
Share on other sites
CLOD takes a heightmap and then decides which verticies should be drawn depending on how far away from the viewpoint they are and how much their being drawn would affect the final image on the screen.

Share this post


Link to post
Share on other sites
Can someone here tell me how you might store vast terrains on a diskfile most efficiently?

Im looking at a scale like a MMOG, and wants to store huge maps... But how would i go about the storage?

Regards

Share this post


Link to post
Share on other sites