Recently in Coder Category

It's affine transformation, but I want perspective

April 30, 2012 3:31 PM | No Comments | No TrackBacks

I'm writing a little software rasteriser which lets you apply an arbitrary transformation to a 2D image. This includes both translation, rotation, scaling and shearing (the affine transformations) as well as full perspective mapping.

There are a few tricks to do quick affine transformations which I won't go into here; they're pretty easy to find, online and in books. Essentially, you exploit the fact that opposite sides are parallel in the quadrilateral (or quad) that defines the boundaries of the transformed image.

What is harder to find is dealing with perspective mapping; at least, in a 2D context.

The mathematics of perspective

A perspective-mapped rectangle has one or two vanishing points; the point at which opposite sides of the rectangle meet. Objects which are regularly spaced apart will appear closer together the further away they are, such as the sleepers on a railway track:

Railroad at Sunset

Picture taken by Michael Wilson. Used under CC BY-NC-ND 2.0 license.

The further back you go, the smaller everything gets. More specifically, the apparent size of an object is inversely proportional to its distance, reaching its limit at the vanishing point where everything is infinitely small. Obviously we can't just linearly interpolate between the corners of our quad, like we can with an affine transformation; we need to include the depth information in our calculation. The interpolation equation (shamelessly lifted from Wikipedia) :

u^{}_{\alpha}= \frac{ (1 - \alpha ) \frac{ u_0 }{ z_0 } + \alpha \frac{ u_1 }{ z_1 } }{ (1 - \alpha ) \frac{ 1 }{ z_0 } + \alpha \frac{ 1 }{ z_1 } } where 0 \le \alpha \le 1 with endpoints specified by u_0 and u_1 .

Extruding flatland at an angle

So that's great, but how exactly do you get that depth variable z from a 2D quad? Consider the above equation. When z_{\{0,1\}} = 1 it is equivalent to linear interpolation. We know that the vanishing point is asymptotic and that the apparent size is inversely proportional to distance (or depth) - the latter is accounted for in the interpolation equation, so we need only select appropriate reference points.

Setting z_v = 0 to represent the vanishing point will give us an asymptote via division by zero. Setting z_0 = 1 will leave the point on the quad furthest from the vanishing point unchanged; now all we need is to find the depth of the point closer to the vanishing point z_1 where z_v \leq z_1 \leq z_0 .

Cross products and angry merchandise

We can find out if there is a vanishing point by using the vector cross-product. If you're familiar with the vector cross-product, feel free to skip a few paragraphs. Otherwise, here is its definition:

\vec{u} \times \vec{v} = (u_y v_z - v_y u_z) \mathbf{i} + (u_z v_x - v_z u_x) \mathbf{j} + (u_x v_y - v_x u_y) \mathbf{k}

This calculates the vector perpendicular to both \vec{u} and \vec{v} in three dimensional space. You will note that, in two dimensions, the z component is always zero, leaving us with the simplified equation

\vec{u} \times \vec{v} = (u_x v_y - v_x u_y) \mathbf{k}

which means it is also the magnitude of that vector. It can be considered a measure of 'perpendicularness', as is apparent when taking the cross-product of the unit vectors: \mathbf{i} \times \mathbf{j} = 1 and \mathbf{i} \times \mathbf{i} = 0 .

Diversion over. Take the vectors of two opposite sides of our perspective-mapping quad:

\vec{AB} & = (b_x - a_x, b_y - a_y) \\ \vec{DC} & = (c_x - d_x, c_y - d_y) \\ \vec{OA} & = (a_x, a_y) \\ \vec{OD} & = (d_x, d_y)

where \vec{OA}, \vec{OD} is the vector from the origin to points A and D, respectively. If the cross-product \vec{AB} \times \vec{DC} = 0 then the lines are parallel and there is no vanishing point; otherwise we may find the intersection by calculating the point at which the two line equations are equal:

\vec{OA} + \gamma \vec{AB} = \vec{OD} + \delta \vec{DC}

Cross both sides by \vec{DC} :

(\vec{OA} + \gamma \vec{AB}) \times \vec{DC} & = (\vec{OD} + \delta \vec{DC}) \times \vec{DC} \\ \vec{OA} \times \vec{DC} + \gamma \vec{AB} \times \vec{DC} & = \vec{OD} \times \vec{DC} + \delta \vec{DC} \times \vec{DC} \\ \gamma & = \frac{(\vec{OD} - \vec{OA}) \times \vec{DC}} {\vec{AB} \times \vec{DC}}

Making use of the cross-product identity \vec{DC} \times \vec{DC} = 0 .

Now we have our value for \gamma we may substitute it into the first line equation to find our intersection point, aka. the vanishing point:

(v_x, v_y) = \vec{OA} + \vec{AB} \frac{(\vec{OA} - \vec{OD}) \times \vec{DC}} {\vec{AB} \times \vec{DC}}

Note that if \gamma is negative then the intersection lies in the direction opposite \vec{AB} , making B the farthest point from the vanishing point and therefore the nearest point to us.

The depth equation

Now we may calculate the depth of the farthest point f by linearly interpolating between the nearest point to us (A or B as found in the last paragraph; referred to in the equations as n ) and our vanishing point v , and applying our depth formula. Remember that z_v = 0, z_0 = 1 .

f & = z_1 n + (1 - z_1) v \\ & = v + z_1 (n - v) \\ z_1 & = \frac{f-v}{n-v}

Tying it all together

Two-point Perspective, depth labelled

With two-point perspective, the depth is the same along each parallel edge, with the longest at z_0 and the other z_1 . However, three-point perspective places each corner at a different depth. We calculate the depth of the two points on the same line as the nearest point, and then calculate the final point's depth as the product of the two adjacent to it. (Two-point perspective is a special case of this method - can you see why?)

Three-point Perspective, depth labelled

Luckily for us, depth along these lines is a linear function - so we now have everything we need to map perspective. First, find the line upon which our u, v coordinates lie by interpolating by \alpha on opposite sides of the quad.

\vec{AB_{\alpha}} &= \frac{ (1 - \alpha ) \frac{ \vec{A} }{ z_A } + \alpha \frac{ \vec{B} }{ z_B } }{ (1 - \alpha ) \frac{ 1 }{ z_A } + \alpha \frac{ 1 }{ z_C } } \\ \vec{DC_{\alpha}} &= \frac{ (1 - \alpha ) \frac{ \vec{D} }{ z_D } + \alpha \frac{ \vec{C} }{ z_C } }{ (1 - \alpha ) \frac{ 1 }{ z_D } + \alpha \frac{ 1 }{ z_B } } \\ z_{AB} &= ( 1 - \alpha ) z_A + \alpha z_B \\ z_{DC} &= ( 1 - \alpha ) z_D + \alpha z_C

Now we can calculate u, v by interpolating along the line between those two points.

\vec{u_{\alpha}v_{\beta}} &= \frac{ (1 - \beta ) \frac{ \vec{AB_\alpha} }{ z_{AB} } + \beta \frac{ \vec{DC_\alpha} }{ z_{DC} } }{ (1 - \beta ) \frac{ 1 }{ z_{AB} } + \beta \frac{ 1 }{ z_{DC} } }

UV coordinate calculation

This just leaves one part left: how do we use these coordinates to render our image? And how do we actually render the image efficiently? This will be revealed in the next part coming soon...

A US keyboard with a UK pound sign

April 3, 2012 7:48 PM | No Comments | No TrackBacks

I bought a mechanical keyboard from the USA a few months ago and absolutely love the action on it. Of course, an American keyboard brings with it an American layout - and while the wide shift keys on both sides and the subtle positioning differences of the keys are nice to have, every Brit needs to be able to enter £ signs.

Ubuntu comes with enough layouts and the customisation provided by (X? Gnome?) to do this out of the box, but Windows was a little more tricky. The United States-International layout gave you a pound but also gave you a whole bunch of dead keys for entering accents - a total deal-breaker, since every time you press quote or apostrophe, it waits for you to enter a letter (to add an accent) or hit space if you just want a quote. The UK Extended layout manages to deal with this in a superior way, by adding accents only when you hit the Alt-Gr key as in (Alt-Gr + ^, e) for ê.

Fortunately, Microsoft provides a keyboard layout creator, so I duly modified the US-International layout to be more like UK Extended, using right Alt for dead key accents. Now I can (right-Alt + $) for a £ and enter quotes and apostrophes like a regular layout!

The best thing of all is that it’s easy to distribute the layouts. You can download my keyboard layout, run the installer, and have a pound-friendly American keyboard layout without any fuss. Hopefully this will save other people time searching for a solution.

Heavy-duty persistence for Lua

May 24, 2011 4:17 PM | No Comments | No TrackBacks

I was using Lua for my final year project, but found some bugs with the Pluto library on 64-bit systems.

Pluto lets you serialise almost any Lua object into a flat representation; tables, functions, even coroutines, which allowed me to recreate continuations in Lua, albeit with some limitations.

However, the library seemingly hadn’t been updated since early 2010, and there were a few problems. Digging on the lua-users mailing list I found that someone else had taken over maintenance and posted the code on github. If I’d found this earlier it would’ve saved me a lot of time!

Hopefully future users can find it more quickly: Pluto - Heavy Duty Persistence for Lua

God the Software Developer

June 30, 2010 11:32 AM | No Comments | No TrackBacks

Stolen off reddit:

Look, most new products spend YEARS in development - god only spent 6 days rushing out the entire universe, and only a single day on humans (if that). When you rush things out they contain bugs and after that you need to patch them and maintain them.

Adam and Eve were corrupted by a snake (worm) and everything went south from there - you can see it time and time again; god backed up his important documents and placed them in an ark and then formatted the world, before declaring he should never have to do it again, yet he reguarly formats mini sections of the globe in a haphazard manner.

Jesus represents a sort of Service Pack, however it is clear that after that God just sort of gave up and hasn’t bothered to make any updates since.

Lighttpd, PHP 5.3 and MySQL 5.1 on a small VPS

June 8, 2010 12:18 PM | No Comments | No TrackBacks

To save money, I decided to migrate several of my family’s websites to a VPS. Now, setting up lighttpd is a piece of cake, but because these websites are dynamic, database-backed affairs, you have to do a little more work. I might be a programmer, but I’m not really a Linux expert.

That said, it was relatively painless, and in contrast to some previous experience. Besides, who needs tech support if you have Google and a decent brain in your head?

Why Lighty?

Apache is very well known and full-featured. It’s also rather memory-hungry. Lighttpd has a far smaller memory footprint, but still has a lot of capability; if YouTube and Wikipedia prefer it over Apache, it’ll be just fine for my piddly little sites.

The smaller memory means I can get away with a smaller VPS. I’m using an incredibly inexpensive 128MB instance from Prgmr. Even that is overkill, but then I’m not using the server solely for websites.

Also, configuring lighty is pretty simple. I never had much fun configuring Apache.

Step 0: download all you require

I chose to build lighttpd and PHP from source for more control. For MySQL, I decided to install a package provided by the IUS Community Project (more details on doing this yourself here).

Step 1: get lighttpd working

Follow the guide, obeying the instructions for your particular distribution.

It would be wise to create a unprivileged user for lighttpd to run as. After installing,

addgroup www
adduser -g www -M www

Now let’s create somewhere for the websites to reside:

mkdir /var/www
mkdir /var/www/default
echo hello world >/var/www/default/index.html
chown -R www:www /var/www/default

Finally, setup lighttpd.conf (should reside at /etc/lighttpd/lighttpd.conf) with the following:

server.username = "www"
server.groupname = "www"
server.document-root = "/var/www/default/"

mimetype.assign = (
  ".html" => "text/html", 
  ".txt" => "text/plain",
  ".jpg" => "image/jpeg",
  ".png" => "image/png" 
)

Run /usr/sbin/lighttpd -D -f /etc/lighttpd/lighttpd.conf and try connecting to your server. If you get the ‘hello world’ message, everything is rosy. Press Ctrl+C to stop lighttpd and install the other bits.

Don’t forget to /sbin/chkconfig lighttpd on so that lighty runs on server startup.

Step 2: install MySQL

I did this from a package, so nothing more to say here than yum install mysql51 mysql51-server mysql51-devel.

It’s important you install the development package as PHP requires the MySQL libraries/header files for MySQL support.

After installation, run /usr/bin/mysql_secure_installation to finish setting up the database. (Very important!) Follow the prompts and accept their suggestions.

Check you can connect to the database with mysql --user=root --password. If everything’s fine, go create a database and a user account for your PHP website to use later.

Again, /sbin/chkconfig mysqld on.

Step 3: build and install PHP

yum install flex bison
tar xvjf php-5.3.2.tar.bz2
cd php-5.3.2
./configure --with-mysql
make
su make install
cp php.ini-production /usr/local/lib/php.ini

You probably want to pass more options to ./configure depending on what libraries you need support for, or alternatively don’t want support for. A full list is here. Configure will complain if it can’t find PHP’s dependencies, but it’s not too hard to sort out (hooray for package managers!).

Edit your lighttpd.conf to add the following:

server.modules += ( "mod_fastcgi" )

fastcgi.server = ( ".php" =>
                   ( "localhost" =>
                     (
                       "socket" => "/tmp/php.socket",
                       "bin-path" => "/usr/local/bin/php-cgi",
                       "bin-environment" => (
                         "PHP_FCGI_CHILDREN" => "16",
                         "PHP_FCGI_MAX_REQUESTS" => "10000"
                       ),
                       "bin-copy-environment" => (
                         "PATH", "SHELL", "USER"
                       ),
                       "min-procs" => 1,
                       "max-procs" => 1,
                       "idle-timeout" => 20
                     )
                   )
                )

This sets up FastCGI for use with PHP. You should restart lighttpd to make the changes take effect (/etc/init.d/lighttpd restart) and test if PHP is working in the classic manner (echo <?php phpinfo() ?> >/var/www/default/phpinfo.php). Go to http:///phpinfo.php and see what happens!

Now go and configure to your heart’s content. Have fun!

Things I do

I use mod_rewrite, mod_redirect and mod_accesslog, among others. As you can see, lighty is quite powerful.

# Redirect subdomainless addresses to their www equivalents
$HTTP["host"] =~ "^([^.]+)\.(com|co\.uk|net)$"{
  url.redirect            = ( "^/(.*)" => "http://www.%0/$1" )
}

# Rewrite subdomains.domain.com to doc-root/subdomain
$HTTP["host"] =~ "^(.*)\.starfishgames\.co\.uk$" {
  server.document-root = "/var/www/starfishgames.co.uk/pages/"
  url.rewrite-once = ( "^/(.*)" => "/%1/$1" )
  accesslog.filename   = "/var/www/starfishgames.co.uk/access.log"
}

Raytracer in Lua, update

January 21, 2010 12:29 PM | No Comments | No TrackBacks
I'm actually making a PDF of this for my uni course, which I shall display / break up into bits when it's done. You'll have to wait a few days for that, though - be patient.

Good news, though; LuaJIT has just received all the sponsorship it had asked for to create a 64-bit version! I don't know a great deal about the differences between x86 and x86-64, but having seen some of the unique compilation and optimisation methods employed in LuaJIT, I'm rather excited to see what kind of tricks he can wring out of the 64-bit instruction set.

NP-complete pain in the neck

January 16, 2010 2:16 AM | No Comments | No TrackBacks
When I was a kid, I often asked "why" or "what" questions. "Why is the sky blue", "what's in this box", "why can't I have another chocolate", etc. and the answer that would infuriate me the most was "not telling!", or even worse, "because!" Yeah, okay, but WHYYYyyeeeeeeeee-aaaayyyyyyyyy? *pout*

I wonder if mathematicians feel the same way when they're faced with things like NP-complete problems.

"Yes, there is a solution to this, but hell if I'm going to tell you what it is."

"Aww, meanie! Is this a solution?"

"No."

"How about this?"

"Nope."

"Okay... um, this one?"

"No."

"What abou-"

"Nor that."

"Then WHAAAAT IIIIIS IIIIIIIIT?!" *pout*


The best you can hope for is knowing when a problem falls into that category and steering well clear of it. Or be smart enough to discover P = NP, but I won't hold my breath.

Raytracer in Lua, part 0

December 30, 2009 7:14 PM | 1 Comment | No TrackBacks
In which I learn about metamethods, try my best to restrain myself from abusing them, and get an opportunity to hurl more abuse at Java

I fancied learning a new language, and needed an excuse to do it. Fortunately, I have been assigned to create a raytracer. We'd already discussed the mathematics of it in class, and the end result is fairly obvious, so there shouldn't be too much frustration caused by boxing myself into a design corner accidentally. What better opportunity?

There were two languages hovering in my mind, Lua and Scala. Well, raytracers need performance, and LuaJIT was far more promising in this respect than Scala, so the choice was obvious. It turns out Lua is an amazingly simple language - for something that isn't Lisp or Brainfuck, at any rate.

This also means there isn't any built-in object system, should you want one. Strings are strings, functions are first-class (yay!), integers are doubles (that's much better than it sounds, by the way) and tables are the only data structure you get to play with. Tables are arrays and/or dictionaries, and while the way you access array and dictionary elements are the same - var[x] - they exist independently, for the most part, so your fears of hash-table-backed arrays are unfounded.

You also get to access dictionary elements using var.element, which is equivalent to var["element"] - a nice bit of syntactic sugar which JavaScript also has, and helps you feel as if you're dealing with well-defined objects rather than key/value stores. You can also duplicate JavaScript's prototype-oriented system very easily in Lua (more later). However, that's where the similarity ends.

Along with tables, you also get metatables. They let you customise the behaviour of a table, remapping operations upon it with your own functions. Think operator overloading in C++, except in a dynamic language. Importantly, you get to overload key accesses and writes, though only for keys that don't exist in the table inspected (for performance reasons if anything else). For example, we try to access foo["abc"], but foo doesn't contain abc. So, we call foo's metamethod for looking up table keys, which simply returns the value of the key in another table, bar. Ta-da, you've just inherited the keys of bar for free! You can do more complicated things, if you wish - but use your power with restraint.

I've seen far too many people condemn operator overloading in C++ - and often for good reason, since there are many things to consider, and many assumptions must be made such as the burden of object allocation, exceptions, and dealing with the sometimes-baroque overload resolution rules.

In Lua, however, you have garbage collection, a well-defined exception system (die horribly), and the simple rule of 'call the left object's metamethod, if it doesn't have one, call the right object's metamethod, if that doesn't have one then die horribly'. It's not complicated, and it leaves you to do something sensible, whatever that might mean in your case.

On the subject of exceptions, this isn't like Java where you are forced to catch exceptions for things which are honestly rather trivial, like a NumberFormatException for parsing a bloody integer of all things. Lua's error system is borne from its origins and primary purpose as an extension language, in that it's OK for a chunk of code to error and return control to its caller, since you probably won't have huge chunks of code anyway, and errors worth halting the whole thing are due to faulty program logic rather than edge cases. As a result, Lua and its libraries return error codes for things which aren't the programmer's fault, such as trying and failing to open a file, and raises halting errors for things that are, like accessing a non-existent member of a table. This is further encouraged because the only error control mechanisms you get are error (and assert) for raising errors, and pcall to execute a function and capture either its return value or its error.

It's certainly satisfactory enough for most uses, though I'd rather have Python's more powerful exception handling if I was writing a large program. In any case, error handling depends more on the programmer than the language. Even when it tries to force your hand like Java's checked exceptions does, it's no guarantee you actually solve the problem, let alone in a reasonable way.

There's one thing Lua does better than Python, though (and Java, but that's obvious). First-class functions with real closures. The best way I can express it is being able to pass around behaviour with state as an object like any other, and being able to define it with the same convenience. If something is easy to use, you will use it more often. Being able to define behaviour means you'll readily create functions that accept behaviours, just like map, filter, sort... and thus get one step closer to the Holy Grail of Code Reuse. I think we can all agree that the less new stuff we have to write, the easier it is for us and the fewer new bugs we will introduce. Amen to that.

Temporary Freedom

December 14, 2009 9:55 AM | No Comments | No TrackBacks
That's it, my last deadline of 2009 has been met. It's rather too tempting to spend the day making ice cream, playing TF2 (team Demo!) and going out on the town, so that is precisely what I'll do. But only today!

Tomorrow, however... that is when I start my Coder series on

Building a raytracer in Lua

Serving both as the solution to one of my assignments and a diary of my experiences learning a new-to-me, yet very promising language, and one that receives wide usage in the games industry already. I'd do well to know it, especially since MMF2 has a Lua interpreter extension.

Raytracers are very computationally intensive, which is why they're generally written in C(++). As far as performance is concerned, LuaJIT appears to be doing reasonably well for itself, and you get the benefits of dynamic typing, closures and first-class functions. You also have a rather flexible object system - as in, there isn't really one, but the language features plus a little syntactic sugar give you the tools to develop a model that fits your particular circumstances. You know, like Perl, except without the feeling you're filling your source code with censored profanity.

A raytracer might not need all that flexibility, being one of the most naturally-object-oriented applications you can make, but I certainly don't intend to make raytracers all my life. Or ever again.

Plus, since I'm not Steve Yegge, the lack of braces isn't a turn-off. Besides, the benchmarks I've seen put the V8 JavaScript engine slower than LuaJIT - though I have no idea whether that holds once you make a more substantial program.

At the very least, compared to Win32 C programming, Lua will be quite the welcome break. Once you've had a taste of functional programming, writing in C again seems nearly as painful as if you'd lost your compiler and had to resort to typing COPY CON: OHGODWHY.EXE (and believe me, typing italics into a command prompt is tricky stuff). Time will tell whether it's all I've cracked it up to be.

One day Google are gonna screwgle

November 27, 2009 2:00 PM | 1 Comment | No TrackBacks
Reading an article on Chrome OS prompted me to ponder the up-and-coming juggernaut that is Google - at least where the Internet is concerned, but as that keeps growing, so will their power.

The obvious thing is that Google is about advertising. What do you think pays for all your space on Gmail? The revenue from Google Apps for Business won't cover it - and if you think of all the ISPs that resell the platform yet retain ads, e.g. Sky, you can see where the real value lies.

The added benefit of reselling is passing on the cost of support; this leaves more resources for Google to spend making those ads more relevant and thereby improving the bottom line.

That's fine, though. I can live with that. Companies need to make money somehow, and Google doesn't do this in a particularly insidious way; their ads are the only ones I actually allow because I have found them useful at times, and because they aren't insanely irritating compared to the competition. (Even YouTube fares better to commercial TV, IMHO.)

The real concern in my eyes is that, while Google is sticking to 'Do no evil', they're not doing good, either. Let's get back to Chrome OS: no support for native apps or data storage is in no way good for users. It is a serious step back in time in an era where storage is insanely cheap and mobile processors have more power than huge mainframes did not too long ago. People might spend huge amounts of time on the web, but everybody I know needs at least one killer app which you can't get via a web browser. That might be Skype, it might be an image editing program... hell, people have mobile devices which need to sync somehow, whether it's an iPod, smartphone, or digital camera.

I just wonder where the value comes in from having Google's glorified browser as the only thing on your netbook. It's not like manufacturers haven't tried putting Linux on to cut costs - look at how successful that ended up. I suspect people want a little more than that - but I also suspect I may be proved wrong and Google succeed over that original failure.

But that's not really the issue here. There's a good reason why Google want people to stick to the web - it's what they're good at, they make money from it, and it's all they really care about. The linked article at the top gives plenty of examples where it's obvious their only loyalty is to themselves. Getting people on the web where they have huge popularity and more control of things can only be good; even if some people avoid all Google-using sites as a consequence, there's going to be many more using them by virtue of their reputation, and they know this. A win for Google.

Advertisers are their customers, and users are their product. They worked out that attracting users means you have to make things users like, and damn anyone else; the perfect example being Google Book Search's lack of regard for copyrighted works, and the associated furore.

Sure, Google makes nice things for us. Just don't fool yourself into believing it means they love you; if you do, one day you'll wake up with a nasty surprise, a very awkward situation on your hands and terabytes of data all about you stored somewhere in the Googolplex. The sea level will rise a metre solely from how much advertisers are salivating right now.
« CB | Main Index | Archives | Cooking »