This topic is 2 pages long:   1  2  |
Author Topic:   Quicker bintri tree rendering?
JohnMancine
Member
posted October 16, 1999 01:26 PM            
I was trying to think of a way to speed up the process of rendering my terrain using
the bintri method. Right now, i have to make two walks through the tree... one for
tessellation and one for rendering. All my rendering loop does is recursively
walk the entire tree and render the leaf nodes. (ie. renders whatever the tessellation
routine decides is in view etc.)

Wouldn't it be possible to get rid of the 2nd rendering tree walk, and simply have a
'render bin' of sorts that is built when tessellating? When you tessellate the bintris ..
basically when you are about to leave the function (ie. no more splits needed etc. so you
you know this tri will be rendered.) couldn't you through the tri into a render bin? Then,
just cycle through this bin and render all the tris.

I'm not sure if this would be faster then walking the tree... but I just thought i'd
mention it. I'm sure someone (read: Seumas) has already considered this and isn't doing
it for a very good reason that I'm not aware of. =]

So is walking the tree and rendering the leafs quicker then just storing them in a bin
and rendering that? Am I missing something? =]

Thanks,
John

IP:

LDA Seumas
unregistered
posted October 16, 1999 10:16 PM           
The problem is that while you're splitting the trees, you can never be completely sure that a binary triangle is split as much as it will be split, and is renderable. A chain of forced splits from a location quite a ways away (or right next door) could cause a seemingly "finalized" binary triangle to be split again. It's this interlocking property of binary triangle trees that makes them so easy to avoid cracks with, but it also means, as far as I can tell, that you always need two passes.

Besides that, if you could "finalize" binary triangles during the split pass, you probably wouldn't need a separate render bin, and could just render them as they were finalized. A render bin would also require storing triangle coordinates, and in my algorithm coordinates are never stored, but passed through the stack during the recursion.

Now, being able to "finalize" binary triangles during the split pass is an interesting idea... Perhaps if the variance tree was constructed with forced-splits in mind, so that variance values were artificially boosted for tris neighboring on very variant tris, then you could fairly safely finalize a binary triangle after splitting it as much as its local variance required, since the local variance would already take neighbor forced splits into account. To be extra sure you could set a "finalized" flag in the tri, and if a forced split attempted to split a finalized (and thus already rendered) tri, the splits would be backed out of and the originating split skipped.

One down side I can see is that if a highly variant piece of terrain was barely outside of the frustum, the terrain that was in the frustum would see no advantage, and would still be over-split due to the boosting of variance values stored in the variance tree.

------------------
-- Seumas McNally, Lead Programmer, Longbow Digital Arts

IP:

JohnMancine
Member
posted October 17, 1999 07:52 AM            
"You've bested me yet again..." =]
I hadn't thought about all the forced splits that are occuring. Oops.
Thanks for clearing that up. Looks like I'll be sticking with 2 passes as it seems the simplest and most effcient way.

--John

IP:

Oiler
Member
posted October 21, 1999 02:57 PM            
If your using the split-merge method (rather than split-only method) you just have to render you split queue....thats how I do it as it always contains the leaves. Just make sure to render only those in the view frustum is all which should be a simple flag check.

Oiler

IP:

Mr. Moody
New Member
posted October 26, 1999 12:56 AM            
Would you elaborate as to how to perform a "simple flag check" in to determine visibility? How would you implement this?

------------------
Your mouse has moved, please reboot your Windows machine now.

IP:

bdiscoe
Member
posted November 12, 1999 07:59 AM            
In my implementation, i actually need *three* passes:

1. walk tree, determine render state
2. walk tree again, put each triangle into one of many render bins, corresponding to which texture map it will require
3. render the bins, switching texture context only once per bin

One advantage of having this state separate is that you don't have to determine render state every frame.. with a good framerate (eg. >15) you can do it once every few frames, and just render from the existing bins on the other frames... much faster, but potentially slightly jumpy.

-Ben http://www.washedashore.com/Terrain/

IP:

LDA Seumas
unregistered
posted November 13, 1999 06:38 AM           
If you throw all your triangles into bins, doesn't that mean that you have to store the coordinates of the three vertices with each triangle in the bins, taking more space and limiting vertex sharing possibilities? Or is there some way to bin the triangles without storing all that extra state?

I don't store any coordinates in my binary triangle structures, and pass down coordinates on the stack as I descend the tree. I also have one texture per two root binary triangle trees, with no overlap, so sorting by state changes happens automatically.

------------------
-- Seumas McNally, Lead Programmer, Longbow Digital Arts

IP:

bdiscoe
Member
posted November 15, 1999 03:45 AM            
Actually, the bins contain only the indices of the vertices (3 ints), not the coordinates. You're right, though, that it does take up space (in a re-used memory pool) and gets in the way of vertex sharing.

However, i haven't found any other way to have more than one texture map for the terrain. For a 4K*4K textured surface, it takes a 4*4 array of 1K*1K textures. Using bins is the only way i've found to do it.

Binary trees would probably help, because a face's children are known to be contained in their parent's area. That's not true of LK vertex quadrees.

-Ben

IP:

LDA Seumas
unregistered
posted November 24, 1999 12:37 AM           
Ben,

Couldn't you use 16 separate quadtrees, each one exactly matching one of the 1kx1k textures, and each one connected at the edges to the other ones such that there are no cracks (or however cracks are fixed in that style of terrain algorithm)?

------------------
-- Seumas McNally, Lead Programmer, Longbow Digital Arts

IP:

bdiscoe
Member
posted January 02, 2000 07:51 PM            
Seumas wrote:
> Couldn't you use 16 separate quadtrees, each
> one exactly matching one of the 1kx1k textures?

I wish! As you can see from how a binary triangle tree looks, there is no clear way to isolate a subset of the tree that corresponds to a 1/16 quad area of the terrain. If anyone has an idea how to do this, i'd be *extremely* interested. Somebody's going to have to do this eventually, since users are going to start expecting terrain larger than the single-texture-size limit (1K on most cards).

-Ben http://vterrain.org/

IP:

LDA Seumas
unregistered
posted January 03, 2000 05:26 AM           
Ben,

I'm not quite sure what you mean... I don't know Quadtrees, but with Binary Triangle Trees all you need to do is have multiple root trees, and connect them together through their neighbor pointers before you start doing any splitting. This is what I do in Tread Marks, as I break the terrain up into 64x64 sample (which is also 64x64 meters) blocks which each correspond to one 64x64 texel texture downloaded to the graphics card, and two root binary triangle trees in a diamond shape.

The Tread Marks engine is currently built for relatively small terrains (1024x1024 right now) with matching edges to allow infinite tiling, but I don't see anything that would prevent upgrading the engine to support stupidly large non-tiling terrains with blocks dynamically paged in and out from disk as required.

The stickiest detail would be modifying the height map sampling functions to work with huge dynamically paged block based terrain; right now they are very fast, using a simple bitwise AND and shifts to acquire the address of the appropriate height sample within the linear 1024x1024 height field array (though I know, this probably has bad cache effects even now). I would probably need some sort of coarse array or hash table of table of block pointers, to first find the block of height data containing the x/y point requested, and then the sample itself from within that block. If done right this could actually be faster than the way I'm currently doing things by virtue of cache-friendliness.

Stupidly huge paged terrains is something I'm seriously considering for our next terrain based game. Although perhaps just moderately large block paged terrains that would still tile at the distant edges would be better for the style of game I currently have in mind.

Also, the above approach should work with frame-coherent binary triangle based engines as well, with the additional complication of having to "mesh" any newly created blocks with their neighbor blocks that already exist and have working binary triangle trees. This would require (in one jump) splitting the new block to a level such that its edges exactly match the edges of its neighbors, followed by fixing up all the neighbor pointers of bordering binary triangle structures to be correct. Due to the way my engine is structured, this procedure would have been required anyway if I had seriously tried implementing a frame-coherent engine such as ROAM describes. This complication was one of my reasons for sticking with a non-coherent algorithm and getting on with the game, as it were.

------------------
-- Seumas McNally, Lead Programmer, Longbow Digital Arts

IP:

Bryan T
Member
posted January 03, 2000 11:55 AM            
Seumas,

Ahhh, my favorite topic! "Stupidly Huge Terrains"! This was the whole reason for working on a terrain engine in the first place. Software-voxel engines are just too slow.

Here's what I've been working on; Think of an infinite landscape stored across multiple servers. Players are spawened at a spawn point near 0,0 of the world. As they move out from this point, an algorithm is run to find each new 'patch'. These patches are small fractal data fragments ~512 bits (not bytes).

Each patch is 'floating' in space, separated from the other patches by a short space (4 units?). This buffer space allows simple interpolation between the edge of one patch to another, thus no need for the edges to match (this after much thought of how to get fractal edges to match up - that kind of math makes me sick). Additional noise can be added to the interpolation to give more 'texture' to the transition - texture in heightmap terms, not colors.

For each patch, there is no need to store the data unless a change has been made. Thus an infinite landscape can be stored in remarkably few bytes of memory (just a seed for a RNG). When the landscape changes, the function which delivers a patch notes that that patch coordinate is 'differenced' from the fractal algorithm. Now when someone requests that patch, the differenced version is given instead.

Some interesting artifacts of this method are that the landscape must be smooth (due to the lossy compression of the fractal), and when a change is made to the patch, it is not localized to the heightmap entrys, it get's 'smoothed' into the terrain - sometimes in undesirable ways. Overall, however, this is what I'm working towards.

Now throw an adventure game on top of this and some multiplayer action and you got the gist of it.

--Bryan

IP:

LDA Seumas
unregistered
posted January 05, 2000 04:41 AM           
Bryan,

I've thought about the same possibility. The main downside is that you lose the artistic touch that a real person can put into a designed terrain, or the realistic touch that using real world height data will provide. It may be possible to mix fractal and artist designed, perhaps using the same framework for differencing as would be used for storing terrain modifications.

As for spaces and interpolation between blocks, I don't see why this would be necessary. It should be possible to use a fractal that is continuously smooth over the entire near-infinite range of space you'd want the terrain to cover, and just sample it for a specific block down to a specific resolution when you need to create and cache a block coming into view. Perlin Noise or a similar function would work well for this, as it has essentially infinite range, and remains smooth. You can also make it as unsmooth as you like by strengthening the finer Octaves in the noise, and it can be evaluated with an explicit-style algorithm to create an entire block of noise faster than with the usual implicit single-sample style function.

What could be really interesting would be to use a few different algorithms, and to blend them together based on yet another algorithm (such as a low-octave, fast to compute Perlin Noise, where 0 means use all of Algo A, and 1 means use all of Algo B, for a specific height sample).

------------------
-- Seumas McNally, Lead Programmer, Longbow Digital Arts

IP:

Bryan T
Member
posted January 05, 2000 01:19 PM            
Well, I can't say much for my artistic talent, so I've had to use other means to get nice landscapes. *sigh* As for real height data, I had planned on extracting coefficients from patches of real world terrain to give seeds to different patches of the fractal landscape.

Also I was trying to minimize the use of heightmaps (the actual full arrays). Since the order of magnitude I'm looking for is much too high for today's memory. I'd really like to render the distant mountains and valleys before you get to them.

The problem I run into with a full fractal landscape is the differencing, it still has to be broken into patches and if you don't store the full heightmap for a differenced patch, there will stil be obvious artifacts along the patch borders. Smaller terrains would not have this problem since they can store the entire differenced heightmap on one harddrive. For my project, this would be impossible.

I have tried the blending you mention, it works well on a large scale (certain patches are more mountainous, while others are just hilly, etc). I've not yet tried it at the micro-level that you are suggesting.

As an asside, I've been discussing the game idea itself on http://www.gamasutra.com in their forum for multiplayer gaming (Connection->Programming->Multiplayer Online Games). I invite anyone interested in such topics to join us, some of the ideas recently have been enlightening.

--Bryan

IP:

LDA Seumas
unregistered
posted January 07, 2000 08:22 AM           
Ah, so you're intending to only evaluate the fractal when you actually need to determine a height sample? In that case you will want a fairly simple and quick to evaluate fractal... Though I think the RAM issue when caching fractal terrain could be solved by essentially mip-mapping each patch/block, and thus only calculating a very low-resolution version of the patch at a distance, and calculating continually higher resolution versions as the patch gets closer and your engine tessellates it more deeply. This caching would save having to continually re-evaluate the fractal, and would let you use a much more complex combination of fractals.

I'm still not sure why there would have to be a problem with the borders between neighboring patches... If the Difference Maps (for terrain modification) are stored at a low resolution, obviously they will have to be bilinearly filtered (in software) when height samples are required at a higher resolution than the difference map provides, and this should be able to seamlessly blend over patch borders as well (though the more I think about it, the trickier it might be, but this is where caching multi-resolution versions of the height data could come in handy again). For hard drive storage, it should also be easy to compress difference maps (either with ZLIB, or plain RLE), so that only the small portion of terrain actually modified by something will be saved, and with ZLIB, possibly compressed even more still.

------------------
-- Seumas McNally, Lead Programmer, Longbow Digital Arts

IP:

Bryan T
Member
posted January 07, 2000 01:18 PM            
A quick view of the detail I'm looking for might exemplify the problem. Tread Marks maps are 1 m resolution 1024x1024 ~= 1 Meg of HD space uncompressed. The engine I'm examining would use 64x64 patches with each unit representing 16 cm. That's roughly the size of a standard step on a staircase.

To fill out the same area as one Tread Marks map with this detail, the full height field array would be 41 Meg. And that's just the beginning, the world is (nearly) infinite in dimention, you should be able to pick a random direction and walk for hours. There is no harddrive today that can hold this amount of data. Compression is good, but not that good. (and there's still the color map data to store! ugh..)

Thus the need for an algorithmic method (fractal landscapes). The differences database would end up bieng billionths of the size of the full height field for the world. But storing the full height field for all differenced patches (in a long-term persistant game) would become a burden.

The memory concerns for RAM are very real; the actual number of patches that are in memory would be 41 times the number of patches in Tread Marks to get the resolution I'm looking for. (not exactly true, you would need fewer as the distance increased, but it's still a significant difference)

This is why I chose the separated, on-the-fly generation of patches to allow for filtering between the patches & avoid the cracking problem. I agree it's a hack but it would work, and it's simple. This gives me the freedom to use a fractal function that does not have to be smooth over the infinite range and can be optimized for on-the-fly binary operations. Also a full differenced patch weighs only 64 bytes (with the current method, though I'm sure it'll change as time goes on), that's plenty small enough.

Artistry is not dead either, a game designer can simply mark a patch as differenced and supply their own 64 bytes that specify the patch they want.

Thanks for the discussion BTW, this is helpful.
--Bryan

IP:

Bryan T
Member
posted January 07, 2000 01:30 PM            
Doh! That's what I get for writing messages in the background.. didn't even get to the questions.

I like the idea of mip-mapping, and had not considered it for the case of a smooth fractal. Wouldn't the total overhead of the number of patches become a problem still? You are keeping all possible viewable patches in memory no? - but only tesselating the ones in the frustrum?

Also I think I'm missing your insight on avoiding mesh cracks with differences.. So you would generate a height field to a certain resolution, then apply the (now uncompressed) difference to it? Then from there tesselate? Can you imagine a method that would not require generating the height field?

--Bryan

IP:

LDA Seumas
unregistered
posted January 09, 2000 08:31 AM           
Bryan,

I see, you're working with a much higher resolution. Roughly 6x6 = 36 samples per square meter, where I use 1 sample. In that case 64x64 patches seem rather too small to me, as eatch patch is only about 10x10 meters. Patches the size of 128x128 or 256x256 would make better use of texture state changes (which can hurt), especially if you want to be able to view a kilometer or more into the distance. Also realize that you will have trouble tessellating to a lower density than your patch size, so 10x10 meter triangles way off in the distance could start to be a little smaller than optimal, especially on slower systems.

I'm still not sure I follow "storing the full height field for all differenced patches". When you store a difference map, it should compress very small if there is little change. If someone builds a 1 meter by 1 meter sand castle, the difference map stored on hard drive should compress to around 20 bytes, I'd guess, and that's with full-resolution differencing (from reading below, I recall you're actually planning low-res differencing anyway).

As for memory, with mip-mapping of the terrain detail your RAM requirements should drop off hugely with distance. You will only need the highest density patches at very close ranges, as with 16x16 cm samples you will very quickly come near 1 pixel polygons at the highest tessellation, and I find terrain triangles never need to get below about 8x8 pixels to still look excellent.

Are you sure it's that much of an advantage to use a fractal algorithm that is not smooth over its full range? I mean, you seem to be saying that it's going to be just a _little_ bit un-smooth at the patch borders, and I'm having a hard time envisioning an algorithm that would work like that... The two most likely possibilities I see are a totally smooth algorithm that just works, or a totally disjoint algorithm where each patch is totally different and borders will need huge and ugly elevation changes to fix up continuity.

If your field of view is 90 degrees, keeping all possibly visible patches cached is only 4x the ram, and again with mip-mapping and view-dependent tessellation, I think the ram requirement would end up being very low.

Yes, I don't see why you couldn't use difference maps along with implicit (when a sample point is needed) evaluation of the fractal, if that's what you're asking. Just add the difference map (if low res, then bilinearly filtered) for that point after evaluating the fractal for that point. If there is a difference map for a neighboring patch, it shouldn't be too hard to have the bilinear filtering for that edge of samples filter using the corresponding edge on the neighboring patch's difference map to keep the difference map transition perfectly smooth. Since it'll be less likely that an edge of a patch will be differenced as it will be that an area in the center will be differenced, you could store 4 edge flags saying whether the edge has any difference values other than 0, and if the edge or the neighbor's edge has no differences, just ignore that edge and bilinearly filter off-edge difference samples as if they were 0.

------------------
-- Seumas McNally, Lead Programmer, Longbow Digital Arts

IP:

Aelith
New Member
posted April 28, 2000 08:19 AM            
Wow Bryan - its encouraging to see that someone else is trying what I am trying!

I have been working on a real-time fractal terrain engine for a little while now. I use quadtrees, and in the begining I used two queues: one for merges and one for splits. (Now I use just a single queue) I started with a very simple error metric that estimates the projected screen area of a quadtree patch by treating it as if it was oriented perfectly to face the viewer. The error terms are just simply the size of the patch divided by the square of its distance to the viewer, measured from its center. I am still working on better priority determination that incorporates how far a patch is from the center of the screen, how much it is moving relative to the center of the screen, and its surface roughness.

Each quadtree node contains a regular grid of vertices (often 4x4, 6x6, etc), a height field (floating point) and another floating point texture used to generate color.

When I split a quadtree node, I generate new textures procedurally by simply adding in the next frequency levels to the interpolated parent texture. So a half-sized region of the parent texture is blown up (using a biquadratic filter), and then I add in the frequencies for this level of detail (which in the case of your basic fractal is simply properly scaled noise).

Note this corresponds to a general quadtree approach for adaptive uncompression of wavelet encoding images - so even though I only use it now for terrain, it could be used for any type of texture. Hand generated detail could be added on top in this way. Or even better, the lowest frequencies (the highest level quadtree nodes in the tree) could be pre-determined and loaded from disk, with the additional detail (frequency levels) represented by deeper quadtree nodes being generated by fractals. (I haven't seen a reason to do this yet, but probably will in the near future)

The inherent frame coherence of a prioritized, que based scheme means that we can split just a few nodes each frame (amazingly enough, my prototype always just performs one merge and one split per frame), and thus we don't have to spend much time evaluating fractals - because we only evaluate one frequency level at a time.

I then generate lightmaps on the fly from the heightmaps and send them to the card (which is also possible because I am only downloadin 1 or a few small maps per frame).

The bitch problems were handling edges, both for vertices (the familiar problem) and for textures (because I use biquadric interpolation). I handle texture edges by having overlapping texture borders that are synchronized on splits (works beautifully) and I handle mesh edges similarilly by sycrhonized vertices across edges on splits. (works fine)

The big problems with the original system were
1.) the geometry LOD was horrendous because it was limited by the texture LOD - which was only fast enough to split one node per frame. The solution (without resorting to bintrees which are geometry processor incompatible) is to have seperate quadtrees for geometry and textures and thus allow the geometry quadtrees to run ahead.
2.) the texture LOD was too slow - unoptimized surface shaders and texture functions are too blame - KNI optimization will allow a 10x speedup so this isn't a big concern
3.) memory concerns - I use up all the video cards' avail tex mem for the final unique textures, and this requires even more system memory. I allievated this with a hack at first (I actually iterate 2 generations of the fractal in each split and through away the 2nd iteration after shading) - thus cutting mem reqs in fourth. Now I am treating this as a more general texture/lighting optimization problem.
4.) caching - obviosly it would help to cache nodes after I generate them for improved effeciency

Nevertheless its comin along quite well. Here is what it looks like:
http://www.astralfx.com/users/ccs/screenshots.html

IP:

Achilles
New Member
posted April 28, 2000 10:55 AM            
Are terrain rendering systems based on bintrees faster than those based around quadtrees? Any other pros/cons of one versus the other?

IP:

Aelith
New Member
posted April 29, 2000 01:51 AM            
Bintrees in general allow more accurate LOD - ie less vertices and thus triangles for the same quality mesh.

The disadvantage of bintrees is speed - since each bintree node is a triangle, they require computation per triangle - thus allowing less triangles. This can be overcome with enough low level optimization.

The major disadvantage of the bintree method is that they can't take advantage of geometry acceleration. Its hard to do that in general with any LOD scheme, but quadtrees are much better suited to hardware rendering.

-Jake

IP:

Bryan T
Member
posted April 29, 2000 06:43 PM            
Aelith,

Amazing! Beautiful! Stupendous! It's everything I've been dreaming of... Who do I make the check out to?

Really though, it looks like you've been implementing the system I've been thinking about all this time. Very nicely done. Some questions:

Frame rate? (on what system/card)

What is KNI optimization?

Can you adapt the fractal algorithm over an area on the fly? (one area is mountainous, while another is smooth)

How much of the frame time is spent generating the dynamic textures vs the terrain mesh?

What is the maximum speed the eye can move/rotate before outrunning your frame coherent splitting?

Oh, and welcome to the discussion
--Bryan

IP:

Aelith
New Member
posted April 30, 2000 02:53 AM            
Well thanks Bryan

I sometimes wish I would have done it earlier. I planned it out and started it last spring, but quit before I got anywhere and didn't come back to it until the beginning of this year. I still don't think anyone else is doing this yet, but they will be soon. (Ken Musgrave, for one, will try with www.fractalworlds.com)

Frame Rate - I posted some stats for that prototype:
The images above were all rendered on a P2 300mhz machine with 64 megs of main memory and a 32meg TNT2 - in less than 50ms (21.2 fps minimum with 27.4fps average).

The Frame Rate for the prototype was determined almost exclusively by the triangle count, which is determined soley by the patch limit * the number of triangles per patch. I think that I was using 4x4=16 vertices, which is 18 triangles, per patch for those screenshots.

The framerate minimum is basically the amount of time taken to merge one patch, split a patch, and then render a fully visible set of patches (which is around 1,000 for that prototype). So in the worst case it was rendering about 18,000 triangles per frame, and that takes roughly half the CPU time, and splitting takes roughly the other half (although merging, visibility, and priority que heapification, also take a few milliseconds each). But it can take less time if the tree is fully optimized, because then it doesn't split or merge. The worst case is when it is almost fully optimized but not quite, because then the number of visibile patches is just a little under the max.

KNI(Katmai New Instructions), also known as MMX2, are the 128-bit vector floating point instruction extensions for PIII's.

With KNI assembly, I could normalize 4 vectors in around 10 clock cycles, instead of around 320. I also could easily multiply 4 color pixels by the shading results in a clock cycle, and those optimizations combined with fast fp->int could realize a 10X improvement in the surface shader. (which takes almost 250 clocks per texel right now)

"Can you adapt the fractal algorithm over an area on the fly? "

I don't know what you mean by this. Right now there is one block of terrain generator code that iterates the next height map texture. It actually switches between two equations, one for the sand and one for the rocks. Both are my own somewhat screwy implementation of multifractals that I arrived at by pure experiementation. (which is probably the most fun part of the whole thing)

Nothing at all is stored or loaded from disk - in fact, the random number seed is determined by the timer - so the terrain is totally different each time you run it. In fact, since I don't have any determinsitic method of generating a seed or my own noise, the noise is different each time it regenerates the same patch, so the terrain is actually changing as you move around.

You never notice this randomization because the lower frequency levels that determine the general shape of the terrain change infrequently. But anyway, at some point I will make it consistent.

"How much of the frame time is spent generating the dynamic textures vs the terrain mesh?"

When a split takes place (which doesn't happen when its priority is less than the next merge - ie when the tree is optimized), it takes a massive 25 milliseconds or so. It makes 4 64x64 textures, and spends about 3.5 ms per texture iterating the final level and doing shading, 0.5 ms uploading to the card, and a few more ms generating lower levels and other stuff (it spends about a ms calling new a couple of times - which will change).

"What is the maximum speed the eye can move/rotate before outrunning your frame coherent splitting?"

Camera motion really isn't much of a problem unless the camera is moving really fast relative to its height above the terrain, but even in that case the problem is solveable simply through a more intelligent LOD equation that takes motion into account
and predicts ahead. Regardless, camera rotation is the real problem.

Hmm... let me do a little math:
with a 60 degree view fustrum, there are about 6 full screens in a 360 degree sphere as we pan all the way around horizontally. So we can calculate the rotational speed at which you could maintain a certain texture resolution given a texture generation rate.

assuming that 80 textures can be generated per second (1 split = 4 textures * 20fps),
then

#textures max rotation
1000 4.8 deg/s
600 8 deg/s
400 12 deg/s
200 24 deg/s
100 48 deg/s
50 96 deg/s
25 192 deg/s
13 360 deg/s

Needless to say, rotation doesn't work very well with such low texture genreation rates. However, its not quite as bad as it seems at first, because what happens when you start quickly spinning around in a circle is that all the textures just get distributed evenly around the sphere by the time you go around once or twice - it spreads out all the detail across the full viewing sphere. And in addition, it never allocates all the textures to just one screen, because 25% of all the textures are always stored in parent nodes - so there is always a base detail everywhere that you build on. Also - the faster objects move, the less detail they need - which is fortunate.

A more important metric is the time taken to build the full texture tree from scratch. Right now at 80 textures/sec, it can take about 12 seconds to build the full tree at max resolution.

If I could do 10 splits per frame or 40 textures per frame, then it would take just a little over a second to build the full tree at max resolution - thats my goal.

If I got a 10x speedup on the texture rate, by moving to a PIII and using KNI, then it would be just about perfect. Texture download is still a problem, but I am betting it will take at least half the time it takes now. When I get to the point when texture generation takes less time than uploading the texture, then caching won't even be necessary as it won't help much.

1000 textures is alot, it is about 4 million texels, and thus can cover every pixel 4 times (texture/lighting supersampling) even at 1024x768 (assuming no overdraw). There are of course diminishing returns, it still looks good at 300 textures.

-Jake

IP:

Bryan T
Member
posted April 30, 2000 01:59 PM            
Aelith,

Realizing that I didn't have the expertise to discuss your algorithm, I've brushed up on QuadTrees and wrote a modified Rottger implementation. Now, let me see if I can dig a little deeper here...

From what I gather in your description, you are not using the QuadTree structure to store vertex information, but rather patches of landscape. This differs significantly from the Linstrom/Rottger algorithms.

So, the initial landscape is a 4x4 patch sampled from the fractal algorithm. Applied to this is a square texture (also 4x4? or two levels deeper 16x16?).

You then determine if this is too coarse and cut it into 4 vertex patches, each another 4x4 set of verticies based on the parent level but with another frequency level added from the fractal. Are you able to use all the parent verticies in the child nodes, or do some get thrown out?

You mentioned that the nodes also contain a floating point height field (I'm assuming this is a 4x4 array of floats to match the 4x4 array of verticies?). And the floating point texture for color (again, is that a 4x4 array of floats?).

Then there's the texture QuadTree. I don't recall it bieng mentioned specificly, but I assume each node holds the square texture and perhaps some other data. When a node is split, you enlarge each quadrant to be full size (16x16?) and add two levels of frequency to it. Then, based on the heightfield in the vertex QuadTree, it is lit and shaded.

Thus, rendering becomes a combination of sending the Texture node and the Vertex node information to the graphics pipeline in tandem.

Did I get that right?
Do you support GeoMorphing?
How much overlap do you leave for your textures to avoid seams?
Avoiding mesh cracks: you say you do this on splits, but how do you tell which node to sync with?

Thanks for the input. Have you started on a rewrite of it (non-prototype)?
--Bryan

IP:

Aelith
New Member
posted May 02, 2000 07:54 AM            
"From what I gather in your description, you are not using the QuadTree structure to store vertex information, but rather patches of landscape. This differs significantly from the Linstrom/Rottger algorithms."

Yes and no. I store a couple textures in each node of the quadtree and a regulard grid. The Lindstrom paper I am referring to is his original attempt : "Level of Detail Management for Real-Time Rendering of Phototextured Terrain". That is a somewhat similar approach in that he stores a small regular grid in each quadtree node. (from the pictures in the paper, it shows a grid of 2x2 vertices or just 2 triangles per node). My grid size is variable, so I can play with the tradeoff between more accurate LOD (smaller grids down to 2x2 minimum) vs higher polygon counts (bigger grids). Lindstrom stores one texture chunk in each node, I store a couple - one of which is the height map itself. The regular grid is sampled *from* the height map - so the mesh is a byproduct of the fractal generation which is really only concerned with the height map (because the light map generated from it after shading gives the appearance of all the fine detail).

So this isn't a vertex midpoint displacement scheme, its really more along the lines of Musgrave's height field based fractal terrain for ray-tracing (that is its inspiration, after all) - the stuff used in Bryce. The main difference is that I use a biquadtratic filter at each step and thus my basis function is biquadratic. I experiemented with bilinear early on and discarded it quickly - it looks unrealistically jagged. The ray-tracers usually use a bicubic - I may try that at some point but biquadratic seems to work fine for now.

I started by using textures of dimension 66x66 in each node (for the height map). There is a two pixel border on each side and they overlap. Thus each texture is actually 4 pixels wider and taller than it should be, and so pixels 0,1 in one texture(its border) are the same as pixel 62,63 of its left neighbor, and pixels 2,3 are the same as pixels 65,66 of its left neighbor. Thats the simplest way I could think of to handle the required extra pixels needed for interpolation. Then the lightmap is actually 64x64, cuz it needs a little space to calculate derivatives from the height map and so it shaves off one pixel of border on each side, and finally, the hardware needs to do bilinear filtering, so the actual vertex texture coordinates are carefully scaled to only use the 62x62 pixel region within that lightmap -ie, I again shave off the remainting one pixel of border on each side, and the result corresponds to the pixels ranging from 2-63 in the original height map.

When I split a node, I examine the depth of my neighbor along each edge. If the neighbor's depth is equal to mine, then I simply copy its edge vertices into mine. If my neighbor has unequal depth, then I interpolate vertices from the neighbor of greater depth into the neighbor of lesser depth. This also works for merges. I never change the tesselation - I just force the vertices into the correct position. This problem was being solved way back when people started doing adaptive tesselation for bicubic patches, and it seems like everyone resolves over and over. (it can be tricky)

Slight cracks sometimes appear on corners - this scheme isn't perfect yet. Corner vertices are a tad more difficult cuz they depend on 4 nodes.

I implemented geomorphing (poorly) at one point, but it ****ed up the edge handling completely. I am adding it again using a better technique. I also have to do texture morphing in my case.

The rewrite is well underway, I am debugging alot of it now. Its a nice OO design now, it cleanly seperates textures from geometry (they have their own quadtrees now), its more general - ie it will be easily extensible to work with general surfaces, etc. Its the basis of the VISION engine I am working, which is this big ambitious cyberspace research project I just got started.


IP:

This topic is 2 pages long:   1  2