• Advertisement

Archived

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

Scene Hierarchy in a Race Game

This topic is 5065 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello everybody, I''m gonna start real soon a "wipeout" style game, but I''ve encountered some theorical problems... I''ve have already coded some engines using BSP trees(they were quake like as you''ve guessed), but never coded an engine for outdoors. So I documented myself with books and my friend google, and apart the BSP trees data structure, there seem to be the quadtrees and the octrees(apparently they''re analog to 2D_BSP and 3D_BSP). The great advantage of BSP trees is the double information contained in the nodes(if leafy bsp) or in the leaves : - Fast frustum culling in object space - Z sorting Althought I''ve never coded Quadtrees or Octrees, it is obvious that these two do not permit Z-sorting, and if they can, I''ll be very happy and curious to know how. So my problem is here, I''d like to design tracks(that will be statics), then input them in a home made 3Dcompiler that will output the structure that the engine will use. I''ve thought of doing a 2DBSP compiler where the tracks will be seen from the sky (projected on the X,Z plane); the first splitting plane will be the start segment of the track, then I will kinda detect the curves on the circuit so that my planes will be placed othogonally to the track normal direction. What annoys me is detecting this notion of curve, and also, it limitates the design quite a lot(tunnels, no tracks going too much up and down). The second idea is using a quadtree, wich will regularly subdivide zones in 4 smaller zones. For each leaf, I would calculate a PVS. But with this approach I won''t have Zsorting as the camera orientation isn''t unique, and besides if I let the players go in reverse sens on the track, the PVS will be of a greater size. So I need help . Maybe all I''ve said is rubbish, but I''d like to know what have professionals used for their games(Wipeout, RidgeRacer, POD...), and of course your personnal advices. I really need a structure usable for ZSorting AND for Frustrum Culling, the game is intended for the GBA wich is slow(I''ve already did a quake1 bsp engine in ASM wich worked at 25FPS on this console, so I''m kinda optimistic and curious).

Share this post


Link to post
Share on other sites
Advertisement
One of the main reasons that the BSP technique is outdated these days is because Z-sorting isn''t much of an issue any more. You can just use the Z-buffer.

Share this post


Link to post
Share on other sites
quote:
Original post by superpig
One of the main reasons that the BSP technique is outdated these days is because Z-sorting isn't much of an issue any more. You can just use the Z-buffer.


Z-sorting is still useful with a z-buffer, just for different reasons. Instead of drawing back to front to get everything looking correct, you want to try and draw front to back to capitalize on the z-buffer early exit and thus minimize your overdraw. Of course, it's certainly not essential, it just helps to keep your frame rate up.

As for the original question, I think that bsps are actually quite popular in racers - the race takes place in a series of linked rooms which form a tunnel, with trees and other bits of scenery by the side and a nice skybox to make it look like you're driving about in the open.

Of course, this assumes you're not allowed to venture or see far away from the track. If you want more freedom, you'll probably want to go for a quadtree/octree thingy and sacrifice your z sorting.

EDIT: just noticed you said you're developing this for the GBA. So maybe z sorting is essential...

[edited by - Sandman on April 14, 2004 9:39:29 AM]

Share this post


Link to post
Share on other sites
Well I don''t think BSP is outdated, and I don''t think it will be until we find a better structure for indoors. Even if ZBuffer in hardware is fast, you can still use the informations contained by the tree to draw from front to back as Sandman said. The original quake would use a front to back ordering with a span buffer and a zbuffer, the zbuffer was used after for drawing the moving entities.
Anyway, I can hardly admit there is no way of precalculating the sorting of the polygones in a quadtree... Maybe I could stop the recursion of the quadtree compiler when I get convex leaves? (it means that Z Sorting isn''t important here). If you think about it, don''t we have a lot of these convex places for small portions of a race track?
Isn''t there in here an old Gourou who would knows some tips on how it was done back then(Wipeout, TestDrive 1,2,3, Ridge Racer...)???
Also, when traversing a Quadtree in Back to Front, let us say our camera is C, and + is the normal direction of the plane :

a| b
C |
|
__+_________
d| c
|
+|

We would do(for rendering) : c, b, d ,a OR c, d, b, a?
Is it important BTW?


Share this post


Link to post
Share on other sites
Actually you could probably just sort the children as you traverse the tree, and thus traverse each node''s children in z-order. There''s only ever 4 nodes to sort at a time, so sorting them isn''t going to be all that difficult.

I can''t think of any cases where this wouldn''t produce a properly Z ordered result off the top of my head. However, as I mentioned before, I think games like wipeout generally use an ''indoor'' engine like a bsp tree. Unless you want to give the player the freedom to completely ignore the main track and go off exploring the terrain, you''re probably better off with the bsp approach.

Share this post


Link to post
Share on other sites
The problem I have with the BSP approach on a track would selecting the splitting planes. For an indoor game, you usually use splitting planes out of well choosen polygones (the one who will balance well the tree and will subdivide few polygons). But in a race game, isn''t there any good heuristic to determine the splitting planes?

Share this post


Link to post
Share on other sites

  • Advertisement