PDA

View Full Version : looking for an implementation of a TIN algorithm



robotech_er
03-12-2012, 12:07 AM
Hi,all. I am looking for an implementation of a TIN(Triangulated Irregular Network) algorithm, namely Smooth view-dependent level-of-detail control and its application to terrain rendering (http://research.microsoft.com/en-us/um/people/hoppe/proj/svdlod/), which seems to be very promising for terrain rendering.

I have found some TIN implementations, TinLib (http://jca3.freeshell.org/tinlib/tinlib.html) ,and, Triangulated Irregular Network 73 (http://www.ecse.rpi.edu/Homepages/wrf/pmwiki/Research/TriangulatedIrregularNetwork) .but neither is the specific algorithm i want.
Could any one please give me some links about this algorithm? Such as a open source library?

Thanks in advance! :D

Aleksandar
03-12-2012, 02:53 AM
I don't want to disappoint you, but TIN is a little bit deprecated approach. Take a look at the date of that paper.

robotech_er
03-12-2012, 04:51 AM
I don't want to disappoint you, but TIN is a little bit deprecated approach. Take a look at the date of that paper.

yes, it is kind of old. but can be used in the pre-process stage, where the terrain blocks can be simplified as much as possible to reduce the amount of vertices.

ZbuffeR
03-12-2012, 06:33 AM
View-dependant and pre-process do not mix well.

Dark Photon
03-12-2012, 06:53 AM
As with all run-time vs. pre-process, just depends on what you need to spend run-time cycles on, and what you can "cheat" on (and that all depends on your requirements). 3D graphics is all about cheats.

So, deprecated to some for some specific applications, but not for others. And just because something wasn't written this year doesn't make it obsolete. You need to objectively look at limitations/performance vs. alternatives.

Also, by precomputed TIN I didn't mean to imply a specific method for generating. Just was talking in general about pre-computed triangle meshes. To handle view dependent, you can LOD in and out of meshes with different densities, though whether you even need to, again, goes back to your needs and requirements.

Aleksandar
03-12-2012, 12:24 PM
In the early days of 3D graphics the number of rendered triangles was very important. Additional work on the CPU was necessary to minimize GPU burden and gain fluent frame-rate.

Nowadays the power of GPUs is at leas two orders of magnitude higher. We can easily fill full HD screen with pixel-size triangles and still have real-time rendering. Nowadays it is more important to efficiently feed those GPUs than to reduce the number of rendered primitives.

TINs have many disadvantages considering storage and manipulation. The most obvious are:
- complex data structures (compared to regular/semi-regular grids),
- requires all three coordinates for each vertex (instead of just one),
- complex real-time view-dependent LOD determination (requires traversing massive tri-trees on the CPU),
- complex view-frustum culling and collision detection.

And all previous assumes you have precomputed TIN. Generating TIN requires additional CPU computation resources.

thokra
03-12-2012, 04:31 PM
If you want TIN in any case for terrain rendering, check out Hoppe's paper:

http://research.microsoft.com/en-us/um/people/hoppe/proj/svdlod/

However, as all the guys above have already cleary stated, you shouldn't use TIN or any progressive mesh approach with better alternatives at hand - like geometry clipmaps, also proposed by Hoppe et al.

Edit: Just to clarify, I'm strictly talking terrain visualization here!

Dark Photon
03-13-2012, 04:39 AM
- complex data structures (compared to regular/semi-regular grids),
- requires all three coordinates for each vertex (instead of just one),
- complex real-time view-dependent LOD determination (requires traversing massive tri-trees on the CPU),
- complex view-frustum culling and collision detection.
Complex? Hardly.

Precomputed trimesh batches get memcpyed as-is into GPU DMA buffers and ripped via sequential access, and you only upload what you're going to render. With regular grid terrain? Hmmm....

Storing all 3 coords per vertex? Yes, but storing a ton fewer position samples than with regular grid terrain.

And what about dynamic view-dependent curvature-dependent LOD for regular grid terrain? Most like geometry clipmaps just hand-wave this and throw craploads of tris at the terrain (a few more up-close than further away), because that's all they're rendering. Again, depends on one's requirements, but I'd personally rather use the cycles and GPU memory on something else...

And there are cases in some domains where you need to inset pre-modeled ground features into your terrain skin. So we're talking dynamically cutting out and restitching the nice, simple, regular grid terrain mesh to these features to avoid T-junctions, and managing this properly as it moves away across concentric terrain LOD rings? I dunno, sounds like some complexity coming on here...

And suppose you're casting dynamic shadows in your scene, including from terrain. You have the similar issues as with skinning. Are we going to skin them 2-5 times? Or try to pre-skin a superfrustum via transform feedback to some space. Whereas with precomputed mesh, the memcpyed batches are still in the GPU ring buffer and you just rip them sequentially directly from GPU memory again.

And you still need those simple (or "complex", as you put it) culling and LOD techniques to handle paging and rendering of everything else in your scene that's "not" terrain. So why not just use it for the terrain too?

That said, regular grid terrain alone does have an appeal for doing unbounded LOD (if your app needs that). And if you can accept its limitations, it does have the benefit of avoiding pre-computing the tri mesh (which can be a key benefit for some projects).

So I think there are domains where each of these techniques are appropriate. Just have to look at your full set of requirements carefully to see what makes the most sense.

tonyo_au
03-13-2012, 06:32 PM
As Dark Photon says it is horses for courses. We use both TINs and regular grids. Some of our views require that we hold all the original vertices from the TIN, while others speed of render is more important.

robotech_er
03-14-2012, 02:19 AM
Much thanks for all of you, especially Dark Photon & Aleksandar ,I have learned much from your excellent comments.

One more thing confuses me. before jumping into the TINs which seems a little complex, i implemented two methods using semi-regular grids, a quad-tree method and the famous ROAM. the quad-tree i mention here is not the restricted quad-tree, which restricts the hierarchy difference of two adjacent nodes not over 1 to form a crack-free mesh. instead, I add new triangles to the quad node at higher hierarchy ( higher hierarchy means lower resolution ) to fix the cracks.

I amazingly find that the quad-tree method would generate 3 times more triangles than ROAM, of course with the same error parameter. Is this normal since I was told they are basically equivalent methods? I have checked the code Thoroughly, and many times.

Thanks.

thokra
03-14-2012, 04:34 AM
I amazingly find that the quad-tree method would generate 3 times more triangles than ROAM, of course with the same error parameter. Is this normal since I was told they are basically equivalent methods?

IIRC, the quad-tree approach generates whole regions or patches of some predetermined size as a preprocess and determines the acceptable resolution by evaluating some error metric. Correct?

If so, bare in mind that ROAM is a progressive meshing approach which dynamically adapts the triangle count per frame and thus can adapt the final resolution much better than fixes, precomputed levels of geometry. I assume your using geometry mipmapping because it uses the same error metric as ROAM, at least the variant proposed by de Boer.

What's most problematic about ROAM though is that in its native form, as proposed by Duchaineau et al., it's not easily portable from the CPU to the GPU - which isn't surprising since it wasn't designed as a GPU-based algortihm. Also both variants need preprocessing. But ROAM2 was to be mostly GPU sided and I'm sure there are GPU based variants of quad-tree terrain rendering algos.

Both problems are easily avoided by using geometry clipmaps. However, the triangle count isn't optimal since whole levels are equally fine-grained. Still, the very low CPU overhead makes up for that and it only becomes faster with faster hardware which lowers the transform costs and API calls. GCMs are realized with a single indexed vertex buffer and displaced in the vertex shader. Also it can store huge terrains compressed in video memory.

robotech_er
03-15-2012, 01:18 AM
IIRC, the quad-tree approach generates whole regions or patches of some predetermined size as a preprocess and determines the acceptable resolution by evaluating some error metric. Correct?

If so, bare in mind that ROAM is a progressive meshing approach which dynamically adapts the triangle count per frame and thus can adapt the final resolution much better than fixes, precomputed levels of geometry. I assume your using geometry mipmapping because it uses the same error metric as ROAM, at least the variant proposed by de Boer.

thanks, thokra, you are right. A quad-tree node can be triangulated in various methods, I just used the most native one, where one node needs up to 8 triangles.