Slashdot Mirror
Stippling As Fast 3D Technique
An anonymous reader writes "This Stippling
effort wins best paper at IEEE Boston conference. Could real time medical rendering be whizzier than Id?"
← Back to Stories (view on slashdot.org)
← Back to Stories (view on slashdot.org)
Probably not, but it's certainly just as bloody... or maybe i'm underestimating doom III.
...when will it be used for pr0n?
Stippling is just the application of small, uniform polygons (aka "dots") in rendering images. To modern graphics hardware, a dot may as well be a polygon, so we haven't gained much in practical terms.
Can a bunch of PhDs who are all supposed to know quite a bit about what they are doing, including Purdue EE professors, a researcher or two from IBM TJ Watson, and some almost-PhD graduate students, come up with something as mighty as what Id Software can invent?
Id is great and everything, but gee, I hope the answer is yes, they probably can.
Abstract
NON-PHOTOREALISTIC VOLUME RENDERING USING STIPPLING TECHNIQUES
This is obviously a compromise approach. There's no way this would be able to make photorealistic games.
The difference between medicine and gaming is that with medicine, you have a real-life object whose structure whose PROPERTIES you're trying to recreate realistically, regardless of how off-color or computer generated it appears.
With gaming you have an object that's computer generated, whose APPEARANCE you're trying to recreate, with lesser regard to the properties within that object. For instance, most gaming models consisting of polygons have hollow insides...
People at Id don't bother to render and model the organs. People in medicine don't care about having models of human hearts bumpmapped or glossy.
This is supposed to be news for nerds. What's with all the mindless generated hype?
/^[A-Z0-9._%+-]+@[A-Z0-9.-]+\.[A-Z]{2,4}$/i
Essentially, they are just using a different primitive (point) instead of splat or voxel, traditionally used in volume rendering visualizations.
Most of the complexity in volume rendering consists of preprocessing the data (alpha testing would be a simple way, other methods involve transformations into the frequency domain, etc.) to reduce the asymptotic complexity of the set to be rendered from the naive O(n^3) to something which corresponds to the actual visible set, not the actual rendering itself.
I don't think they are doing anything different in this stage -- it's still the same dataset that needs to be worked with, after all.
There's 10 types of people in this world, those who understand binary and those who don't.
That said, you CAN have sketchy-looking Quake if you want with NPRQuake. I've tried this and it looks incredible- it's a shame no commercial games have used this technique yet. Reminds me of that 80s music video where the gal walks into the mirror, and everything's all "pencilly-looking" but in real-time... now what was that damn song? (racks brain)
Also check out Waking Life. It's available on P2P as I write this, but you didn't hear that from me, and you're better off renting the DVD for all the extra goodies. It's not as pretentious as many make it out to be, and the visuals alone are worth it.
Wrists killing you? Not in 2 weeks. Learn Dvorak.
The actual papers are presented here.
Rumor has it, doctors will soon be rendering a patient's internal organs with ASCII art.
Not so. In fact, many of the developments first applied to games are usually directly applied to the medical field and other visualization fields.
One future, two choices. Oppose them or let them destroy us.
This technique is meant to be a fast ( real time ? ) method of viewing medical data , like watching a CAT scan as it's happening. It's *not* attractive , it has no textures , it doesn't render the organs with all their colour or bump maps. What it *does* do is give the surgeon an immediate source of information on the status of the patient's condition. Very interesting stuff , good application of a technique to a real need. But it's not anything to do with Id. It *won't* make Quake 4 any faster.
As most people know , including most Slashdotters ( I hope ) , 3D doesn't begin and end with Video Games. Other things use the technologies too.
The fact that no one understands you doesn't mean you're an artist.
...from drawing an image as a collection of pixels ? Isnt the fact that 3D objects can be represented as collection of discrete pixels well known ?
From the article:
Wow, think of what you could do with this! You could print grayscale images using only one color of ink, or color images using only three or four! No longer would we be limited to viewing images on expensive computer and television screens. We could actually print the images on a super-thin sheet of cloth or wood. We could call this new device "paper".
Ancient artists sure were smart.
Could this be used in a FPS to map people's facial expressions in real time (well, less the appropriate lag). I'd love to be able to see the pissed off look on some guy's face who I've fragged three dozen times straight.
Could real time medical rendering be whizzier than Id?
Probably, but not because of this. This technique would have very little use in a gaming environment. Indeed, algorithms indended for medical imaging rarely do. In this particular case, the dotted images don't really provide any sort of occlusion. That is, you can see right through the image to whatever is behind it. Great for medicine (where the whole point is to see inside the patient's body), bad for games.
As a matter of fact, when I read this, my only thought is "well, duh". I do 3D graphics myself, and I am having a hard time believing that this technique is new. Particle system rendering? There must be something more to this that the dumbed-down article isn't telling us. Maybe they have a new, advanced algorithm for deciding exactly where to place the dots... that really must be it. As long as we're reporting on low-level algorithms, I have a new algorithm I came up with for drawing borders on the silouette edges of cartoon renderings efficiently. Do you want to hear about it? No? Aww...
"whizzier than Id"
I really, really hope that was an unintentional pun.
the world needs entertainment as much as it needs medicine. There is no proof that Id's games are damaging for society, it is more likely America's lack of gun control.
The army has used Id's technology before for training simulators, so it can be said that their software DOES help America in at least one way other than entertainment.
GoatPigSheep, the 3 most important food groups
They have made the renderer available, here (win 2000 only). I don't think I have the interest to see further than just trying whether it works for me, but if someone does, please let us know if you find anything worth commenting :)
...that they don't confuse this technique with "stapling" the next time you go into the doctor's for a thorough physical. Ouch.
I'll form my OWN solar system! With blackjack! And hookers!
This article sucks, and the /. write-up sucks more. It has virtually nothing to do with id, Doom, or games in general. They're visualizing data sets, not shooting rockets at each other at 60 FPS (or 8 fps in the Doom3 demo ;). Rendering static, previously collected data Vs. On-the-fly rendering of a rapidly changing dynamic environment.What should one expect from an anon submission, though? :P
/. dupe. (similarities highlighted)
...were...)
And how bout these amazing captions? They read like a typical
IMAGE CAPTION 1: This image of a human cranium was created with a new kind of computer-imaging software that uses the ancient technique of stippling to convert complex medical data into 3-D images that can be quickly viewed by medical professionals. Data from CT scans were converted into dots to create the stippled image. Cave dwellers and artisans used stippling thousands of years ago to create figures by painting or carving a series of tiny dots. More recently, 19th century Parisian artist Georges Seurat used the method, also called pointillism, to draw colorful, intricately detailed works. Because dots are the most simple visual element in a picture, they also are ideal for computer visualizations.
IMAGE CAPTION 2: This picture of a human foot was created with a new kind of computer-imaging software that uses the ancient technique of stippling to convert complex medical data into 3-D images that can be quickly viewed by medical professionals. In this image, data from CT scans were converted into dots to create the stippled image. Stippling uses tiny dots to create an image. Because dots are the most simple visual element in a picture, they also are ideal for computer visualizations.
Oh well, at least their subjects and verbs agreed in number. (...data...
It is not as simple as it seems. You want the nearer bones (or whatever structure) to show up more, but not completely obscure what is behind. And you want the stuff behind to look "behind". But how?
It is not the same problem as calculating normals of polygons to see which surfaces are facing the viewer, sorting things by depth, and finding out what is completely obscured by what else. Go back, and think again.
I'm guessing (without reading the paper), that the point of using dots is that the dots are not infinitely small, but rather have a small measureable size, and so the nearer dots are drawn larger, but that all dots are small enough that they don't tend to "hide" each other in the Z direction, but rather "pile up" a bit to make the piled up places darker. This sort of "implementation" is interesting I think solely because one might be able to implement it in a way that makes use of fairly standard operations implemented by vroomy graphics hardware. (Ie. it is not otherwise an obvious implementation of the desired operation, and I'll guess that the initial reaction of the people who built the graphics hardware/driver is "hey, you're abusing it!", followed almost immediately by "wow, cool!". It's as absurd and wonderful as if you drew a cloud of smoke between you and another object by drawing each particle in the cloud.)
Didn't Future Crew have a pixel based 3-D effect towards the end of the Unreal demo? Its was really cool for its time.
We were doing color 3-D Ultrasound in Japan 10 years ago...great fun. You recall the visible man and woman projects right? Checked them out lately?
Hmm... I've never been a big fan of pointalism. It looks like too much work.
Now, a nice impressionist rendering would be great. Although, I'm not sure I'd want a neurosurgeon screwing around with my brain based on an artistic impression of it.
"Well, see the giant green splotches represent perverted thoughts and... well, there isn't much else to speak of. Apparently, this small yellow part over here is occupied with programming, and it's slowly being invaded by a brown sludgy part which wants some more coffee. Overall, the painting's not worth much, and I certainly wouldn't want it hanging over my couch. Ok... let's make the first incision."
bytesmythe
Hypocrisy is the resin that holds the plywood of society together.
-- Scott Meyer
Does noone remember Quake 2? The software renderer had an option called "Stipple Alpha" which would render transparent entities such as water and glass using a stippling method. It was much faster than true alpha blending, and it got the job done. Carmacks like four years ahead of the curve as usual..
The purdue scientists know what stippling is. They point is they found out how to transform voxels into 3d stipples that look good from multiple directions... not stippling in the screen coordinate sense. So how is Carmack suddenly a pioneer of medical imaging?
THIS THING CAN TURN ON A DIME, MACROSSZERO STYLE ALSO FUCK BETA, ~NYORON
You can map voxel and density rendering onto modern graphics hardware to get real-time volume rendering without too many problems. Furthermore, medical applications require high fidelity: you don't want doctors to miss some detail, and these kinds of stippling techniques greatly reduce the resolution.
To shrug this off as having no bearing on the gaming world may be a bit narrow-minded. Remember, just because something is in 3D, it doesn't mean you want it to look like it's in 3D.
For instance, the cel shading technique, by which specifically designed shading networks are applied to polygons in order to emulate the look of 2 dimensional animation. For the same reasons that technique has garnered so much popularity over recent years in the gaming industry, an application like this may find similar inspiration.
In addition, this type of rendering goes beyond gaming, right into the entertainment industry. Art studios are constantly looking for new ways to present their animations. There have been several festival animations, done in 3D environments, that were purposely rendered in 2-dimensional ways. Who's to say you won't see this method used in the future?
Wow, goatse.cx prior art. Scary.
Money for nothing, pix for free
This is the ancient dotball from the amiga demo time. I know someone would make good use of it. Don't see what the news is yet though.
Yeah, these images look pretty sweet, takes me back to the olden tymes when a digitized, hires black and white picture on the commodore 64 looked exactly like this.
To come so far to turn back. Ahh, technology.
Uh, actually, the strippers would probably cost a hell of alot more than the CS majors cost.
Then again, most lonely CS majors end up at strip clubs at the end of the week, giving their hard-earned cash to boob girls. It all comes full circle.
So I guess, in a way, you can say that ATI/NVIDIA already hired strippers, and they're doing a fine job.
one of the first (if not the first) to use animation in a video
Yesterday, I saw the video of 'Leader of the pack', by the Shangri-La's, from 1972. Animated.
It's just possible that this was something made by the BBC, not an official video clip, but I'd be very surprised. It looked vintage 1970s (ie, bad).
I believe posters are recognized by their sig. So I made one.
Note: I've read the linked article but not the actual paper.
I think the reason for doing a stippled technique is to cut down on preprocessing of the data set, rather than to speed the actual rendering of the graphics.
You're trying to visual a 3d volume, but you don't have a surface map. What you have is a series of bitmaps taken at different z-depths. You can either just render the z-ordered bitmaps with appropriate transparency (expensive for your graphics hardware) or you can try to calculate surfaces and render polygons. Calculating the surfaces can be extremely expensive (think hours of computer time on what was not too long ago a super-computer class machine).
It looks like what they've done is find a way to render the bitmap data with (a) minimal preprocessing and (b) not needing hundreds of megs of video RAM.
A few years ago I shared a VR setup with some people visualizng seismic data. They were always complaining about the onyx only having 256 megs of video ram...
it's wrong that you you couldn't have texturing. you could even have 3D textures---something most current gfx cards still can't do. remember the voxel terrain of comanche? they had a texture across their terrain back in 1994. you're right, "at most, you could have coloured dots", but that's exactly what a texture is about: colouring the picture elements, wheter those are pixels or voxels. not sexy for games? comanche was _damn_ sexy back in the day, you wouldn't have expected that kind of terrain would be possible on your 486 25MHz!
of course, texturing only looks good if the voxels are dense enough and form a solid, whereas the idea of the technique we're talking about here is all about rather sparce voxels. you could still colour them in to make arteries look different from veins or something.
an issue with which i'd be much more concerned: what kind of hardware acceleration can you get for that technique? i doubt that it renders 10x faster than polygons with a comparable level of detail on your vanilla geforce.
but what do i know, i'm just a model.
I was quite horrified at the number of comments I saw posted suggesting that generating a decent stippled 2d image from 3D volume data is trivial or somehow like "2d point sprites" or "reinvented voxels".
I felt I should try and explain a few things to help the less, um, "graphics savy" among us appreciate and understand what's going on here.
First, we need to know what "non-photorealistic rendering" (NPR) means. It is NOT (as some fool mentioned) a "tradeoff" and inferior to photorealistic effects. It only implies that the rendering does not use a light-transport model to acheive its results (hence not realistic in terms of how lights/cameras work).
This is a GOOD thing. In a CAT scan you don't want a picture of the guy's head. You want an image giving you useful information about the internal structures of the guy's head. Photorealistic rendering would be as useful as taking a picture your patient.
The problem of getting a useful image from a large volume dataset is non-trivial. Doing this at interactive rates is even tougher. Further, drawing realistic stipples is difficult in its own right, because of the nature of the stippling technique (spacing and distribution are used to convey transparency, as well as contour).
The images produced by this technique are amazing, and look very close to what one might imagine an artist would produce for a textbook. That's incredible, people! If you compare these images to those that doctors currently have to look at (slices, color coded density maps, etc) you'll notice that the stipples are much easier to understand, and look very natural.
Congrats to the Purdue team and kudos to Slashdot for covering a real comp sci paper, despite the fact that the yokels in the groups think that it has something to do with Quake 2. (Groan)
Sounds a lot like splatting, a common 3D volume rendering technique.
I don't know if you've ever seen Seurat's work, but it is LARGE (canvas-wise) and absolutely stunning visually. I got up close to the canvas at MOMA in NYC and said "He's dithering!" and my girlfriend, the BACS going for her art degree now, craps all over me "No, it's pointillism!".
I dropped the argument due to my desire to make sweet love to her all night long.
HBI's Law: Frequency of calling others Nazis is directly correlated with the likelihood of the accuser being Communist.
...My, those sample pictures have a wonderful old-timey look to them.
For many decades, stippling was the standard technique used for rendering biological or medical illustrations. I suppose it has something to do with the printing processes used for line art being cheaper than those for half-tones.
Indeed, I see that this journal and perhaps others still say "Use 'stippling' and 'hatching' techniques to achieve tonal quality. Avoid the use of shading (pencil, wash, or airbrush) for a tonal effect..."
Now, if we just had a font that reproduces the look of Leroy lettering?*
*(OK, OK, a Leroy lettering set consisted of a sort of stencil, in which the letters were merely engraved deeply rather than perforating all the way through, and a little pantograph device. The pantograph had a technical pen and a tracing point. As you followed the stencilled letters with the tracing point, the technical pen would make corresponding motions on the paper. Very common for captions in technical illustrations in research papers, museum displays, etc. Obviously too neat to be handwritten, yet obviously not typeset...)
"How to Do Nothing," kids activities, back in print!
Sun had a 3D volume rendering package in circa 1984 called SunVision(?). Point rendering was an option. Fast, but not as pretty.
At a guess, the technology didn't go anywhere because it was too slow to be of much use.
Stippling is not exact. At no point did "cave dwellers" specificy that there had to be a point at "x,y,z".
This is an advantage to doctors and medical professionals in that they don't care if an image is perfect, but they would benefit greatly from an improper image that more clearly represents information in real time.
Dots are simpler in 3d, especially for this, because everything is purely ratios and percentages, rather than exact formulas for edges of lines.
As stated in a previous post, the goal for this is the PROPERTIES, not the graphical capabilities. Have you ever seen a sonagram? Those images are extremely cryptic, but with a trained eye, they are extremely useful because they depict the truth in not an exact way, but a recognizable way.
We're human, we can use our brain to interpret this stuff.
Somebody keeps taking my stippler
Bill said I'm supposed to have my own stippler
I'm going to set the building on fire
I didn't read the article, but looked at the paper..
:)
;)
This technique claims to reinvent neither voxels nor point sprites, but it's rather a way to convert voxel datasets (like CT scans) into a threedimensional stipple representation. Imagine a particle system with the particle density at a given place about proportional to the density value in the voxel data at that place.
Ok, it's not that easy, there are a few algorithms described which allow for more "intelligent" placement of particles to enhance features and the general transparency, which makes up the main part of the paper.
The trick is then that these particles can be sent to a modern graphics card (GF3 and up) for immediate and fast display. You can zoom and rotate the model and your camera without having to recalculate anything, which makes rendering really fast.
A few future thoughts in the paper are about using vertex shader programs to shift some of the per-particle calculations to the GPU which would anhance rendering speed and clarity further, as now angle-dependent particle calculations would be possible without any significant overhead.
I didn't find any real thoughts on decreasing the complexity of the precalculation process tho. Still, having to calculate the major part only once per dataset instead of once per frame is a significant improvement over similar methods (such as most triangulation methods which require a complete re-calc as soon as you try to look at other features of the dataset).
And the comparison with Id? Come on, this doesn't have ANY relationship with 3d games, and furthermore Carmack is a good engineer who knows to deploy new rendering techniques at exactly the time PCs are good anough for them, but all of his techniques since Wolf3d were invented years ago by the very bunch of PhDs etc who also wrote this paper
For demos of course... hmmm... this could actually make metablobs look good
I skimmed the vstipple website, and it appears to be a montecarlo algorithm: depending on the inensity of a voxel, it has a proportional probability of being drawn.
The thing is, calling it "stippling" ignores the pre-existing term "montecarlo", which is precisely what is going on.
Similar techniques have been used in the 2D world to generate half-tone images without the use of regular half-tone screens. I believe in that context, it is called generating pseudo random halftones. Floyd-Steinberg is a deterministic version of the same idea.