Another terrain question
Author
In a chunked LOD terrain system (using a quad-tree) what is the best way to determine the distance between viewer and terrain patch? Is it to calculate the distance between the viewport and the center of the patch? I'm not sure if this would be entirely correct for a particularly hilly terrain. Consider a terrain patch that has one corner very much higher than the opposite corner. The effective vertical center of this patch would be the average of the vertical extents. If you were stood in one corner (the high one) looking at the low one, the distance to the center could be a considerable amount even though you were actually stood on the patch - possibly enough to not increase the LOD level based on the error metric of the patch.
Is there a 'standard' way to determine the distance to a patch with regards to changing the LOD level? In my quadtree-based terrain, I have calculated the error metric per node per LOD level. The error metric is calculated in the standard way I believe - calculating the interpolated height between pairs of vertices of the current LOD and comparing it against the that interpolated vertex position in the next LOD - and storing the biggest difference per node. This seems to work fine.
At the moment, I'm just checking the distance to the center of the node and splitting the node if the error metric is too high - is this correct? Should I be checking the distance to corners instead?
Thanks in advance
Yes. Use the closest corner of the 3D bounding volume of the patch.
The goal of LOD selection is to limit the maximum screen-space error. You've pre-computed the maximum world-space error of each patch, and it stands to reason that world-space error will have the greatest impact on screen-space error at the point of the patch closest to the viewer. So, if you determine the shortest distance to the patch and project the patch's maximum world-space error to that distance, then you have determined an absolute upper bound on the screen-space error.
Of course this is complicated if the viewpoint is within the 3D volume of a patch. The "right" thing to do is to compute the shortest distance to the actual triangulated surface defined by that patch, but this is probably too expensive to be worth it. As an alternative you can assume that you'll always subdivide any patch whose bounding volume contains the viewpoint. The recursion terminates when either 1) the patches get so small that their bound no longer contains the viewpoint or 2) you hit a leaf.
The goal of LOD selection is to limit the maximum screen-space error. You've pre-computed the maximum world-space error of each patch, and it stands to reason that world-space error will have the greatest impact on screen-space error at the point of the patch closest to the viewer. So, if you determine the shortest distance to the patch and project the patch's maximum world-space error to that distance, then you have determined an absolute upper bound on the screen-space error.
Of course this is complicated if the viewpoint is within the 3D volume of a patch. The "right" thing to do is to compute the shortest distance to the actual triangulated surface defined by that patch, but this is probably too expensive to be worth it. As an alternative you can assume that you'll always subdivide any patch whose bounding volume contains the viewpoint. The recursion terminates when either 1) the patches get so small that their bound no longer contains the viewpoint or 2) you hit a leaf.
Author
Thanks Trurl.
I adjusted my terrain to use the minimum of a) the distance from viewer to nearest corner of the patch and b) the distance from the viewer to the center of the patch. This seems to work okay for distant terrain (i.e. areas with more 'dynamic' terrain appear in higher detail to those without), but when up very close to a patch in the terrain which should be split, it only gets split when I'm either very close to one of the corners or the center of the patch.
I can kind of understand this really - the error delta of a patch one LOD lower (less detail) than the max detail LOD level is probably not going to be a huge amount for an average patch of terrain. And as the distance to this patch (using the above method) becomes quite small, my calculation reduces the screen space error below the threshold which stops it from splitting. I think this is incorrect as I'd obviously like leaf patches with fair detail to be at the highest LOD level.
To check I'm storing my error deltas correctly, once the error delta for a particular node has been calculated, I then get the error metrics for each of its children nodes, take the highest out of those four and add that to the current node's error delta. This means that each node of the terrain patch tree should contain the highest delta between _its_ LOD level and its farthest descendants (i.e. all its leaf nodes). Is this correct?
So do I need to adjust my screen space error calculation in order to cater for when I'm getting closer to the leaf nodes? I did try the approach suggested by Trurl which is to check if the viewer position is within the bounds of the node, but that tends to make LOD detail appear 'drastically' when you enter a particular node. By this, I mean you could be looking at a fairly large patch (with a low LOD) and when you cross into its boundary, it splits along with the child quadrant at the point you entered and so on. You end up not seeing any detail, then almost all detail at the corner you entered the big patch. This won't work with my intention to include geomorphing.
My screen space error calculation seems to change hourly, but currently it is something along the lines of:
Where focalLength is set at 50.0f
Am I on the right track?
Thanks
I adjusted my terrain to use the minimum of a) the distance from viewer to nearest corner of the patch and b) the distance from the viewer to the center of the patch. This seems to work okay for distant terrain (i.e. areas with more 'dynamic' terrain appear in higher detail to those without), but when up very close to a patch in the terrain which should be split, it only gets split when I'm either very close to one of the corners or the center of the patch.
I can kind of understand this really - the error delta of a patch one LOD lower (less detail) than the max detail LOD level is probably not going to be a huge amount for an average patch of terrain. And as the distance to this patch (using the above method) becomes quite small, my calculation reduces the screen space error below the threshold which stops it from splitting. I think this is incorrect as I'd obviously like leaf patches with fair detail to be at the highest LOD level.
To check I'm storing my error deltas correctly, once the error delta for a particular node has been calculated, I then get the error metrics for each of its children nodes, take the highest out of those four and add that to the current node's error delta. This means that each node of the terrain patch tree should contain the highest delta between _its_ LOD level and its farthest descendants (i.e. all its leaf nodes). Is this correct?
So do I need to adjust my screen space error calculation in order to cater for when I'm getting closer to the leaf nodes? I did try the approach suggested by Trurl which is to check if the viewer position is within the bounds of the node, but that tends to make LOD detail appear 'drastically' when you enter a particular node. By this, I mean you could be looking at a fairly large patch (with a low LOD) and when you cross into its boundary, it splits along with the child quadrant at the point you entered and so on. You end up not seeing any detail, then almost all detail at the corner you entered the big patch. This won't work with my intention to include geomorphing.
My screen space error calculation seems to change hourly, but currently it is something along the lines of:
float scale = focalLength / (focalLength + distanceToPatch);float screenSpaceError = scale * errorDeltaOfPatch;If (screenSpaceError > visualErrorLimit){ split, etc..}else{ draw this node, etc…}Where focalLength is set at 50.0f
Am I on the right track?
Thanks
Quote:Original post by RobMaddison
I adjusted my terrain to use the minimum of a) the distance from viewer to nearest corner of the patch and b) the distance from the viewer to the center of the patch. This seems to work okay for distant terrain (i.e. areas with more 'dynamic' terrain appear in higher detail to those without), but when up very close to a patch in the terrain which should be split, it only gets split when I'm either very close to one of the corners or the center of the patch.
Yeah I can see that, and after posting I realized that I omitted a significant consideration: the closest point on the patch bounding volume might not fall upon a corner. It might instead lie along an edge or in the middle of a face.
Quote:
To check I'm storing my error deltas correctly, once the error delta for a particular node has been calculated, I then get the error metrics for each of its children nodes, take the highest out of those four and add that to the current node's error delta. This means that each node of the terrain patch tree should contain the highest delta between _its_ LOD level and its farthest descendants (i.e. all its leaf nodes). Is this correct?
The maximum error of a given patch can be computed in total isolation, given only the base height map as reference. I can see that computing parent error as some function of child errors might give a performance optimization (and there might even be something in the literature on this, IDK) but it kinda scares me. I don't think it's necessary to enforce the invariant that error increases monotonically up the tree, since it should happen naturally.
Quote:
So do I need to adjust my screen space error calculation in order to cater for when I'm getting closer to the leaf nodes? I did try the approach suggested by Trurl which is to check if the viewer position is within the bounds of the node, but that tends to make LOD detail appear 'drastically' when you enter a particular node. By this, I mean you could be looking at a fairly large patch (with a low LOD) and when you cross into its boundary, it splits along with the child quadrant at the point you entered and so on. You end up not seeing any detail, then almost all detail at the corner you entered the big patch. This won't work with my intention to include geomorphing.
The correct solution (whatever it may be) will work at all LODs regardless of depth. Are you enforcing the constraint that adjacent patches be within one LOD of one another?
Author
Quote:
Yeah I can see that, and after posting I realized that I omitted a significant consideration: the closest point on the patch bounding volume might not fall upon a corner. It might instead lie along an edge or in the middle of a face.
I don't think using corners or other parts of the patch will work (with my current screen space error calcs). There will always be a spot on the patch that isn't catered for which will produce a very low screen space error (lower than the threshold) and stop the patch splitting. One way round this might be to simply use the 3d center of the patch and multiply the patch's error delta by a fairly small distance factor before using it in the screen space calculation. That way, the closer you get, the bigger the error delta will get - I'll have to try this later and check the results.
Quote:
The maximum error of a given patch can be computed in total isolation, given only the base height map as reference. I can see that computing parent error as some function of child errors might give a performance optimization (and there might even be something in the literature on this, IDK) but it kinda scares me. I don't think it's necessary to enforce the invariant that error increases monotonically up the tree, since it should happen naturally.
I think you're probably right. In my previous code, I only checked the highest detail vertex interpolated exactly halfway between the two vertices being sampled in the current node as opposed to all of them. I can't really get my head around whether or not this is right. Correct me if I'm wrong, but a patch's error delta should be the height difference between interpolated vertices in the current node & child nodes, not the height between the current node and the highest LOD level (i.e. checking every single unit heightmap value against the interpolated height between two vertices of any particular node).
Quote:
The correct solution (whatever it may be) will work at all LODs regardless of depth. Are you enforcing the constraint that adjacent patches be within one LOD of one another?
I assumed that would be the case - I guess it's just finding that solution... I'm not enforcing that constraint, no. I hadn't thought of doing that. I guess you'd need to introduce some kind of LOD precedence. i.e. if you have a high detail patch next to a low detail patch (with at least 2 LOD levels difference), the low detail patch would increase a level?
I'm sorry I don't have time to read the entire thread, falling asleep here. Just thought I'd mention that personally I find the closest of the centre points of the planes that make up the bounding box. This seems to work quite well for distance culling and LOD decisions.
There should be a way to get the MinX, MaxX etc of the bounding box which returns the centre point of the planes involved.
There should be a way to get the MinX, MaxX etc of the bounding box which returns the centre point of the planes involved.
In reality, the only thing you're really worrying about is how much screen space area a given triangle occupies. If it starts moving closer to sub-pixel sized, then you'll want to destroy it for larger polygons, and visa-versa.
So, with that, one other alternative to consider:
On HALO WARS, we would take the AABB of a given patch of verticies, and project it into screen space, and then construct an AABB from those points in screen space. The resulting rectangle easily gives us screenspace area of the given patch of terrain data.
This worked a million times better than a distance based solution, because hilly terrain patches that occupied more vertical space, would be projected to screen space, occupying more screen area, and thus requiring a better resolution.
In constrast, patches which were more flat, and aligned with the XZ plane would project to smaller areas of screen space, and thus would require a lower resolution.
The difference here is that you're no longer concerned with arbitrary depth from the camera, but more concerned about the given fill-rate of a group of polygons. (which is where your big performance problems start showing up)
~Main
Author
Thanks for everyone's replies so far.
Colt, without immediately writing back with 'how do you do that?' - I spent some time trying to think about this concept and whilst I can see its merits, I have a couple of questions if you don't mind.
1) You have the screen-space AABB (which is, as you say, essentially just a screen rectangle) from any given terrain patch. If you're looking at a fairly flat peice of terrain but from higher up (imagine you're at the top of a building looking down at the flatish ground), because of perspective, won't the screen space rectangle of near patches be rather big even though the terrain is essentially flat? This may cause unnecessary splitting to higher detail levels?
2) How would you decide on which LOD level to display? If a node in the distance takes up too much vertical screen space, you'd split that node until each node takes up a heigh less than the threshold?
Thanks
Quote:On HALO WARS, we would take the AABB of a given patch of verticies, and project it into screen space, and then construct an AABB from those points in screen space. The resulting rectangle easily gives us screenspace area of the given patch of terrain data.
Colt, without immediately writing back with 'how do you do that?' - I spent some time trying to think about this concept and whilst I can see its merits, I have a couple of questions if you don't mind.
1) You have the screen-space AABB (which is, as you say, essentially just a screen rectangle) from any given terrain patch. If you're looking at a fairly flat peice of terrain but from higher up (imagine you're at the top of a building looking down at the flatish ground), because of perspective, won't the screen space rectangle of near patches be rather big even though the terrain is essentially flat? This may cause unnecessary splitting to higher detail levels?
2) How would you decide on which LOD level to display? If a node in the distance takes up too much vertical screen space, you'd split that node until each node takes up a heigh less than the threshold?
Thanks
Quote:Original post by Trurl
Yes. Use the closest corner of the 3D bounding volume of the patch.
Unfortunately, distance-to-closest-corner is wrong. The distance-to-box for LOD selection, as I use it, is the minimum of:
- If you are outside the box
- distance to nearest quad (not plane!) (named d_p hereafter)
- If you are inside the box
- 0
Look at that example:
|B | A a----------b - - - -| || || C || |+----------+- From that example, it should be clear that, if you use the distance-to-nearest-corner, for observer A, you get a wrong guess if you use d=|A-a| for distance measure. Say the box has a width of 40 meters. Observer A could could be standing just a millimeter away of the "box-wall", where you would choose high levelof-detail, but still it's distance-to-nearest-corner could roughly be 20 meters, and you could choose a lower LOD.
- Clearly, choosing the nearest plane for observer B would be false (in the example, it would be some centimeters of the right place). Instead, you are really interested in the distance to the nearest quad, which would be both of the upper right planes. The distance to both would be equivalent to the distance d=|B-b|, or the distance-to-nearest-corner. This could be seen as an optimisation (a canonical one).
- For C, all you are interested in is highest detail, hence we obviously choose d=0.
Distance-to-nearest-corner is a wrong misconception (but from my experience a very common one; I fell into it myself), but general distance-to-nearest-quad can be expensive. But in case of axis aligned bounding quads or boxes, it is easy to detect the correct of the above cases in a way so that no fancy plane-vs.-vector math is required (start with something like "const bool inside_x = vector.x>=box.min.x && vector.x<=box.max.x", or the non-branching version with logical or; the rest will be ovious)
Quote:
1) You have the screen-space AABB (which is, as you say, essentially just a screen rectangle) from any given terrain patch. If you're looking at a fairly flat peice of terrain but from higher up (imagine you're at the top of a building looking down at the flatish ground), because of perspective, won't the screen space rectangle of near patches be rather big even though the terrain is essentially flat? This may cause unnecessary splitting to higher detail levels?
It sounds like you're mixing two concepts :
Firstly is the concept of screen space area being correlated to the amount of density you want a given patch to contain. Effectively, you can plug the screen space area of a patch into a quantized lookup table to derive the amount of density you want for that patch. Screen space area is a much better heuristic for tessellation than relative distance from the camera.
Secondly is the concept of worldspace displacement amount being tied into the amount of tessellation that a given patch requires.Knowing the amount of displacement a patch has allows you to put an upper limit on tessellation.
So in your example, if you standing on a tall building, looking down at large patches of flat terrain, you have some issues with perspective and tessellation.
If the terrain is mainly 'flat-ish' then it's max tessellation should never get above X amount of tessellation. (IE if it never needs more than 2 polygons to represent it, then why ever tessellate it higher?)
The 2nd question here is the size of a given patch / chunk of terrain. If your patch sizes are large enough that standing on a building, looking down, that a single patch fills the entire screen, then you may have other issues with performance from not splitting up that chunk into smaller sections so that you can effectively cull it when your camera is closer to it.
So if you've sub-divided your terrain enough, and you have a patch that occupies 50% of your screen, chances are that patch is very important, and should be highly tessellated.
Quote:
2) How would you decide on which LOD level to display? If a node in the distance takes up too much vertical screen space, you'd split that node until each node takes up a heigh less than the threshold?
We used a set of quantized values to represent discrete tessellation states, and would then interpolate between them to smoothly transform between set LODs.
Shamefully I'll admit that the process of determining these quantized states was done very trial-and-error with unicorn-dust and elf-magic ;)
Hope that helps.
~Main
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
