Mesh Compression for 3D Graphics

IanDanforth writes "A new algorithm that uses successive approximations of detailed models to get significant compression has been revealed by researchers at The University of Southern California. Just as MP3s remove high frequencies we can't hear, this algorithm removes the extra triangles in flat or near flat surfaces that we can't see. Experts in the field are giving this work high praise and imply that is will be immediately applicable to 3D modeling in games, movies, CAD and more."

Comments

MP3 compression == complicated

[Raindance]

I think this is interesting, but the analogy drawn between MP3s and this 3d-object compression is a bit strained.

The MP3 compression routine revolves around 'frequency masking' much more than it does "remov[ing] high frequencies we can't hear". Most of the work in MP3 is done through 'frequency masking'. That is, imagine a graph of the frequencies being played at any given time- find the high points, then draw sloping lines down to either side of those points. Humans can't hear anything under those lines- they're 'masked' by the nearby strong frequency.

Nothing very much like that goes on in this algorithm. There might be some other mesh-compression-analogous process that goes on in MP3 that's like this, but that ain't it.

Sorry to nitpick, but I figured it's important that
1. MP3 compression is not just simply throwing out high frequencies (a lot of these are actually retained) and
2. This isn't anything analogous to that, anyway.

Looking over my post, I'd have been fine if the submitter had said "Just as MP3s remove frequencies we can't hear, this algorithm removes..." but that's not very descriptive anyway.

RD

Re:This has been around for many years.

[MrBigInThePants]

You both should try reading the article:

Computer scientists have struggled with the problem of finding an optimal mix of large and small elements for years. In 1998, theoreticians proved that the problem was "NP hard" that no general solution exists that can be solved by a computer in finite length of time. They did find work-arounds: fast methods to simplify meshes, which were unable to guarantee accuracy, and accurate techniques, which were too slow.

The Desbrun teams novel approach comes from the seemingly unrelated field of machine learning using a technique invented in 1959 called Lloyd Clustering named after its inventor Stuart Lloyd. Desbruns algorithm uses it to automatically segment an object into a group of non-overlapping connected regions an instant draft alternative to the too-numerous triangles of the original scan.

If you actually read it, it would be pretty obvious why this is new...sheesh!

Also, game data is built of far fewer triangles and in a much easier form than raw data read from a real-life source. (such as a laser range finder)LOD mesh reduction is usually done by full or partial MANUAL selection.

No.

[autopr0n]

This isn't about compressing the data required to store a mesh, although it will help.

This is about reducing the complexity of meshes so that they can render faster.

This isn't new?

[grammar fascist]

Un-disclaimer: I'm currently pursuing a PhD in machine learning.

Yes, it is new. First of all, y'all need to read the article and find out how.

It is for two reasons, both of which are stated:

The Desbrun team's novel approach comes from the seemingly unrelated field of machine learning...

Machine learning: getting a computer to generalize (invent hypotheses) given data instances. Work in machine learning has proven that generalization and compression are equivalent. That someone has applied those ideas to 3D model compression is at least notable.

We believe this approach to geometry approximation offers both solid foundations and unprecedented results...

In other words, it's not using some hacked-up heuristics. The bias behind the generalizations it makes are solidly described, and can be tuned. Machine learning consistently beats heuristics in accuracy, so their expectation of "unprecedented results" has a good foundation.

Re:This has been around for many years.

[Jerry Talton]

In 1998, theoreticians proved that the problem was "NP hard" that no general solution exists that can be solved by a computer in finite length of time.

Wow. That's pretty far from what "NP hard" actually means.