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."

Proliferation of 3D Content on the Web?

[Alphanos]

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?

Patented?

[CharAznable]

So, is this something everyone can use, or will it be patented?

This has been around for many years.

[Speare]

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?

Re:slow connections

[tomhudson]

A decade ago, 14.44k modems were top-of-the-line, and expensive, and your provider either billed by the hour or $50/month.

Today you can get a cable modem connection at 5mb down /1mb up, the modem costs $100, with a $100 rebate (so it's free) and the service is still $50/month.

You can watch multiple mp4 video/audio streams at this speed - so why not 1 3d model?

Problems with lighting interpolation

[sashang]

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.

Re:Proliferation of 3D Content on the Web?

[Anonymous Coward]

Bandwidth probably isn't the problem, because 3D models can be described in ways that don't require much space. A renderman .rib file is far smaller than an image of the scene it describes, and a renderman shader can also be quite small. I'd expect something similar is the case for OpenGL.

I'd guess the bandwidth would really be taxed by the transmission of bitmaps used for textures. That won't be helped by removing triangles from the model.

I expect any acceleration would be in the processing on your computer. The CPU and/or GPU would have less work to do, because of the reduced number of triangles to render. So your game gets a higher frame rate, and/or uses fewer cycles, or can perform faster with less powerful hardware.

The real reason 3D content hasn't taken off is that it frankly isn't very useful for every-day browsing.

I'd say multilevel meshes is a better answer...

[CompSci101]

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

Similar Idea already in use...

[dfj225]

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 [fileplanet.com].

Re:MP3 compression == complicated

[Mister Transistor]

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".

Re:This has been around for many years.

[Anonymous Coward]

Yes, the idea of mesh simplification is not new. This strategy, however, is new, and it is substantially better than older ones. I went to a technical talk by this guy about a year ago; it does achieve better (by several reasonable measures) mesh compression than its predecessors.

Useful for CAD? yes/no

[t_aug]

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.

Re:Impressive.

[gtada]

It exists. Check out what ZBrush is doing. [209.132.69.82]

Also, I believe ATI has a tool to do this as well.

Re:CAD??? ;-)

[iLEZ]

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.

I'm not sure that's the problem.

[Bruce Perens]

Notice that this is mesh compression. It is a way to compress an irregular and aperiodic surface. If you want a compact 3D model the first thing to try is using simpler geometry.

Bruce

Re:Proliferation of 3D Content on the Web?

[electrofreak]

but you still have the problem of slow connections and text-only browsers. They're going to have some roadblocks on this one....

Slow Connections: This concept is to help the slow connections, but it still may be slow for them. They just need to realize that for about twice the cost (thinking of AOL here) you can have like 500 times the speed.

Text browsers: It would be inserted content and there for the text browsers wouldn't display it, just as they don't display images. Not a problem here.

Re:Useful, but over stated...

[ZorbaTHut]

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.

It has been done before.

[ZorbaTHut]

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 [209.132.69.82]) 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 . . .

Splines

[Bones3D_mac]

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.

Re:MP3 compression == complicated

[daVinci1980]

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).