• Advertisement

Archived

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

Real Game Octrees?

This topic is 5035 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

Hi how do real games usually store octrees? does their editor arrange the vertices in a way that there is only a minimum of splits necessary? Are vertices automatically aligned on minimal-octant-size boundaries? Most samples i found just use a heightmap and generate "perfect" values out of it. I think that only very few to no fps games actually use heightmaps, because there cant be a cave or something in the terrain. So whats the best way of arranging arbitrary geometry into an octree? TIA

Share this post


Link to post
Share on other sites
Advertisement
Not exactly what you were asking, but Far Cry uses height maps and supports caves. I guess the terain is heightmapped and the caves are modeled into it or something.

And are you refering to using an octree with terrain rendering (I''m assuming this due to all those mentions of height maps and stuff)? Why not use quadtrees instead? And the you just divide your terrain into patches, which you stick into the qtree. You could easily use geometrical mip-mapping with it to care of LOD.

Share this post


Link to post
Share on other sites
Ive heard of farcry using heightmaps but noone really seems to know how exactly they did it. ( Does anyone here know any details of their technique? )

Yes iam referring to using an octree with terrain rendering mainly. But since my engine is supposed to support indoor stuff as well, quadtrees aren't really an alternative.

"And the you just divide your terrain into patches, which you stick into the qtree. You could easily use geometrical mip-mapping with it to care of LOD."
'How' do games usually divide it? Is the geometry arranged to be split up by the editor or does the engine just perform a brute force split upon the geometry?

[edited by - Dtag on May 9, 2004 7:01:45 AM]

Share this post


Link to post
Share on other sites
Why not use quadtrees for terrain and some other structure for internal rendering? I think that most of the engines out there use seperate ways of rendering outdoor and indoor areas.

How they split it? If you have a 1024x1024 terrain, just just split it up into 64x64 patches for example and the edge vertices of the patches align automatically.


Consider this 5x5 terrain:

x--x--x--x--x
| | | | |
x--x--x--x--x
| | | | |
x--x--x--x--x
| | | | |
x--x--x--x--x
| | | | |
x--x--x--x--x

You could split this into 4 3x3 terrain blocks:

x--x--x x--x--x
| | | | | |
x--x--x x--x--x
| | | | | |
x--x--x x--x--x

x--x--x x--x--x
| | | | | |
x--x--x x--x--x
| | | | | |
x--x--x x--x--x


And it would be very easy to stick all of this into a quadtree.

Share this post


Link to post
Share on other sites
Just place the polygons inside of higher level nodes in the tree.

Say you have node A, which contains node A1,A2,A3,and A4.
Polygon a,b,c, and d all fit into one of the 4 smaller nodes, but polygon e is too big, but it fits within the boundries of node A.

The problem this creates is, of course, the fact that a single large polygon can cause all 4 of those nodes to be rendered, which might have an adverse effect on performance.

The solution is clearly to split the polygon. That can be done when "compiling" the level (ala UnrealEd). This would give you 2 (or more) polygons that fit neatly within the smaller nodes.

Share this post


Link to post
Share on other sites
I basically know how its split.
"and the edge vertices of the patches align automatically." Who does this alignment? The editor?

Share this post


Link to post
Share on other sites
The terrain is generated on runtime from the heightmap. This is where a giant patch is created and then split into smaller chunks as I described above. If you do you terrain with quad patches, where X and Z vaules of vertices are on a fixed grid and only Y (height) varies, then you never have to split polys, beacuse you only split the patches at junctions (see above) and for example:

Let's use the code from above:

x--x--a--x--x This is "full" terrain - note the abcde vertices
| | | | |
x--x--b--x--x
| | | | |
x--x--c--d--e
| | | | |
x--x--x--x--x
| | | | |
x--x--x--x--x

You could split this into 4 3x3 terrain blocks - now observe the abcde vertices

x--x--a a--x--x What you would do, would create patches, which
| | | | | | have duplicate vertices on the edges (same as
x--x--b b--x--x neighbour patches)
| | | | | |
x--x--c c--d--e

x--x--c c--d--e
| | | | | |
x--x--x x--x--x
| | | | | |
x--x--x x--x--x



You should really check out this:
Clicky!

[edited by - klajntib on May 9, 2004 12:51:21 PM]

Share this post


Link to post
Share on other sites
"The terrain is generated on runtime from the heightmap"
This is exactly what i dont want to assume
Thx for the link ill check it out

So you think i should be going for heightmaps for now, and maybe extend it later for every kind of terrain?

Share this post


Link to post
Share on other sites
By looking at the Far cry editor (in wireframe mode), I noticed a few things :
- their terrain technology is geo-mipmapping
- For handling caves, you are able to cut holes in the terrain by telling some faces not to draw themselves.
- There seem to be some kind of occlusion culling performed through "hardware occlusion queries", what lead me to think that is because of the kind of lag with which the occluded objects are removed. This remind me of an article on the (excellent) book "GPU Gems" about occlusion culling

Try the far-cry''s sandbox editor, there''s plenty of reverse engineering to do with it.

Share this post


Link to post
Share on other sites

  • Advertisement