Monthly Archives: March 2009

More With the Links

I love the movie sequel title “2 Fast 2 Furious”. How clever, and a great way to guarantee there will never be a third movie. Well, there was, but they had to go the colon route, “… : Tokyo Drift”.

Which is indicative of nothing, as I don’t think I’ve ever actually seen any of these movies. I was reminded of the title as my goal today is to whip through the backlog of 72 potential blog resource links I’ve been gathering on del.icio.us. [Well, as it turns out, I got through 39 of them (the fresher ones), 33 to go…]

ShaderX^7 has been published. We hope to give it an overview sometime soon (mine’s on backorder from Amazon.com).

From various source I heard that OnLive got a bit of notice at GDC. Think: pure server-side computation of all graphics for a game, i.e., a cloud computing model. Now even your grandma’s computer or even a rigged-out TV can play Crysis, assuming the net bandwidth is there. Which of course makes me think: what about latency? Lag for how other players see your action is always there, and causes mismatches (“how did I instantly die?”). But increasing lag for you seeing the consequences of your own actions seems like a non-starter for shooters, at least.

Mark DeLoura has a great two-part article on what game engines are licensed for titles. First part is a general survey, second is about the technology involved. I found it interesting to see what people cared about, e.g. multicore is on people’s minds. Nothing too shocking here, but it’s fantastic to see what is getting used, and why, in this marketplace.

Related to this, I happened across a list of game engines on wikipedia. Not massively useful (e.g. no sense of what’s popular), but a starting place.

John Ratcliff has a graphics math library available for download with an unrestrictive reuse license. He recently added best fit methods for AABB’s and OBB’s.

I was interested to look at the open source, cross-platform (!) model viewer GLC. I’ve wanted something like this for doing some experiments with mesh manipulation. Not a bad viewer, but that’s all it is at this point, unfortunately: you can’t even export to a different 3D format. The search continues… If you know a reasonable open source 3D file viewer/converter out there, please tell me. I should probably bite the bullet and just use Blender, but this application is way overkill.

CUDA voxel rendering – pretty impressive!

I liked this post on optimization mainly because of the line “I went in and found out that some title bar was getting rendered 140 times every time you refreshed the screen”. I can entirely relate (though 140 must be some kind of record): too many times I’ve put output debugging statements showing updates, only to see 2,3,6 updates happening. I once started on a project and in the first few weeks increased performance by 100%, simply by noting the main draw path was being executed twice each frame.

Speaking of performance, there’s an article on volume rendering optimizations when using a ray-casting approach on the GPU.

Wolfenstein source code for the free iPhone version, along with Carmack’s documentation on the project, is available.

Software patents are only slightly dumber than business method patents, which are patently absurd. I hadn’t noticed until now, but there was recently a ruling on a business method patent, In re Bilski, which has been used to strike down software patents.

A detailed data and execution flow diagram for the new DirectX 11 pipeline front-end is available from Jolly Jeffers.

People are still making ray-tracing specific hardware; witness Caustic Graphics. They have a rather amazing claim: “The CausticOne, however, thrives in incoherent raytracing situations: encouraging the use of multiple secondary rays per pixel. Its level of performance is not affected by the degree of incoherence.” Good trick. That said, I can’t say I see any large customer base for such a product. This seems like a company designed for acquisition, similar to Ageia. Fine by me, best of luck to them.

I’m happy to learn that the Humus site now has a news blog. This is a great site for demos of advanced techniques, and for honest comments about strengths and limitations of various approaches.

Another blog: The Geeks of 3D. Tracks demos, APIs, SDKs, and graphics card releases. Handy – some of the links here I found there.

There was a nice little article on data alignment on Gamasutra. Proper alignment is a key element in getting high performance.

I was trying to find the name of the projection of equidistant latitude and longitude lines for a surrounding spherical environment. From this interesting page (click on the “Wall Maps of the World” text) I found it: Plate Carrée.

Predicting the future is so much more interesting than predicting the past. I love this: MIPS per $1000. It’s entertaining to equate raw computing power with structured processing. By the same equivalence, I should be able to hook up 1700 mice in parallel to get a human brain.

A great line from a GPU review: “Nvidia’s new line of unbelievably expensive cards will block out the sun, and ray-trace its own shadow in real time.”

Faber College’s motto is “Knowledge is Good”. Learning about the idea of metamers would have saved this article from confusion. Coming back to this article now, I see all the comments have been removed, and an apologia trying to convert confusion into enlightenment added, but I think this still misses the point. Sure, there is a color associated with a single wavelength of light. But, my guess is that 99.99% of the colors we perceive arrive at any location on the eye as light with a spectral mix of wavelengths, not a single wavelength (Naty will correct me if I’m wrong). Unless you’re Dr. Evil and deal with sharks with frickin’ laser beams on their heads on a daily basis. Hmmm, I’m probably forgetting some other single-wavelength phenomena, like fluorescence. Anyway, the article did lead me to look up more information on metamers on Wikipedia, where I learnt about metameric failure, a term I hadn’t heard before. One more reason a simple RGB representation of color isn’t sufficient.

Cute thing: Snapily lets you turn some set of images or video into lenticular prints.

I don’t have a lot to say about what I do at Autodesk. Here’s a tidbit.

Art for the day, crayons as pixels.

ACMR and ATVR

ACMR is Average Cache Miss Ratio, which is used to measure the effectiveness of a vertex reordering scheme to see how it performs. That is, the GPU has a certain number of transformed vertices it keeps in its post-transformed vertex cache. This cache will be more or less effective, depending on the order you feed triangles into the GPU. ACMR is the sum of the number of times each vertex must be transformed and loaded into the cache, divided by the number of triangles in the mesh. Under perfect conditions it is 0.5, since the most a cached vertex can be shared on average in a (non-bizarre) mesh is 6 times and each triangle has 3 vertices.

Ignacio Castaño has an excellent point: a better measure is to ignore the number of triangles in the mesh but instead divide by the number of vertices. He calls this the ATVR (average transform to vertex ratio) of a scheme. The problem with using the number of triangles is that this number varies with the mesh’s topology. Optimal ACMR, vertices over triangles, gives a sense of the amount of shared data in a mesh. ATVR is a better measure of cache performance, as it provides a number that can be judged by itself: 1.0 is always the optimum, so if your caching scheme is giving 1.05 ATVR, you’re doing pretty good. The worst ATVR can get is 6.0 (or just shy of 6.0).

I think the reason ACMR is used is that we evolved from triangle strips to connected meshes. Individual triangles have an ACMR of 3.0. Triangle strips have an optimum ACMR of 1.0, since each vertex can be shared with a maximum of 3 triangles. The way to think about triangle strips is how they increase sharing of vertices with triangles. Gluing strips together in a certain order allowed a better ACMR, since the vertices in one tristrip could be then reused by the next tristrip(s). So the ACMR as an optimum measure was a way to show why general meshes were worthwhile. But, once general meshes came to the fore and became the norm, this vertex/triangle ratio became less meaningful. At this point ACMR just makes it difficult to compare algorithms, as you alway need to know the optimum ACMR. The optimum ACMR changes from mesh to mesh. The optimum ATVR is always 1.0, so different meshes can be compared on the same scale.

That said, this comparison of different meshes using just ATVR can be a bit bogus: if a “mesh” was actually a set of disconnected triangles, no sharing, the ATVR would be 1.0 no matter what, since each vertex would always be transformed once and only once. ACMR would always be 3.0. So, the optimum ACMR is also good to know: a lower optimum ACMR means more sharing is possible and can be exploited.

Ignacio has a followup article on optimal grid rendering, showing the ACMR and ATVR for various schemes.

I3D 2009 Report

I was holding out in hopes that Jeremy Shopf would do a summary of days 2 and 3 of I3D 2009, since he did such a nice piece for day 1. No such luck, so here’s mine. What follows is a brief overview of I3D, mostly the papers that I cared about most, i.e., those on rendering and maybe a little modeling. The goal is to put enough information to let you skim through many papers and decide which you want to read.

There were about 100 attendees. As usual, you can find the paper titles and links to many of them on Ke-Sen Huang’s website.

Day 1:

Pat Hanrahan’s keynote was on do-it-yourself UI. He encouraged people to get their hands dirty and try making some dirt-cheap UI hardware, just to see where it might lead. How to summarize an hour-long talk? “Just Do It”, Arduino, Maker Faire, and this video, which is brilliant.

Multiscale 3D Navigation – The interesting nugget was the idea of rendering a cube map around the viewer to get the depths at pixels, then use this depth data to adjust the near and far planes, adjust the amount of distance traveled when moving forward, and perform collision detection and object avoidance when moving forward.

Gigavoxels – Make everything voxels. They use an octree at the upper levels, 3D textures at the nodes. Compress. Render.

A Novel Paged-Based Data Structure for Interactive Walkthroughs – A “what if our model has 110 million triangles?” paper. Usual idea of textures for far away stuff. Key idea is to divide the scene into coherent chunks that each fit into a disk page, with a k-d tree atop. Lots of preprocessing. Nice result of 20 FPS of the scene at good quality, on a laptop.

Terrain Sketching – UI and algorithms for artist-controlled creation of heightfields. Various ways to create them (silhouette, then “spine”, or vice versa). I liked where he uses spectral noise analysis of real terrain to fill in the artist’s shaky silhouette to make the final result more convincing.

Animation’s not my forte, so I’m skipping reporting that session. That said, Kavan’s paper seems to offer a nice thing, his (or any) higher quality non-linear skinning can be automatically turned into linear skinning, which CAD tools and GPUs support well.

Soft Irregular Shadow Mapping – similar to an earlier paper by Sintorn, now for Larrabee. Wild stuff: take the scene from the eye, take those samples that are seen and transform them into light space as a group. Cells in the light’s “grid” view of these samples are processed. Samples are compared to geometry and an approximation of the coverage of the occluder of the sample is made. Quite involved, but imaginable that this could be “the future”. Table 3 is particularly valuable to anyone interested in shadows, as it’s a summary of previous work and what features each has (more or less).

Hair Self Shadowing and Transparency Depth … – a different way of quickly creating a deep shadow map (like a shadow buffer, but with an opacity function at each pixel instead of a depth). Interesting use of buckets to count hairs at each depth, an “occupancy map”. Good error analysis & corrections done. Seems to work pretty well.

Approximating Dynamic Global Illumination in Image Space – SSAO has no view-dependent component, so as the lights move this self-shadowing component never changes. With a bit more work and record-keeping you can also get shadows that are more affected by directional lights and can also get color bleeding. Some cool effects, some artifacts.

Multiresolution Splatting for Indirect Illumination – a paper where I understood most of it while watching the presentation, but coming back to it I realize I’d have to read the article carefully to know what it all means when put together. Virtual point lights, min-max mipmaps, all sorts of stuff. If you know reflective shadows maps, this extends those by using multiple resolutions to save on bandwidth. Seems a bit tricksy, but amazing that it works.

Day 2:

Started with the fluids session; I’m not fluid-oriented, so no descriptions for you.

Fast High-Quality Line Visibility – very nice work and a good presentation, giving a number of techniques for computing visible lines. 50x faster than using an item buffer, for complex models.

Dynamic Solid Textures… – solid textures for NPR. Problem: how to balance between 3D textures that stay in place on their surfaces while having a 2D look with a constant frequency of pattern on the screen? Basic idea is to use octaves of noise and fade depending on zoom level.

Laplacian Lines for Real-Time Shape Illustration – A new NPR line type. I have “Suggestive contours are only in concave areas. Laplacian lines are a bit faster.” Hmmm, I didn’t write down much else about this one. As is often the case, some things looked great, some things did not.

Real-Time View-Dependent Rendering of Parametric Surfaces – the summary, “screen-space flatness”. Use CUDA to tessellate patches dependent on how much the curve diverges on the screen from a straight line segment. I didn’t understand fully how cracking was ameliorated, but it came out in questioning that cracking was not fully eliminated (though almost so).

MLS-based Scalar Fields… – wild deformations. Magic.

Real-Time Creased Approximate Subdivision Surfaces – how to keep creases on Catmull-Clark subdivision surfaces. Valve is starting to use this in their pipeline, as they would like to have just one art asset be able to be used both in the game and for offline animation. Has some little glitches at concave corners, and there are fixes for these. Valve seemed to feel this method had some staying power for their modeling in the future. Given the limitations of Catmull-Clark surfaces (e.g. these can’t be concave) it allows a lot.

Posters session followed. To be honest, the one that most sticks in my mind is where the guy analyzed a large number of games to see how artists simulate first-person walking. Does your head bob, does your gun bob, do both? Would something else work better? Bob patterns included up and down, U-shaped, infinity-symbol-shaped – the latter two were slightly better. This one won best poster presentation, in fact. Other one that was of interest was combining SSAO and toon shading, which seemed to give a bit more detail to objects.

End of day 2; I already covered the NVIRT announcement at the banquet that night.

Day 3:

Granular Visibility Queries on the GPU – about occlusion culling. First gave a summed area table way of tracking occluders, but that method seemed fussy and complex. The hierarchical item buffer presented seemed like a winner.

Parallel View-Dependent Refinement of Progressive Meshes – indeed, how to do this in parallel. Some very nice visualizations during this talk.

Efficient … Audio-Visual Rendering … – If you have a CPU budget for rendering images plus generating sounds, which pays off best? Nice to see someone do something different.

Don Greenberg gave an enjoyable capstone talk about the history of perspective and its use in architecture. He focussed on historical Italian architects playing tricks with right angles in buildings to make corridors look longer, trompe l’oeil painting, etc.

… human motion papers… crowd patches… egocentric affordance fields… – not my areas, and I faded a bit as conference paper overload started to set in.

The last paper I attended to more carefully, since it was from my company and I’m working in this area (but have nothing to do with the paper):

Multiscale 3D Reference Visualization – Infinite multiscale grids and how to render them well when zooming in and out. Also, put objects on blue stalks (red if two blue stalks merge) with the stalk bases forming circles on the ground plane grid, to give clearer visual cues as to the location and size of objects. New word for the day: exocentric. Egocentric rotation is where the viewer rotates his head, exocentric is where the object stays still and the viewer orbits (or for you gamers, strafes) around it.

And then home the next day through a snowstorm. My car survived, I survived, life’s good.

ShaderX^8 CFP – proposals due May 17

Will there be a GPU Gems 4? I don’t know. But I do know there will be a ShaderX^7 and, with your help, a ShaderX^8. The timeline and information about this next volume is at the ShaderX^8 site. If you’re interested in submitting, one detail (currently) missing from this site is that an example ShaderX proposal, writing guidelines, and a FAQ can be downloaded from here. The key bit: proposals are due May 17th. I’m not currently associated with this series (though I was for volumes 3 & 4), I just like to see them get good submissions.

The existence of these book series – Game Programming Gems, ShaderX, GPU Gems – is a fascinating phenomenon. Conferences like SIGGRAPH are heavy on theory and cutting-edge research, light on practical advice. Books like ours can be more applied, but are survey-oriented by their nature, not spending a lot of time on any given topic. Code samples and white papers on the web from NVIDIA, AMD/ATI, etc., and independents such as Humus, they’re great stuff, but are produced by particular groups of people with specific interests. Also, sometimes just finding relevant code samples on these sites can be a serious challenge (“search” sometimes works less well than I would like).

These book series fill the gap: they go through a review and editing process, improving quality and presentation. This in turn makes them of higher average interest to the reader, vs. a random article on the web of unknown quality. They won’t disappear if someone’s domain expires or interest wanes. They can be easily accessed years later, unlike material published in ephemeral venues such as Game Developer Magazine or GDC proceedings. The titles, at least, can be surveyed in one place by sites such as IntroGameDev (though this one appears to no longer receiving updates, unfortunately, e.g. ShaderX^6 is not listed).

The major downside of these books is that they’re only available on paper, not as searchable PDFs (except the first few ShaderX books). Well, almost the entire GPU Gems series is, wonderfully, online for free, but is still not easily searchable. Now if someone could just figure out a Steam-like system that let people buy books in electronic form while protecting publishers’ monetary interests. Hmmm, maybe eye-implanted bar-code readers that check if you have access to a given piece of digital content, that’ll be non-intrusive… Anyway, this is the challenge ahead for publishers. Maybe the Kindle is the best solution, but I like the Steam games model better, where something you’ve purchased is available on any computer attached to the Internet.

Best of all for consumers is free & digital, of course, but this does trim back the pool of authors pretty drastically, as a royalty percentage of 0% is not much of an incentive (I’ve been reading too many popularized economics books late, e.g. Naked Economics, so have been thinking more in economics-speak, like “incentives”). We wrote our book for the love of the subject, but I can’t complain about also, to my surprise, earning a bit of money (enough to allow me to, what else, upgrade my computer and graphics card on a regular basis). Enough rambling, but the subject of electronic publication is one that’s been on my mind for a few decades now. I expect a solution from you all by the end of the week, then let’s create a startup and we’ll sell out by next March and make a mint.

NVIRT Slides

Austin Robison kindly shared with some of us his NVIRT talk slides (see my previous blog post). It sounds like these would take a few weeks to show up on the NVIDIA website somewhere. So, until then, I’ve put them up for viewing on our website. No favoritism; it’s just interesting information.

I liked his dichotomy for rasterization vs. ray tracing: rasterization is fast, but needs cleverness to support complex visual effects; ray tracing robustly supports complex visuals but needs cleverness to be fast. Sure, there are any number of counter-arguments to this split, but it has a nugget of truth at its core.

Romanesco Broccoli

While you anxiously await the next links roundup, how about a snack?

This is just cool, a vegetable that looks like it was invented by a computer graphics hacker: Romanesco broccoli. Thanks to Morgan McGuire for pointing this thing out (which he calls a “cone-flake”), and for his photo below (appropriately enough, snapped at a farmer’s market in Sunnyvale, CA). Click on the photo for the full image.