Exercise for the Reader

November 27, 2008

There’s No Substitute for Triangles

Filed under: 3D Graphics — Tags: , , — Seth Porter @ 11:16 pm

Sometimes per-pixel lighting just can’t save you. That’s my final conclusion, but I thought the journey was interesting, and explored a few different ways of trying to figure out why your shaders aren’t doing what you expect.

This adventure started from a mistaken assumption. In a previous life, I worked a lot with texture mapping the world around a fixed viewpoint. In that setting, the actual geometry of the enclosing mesh doesn’t matter, as long as your texture is either pre-distorted (so that linear interpolation is geometrically correct) or sampled frequently enough (per-pixel computation to the rescue!). Somewhere along the line, I seem to have picked up the idea that as long as the outlines are correct, per-pixel computation will always let you reduce the geometry. That’s true for some extreme definitions of per-pixel computation (if you’re willing to do full per-pixel matrix computations, you can almost render an aligned quad and walk away); however, in the real world you have to be able to defer some computation to the vertex shader and take advantage of all that hardware linear interpolation.

Anyway, my goal is to draw cheap, correctly-lit cylinders, using as few triangles as possible. In the long-term, I want to use this technique for highly tessellated poly-lines, so there are serious upper bounds on the budget I can spend on each individual line segment. Thanks to my assumption above, I figured I should be able to get away with four points sampling a unit circle, and make up the difference in the pixel shader.

Per-pixel shading is necessary for this sort of task from the beginning; calculating color at each vertex just doesn’t cut it when you’re approximating non-linear shapes. Just for the record, though, here was the first result with per-vertex lighting of the “square cylinder”:

Per-Vertex Shading; 4-sided "cylinder"

Per-Vertex Shading; 4-sided

I figured that everything would be sorted out with per-pixel lighting. In practice, though, here were my results (followed by a high-tessellation version as the “right answer”):

Per-Pixel Shading; 4 sided "cylinder"

Per-Pixel Shading; 4 sided

Per-pixel; 2048-sided cylinder. The reference image.

Per-pixel; 2048-sided cylinder. The reference image.

These images look similar, but if you flip back and forth (I’ll try to get that working once I know WordPress a little better) you’ll see that the low-tessellation version has a band of brightness about a quarter of the way up the “cylinder”, while in the correct version, this is concentrated at the very bottom of the image.

(more…)

November 26, 2008

Justifying the Library Habit

Filed under: Development Infrastructure — Seth Porter @ 6:24 pm

I think we still tend to underestimate the importance of (code) libraries and how our code interacts with them. The only time I’ve written fan mail was to Steve Mcconnell after reading (and being blown away by) Code Complete; I asked him for his thoughts on how to write code which fully leverages libraries, but still retains some independence. In conversations at work and elsewhere, I’ve realized that I have an internal categorization of libraries which isn’t widely shared (perhaps for good reason). Be that as it may, it’s my blog, so I’m going to lay them out.

There are several different reasons for using a library; each needs to be accompanied by a different style of use. The different reasons also imply different levels of coupling between your code and the library. At one extreme, your code can be completely oblivious to the existence of a particular library (some pluggable image loader models, for example, which transparently expand the file handling capabilities of all applications). At the other limit, you explicitly assume throughout your application that a particular library is available. The first is clearly preferable, but there are many times when you’re forced to accept a degree of coupling for one reason or another. The key is to be honest about how dependent you are on a library, and make sure that there’s some inverse correlation between degree of dependency and the likelihood that you’ll need to replace that library. (more…)

November 25, 2008

F# Arithmetic Specialization Rocks!

Filed under: Functional programming, Numerical methods — Tags: , , — Seth Porter @ 2:17 am

With a title like that, you know you’re in for a rocking good time.

Anyway, every good side project needs at least one new language, and after a long time wandering in the imperative wasteland (C# and, more recently, Java), I decided to give F# a look. It’s amazingly production-ready and very nicely integrated with Visual Studio (syntax highlighting and IntelliSense in a type-theoretic language?!). I know, strong type models and a good interactive mode should leave you happy to work in Notepad, but I’ve gotten awfully used to support from a rich IDE. But what a thrill it was to see, in a nicely formatted tooltip no less, my function’s inferred type:

val myFun : 'a * 'a -> ('a -> 'b) -> ('b * 'b)

Anyway, fun is fun, but my theoretical reason for all this was to try out some numerical recipes without tying my hands too early (as far as working in single / double resolution, or even something more exotic like interval arithmetic). Without getting side-tracked with numerical methods, consider good old linear interpolation:

f(p0, p1, u) = p0 * (1-u) + p1 * u

where ‘u’ varies from 0 to 1, and ‘p0’ and ‘p1’ are the values you’re interpolating between. One thing to note is that ‘p0’ and ‘p1’ can, in general, be anything you want — floating point values, vectors, or anything that can be scaled (by ‘u’) and added together.

So, my first, simplest approximation was very straightforward:

let linearInterp0(p0, p1, u) = p0 * (1-u) + u * p1

Looks good, but the inferred type comes out as ‘val linearInterp0 : int * int * int -> int’. Hmm. Maybe I need to explicitly tell it to be more generic. But ‘let linearInterp0(p0 : ‘a, p1 : ‘a, u) = p0 * u + (1-u) * p1’ (where ‘a is a generic type; loosely equivalent to ‘T myFun<T>(T p0, T p1…)’ in Java) fails to compile, with the helpful warning that ‘1-u’ “causes code to be less generic than indicated by the type annotations”.

Fair enough, looks like that “1” is forcing everything to be an integer. (I discovered later that int is also the default type for under-specified math operations, but let’s keep things simple.) Changing it to ‘1.0’ gives me a type of ‘float * float * float -> float’, or ‘1.0f’ for ‘float32 * float32 * float32 -> float32’ (apparently F# uses ‘float’ for what I think of as ‘double’, and ‘float32’ for single-precision floats). But I want to operate on any of the above (and don’t forget about vectors!). There was also no obvious way to manage one type for P0 and P1, and also retain flexibility on whether to use singles or doubles for ‘u’, but one step at a time.

So, some Googling lead to this thread, which almost broke my spirit right there. (Note that the last reply, from “Andyman”, would have helped a lot, but wasn’t posted at the time.) Either you create your own “numeric” interface, and implement it for all the types you care about, or you use magic global associations functions and create pseudo-generic methods which fail at runtime if called with an inappropriate type. Anyway, I tried a trivial “sum” method using the GetNumericAssociation approach (if you’re following along at home, you’ll need to include a reference to FSharp.PowerPack.dll, and open the ‘Microsoft.FSharp.Math’ namespace):

let sumNA(p0 : 'a, p1 : 'a) =
    let numeric = GlobalAssociations.GetNumericAssociation<'a>()
    numeric.Add(p0, p1)

It has a wonderfully generic type, ‘a * ‘a -> ‘a (again, in Java terms something like ‘T myFunc<T>(T p0, T p1)’). In fact, it’s too generic; it will fail at runtime if GetNumericAssociation fails for the provided type. However, it works for float32 and float, so it’s worth seeing what we get out of the compiler. Using ILDASM on the compiled assembly, the truth comes out:

  IL_0000:  call       class [FSharp.Core]Microsoft.FSharp.Core.Option`1<
         class [FSharp.PowerPack]Microsoft.FSharp.Math.INumeric`1<!!0>>
         [FSharp.PowerPack]Microsoft.FSharp.Math.GlobalAssociations::TryGetNumericAssociation<!!0>()
  IL_0005:  call       instance !0 class [FSharp.Core]Microsoft.FSharp.Core.Option`1<
         class [FSharp.PowerPack]Microsoft.FSharp.Math.INumeric`1<!!A>>::get_Value()
  IL_000a:  ldarg.0
  IL_000b:  ldarg.1
  IL_000c:  tail.
  IL_000e:  callvirt   instance !0 class [FSharp.PowerPack]
         Microsoft.FSharp.Math.INumeric`1<!!A>::Add(!0,!0)

Without worrying about the details of the .Net assembly generics syntax, the key is in that last line — ‘callvirt’. We’re calling a virtual method defined in the ‘INumeric’ interface, albeit with some syntactic sugar. I could do that in C# (or even Java), with less confusion. We’ve also lost the nice equivalence of the mathematical definition and the source code. Sigh. I want something more like C++ templating, but with actual types (instead of almost-textual expansion and all the other downsides of C++).

(more…)

« Newer Posts

Blog at WordPress.com.