Author Archives: Eric

7 things for December 22

Some great bits have accumulated. Here they are:

  • I3D 2010 paper titles are up! Most “how would that work?!” type of title: “Stochastic Transparency”.
  • Eurographics 2010 paper titles are up! Most intriguing title: “Printed Patterns for Enhanced Shape Perception of Papercraft Models”.
  • An article in The Economist discusses how consumer technologies are being used by military forces. There are minor examples, like Xbox controllers being used to control robotic reconnaissance vehicles. I was interested to see that BAE Systems (a company that isn’t NVIDIA) talk about how using GPUs can replace other computing equipment for simulation at 1/100th the price. Of course, Iraq knew this 9 years ago.
  • I wish I had noticed this page a week ago, in time for Xmas (where X equals, nevermind): Christer Ericson’s recommended book page. I know of many of the titles, but hadn’t heard of The New Turing Omnibus before – this sounds like the perfect holiday gift for any budding computer science nerd, and something I think I’d enjoy, too. Aha, hmmm, wait, Amazon has two-day shipping… done!
  • A problem with the z-buffer, when used with a perspective view, is that the z-depths do not linearly correspond to actual world distances along the camera’s view direction. This article and this one (oh, and this is related) give ways to get back to this linear space. Why get the linear view-space depth? Two reasons immediately come to mind: proper computation of atmospheric effects, and edge detection due to z-depth changes for non-photorealistic rendering.
  • Wolfgang Engel (along with comments by others) has a great summary of order-independent transparency algorithms to date. I wonder when the day will come that we can store some number of layers per pixel without any concern about memory costs and access methods. Transparency is what kills algorithms like deferred shading, because all the layers are not there at the time when shading is resolved. Larrabee could have handled that… ah, well, someday.
  • Morgan McGuire has a paper on Ambient Occlusion Volumes (motto: shadow volumes for ambient light). I’ll be interested to see how this compares with Volumetric Obscurance in I3D 2010 (not up yet for download).

Amazon Stock Market update: one nice thing about having an Amazon Associates account is that prices at various dates are visible. The random walk that is Amazon’s pricing structure becomes apparent for our book: December 1st: $71.20, December 11-14: $75.65, December 18-22: $61.68. Discounted for the holidays? If so, Amazon’s marketing is aiming at a much different family demographic than I’m used to. “Oh, daddy, Principia Mathematica? How did you know? I’ve been wanting it for ever so long!”

Shader variations and ifdefs

Morgan McGuire’s page is the only twitter feed I follow (though Marc Laidlaw’s Trog Act Manly But is darn tempting), as he simply offers up worthwhile links on computer graphics and on game design. Strangely, though, some ideas cannot be expressed in 140 characters. So, here’s our first guest post, from Morgan:

When experimenting on a new algorithm, I have a zillion variations I’m testing packed into one shader and a lot of #ifdefs and helper functions to switch between them.  Often you need the invoking C++ code to line up, and I’m always forgetting to switch the routines in both the shaders and C++ to keep them in sync…

I just realized that I can put my #defines in a header and include the exact same header into HLSL, Cg, GLSL, CUDA, and C++ code, since they have exactly the same syntax.  So I now have both C++ and GLSL files that say #include “myoptions.h” at the top.  Cool!

(Ok, my GLSL infrastructure adds #include to the base spec, but I assume everyone else’s does too).

Amazon Needs Programmers, We Suspect

… at least judging from an email received by Phil Dutre which he passed on. Key excerpt follows:

Dear Amazon.com Customer,

As someone who has purchased or rated Real-Time Rendering by Tomas Moller, you might like to know that Online Interviews in Real Time will be released on December 1, 2009.  You can pre-order yours by following the link below.

With a title-finding algorithm of this quality, Amazon appears to be in need of more CS majors.

Don’t fret, by the way, I’ll be back to pointing out resources come the holidays; things are just a bit busy right now. In the meantime, you can contemplate Morgan McGuire’s gallery of real photos that appear to have rendering artifacts or look like computer graphics. It’s small right now – send him contributions!

A Digression on Marketing

In my previous post on Larrabee I talked about the marketing of an ancient HP workstation. I ended with, “If anyone wants to confirm or deny, great!”

Followup from a reader: the story misses 3 additional changes to the machine. The more expensive business machine had: a bigger cabinet, more flashing lights on the front, and required 220 power. Apparently the business market wouldn’t take the machine seriously unless it required special power and wanted something with flashing lights so it looked more like a computer. The lights were completely random and the engineers wanted to hook them up so you could at least use them to see what was going on with the machine. And, no, the engineers didn’t win.

By the way, this isn’t meant as a diss against HP: I have two HP computers at home and love them, they make quality products. I’m just pointing out that even HP (which used to be known as the company that would market sushi by calling it “raw dead fish”) finds that marketing that contravenes rational thought is sometimes necessary. The “blinkenlights” story is a common theme, because it’s true. I recall an article (which I wish I had saved) from the early 90’s in the Wall Street Journal where people running the Social Security program were duped into thinking a computer company’s offerings were ready by being shown empty boxes with blinking lights inserted. “See, the computer is computing right now”. It was quite the scandal – front page news – when this ruse was uncovered.

Bonus quiz question: In researching (if you can call it that) this story, I ran across this site, which had an excellent question, “what was the world’s first personal computer?” Answer here. I was way wrong with the Altair. The answer, a computer I hadn’t heard of before, even bears on interactive computer graphics history, as it was the first computer experience for a famous graphics pioneer.

More on Larrabee

I wrote earlier on Larrabee being delayed. A coworker pointed out this article from Jon Peddie Research, who know (and usually charge) more than I do. It makes a plausible case that cancelling this first version of Larrabee was the correct move by Intel, and that the experience gained is not wasted. JPR argues that the high-performance computing market is also high-margin, so needs fewer sales to be profitable. There are other gains from the project to date – anyway, a worthwhile read. I’ll be interested to see what’s next for Larrabee.

The magic of marketing and price differentials is fascinating to me. Books like The Underground Economist have some entertaining tales of how prices are set. Here’s a marketing story I heard (elsewhere), and it might even be true: HP had two versions of the series 800 workstation in the late 80’s/early 90’s, the only difference being, literally, one bit on a ROM chip. If the bit was set, then HP-UX could not be run on the workstation. Amazingly, the price for this version of the workstation was higher, even though it was seemingly less capable. This version was marketed to hospital administration, which at the time didn’t use HP-UX (so didn’t care); the workstations that could run HP-UX were sold to engineers. HP could honestly say there was a difference between the two workstations, say that one was tailored to hospital admin and the other to engineers, and so justify the price differential. If anyone wants to confirm or deny, great!

Larrabee Chip Delayed/Cancelled

The news for the day is that the current hardware version of Larrabee, Intel’s new graphics processor, for the consumer market has been delayed (or cancelled, depending on what you mean by “cancelled”). Intel is not commenting on possible future Larrabee hardware, so the Larrabee project itself exists. I don’t see an official press release (yet) from Intel. The few solid quotes I’ve seen (in CNET) is:

“Larrabee silicon and software development are behind where we hoped to be at this point in the project,” Intel spokesperson Nick Knupffer said Friday. “As a result, our first Larrabee product will not be launched as a standalone discrete graphics product,” he said.

along with this:

Intel would not give a projected date for the Larrabee software development platform and is only saying “next year.”

The Washington Post gives this semi-quote:

Intel now plans its first Larrabee product to be used as a software development platform for both graphic and high performance computing, Knupffer said.

See more from The Inquirer, CNET, ZDNet, Washington Post, and the Wall Street Journal. Many more versions via Google News.

In my opinion, Intel has a tough row to hoe: catch up in the field of high-performance graphics, when all they’ve had before is the ~$2 chip low-end GMA series. This series probably has a larger market share in terms of units sold than NVIDIA and AMD GPUs combined (basically, any Intel computer without a GPU card has one), but I assume makes pennies per unit and by its nature is limited in a number of ways. Markets like high-performance computing, which make the most sense for Larrabee (since it appears to have the most flexibility vs. NVIDIA or AMD’s GPUs, e.g. it’s programmable in C++), is a tiny piece of the market compared to “I just want DirectX to run as fast as possible”. The people I know on the Larrabee team are highly competent, so I don’t think the problem was there. I’d love to learn what hurdles were encountered in the areas of design, management, algorithms, resources, etc. Even all the architectural choices of Larrabee are not understood in their particulars (though we have some good guesses), since it’s unreleased. Sadly, we’re unlikely to know most of the story; writing “The Soul of An Unreleased Machine” is not an inspiring tale, though perhaps a fascinating one.

Things I learned from the ACM

Well, not just from the ACM, but also from people involved in the Ke-Sen Huang and ACM Publications situation.

  • ACM SIGGRAPH membership also gives you access to just about all computer graphics papers in the ACM Digital Library. This I knew already, but found that others haven’t realized it. Any conference sponsored by SIGGRAPH is available, from what I can tell, e.g. I3D. I noticed a few weeks ago that the SIGGRAPH 2009  Posters were not accessible to me through this benefit; the ACM fixed this problem when I reported it.
  • Deep linking, where one site links directly to content on another site, is not illegal. The EFF notes that deep linking has not yet been found to be illegal by the courts. However, linking to sites providing infringing (illegal) copies of a work for download is contributory infringement.
  • “Sweat of the brow” compilations, such as the white pages of phone books, are not copyright. There is no original expression involved, so the Supreme Court ruled such are not protected. Paula Samuelson’s article in the Communications of the ACM (Google Scholar hits here) is a fascinating overview. Titles are not copyright. Elements such as the order in a Table of Contents are in a gray area, from what I can see. The ordering and grouping of the articles into sessions may be copyright protected – the courts have not ruled, as far as I know. Changing that order on an external web page would then not be copyright, since it would be a different “original” expression. Alphabetized or numerical ordering is not copyright protected.
  • You do not need to enforce your copyright to maintain it, unlike a trademark. You can ignore an infringement and not lose your rights. So the argument that a copyright must be protected now in order to preserve it in the future is incorrect.

Do you really display PNGs?

Digging up the luma palette images reminded me of a useful PNG I made back around 1996 or so, back when this file format was quite new. A peculiarity of the PNG file format is that it stores alpha separately, unmultiplied. For 3D work it is the norm for the color stored to be premultiplied by the alpha. I won’t go into the how and why; this topic is covered in our book on pages 139-140 and is discussed on Wikipedia, among many other places.

One nice feature of premultiplied images is that you can just ignore the alpha channel entirely when displaying them for preview. This is equivalent to compositing the image over a black background. With PNG, you are required to examine the alpha channel and multiply the RGB by it in order to get the right color to display. Unmultiplied alpha has a 2D photo sense to it, the RGB image exists everywhere and the alpha is masking some part of it. The alpha is not an integral part of the pixel, as it is in 3D.

On to the image:

alpha_test

I cobbled this together to be able to quickly check if a particular piece of software was respecting the alpha channel in PNG. Back then, most software didn’t, so what would be displayed is “This viewer does not support transparency”. Today, it’s pretty rare to find such flawed PNG readers commercially (I couldn’t find a current example for you to try). Still, I’ve found this image useful as a quick reality check for whether software is using the alpha in a PNG.

Lest we forget, it was the LZW patent in the GIF format that helped popularize PNG as a patent-free alternative for the web. The Unisys patent finally fully expired back in July 2004, so it’s a moot point now, but for awhile this was a patent enforced for tens of millions of dollars, with over 2,000 licensees. My favorite quote on the whole controversy was from a flak at Unisys giving spin about their positive role enforcing a patent on a technology unknowingly used in a file format that they didn’t invent:

But Unisys credited its exertion of the LZW patent with the creation of the PNG format, and whatever improvements the newer technology brought to bear.

“We haven’t evaluated the new recommendation for PNG, and it remains to be seen whether the new version will have an effect on the use of GIF images,” said Unisys representative Kristine Grow. “If so, the patent situation will have achieved its purpose, which is to advance technological innovation. So we applaud that.”

Constant Luma Palette

I was looking around my image files and found this:

Constant luminance image

I made this incredibly hideous drawing back in 2001. What’s interesting about it is that if you convert this image to grayscale, using say Irfanview or XnView, it disappears entirely into a solid gray. Download and try converting it with your favorite image manipulation program (I refuse to insert a solid gray image of it here as “proof”).

Here’s the palette I used, in image form; the perl program for creating it is at the end of this post.

LUMA_PAL

My goal was to make a palette where you could draw anything, knowing that if it were converted to grayscale (e.g., via a scanner, or printed on a monochrome printer) it would become illegible. A similar technique was used long ago as a copy protection scheme for documentation for some computer games: print black on dark red and a photocopier would typically return all-black. Perhaps publishers that are against Google Books’ scanning of their works will use such a palette someday… I can only hope not.

What I found interesting about this little experiment was how differently we perceive the various colors compared to the constant luma computed. Grayscale conversion is supposed to take colors with the same impact and give them the same gray level. In my drawing, that pink is way brighter than the gray clouds, and even the green streaks on the ground at the lower left are brighter than the rest of the ground plane. It makes me wonder if there’s some better conversion to grayscale that more closely matches our perception of impact. Wikipedia mentions luminance as just one strategy; are there others that work better (on average)? Info, anyone? Update: a keynote at I3D 2022 by Dr. Margaret S. Livingstone discussed this very effect in depth; see her book Vision and Art for information about it.

Luma

So what’s luma, versus luminance? It turns out that the formula we typically use to convert to grayscale is flawed, in that what should happen is that the color to be converted should be put in a linear space, converted to grayscale, then gamma corrected. By applying the grayscale formula (see below) to the displayed image data directly, what most every image manipulation program typically does, we get the order wrong. However, it’s a lot more work to “uncorrect” the gamma (make the image’s channels represent linear values), apply a grayscale formula, and then gamma correct. Long and short, the grayscale value computed without taking into account gamma is called “luma”, to differentiate it from a true luminance value.

You can find more about this in Poynton’s color FAQ and Wikipedia, and details about the difference this makes can be found here. Relevant quote from this last source: “…introduces a few image artifacts that are usually fairly minor. The departure from the theoretically correct order of operations is apparent in the dark band seen between the green and magenta color bars of the standard video test pattern.”

I decided to reformulate the palette today and see what it looks like with constant luminance instead of luma, by raising the normalized palette values to the power 0.45. There’s a definite difference, as expected:

lumapal10x luminancepal10x luminancepal8

Left is the original luma palette, zoomed up (hmmm, should have used nearest neighbor); middle is the luminance palette, with gamma correction; right is another “slice” of the luminance palette, having 0.8 being the highest linear green value. These right two images do look more equivalent in visual impact to me. So a better perceptual grayscale, I suspect, is to correctly account for gamma. Trying this rightmost palette out, the image becomes:

LUMINANCE_IMG

This looks a lot better to me, more equal. The green streaks on the ground are hardly noticeable now, for example. The pink house still looks a bit bolder than the rest, but otherwise is pretty reasonable. I’ll bet if I used the newer grayscale formula (see below) the pink might fade further—well, enough hacking for the day or I’ll never get this post done.

LCD brand does matter: my Dell LCD displays the image fine from most angles, the Macbook Pro screen definitely varies with vertical angle in particular, and it’s hard to know what the “right” angle is. Using Steve Westin’s old gamma page and aiming for 2.2 seemed to work.

In case you’re curious, here’s what the grayscale image looks like for this luminance-balanced image, using XnView:

LUMINANCE_grayscale

Which to me emphasizes the weaknesses of using luma instead of luminance: the house is darker, the clouds are lighter in grayscale? Not to my eye.

Gory Details

Conversion to luma Y’ grayscale uses a formula such as:

Y’ = 0.212671*R’+ 0.715160*G’+ 0.072169*B’

from Poynton’s color space FAQ; it’s the common form for contemporary CRTs.

Or older ones such as:

0 299
0 587
0 114
’ = ’
+ ’
+ ’

Y’ = 0.299*R’ + 0.587*G’ + 0.114*B’

from Poynton’s FAQ and used in his Digital Video and HDTV: Algorithms and Interfaces. This is the one I used back in 2001.

Or:

Y’ = 0.2904*R’ + 0.6051*G’ + 0.1045*B’

from Dutré’s useful Global Illumination Compendium – download it free.

Here’s the Perl program, which outputs to a PPM file.

printf "P3\n16 16\n255\n";
for ( $r = 0 ; $r < 16 ; $r++ ) {
    for ( $b = 0 ; $b < 16 ; $b++ ) {
        $red = $r * 255 / 15 ;
        $blue = $b * 255 / 15 ;
        # The 255 below can be set in the range 180-255 for different constant palettes.
        $green = 255 - $red*0.299/0.587 - $blue * 0.114/0.587 ;
        printf( "%d %d %d%s", $red+0.5, $green+0.5, $blue+0.5, ($b==15)?"":" " ) ;
    }
    printf("\n") ;
}

If you make the starting point for green lower than 180, the green channel would take on negative values.

printf "P3\n16 16\n255\n";
$gamma = 1/0.45;
for ( $r = 0 ; $r < 16 ; $r++ ) {
    for ( $b = 0 ; $b < 16 ; $b++ ) {
        $red = $r/15;
        $blue = $b/15;
        # The 0.8 below can be set in the range 0.703 to 1 for different constant palettes.
        $green = 0.8 - $red*0.299/0.587 - $blue * 0.114/0.587 ;
        # gamma correct
        $red = 255 * $red**(1/$gamma);
        $green = 255 * $green**(1/$gamma);
        $blue = 255 * $blue**(1/$gamma);
        printf( "%d %d %d%s", $red+0.5, $green+0.5, $blue+0.5, ($b==15)?"":" " ) ;
    }
    printf("\n") ;
}