Solved

Cracks in terrain when using LOD

Posted on 2008-10-04
8
757 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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
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

Secure Your Active Directory - April 20, 2017

Active Directory plays a critical role in your company’s IT infrastructure and keeping it secure in today’s hacker-infested world is a must.
Microsoft published 300+ pages of guidance, but who has the time, money, and resources to implement? Register now to find an easier way.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Flash video stream duplicate 5 354
Sudoku - eraseable white board 2 298
Any decent scenery blocks for my RTS 6 95
Any Fantasy Football Brute force AI suggestions? 2 81
Recently, in one of the tech-blogs I usually read, I saw a post about the best-selling video games through history. The first place in the list is for the classic, extremely addictive Tetris. Well, a long time ago, in a galaxy far far away, I was…
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.
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

749 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