OpenGL 4+ : the first steps

I got a little depressed when I felt the learning curve, going from OpenGL 2 to more recent versions. NeHe‘s tutorials are deprecated and the current titles in the book stores take too much time to get to the “real stuff”. Luckily, the person running this tutorial site (According to NeHe, this guy’s name is “Damien”) offers a wide range of lessons in “modern” OpenGL to kick start your apprenticeship.  Not that the bigger books aren’t important, but as a hacker, I always learned by focusing my interest on building cool stuff first, then I crack open a book like OpenGL Superbible or the famous “Red book” to understand the more technical details.

And it’s not just about OpenGL, but also how to interact with other popular software packages like Blender.  There’s a nice tutorial on how to program your own OBJ format loader.  This gives a huge boost of confidence on what you can achieve and it adds the possibility to play and have fun with your code instead of watching rotating cubes.

I like the NASA 3D Resources page where you can use models of rockets and other space vehicles. International Space Station ? No problemo.  Convert to OBJ and voilà.

iss_wireframe_thumb

Next step: texturing.

For 15 years, I wanted to program my own raytracer …

narc-thumb-000014

Recommended by a friend, I checked out a site featuring a new, free and open-source Javascript superset called TypeScript, created by some developers at Microsoft.  It’s an interesting language for those of us who want Javascript to look more like an object-oriented language like C++.

But what really caught my attention was this sample code on the site that was an actual, living, breathing, raytracer.

OK, this doesn’t sound impressive to any of you, fine!  You probably rolled out your own in high-school, or in kindergarten for that matter.  But I’ve been struggling with some parts of it for the last 15 years because of my lack of math skills, to which I am slowly doing some catching up.  It took me several come-backs when, on an off, I would try to solve some basic stuff about shooting the darn rays.  And I didn’t want to just copy some code (there is plenty of raytracer code out code for free) but I wanted to understand what was going on.  Luckily, this one is simple enough for learning the basic nuts and bolts of raytracers, and so I gave it a shot and ported it from TypeScript to C++.  Porting also meant getting my hands dirty on the math because what was easily resolved in a TypeScript function didn’t mean that a C++ library call was equally available.  And TypeScript is still JavaScript so I had to really tear apart some of those embedded callbacks we love to hate when we’re dealing with this language for the first time.  Nevertheless, the port was successful and I am proud to show my first image with it (which, unsurprisingly, looks like the one from the Typescript site).

After poking around the Internet, I found that this TypeScript version was probably a port from this one written in C# by yet another prominent Microsoft developer.

My code is around 800 lines compared to the smaller size these versions have, 200 and 300 lines respectively.  I could work to make the code smaller, but it’s not my intention to publish it or anything, only to use it as a learning tool for better understanding graphics.

So while I didn’t program it from scratch, I think it’s the next best thing for learning how to program a raytracer.  I suggest you check that TypeScript code and make a port yourself.

The big question for me was “Why did it take me so long ? ” – besides having the attention span of a new-born puppy, jumping from project to project …

Part of the answer lies in a fundamental aspect of the raytracer: the camera.   I’ve noticed that tutorials on raytracers hardly ever discuss camera settings.  Camera positions, yes: the front, the up, the right, etc.  but not on how to align the rays in their starting positions in order to shoot rays.  I was always trying to achieve some form of circular disposition for my rays, naively following a sphere’s natural form, and that failed for some reason.  Imagine my surprise when I saw that this code didn’t really care about that.  It is flat based and each ray is sampled equally before rotation is applied to reach the desired angle.  Which kinda makes sense since it matches our “camera” view from a flat screen.

The results speak for themselves and I’m quite happy with it because I can focus on the more pleasing aspects of the job: showing off decent renderings, dealing with lights, shapes, etc.  Lots of work and study ahead but I never though it was going to be easy.

But regardless of the results, the code does present some challenges in the area of the camera: there is no parameter for setting a precise field of view (FOV), making some of the calculations seem arbitrary – like using 1.5 as a factor for the cross-product result of right and up, or the fact that the results can also be simplified because of an additional division by 2 on the raytracer’s screen operations.  Call it a gut feeling but I ran some measurements on the distance between each ray – or theta (θ) in trig parlance – and it is not equal amongst all rays.  The current camera has a FOV of about 41,11 degrees. I rendered a 10×10 image and the distance between the two furthest angles from the center compared to the the two closest ones drops to about 91%.  When I increased the number of pixels, my tests suggest a more significant drop, down to 87% on a 800×800 image.  Is it a “normal” way to set a camera ? The inevitable artifact of rendering to a flat screen ? I guess there’s always room for more personal research.

Lately, I’ve been playing with OpenGL 4.3.  This excellent tutorial on matrices in OpenGL really made my day.  I could probably apply some of that knowledge on raytracing.

Yet another recursive Sudoku solver

I haven’t published in two years and all I post today in a lousy Sudoku solver. Not that building one was essentially difficult. I always do some puzzle-driven program when I’m bored and just to prove myself that I can shake boredom out of me, I’ve decided to code it, publish it, transform it into some kind of tutorial and finally put it to rest so I can find something more productive to do. Nothing revolutionary here and not the fastest one around (I didn’t check, but I’m pretty damn sure it’s not). But as usual, someone may find it useful.

This is a tutorial on making a recursive Sudoku solver. It will brute force every number from 1 to 9 on an empty cell, starting from the first cell, until all free cells are filled and the Sudoku is resolved. It is written in C++. It assumes that the starting grid is correct and will provide only one solution.

Let’s start.

Loading and storing the grid.

First we need some way to store our grid and parse it. A simple grid in a text file should do it.

6 . 5 . . 3 . 4 .
. . . 9 4 . 5 . .
. 2 . . 5 . . . 3
. 9 . 8 . . . . 6
. . . . . . . . .
2 . . . . 6 . 9 .
3 . . . 7 . . 2 .
. . 8 . 1 9 . . .
. 7 . 3 . . 8 . 4

I use dots to represent empty cells. White-space (either “space” or “line feed”) will be ignored by the parser.

// A simple data reader: ASCII-based data from 1 to 9, 
// white-space separated, up to v.size() characters
// (a Sudoku grid has 81 values). You can either put '0'
// or '.' to represent an empty cell.
istream& operator >> (istream& iss, vector<int>& v)
{
	for (int i=0; i < v.size(); i++)
	{
		char x;
		iss >> x;

		if (x == '.')
			v[i] = 0;
		else
			v[i] = (int)(x - '0');
	}

	return iss;
}

As you can see, I overload an operator to create a simple call from the file stream to the vector. We parse each item as a char. Then determine if the cell is busy or free and transform the value to 0 if it’s the latter.

You can simply create your data file and do:

#include <fstream>
#include <vector>

using namespace std;

vector<int> grid;
grid.resize(81);
ifstream file("data");
file >> grid;

and everything is stored in the vector.

Printing the grid isn’t necessary, but I develop almost exclusively on CLI so it’s always nice to have a function that dumps any array onto the terminal or file just to check out things.

Validation routines

I’ve decided that the easiest way to keep these routines short and simple is to separate the validation of unique values, in a line or box, from determining all the available positions each line or box has.

Whether it’s from horizontal lines, vertical lines or in boxes, uniq() is essentially a function that verifies whether or not a list has unique numbers.

A single function should be useful for all checks. A bitset is a wonderful tool in C++ for this kind of trick.

// Check if a vector has unique numbers
// (but ignore zeros)
bool uniq(const vector<int>& vect)
{
   bitset<9> mybits;

   for (int i=0; i<9; i++)
   {
      int val = vect[i];

      // If value is 0 (empty), ignore
      if (val)
      {
         // If number is already found in the vector, 
         // the uniqueness test failed.
         if (mybits.test(val-1))
            return false;

         // Set number (base-0)
         mybits.set(val-1);
      }
   }

   return true;
}

Next, a generic function that will provide the vector for the above function is built. Note that this function doesn’t care if the check is horizontal or vertical or box bound, it will accept a group of positions, gather all values from those positions, and submit them to the uniq() function.

// Given a vector of grid positions, store their values 
// in a vector and check if they are unique.
bool Check(vector<int> pos)
{
	vector<int> vect;

	for (int i=0; i<pos.size(); i++)
		vect.push_back(grid[pos[i]]);

	return uniq(vect);
}

Naturally, the Check() function will be called by specific functions that deal with horizontal and vertical lines and boxes. These will group positions according to the current cell.

// Check the values of the row where <i> is located.
bool CheckHorz(int i)
{
	int j = i/9*9;	// row starting at no. j
	int k = j+9;	// row ending at no. k

	vector<int> pos;

	while (j < k)
		pos.push_back(j++);

	return Check(pos);
}

// Check the values of the column where <i> is located.
bool CheckVert(int i)
{
	int j = i%9;	// column starting at no. j

	vector<int> pos;

	while (j < MAX)
	{
		pos.push_back(j);
		j+=9;
	}

	return Check(pos);
}

As you can see, horizontal and vertical positions are trivial to calculate. The box-bound positions need a little help on this matter. I tried fantastical algorithms to offset small boxes around the grid, but a good old stencil is the best way to create an error-free list.

vector<int> boxes {

	0, 0, 0, 1, 1, 1, 2, 2, 2,
	0, 0, 0, 1, 1, 1, 2, 2, 2,
	0, 0, 0, 1, 1, 1, 2, 2, 2,
	3, 3, 3, 4, 4, 4, 5, 5, 5,
	3, 3, 3, 4, 4, 4, 5, 5, 5,
	3, 3, 3, 4, 4, 4, 5, 5, 5,
	6, 6, 6, 7, 7, 7, 8, 8, 8,
	6, 6, 6, 7, 7, 7, 8, 8, 8,
	6, 6, 6, 7, 7, 7, 8, 8, 8,
};

// Check the values of the box where <i> is located.
bool CheckBox(int i)
{
	int box = boxes[i];		// Get box no. at location i
	vector<int> pos;

	for (int j=0; j<MAX; j++)
	{
		if (box == boxes[j])
			pos.push_back(j);
	}

	return Check(pos);
}

Yes, I could have hard-coded the actual positions of each box into the grid and avoid the extra 72 iterations each time. But this is a nice visual presentation of the problem. Feel free to change this when you will be bored. 🙂

Solving the grid

Solving the grid is just a matter of jumping onto a cell, set the value to 1, check if it passes the three tests above and then go to the next cell – or simply change the current value to the next one in line and test again. If it still fails, this means that some of the numbers we set on previous cells are incorrect, we need to go back one step, change to the next value, come back and start again with new values. We can also go back all the way to the beginning if we have to and change the first number we put on cell 0 in order to solve the puzzle. If the current cell already has a value, one that was assigned by the original puzzle, then we jump to the next cell without hesitation.

void Solve(int i)
{
	// If we reach this, the Sudoku is solved.
	if (i == MAX)
	{
		PrintGrid(grid);
		exit(0);
	}

	// If cell already has a value, go to next cell
	if (grid[i])
		Solve(i+1);
	else
	{
		// We will iterate through all numbers and
		// set the current grid with this value.
		// If it passes all tests, we will go to 
		// the next cell.
		// If not, we simply set the cell back to <empty> and
		// go back to the previous cell.
		for (int j=1; j<=9; j++)
		{
			grid[i] = j;

			if (CheckBox(i) && CheckVert(i) && CheckHorz(i))
				Solve(i+1);
		}

		// Set to empty.
		grid[i] = 0;
	}
}

Once the supplied parameter reaches the magic number of MAX (or 81), then the Sudoku is solved. Print and abort. Mission accomplished.

Here’s the answer to the above grid, BTW:

6 1 5 7 8 3 2 4 9 
7 8 3 9 4 2 5 6 1 
4 2 9 6 5 1 7 8 3 
1 9 4 8 2 7 3 5 6 
8 3 6 5 9 4 1 7 2 
2 5 7 1 3 6 4 9 8 
3 6 1 4 7 8 9 2 5 
5 4 8 2 1 9 6 3 7 
9 7 2 3 6 5 8 1 4

Complete code here.

Happy Hacking.

return top