Slashdot Mirror
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."
This will usher in a new age of video piracy!
Wide-spread use of graphics on the web didn't really take off until jpeg and gif compression became common. Will the easy compression of 3D models allow use of 3D content on the web to take off?
Alphanos
So, is this something everyone can use, or will it be patented?
The perfect sig is a lot like silence, only louder
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
Well, if THAT surface was there I bet there was someone to put it there, and (s)he thought that it had some useful function...
;-)
How would you like to fly a plane designed without those thin "thingies" called "wings"?
Paul B.
Man, this has been around for years. I'd bet a decade. Almost all GPSes with mapping features use a 2D variant of this to store less line segment data for roads. 3D systems with multiple levels of detail choose among a number of differently-optimized models to reduce vertex transformation overhead on far-away objects. Where have you guys been?
[
I am for cannot waiting able frequency to this have! I too am so greatness compression going to get.
I am ask: can use this games? UT2k4 is good. It is very big game however maybe some for people.
Can this technology fast enough for gaming be?
Read journal when you are not understand
A decade ago, 14.44k modems were top-of-the-line, and expensive, and your provider either billed by the hour or $50/month.
/1mb up, the modem costs $100, with a $100 rebate (so it's free) and the service is still $50/month.
Today you can get a cable modem connection at 5mb down
You can watch multiple mp4 video/audio streams at this speed - so why not 1 3d model?
The actual paper can be dowloaded from here.
-jim
This kind of mesh simplification has been around for years, in many of the high end programs such as Lightwave and Maya. Also, when you're dealing with data that is triangulated, most likely, you're dealing with mathematical contructions based on DEMs, or other automated processes, and not the type of graphics that you see on TV and movies. All in all, not too groundbreaking, it just means that some scientists' computers can relax just a little bit more....
This is a great way to minimize scan data, but it isn't as useful as the article makes it out to be. Most modeled 3d objects are as low resolution as possible. Shrek has as many polygons as he needs to have, to take away some, or swap their location would destroy the model. For instance, I am a Modeler/TD and most animable character models have 5 divisions, or 'loops' around a deformable joint. Any less would not allow for the deformation control we need. As with most background scenery, it is modeled by hand and as low resolution as possible.
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.
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.
The article is short on technical details but...
h tm is in wide use. In fact, pretty much all 3d gemoetric level of detail techniques rely on collapsing "flat" areas. The source data for the geometry can also compress geometric data with stuff like NURBS and other parametric surfaces which is probably much better than some sort of lossy compression. With the coming "DirectX Next", OGL 2, and newer video cards, parametric surfaces (read: infinite curve detail) will easily become the norm.
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.
http://brandonbloom.name
How's the lighting meant to work if the extraneous triangles are removed from flat surfaces? You'll end up with shading that isn't very pleasing to look at. You need those extra triangles, even though you can't see them and the surface is relatively flat, if you want the model to look nicely shaded.
I'm surprised no one's done this before, actually. Good texture maps, and especially bump maps can alleviate the need for a lot of triangles. I wonder if this compression routine takes those things into account. It would be great if you could pass in a detailed mesh, and get a simple mesh + texture + bump map back out.
autopr0n is like, down and stuff.
I've played often with triangle meshes for various softwares. One thing that many do is to merge groups of adjacent triangles with the same surface normals. This is lossless, versus something like JPG. There are programs for POVRay that will do this, essentially iterating through the grid of triangles, calculating the normals, then merging.
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
It's a MOON!
We do not live in the 21st century. We live in the 20 second century.
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.
autopr0n is like, down and stuff.
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.
I got my Linux laptop at System76.
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.)
Shouldn't the industry be pushing further toward graphics cards that can accelerate true Phong shading, rather than shortcuts and texture mapping tricks? Or even automatic interpolation between meshes of different complexity depending on how much of the scene a particular model takes up? If that functionality was developed first, then this mesh optimization would make perfect sense. But, for now, anyway, it seems like getting rid of the geometry is going to force developers to continue to rely on tricks to get the best look out of their engines.
Not that you'd HAVE to use it, though...
C
The Sun is proof that we can't even do fire properly.
Read the fine article. You are correct that mesh optimization has been a most popular MA/PhD thesis subjects for over two decades. Which is exactly why someone comming up with a method that is an order of magnitude better than any other previous method is big news.
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.
Actually, the primary brunt of MP3 focuses on perceptual coding; to put it simply, it uses a model of how important a given sound is based on its frequency and position in time. These 'importance' numbers are used to determine how much accuracy should be used to store the specific time/frequency you're looking at. More accuracy, more bits, less accuracy, less bits.
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).
---
Mod me down, you fucking twits. Go ahead. I dare you.
(I read with sigs off.)
I've been using 3D Studio for about 12 years. I can't remember when this type of triangle reduction feature came in, but 3DS had it.
It would basically reduce the number of trianges more where they together made flatish surfaces and practically not touch the triangles that made up significant details.
"Mathieu Desbrun, assistant professor of computer science at the USC Viterbi School of Engineering says that digital sound, pictures and video are relatively easy to compress today but that the complex files of 3-D objects present a much greater challenge."
What!? How hard is it to remove triangles based on the direction that they face!?
"His "Variational Shape Approximation" scheme created with two collaborators produces simplified but highly accurate "meshes" representing 3-D shapes. The meshes are orders of magnitude smaller than those produced by existing ways of handling such files but remain completely compatible with all widely used methods to display and use the information."
This is really hyped. This is not compression in the sense of MP3, where you have to decode it. It's just replacing lots of small trianges that make up a flatish surface, with fewer large triangles or polygons. Big deal!
"The proxy representation, once refined, is then reconverted into a now-optimized mesh -- but not necessarily a mesh of triangles. The technique turns them instead into an assortment of polygons -- some triangles, but also four, five, six or more sided figures that more efficiently represent the shape"
Could this be a cop out? Since it could be difficult to replace some triangle groups with a larger triangle without changing the overall shape?
Polygon's are traditionally reduced to triangles for speed benefits! So why not go that little extra?
"This is not a hack," says another expert, in the field GÈrard Medioni, professor of computer science and chair of the department at the Viterbi School, using the term for a makeshift, unsystematic improvisation. "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...
War crimes, torture, lies, illegal spying... Would someone give Bush a blowjob, already, so he can be impeached?
No offense, but you obviously don't know a hill of beans about what the article is about. It is about "lossy" compression, like MP3 compression for audio, or JPEG compression for images, or MPEG compression for video. Lossy compressed 3D images would look worse-- not better-- than uncompressed 3D images.
Honey, I shrunk the Cygwin
they probably also do some perceptual stuff, but I'm not familiar with video perceptual coding
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
I write a blog now, you should be afraid.
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.
One god, one market, one truth, one consumer.
is probably not going to be seen by the end user in games or movies or otherwise, as has been noted 3d models are allready as low poly as they can be. The only use that comes to mind is in the area of scanning real models into computers which outputs huge files and many many poly's, this is where an algorithym like this would be very useful to get a model that can be used without being overtaxing on system resources.
I get the feeling this technique won't be so useful for what most people consider to be CAD. That is, defining the size and shape of parts. (ALA Pro/Engineer, Catia or the like) The part of CAD that I feel may benefit is Finite Element Analysis (encompased by the phrase: computer aided design). Meshes of 3D shapes can get VERY complex VERY fast and this complexity has to be stored in large files. The hangup is probably that this technique was developed to retain visual similarity. That dosn't mean that the data it retains will provide a good numerical solution.
You can watch multiple mp4 video/audio streams at this speed - so why not 1 3d model?
Because we're all still using 2D cameras and monitors... and that's the real hold-up in 3D content production. Things like QuickTime VR have been around for years, but haven't really caught on because they're not easy to make content with and the results are not exactly stunning sometimes.
Bruce
Bruce Perens.
In production code, for that matter.
I wrote a polyreducer for a game I worked on. It would take as input a mesh, bone data, and an input texture map, crunch over them for a few minutes, and spit out a mesh with fewer triangles (and a new texture map). It would have been easy to make it spit out a bump map as well, except we were targeting PS2 and a bump map would have taken another rendering pass.
Quite effective. We stripped about 25% of the triangles out of most models. I kinda wish I'd gotten time to apply it to the world geometry too - especially if I could have snuck it in before the lighting step. That might have been tricky though.
One amusing side effect is that I end up looking at people's examples of their algorithms (like, say, ZBrush) and just laughing. They're not doing *any* of the hard parts - they're getting as input the target mesh, they're guaranteed the high-detail mesh is a subdivided version of the target mesh, what are they doing to earn their $500? Mine would take the high-detail mesh only and do *everything* from there!
Maybe I should talk to my old boss and see if he'll let me reimplement the algorithm and sell it as a plugin . . .
Breaking Into the Industry - A development log about starting a game studio.
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. 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.
This is nice and all, but is it really necessary now that curved surfaces can be accurately represented by splines? While it may require more data per point in the model, the total number of points in a spline-based model is already far lower than the number of verticies needed to create the same model using polygons.
I can't imagine why else anyone would need a high-density of verticies unless they were trying to represent a curved surface.
8==8 Bones 8==8
As others have pointed out this is a new solution to a classic computer graphics problem. The first technique I know of to automatically reduce the poly count of meshes, while preserving the overall appearance was Garland and Heckbert's QSLIM algorithm. This was first published in SIGGRAPH 97. Or actually, hmmm, no, it looks like Hoppe's work on mesh optimization came a good bit earlier (1993).
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 which will appear at SIGGRAPH 2004 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 on the SIGGRAPH 2004 web site (or go to Tim Rowley's easier to browse version of the list), pick something that looks interesting, and send the story to slashdot! 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.
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 (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 (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.
The ultimate plays for Madden 2006
they believe in free speech instead of trying to squish it, and they, unlike their **AA counterparts, aren't trying to sue the pants off of the online world, or run to Congress whining.
Nice random MPAA/RIAA dig there (is it all Slashdotters think about anymore that they have to interject it at every opportunity?), but the fact is that there have been several articles in the past five years about how the porn industry is worried about P2P because it pirates their material. Ever done a search on eMule to see how much porn is out there ripped from the subscription sites?
The porn industry doesn't run to Congress because Congress isn't going to take a porn industry seriously! Painting them as some sort of free speech golden defenders is hilarious--they're a sleazy, money-grubbing business like any other (and they like to buy ad space through horrible spyware delivers like CoolWebSearch).