Mesh Compression for 3D Graphics 297
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."
MP3 compression == complicated (Score:5, Informative)
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
Link to publication (Score:5, Informative)
The actual paper can be dowloaded from here [usc.edu].
-jim
Useful, but over stated... (Score:5, Informative)
This could come into more handy later if it is built into a renderer.
A subpixel displacement renderer that can nullify coplanar polys in this way (though there arent that many usually in detailed oranic objects) it could speed things up quite a bit.
Abstract (Score:3, Informative)
David Cohen-Steiner, Pierre Alliez, and Mathieu Desbrun
To appear, ACM SIGGRAPH '04.
Abstract: Achieving efficiency in mesh processing often demands that overly verbose 3D datasets be reduced to more concise, yet faithful representations. Despite numerous applications ranging from geometry compression to reverse engineering, concisely capturing the geometry of a surface remains a tedious task. In this paper, we present both theoretical and practical contributions that result in a novel and versatile framework for geometric approximation of surfaces. We depart from the usual strategy by casting shape approximation as a variational geometric partitioning problem. Using the concept of geometric proxies, we drive the distortion error down through repeated clustering of faces into best-fitting regions. Our approach is entirely discrete and error-driven, and does not require parameterization or local estimations of differential quantities. We also introduce a new metric based on normal deviation, and demonstrate its superior behavior at capturing anisotropy.
How new is this (Score:3, Informative)
While the algo may be new, the idea certainly isn't. Direct3D has built in support for optimized meshes, the ROAM algo http://gamasutra.com/features/20000403/turner_01.
Many algorithms do this (Score:2, Informative)
The POVRay mesh format is a good place to start if you want to learn about triangle meshes. Check the povray.org site for lots of good info.
You can also do something similar to a discrete cosine transform on meshes. You don't gain on the rendering side which is what the article seems to be doing, but you could potentially decrease large file sizes by an order of magnitude.
As for applications, who knows. Triangle meshes are often used for terrain maps; however, terrain is just as easily saved using some sort of height field.
KLL
Re:This has been around for many years. (Score:5, Informative)
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. (Score:5, Informative)
This is about reducing the complexity of meshes so that they can render faster.
Re:This has been around for many years. (Score:4, Informative)
The concept of lossy compression of 3D models might not be new, but that doesn't mean that the method for doing it isn't.
Also, even if the problem were trivial for 2 dimensions, it wouldn't neccesarily be so in 3. The 2 body problem has a simple solution, the 3 body problem has no solution in elementary functions. Random walks are recurrent in 1 and 2 dimensions but transient in 3 or more. I can think of several other mathematical examples where the difference between 2 and 3 dimensions (or 2 and 3 objects) changes things completely.
Don't judge unless you know you understand the subtleties of this algorithm compared to others
This isn't new? (Score:5, Informative)
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.
Hi (Score:2, Informative)
Re:slow connections (Score:1, Informative)
That is why it is news. (Score:4, Informative)
Also for all those questioning it's usefullness, you need not look any further than 3D scanning. When it comes to detailed models, very few things are done by scratch, instead the are digitized using one of many scanning techniques. This model is then massaged by hand by an artist. This technique would allow you to get a much better first cut, saving time for the artists.
Lastly, quake and others generated meshes from smooth NURBS objects. This is quite different, and much easier than generating one mesh object from another. Those tequniques are not usefull for scanned objects where you start with a dense mesh object.
Re:Proliferation of 3D Content on the Web? (Score:2, Informative)
Re:A little skeptical, at least based on post (Score:3, Informative)
You're thinking of the video versions, which work the way you described (to my knowledge; they probably also do some perceptual stuff, but I'm not familiar with video perceptual coding).
Re:Proliferation of 3D Content on the Web? (Score:2, Informative)
Open Source Prior Art (Score:1, Informative)
This may not be exactly right, but The terrain starts as a regular grid of datapoints take from DEM data which is interpolated into an irregular grid of points within certain error constraints, which preserves the contour of the scenery but drops the number of triangles needed. This has the effect of dropping out datapoints in the middle that don't contribute anything:
A quote from a paper [flightgear.org] on the Flight Gear Web Sight:
Re:Nice add-on to 3d movies (Score:3, Informative)
Re:A little skeptical, at least based on post (Score:3, Informative)
They do. Your eyes have better resolution when dealing with luminosity than colour, and also detect lower frequency changes better than high frequency ones. JPEG uses both these effects, as do all video compressors AFAIK.
Cheers,
Dave
No. Re:No. Re:No. (Score:5, Informative)
Skimming the article, this just seems to be polygon aggregation on the model ( not HSR, which is certainly not what grandparent was implying anyway ). It's certainly not a method for compressing the stored mesh, it's just discarding arguably redundant detail.
Desbrun explains that his accomplishment was to simplify such a mesh, by combining as many of the little triangles as possible into larger elements without compromising the actual shape. Nearly flat regions are efficiently represented by one large, flat mesh element while curved regions require more mesh elements.
( My emphasis ). I was pretty sure this was nothing new, although I'm sure a general case algorithm, let alone a fast and accurate general case would be novel. But I was writing polygon aggregation code for my undergraduate computer graphics subjects ( much simpler meshes though ), and I would expect anyone with any CSG education to not confuse the subject matter with an actual storage optimisation.
Re:Is this maybe a little hyped? (Score:3, Informative)
"It has a strong formal basis. You can make up extreme cases that will trick it, but for ordinary shapes, it works remarkably well."
Cool, Shrek 3 will be nothing but primitives! Move along, nothing to see here...
Ordinary != primitives. Ordinary = things you generally find in reality. That would be faces, bodies, hands, everyday objects like trees, toasters and television sets...
The technique is borrowed from machine learning (which is my current area of study, so I feel I have some understanding of it). You can regard what they're doing as generalizing (the aim of machine learning), which is always prone to error when presented with pathological cases. In other words, if you try really, really hard, you can invent cases which it utterly fails at, but it just doesn't happen in normal practice.
(For a human analogy, consider those weird optical illusion drawings: they're pathological cases that throw your brain out of whack. But in practice, you really don't need to be able to quickly and correctly analyze those sorts of things.)
Re:This has been around for many years. (Score:5, Informative)
Wow. That's pretty far from what "NP hard" actually means.
3D Content could have proliferated long ago (Score:2, Informative)
I could have sworn that someone came up with a format for streaming 3D on the web ages ago. No, not VRML, something else. I just tried to do a Google search for it, but came up with too many results [google.com]. It was supposed to allow 3D content on the web to take off as well.
VRML was supposed to do that, for that matter, and has been around since around 1996. I think 3D has never really taken off on the web because of the way you have to navigate through 3D worlds. I recall navigating through VRML was a real pain with a mouse. If they found some way of automating walkthroughs with just one click when they first introduced it, then maybe it would have been more popular. I haven't followed VRML it since its introduction, so I don't know if it now has automated walkthroughs.
Re:I'd say multilevel meshes is a better answer... (Score:1, Informative)
The immediate problem that springs to mind for me is that current graphics cards and APIs don't produce good shading effects when the geometry is turned down. Gouraud shading (color-per-vertex interpolated across the face of the triangle) is the best that hardware acceleration will handle right now, and turning down the number of vertices will lead to problems with detailed color operations under normal circumstances (complicated lighting/shadow effects, etc.)
i see, you are not in the field but rather stuck with textbooks from 1996.
low poly with dot3 or other pixelshader based lightning models is currently all the rage because the xbox and ps2, while having a fast graphics part, are memory and cpu limited.
Re:the use of this technology... (Score:3, Informative)
Classic problem in computer graphics (Score:3, Informative)
Anyway, it's a pretty old problem in graphics. The USC press release that prompted this slashdot story is simply advertising Cohen-Steiner, Alliez, and Desbrun's paper [usc.edu] which will appear at SIGGRAPH 2004 [siggraph.org] later this summer. That's all it is. They have a new way to do automatic poly reduction. Now it could be that it's vastly superior to anything else that's been done in the area, but even if so, this isn't likely to cause any revolutions. Why? Because the existing poly reduction algorithms already work pretty well. They work well enough that they're already in production use (as others have pointed out there are plugins for most major 3D packages already, and most game engines have had "continuous level of detail" systems for a good long while). So at best this is going to make life easier for some 3D content creators who won't have to do so much hand-tweaking of LODs (levels-of-detail, aka "optimized" meshes). So don't expect to see any huge changes in the games you play or movies or whatever because of this. Mesh optimization/LOD techniques are already being used pretty much everywhere it make sense to do so.
But here's an idea for all you Karma Whores out there: go to the list of papers [siggraph.org] on the SIGGRAPH 2004 web site (or go to Tim Rowley's easier to browse version of the list [brown.edu]), pick something that looks interesting, and send the story to slashdot [slashdot.org]! There's at least 50 more slashdot stories there just waiting to burst! Happy hunting! There's enough Karma for everyone, so don't be greedy now.
A Summary for the Uninitiated (Score:3, Informative)
First of all, as many posts have stated there are wuite a few algorithms out there for mesh optimization. Two of the classic techniques were developed by Schroeder and Turk.
Schroeder's method [columbia.edu] (PDF) is fast and is able to reuse a subset of the original vertices, but the quality is not great. Essentially, the mesh is simplified mainly by collapsing edges (eliminating two triangles for each edge collapsed) in the flattest parts of the mesh.
Turk's method [gatech.edu] (PDF) is more accurate, but cannot reuse the original vertices. Basically a new set of vertices are scattered across the original surface, forced to spread out from their neighbors. The amount of local spreading or repulsion is determined using local curvature, allowing greater point density where curvature and therefore detail is high. A new mesh is generated through these points using the original as a guide.
Further work has been done to create progressively decimated meshes, much like progressive JPEG images work. A model sent over the web could be displayed in low resolution very quickly while the bulk of the geometry is still in transit. Methods for this tend to be colser to Schroeder's approach because obviously it is desirable to reuse the existing data at each level of representation.
This new method is quite a bit different. It clusters triangles into patches that can be represented simply. These patches are optimized iteratively. Finally a new mesh is created, using the pathces as partitions and reusing vertices where the partitions meet.
Some benefits to this method:
To me the potential animation capabilities and optional interactivity sound most interesting. Accurate decimation methods are already available that work well offline, and faster methods are available for online LOD management. Merging decimation with animation could lead to higher quality, lower computational cost 3D anmiation. Allowing high interactivity could help artists improve the aesthetics of scanned artifacts.