Archived

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

ashley_mcconnell

Frustrum Culling for racing game - comments please

Recommended Posts

Hi Folks, Please be gentle I am only learning :D I am considering track formats for my racing sim at the minute. Currently I just rely on the gfx card to do my culling as I just wanted to get something up and running to test out the physics. I am considering using quadtrees to quickly cull away large sections of track that will not be visible. This is my first venture into the world of gfx so can you confirm some assumptions / questions I have formulated. 1. All quads (at each level) are the same size. 2. You can only have 2x2 / 4x4 / 8x8 / 16x16 / 32x32 / 64x64 3. A good size for culling would be around 10meters 4. I store a list of references to objects contained within each quad tile, if the object would span "child quads" then it is stored at the level above (rather than the leaf node). 5. Quadtrees can help for collision detection. Can anyone suggest any other methods I should consider? Thanks for your help Ashley

Share this post


Link to post
Share on other sites
(1). yes
(2). yes, but ... (i.e 128x128,256x256... etc), total quads or at each level

For (3), its implementation dependant... depends on number of polygons per some area. YOu should find optimal number by educated trial and error. (4), thats one way to do it. (5). yes they do.

Another thing to note is that its best to use quad/octree on bounding geometry (triangles making up bounding box)... so if you have terrain/floor, divide it up into several boxes, and use each area's bounding box (3D axis aligned Bounding Box) 's triangles in the quadtree.

ps. no one will flame you for asking a serious question.

[edited by - SporadicFire on July 29, 2002 12:41:01 PM]

Share this post


Link to post
Share on other sites
1: Right, in a QuadTree, the Quads would be the same size.

2: Right, in a quad tree you divide space into 4 quadrants.

3: This is hard to determine. Testing and benchmarking is the only way to find out, but it''ll probably be different with every track.

4: You could do this but I would actually store a reference to every node that is in a node down to ever last node it intersects. So if it spans 3 nodes, those 3 nodes (and their parent) would know about them being there. Storing at the leaf is fine although perhaps not as optimized.

5: As a matter of fact, they help tremendously. I have a tutorial of doing Collision Detection using an Octree (3 dimensions instead of 2 as in a quad tree) on my website. Check it out if you need any help.

I checked out your little demo btw; very nice. I can see why you need some kind of performance enhancer though. The quadtree will definetly help. The physics are nice btw but you have some strange anomalies when the car is stationary.

SporadicFire: I dunno man, I think Ashley''s concern is warranted. I''ve seen people being flamed for less. She''ll be lucky if someone doesn''t say "search google" (and why google, why not hotbot or yahoo???).

"Love all, trust a few. Do wrong to none." - Shakespeare

Dirge - Aurelio Reis
www.CodeFortress.com
Current Causes:
Nissan sues Nissan

Share this post


Link to post
Share on other sites
i wonder why a quadtree should be so much faster than just storing your tiles in a 2-dimensional array. If all tiles are the same size you''ll know every one''s position. Determining which tiles are to be drawn is just like drawing a 2-dimensional triangle (the viewing frustum) at a very low reolution (depending on you tile-size of course). So instead of drawing a pixel on a 2d screen you draw your tile.

what do you think about it?

eloso

Share this post


Link to post
Share on other sites
Hi Guys,

Thanks for the advice and clearing up a few things for me and reinforcing my (limited)knowledge. I know there have been a few questions about frustrum culling in here - was just wondering if there were any special considerations for a racing sim type outdoor game.

Sporradic : yep, I was going to do bouncing box around each of the objects in the scene. The track will be split up into smaller sections (perhaps 20-30m long) and there will be barriers / trees / trackside objects. I will play about with tile size to find one that is the best.

Dirge : I don''t quite get your answer to number 4. Could you expand a little, I am sure your absolutely correct, but I just havent quite grasped what you are saying . Great! I''ll look at your tutorial (and referenced tutorials) when I get home - looks just what I need.

Glad you liked the demo, the physics are still quite primitive, although, the tyre model is pretty much there (however, the data is still a little dodgy atm). Quadtrees should allow larger tracks without much strain.

One question, am I right in my assumption that using the simpler (i.e. quicker) quadtrees rather than octrees with (on the whole) flat tracks is the correct way to proceed?

Oh yeah (clearing throat) - I am a man :D

Eloso : It means you can disregard large sections of the map at once rather than checking each of the tiles, or perhaps you mean something else?


Thanks for your replys guys

All the best,
Ash
http://www.siroccoracing.com

Share this post


Link to post
Share on other sites
You don''t have to check any tiles but just draw the ones in your frustum. Just remember how to render a filled triangle into a framebuffer. Well if you map your viewing frustum on the ground you''ll get a trapezoid, but for simplicity you can convert it to a triangle. So you have the 3 2d-coordinates of your "viewable area". You can divide them by your tile size and voilá you have 3 tile indices into your 2dimensional tile array. Now imagine each pixel coordinate of a triangle rendered to a framebuffer is an array index to the tile. So instead of putPixel(x,y) you do a drawTile(x,y).

Well, i''m not good at writing articles, but i hope now you understand it anyway.

eloso

Share this post


Link to post
Share on other sites
Ash,

if you will only make a race track then yes, quadtrees are perfectly fine. If you add tall buildings with many polygons (such as audience seating), then its a different story. Then you can possibly benifit from an octree. I see your racetrack is flat, so for now just need a quadtree

Share this post


Link to post
Share on other sites
Sporadic beat me again. Ditto on what he said.

Sorry about the confusion btw, hehe.

What I meant was, when you insert your world entity''s into the quadtree, you use their bounding volume as a means to determine which node they go in, right? Well, you would actually store a pointer (for instance) of them in every leaf node they intersect. You can''t just put it in their parents node because then the collision detection would get messed up. Imagine this: your entity takes up multiple node''s (or voxels, we don''t call them quads. well maybe some). So if you just put a reference to it in the parent, in a collision check you might be checking unneeded nodes. When you put it in the leaf nodes, you still do a check for the parents, which eventually branchs down to the leafs, where you finally do a more complex intersection test.

I really hope that clears things up a little.

"Love all, trust a few. Do wrong to none." - Shakespeare

Dirge - Aurelio Reis
www.CodeFortress.com
Current Causes:
Nissan sues Nissan

Share this post


Link to post
Share on other sites
Thanks guys,

That seems to make sense now Dirge . Although I''ll probably need to read it a few times before I start to implement .

Is the overhead for doing octrees much more. Perhaps it would be worthwhile?

Eloso : that makes sense to me, guys is there any reason against this?

All the best,
Ash
http://www.siroccoracing.com

Share this post


Link to post
Share on other sites