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.

NVIRT, a mini-blog, and “Creating Games”

I’m at I3D 2009; tonight at the dinner Austin Robison at NVIDIA announced NVIRT, which is NVIDIA’s ray-casting engine. I say “casting” as the idea is that you feed it objects, hand it a ray generator and it gives you back the ray intersections desired. Certainly it can be used for ray traced rendering, and the constructs presented make it clear they have thought through this aspect: rays can terminate on the first intersection found (useful for shadow rays), or can return the closest intersection point (eye/reflection/refraction rays). Rays can continue on when a fully transparent object is hit. Objects can be put in any efficiency structure you wish, and structures could be contained by other structures (Jim Arvo’s metahierachies idea). For example, you could put static geometry in a k-d tree, which is highly efficient but expensive to update, while placing dynamic objects in a bounding volume hierarchy, which usually can be updated more easily (though losing efficiency over time) by growing bounds. You have control over what efficiency methods are used.

They’re thinking of this SDK in more general ray-casting terms: collision detection, AI queries, and baking illumination or other characteristics onto surfaces. I can certainly imagine uses for engineering simulation. It runs on CUDA, but hides CUDA programming from the user. By the way, the switching time between CUDA and the graphics API will someday soon be a lot less that it is now.

This SDK will be released sometime this Spring (it will also be incorporated with NVIDIA’s NVSG scene graph SDK, as a separate release). The SDK will come with lots of samples, including source fo a basic ray-tracing renderer. All in all, an interesting development. The catch is, of course, that CUDA does not run on anything but NVIDIA hardware. Nonetheless, this is a fascinating first step. Austin says this effort is a serious attempt by NVIDIA to put this sort of engine in the hands of developers, not some “let’s see if this research sticks” half-baked release. Hearing him talk about the bits of inside information their group learnt about the operation of the GPU, and the corresponding boosts in performance, makes me wonder if other GPU-based ray tracers out there will be able to get near their performance.

I have a bunch of links saved up, which I’ll dump here someday soon, as well as more about I3D 2009 (see Jeremy Schopf’s blog in the meantime). For now I’ll just mention one quick link: Morgan McGuire’s twitter blog. No, it’s not a “I’m drinking a latte and using my iPhone” twitter blog. I like the idea a lot: it’s where he simply puts any great links he’s run across, with a quick description for each. Low maintenance, minimal effort, and useful & interesting, at least to me. It’s about game design and related topics (and unrelated ones) as much as graphics. This is one of those “everyone who finds cool stuff on the internet should do this” concepts, as far as I’m concerned. Sure, there’s del.icio.us and similar social bookmarking sites, but a blog lets me know when there’s something new from someone I respect.

Morgan is one of those uncommon people who has considerable industry experience (e.g. “Titan Quest”) while also being in the academic world. He’s a coauthor of the new book Creating Games, which I had been jumping around inside and sampling snippets, and am now sitting down and reading for real. It is aimed at being a book for teaching a college course on making games, both board- and video-, giving a number of schedules for 3 to 4 week projects and worksheets for these. However, these are appendices; the focus of the book is well-informed surveys of a wide range of game design and creation practices. The first chapter has a great startup project for small groups in a class: “here are some dice and pieces of different colors, some paper – go, make a game in 7 minutes.” Anyway, not graphics related per se, but there’s certainly a lot about the computer games industry inside, much of it technical and practical. My favorite illustration so far is the dependence graph amongst the art assets for Spiderman 3, Figure 3.8 – daunting. You can look inside at Amazon. Me, I’m an avid boardgamer (I was up too late last night playing Dominion with Morgan and Naty Hoffman – consider me entirely biased), so I’m enjoying reading it and thinking maybe I should try to design a game…

Graphics Gems Excerpts

I noticed (or maybe re-noticed) recently that 4 of the 5 Graphics Gems books are excerpted on Google Books. I’ve added links to the excerpts from the Graphics Gems repository. Which made me wonder, can you look inside these books on Amazon? Indeed you can. So I’ve also just added links to Amazon’s Look Inside pages. Between these two resources you can now pretty much read any article from these books online, one way or the other. Handy.

RT Quake Wars update

Daniel Pohl has a new article at his site about his efforts to ray trace the game Quake Wars at interactive rates. This article is not heavy-duty, and has some interesting tidbits and visualizations. For example, it turns out that cut-out textures (used for making trees, for example) are pretty expensive for his ray tracer. The problem is that a new ray must be spawned after each intersection is detected. The headache for ray tracing (at least in this system) is that the texture itself is not accessed at the time of intersection – deferred shading, essentially. So the ray tracer does not know that the ray has, in fact, not hit anything (i.e., hit a fully-transparent texel) and could continue unaffected. He also talks about other optimizations that have helped and might help in the future.

What I find exciting about Daniel’s work is that he’s working with data that was optimized for rasterization, not for ray tracing. If ray tracing was suddenly 10x faster than GPU rasterization with existing hardware in, say, DirectX 11 (keep dreaming), it wouldn’t matter that much in the short-term. For most companies there’s a lot of investment in training, workflows, and tools for producing games. For example, look how long it took normal mapping to become a mainstream feature, well after all new GPUs could support it (around 2002 with SM 2.0). So, ray tracing existing models I see as useful for determining whether ray tracing is feasible for current games, while also finding pain-points (such as cutout textures) that will be present in artist-generated content for some time to come.

This, That, and the Other

Time to clear the collection of links and tidbits.

First, two new graphics books have come to my attention: Essentials of Interactive Computer Graphics and Computer Facial Animation, Second Edition. The first is an introductory textbook for teaching, well, just that. Real-Time Rendering was never meant as an introduction to the field of interactive graphics, we’ve always seen it as the book to hit after you know the basics. The Essentials book is squarely focused on these basics, and is more event-oriented and application-driven: GUIs and MFC, instancing and scene graphs, the transformation pipeline. It’s truly aimed at computer graphics in general, not 3D lit scenes. Shading is barely mentioned, for example. The book comes with a CD of software libraries developed in the latter half of the book. See the book’s website for much more information and supplemental materials (e.g. Powerpoint slidesets for teaching from the book!).

Computer Facial Animation is an area I know little about. Which makes this book intriguing to page through -how much there is to know! The first few chapters are dedicated to anatomy and early ways of recording facial expressions. The rest covers all sorts of areas: speech synchronization, hair modeling, face tracking, muscle simulation, skin textures, even photographic lighting techniques. This is one I’ll leave on my desk and hope to pick up at lunch now and again (along with those other books on my desk that beg to be read, like Color Imaging – I need more lunches).

Which reminds me of this nice talk by Kevin Bjorke: Beautiful Women of the Future. The first half is more aesthetic with some interesting fact nuggets, the last half is a worthwhile overview of interactive skin and hair rendering techniques.

It’s worth noting that there are many computer graphics books excerpted on Google Books. Our portal page, item #6, lists a few good ones.

Game Developer Magazine’s Front-Line Award Winners have been announced. Our book was nominated, but to be honest I’m not terribly upset it didn’t win (our second edition won it before); instead, a new book on (video)game design got the honors in the book category, The Art of Game Design. The rest of the award winners are (almost) no doubt deserving, but the winner list provides little new information. It’s the usual suspects: Photoshop CS3, Havok, Torque, Visual Studio 2008 (really? I’d go with Visual Assist X, which adds a bunch of useful bits to VS 2008 to make it more usable). I haven’t seen the Game Developer article itself, which should be more interesting to see the list of runner-ups.

Update: it’s a day later, and the Front Line awards article is available online. Good deal!

I just noticed that Jeremy Birn has been having lighting contests for synthetic scenes. Meant more for the mental ray users of the world, I like it just because there are some nice models to load up in my test applications.

We mentioned SIGGRAPH Asia before; see the papers collection here and some GPU-specific presentations here.

A fair bit going on in the blogosphere:

  • Christer Ericson has an article on optimizing particle system display. I hadn’t considered some of these techniques before.
  • Bill Mill has a worthwhile rant on publishing code along with research results. This often isn’t done, because there’s little benefit to the author. Some researchers will do it anyway, for various reasons (altruism, fame, etc.), but I wish the research system was structured to require such code. It’s certainly encouraged for the journal of graphics tools, for example, but even then the frequency is not that high.
  • Wolfgang Engel has lots of posts about programming for the iPhone & Touch; I was more interested in his comments about caching shadow maps.

Everyone should know about the Steam Hardware Survey. The cool thing is that they recently started adding a history for some stats and, dare I dream it?, pie charts to the site. Much easier to grok at a glance.

Tutorials galore:

Need a huge (or medium, or small), free texture of the whole earth? Go here.

Google’s knol project collects short articles on various topics. Here’s a reasonable sample: a short history of theories of vision. To be honest, though, the site overall seems a bit of a dumping ground. This sort of lameness is proof why editorial supervision (either a single person or a wiki community) is a good thing.

DirectX 10 corrects a long-standing “feature” of previous versions of DirectX: the half-pixel offset. OpenGL’s always had it right (and there really is a right answer, as far as I’m concerned). I was happy to find this full explanation of the DirectX 9 problem on Microsoft’s website.

Our book had a little review in the February 2009 issue of PC-Gamer, by Logan Decker, executive editor, on page 80. I liked the first sentence: “I don’t know why I didn’t immediately set fire to this reference for graphics professionals the moment I saw all the equations. But I actually read it, and if you skip the math bits as I did, you’ll get brilliantly lucid explanations of concepts like vertex morphing and variance shadow mapping—as well as a new respect for the incredible craftsmanship that goes into today’s PC games.”

This one’s made the rounds, but just in case: the Mona Lisa with 50 semi-transparent polygons, evolved (sort-of). Here’s a little eye candy (two links). Plus, panoramas galore.

Finally, guard your dreams.