Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Mesh Compression for 3D Graphics

michael posted more than 10 years ago | from the this-is-not-a-hack dept.

Graphics 297

IanDanforth writes "A new algorithm that uses successive approximations of detailed models to get significant compression has been revealed by researchers at The University of Southern California. Just as MP3s remove high frequencies we can't hear, this algorithm removes the extra triangles in flat or near flat surfaces that we can't see. Experts in the field are giving this work high praise and imply that is will be immediately applicable to 3D modeling in games, movies, CAD and more."

Sorry! There are no comments related to the filter you selected.

How managers and business can help FOSS (-1, Troll)

Anonymous Coward | more than 10 years ago | (#9448824)

Simple, fire anyone in your organization that develops open source software as a hobby.

This is quite logical.

They prefer working on their projects instead of the work you give them, and quite often will work on their projects on work time even though they are not meant to. By firing them, you give them more time to work on their open source project which produces a better product. You then use their open source project for free. As it has improved, you do not need to buy commercial software and can save money.

So you have saved in two ways. You fire someone who is not working hard enough and replace them with someone more productive. And if enough people fire their open source developers you can ditch your commercial software and get their products for free!

Oh how I love this free software business model!

Parent is Insightful idiot mods! (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#9448899)

Very logical post

Hmmm...slightly OT, but certainly a valid point! (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#9448986)

Very interesting concept.

Makes a lot of sense when you sit down and actually think about it!

fp (-1, Troll)

Anonymous Coward | more than 10 years ago | (#9448831)

fp

Beaten by an MS fanboi! (-1, Troll)

Anonymous Coward | more than 10 years ago | (#9448839)

Hahahaha

Beaten by the MS fanboi!

Just goes to show how slow open sores developers are!

HOW DOES THIS BASH MICRO$LOTH OR WORSHIP APPLE? (-1, Troll)

Anonymous Coward | more than 10 years ago | (#9448833)

in other words, WHO CARES?

You must be running Linux! (0)

Anonymous Coward | more than 10 years ago | (#9449137)

This would explain your miserable failure rate

Excellent! (3, Funny)

Brian Dennehy (698379) | more than 10 years ago | (#9448834)

This will usher in a new age of video piracy!

Re:Excellent! (5, Funny)

dasmegabyte (267018) | more than 10 years ago | (#9449126)

No, what it will usher in is a new wave of whining when companies go with some proprietary method of mesh compression instead of whatever compression is eventually developed by the Ogg team.

Proliferation of 3D Content on the Web? (5, Interesting)

Alphanos (596595) | more than 10 years ago | (#9448836)

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?

Re:Proliferation of 3D Content on the Web? (0)

Anonymous Coward | more than 10 years ago | (#9448858)

Yeah, but you still have the problem of slow connections and text-only browsers. They're going to have some roadblocks on this one.... btw the "In soviet russia" episode of family guy is on now.

Re:slow connections (3, Interesting)

tomhudson (43916) | more than 10 years ago | (#9448889)

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?

Re:slow connections (1, Informative)

Anonymous Coward | more than 10 years ago | (#9449018)

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

Re:Proliferation of 3D Content on the Web? (5, Interesting)

Anonymous Coward | more than 10 years ago | (#9448950)

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.

Re:Proliferation of 3D Content on the Web? (1)

Anonymous Coward | more than 10 years ago | (#9448984)

i don't know, it would be really efficient... you could have a 3d environment as a site, with maybe 2d windows floating in space, "portals", that take you to another page. Large sites could even be landscapes... a final fantasy fansite could have the equivalent of popup ads with random "battles" and advertisers could write their messages across the sky. I'm sure someone was hesitant to put anything below the 640x480 fold... this is just the next step.

Re:Proliferation of 3D Content on the Web? (0)

Anonymous Coward | more than 10 years ago | (#9449059)

Er, no. That would be less efficient.

If you want to improve efficiency, you want to remove dimensions, not add them.

If I want a beer, it's more efficient if I only have to move in 2 dimensions, rather than 3, to get it. (The fridge is on this floor, not upstairs.)

It would be even more efficient if I only had to move in one dimension. (The fridge is a straight line walk from my seat.)

It would be even *more* efficient if I could get a beer without moving at all.

Dimensions are obstacles to be overcome, not aids to movement. Dimensions hide information, they don't generally reveal them.

No. (5, Informative)

autopr0n (534291) | more than 10 years ago | (#9448961)

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.

Re:Proliferation of 3D Content on the Web? (1)

Jeff DeMaagd (2015) | more than 10 years ago | (#9448992)

Wide-spread use of graphics on the web didn't really take off until jpeg and gif compression became common.

Wasn't GIF a format developed by Compuserve, as in predating the commercial development of the Internet? I thought that web servers and browsers had it already once the US government opened up the Internet to commercial uses (IIRC, 1993?).

Re:Proliferation of 3D Content on the Web? (2, Informative)

notAyank (597271) | more than 10 years ago | (#9449098)

Yes, IIRC gif86 and gif89a were the 2 gif formats and the numbers represented the year the formats were created

Re:Proliferation of 3D Content on the Web? (2, Informative)

uhlume (597871) | more than 10 years ago | (#9449044)

Quite simply, no. This may well help to lower the bar for rendering 3D graphics on low-powered hardware, which could indeed serve to speed the wider adoption of real-time 3D graphics on the web -- but it won't have anything to do with file size reductions in 3D models, which are negligibly small to begin with. This particular compression technique isn't aimed at smaller file sizes, but rather reductions in the complexity of 3d meshes: fewer triangles mean simpler geometry, resulting in increased rendering efficiency.

Re:Proliferation of 3D Content on the Web? (1)

JessLeah (625838) | more than 10 years ago | (#9449116)

Wrong. Widespread use of graphics on the Internet didn't really take off until JPEG and GIF compression became common. The Web-- which is only one part of the Internet, and not a synonym for it-- had GIF and JPEG from day one.

Nice add-on to 3d movies (1)

sud_crow (697708) | more than 10 years ago | (#9448841)

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

Re:Nice add-on to 3d movies (1)

Lanzaa (761994) | more than 10 years ago | (#9448857)

I don't think this will add onto 3d movies. It will simply make it easier for starting companies to not have to buy as much memory to store their 3d art. Not very great.

But if you think that in gaming the simpler the faster and faster = more fps this could be good game optimisation. As stated in the article somewhere. *i think*

Re:Nice add-on to 3d movies (1)

sud_crow (697708) | more than 10 years ago | (#9448894)

Actually i think its a good thing, because cheaper production means that more studios will be able to do it, until now, Pixelstudios were the only real 3D movie studio that made some "hits" due to its high quality products. We yet have to see if they will make any good use of this to make better products or not. Anyway, i think as you about the gaming segment will have some impact, although this might be for making games, and not running them, same as the movies.

Re:Nice add-on to 3d movies (0)

Anonymous Coward | more than 10 years ago | (#9449006)

Shrek and all movies of its kind are PRE RENDERED. This would have no effect on the final product of those movies. The gains here would be in less system overhead to create realtime 3D modelling.. not taking a series of individual pictures and sequencing them together 1 time and creating a movie out of it.

Re:Nice add-on to 3d movies (2, Informative)

JessLeah (625838) | more than 10 years ago | (#9449129)

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.

Patented? (5, Interesting)

CharAznable (702598) | more than 10 years ago | (#9448846)

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

Re:Patented? (3, Insightful)

mi (197448) | more than 10 years ago | (#9448863)

MP3 is patented. Chilling [chillingeffects.org] or not, just about everyone is using it.

Re:Patented? (1)

DigiShaman (671371) | more than 10 years ago | (#9449133)

Math is math. But its application of it is patentable. I don't have a problem with this. I DO have a problem when that patent shit like....the entire internet or something to that all encompassing event.

MP3 compression == complicated (5, Informative)

Raindance (680694) | more than 10 years ago | (#9448847)

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

Re:MP3 compression == complicated (0)

Anonymous Coward | more than 10 years ago | (#9449118)

/cleans out belly button

See these two pieces of lint? They might look the same to the casual observer, but this one has an extra bit of blue tint in it. That means it was made at a different time of day then the other one.

In other words, who fucking cares? This isn't an article about how mp3 compression works.

Re:MP3 compression == complicated (4, Interesting)

Mister Transistor (259842) | more than 10 years ago | (#9449119)

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:MP3 compression == complicated (0)

Anonymous Coward | more than 10 years ago | (#9449134)

I'm not familiar with MP3 compression, but the process you describe can be written as convolution against a smoothing filter. When you say "MP3 compression is not just simply throwing out high frequencies," you perhaps mean that the Fourier transform of the filter is not zero at high frequencies. But I'll bet if you actually construct it, it is small at those frequencies.

Um (-1, Flamebait)

Anonymous Coward | more than 10 years ago | (#9448848)

This would have been old news in 1993. Every 3D package has a mesh-reduction feature that does more or less just what the article describes.

Saaaaaay. I wonder if we could get specular highlights on polygons by interpolating vertex normals?

CAD??? ;-) (5, Funny)

PaulBu (473180) | more than 10 years ago | (#9448850)

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.

Re:CAD??? ;-) (3, Funny)

keefey (571438) | more than 10 years ago | (#9448875)

Try flying the Dodo in Grand Theft Auto 3 to find out. Bloody difficult.

Re:CAD??? ;-) (1)

BlueBiker (690984) | more than 10 years ago | (#9448981)

Must be what happened to the phalanges.

Re:CAD??? ;-) (1)

Viceice (462967) | more than 10 years ago | (#9449046)

The actual data might be retained but the models used for visualisatios could be compressed no?

This has been around for many years. (5, Interesting)

Speare (84249) | more than 10 years ago | (#9448855)

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:This has been around for many years. (1)

nbensa (730579) | more than 10 years ago | (#9448881)

Also, Quake3's engine does this. How is this news? Did I miss something?

Re:This has been around for many years. (1)

mypalmike (454265) | more than 10 years ago | (#9448921)

Indeed. It appears to be an interesting new approach to the not-so-new field of mesh optimization [google.com] .

Re:This has been around for many years. (1)

Punboy (737239) | more than 10 years ago | (#9448924)

There is a difference between 2d vector graphics and 3d vector graphics. 2d is much simpler and doesnt require the, well.... 3d dimension. the 3d dimension adds a whole nother level of complexity, which therefore makes the possible permutations much higher (a whole exponent higher), meaning it requires a much more complex compression algorithim.

Re:This has been around for many years. (1)

ktakki (64573) | more than 10 years ago | (#9448948)

Autodesk 3DStudio R4 (for DOS, from 1994, which I still use now and again) has a plug-in which does mesh optimization, simplifying objects by combining faces that are nearly co-planar. Depending on the complexity of the object, a savings of between 30% and 70% can be achieved.

Yes, I RTFA, and I don't see how this is such a big deal. Now, if I could reduce face count by 90% with no loss of detail...

k.

Re:This has been around for many years. (1, Interesting)

Anonymous Coward | more than 10 years ago | (#9449151)

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.

Re:This has been around for many years. (5, Informative)

MrBigInThePants (624986) | more than 10 years ago | (#9448951)

You both should try reading the article:
Computer scientists have struggled with the problem of finding an optimal mix of large and small elements for years. In 1998, theoreticians proved that the problem was "NP hard" that no general solution exists that can be solved by a computer in finite length of time. They did find work-arounds: fast methods to simplify meshes, which were unable to guarantee accuracy, and accurate techniques, which were too slow.


The Desbrun teams novel approach comes from the seemingly unrelated field of machine learning using a technique invented in 1959 called Lloyd Clustering named after its inventor Stuart Lloyd. Desbruns algorithm uses it to automatically segment an object into a group of non-overlapping connected regions an instant draft alternative to the too-numerous triangles of the original scan.
If you actually read it, it would be pretty obvious why this is new...sheesh!

Also, game data is built of far fewer triangles and in a much easier form than raw data read from a real-life source. (such as a laser range finder)LOD mesh reduction is usually done by full or partial MANUAL selection.

Re:This has been around for many years. (1)

Repran (560270) | more than 10 years ago | (#9448973)

The novelty here is that this approach automatically generates optimized meshes that approximate the original shape based on how much storage space you allow it to work with. Those meshes can then be used in the ways you describe (e.g. LOD).

Re:This has been around for many years. (3, Informative)

Ibag (101144) | more than 10 years ago | (#9448975)

While I can't say for sure that nobody has used this method before for 3D models, the article seems to suggest that this is slightly different than using differently optimize models. Instead, this seems to be a way to optimize the models so that they look good up close as well.

The concept of lossy compression of 3D models might not be new, but that doesn't mean that the method for doing it isn't.

Also, even if the problem were trivial for 2 dimensions, it wouldn't neccesarily be so in 3. The 2 body problem has a simple solution, the 3 body problem has no solution in elementary functions. Random walks are recurrent in 1 and 2 dimensions but transient in 3 or more. I can think of several other mathematical examples where the difference between 2 and 3 dimensions (or 2 and 3 objects) changes things completely.

Don't judge unless you know you understand the subtleties of this algorithm compared to others :-)

That is why it is news. (3, Informative)

pavon (30274) | more than 10 years ago | (#9449037)

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.

Re:This has been around for many years. (1)

squidfrog (765515) | more than 10 years ago | (#9449053)

I'll have to agree with you whole-heartedly. A Google search [google.com] for "mesh compression" turns up just a few of the resources available on this kind of research. To me, this is like reading a Slashdot article about a new improvement to Windows BMP files called "JPEG compression."

The ROAM [llnl.gov] algorithm, for example, is one of a set of similar algorithms. It's specifically for terrain-type models and turns up in games now and then. (AFAIR, TreadMarks [treadmarks.com] was the first big game to use it.)

Big deal. (1, Funny)

Gary Yogurt (664063) | more than 10 years ago | (#9448870)

They still look better on vinyl. (Brace for impact!)

Re:Big deal. (1)

kfg (145172) | more than 10 years ago | (#9449092)

They still look better on vinyl.

Nothing beats lacquer cylinders for 3D.

KFG

Greatness! (3, Funny)

Milo of Kroton (780850) | more than 10 years ago | (#9448871)

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?


Re:Greatness! (-1, Troll)

Anonymous Coward | more than 10 years ago | (#9448896)

I cannot wait english for to be spoken slashdot on.

*ducks*

Re:Greatness! (-1, Troll)

Anonymous Coward | more than 10 years ago | (#9448925)

hi man dont get excessive with him not good in spirit and loveliness. he fail ok.

Re:Greatness! (5, Funny)

42forty-two42 (532340) | more than 10 years ago | (#9448917)

I am for cannot waiting able frequency to this have! I too am so greatness compression going to get.

Slashdot's using lossy compression on posts now?

Re:Greatness! (1)

Punboy (737239) | more than 10 years ago | (#9448980)

I believe he means to say: I can't wait to have this. I want to get great compression too. I ak: can i use this for games? Unreal Tournament 2004 is good. ...cant figure that one out.... Is this technology fast enough for games?

Re:Greatness! (1)

trendyhendy (471691) | more than 10 years ago | (#9449168)

I think he's saying that UT2k4 takes up a lot of hard disk space for maps, which is a problem for people with limited HDD space. Maybe this mesh compression could allow the maps to take up less space.

Re:Greatness! (0, Offtopic)

bersl2 (689221) | more than 10 years ago | (#9448987)

This is "funny" because Babelfish translated his message badly?

Somebody shoot that moderator to put him out of his misery.

Re:Greatness! (0)

Anonymous Coward | more than 10 years ago | (#9449060)

What you say!!

Re:Greatness! (1)

Johnno74 (252399) | more than 10 years ago | (#9449166)

All your base are belong to UT2k4!!

must do this (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#9448873)

But does it support Ogg? Or is it the other way around?

Re:must do this (0)

Anonymous Coward | more than 10 years ago | (#9449071)

I didn't RTFA, but it's probably the other way around in Soviet Russia.

Link to publication (4, Informative)

j1m+5n0w (749199) | more than 10 years ago | (#9448890)

The actual paper can be dowloaded from here [usc.edu] .

-jim

Abstract (2, Informative)

j1m+5n0w (749199) | more than 10 years ago | (#9448911)

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.

MOD PARENT DOWN: Link contains Goatse. (-1, Troll)

Anonymous Coward | more than 10 years ago | (#9449169)

Rob "CmdrTaco" Malda stepped off the bus and was led into the yard of the Main
State Correctional Institute. He had been given ten years for participating in
a stock fraud. Five with good behavior. Years spent basking in the glow of a
CRT had been hard on him. His body was frail, his skin pallid. He knew he could
never make it through ten years in the general population with his virginity
intact. He had to get into solitary.

As soon as the burly guard unshackled him he made his move. Exhaling a feminine
"hmmph" he weakly slapped the guard. He was quickly taken to the ground,
receiving a swift kick to the ribs before being restrained. As he was dragged
to the solitary confinement cell he felt nothing but relief. "At least in
solitary," he thought "I'll be safe." Unfortunately for Rob he had picked the
wrong guard to mess with.

The next few days were uneventful. The time in his cell he spent evenly between
sleeping, reading a "Perl for Dummies" book he had gotten from the book cart,
and masturbating furiously. His self-flagellation was interrupted on the fourth
day. The burly guard he had attacked earlier stepped into his cell. The gleam
in the guards eye and the mean grin on his face made Rob's pecker quickly
shrivel in his hand. "You fucked with the wrong man when you fucked with
Michael Simms," said the guard. "The inmates here call me The Asshole for a
reason. Now come with me, punk."

The guard led him down the hall to one of several empty shower stalls. He
roughly threw Rob in the stall and locked the door. Rob was petrified. His mind
raced as he imagined the myriad of different tortures that could be in store
for him. His worst fears were confirmed when the guard returned. In his hands
were a short black dress, black stilleto heels, and a curly blonde wig. "Strip
down and put this on, bitch." Rob did as instructed and was pleased to notice
that the dress fit well and the heels gave him a nice slimming effect. The
burly guard admired the drag queen. "The GNAA is gonna love you!"

The guard left the shower stall, only to return minutes later. He opened the
door and led 20 large black men into the stall. "Rob, meet the Gay Nigger
Association of America. GNAA, meet Rob. I'm sure you all will get along fine."
With that the guard slammed the shower door closed and walked away laughing.

The men approached Rob, backing him into a corner. The apparent leader stepped
forward. "No matter what I'm gonna fuck that purdy lil' ass of yours. Now I can
fuck it dry or you can lube it up for me." Rob knew he had no choice. He
kneeled in front of the leader, who began to slap his face with his 10 black
inches. Puss from syphilictic sores quickly covered Rob's cheeks. When the
leader was sufficiently aroused he placed his throbbing cock up to Rob's lips.
As soon as Rob opened his mouth the leader violently shoved his manhood to the
back of Rob's throat and exclaimed "Swallow my shit you cracker bitch!" Rob
gagged as he was violently face fucked.

Just when he was about to pass out the leader pulled out, turned him around and
shoved his cock into Rob's ass. Rob began to scream in agony but his cries were
quickly muffled by one of the other gang member's cocks. They rode him like
that for the better part of an hour. When one man finished another quickly took
his place. Just as Rob was getting used to the throbbing pain in his anus the
men stopped. One man lay down on the floor and Rob was told to get on top of
him and take his dick inside him. Exhausted and humiliated, Rob had no will
left to fight. As soon as he inserted the penis another man came up behind him
and began to force his cock into Rob's already filled anus. Again his screams
of agony were muffled, this time by a smelly black anus.

For another hour he was violated in this way. When the men were finished with
him he couldn't walk and his mouth was filled with dingleberries and ass hairs.
Before they all left the leader had some parting words for Rob: "Thanks for
that sweet piece of ass, punk. We'll see you again tomorrow. Oh by the way, we
all have AIDS." It was going to be a long ten years for Rob.

This is NOT new technology (2)

skittixch (777368) | more than 10 years ago | (#9448897)

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

Useful, but over stated... (4, Informative)

Anubis333 (103791) | more than 10 years ago | (#9448903)

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.

Re:Useful, but over stated... (2, Insightful)

yasmar (685541) | more than 10 years ago | (#9449025)

There is a lot of work on mesh simplification and compression happening right now because there _is_ a real need for it. Meshes that are modeled by hand may not benifit from it, but many many mesh datasets are being produced by laser range scaners or isosurface extraction of volume data (from some kind of medical imager such as mri say). These meshes are often messy and generally have far more polygons than they need.

Re:Useful, but over stated... (1)

sebenhuh (773800) | more than 10 years ago | (#9449082)

There is a similar idea: Level Of Detail meshes used in most engines, not to mention the recent inclusion of displacement maps, bump maps, and normal maps in some newer engines. With this combination a generated illusion of depth and detail is easily and quickly achieved.

This looks more like a solution to a more automated system to creating 3D models [ie 3D scanners] which have always had problems and usually take more nurturing than if it had been sculpted by a modeler to begin with.

uhh LightWave (1)

aarku (151823) | more than 10 years ago | (#9448908)

This has been something that LightWave (and probably other big 3d apps) could easily do for years and years. How's this different?

How new is this (3, Informative)

SnprBoB86 (576143) | more than 10 years ago | (#9448915)

The article is short on technical details but...

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

A little skeptical, at least based on post (1)

SilentChris (452960) | more than 10 years ago | (#9448920)

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

Hi (1, Informative)

autopr0n (534291) | more than 10 years ago | (#9449000)

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.

Re:Hi (0)

Anonymous Coward | more than 10 years ago | (#9449164)

This is not flamebait! He's right. The grandparent is total crap.

Re:A little skeptical, at least based on post (2, Informative)

Kiryat Malachi (177258) | more than 10 years ago | (#9449058)

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

Problems with lighting interpolation (2, Interesting)

sashang (608223) | more than 10 years ago | (#9448930)

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.

Games? (1)

jcostantino (585892) | more than 10 years ago | (#9448932)

I can't be the only one who thinks this would be great for 3D games? Can I?

Impressive. (3, Insightful)

autopr0n (534291) | more than 10 years ago | (#9448943)

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.

Re:Impressive. (1)

Trillan (597339) | more than 10 years ago | (#9449054)

It does seem surprising, doesn't it?

I think this is one of those inventions that "anyone could have invented," but nobody ever did... which makes it all the more impressive, doesn't it? :)

Re:Impressive. (1)

PhrostyMcByte (589271) | more than 10 years ago | (#9449081)

There are already programs that generate bumpmaps from detailed models.

The only reason they are good is that sending a large texture once is a lot better than sending a ton of geometry to a video card every frame. It is unrealistic for storage- unless the model is extremely detailed the texture will probably be larger than the model.

Many algorithms do this (2, Informative)

Anonymous Coward | more than 10 years ago | (#9448944)

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

That's No Icosahedron (4, Funny)

Hektor_Troy (262592) | more than 10 years ago | (#9448959)

It's a MOON!

Re:That's No Icosahedron (1)

pla (258480) | more than 10 years ago | (#9449113)

That's No Icosahedron, It's a MOON!

Well, even if no one else did, I considered that one of the most insightful (and funny) comments in this thread so far. :-)

I did find some of the examples at the link amusing, however... Sure, it reduces polygon counts - But makes your spiffy model of a human head look like someone attacked a styrofoam hat form with a cheese-slicer.

HomPo (-1, Flamebait)

Anonymous Coward | more than 10 years ago | (#9448962)

amove forwar3,

This isn't new? (5, Informative)

grammar fascist (239789) | more than 10 years ago | (#9448983)

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.

Max (1)

I7D (682601) | more than 10 years ago | (#9448991)

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

I'd say multilevel meshes is a better answer... (5, Interesting)

CompSci101 (706779) | more than 10 years ago | (#9448994)

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... (1, Interesting)

dfj225 (587560) | more than 10 years ago | (#9448996)

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

Mmmm...!? (0)

Anonymous Coward | more than 10 years ago | (#9448997)

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

Re:Mmmm...!? (0)

Anonymous Coward | more than 10 years ago | (#9449061)

I compleatly agree with you.

This Article is basicaly BS.

Plus when dealing with 3d models more detail is better, there is no reason to compress the file by eliminating polys, it would be much better to save the polys and use a zip or rar compression on the file.

Further more Mesh optimization isn't just in 3D modeling programs, many games do this on the fly as i think was stated in another post.

I'm going nuts over this article and i though this was the best post so far so i decided to respond.

Licensing Concerns (1)

Obyron (615547) | more than 10 years ago | (#9449002)

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.

Very nice, but.... (0)

Anonymous Coward | more than 10 years ago | (#9449036)

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

Ob Ref (0, Offtopic)

Queer Boy (451309) | more than 10 years ago | (#9449039)

I'm a polyhedron, you insensitive clod!

Is this maybe a little hyped? (2, Insightful)

Shanep (68243) | more than 10 years ago | (#9449069)

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

Re:Is this maybe a little hyped? (1)

zalas (682627) | more than 10 years ago | (#9449130)

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! Uh... using your analogy, DCT+quantization based video compression is just replacing lots of different frequencies of similar magnitudes with one magnitude. Transforms aren't necessary for compression, especially if the input data is already in a somewhat analyzed state, like triangle vertex data.

What is the time complexity of it? (1)

drgonzo59 (747139) | more than 10 years ago | (#9449091)

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.

Not Written by the Scientists (1)

SpootFinallyRegister (787720) | more than 10 years ago | (#9449094)

In 1998, theoreticians proved that the problem was "NP hard" -- that no general solution exists that can be solved by a computer in finite length of time.
ooops. someone forgot to read this over.

Open Source Prior Art (2, Informative)

Port-0 (301613) | more than 10 years ago | (#9449100)

I think the Flight Gear Fight Simulator [flightgear.org] has been using this technique for 5 years or so to model the terrain of the earth.

This may not be exactly right, but The terrain starts as a regular grid of datapoints take from DEM data which is interpolated into an irregular grid of points within certain error constraints, which preserves the contour of the scenery but drops the number of triangles needed. This has the effect of dropping out datapoints in the middle that don't contribute anything:

A quote from a paper [flightgear.org] on the Flight Gear Web Sight:

An irregular grid can often represent the same level detail as a regular grid with 4-6x fewer polygons. This is very desirable in a flight sim where both detail and rendering speed is very important.

This almost sounds good, (1)

LordZardoz (155141) | more than 10 years ago | (#9449144)

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
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?