Tessellation

You are currently browsing articles tagged Tessellation.

We all have dumb little blind spots. As a kid, I thought “Achilles” was pronounced “a-chi-elz” and, heaven knows how, “etiquette” was somehow “eh-teak”. When you say goofy things to other people, someone eventually corrects you. However, if most of the people around you are making the same mistake (I’m sorry, “nuclear” is not pronounced “new-cue-lar”, it just ain’t so), the error never gets corrected. I’ve already mentioned the faux pas of pronouncing SIGGRAPH as “see-graph”, which seems to be popular among non-researchers (well, admittedly there’s no “correct” pronunciation on that one, it’s just that when the conference was small and mostly researchers that “sih-graph” was the way to say it. If the majority now say “see-graph”, so be it – you then identify yourself as a general attendee or a sales person and I can feel superior to you for no valid reason, thanks).

Certain spelling errors persist in computer graphics, perhaps because it’s more work to give feedback on writing mistakes. We also see others make the same mistakes and assume they’re correct. So, here are the two I believe are the most popular goofs in computer graphics (and I can attest that I used to make them myself, once upon a time):

Tesselation - that’s incorrect, it’s “tessellation”. By all rules of English, this word truly should have just one “l”: relation, violation, adulation, ululation, emulation, and on and on, they have just one “l”. The only exceptions I could find with two “l”s were “collation”, “illation” (what the heck is that?), and a word starting with “fe” (I don’t want this post to get filtered).

The word “tessellation” is derived from “tessella” (plural “tessellae”), which is a small piece of stone or glass used in a mosaic. It’s the diminutive of “tessera”, which can also mean a small tablet or block used as a ticket or token (but “tessella” is never a small ticket). Whatever. In Ionic Greek “tesseres” means “four”, so “tessella” makes sense as being a small four-sided thing. For me, knowing that “tessella” is from the ancient Greek word for a piece in a mosaic somehow helps me to catch my spelling of it – maybe it will work for you. I know that in typing “tessella” in this post I still first put a single “l” numerous times, that’s what English tells me to do.

Google test: searching on “tessellation” on Google gives 2,580,000 pages. Searching on “tesselation -tessellation”, which gives only pages with the misspelled version, gives 1,800,000 pages. It’s nice to see that the correct spelling still outnumbers the incorrect, but the race is on. That said, this sort of test is accurate to within say plus or minus say 350%. If you search on “tessellation -tesselation”, which should give a smaller number of pages (subtracting out those that I assume say “‘tesselation’ is a misspelling of ‘tessellation’” or that reference a paper with “tesselation” in the title), you get 8,450,000! How you can get more than 3 times as many pages as just searching on “tessellation” is a mystery. Finally, searching on “tessellation tesselation”, both words on the same page, gives 3,150,000 results. Makes me want to go count those pages by hand. No it doesn’t.

One other place to search is the ACM Digital Library. There are 2,973 entries with “tessellation” in them, 375 with “tesselation”. To search just computer graphics publications, GRAPHBIB is a bit clunky but will do: 89 hits for “tessellation”, 18 hits for the wrong one. Not terrible, but that’s still a solid 20% incorrect.

Frustrum - that’s incorrect, it’s “frustum” (plural “frusta”, which even looks wrong to me – I want to say “frustra”). The word means a (finite) cone or pyramid with the tip chopped off, and we use it (always) to mean the pyramidal volume in graphics. I don’t know why the extra “r” got into this word for some people (myself included). Maybe it’s because the word then sort-of rhymes with itself, the “ru” from the first part mirrored in the second. But “frustra” looks even more correct to me, no idea why. Maybe it’s that it rolls off the tongue better.

Morgan McGuire pointed this one out to me as the most common misspelling he sees. As a professor, he no doubt spends more time teaching about frusta than tessellations. Using the wildly-inaccurate Google test, there are 673,000 frustum pages and 363,000 “frustrum -frustum” pages. And, confusingly, again, 2,100,000 “frustum -frustrum” pages, more than three times as many as pages as just “frustum”. Please explain, someone. For the digital library, 1,114 vs. 53. For GRAPHBIB I was happy to see 42 hits vs. just 1 hit (“General Clipping on an Oblique Viewing Frustrum”).

So the frustum misspell looks like one that is less likely at the start and is almost gone by the time practitioners are publishing articles, vs. the tessellation misspell, which appears to have more staying power.

Addenda: Aaron Hertzmann notes that the US and Britain double their letters differently (“calliper”? That’s just unnatural, Brits). He also notes the Oxford English Dictionary says about tessellate: “(US also tesselate)”. Which actually is fine with me, except for the fact that Microsoft Word, Google’s spellchecker, and even this blog’s software flags “tesselate” as a misspelling. If only we had the equivalent of the Académie française to decide how we all should spell (on second thought, no).

Spike Hughes notes: “I think the answer for ‘frustrum’ is that it starts out like ‘frustrate’ (and indeed, seems logically related: the pyramid WANTS to go all the way to the eye point, but is frustrated by the near-plane).” This makes a lot of sense to me, and would explain why “frustra” feels even more correct. Maybe that’s the mnemonic aid, like how with “it’s” vs. “its” there’s “It’s a wise dog that knows its own fleas”. You don’t have to remember the spelling of each “its”, just remember that they differ; then knowing “it’s” is “it is” means you can derive that the possessive “its” doesn’t have an apostrophe. Or something. So maybe, “Don’t get frustrated when drawing a frustum”, remembering that they differ. Andrew Glassner offers: “There’s no rum in a frustum,” because the poor thing has the top chopped off, so all the rum we poured inside has evaporated.

Tags: , ,

Direct3D 11 adds three new pipeline stages, with the goal of enabling efficient tessellation of higher order surfaces. This is the Direct3D 10 pipeline, as shown in “Real-Time Rendering, 3rd Edition”:

Direct3D 10 Pipeline

The color of each stage indicates whether it is fully programmable (green), configurable (yellow) or fixed function (blue). The stages are described more fully in the “Graphics Processing Unit” chapter of the book. Note that the “Geometry Shader” stage is new to Direct3D 10, but the other stages have been in the pipeline for quite a while.

The Direct3D 11 pipeline adds three new stages between the vertex and geometry shader stages (framed in red). Two of the new stages are programmable (the hull and domain shader stages) and one is configurable (the tessellator stage):

Direct3D 11 Pipeline

This pipeline operates on meshes represented as a series of surface patches. Triangle and quad surface patches are primitives in Direct3D 11 (there is also a tessellated line primitive). The shape of each patch is defined by a number of control points. These control points are transformed, skinned and / or morphed one by one in the vertex shader.

The hull shader is called for each patch, using the patch control points from the vertex shader as inputs. The hull shader has two main responsibilities. The first is to (optionally) convert the control points from one representation (basis) to another. for example, it can implement the technique introduced in Loop and Schaefer‘s paper “Approximating Catmull-Clark Subdivision Surfaces with Bicubic Patches“. The control points are sent directly to the domain shader, bypassing the tessellator. The hull shader’s second responsibility is to compute appropriate tessellation factors, which are passed to the tessellation stage. This allows for adaptive tessellation, which can be used for continuous view-dependent LOD (level of detail). The tessellation factors are specified per patch edge, and range from 2 to 64. This means that each edge of the patch may be split into at least 2 (and as many as 64) triangle (or quad) edges.

The tessellator is a fixed-function (but highly configurable) stage, which uses the tessellation factors to tessellate (subdivide) the patch into multiple triangle or quad primitives. The tessellator does not have access to the control points – all tessellation decisions are made based on configuration and the tessellation factors passed on from the hull shader. Each vertex resulting from the tessellation is output to the domain shader. Only the patch parametrization coordinates are passed on for each vertex.

The domain shader operates on the patch parametrization coordinates of each vertex separately, although it can also access the transformed control points for the entire patch. The domain shader sends the complete data for the vertex (position, texture coordinates, etc.) to the geometry shader (or the clipping stage if no geometry shader is present). Effectively, it evaluates the surface representation at each vertex. Techniques such as displacement mapping can also be applied by this shader stage.

Although Microsoft gave an example using Catmull-Clark subdivision surfaces, the programmability of the pipeline enables other surface representations to be used. Alternatively, the tessellation stages can be turned off and traditional triangle or quad meshes can be used.

Tags: , , , , ,