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."
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
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?
[
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?
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.
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.
This might be slightly off topic, but it seems to me that an idea very similar to this is already being used in development. What I am talking about is the new Unreal engine. From the videos I have seen, it seems like the technology strives to create complex surfaces without using many polygons. Once of the examples they show in the game is a box with a complex grated surface which interacts with light and is shadowed appropriately, but when viewed in wireframe mode is simply a flat box made of very few polygons. They also give many more examples, including a wall made of bricks which a bump-mapped correctly but, again, in wireframe the wall is flat and the bricks are not composed of polygons. You can see the video for yourself here.
SIGFAULT
A much better analogy would have been to refer to the digital vocoder in cellular phones. They take a phonemic audio sample and find the nearest match, then replace it with a compression token that represents that bit of speech.
That achieves compression effectively by recreating a high bandwith audio stream from a low bitrate stream of tokens.
A thought I had years ago is:
3-D imaging via raytracing can be thought of as one of the most aggressive forms of compression, in that you represent a fastastically complex high-bitrate stream (i.e. The World, or at least the 3-D scene in question) with a very small (usually under 1K) stream of "tokens" (the raytracer's command repertoire). That "compresses" billions of voxels of 3-D space into a tiny scene descrption stream, and vice-versa during "decompression".
-- You are in a maze of little, twisty passages, all different... --
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.
It exists. Check out what ZBrush is doing.
Also, I believe ATI has a tool to do this as well.
Also, we 3d-modellers usually do this by hand anyway.
Does this mean that we are going to see crappy 3d-game modellers making hi poly objects and simply run them through a little wizard to "make 'em good for the game"? =)
Guess i'm just bitter for not working with CGI yet.
You cant fight in here, its a war room!
Bruce
Bruce Perens.
I disagree. I built a polyreducer for a game company and I can say first-hand that, despite the fact that we had models built by hand, despite the fact that we had really skilled artists, despite the fact that they *knew* triangles were at a premium, the polyreducer I constructed was able to get rid of an easy 10% of the triangles before visual quality decreased noticably. 20%-30% if the camera was far away (which it was through most of our game, so we polyreduced our models a lot :) )
I don't know how many triangles the models in movies have, but I find it hard to believe that all of them are 100% necessary - like with large programming projects, the focus tends to move more towards "don't worry about making it as efficient as possible, just make it look good/feel good/work". A well-designed polyreducer could probably do quite a number on those.
Breaking Into the Industry - A development log about starting a game studio.
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.
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
Actually, your description of what MP3 is doing is almost identical to what the algorithm is doing to remove unnecessary triangles.
He's not just throwing out high definition data either (which would be a poor compression algorithm). He's finding a seed point, and then trying to build the largest flat surface that masks the underlying points, because they don't really give much detail anyways (not always true).
I currently have no clever signature witicism to add here.