Still looking at LOD stuff

My attempt to foster a discussion in the general area didn't pan out, it would seem that LOD isn't much of an issue to many people.

Anyhow I have been digging into this, and the more I see the more I'm convinced that something isn't quite right.

de Boer's equations are presented without derivation, and I haven't seen anything like them in my literature search. Unfortunately this is a holiday weekend, so I can't visit a proper research library until next week. But I've checked all of his citations.

If we step backwards to Lindstrom's paper, we see screen-space error calculations with derived equations. I haven't sat down and walked through them, but I have a gut feeling they are correct (its been years since I've written projection code).

Fiddling with PLSM, I am leaning more towards the belief that there is little relationship between screen-space errors and the minimum distances before a LOD change occurs.

The terrain popping I have been seeing is not to be blamed on the source data. At worst case (if things were working properly) data with high deltas should be rendered at LOD 0 all the time, effectively turning off LOD. I have constructed small 2D meshes which I believe cannot be rendered at anything but LOD 0, as a means of gaining insight into this phenomenan.

So what could be the root cause of the popping (which only seems to bother me )? I think it comes down to the minimum distance calculations -- LOD is being changed too close to the camera. I have looked at this distance being calculated, and it is matching de Boer's calculations fairly well (except for "A" which is set to 1.0). So if the implementation is correct, then the root equations become suspect.

I would have expected that the maxPixelError would at some point be projected from the viewport to the nearest face of a renderable to determine the maximum delta an LOD would be allowed for that renderable. Then minLevelDist would be adjusted.

I do see "C" being recalculated on camera movement, and both "C" and the camera bias is used when comparing LOD distances. I assume camera bias is to account for non-horizontal camera orientation, which leads me to believe that "C" isn't getting the job done.

There are likely several logical wrong turns in the above, and I would appreciate seeing them pointed out. But one thing is certain, and that is that popping does occur with certain terrain data if LOD is used. (Setting maxPixelError to 1 effectively disables LOD as everything is rendered at LOD 0).

I'm toying with the idea of a different LOD algorithm based on some color quantization work I did years ago. It could likely yield an interesting paper, if nothing else. The things which are holding me back are:

1) understanding screen error calculations (I should probably just go with Lindstrom's equations rather than de Boer's unless someone can explain what de Boer is doing).

2) handling terrain deformation. Blowing things up to the point where LOD calculations are affected is not my cup of tea, but I respect that others are very interested in this. So would I be able to update LOD information on the fly in real-time?

Thanks for letting me ramble. I'd appreciate hearing from any interested parties.

I'm very interested in seeing the terrain system working as well as it possibly can.

Personally I have played with the different available variables exposed by the terrain system until the level of detail works fairly well, especially when vertex morphing is enabled. However, it took playing with a bunch of "magic numbers" in the terrain config that I generally have no idea what they actually do

As you can tell, I'm not the man to be contributing much to the terrain implementation, I kinda just use it and hope others are doing a great job with it.

I'm sure tuan kuranes will have some replies for you. There are a limited number of people who will be contributing to the core terrain rendering functionality and a larger number of people who are just interested in using the terrain system but have no idea what's actually going on in the depths of the terrain rendering code.

Clay

This whole LOD business is a distraction from my interest in terrain texturing, but a necessary one I think. I am further distracted by the need to trim my Christmas tree

If I'm going to experiment with a different LOD implementation (or if anyone else is for that matter), I think that it would be beneficial to abstract LOD into an object so one could conceivably have multiple LOD systems instantiated and switch between them at run-time (for comparison).

I think it also helps to clarify the interface between the LOD code and the rest of the system. At the moment, LOD stuff is scattered about a bit.

One thing I've learned is that the triangle list for a given renderable is recalculated and loaded to hardware on each frame. This may be necessary, I haven't had time to consider this fully. But it does smack of recalculating the same result too often. Although I note that the time to calculate the "skip N vertexes" style of LOD is minimal. Anyhow, given the frequency of LOD changes, it is tempting to be a bit free with memory and say that each renderable should keep its current triangle list around. Perhaps the need for reloading the card's vertex and index buffers is due to the possibility of having these buffers discarded during the previous frame?


OgreSceneManager::_render
PagingLandScapeRenderable::getRenderOperation
PagingLandScapeRenderable::getIndexData
PagingLandScapeIndexBufferManager::getIndexData
PagingLandScapeIndexBufferManager::generateTriListIndexes


Anyhow, if we abstract the LOD implementation, then the "de Boer" style LOD is free to recalculate its triangle list, and I am free to save mine.

Here is my first cut at an interface (in the Java sense):


// vertex and index data are paired
struct TriangleData
{
VertexData *vertexData;
IndexData *indexData;
};

class OgreLOD
{
public:
// returns a list of triangles suitable for rendering at current LOD
TriangleData *getVertexData (void);
TriangleData *getVertexData (int LOD);

// assign the highest LOD vertex data
// heightmap data is easiest to start with. Using PagingLandScapeData2D was considered,
// but lacks generality. This isn't much better, but the values can be easily obtained from
// the 2D data.

void loadVertexData (Real *HeightData, int x_size, int z_size);

// when a camera is moved, there is a chance for a LOD change on each visible renderable
// this is usually determined by measuring the distance from the camera to the renderable
// and deciding how much of a reduction in detail can be tolerated without visible changes.
// This method is free to recalculate a triangle list if it wishes.
void assignLOD (Camera *cam);

// an integer LOD value is a measure of how many triangles are removed from a renderable
// LOD 0 is full resolution, LOD 1 has approx half the triangles removed, LOD 2 is 3/4 etc
int getLOD (void);

// height requires interpolation between vertexes, and therefore depends on LOD to know
// which vertexes are being kept. Used mainly by ray intersection calculations.
Real getHeight (Real x, Real z);
}


The next step would be to take the existing LOD code, refactor it in the above form, and make sure everything works as well as it does currently.

At that point anyone interesting in poking at LOD would be able to subclass the LOD class (assume the above methods are virtual) and play around with the knowledge that a working LOD class was still available.

While I am in a rambling mood, the definition of success/quality should be explored, don't you think? Here is my ordered list.

1. No terrain popping!
2. No decrease in FPS
3. A significant decrease in rendered triangles/frame

Edit: added getLOD() for stitching

C isn't recalculated at cam movement.
Cameradistance to center of renderable is compared with the previously computed LOD distances.

1) mail author or post in gd-list on sourceforge (he is on it anyway.)
2) actually deformation update handle LOD.

Triangle list and Index list is loaded only when needed.
Vertex data is loaded once at start and when deformed (lod doesn't have any relation with it, that the whole point of indexed list uses here. ).

Index list are LOD and Stitch dependant (but data independant, that's why they are shared across renderables.


An abstract LOD implementation would be good thing, tough.

A good start would be to able to switch from Boer LOD to Center of cam circle of LOD (tile under cam = max Lod, nexttile= max lod -1, etc...)

For terrain popping, I would try to test distance to cam against "tile bounding box nearest point" isntead of tile center, and see if it doesn't help.
If you can send me a map particularly representative of the terrain popping problem you're facing, i'm not against.

I think you misunderstood what I was saying earlier.

C isn't recalculated at cam movement.

I'm not sure how I reached that conclusion. It is recalculated in updateSceneGraph, at one point I followed the chain backwards. I also had logging in the calculation code, and if I have time today I'll put that back in. If it is *not* recalculated on camera movement, then things are even worse since screen error is a function of camera location.


Cameradistance to center of renderable is compared with the previously computed LOD distances.


I'm not sure why you mention this. I see nothing in my post questioning this, and it is fairly obvious. Perhaps you can clarify your point.


1) mail author or post in gd-list on sourceforge (he is on it anyway.)

I mailed de Boer a week or so ago. I'm not sure what other author you are referring to. I was speaking in general (not specifically about his).

There is nothing to understand about de Boer's equations since he didn't derive them or explain them. Pretty much every other paper I've read on the subject does present derivations for their equations, and these are the ones deserving of study.


2) actually deformation update handle LOD.

If you reread what I wrote in the first post, I was referring to my own LOD algorithm. Since there is no implementation, there is nothing to "handle" LOD. The problem here is that deformation generates new deltas which must be handled in real-time, unlike non-deformable terrain. This bothered me for a day or so, but I think I can handle things.


Triangle list and Index list is loaded only when needed.
Vertex data is loaded once at start and when deformed (lod doesn't have any relation with it, that the whole point of indexed list uses here. ).

I have no idea what this is referring to. Taking a stab at the text in bold, LOD implementations typically remove vertexes, so deformation is going to have an impact on LOD. In general retriangulation is required, error values have changed.


Index list are LOD and Stitch dependant (but data independant, that's why they are shared across renderables.

Stitching is an artifact of the implementation. I don't have a problem with the current LOD's stitching, but there are LOD systems which don't use stitching.


A good start would be to able to switch from Boer LOD to Center of cam circle of LOD (tile under cam = max Lod, nexttile= max lod -1, etc...)
That doesn't do it for me. I'm hung up on screen space errors as the prime metric. Consider this case:

I have a data set with some large flat areas -- sea level around an island intended to have some nice ocean material applied at some point. Imagine one page of this data for a moment.

A 64x64 tile would have 4K vertexes at L0, for a renderable which could be reduced to two triangles with no screen error. So the center of cam would not be optimal.

(Sorry if I seem cranky here).

The de Boer approach is a variation of the "skip N vertexes" approach. The triangulations are quick to calculate, but are arbitrary. The error depends on where one starts skipping vertexes. Put a huge delta at vertex N+1 and the renderable's error goes arbitrarily high. If that same delta is at vertex N, the error is much less. A "skip N" system removes N vertexes arbitrarily, rather than selecting vertexes based on their contribution to screen error.

For terrain popping, I would try to test distance to cam against "tile bounding box nearest point" isntead of tile center, and see if it doesn't help.
If you can send me a map particularly representative of the terrain popping problem you're facing, i'm not against.

The problem isn't with distance calculation, so I'm certain that testing the near side vs the center isn't going to cure things. The screen error equations used are quite different from anything else I've seen in the literature.

I'll mail you a 4kx2k png and the corresponding .gen.cfg file. I think that would be useful for this discussion.

Note that one could avoid problems by modifying the heightmap, but I am concentrating on seeing PLSM do the best job it can on this arbitrary heightmap. And if a few rough edges are exposed, this is an opportunity to deal with them.

So I'm not looking to reduce the MaxPixelError or otherwise tweak variables so that this single heightmap renders well. I expect that when a screen-space error bound is provided that the LOD system will limit its popping this quantity.

reduced to two triangles with no screen error

sorry I was thinking that you goal was to modify current approaches, not adding a new one.

So you're after TIN terrains.

I tried that approach once without being able to avoid the pre-processing phase. The second problem was the runtime complexity of 'getheightat' queries to interpolate height at any point on the TIN mesh.

reduced to two triangles with no screen error

sorry I was thinking that you goal was to modify current approaches, not adding a new one.

So you're after TIN terrains.

I tried that approach once without being able to avoid the pre-processing phase. The second problem was the runtime complexity of 'getheightat' queries to interpolate height at any point on the TIN mesh.

Something along those lines, yes. I don't mind preprocessing, and consider the map-splitting to fall into that catagory. One performs this time-intensive step once and is done with it. The frequency which one adds new terrain to a project is probably much lower than the frequency in which it is used.

Approaches which use preprocessing are especially sensitive to deformation (thus my earlier concern). But not everyone needs to use deformable terrain. And LOD system which doesn't support deformation wouldn't be out of the question as long as an alternative was available.

TIN approaches were some of the earliest approaches used with LOD, before people gave up on them.

What I'm concentrating on isn't a TIN, but a regular grid like PLSM uses. My thought is to select which vertexes are removed at a given LOD rather than "skipping N".

The next step in evolution would be to perform more radical retriangulation, a TIN is likely required. I'm curious as to whether one can take an N-vertex mesh and represent it as a M-vertex (M<N) mesh by repositioning vertexes such to reduce the cumulative error. I recall color quantisation work years ago where one would plot color values in RGB space, and then create a set of elipsoids such that the cumulative error was minimized.

The results were shockingly good.

Ok. I see the thing. So it's a fast multi-resolution mesh approaches perhaps using curvatures, or even normals to select vertex to skip.

Best results I saw was from there.
http://graphics.cs.uiuc.edu/~garland/so ... scape.html
(check all the papers they made too.)

Thanks, its always good to see more papers on a subject.

I've been testing screen error formula using ray casting from the camera and projecting back to the camera. For some reason it only works if I treat the camera as a point on a sphere. Its likely to take me another day or so to reason this out, unless I just got lucky with some points (and the projection only works for that test).


Edit: nevermind, I figured it out. Since I was treating the distance on the reverse direction as a constant, it was forming a hemispherical cap on the end of the projection frustrum!

Calculating an error in screen space requires only a couple of divisions and multiplications, is an exact value, and easier to document than most of what I've read in the literature. If anyone is interested in the derivation I could provide it, once I locate where the movers left my scanner.

Edit 2: Grr, works on paper but not in code. Guess I'm going to need to hunt down the math error now.

Tuan, did you receive the files I sent to your free.fr address? I'm not expecting you to do anything with them right now, but would like to make sure you have them.