|
Author Topic:   BinTri Memory Overhead
MikeC
Member
posted November 22, 1999 01:26 PM            
I was starting to implement a version of the BinTri land algorithm, and got to thinking about the memory overhead. I may be wrong, but the way I figure it.. in order to store information for a 1024x1024 terrain, you will need AT LEAST 20 megabytes of memory. The reason I say that is, you have 5 pointers in a node, left/right child, left/right neigbor, and a base neighbor. That is at least 20 bytes, not including the variance information. I think I could have figured the variance memory wrong, but basically I came up with 2 meg. The way I figured it was, 1024 * 1024 * 2 (2 tris per grid block). Altogether that seems like a LOT of memory.

The other algorithm that I implemented (I posted the code to earlier) would have taken at most 3 megabytes for the same 1024 x 1024 terrain. There is the 1 byte of height info, 1 byte of variance info and another 1 byte used to store a preframe process to flag tris to be drawn. I didn't store vertice information in this algorithm since I passed them on the stack.

Basically I just want to confirm that the BinTri method does indeed take this much memory. I really want to find out if there is a way to optimize this, which I am sure many have you may have already done.

thanks for you time.

Mike C

IP:

CheshireCat
Member
posted November 22, 1999 11:35 PM            
You do not not need to store the triangle connectivity information for the fully tesselated landscape. You only need to store the information for your current siplified mesh. 4000 or so triangles instead of 1024 * 1024 * 2.

CheshireCat

IP:

LDA Seumas
unregistered
posted November 23, 1999 02:41 AM           
Right. You generally start with 2 binary triangles connected as a Diamond which covers your entire height map (or a square patch of the height map), and then split them into more triangles from there.

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

IP:

MikeC
Member
posted November 23, 1999 08:08 PM            
What I was trying to determine when I was calculating this, was how much memory to allocate for my triangle pool. I don't want to malloc/free memory constantly, so I setup a triangle pool. I just wanted to make sure I didn't run out of tri's. So I now have one estimate of 4000 tris per frame, anyone else have an average? I guess even if I allocated 10,000 that would still be much better than 1 meg of tris.

Thanks,

Mike

IP:

LDA Seumas
unregistered
posted November 24, 1999 12:24 AM           
Tread Marks maxes out at 10,000 displayed triangles per frame, which means 20,000 binary triangle structures. I believe my pool of structures is 25,000 long to give a little breathing room.

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

IP:

Zoombapup
New Member
posted November 24, 1999 03:39 PM            
Hmm, is it really necassary to store the triangles neighbours? (I am kind of missing something, I can understand having pointers to the parent and the triangle which is shared with the hypoteneuse (so you can force split), but why the neighbours?

Its amazing how many people are playing with this stuff..

IP:

CheshireCat
Member
posted November 24, 1999 07:20 PM            
You need to keep all of the neighbor information so that you can figure out the base neighbors for the newly created triangles. The base neighbors for the new triangles will be the left and right neighbors of the parent.

CheshireCat

IP:

Zoombapup
New Member
posted November 25, 1999 06:55 AM            
I am just having a go with the bintree structure (well, why not )

I have a variance stored in a short array for 1024 levels down (basically its 1024^2 shorts (2097152 bytes). I just wondered if this seemed a reasonable level of detail for the variance info?

Also, has anyone tried bytes for variance? or ints?? (I settled on shorts because they give me quite a bit of leeway, but the resolution of the terrain might be such that bytes would suffice).

I like the bintree structure, it seems pretty elegant to my mind. (I have a natural aversion to complex data structures )

One thing I was wondering.. seamus was saying that he passes distance into the first pass through the bintree (for splitting purposes), i take it this distance is to weight the triangle for split operations? (i.e. modify the variance for that triangle with some frustrum/field of view/importance of some type?).

So is the distance the only error metric along with the variance?

Have you ever tried applying this type of structure to fractally generated (IFS) landscapes? We have some guys here working on some fractal world landscape generator stuff that would work VERY well with this implementation.

Phil.

IP:

LDA Seumas
unregistered
posted November 26, 1999 03:30 PM           
I use bytes for my variance info, since my vertical height map resolution is 25cm. Since the variance tree can get pretty big, I'd suggest using bytes anyway, perhaps with a non-linear scaling if you need larger dynamic range.

Right now the only two things that affect splitting in Tread Marks are the distance and the variance, though I would like to add a modifier for triangle normal too, to give less precedence to back and front facing tris and more to edge on tris.

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

IP:

Zoombapup
New Member
posted December 05, 1999 01:29 PM            
Yeah, using the latest demo of TM, and using wireframe, you can see that you really could do with some simple form of normal checking (lots of detail unused in the backfaces).

I am trying a byte based tree, to see if it will deform enough for my needs. How deep is your implicit tree btw? forgot that 1024 i talked about earlier, got some mad calculation wrong in my head )

I am just thinking how well this algorithm would port to a console (I have to take these things into account).

Cheers.

Phil.

IP:

Zoombapup
New Member
posted December 05, 1999 01:36 PM            
Thinking about more details to add for computing variance, it would be useful to use the slope of the face (in effect, rather than the normal, use the Z/Y slope of the face, that way you can heighten front faces, and less back faces. If you had some adjacency info, you could also check that the slopes are both negative/positive, and weight higher where there is a difference (i.e. when you split a tri, calculate the slop of the child faces and pass that through as well as distance).

Phil.

------------------
Programmer - Team17 Software Ltd. (Although probably not endorsed by them :))

IP:

LDA Seumas
unregistered
posted December 22, 1999 03:16 AM           
I believe my implicit variance tree is max-4 levels deep, so imagine the finest tessellation possible, then step back 4 levels from there.

Now that TM is in the can, I will be experimenting with Normal Maps and view-dependent Normal Map Lookup Tables to very quickly give higher priority to triangles with normals perpendicular to the view vector and lower priortities to tris with normals parallel to the view vector. I'll let you all know how it turns out.

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

IP:

bdiscoe
Member
posted January 02, 2000 06:38 PM            
> I believe my implicit variance tree is
> max-4 levels deep, so imagine the finest
> tessellation possible, then step back 4
> levels from there.

Seumas, could you explain this puzzling sentence? What kind of 'levels' are you talking about, levels of the triangle bintree or the node/vertex quadtree? For example, would a 9x9 grid mean a tree of 6 or 7 levels deep? If you stop 4 level before the bottom, then not every vertex has a corresponding variance value?

Confused and desperate,
Ben

IP:

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

By "level" I'm referring to levels of the balanced implicit binary trees which store triangle variance values as bytes. Since I don't work with odd-sized maps or patches, in my case it would be an 8x8 patch, and a binary triangle tree for one diagonal half of it would have a total of 7 levels to represent the patch to maximum tessellation, assuming the first triangle is called level 1. So in this contrived case my implicit variance tree would only go to level 4, since I just revisited the code and realized that I actually only don't bother with the lowest three levels in the implicit trees.

I don't store any quadtrees, or any vertex data structures. All vertex coordinates come through a combination of being passed down through the recursive functions, and for height, sampling into the height map.

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

IP:

Bryan T
Member
posted January 03, 2000 11:20 AM            
Well, you lost me again on this one. First some clarification. I'm using a 64x64 grid-point patch over the heightmap, this requires 6 levels of a variance tree (2^6 == 64). Thus the total size of the variance tree for a patch is: 2 trees * (1 + 2 + 4 + 8 + 16 + 32 + 64) == 254 bytes.
Is this the same for yours? (and now I note that is 7 levels, I'll have to check my code again..)
So to my questions; First was the "8x8 patch" a typo? Now Ben's question seems poignant, stopping 3 levels from the bottom is wasteful of variance data and seemingly bad for the tesselation. Are you still visiting the lowest levels of the tree, but at a higher level in the tesselation or are you truely ignoring them, for speed's sake?

--Bryan

IP:

LDA Seumas
unregistered
posted January 04, 2000 11:56 PM           
Bryan,

Your numbers sound right. I used the example of an 8x8 patch because Ben used the example of a 9x9 patch, and the closest thing in my engine would be an 8x8 patch. I don't ever use 8x8 patches, though.

And yes, I simply don't store the lowest 3 levels of the variance trees for speed's sake, or rather, for RAM's sake, as the trees would be rather large if full depth. It doesn't seem to cause much problem when tessellating; I use the last available variance value in the tree when deciding whether to split a near lowest level tri without a unique variance value, and in the tree I still compute down to the lowest level and store the maximum of the children, so the lowest level tris still affect the variance trees.

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

IP:

Bryan T
Member
posted January 05, 2000 11:27 AM            
I see... this actually answers another question I had about morphing. I've had to add an extreme amount of code to avoid cracks in the mesh during morphing. This is always a red flag in programming.

With your implementation, it would seem to smooth the transition since the last three levels of splitting will either ALL happen or not. Thus when morphing, you are nearly guaranteed to have neighbors at the same level of tesselation as yourself.

Oh, and a big thumbs up for performance on the GeForce. I had a crash when exiting TreadMarks, but there have been several other stability issues with the card too, I'll let you know if it persists. For reference it's the Creative GF256 DDR with v3.48 drivers.

--Bryan

IP: