Designing a GPU-oriented geometry abstraction – Part Three

In this post, I want to propose an geometry abstraction along with an example on how it works. But first I’ll clarify the goals of the abstraction:

• Should support functional composition and transformation. This basically means that it will support operations like a + b where a and b are geometry values and the result is a geometry value or f(a) where f is a pure function from geometry value to geometry value.
• A geometry value can be rendered by one call without any other companion values.
• Very limited magic and hard coded properties. Only properties relevant for rendering, vertex position, pixel color, and topology, are semi-magical in that a render call will look for them. All other properties and all calculations, such as those that specify layout or apply lighting, are non-magical and expressed explicitly by manipulating/transforming geometry values.

The above goals ensure that the abstraction is easy to use and that we can easily modularize geometry-building code using standard in-language constructs such as procedures, objects, or functions (including high-order functions). Now, let’s introduce the abstraction via an example using a neutral syntax:

Designing a GPU-oriented geometry abstraction – Part Two.

My last post described the problem of crafting an appropriate geometry abstraction for Bling. Bling previously solved the code problem for vertex and pixel shading, but lacked decent geometry input abstractions as well as an abstraction that supported geometry shading. The last post proposes giving geometry its own abstraction, but I was a bit hesitant in including properties within the geometry, which leads to either a problem of flexibility or static safety. I think its time to back up a bit and describe the abstractions that are relevant to a traditional programmable rendering pipeline:

Designing a GPU-oriented geometry abstraction – Part One.

One the inputs of rendering via programmable shading on a modern graphics card is a collection of vertices associated with some per-vertex properties used in shader computations. When programming the GPU, this collection of vertices is commonly abstracted as a vertex buffer, which is essentially just a bag of bytes. The collection of vertices describes a primitive point, line, or triangle topology along with an optional index buffer (if triangle) that describes vertex sharing.  Again, the abstractions for describing these topologies are very weak and essentially amount to flags and arrays, although we can informally describe to the vertex buffer plus its primitive topology description as a geometry. Each vertex first individually undergoes processing in a vertex shader, and then (optionally) per-primitive (point, line, or triangle) in a geometry shader where a new geometry can be specified with fewer or more vertices or even a completely different topology. After vertex and geometry shading, the position of each vertex must be specified. Finally, each pixel of the rasterized primitive is processed by a pixel shader to determine its color. This is a simplification, the GPU supports other features such as instancing, where we reuse the vertex buffer multiple times in a single rendering, and geometry shader stream out, where we save the result of vertex/geometry shading for later re-use.

Swizzling in C# via Bling

Swizzling is a GPU-supported operation that allows you to cheaply reorganize and repeat elements of a vector during an operation. Given its efficiency, it is very important to support swizzling in a language that targets GPUs. HLSL has special syntax where any scalar or vector can be swizzled; e.g., p.xyz takes a vector4 and returns its first 3 elements as a vector3, p.zyx reverses these elements, and p.xxy repeats the first element twice then pairs the result with the second element. Through C# extension methods, we can define some common swizzle combinations (e.g., xyz and zyx), but with repeated elements and considering vectors of size 4 (the max that is supported by GPUs), we’d have to define way too many extension methods to be complete. Rather, I’ve defined a few overloaded extensible extension methods where the swizzle indices are indicated as type parameters; e.g., considered swizzled quaternion transformation in C#:

Double3Bl m = -q.XYZ().Square;
m = m.Sw<Y,X,X>() + m.Sw<Z,Z,Y>();

Double3Bl n = q.W * q.XYZ();
Double3Bl r = q.Sw<X,X,Y>() * q.Sw<Y,Z,Z>();
Double3Bl t = r.Sw<X,Z,Y>() - n.Sw<Z,X,Y>();
Double3Bl u = n.Sw<Y,Z,X>() + r.Sw<Y,X,Z>();
Double3Bl p = argB;
Double3Bl v = m * p.XYZ() + t * p.YZX() + u * p.ZXY();
return 2d * v + p.XYZ();

Sometimes we use extension methods (e.g., XYZ()), and sometimes we use the Sw method, which is slightly more verbose but still reasonably concise. For type safety, we define the X, Y, Z, and W classes so that X <: Y <: Z <: W, then if the target is a 4 vector, the type parameter bounds for all the swizzle parameters is W , while if it’s a 2 vector, the type parameter bounds for all the swizzle parameters is Y, disallowing Z and W. The X, Y, Z, and W classes can then be instantiated as type parameters to determine the index they represent.

Announcing Bling 3.1!

I’d like to announce a new version of Bling (http://bling.codeplex.com/) with maturing experimental support for retained and programmable 3D graphics. On the one hand, we have immediate-mode programmable graphics in Direct3D, which is flexible and fast but is more difficult to program. On the other hand, we have retained mode graphics in WPF 3D, which is easier to program but is less flexible and not as fast as straight Direct3D. Bling is a side project that experiments with something in between the two: the ease of programming that a retained graphics model provides with the flexibility and performance that comes with the ability to express custom pixel and vertex shaders.  Bling is built on top of Direct3D via the WindowsAPI Code pack, the DLR, and WPF.

Long description/example for those that are interested:

What is a programmable abstraction?

In a recent blog post I described the principles behind Bling’s design. The primary principle is preferring programmable over fixed abstractions. But I feel that my definition of a programmable abstraction is so far unsatisfactory and undeveloped. To converge on a better definition, let’s first start at the beginning and discuss abstraction.

Announcing Bling 3!

I’d like to announce a newly rewritten release of Bling with many improvements and exciting new features. Bling is a novel experiment in how WPF/UI programming can be enhanced via a lightweight domain-specific language hosted completely within C#. Bling basically changes the meaning of statements and expressions to do more that is otherwise possible with normal values in C#; e.g., a + b no longer means add the value of “a” to the value of “b,” but rather it creates tree that we can then transform into a databinding relationship, HLSL code, and so on. We exploit this to reduce or completely UI boilerplate code; e.g., no more value converters, no more HLSL code, no more C# shader classes, etc…Bling 3 goes farther with this style of programming through the addition of lifted functions (so f(a) also creates a tree!). For more details, see my blog.

A web browser suitable for Harry Potter in WPF!

Daily Prophet eat your heart out! Here is a prototype web browser we threw together in Bling:

Bling Manifesto

User interfaces toolkits are becoming increasingly complicated through frameworks with rigid architectures and numerous high-level abstractions that must be customized down to meet application requirements. In contrast, modern low-level 3D graphics toolkits are moving en masse away from similar fixed function APIs to flexible programmable shader models. For example, rather than call a point light on diffuse material fixed function, one would instead encode the math for this operation in a shader. Custom forms of lighting are easily expressed through new math. Can similar model work for user interfaces? Consider layouts: a few fixed kinds of panels (stack, flow, etc…) can be configured and composed to implement various kinds of layouts. The number of fixed layouts combined with their customization options make such APIs very complicated and difficult to learn and use. However, the ability to express layout math can accommodate any kind of layout, and since the layout is being expressed as math their are no customization options to learn and use. This brings us to the first principle of Bling’s design: to optimize for flexibility and simplicity, support bottom up construction of “programmable” abstractions as opposed to the top-down customization of high-level fixed abstractions.

The drawback of such programmable abstractions is convenience and repetition—no one wants to reinvent the wheel while inventing an effectively round wheel requires complex processes. Consider implementing a custom layout algorithm in WPF, boilerplate make expressing programmable layouts difficult and repetitive: one must define a new panel, define minimum, maximum, and preferred sizes, and deal manually with layout changing events. Later on, this panel can only be reused in its entirety: parts of the algorithm must be re-implemented in a new panel. Likewise, boilerplate in Direct3D makes it difficult to setup even simple scenes, while boilerplate to interface with shaders prevents the modularization of lighting math that can run either on the CPU or GPU. The solution to the boilerplate problem is to eliminate boilerplate. For example in expressing layouts, convenient and concise databinding to arbitrary expressions makes it practical to encode arbitrary layout constraints that automatically react to dynamic changes. Likewise, the direct expression of shader code regardless of whether on the CPU or GPU allows for the modularization of lighting code into simple functions. This brings us to the second principle of Bling’s design: avoid inconvenience and repetition through boilerplate-hiding abstractions such as those concerning databinding or function composition. Code can then simply be organized into methods or functions.

Other Bling principles:

• To reduce confusion and keep the API as small and simple as possible, avoid redundant abstractions. For example, Bling does not support WPF storyboards because they overlap with databinding and explicit clocks to synchronize animations. Likewise, styles and triggers are easily replaced with constraints expressed via databinding.
• Focus on math. Almost everything in UI is math heavy, be it layout, animation, gradient blending, lighting, or physics.  Therefore it makes a lot of sense to optimize our abstractions for the expression and modularization of math. Bling includes an extensive math library, support for composite tuple, matrix, and function operations, simple algebraic solving, and symbolic derivation.
• Programmer friendliness through reasonable defaults. The days when a rectangle does not show up on the screen because the programmer forgot to set a stroke or color should be over! For programmer friendliness, Bling strives to ensure that all properties have default values, which then cause something noticeable to happen on the screen.
• Avoid abstraction performance penalty through dynamic code generation. Layers of abstraction can be expensive in performance critical parts of a UI, such as in layout, lighting, animation, or physics. This expense can be eliminated by using abstraction-heavy code to generate unabstracted code at run-time. Furthermore, code can be generated to run on GPUs as well as CPUs, leading to even greater performance improvements while isolating programmers from the otherwise inconveniences of GPU programming.
• To support code generation and symbolic analysis, manipulate expression trees, not values. Bling is like LINQ in that it is based on manipulating expression trees. Various tricks such as the use of operator overloading allows expression tree compositions to resemble comparable operations on values; e.g., a + b can form an addition tree node with a and b sub-trees.

Fun(ctional) graphics in C#!

Graphics programming often involves customizing and combining well known techniques as mathematic formulas and algorithms related to geometry, lighting, physics, and so on. For performance and architecture reasons, realizing these formulas in a real programming involves drastic transformations that results in code that is hard to read and write. For example, multiple graphics techniques are encoded into low-level pixel and vertex shader code in way that renders them unrecognizable.

One solution is to encode graphic techniques in a high-level functional programming language, where functions allow us to effectively represent, combine, and manipulate graphic techniques. Take for example lighting computations that can be represented as a function Position3D –> Normal3D –> InputColor –> ResultColor, which can then be combined via addition: take two lighting computations l1 and l2, where a succinct l1 + l2 expands to p –> n –> c –> l1(p)(n)(c) + l2(p)(n)(c). As graphics is math-intensive, it benefits dramatically from function representations.

Unfortunately, their are a couple of drawbacks to this approach. First, the execution of a functional program is drastically slower than imperative code. However, as most graphics computations are moving to GPUs via memory-restricted shader code, this problem can be solved by generating shader code from functional programs. Such is the approach taken by Conal Elliott’s Haskell-hosted Vertigo library done at MSR. In Vertigo, geometries can be expressed as parametric surfaces, surface normals for lighting are computed via symbolic differentiation. The second drawback is more one of familiarity: the techniques seem to require abandoning our existing mainstream languages and tools for dramatically different and less familiar languages such as Haskell. However, while functional programming definitely benefits from functional languages, functional programming techniques can definitely be applied in more familiar languages. As a mainstream language, C# even provides a lambda construct to support programmers who want to dabble in functional programming; e.g., by using LINQ to query databases.