|
Author Topic:   Precomputed Variance v.s. Deformable Terrain...
Bryan T
Member
posted December 21, 1999 10:49 AM            
What an excellent resource! It took me awhile but I've read most of this archive now. It's such a fascinating topic. I want to give a big 'Thanks' out to Seumas for his hard work and willingness to help.
Tread Marks looks downright fabulous, and after Christmas I'll tell you how much better it looks on a GeForce too...

I started an implementation of the ROAM paper as a side project. The simple part (thanks to this forum) was the split/merge work. However I hit a wall with the precomputed variances.
If I understand the original algorithm, this is the max difference in height between the three points in a triange at maximum detail, then averaged out over an implicit bin tree up to the root. Thus the root node contains the maximum height difference from the lowest point on the map to the highest.

That's great, but when I make a crater, the variance of the affected tris will change dramatically. Moreso with a nuke!
Are you ignoring this effect in TM, and just going with the original variance value of the map? Or are you using a different scheme?

Has any one else solved this problem?

Thanks!
--Bryan

IP:

LDA Seumas
unregistered
posted December 22, 1999 01:53 AM           
I'm glad this forum is helpful.

For variance, I don't think merely the min/max height of the triangle's vertices will do... What I store is the difference between the interpolated hypotenuse center height, and the sampled hypotenuse center height. The interpolated height is just the center of the line drawn between the two end points of the hypotenuse. The sampled hypotenuse center height is the height map value at that point when looking down from above. This difference roughly records how "wrong" the terrain will be if this particular triangle is left solid, and not split into two. The value stored for each triangle in the implicit tree is the maximum of the value for that tri, and the value for all its children. Thus a tri will never have a lower stored variance value than any of its children.

For dynamic terrain I simply re-calculate the affected block of the variance tree after the crater or mound is made. The process is quite quick, so even when a 100 meter wide nuke crater is made there is barely a detectable pause.

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

IP:

bdiscoe
Member
posted January 02, 2000 06:20 PM            
> The value stored for each triangle in
> the implicit tree is the maximum of the
> value for that tri, and the value for all
> its children.

Waitaminute.. the variance aren't stored with the triangles, they're stored with the vertices, right? The triangles only exist in a small pool, while the variances are precomputed and correspond to the vertices which will be removed when merging the triangles. So, what does "stored for each triangle" mean?

Thanks,
Ben

IP:

LDA Seumas
unregistered
posted January 03, 2000 04:42 AM           
It means stored for each triangle.

I store an Balanced Implicit Binary Tree, with one byte per node, for each root binary triangle on the map. Since the maps are 1024x1024 and when rendered are broken into 64x64 blocks, that means there are 512 root binary triangles (256 diamonds of 2) in the map, and thus 512 separate pre-computed variance trees. These trees store variance for binary triangles, and not vertices. They are also totally separate from the dynamic binary triangle trees which are created for the actual rendering. They correspond directly to the binary triangles created in the dynamic trees, though, so it is easy and quick to determine the variance of a triangle in the dynamic tree when deciding whether it should be split or not.

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

IP:

Bryan T
Member
posted January 03, 2000 10:09 AM            
Ben, I discovered an article just after my original post which cleared up both questions (yours and mine), written by our good friend Seumas M. http://www.gamedev.net/reference/programming/graphics3d/article806.asp

He's also written several other articles at GameDev.net, take a look-see.

(Props to Seumas, you rock)

On another note, I've finished my TreadMarks clone terrain engine (except for that new Z distance move... hehe, I was thinking about that one over the hollidays too).
I'm planning on writing an article, it would essentially collate everything that's presented in this forum on terrain implementations - with proper LDA props of course. Along with it would go my code (VC6 project & OpenGL).

--Bryan

IP:

LDA Seumas
unregistered
posted January 03, 2000 03:07 PM           
Bryan,

Actually, that GameDev.Net article is just a re-print of the Binary Triangle Tree article from my programming page on the LDA web site. The other articles there are probably re-prints of other articles here too, as I don't think I've written anything specifically for them yet. It is a great resource though.

As for a catch-all article, I'll be speaking at this year's Game Developers Conference about the Tread Marks engine, so over the next month I'll be writing a paper that will cover all the important implementation details in one place. I'll likely post it on the web once it's done, too.

Of course, I don't think I'll be releasing the Tread Marks source code too soon (give it a year, maybe), so your source code to a similar engine would probably be helpful to a lot of people.

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

IP: