Solved

Cracks in terrain when using LOD

Posted on 2008-10-04
8
756 Views
Last Modified: 2013-12-26
Hello,
when implementing any LOD algorithm on terrain, 'cracks' will often appear between parts where different level of detail is used. What is the best solution to it? Of course I mean not algorithm modifications, but some way to connect those parts.

Thanks in advance
0
Comment
Question by:Eriandus
  • 3
  • 2
  • 2
  • +1
8 Comments
 
LVL 13

Assisted Solution

by:Mark_FreeSoftware
Mark_FreeSoftware earned 100 total points
ID: 22641287
lets say you want a high detail hill, and the lower ground should be lower detail,
(see attached image)

black is the high detail terrain,
red is the low detail terrain, the green line is where you should cut your low detail terrain, and the dark blue line is where you should cut the high detail terrain.
the yellow circle is the important part, where both terrains intersect.
this way you have no gap between the high detail and low detail terrain.
example.JPG
0
 
LVL 3

Author Comment

by:Eriandus
ID: 22641620
Thank you Mark, but I don't really understand your answer. Do you mean that between those 2 LOD squares I should leave 1 unit empty space for those connections?

Umm, I'm rather looking for some algorithm or explanation of method how to connect triangles from 2 neighboor squares (each can be of different size and level of detail).
0
 
LVL 13

Expert Comment

by:Mark_FreeSoftware
ID: 22642034
i have edited the image, so it maybe shows better what i meant,

i removed the parts that should have been cut off according to my description,
the yellow part shows where the polygons intersect,
this way they dont show a gap, but they are not connectect!
(so it's only a visual thing)
example.JPG
0
Free Tool: Postgres Monitoring System

A PHP and Perl based system to collect and display usage statistics from PostgreSQL databases.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
LVL 11

Assisted Solution

by:jgordos
jgordos earned 50 total points
ID: 22642091
There's two things to do to help with this, and it's all in his algorithm above....

Basically, since the hi-res and the lo-res meshes are teh same surface, generally there's a spot in the mesh where the two meshes will intersect.. ie, they trade which is being rendered in Z order....

If you colored both meshes and redered them, you'd see it.

That's the spot where you want to switch the LOD.....

that single spot, though, will form an elipse of some sort around the camera

that's the spot all the way around.  

You can't use a simple "radius" because it needs to match the surface contour.

-john
0
 
LVL 3

Author Comment

by:Eriandus
ID: 22644476
Thank you for your answers. Still, I don't really get your method as it don't really describe the thing which I'm looking for.

I'm storing the terrain in something similiar to quad tree to apply quick frustum culling and the lowest levels of this tree are what I'm rendering. Each of this node have precalculated few level of details which I'm displaying depending on the distance from camera and few other things. What I'm looking for is some kind of algorithm to connect triangles between two squares (can be of different size) with different level od detail.

http://www.tar.hu/gamealgorithms/ch14lev1sec3.html
Check last image in above link (it's about geomipmapping) - generally it's what I'm looking for. The problem there is that it will still leave cracks in terrain and it doesn't really solve the problem.

I hope you understand what I'm talking about, as I'm a bit sleepy :)

Thanks in advance.
0
 
LVL 18

Accepted Solution

by:
JoseParrot earned 350 total points
ID: 22673852
Hi,
Seems a common problem with terrain LOD, where a lower level of detail isn't properly linked to a neighbor triangle.
Please note the red dots at (a). A triangle side lies in a side of the neighbor triangle. Each triangle vertice must lie in another triangle vertice.
Jose

LOD.GIF
0
 
LVL 18

Expert Comment

by:JoseParrot
ID: 22675818
Continuing...
The drawing LOD.GIF above shows a quadtree projection. In the 3D space, a red point can be either 2 points in different hights, then being cracks, or can be a single point, in this case being a T-junction.
Cracks render as holes, allowing the background to peak through.
T-junctions result in bleeding tears, due to small floating-point rounding differences.
To solve the crack, a common solution is to recursively split the triangles around the crack to produce a continuous surface. Of course, this solution creates new triangles, so canceling partially the triangle reduction obtained with LOD.
As you are looking for LOD, must take a look at the algorithms from Lindstrom (SOAR)
    http://www.cc.gatech.edu/~lindstro/papers/visualization2001a/
and Duchaineau (ROAM)
    http://www.cognigraph.com/ROAM_homepage/index.html
Please note, both provided source codes require OpenGL.
Jose
0
 
LVL 3

Author Closing Comment

by:Eriandus
ID: 31503011
Thank you ;)
0

Featured Post

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

What is RenderMan: RenderMan is a not any particular piece of software. RenderMan is an industry standard, defining set of rules that any rendering software should use, to be RenderMan-compliant. Pixar's RenderMan is a flagship implementation of …
Performance in games development is paramount: every microsecond counts to be able to do everything in less than 33ms (aiming at 16ms). C# foreach statement is one of the worst performance killers, and here I explain why.

809 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question