Parsing null terminated strings from a stream

During a project this week, my project partner and I ran into a problem that is somewhat interesting: how do you parse a string whose delimiters are null characters (‘\0’)? For example, how do you separate something like this:

This\0is\0a\0null\0character\0separated\0string

…into something like this:

This
is
a
null
character
separated
string

The problem is, of course, that you can’t put this into a std::string and iterate over the string to separate it out, because std::string terminates on the null character. So doing something like this:

std::string str = std::string("This\0is\0a\0null\0character\0separated\0string");

…results in str returning only "This" when it is used, and iterating would stop at the first null character.

So what can we do? Assuming our null terminated string is of type char *, we can actually use this string constructor behavior to our advantage by pointing at the beginning of each part of the string, then moving forward past the null terminator until we’ve reached the end of our character stream.

std::vector<std::string> splitOnNullTerminator(char *str, int length) {
    const char* p = str;
    std::vector<std::string> vector;
 
    do {
        vector.push_back(std::string(p));
        p += vector.back().size() + 1;
    } while (p - str < length);
    return vector;
}

This solution assumes, of course, that str is contiguous in memory (i.e. it’s a char array). But it is elegant, don’t you think?

Dot products and saving face

A few weeks back, someone asked me a question that, as someone who has worked with computer graphics quite a bit, I should have instantly known the answer to: how to compute a dot product of two vectors. Instead, I floundered for an answer and tried just about every way but the correct way I could conceive of because the correct way ‘didn’t look right’ to me. If you’ve ever spelled a word and then thought, ‘that doesn’t look right’ even though you have spelled it correctly, you’ll know what I mean.

In my defense, I had been running low on sleep and energy for a few weeks at that point due to working on a proposal.  So not only was I tired, I was cold on writing code. Worse, I hadn’t written a line of graphics-related code in months.

These are really just excuses though.  Eventually I slogged through to the correct answer, but I felt like I had completely misrepresented myself to this person.

So, without further ado, here is an example of how to compute a dot product between two vectors in C++:

vec4.h

#ifndef ____vec4__
#define ____vec4__
 
class vec4 {
private:
    float x, y, z, w;
public:
    vec4(float x, float y, float z, float w);
 
    float dot(vec4 v);
};
 
#endif /* defined(____vec4__) */

vec4.cpp

#include "vec4.h"
#include <stdio.h>
 
int main() {
    vec4 v1 = vec4(5.0f, 4.0f, 3.0f, 1.0f);
    vec4 v2 = vec4(1.0f, 2.0f, 3.0f, 1.0f);
    float dotProduct = v1.dot(v2);
    fprintf(stdout, "dot product: %.2f\n", dotProduct);
}
 
vec4::vec4(float x, float y, float z, float w) {
    this->x = x;
    this->y = y;
    this->z = z;
    this->w = w;
}
 
float vec4::dot(vec4 v) {
    float sum = 0.0f;
    sum += this->x*v.x;
    sum += this->y*v.y;
    sum += this->z*v.z;
    sum += this->w*v.w;
    return sum;
}

There are a dozen other methods that should be added to this class as well, like a cross-product, conversion to a unit vector, or a method for determining the angle between this vector and another, but it occurred to me that there are plenty of C++ libraries out there that already do this. However, is there one for Swift? I’m not sure – there are the beginnings of a Vector2D in the Swift Programming Language Guide, but it is clearly not finished.

I decided I’d mirror the functionality of the above C++ class in a Swift class in a playground as a start in the direction of creating a reusable vector class:

class Vector4D {
    var x, y, z, w : Float;
    init(var x : Float, var y : Float, var z : Float, var w : Float) {
        self.x = x;
        self.y = y;
        self.z = z;
        self.w = w;
    }
 
    convenience init() {
        self.init(x: 0.0, y: 0.0, z: 0.0, w: 0.0);
    }
 
    func dot(vec : Vector4D) -> Float {
        var sum : Float = 0.0;
        sum += self.x*vec.x;
        sum += self.y*vec.y;
        sum += self.z*vec.z;
        sum += self.w*vec.w;
        return sum;
    }
}
 
var v1 : Vector4D = Vector4D(x: 5.0, y: 4.0, z: 3.0, w: 1.0);
var v2 : Vector4D = Vector4D(x: 1.0, y: 2.0, z: 3.0, w: 1.0);
v1.dot(v2);

The code is remarkably similar to the C++ code, but there’s definitely some new flavors in there too.  I’ll come back to this later if it turns out that I need something like this.

Apple’s Swift language

I’ve been spending a bit of time over the last couple of weeks on learning the Swift language that Apple debuted at WWDC ’14.  So unfortunately, this post really doesn’t have much to do with computer graphics except that this will eventually become my entry point to working with Metal.  I thought I’d post a bit about Swift – in particular, a few things that have caught my eye from the language so far.  I’m not quite all of the way through the Swift iBook yet, so I’m sure I’ll miss a thing or two.

Swift switch cases do not fallthrough by default.

Swift throws away the old tradition of breaking (via the ‘break’ keyword) to prevent fallthrough and instead introduces a ‘fallthrough’ keyword. So instead of falling through by default, you must explicitly tell Swift that you would like your switch case to fallthrough to the next one. This should save a few headaches and make for tidier code for most people and for most usages.

Values in switch cases can be checked for inclusion within a range.

I can’t express how awesome I think this is.  As someone who’s written Java and C/C++ way too much, simply being able to use ranges is great, but being able to create switch cases for them is amazing.  Here’s what an example of what this might look like in Swift:

var numberOfDigits: String
switch count {
	case 0...9:
		numberOfDigits = "one"
	case 10...99:
		numberOfDigits = "two"
	case 100...999:
		numberOfDigits = "three"
	default:
		numberOfDigits = "many"
}
println("\(count) is a \(numberOfDigits) digit number.")

I can easily imagine that being able to use ranges might eliminate a number of if/else conditional statements in my code and replace it with readable, concise, optimized code.

If this is not enough for you to love Swift’s switch-case statements, keep reading.

You can use tuples to test multiple values in the same switch statement.

I’m sure there’s more than a few ways to use this in computer graphics.  For example, let’s say you want to work with a set of 3D vectors that should all be constrained from 0 to 1, inclusive:

let somePoint = (5.0, 5.0, -4.0) //our example vector
switch somePoint {
	case (0.0...1.0, 0.0...1.0, 0.0...1.0):
		//this vector is already good, let's use it
		doSomeProcessing(somePoint)
	default:
		//this vector needs to be converted
		var newTuple = convert0To1Range(somePoint)
		doSomeProcessing(newTuple)
}

Swift also has wildcards (using the _ character), so you could write a case like this one to satisfy only points on the y-z plane at x = 0:

	case (0.0, _, _):

Or you could bind those y and z values to be used within the case:

	case (0.0, let y, let z):
		println("on the y-z plane at 0.0, \(y), \(z)")

Or do a full blown conditional check as a part of the case:

	case (0.0, let y, let z) where y == z:
		//this case only runs if y is equal to z
		println("on the y-z plane at 0.0, \(y), \(z)")

And we’re not done yet…

You can type check within a case.

Swift uses the ‘as’ keyword to perform type conversions by downcasting.

	case 0 as Int:
		println("Integer zero.")
	case 0 as Double:
		println("Double zero.")
	case let someInt as Int where someInt > 0
		println("Positive integer.")

Optional types are pretty neat.

There’s a chance you could already know (or know someone who knows) C#.  From what I understand, Swift’s optional types has quite a bit in common with C#’s “nullable types”.

The general idea is that unless you specify a variable as having an optional type (with a ? modifier), the variable will be treated as though there is guaranteed to be a value stored in that location in memory.  However, an optional type can have a value of nil.  What’s more, there’s nothing preventing structures of optional types, resulting in ‘optional chains’.  For example:

var myInt = dataStructure?.subStructure?.intValue

The variable myInt gets an inferred type of Int?, or an ‘optional Int’. If either dataStructure or subStructure are nil, myInt gets set to nil and nothing else happens.  Nothing breaks, nothing throws exceptions, we just move on in our code. If both are not nil, myInt gets set to intValue. If we use myInt later on in our code, we would reference it with myInt?. If we are eventually certain that myInt has a value, we can forcibly unbox it with myInt!.

Swift will be another entry point for Metal.

When I first looked at the Metal API docs on Apple’s developer site, I was concerned.  Just about everything I came across was written with Objective-C, which is (in my opinion) not the easiest language to read or write.  Add to that a graphics API whose purpose is to work very close to the bare metal of a GPU, and you have a recipe for unreadable complexity.

But then when I was working within XCode 6 Beta 2, I saw that the game template allowed me to write code in Swift and use Metal for graphics.  I wanted to see what this looked like, so I created a project using the template.  But then something unexpected happened, although being a beta, I probably should have expected it: Metal could not be found by XCode.  In fact, the brand-new project could not compile, let alone run, and I hadn’t even typed anything yet.  What’s more, it turns out that XCode’s simulator won’t run Metal projects (yet) – you must have a device running iOS 8 beta to run them at all, and I don’t have a spare device at the moment.  I guess that XCode Beta just isn’t ready to do it all just yet.

In the meantime, I’m going to continue learning Swift, and when XCode is ready for me to write Swift/Metal, I’ll post some tidbits.

Quick update

Tonight, I added some quick and dirty soft shadows to Stained.  This had two effects:

  1. It made the sphere in the scene look more realistic by effectively diffusing them.
  2. It made the stained glass look more realistic by mixing some colors together while keeping some splashes of rich colors.

To accomplish this feat, I added some code to sample in the 6 basic directions relative to my light source, since technically my light source is not a point source, and has width, height, and depth, as well as the center point.  So these 7 checks I added are done in a loop in my shadow function, including the center point of the light, of course.  Normally, you would want to randomly sample dozens of these points, and probably in a greater number than 7, but this was fast and effective enough to create the basic desired effect in real-time in this case.

I’m actually really happy with the amount of improvement this one little adjustment has made to the scene.

Here’s the live shader (loads fastest in Chrome): Continue reading Quick update

Putting things together – Magnifying Lens (Fresnel) shader

In an effort to start putting concepts together, I’ve combined some parts from two of my initial efforts (the interactive sphere and Perlin noise) into a single demonstration.  I’ve also been interested in understanding how Fresnel reflection and refraction work, and so today I spent my afternoon assembling a fun shader to do all of this.  The subtle challenges inherent in this shader:

  1. Getting the Perlin noise to scroll infinitely to the right
  2. Using a Fresnel reflection and a Fresnel refraction
  3. Doing it all by ray tracing a sphere
magnifyinglens
Click on the image to see the “Magnifying Lens” Fresnel shader

Perlin Noise

Today’s entry is about Perlin noise – I came across Ken Perlin’s reference implementation of improved Perlin noise while looking for information about noise in general.  It was a complete mystery to me until I found The Perlin noise math FAQ, which explained the basics of how the noise algorithm works.

I wanted to put something together for a simple Perlin noise shader, and I made an attempt or two before getting frustrated by GLSL’s mod() function , which did not work exactly the way I expected (integer support?).  I probably could have kept going and hashed something out, but instead I decided to look up an implementation that I had seen referenced on ShaderToy elsewhere:

It worked right out of the box, and there really wasn’t much to it, so I threw in an improvised zoom effect, which I altered slightly to become more like a Ken Burns effect, although I’m really just flipping coordinates for the outputted buffer over time.  Here’s the result:

perlinnoise
Click on the image to see the “Perlin noise with a Ken Burns effect” shader

Perlin Noise – Ken Burns effect

RenderLoupe: the art and science of real-time computer graphics

I decided at some point in the last couple of weeks that I wanted to put together a site that would look at some of the real-time computer graphics gems that I’ve either created or come across in my work. RenderLoupe is the culmination of this desire.

Why “RenderLoupe”?  Well two reasons:

  1. To anyone knowledgeable about computer graphics, there’s an obvious play on words here with “render loop”.
  2. Since we’re going to be looking at things, and perhaps scrutinizing them, the idea of looking at things through a loupe really appealed to me.

To start off with, just to whet your appetite, I have links to a couple of sites that allow you to write GLSL in the browser:

  1. ShaderToy (a lot of times this is a very slow loading site, so be patient!)
  2. GLSL Sandbox Gallery

On ShaderToy, I wrote a couple of simple shaders to get started – if you’re interested in seeing “what is possible” in the browser, there are a lot of great examples.  The first one I wrote is an edge detection shader, which uses matrix convolutions, such as the Sobel kernel, to highlight places in the image where there is a significant change in luminance from one pixel to another.  I decided to include a number of other kernels as options.  The shader source is documented, so here you go:

simpleEdgeDetection
Click on the image to see the “Real-time edge Detection” shader

I also wrote a shader that casts rays at a sphere in real time.  You can drag the mouse and the eye/viewpoint will update accordingly:

simpleSphere
Click to see the “Simple sphere ray casting” shader (trace with no bounce)

The art and science of real-time computer graphics