Jump to content
  • Advertisement

Archived

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

okonomiyaki

chunked lod.. more about it

This topic is 5667 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
Advertisement
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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!