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
I guess that with all the money going on 3D movies, some will make good use of it... Although Sherk 2 looks quite alright without it :)
no sig
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?
[
They still look better on vinyl. (Brace for impact!)
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.
This has been something that LightWave (and probably other big 3d apps) could easily do for years and years. How's this different?
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
"Just as MP3s remove high frequencies we can't hear"
Not quite. The primary brunt of MP3 focuses on areas of repeated sound (which can easily be compressed). All of the MPEG codecs attempt to find areas where change is infrequent, then tell the system "from frame X to frame Y, don't change the vast majority of the sound/video".
In the case of 3D graphics in particular, the image changes. Often. Actually, it's more like an action movie than anything else (Ever see the artifacts on a poor digital cable or satellite connection? They tend to show up worst in fast moving scenes).
This compression may help a lot on still or near-still images, but I'm not sure it'll help with most modern day 3D apps and games.
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 can't be the only one who thinks this would be great for 3D games? Can I?
Reviews with a twist! http://www.sardonicbastard.com
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.
In 3Dstudio max, there is a "optimize" plugin, which basically does just that. Once the stack is compressed, and the file is saved, The mesh object will be much smaller in size. I'm sure all 3d programs have similar functions built it.
:)
does this new compression format work outside the 3D program? I didn't rtfa.
Neil is that you? Yeah yeah, it's me... Neil...
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
OK, we've had Mesh OPTIMIZATION for a long time now, so how is this any different? Secondly, how does this method know where the model has "important" details and where the detail is less visible? That really affects which triangles should be removed and which should not. (The existing solution has been to assign vertex priorities when defining "level of detail" information in a mesh. Again, what are these guys doing that's any different or better?)
;-)
Lastly I wanted to state that Mesh data is already very small. It's the textures that suck up lots of memory/filesize. The exception is with mesh animation based on vertex transformations (as opposed to the simpler, and smaller (data-wise) joint/axis animation). I didn't RTFA, so perhaps they discuss this already.
I just wanted to let you know that you seem not to have any idea what you're talking about, and you definitely don't have any idea what the article is talking about.
autopr0n is like, down and stuff.
Has their been any word on licensing? Considering that JPEG and GIF are both subject to the whims of private groups (Joint Pictures Expert Group, and Compuserve respectively) it'd be nice to have a good free image format. I haven't "R"ed the "FA," so if my question's answered there I apologize.
--Obyron
Because not everyone in every country has access to a good broadband infrastructure. I speak as an Australian who can't get broadband because Telstra has severly outdated infrastructure. Even if you can get access to their ADSL services, it tops out at 1500/256 kbs. It's not so bad if you're one of the 3 people in the country with access to the cable network (mostly owned by Telstra, 10% is owned by Optus/Singtel).
.... will it be used in Duke Nukem Forever?! Maybe this is the holy grail they've been waiting for!
Hooray for old technology that has been marketted as being new!
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.
I'm a polyhedron, you insensitive clod!
Not since Marie-Antoinette played milkmaid has looking simple and honest been so fake and complicated.
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?
I didn't RTFA, but it's probably the other way around in Soviet Russia.
I couldn't tell from the article. To have an algorithm is nice, to have an efficient one is nicer. I will get excited when I see some benchmarks or at least a time analysis of it.
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 on the Flight Gear Web Sight:
This would explain your miserable failure rate
but the level of detail for a 3d mesh is affected by how close you will end up zooming in. This can be tweaked by using vertex normals to smooth out a mesh, but the loss of detail for this sort of compresssion is a pretty risky tradeoff.
Can it reliably restore the level of detail after compression? How does it handle animated objects vs static objects? What is the intended use for this compression?
Still, it is intresting enough to warrant a closer look, I suppose.
END COMMUNICATION
It's a SPACE STATION!
Thanx for the Tshirt Idea
BTW i'm a greedy republican
You're thinking about hidden surface removal. That's been around for a while :). This actually is about using less space to store a mesh. The article even says it: elegant algorithm to compress the large and ungainly files that represent 3-D shapes used in animations, video games and other computer graphics applications.
Any real 3D application (Max, Maya, XSI etc) have had poly reduction algorithms in place, have had them for years and are probably far more tested and refined than this. Games have been using stuff similiar to this for years, every single modern game has some kind of scalable meshes, pre-made or realtime. Even old ones do too and not just pre-made models with higher or lower polycounts, but models that are dynamically scaled in poly counts by the games engine, Sacrifice is one game that comes to mind. And wouldn't it be better to use premade meshes of different polycounts rather than have them be scaled in real time? It seems like it'd use less resources that way and it would give the artist more control to make a better looking model at lower polycounts.
I hope this will speed up the day when we have a world wide quake environment. Where avatars can walk down a hallway into a different room which is on a different server somewhere else on the planet.
This is all possible today. The bandwidth requirements are huge, but enough people have high speed internet connections to download the massive amounts of information. We just need someone to design the open standard equivalent of HTML for this virtual world with earth like physics.
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.
the other is will this actually allow lower end computers to do better graphics (by virtue of having less to compute)?
It exists. Check out what ZBrush is doing.
Also, I believe ATI has a tool to do this as well.
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.
There's already a process for taking a 3D world and then flatening all of the surfaces and removing all of the surfaces that are not within the view of the camera so that they no longer are included and then compressing the result...
It's called rasterizing... the process of taking a 3D world down to a 2D image.
If you people don't know what you're talking about then why not just not say anything ? 90% of the posts in this thread are from idiots who know a tiny amount about the domain, and feel they can flaunt and strut their embarrassing morsel of knowledge in front of the community. grow up.
No one is claiming that there haven't been algorithms to do this job before - there are quite a few - but IT'S FUCKING HARD. Reducing the complexity of shapes while retaining their identity is a very tough problem - just because 3D studio has the ability to simplify geometry doesn't mean it does a particularly good job of it. Most games houses for instance can't rely on automatic simplification of models and have to employ people to hand craft low poly models. Newer techniques such as normal mapping are making this more automated, but even then there is a lot of scope for improvement - it's exactly for those kinds of uses that this algorithm (if it's as good as they say) will be the most useful.
As for the guy who offered his hilarious description of MP3 encoding as "encoding the differences between one frame and the next", perhaps now might be a good time to crawl under a rock.
"Just as MP3s remove high frequencies we can't hear..."
This is the single most idiotic comment I've heard this year.
hmm, hidden surface removal is quite old thing, I guess every 3d-engine has it already.
class he-man extends man!
Bruce
Bruce Perens.
The article is Wrong. It says that NP-Hard problems cannot be solved. NP-Hard problems CAN be solved, it just takes too long because the only known algorithm just lists all possibilities and tests them one by one. This is slow, but impossible? Nope. Such problems are being solved every day, it just takes too much time to solve them. The article probably has a point there, though, as it speaks of real-time 3D graphics which needs all things to be as fast as possible.
instead the(y) are digitized using one of many scanning techniques
What are the different scanning methods you are aware of? I've come across a few and I'm interested in knowing about others. I came across a method used by the National Research Council of Canada, and I think it has spun off into a commercial entity called Arius 3D. It captures surface 3D and colour data of objects on some kind of turntable, scanned by an RGB laser device. There's also the FastScan input device that uses motion-capture technology in combination with a monochrome surface laser scanner, so you move the scanner around, not the object. It was used for Lord of the Rings. I also came across the iModeller software package that apparently lets you use a standard digital camera to capture 3D images somehow. And I also recall seeing a documentary on television before where a RGB laser scanner, like the Canadian one mentioned earlier, was used to scan in ancient cave wall paintings. It scanned the 3D contours as well as the colour information of the cave wall surface, except the scanner laser moved around like a CRT scan line, so neither the scanned object nor the scanner needed to be moved. I couldn't find any information about that one on the web. I'd like to know of other methods and information about them on the web. Oh, and if anybody knows about that cave wall painting scanner device, I'd like to know more about that as well.
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.
Although the technology is already here, it'll probably take a few years to implement. Just look at how many years it took for MP3 to become the giant it is now. When it is implemented, I think we'll be able to fit entire cities on a single dvd. I bet Carmack is already looking at this for use in his next engine, or not...
I doubt that this would provide much assistance in FEA as there is the need to keep similar mesh sizes (with localised refinements for extra detail as needed). It has been too long since my analysis courses at university but I don't think this is the silver bullet for making FEA quicker. Most respectable FEA packages are good at meshing in a reasonably sensible manner.
Then again, I'm a structural engineer and most of our stuff is reasonably planar, or curved in a steady fashion with few fiddly bits which would need far more care with meshing.
I do know what you mean though about file sizes. A colleague of mine had a FEA model of a high rise that needed one gig of RAM to run it, without having it going into hard disc swapping.
"And we have seen and do testify that the Father sent the Son to be the Savior of the World" 1 John 4:14
It'd be one thing if this were in the popular press, but this is on the school of engineering's press release site. Oops.
I was going to give them a friendly heads-up that they're publishing information most undergraduates in the field know to be flatly wrong, but I couldn't find a relevant contact address.
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
Hasn't this been done a zillion times before? Just thinking of all those *LOD algorithms.
Slashdot social media options: AIM, ICQ, Yahoo, Jabber and Mobile Text. Why no MySpace?
... before some stupic idiot patents this?
I guess it will happen, as it is easy to claim one did prior research to this.
Patenting mathematical methods is stupid. Assume Newton or Leibniz patented integration...
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
It's about time someone came up with lossy compression for 3D graphics.
Given advances in bump mapping, texture mapping and antialissing I feel I could live with a few less detailed polygons, in exchange for faster download time. This could have a big impact on blue vs red, no?
I think this question harps back to the old argument about levels of detail. Should we spend an extra 1000 CPU cycles giving counterstrike bots a more refined nose or spend it on more advanced AI?
I think the nose job camp is winning at the moment. Not in counterstrike mind! Just in the industry in general.
May the Maths Be with you!
Could the same techniques be used to reduce mouse/pen gestures so that things like joined up handwriting recognition become possible
thank God the internet isn't a human right.
In an MMORPG, compressing models down farther than otherwise possible you could have players download new models for new content quicker.
If you really want to lower the file size of large, complex 3d models, you should be looking into things such a using bezier paths to describe curved surfaces, which also has the advantage of providing infinite levels of detail and thus can be dynamically scaled depending on the power of the rendering engine being used.
That being said, textures often take up more room than 3d models. Either reusing textures or using more polygons and less/lowerquality textures can save space.
Shoot Pixels, Not People!
See this paper by Hugues Hoppe, presented to ACM SIGGRAPH in 1996. It's the same thing. Progressive meshes have been implemented in the D3DX library for years already.
...the author of this work Mathieu Desbrun recently organised a seminar class at Caltech (along with Peter Schroeder, also mentioned in the article) on Discrete Differential Geometry:Theory and Applications. Movies of all the lectures are on the class website in wmv format, with accompanying slides.
My mind goes to the game 'Far Cry', but I bet there are lots of other games that do it.
The trick is really simple: the number of polygons is reduced, and the curving detail is transferred to the texture. The texture appears curved, but it is actually drawn with curve rather than being applied on a curved surface consisting of many small triangles.
... the rest of the process involves storing the differences between each successively simplified model and the detail level above it. I suppose a wave-interference - or turbulence - method would work well.
Another key aspect of this approach is the amount of data required to send across the bus and to store on the card decreases dramatically, so you can attain far more complex animations than previously possible. By varying a few key points of the representation you could do fairly complex deformations at any detail level in real time without losing the coherence of the model.
I can't wait to see this new approach applied.
-- thinkyhead software and media
The mesh file isn't taxing your bandwidth during a download. Mesh files are tiny compared to everything else. It's the bitmaps that suck up all the space.
And, as the original poster stated, good game artists have already optimized the model to get an optimal # of polygons while maintaining a good visual appearance. Any further automatic reduction would either be trivial or could distort the look of the object to the point that it was no longer acceptable.
One day in 1992 or thereabouts, I was sat in the computer room at college, writing 3D code in Pascal instead of 'learning' about databases. The first step I took in simplifying the render process was to cull adjacent triangles with identical or closely similar normals. This was done to speed up rendering, not for the sake of data compression, although that was of course a happy side effect.
I'd put money on someone else having done the same thing before me. Decades before me.
So without wanting to sound bitchy or sarcastic, what's the big news here?
Researchers have stumbled upon a technique that must surely be used at some point in the development of every modern computer game?
My understanding of low-poly modelling is that high-poly models are created and then simplified, ie: imperceptible triangles are removed and adjacent triangles are expanded to cover their place.
Also, what about real-time distance-based simplifying? A game might use all 1000 triangles of a model when it's close-up, but simplify the model to 50 triangles when it's further away. Same principle.
This strikes me as a case of reinventing the wheel.
Computational Fluid Mechanics.
Their main problem seems to be summarized as such: How can we get rid of mesh nodes while still accurately representing the surface?
A related approach is: Given that we have N node points available, how can we distribute them among the surface to provide the most accurate representation? If we can add a few nodes, where would it be best to add them? If the mesh is good enough, where would it be best to remove them?
Then, they explain their approach a bit more:
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 colleagues, who do advanced computational fluid mechanics (applied to drop-drop collisions with surfactant diffusion, simulation of tumor growth, biomathematics, etc.) do similar work, but in a very different way. For a given surface mesh, they assign a sort of mesh energy to the whole structure, where the energy of any point depends upon the local curvature of the surface, etc., and they add a constraint or two. (I don't remember the full details.) It's very similar to a network of springs. Then, they apply standard optimization techniques to minimize the mesh energy. The result: a mesh that has the highest density where the surface has the highest curvature, and the lowest density where the surface is flattest. The method is fully adaptive and even works during and after surface topological changes, which is very useful in CFM, where your surfaces can break, merge, etc.
So, this idea of modeling surfaces by concentrating mesh nodes where the surface curvature is greatest with an automated, adaptive algorithm is not new, and it is very applicable in making more efficient use of limited computational resources.
OpenSource.MathCancer.org: open source comp bio
This algorithm of removing polygons that you can't see has been around for a long time...
as a modeler, I know you need to put in a ggod number of extra vertexes/triagles around joints to prevent distortion when you animate them. Why choose a "lossy" standard, rather than a lossless one. you get the same compression on a 3D file containing only geometry as you do with a flat text file. open up note pad make a 1 meg text file, and then zip it up, and see how small it is.
I was working with this stuff for a game developer 5 or 6 years ago. The goal was a little different than simple compression since they wanted a better way to transition between multiple versions of the same object, each having a different resolution. Hugues Hoppe at Microsoft Research has a bunch of papers on the subject publ;ished at SIGGRAPH in the mid-90s.
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.
I dont think the model itself takes a lot space, only the texture does, the compression's advantage probably will result in less GPU/CPU usage to render the model, which will yield not as nice result as well.
3D Studio's later DOS versions had an Optimize feature that accomplished what seems to be exactly the same thing.
--
Jeff S.
I remember 3D extensions to browsers circa 1995. They used a metafile format called "virtual reality markup language", which was a variant of the SGI Inventor 3D metafiles (simplification plus web keywords). In the 1990s both the slow net bandwidths and slow graphics engines were bottlenecks.
People made demos like the Xerox PARC multi-player maze chase game. But it was slow.
Meshing is easy. Transforming the matrix is hard.
Marc Levoy at Stanford has scanned Michelangelo's statutes at sub-millimeter resolution. These generate billion polygon meshes at full resolution. Its a challange to render these. But when done properly they can seem rather real, and easier to view than in the museum. Other people are scanning other art works like the Parthenon friezes.
(its all in the subject)
-... ---
While I welcome a new approach to fast and efficient mesh optimization (yes, yes, our new mesh simplification overlords), it is hard to lend credence to the description of the algorithm as highly accurate. The very first example figure in the article (a mesh of a small-case letter "a" in 3D) shows a mesh reduction result that removes all of the curvature from the end of the top left "hook" of the "a". I do not consider this a highly accurate representation, unless perhaps they are referring to the bounds of the mesh reduction.
Another troubling point is the list of possible applications; retail web sites, museums, cartoon characters/video games, and CAD. Of these, the web and video game applications are reasonable, but for CAD it would be ridiculous except in the case of a quick and dirty look at a large complex assembly. For museums I know of one solution that gives exceptional speedups in rendering, but does so without loss of visual detail: Qsplat from the Michelangelo Project at Stanford.
In any case, I do look forward to hearing more about this at Siggraph 2004.
--- Void where prohibited. Your mileage may vary. ---
Dammit, stop compressing things unless it's lossless. yes I can notice a 20khz sound you took out of my music, yes I can tell you're not resampling the background on my cable TV during a talking heads scene, and yes I'll notice a significantly reduced polygon count on my 3d meshes.
-- I was raised on the command line, bitch
If this is just about optimizing progressive meshes, then it's been around for over a decade in mainstream games. Progressive meshes are like mipmaps for polygons. Mesh optimization is sort of like low-frequency noise reduction, where you get rid of minor details that don't really show in the rendered scene, merging adjacent polys, occlusion filtering etc etc.
If they just combined the two then I give a big Whoop, because that's like claiming to have invented steak & cheese. Steak rocks, cheese rocks, steak & cheese is just a combination of rock-ness.
-Billco, Fnarg.com
Umm, we first bought 14.4 modems about 1991, so more than a decade, those trailblazers 19.x were the best you could get too, though those 'bbs' deals were the only way to get em real cheapass though.
but by 1994, we could source 14.4s for $99 ea, so it was way past intro stage.
remember, all those warez bbs's in 1988...1992 was what really spured the demand for BBSs/Modems, no matter what legit people say , its the truth. Coz we at least knew no one that used them for 'normal usage'.
Liberty freedom are no1, not dicks in suits.
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).
Anyone else think the MP3 comparison was pointless, silly, and just an attempt to connect this to some sort of beloved buzzword to make the article submission seem cooler?
MP3 doesn't "remove" frequencies anyway. And this mesh compression is merely the same sort of thing I've already seen in terrain engines like in Black & White and Far Cry. Not to mention, this has nothing to do with compressing meshes for storage space but to speed up rendering, further making the MP3 comparison silly.
Work in machine learning has proven that generalization and compression are equivalent. I'd like to hear more about this. Can you provide a pointer or some references, please? Thanks.
I mean, jeez, I've implemented a progressive-mesh generation algorithm myself, almost five years ago! Mesh detail reduction based on, say, the quadric error metric of Whatsisname and Cantremember has been around for _decades_ now.
I notice a lot of people are a bit confused by this. I didn't think it was anything new or great either, at first. And actually, it *is* a bit of common sense -- but it's used in the right way.
This technique is not so useful for generating LOD (levels of detail). What it IS useful for, is for generating manageable 3D models from _scanned_ data. This will never compare to what a 3d animator can do by hand. However, if we're a few years in the future, and scanning in (somehow...) 3D data for the entire city of London for our next game, having a solid and fast algorithm to make that data manageable (and renderable) is going to save a butt load of time.
Maybe "London" was a bit of an extreme example, but if we're using Vin Diesels' likeness in a video game, being able to scan him in and click a button is much preferred over hundreds of hours of artist time of removing redundant polygons.
This is probably the best I can do.
:))
Whether you're finding exploitable patterns in discrete data or estimating a "function" for a block of pixels in an image to use in some kind of lossy compression, it's a form of generalization. It's one way of formulating a learning problem.
I can think of one very interesting project offhand, which uses compression coefficients to assess expected generalization accuracy.
(Ooh. I just found a paper on Compression-based Learning. That one looks like fun.)
Okay, I've been searching for about a half an hour now. I apologize that I haven't been able to find something that proves equivalence. (There's a guy in another lab that's really into this. Maybe he's got a paper on it.) You can think of it this way, intuitively: both compression and generalization seek a small number of bits to accurately describe a large number of bits.
(Huh. Maybe this dearth of papers on compression = generalization indicates that it's something I ought to look into for a new research direction...
I got my Linux laptop at System76.
First of all your statement is circular logic, yes something didn't get wide-spread use before it was common. Isn't that like the definition of common?
GIF and JPEG at least predate the internet (web) that I know here in Denmark, so it was not lack of these formats that kept users from using them, and I actually do remember a lot of awkward GIFs on the initial batch of personal homepages.
The actual reason to why the web has become more graphical is probably not just about bandwidth, but also the commercial interests and the fact that this is no longer just academics who publish their knowledge.
Back in the early days (1996 IIRC) my modem could retrieve 3.1 KB of data, and I was told by a company (who's web-page I helped create) that their goal was to have the entire thing load in 30 seconds. That's an 256 colors *uncompressed* image of 300 x 300 pixels -- and that was approximately half my resolution back then. Still it would have been stupid of them to waste the page with one big image, and today you actually see the successful designs cut down on graphics!