Archived

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

chunked lod.. more about it

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

As simple as the theory is, I just can''t get it working in my application. I''m so frustrated that sometimes I want to give up on the program. But as always I come back to it, but I still can''t get it to work. I have everything working from the LOD algorithm to the patching of different levels. The part I''m stuck on is rendering it. I''m using a recursive solution because that''s what the paper suggested. But nothing I do seems to work! First off, it subdivides all the way down to the highest level of detail block everywhere- meaning the screen space error test is always failing until it just renders the highest level block available. Second, my framerate is dropping in the 20''s, when even rendering the terrain normally (without recursion and all the checking) on the highest level is detail gives between 40-50. I''m sure that Chunked LOD helps the framerate or it wouldn''t have caught the interest of people as it has! Something is just wrong in my code- which I will post when I get home in a little bit. I just really want to hear other people''s ideas or pseudocode for the rendering part. There''s not too much information on Chunked LOD yet. Another question I had is when calculating K in the equation [max_error/D * K]. I can''t get acrobat reader working on this computer (their new version seems to have a lot of bugs), so I can''t look up the exact equation of K right now, but when I looked at tulrich''s source code the K equation looked a little different than in his paper(like he didn''t multiply the denominator by 2). Can someone verify the equation of K? Thanks!

Share this post


Link to post
Share on other sites
Well, I can''t post my code yet actually because I''m rewriting a lot of my Terrain class for optimization and also to make a tree hierarchy of the patches. This will make the recursive drawing a lot simpler. Maybe it will work?
How many people use Chunked LOD? I''m really getting the impression that no one uses it because no one responds to posts like this. Not that I mind that much, I''m just starting to debate if it''s really worth my time.

Share this post


Link to post
Share on other sites
Hi,

Chunked LOD should work well for terrain so don''t give up on it yet. From reading your post I''d say there is going to be a bug or mistake somewhere in the code. I say this based on the fact that it appears you are always rendering the highest detail LOD.
I''ve not done Chunked LOD yet, (although I have made a chunk terrain engine) but I would look at the space error metric, possibly the value you have is too low, or the equation is inccorect.

However if that is not the case how about approaching this from a different angle. The aim at the moment I would say is to ensure that the chunk LOD is working, so replace your space error metric with a simple distance to chunk origin test. I.e for each visable chunk get the distance from the camera to the chunk. Then depedning on how many levels of LOD you have, set it so that the further away a chunk is the higher the LOD used (less polygons). This way at least it will show whether the LOD system is working. It should be an easy visual check with wireframe mode, further away chunks having less polys. Don''t bother trying to make this ''work'' or look good, its just the easiest way I can think of testing most of the chunk lod terrain to ensure that code is working.

If it doesn''t work, then you know the problem is somewhere in the LOD/patching/chunks. If it does work, then the problem should be within the screen base error metric code.

Don''t know if this will help. But at the moment it looks like you need to pin down where the problem is.

As to the vertue of Chunked LOD algorithm this post might be of interest if you''ve not seen it already
http://www.gamedev.net/community/forums/topic.asp?topic_id=156531

Share this post


Link to post
Share on other sites
I don''t know what you are doing wrong but chunked LOD should be faster than brute force in all cases (except when >90% of terrain is in view).

This will be a bit OT : There is one point that always botherd me in most QT based algoritems. They all need to recurse down to leaf level. What''s the point of that. GMM was created for the purpose to use less CPU & more GPU. But is it realy so? It sure is better then ROAM but in the end you are rendering a few nodes at full LOD (1000 tris/call) but there are a lot of calls (for nodes far away) that render only a few tris (<16). This is bad in 2 ways. First you need to recures down to the leafs [you don''t actualy need to use recursion] so you waste a lot of time just getting there then you render a node with 8 tris. Now that is just a waste of time. So in my engine I combined GMM and Adaptive QT. This works like a charm. All calls to render a node now have the same amount of tris. And recursion stops when node size on screen is under some treshold. For nodes near camera recursion goes all the way down to level 0 LOD while for nodes far away it goes only to level 4 or so. Combined with iterative tree tansvelsal it gives much better results than any of other algoritems I implemented from papers found on the net. And I''ve tried quite a lot .


You should never let your fears become the boundaries of your dreams.

Share this post


Link to post
Share on other sites
Darkwing: From what I understand from the Chunked lod paper, that''s exactly what it does. Thanks though..

Thanks for the reply noisecrime. I''ve tested the different levels to make sure they are ok but I guess I haven''t tested a simple distance LOD algorithm yet. I will do that as soon as I get home and post the results. I had seen that thread a little while back but I forgot about it, I''ll scan through it and see if has any information, thanks!

Share this post


Link to post
Share on other sites
Sorry for taking so long to do it, I'm writing a Perlin Noise tutorial that's starting to become more interesting (and less frustrating :D ).

Well, I did as you said noisecrime and tested the distance LOD. It worked, so I am sure that the error is in the screen space error metric code.

But I got it EXACTLY like it is off the Chunked LOD paper. This is my code:



void RenderNode(D3DXVECTOR3 view, int level, lodchunk* node) {

double screen_error;
if(level != 4) {
float x1 = node->midx - view.x;
float y1 = node->midy - view.y;
float z1 = node->midz - view.z;

double dist = sqrt(x1*x1 + y1*y1 + z1+z1);
dist -= XTerrain/LODController->GetSubFactor(level)/2.0f; //just kind of a spherical distance, this would be the radius


screen_error = node->maximum_geo_err/dist * k;
}
else
screen_error = 1.0;

if(screen_error < 2.0) {
LODController->RenderLodChunk(level, node);
}
else {
RenderNode(view, level+1, node->sib1);
RenderNode(view, level+1, node->sib2);
RenderNode(view, level+1, node->sib3);
RenderNode(view, level+1, node->sib4);
}
}


and k is set as :

double k = 1280/ (2*tan(D3DX_PI/3.0/2.0));

I actually used D3DX_PI/6.0 but that reflects the original equation better.


Any blatant errors?

[edited by - okonomiyaki on June 7, 2003 4:35:13 PM]

Share this post


Link to post
Share on other sites
Well I can''t see any obvious errors, but then i''ve never implemented this, and there are a few unknown varibles that make it difficult to know what values you should be getting.

I''ll state the obvious though. Its the code within the if(level != 4) statement that must be the cause of the problem. That is if as you say every cunk is rendered at the lowest LOD (highest poly). It means that the if statemnet is always making screen_error >= 2.0 forcing the recursion down until level == 4.

I would monitor the values produced within the if statement, simply dump them out to a log file, or even dry run through some values yourself since you should know the value of all the varibles. Double check that it works as expected.

Sorry I can''t be of more help.

BTW how did you test the LOD? I would hope that it was just some code to replace the RenderNode function code - just to ensure that running down to that handler worked.

Share this post


Link to post
Share on other sites
Yeah, I simply replaced some of the code in the RenderNode function to see if the distance was in a certain range, then render the appropriate level.
Yeah, my values are totally screwed up, but I don''t know why. I don''t know which equation is wrong. I wish someone would at least verify the equation of K. But thanks a lot for the help noisecrime! I appreciate the interest, and I''ll just keep debugging it. Thanks for the help though.

Share this post


Link to post
Share on other sites
Sorry i couldn't have been of more help, however i'm interested in this area becuase at some point i'd want to try implementing it. So i checked out the paper you mentioned in the original email and worked through some of the code.

I'm not sure but i'd question the second line of code below

double dist = sqrt(x1*x1 + y1*y1 + z1+z1);
dist -= XTerrain/LODController->GetSubFactor(level)/2.0f;

I can't see any reason for that line. In the paper 'dist' is calacualted as you have in the first line. So try ditching that second line.

Looking at it, the second line appears more like the calculation for the LOD geo-error per level. That is if the chunk has a master error metric of say 16 units, then higher levels of LOD should have half the error value - so level 1 = 16 level 2 = 8 etc. I would have thought these values would have been precalaculated and stored with each level of LOD for the chunk, but i guess they could be worked out dynamically. In which case your second line above the variable should note be 'dist' but a temporary variable level_geo_error. If so then this value should be used in

screen_error = level_geo_error/dist * k;


Definaiton of K
double k = 1280/ (2*tan(D3DX_PI/3.0/2.0));
in the paper it is
k = viewportwidth/2*tan(horizontal FOV/2.0)

So this means your FOV is 120 degrees - which to me is rather large, but there may be a good reason for it. Anyway it shouldn't be the cause of your problems.



[edited by - noisecrime on June 9, 2003 8:50:54 PM]

Share this post


Link to post
Share on other sites
o.k. Now i''ve been thinking about chunk LOD some more i''d like to ask how do you calcualte each chunks maximum geometric error?

Its something that doesn''t appear to be described in any detail in that paper, and I don''t remember it being discussed in any others.

I had almost asumed that perhaps you''d use the bounding box for a chunk comparing it against each LOD level. You''d be comparing the highest hieght of each LOD level to the maximum LOD (most polys) and using the difference as the error metric. But i''m not sure tat makes much sense.

Further more i''m confused by the paper as he say''s
''For simplicity''s sake, I assign the same E to all the meshes at a particular level in the chunk tree.''

where E = Maximum geometric error
This seams counter productive to me, as each child chunk could well have an error greater or less than an other.

Furthermore his equaition for calculating the error for specific LOD levels, is simply to divide the parent level by two, which again I would have assumed to be inaccruate.

Whether the inaccrucies of either these two points actually contribute to the performance of the algorithm i''m not sure.

Anyone care to explain?

Share this post


Link to post
Share on other sites
Oh thank you thank you thank you!!
I got it working! Your right, I was making some stupid mistakes that are now obvious.
First of all, when you reposted my distance formula, I noticed that I was only adding the z1 and not multiplying it! I didn''t see that at all before...
quote:

I can''t see any reason for that line. In the paper ''dist'' is calacualted as you have in the first line. So try ditching that second line.


I took the distance subtraction out (that second line) and it worked as well but I think it''s a little more accurate with it. What I was trying to do was do a kind of spherical distance check, imagining the chunk to be bounded by a sphere, not a box. I calculated the distance from the center, and then that value was the radius (half of the width of the box) and I subracted it. That''s just another calculation though, and I don''t think it makes that much of a difference if I change around my screen space error tolerance to the right measure.

quote:

Looking at it, the second line appears more like the calculation for the LOD geo-error per level. That is if the chunk has a master error metric of say 16 units, then higher levels of LOD should have half the error value - so level 1 = 16 level 2 = 8 etc. I would have thought these values would have been precalaculated and stored with each level of LOD for the chunk


quote:

how do you calcualte each chunks maximum geometric error?


You are right!!
You pointed out one of the biggest errors. I interpreted the paper wrong, and I thought I had to store the maximum geometric error of each chunk, but I can easily get it with just pow(2, 4-level). Even better, store it in a lookup table. Why would this make a difference? I should have even more accuracy about each chunk if I stored its own maximum geometric error. But there was a problem in the way that I got that. I got it when I did the vertex-LOD calculation of each level, I simply checked the current error against the current max, and if it was bigger, set the max to the current. My problem was that when it was at the first level (2 triangles for the whole terrain, least LOD) it would set the maximum geo error very high and then recurse lower and it would still be high. This was a HUGE error and is why it kept recursing down to the most polys- it kept thinking each chunk had a HUGE geo error. Thank you so much noisecrime, you really hit it on the head and made me rethink this part.

quote:

So this means your FOV is 120 degrees - which to me is rather large, but there may be a good reason for it. Anyway it shouldn''t be the cause of your problems.


I think you are mistaken though on my Horizontal FOV.. It would be D3DX_PI/3 which would only be 60 degrees (180/3), not 120, correct?

quote:

I had almost asumed that perhaps you''d use the bounding box for a chunk comparing it against each LOD level. You''d be comparing the highest hieght of each LOD level to the maximum LOD (most polys) and using the difference as the error metric. But i''m not sure tat makes much sense.


I see what you are saying. That would work, but I think it''s more work than it takes. I said before how I did it in the first place (although it had a bug, it could be fixed to work correctly). But I don''t think you get much inaccuracy if you just go ahead and set the maximum error to pow(2, max_level-level); It''s easy, simply, could be put into a lookup table and you don''t have to worry about each chunk as long as you have the level of detail of the chunk.

quote:

Further more i''m confused by the paper as he say''s
''For simplicity''s sake, I assign the same E to all the meshes at a particular level in the chunk tree.''

where E = Maximum geometric error
This seams counter productive to me, as each child chunk could well have an error greater or less than an other.


It''s just what I was talking about in the last paragraph- it''s easy and accurate it go ahead and set every chunk in level N to have the maximum error of pow(2, max_level-level). If it recurses to the child chunk, the level would go higher and have a less max error. Don''t think of it as a tree this time and just think of the 5 (or whatever) different levels as separate, subdividing by pow(2, level) and each chunk having a max error of pow(2, max_level-level).

quote:

Furthermore his equaition for calculating the error for specific LOD levels, is simply to divide the parent level by two, which again I would have assumed to be inaccruate.


I hope you are thinking of the vertex-LOD calculation and LOD-level subdividing as two different steps. We calculate the LOD of the terrain witha max of, say, 16 and space out the vertex as needed according to whatever algorithm. Then we store this in chunks, and subdivide pow(2, level) times. Do the same think with a max of 8, vertices would be calculated, and then the terrain would be evenly divided to one more extent than last time. The max error is calculated by pow(2, max_level-level) as I have said many times.
So you can see that each level WILL have a max error of it''s parent/2. It''s quite accurate, I''m finding that in the first step (vertex-LOD calculation) it rarely (if ever) calculates down to the highest vertices possible, meaning that the max_error is almost always reached in each chunk.


I think that I am getting it

Share this post


Link to post
Share on other sites
Glad I could help, even if it was indirectly

Looks like it was your maximum geometric error per chunk LOD level that was the main cause then. It being so high for all of them forced the highest LOD level to be rendered?

Its also amazing no matter how many times you check your own code that little typos like z+z instead of z*z can slip through. I guess in this case the dist equation is so simple and obvious it was never checked properly as to a quick glance it looks fine.

You mnetion several times that the chunk LOD max error is calaculated by pow(2, max_level-level). I''m rather suprised by this as i''d assumed it had to be related to some form of error between the hieght of the vertices between LOD chunks, or some for of actual unit/distance value. However as it appears you''ve now got it working I guess its right, just a little puzzled over why it has no relation to units or distances.

Anyway its going to be some time before I can get round to trying this for myself. I''d love to see a demo or screenshot (+wireframe) of your project in action.

Share this post


Link to post
Share on other sites
I could try to wrap it up in a small demo, I'll see if it's as easy as making a new project and using the class. I hope so. Should run fine on almost anything. (I couldn't put out my program right now, it is soo sloppy and unoptimized.)
If anything I'll post a couple screenshots. I may wait though until I also implement the out-of-core data loading because that's where this helps really good, because you can see so far! Right now it's just a 1024x1024 terrain. I've heard this works with up to 40k (I think it might have been that link you gave me in the second post).
I'm also still fine-tuning it to find the best screen error max. I'm a little confused because I thought that people usually used between 2 to 4, but I have to put it up to 6 or 8 to get anything good.
Also, I haven't implemented his solution for cracks or geomorphing yet, I will though.

quote:

Its also amazing no matter how many times you check your own code that little typos like z+z instead of z*z can slip through.


Yeah, seriously. Heh heh, thanks for making me read it again, I probably never would have seen it

And about the max error, if you think about it, you could calculate the real error of the spot with maximum error and such.. but it will always be pow(2, max_level-level) or very close because that's what you set the max error to be at that level when you did the vertex-LOD calculations. And this is just the geometric error, so it doesn't involve distance at all.

I will get stuff up about this, probably on my website, http://www.animeimaging.com. There's absolutely nothing there right now and I'm making a new design, but that's where I'll probably set up a Chunked LOD section. I'll email you when its up. If you have any questions also when you implement this, feel free to email me It doesn't seem like very many people are interested in this subject.

[edited by - okonomiyaki on June 10, 2003 10:31:12 AM]

Share this post


Link to post
Share on other sites
Would definitely be interested. From all the discussion it looks like Chunk-LOD is probably the best algorithm for rendering large scale terrain scenes. Eventually I''ll get round to writing some terrain rendering code, but should really finish the actual rendering core part of the project first. When I get time .

Share this post


Link to post
Share on other sites