Sign in to follow this  
funkeejeffounet

Desperate for finding a good partitionning scheme for a racing game...

Recommended Posts

Hi, Since I have the project of a 3D race game on GBA, I've documented myself a lot and posted a lot here to know of a good partitionning technique concerning my project. I've implemented with success ABTrees but they do not seem being the right choice for the job as I need perfect Z sorting precomputed. Plus, the overgrowth of the Bounding Boxes for non splitting some faces do have consequences in software pipeline... Quadtrees(and octrees) have the same problem in term of Z sorting. I've thought of including a mini bsp in each leaf but then the traveral of the tree becomes too costy at each frame(I cannot afford loosing CPU cycles, nor pushing the stack too much...). So I've finally thought of my old friend the bsp trees, but another problem rised. This is a race game so no walls are presents, the splitting planes are choosen from road segments and are orthogonal to the ground(you can see this as 2.5D BSP with the splitting being done while viewing a race track from up). There are two distinctive parts in the game : - The road where the ships always lie(for collision detection) - The environment(buildings, tunnels and more), here the ship cannot approach them, they are here to make the levels nicer. By the way, those entities are convex, so no z sorting need to be performed on their faces The first problem is when stopping the construction of the BSP tree : - The BSP is leafy cause no polygone can be stored in the nodes(the splitting planes are not generated from polygones) - But as there are road polygones and environment polygones, recursion cannot stop when we have a convex area cause this will never occur, believe me. - Then I should have a polygone per leaf... Absolutely untolerable for the sake of the tree's depth. So I'm stuck :-) Someone told me on a forum that BSP were popular back then for 3D race games like wipeout. But then any idea on the tree construction(how to choose the plane, what info is stored and when do we stop recursion in the construction period)? I tried to find technical links on POD, ridgeracer, FZERO, wipeout and so and so... But could not find anything. If someone know of an old article on these, I would really aprreciate ! Or any other method you know that will help me think better. Cheers, Jeff.

Share this post


Link to post
Share on other sites
I never implemented it myself (moreso on limited hardware with limited storage), but lately I've been thinking about space partitioning schemes for games where the camera follows a fixed path (track-based racing games and arcadey shooters like RayStorm, Ikaruga and etc).

I've been thinking about pre-computing and pre-sorting the visible geometry every n-frames of n-movement units along the path, and store these lists. Then the game would only need to load the visibility data for the current path section.

How big the resulting datates would be would vary, and I'm unsure if this would be viable on the GBA. Depends on how it's done, and how often you store the sets. If the camera can only face forward the path (like in the first Need for Speed), the whole track geometry could be easily pre-sorted and streamed into the screen as the camera moves forward.

Share this post


Link to post
Share on other sites
I also thought about this, I wanted to sort the road as an ordered linked list of poly from the startup line to the startup_finish/line. Then I would have used a bounding sphere hierarchy to determine where the camera is and in each leaf(smallest bounding sphere), the visible poly woul be listed in Z order by index.
But as you've correctly guessed, this does takes memory and unfortunately this project is for a coding compo of 512Kbytes...

There must be a way when you think of it of doing this with accuracy and in a fast way. RidgeRacer on Playstation1 had only 1.5MB of data for the whole game with the music being taken out.

I've thought of many ways(combining BSP trees for the road and a ABTree for the outdoors object as they are convex solids, but this does have a Z sorting problem when an object is in a curve for example; plus it means two trees traversal...).

We definetly need the advice of an oldschool coder or from a cultivated mind :-)

Share this post


Link to post
Share on other sites
Hi,

This is something I did in the past, that worked quite well.

Since you say you only need to sort the track, then a solution is to use a 'sectional' scheme. That is divide up the track into sections, their length is up to you, but obviously should not be too long as to cause draw order errors on things like curves. Each section can be drawn from the outside polygons inward, but this can lead to order errors if your track has walls on a curved section ahead of the player. If this is the case then the draw order of a section should be say left to right, and some simple checks to decide which way to cycle through this list to get the correct order.

In the past i've defined sections as 2D quads, so its easy to determine the section the player is currently in (useful for collision detection if you had walls). Then using the direction the player is facing to determine which way to loop through the sections (forward or backwards depending on if the player is facing the right/wrong way).

Another useful property of sections is being able to define a view distance (i.e x number of sections), can of course break down in areas of tight turns, but if thats the case then you could create a visibility list per quad section, defining which sections to draw. This is also essential if you have areas of cross overs (bridges etc).

Oh yeah since a section can be given a forward direction its easy to determine if the player is facing the right/wrong way, and each one can act as a virtual check point to ensure players don't cheat when making a lap.

Hope this helps

Share this post


Link to post
Share on other sites
Hi,

I'm happy to see someone that have implemented this kind of stuff !

Could you please explain a little more how the compiler should work?
- Is the structure a quadtree? Then the leaves are the "sections"?
- How do you provide a perfect Z sorting inside a leaf?
- Do you treat differently the road and the environment?
- I don't see the point in having a PVS, doesn't a front to back or back to front tree traversal with frustum culling enough?
- How do you determine the vector giving the "right" direction of the player? Is it computed or given by the graphic artist?

I would be really glad if you could enlighten me on those.

Cheers, Jeff.

Share this post


Link to post
Share on other sites
Not sure if your asking me those questions, but i'll reply just in case.

- Is the structure a quadtree?

Nope, its simply an array, although it could be a double linked list.

- How do you provide a perfect Z sorting inside a leaf?

Well this really does assume your track is of a very simple construction. That is in my case a cross-section of the track looked like \____/ , or at least that was the basic frame work. As its clearly convex (if you imagined it solid) then it doesn't matter what the draw order is per polygon within a section. However in practice I noticed that if you could see a bend in the distanceat 90 degrees and many sections away from where the camera is, then one bend direction (left or right) would render back to front. However this happened in the distance and I never bothered to fix it, you were travelling to fast to notice most of the time.

Obviously this isn't good, but a little thought can make it work. Basically as long as the track is simple and convex like in the ASCII sample, then you can simply draw the polygons in any order. However if you sort them say left to right, then you can use the section forward vector with the camera forward vector to determine which way loop through this section list of polys. (I think - not tested).

Oh if you haven't realised my sections where all 1 polygon deep (i.e infront of you), this meant by simply drawing the sections in the right order eliminated any possiblity of incorrect sorting. There is no reason why you can't make it deeper than 1 polygon, as long as the draw order within the section can be pre-determined.

I guess another way to think of it is that the sections are just cubes, attached to form the track, thats the basic principle, and that being inside the cube means you can render the polys in any order.

- Do you treat differently the road and the environment?

Nope, they were all part of sections, but there is no need to do this, just store an index to an object in the section definitons - you said draw order wasn't a problem with them?

- I don't see the point in having a PVS, doesn't a front to back or back to front tree traversal with frustum culling enough?

Thats true, but a PVS can give added benifits. Firstly you don't need to bother doing frustrum culling. Secondly it makes it easier to deal with bridges and crossovers, as those sections which may be many, many sections away in the section array can be drawn, without the inbetween ones.

- How do you determine the vector giving the "right" direction of the player? Is it computed or given by the graphic artist?

In my case it was computed. As I said each section was a 2D quad that contained a number of polygons that formed the track. By using the 2 points of the quad that defined the back line of the quad, you can obtain the lines vector, from this the forward vector of the section. Then a simple dot product with the player's forward vector against the forward section vector can determine if they are going the wrong way.

Perhaps if I explain my OLD project a bit more it would help. It could be that your game is far more complex, than a simple track on a GBA leads me to beleive. In which case this may not be suitable for you at all.

Anyway I wrote 2 editors for my racing game. The first allowed the designer to layout the track as a series of lines perpendicular to the direction of the track. This was done in 2D from an overhead viewpoint. The lines formed the actual cross-sections of the track and each was placed x units infront of the previous. By allowing the line to pivot/rotate around its orign, provided a means to acheive curved track.

The second editor took this track data, where each section had an origin, forward normal, rotation etc, and presented it in 3D. You could advance step by step through each section, tweak the polygon crosssection of the track, add polygons to the side of the track, and raise or lower the track. Other functions allowed hills and valleys to be defined between x number of crosssections.

So the difficulty would be to convert you tracks into sections that are convex. Although that might take more effort than doing a 2D BSP tree, my gut feeling is sectional partitioning would be the fastest method, but with limitiations.

Hope this helps

Share this post


Link to post
Share on other sites
Thanks a lot noisecrime, this helps me a lot and I also feel less lonely :-)

Everything seems clear now, although I won't exactly use the same structure as you(as I don't have an editor creating polygones in sections), I need a way of partitionning a track that the graphic artist gives me(basically a 3D file).

What do you think of using a quadtree like this :
I store in each leaf the ordered faces that are contained in its BoundingBox(even partially, i won't clip them), then I compute a PVS. So for rendering I'll find the leaf I'm in, draw each faces in the order they have been defined, then I'll treat the also ordered PVS(ordered leaves). Each face drawn once will be tagged at each frame for avoiding redrawing.
Maybe splitting would be faster the trick(also I'm not convinced)?

For the buildings, imagine in a leaf I have three of them, they should need Z ordering most of the time, that is why I thought of it.

I also wondered something, do you compute for each polygone(a quad poly) of the road the point and vector for the camera, or would you do it for each leaf(a leaf might contain more than one face)?
I guess I should interpolate in real time the cameras position and coordinate as it is not possible to precompute each of its location and orientation.

And one Bonus : How did you make the car stick to the road? Did you have a simple physic engine(in the cases for jumps and all)?


Thanks a lot so far !

Cheers, Jeff.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this