mercredi 4 mai 2011

Generating normals on the GPU from a height map

While reading Shader X7 I stumbled upon the article "Dynamic Terrain Rendering on GPUs Using Real-Time Tessellation" (if you don't have Shader X7 yet, get it from amazon, it's a must-read).

In the article, Natalya Tartarchuk describes a way to shader such dynamic terrain that computes the normal on-the-fly.
This is very interesting since it could allow one to dynamically modify the height map and have the normals adjust automatically.
After spending a few hours debugging the normals I finally got something visually pleasing, although I've noticed a few artifacts.
After some more testing I've noticed that there is some error involved in computing the normals on the GPU (compared to the reference algorithm on the CPU).

The first image is the reference image, the normals have been generated on the CPU using the central difference algorithm.
In order to visualize the normals, they are moved into the [0,1] range by doing Normal * 0.5 + 0.5:

Reference normals generated on the CPU

The second picture is ATI's algorithm running on the pixel shader.
I had to tweak some of their variable since it seemed to rely on "magic" (but documented) value:

ATI's algorithm

The following picture shows the error between the normals computed as GPUNormal - CPUNormal:

Divergence from CPU normals. Grey areas mean error = 0 (since 0 * 0.5 + 0.5 = 0.5).

The third picture is the central difference algorithm ported on the GPU and running in the pixel shader.

The normals generated by the central difference algorithm in the pixel shader

The resulting error

My implementation of the central difference algorithm on the GPU must be pretty bad considering the divergence. I also tried the two algorithms on the vertex shader but sadly the error was just too great (except on the flat plane).

Now the question is, is it worth it to generate the normals on the GPU ?
I would say, if you're not having a dynamic terrain, you're better off with the normals on the CPU since it leads to much greater visual quality and won't steal one of those precious sampler slot so needed on SM3 hardware.
One advantage of generating the normals on the fly could be to reduce the size of the vertex buffer (take out normal + tangent from the vertex declaration => up to 6 floats per vertex removed) but that is to be balanced with the size of the height map.

mercredi 16 mars 2011

Circumventing the C# reference to reference problem

Recently I have been working on a simple recursive descent parser in C# .Net 4.0 and I encountered an error I did not expect; the following is not valid C#:

Rule integer, factor, expression, term;

integer = +Parser.digit_p();
   
factor = integer
 | Parser.ch_p('(') + expression + Parser.ch_p(')')
 | (Parser.ch_p('-') + factor)
 | (Parser.ch_p('+') + factor);
term = factor *((Parser.ch_p('*') + factor) | (Parser.ch_p('/') + factor));
expression = term * ((Parser.ch_p('+') + factor) | (Parser.ch_p('-') + factor));

This makes sense because we cannot use the rules before they have been initialized !
In C++ we'd just take a reference or pointer to the rule until they are defined; but this does not work in C#.

Instead I had to create a simple RuleRef class as follow:
public class RuleRef
{
 private Rule ptr;

 public Rule Value
 {
  get
  {
   return ptr;
  }

  set
  {
   ptr = value;
  }
 }

 public static implicit operator Rule(RuleRef r)
 {
  return r.Value;
 }

 public RuleRef()
 {

 }

 public RuleRef(Rule value)
 {
  ptr = value;
 }

 public static RuleRef operator +(RuleRef lhs, RuleRef rhs)
 {
  return new Sequence(lhs, rhs);
 }

 public static RuleRef operator +(RuleRef lhs)
 {
  return new OneOrMore(lhs);
 }

 public static RuleRef operator |(RuleRef lhs, RuleRef rhs)
 {
  return new Or(lhs, rhs);
 }

 public static RuleRef operator &(RuleRef lhs, RuleRef rhs)
 {
  return new Sequence(lhs, rhs);
 }

 public static RuleRef operator *(RuleRef lhs, RuleRef rhs)
 {
  return new Sequence(lhs, new ZeroOrMore(rhs));
 }
}

This allow me to then write:
RuleRef integer = new RuleRef();
RuleRef factor = new RuleRef();
RuleRef expression = new RuleRef();
RuleRef term = new RuleRef();

integer = +Parser.digit_p();
   
Rule _factor = integer.Value.WithAction(DebugPrint)
 | Parser.ch_p('(') + expression + Parser.ch_p(')')
 | (Parser.ch_p('-') + factor)
 | (Parser.ch_p('+') + factor);

Rule _term = factor *((Parser.ch_p('*') + factor) | (Parser.ch_p('/') + factor));

Rule _expression = term * ((Parser.ch_p('+') + factor) | (Parser.ch_p('-') + factor));

// Resolve the references to their correct values
factor.Value = _factor;
term.Value = _term;
expression.Value = _expression;

In the next post I will detail my simple recursive descent parser entirely written in C#/Linq.