Jamie's Blog

The ramblings of a programmer with a little too much time on his hands

Tag: C++ (Page 1 of 2)

Code Project: RGB to Y’UV

Edit (18/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

Jargon

In case you don’t know what they mean, I’ve included the following list of jargon terms and rough descriptions of them.

RGB = Red, Green, Blue

YUV = similar to RGB, except that luma (Y) and chroma (U and V) are stored

Sources?

Most of the information for this post came from the Wikipedia article on YUV. You can visit it here: [LINK]

RGB? YUV?

Last week, a friend of mine wanted to meet in the city centre and go for a nosey around the TV stores. He’d recently bought his own place, and is decorating it and looking for a new TV.

While we were walking around “Electronics-Company-That-Isn’t-Named-After-A-Spicy-Food-At-All”, we spotted the Sony and LG LED TVs. I got to wondering whether TV transmissions are still sent in YUV, and whether those same signals were converted to RGB before being displayed on screen.

When I got home, I decided that I should look into YUV and see just how it works. I didn’t actually get around to reading about YUV until this afternoon, but when I did it made sense.

The human eye is more sensitive to changes in brightness, rather than certain colours. So, why  not send the luma (brightness) information and the chroma (colour difference) information?

Back in the days of blank and white TV, all that the TV broadcasters had to send was the luma (brightness) information. As colour TV was invented, top boffins thought that the best (read: “way that requires less bandwidth over the air”) way to send the colour information was the extend the model of just sending luma information, this time including chroma information.

The best way to understand this is to see it. Luckily, Wikipedia have an amazing example. In the following picture (click to enlarge):

  • The top image is how it is displayed on screen in any picture browser
  • The second (blank and white) image is the luma data for the image
  • The third (mostly blue and green) image is the U chroma data for the image
  • The forth (mostly yellow and orange) images is the V chroma data for the image
An image along with its Y', U, and V components.

Images via Wikipedia

They could have ditched the older system of just sending luma, and gone with a purely RGB system. However, this would have required the transmitters to send redundant, extra data over the airwaves. Plus, the older blank and white TV sets would no longer have worked. If a blank and white TV is used, then it simply ignores the UV portion of a received signal.

Also, the data being sent can be compressed before sending over the airwaves. In fact, the video portion of digital broadcasts are compressed in (almost) the same way. Because the human eye is more sensitive to changes in brightness, the chroma differences can be compressed (sampled fewer times), thus reducing the bandwidth.

Why Are You Telling Me All Of This, Jamie?

Basically, one of the ways that I can tell if I understand something that I’ve just learnt is to test myself in some way.

Ever wondered why you have exams in most of your classes?

Also, this links into my (very basic) teacher training:

  • Teach something to the student(s)
  • Get the student(s) to tell you what you’ve just taught them in their own words

Anyway, I’ve tested myself by taking what I’ve learnt about the RGB to YUV conversion and created a small C program that converts RGB to YUV.

At the minute it only converts a set of user inputted strings that represent the RGB values and returns their YUV equivalents.

My browsers built in spell check system is telling me that “inputted” isn’t a word. I’m sure that it is. In fact, a whole slew of Internet resources tells me that it is.

Anyway, onto the code. I wont write any more information about the code than this (as everything else should be included in the comments for my code, hopefully):

I compiled this on MS Windows 7 x64, with MiNGW’s gcc with the following options/command:

gcc <path to source file> -o RGB.exe -O2

/*
 * Project Name:        	RGB to Y'UV
 * Solution Name:		RGB to Y'UV
 * Original creation date:	19/11/2011
 * Edit date:			18/01/2013
 * Programmer name:		Jamie Taylor (aka "GaProgMan")
 * File name:			YUV.c
 * 
 * Purpose of the project:
 *	I was reading through a wikipedia article on
 * 	the differences between YUV and RGB and found it
 * 	very interesting.
 * 		For those who don't know, YUV is a colour
 * 	space - a way of storing colour for digital images,
 * 	film and TV. It focuses on storing Luma
 * 	(brightness - as Y') and two chrominance (colour
 * 	- as U and V) values.
 * 		Most video and still images are stored  in
 * 	this format, as it takes into account the Human
 * 	eye's ability to perceive differences in brightness
 *	at higher definition than differences in colour. This
 * 	greatly reduces the data bandwidth required to send
 * 	and receive images and film in this format.
 * 		This short program explores the mathematical
 * 	formulae used to convert colour data from the RGB
 * 	colour space to the Y'UV colour space.
 * 		For an in-depth description Y'UV, RGB and
 * 	the formulae used, please see the following
 * 	website:
 * 			http://en.wikipedia.org/wiki/YUV
 * 
 * Formulae used:
 *	To convert from RGB to Y'UV, the following
 * 	will be used:
 * 			Y' = W[r]R + W[g]G + W[b]B
 * 			U = U[max] * (B - Y') / (1 - W[b])
 * 			V = V[max] * (R - Y') / (1 - W[r])
 * 		Where:
 * 			W[r] = 0.299
 * 			W[b] = 0.114
 * 			W[g] = 1 - W[r] - W[b] = 0.587
 * 			U[max] = 0.436
 * 			V[max] = 0.615
 * 		Note:- I have placed square brackes around
 * 	the letters in the formulae that are written in
 * 	subscript. This is to make it easier for the
 * 	reader.
 *
 *	GNU Copyright information
 *	Copyright 2011 Jamie Taylor <jamie@taylorj.org.uk>
 *
 *	This program is free software; you can redistribute
 *	it and/or modify it under the terms of the GNU General
 *	Public License as published by the Free Software
 *	Foundation; either version 2 of the License, or (at
 *	your option) any later version.
 *
 *	This program is distributed in the hope that it will
 *	be useful, but WITHOUT ANY WARRANTY; without even the
 *	implied warranty of MERCHANTABILITY or FITNESS FOR A
 *	PARTICULAR PURPOSE.  See the GNU General Public
 *	License for more details.
 *
 *	You should have received a copy of the GNU General
 *	Public License along with this program; if not, write
 *	to the Free Software Foundation, Inc., 51 Franklin
 *	Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/

/* included libraries */
#include <stdio.h>

/* Constants that will be used for RGB to Y'UV */
#define WEIGHTEDRED	0.299
#define WEIGHTEDGREEN	0.587
#define WEIGHTEDBLUE	0.114
#define UMAX		0.436
#define VMAX		0.615

/* function declarations */
void convertFromRGB ();

/* global variables */
float redValue;
float greenValue;
float blueValue;
float yPrime;
float uValue;
float vValue;

int main () {

  /* read values for RGB into memory */
  printf("Please input a value for RED:");
  scanf("%f", &redValue);
  printf("Please input a value for GREEN:");
  scanf("%f", &greenValue);
  printf("Please input a value for BLUE:");
  scanf("%f", &blueValue);

  /* convert RGB to Y'UV */
  convertFromRGB();

  /*display results */
  printf("\nFor the RGB input (%.2f, %.2f, %.2f),\n",
    redValue, greenValue, blueValue);
  printf("The following Y'UV is outputted (%.2f, %.2f, %.2f)",
    yPrime, uValue, vValue);
  return 0;
}

void convertFromRGB (){
  /* 
   * implement formula:
   * Y' = W[r]R + W[g]G + W[b]B
   */
  yPrime = (WEIGHTEDRED * redValue) +
    (WEIGHTEDGREEN * greenValue) +
    (WEIGHTEDBLUE * blueValue);

  /*
   * implement formula:
   * U = U[max] * (B - Y') / (1 - W[b])
   */
  uValue = UMAX * ((blueValue - yPrime)
    / (1 - WEIGHTEDBLUE));

  /*
   * implement formula:
   * V = V[max] * (R - Y') / (1 - W[r])
   */
  vValue = VMAX * ((redValue - yPrime)
    / (1 - WEIGHTEDRED));
}

One last thing: If you’re going to compile and run this yourself, remember to put a blank line at the end of the source code. It’s ANSI C, after all.

When I added my source code to this page, it had the blank line at the end. But when I previewed the page, the blank line was pruned from the code viewer provided by WordPress.  But if you click on either “View source” or “Copy to clipboard” (when hovering over the source code black), you’ll get the code with the blank line at the end.

Until next time,

J – “Soul, peace and chicken grease” (as my brother says)

Problem Six – In C

EDIT (18/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

 

Reading a comment on my most recent post, I felt that I could optimise my code for Project Euler’s Problem Six. So, I went away and read up on the information provided by Kristan (in the comments section), and decided that I’d give it a go… in C.

There were a few reasons for switching to C, the biggest was that I only have a C compiler installed on this machine (a minimal install of MingW), another being that I’m a little more informed about the optimisation options (which I didn’t use for this project) that gcc provides.

Anyway, on with the code.

Firstly

This is a solution to problem 6 on Project Euler. I’ve not posted it up here to gloat, or to provide answers for cheats. I’ve posted it, so that you can see how I solve this kind of problem.

The original problem reads like this:

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 – 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

The Algorithm

Based on my code from the previous version of this project, and the knowledge provided by Kristan and The Internet at large, I’ve used a slightly different algorithm this time around. I’ve covered the algorithm in the comments section for my code, though. So, I guess you should just scroll down and read that.

I’m not a massive fan of providing information twice, in the same format. That and redundancy. That and redundancy

The Code

I’m not going to spend time explaining the code, since it contains enough information in the comments (within the code itself) and in the description of the algorithm above.

So, without further ado, here is the finished code:

By the way, I compiled this code with the following command:

gcc “Problem_Six_In_C.c” -o “Problem_Six_In_C.exe” -Wall

A simple problem with an extremely simple, now optimised,  solution.

Here’s a link to the c file: LINK

Until next time,

J

Sums and Squares – Or: How I Solved Project Euler Problem 6

Edit (18/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

Firstly

This is a solution to problem 6 on Project Euler. I’ve not posted it up here to gloat, or to provide answers for cheats. I’ve posted it, so that you can see how I solve this kind of problem.

The original problem reads like this:

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 – 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

The Algorithm

There’s only one way to solve this problem.

This one is real simple – dependant on your understanding of Mathematics – assuming you can understand Square Numbers.

It’s a two step approach:

  1. Sum (add up) all of the squares of the numbers between 1 and 100
  2. Sum all of the numbers between 1 and 100, then square the answer
  3. Then find the difference between them (subtract one from the other)

There’s a slight problem with this method, though. Skipping ahead – and, hopefully teaching you all a little about speed-of-light Maths – we get:

There is a well known story about Karl Friedrich Gauss when he was in elementary school. His teacher got mad at the class and told them to add the numbers 1 to 100 and give him the answer by the end of the class. About 30 seconds later Gauss gave him the answer.
The other kids were adding the numbers like this:
1 + 2 + 3 + . . . . + 99 + 100 = ?
But Gauss rearranged the numbers to add them like this:
(1 + 100) + (2 + 99) + (3 + 98) + . . . . + (50 + 51) = ?
If you notice every pair of numbers adds up to 101. There are 50 pairs of numbers, so the answer is 50*101 = 5050.  Of course Gauss came up with the answer about 20 times faster than the other kids.

That version of the story comes, courtesy of Dr. Math. The actual story has been around for… well, since the days of Karl Friedrich Gauss

Anyway, skipping to the end, we find that the sum of all the numbers from 1 to 100 comes out at 5050. A quick calculation tells us that 5050 squared (5050 * 5050) is 25,502,500. Quite a big number, wouldn’t you say?

That’s fine, but logic tells me that the other number I’m working out (the sum of the squares) will be huge, compared to this one. So, and int just wont do it.

Dependant on your system, an int can store a value between +2,147,483,647 and – 2,147,483,646 (32 bit)

So because of this, potentially, massive answer, I decided to code this by using an unsigned long long (sometimes called a long int) type.

Again, dependant on your system, an unsigned long long can store a value between 0 and +4,294,967,295 (32bit)

Of course, I’m running 62 bit, so the maximum values that these two variable types can hold are doubled. But that’s not the point.

The Code

I’m not going to spend time explaining the code, since it contains enough information in the comments (within the code itself) and in the description of the algorithm above.

So, without further ado, here is the finished code:


A simple problem with a simple solution.

Here’s a link to the cpp file: LINK

Until next time,

J

Pining For Primes – Or: How I Solved Project Euler Problem 5

Edit (18/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

Firstly

This is a solution to problem 5 on Project Euler. I’ve not posted it up here to gloat, or to provide answers for cheats. I’ve posted it, so that you can see how I solve this kind of problem.

The original problem reads like this:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

The Algorithm

Firstly, there are two ways to solve this problem. One involves brute force, and one requires a little savvy.

Technically, there are a whole bunch of ways to solve this problem – dependant on your understanding of Mathematics. Hopefully, both of these methods will be simple enough to follow – assuming you can understand Prime Numbers.

The brute force check goes like this:

  1. Start at n, check this against all numbers in m
  2. If n divides evenly (i.e there is no remainder) by all the numbers in m, stop. This is the answer
  3. If not, add 1 to n and start again.

“n” starts at 1 (this is the smallest positive number that will divide by all the numbers from 1 to 20)

“m” starts at 1 and goes only as far as 20 (this is the series of numbers that “n” has to divide by)

That’s it.

The smarter algorithm goes like this:

  1. Start with n at 2520
  2. If n divides evenly (i.e there is no remainder) by all the numbers in m, stop. This is the answer
  3. If not, add 2520 to n and start again.

This method assumes that you recognise a few things from the problem statement. Let’s take another look:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Since the numbers between 1 and 20 contain all the numbers between 1 and 10 (1, 2, 3, 4, 5, 6, 7, 8, 9 & 10), some of the work is done for us. We can assume that, since 2520 is evenly divisible by all numbers between 1 and 10, that it must be evenly divisible by all the numbers between 1 and 20.

This algorithm speeds up execution exponentially. Instead of going through every positive integer between 1 and he final answer, we can jump in steps of 2520.

The Code

I’m not going to spend time explaining the code, since it contains enough information in the comments (within the code itself) and in the description of the algorithm above.

So, without further ado, here is the finished code:

And there you have it, another problem solved (and optimised) in minutes.

Until next time,

J

Folding and Libraries

Libraries

I was once asked what I considered an excellent question in an interview. One I managed to screw up completely.

Why do we used standard libraries in place of our own code?

The context for this question was this: I’d just completed a task were I had to, in pseudo-code, implement a function for combining strings. I think I ended up with something similar to this (again, this is pseudo-code):

[sourcecode language=”cpp”]
string CombineString (string firstString, string secondString) {
//create a new string with enough space for both strings to be copied
string combinedString = new string;
combinedString.malloc(firstString.GetLength() + secondString.getLength());
return combinedString = firstString + " " + secondString;
}
[/sourcecode]

Firstly, this wont work. Secondly, this isn’t what I wrote up on the whiteboard that day. This is just a naff example to give you some kind of context with which I was approaching the question.

Now then, the question itself is very simple to answer:

Standard libraries have, we assume, been through a rigorous testing procedure to make sure that they conform to the design documents perfectly, and to make sure that there aren’t any bugs. They are also very simple to implement, compared to designing a library yourself and having to teach the entire team how to use it. They save time, money, and improve productivity – assuming that they are the right libraries for the right task to begin with.

Simple, ne?

I forget what my answer ended up being, but I don’t remember saying much along those lines.

Folding

Most of the past few weeks has been taken up with building muscle/working out, watching The Soprano’s (I’ve never seen this before) and folding. Although, I’m implying that I’m the one whose done all the folding.

I’ve instructed my PC to use the spare cycles on 3 out of my 4 cpu cores and my gpu core to help understand the process of protein folding. A lot has been said about protein folding, and most of it can be found on The Wiki. Needless to say, I’m doing my part. I care for a lot of people, and the problems that CAN be linked to improper folding of proteins are huge.

My PC is still running very efficiently. I’ve got to hand it to the guys over at Stanford, they know how to write a really good piece of distributed code. I’m still able to browse the Internet, watch videos, and even play games. Excellent coding guys.

Watching

I know that The Soprano’s ended back in [goes to check] 2007, but it takes me a while to get into American TV shows, mainly because there’s that much out there. I don’t want to waste my time and (more importantly) money on something that I’m not going to enjoy. I’ve got to say that I’m enjoying The Soprano’s very much, though. I’ve only just started season 2, but it’s drawn me in already.

Plans For The Weekend

Well, that’s this short update done. I’m hoping to get some coding done over the holiday weekend (4 day weekend!!!), and whatever I get done is getting posted on here. Maybe I’ll come up with something interesting. Probably not, though.

Well, have fun.

J

FizzBuzz

Edit (19/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

Firstly, I realise that I’m not the best developer in the world. I can, certainly, hold my end up in C++; read a lot of C and understand it; work my way through a C# listing with confidence; understand enough of an assembly listing to VERY vaguely get what it’s doing.

Secondly, I’ve been using twitter and the blog-o-sphere for a few weeks now, to try and figure out what’s missing from my virtual tool kit (if you like) of developer skills. So far, the answer has been a resounding “Experience is better than a degree”

For instance, Gaven Woolery over at #AltDevBlogADay mentions that (and I’m paraphrasing):

In this age, with the relative ease of access to both online and offline tutorials/books/whatever, and the relatively un-homogeneous structure of Computer Science degrees in most Higher Education facilities, what’s the point of going to [University] for 4 years, and racking up a large debt, when you can just learn all of that at home?

Here’s a link to the original article : Link

This all is beginning to make sense to me. Don’t get me wrong, I thoroughly enjoyed my studies at University. But there where a few modules (known as classes to some) that were better studied at home, or in the labs than sat in a lecture theatre. Then again, there were modules that required that level of theoretical understanding.

I like to think of Computer Science being a perfect marriage between both vocational and non-vocational training.

This leads me onto something that Richard Banks blogged about in the middle of 2009: Some “Developers” Just Can’t Develop. Basically, his argument is for testing new recruits DURING the interview process. Something I have taken part in for some (not all) of my interviews.

I remember during one interview, in the middle of a question even, the interviewer got up and asked me to write some code “it can be in any language you want, even psuedo code,” to copy two strings

Because of my experience, I can certainly see what Richard is talking about. The cost of hiring the wrong person can be crippling. That being said, he links to a post from early 2007 (a year before I graduated, for those who want to know) by Jeff Atwood called “Why Can’t Programmers.. Program?”

The main thrust of Jeff’s post is to promote the idea of using a standardised test during interview processes to find out if the candidate is “good enough.” That being a completely subjective term (some companies require different skills from their employees, especially graduates), he even goes on to say:

Like me, the author [of, yet another post] is having trouble with the fact that 199 out of 200 applicants for every programming job can’t write code at all. I repeat: they can’t write any code whatsoever.

The post Jeff refers to mentions a test that is used by some professionals to see if a candidate can solve “simple” tasks.

FizzBuzz

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

Fain enough, that’s quite easy. One for loop and three checks. Easy.

Most good programmers should be able to write out on paper a program which does this in a under a couple of minutes. Want to know something scary? The majority of comp sci graduates can’t. I’ve also seen self-proclaimed senior programmers take more than 10-15 minutes to write a solution.

What!? How is that possible?

I really hope that the teaching of programming has improved since 2007, otherwise graduates haven’t got a chance of getting that juicy development role they tell themselves they deserve.

In fact, I think it has improved. At least, my experience of the teaching of programming seems to have been quite an amazing one and I’ll prove it to you.

Taking that basic task, I created a solution with 17 lines (including white space) in, roughly, 3 minutes (damned keyboard’s too stiff) that solves this problem; and it goes a little something like this:

I usually have extra newlines in there for formatting and clarity. But I think it looks just as good without them.

There you have it.  A solution to a simple problem in less time then a “self-proclaimed senior programmer” and, dare I say it, an elegant solution, too?

J

Code Examples 5 – Collision Detection in C++

Edit (19/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

Firstly

The post is not going to explain how the chosen algorithm works, although I might cover the basics. I’m going to leave understanding of the algorithm and code up to the reader. Hopefully it’s not that complex, though.

Why Re-Write It?

I re-installed Visual Studio today, and started itching for something to code. Then I remembered that a friend had recommended that I write a program containing my collision detection code to show it off.

Apparently, the pseudo-code and explanation I’d produced for it was quite good.

So, I decided to turn the pseudo-code into actual code. Thinking it wouldn’t take too long, I sat down at my pc and started coding. Providing the background music was Miles Davis (specifically the album ‘Sketches of Spain’, which I recommend to anyone).

I decided that I’d produce some code in C. But Visual Studio doesn’t have support for C, so I decided to give it a go in C++ instead.

Seeing how C++ is just an extension of C (clever naming convention, eh?), it shouldn’t be that different. Especially since I didn’t use any custom objects.

Two hours later, I emerged from my coding “deluge” with a a whole slew of twitter/facebook messages (I tend to zone out when coding) and some working code… sort of.

The Algorithm

It worked, but not entirely as expected. There was a problem with the internal logic, which I quickly fixed (more on this can be found in the change log, linked at the end of this post). Firstly, though, the algorithm.

When we look at a graph with 2 straight lines plotted on it, we can see instantly if the lines intersect (if they cross over each other) at some point. For instance:

Lines 1 and 2 intersect at the point (3,2), we can see this by looking at the image

Looking at the image, we can see that lines 1 and 2 intersect at the point (3,2). We can see that, because we humans have a power that a computer doesn’t: We can see the image as a whole, whereas the computer would see that image as a collection of pixel locations. So how do we get the computer to look for an intersection?

Firstly, we must decide if there is an intersection. There’s no point checking all of the individual locations if we don’t know whether there is a collision or not, as this is very costly (in CPU time); especially since the image area is likely to be rather large. After we’ve decided that there’s a collision, we’ll look for a point of collision.

There are lots of different ways to do this and each has their own benefit. A simple system, for instance would be to check the x value of some point against the x value of some other point. If those points match, check the y values. If they match, then there has been a collision. This is really simple to write, and very simple to read.

[sourcecode language=”cpp”]
bool checkForCollision () {
if (myXValue == someOtherXValue) {
if (myYValue == someOtherYValue) {
//a collision has occured
}
}
}
[/sourcecode]

The problem with this is that every single x value position needs to be checked, at least, once.

Another way would be to create a bounding box. This is slightly less simple, but easier on the cpu. Basically the idea here is to create a list of points around your object and check those against the positions around the other objects. Here is an article on wikipedia about bounding boxes.

The method I chose was to think of the entire screen as a graph. Working with a start and end position for my objects instead of a single set of x and y values, I can create a virtual line that goes through the space each of the objects takes up. Then, by using some, high level, maths we can find out whether any of these lines have crossed.

Look again at these lines

Line 1 consists of two sets of points, (1, 1) and (4, 3) and Line 2 consists of the points (1, 4) and (4, 1). by taking these points and throwing them at a mathematical formula, we can tell if they intersect. By the way, there are 4 formulae to work this out.

  1. x intersection point = x1 + ua (x2 – x1)
  2. y intersection point = y1 + ua (y2 – y1)
  3. ua = (x4 – x3)(y1 – y3) – (y4 – y3)(x1 – x3) / (y4 – y3)(x2 – x1) – (x4 – x3)(y2 – y1)
  4. ub = (x2 – x1)(y1 – y3) – (y2 – y1)(x1 – x3) / (y4 – y3)(x2 – x1) – (x4 – x3)(y2 – y1)

The format for the points are thus:

Line 1 = (x1, y1) to (x2, y2)

Line 2 = (x3, y3) to (x4, y4)

How Does I Use It?

The first thing we have to do is find out if there is a collision anywhere between these two lines. We do this by working out formulae 3 and 4.

Both formulae 3 and 4

As long as the answers to both of these formulae are greater than 0, then we can say that there is a collision happening. Using the values for ua and ub, we can find out the position of the collision by feeding these values back into formulae 1 and 2.

I Get Ya… Sort Of

Now that I’ve discussed a little about how it works (I, intentionally didn’t cover it all because there are tonnes of websites out there that explain the maths better than I can), I’ll post the code.

A quick note: I’ve intentionally made this code a little hard to read. This is so that anyone who block copies this code wont be able to explain how it works without some intense study of the code.

Until next time, have fun,

J

Video Compression

Edit (19/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

What of What?

A few months back, I was thinking of applying for a job relating to video technologies. The company wanted someone with “experience working with video compression techniques with regards to software development.” As with everything relating to software development, this got me curious. How does video compression work? Why do we need to compress video? What are the most widely used compression techniques?

Well?

I’m only going to answer (and party, so) the second question in this post:

Why do we need to compress video?

This is simple. Otherwise we would run out of storage space for digital video. I’ll explain.

Storage Space

OK, so storage space is slowly become less of a problem (I still remember my first 1GB hard drive, back in the days of 3.5″ floppy discs, well before USB memory sticks. Before USB, even). But that’s only because we’re gradually increasing the quality of the footage we shoot. It wasn’t so long ago that the first 3D cameras came out, before that it was HD cameras, before that it was digital cameras.

Of course, I’m talking about cameras that are dedicated to shooting video here, but the same principle applies to digital stills cameras, too.

Our need to take pictures, static or otherwise, at higher and higher resolutions is creating greater need for more and more storage space and better, more efficient compression methods. Eventually we’ll get to a point where we can capture near-to-real-life resolution, and the storage space needed will be astronomical (by today’s standards), but that’s more than 20 years off at the very least.

Why Does Video Take Up So Much Space?

Do you remember taught that animation (of any kind) is a bunch of still images that are played together in a sequence? The images are displayed, one after the other, quick enough that our brains to put them together as one image – usually at, around 24 – 60 images every second. That means that when you’re watching a piece of video footage, you’re actually watching 20 – 60 images every second.

Animation is actually seen as a “Mind Hack” by those in the Neuroscience (Brain Science) community, but since it’s so common place now, many lay-people (I.E not connected with Neuroscience) don’t think of it as such.

Each of those images has to be stored somewhere and, depending on the resolution – the number of pixels (Picture Elements, the individual “dots” that make up the picture) – that can be anywhere from 20Kb to 15Mb per image.

Two things to note here:

  1. When talking about images, we use the measure of bits, not bytes. This is because we store image data in bit, and  text data in bytes. When stored as text, the character “a” takes up 1 byte of memory in a computer; which is 8 bits.
  2. I’m not including audio here, as the audio is actually stored separately in all video formats.

With, on average, 25 images per second of footage taking up 15Mb of storage space, you’re going to run out of space very quickly.

How Quickly?

Well, suppose that you’re taking video at 640 pixels wide by 480 pixels high with a colour depth of 24 (that means 8 bits representing each of the colours Red, Green and Blue). This would give you an overall value of 7Mb per image.

This is what the phrase “MegaPixel” means. It is a measure of how many pixels are captured by a stills camera when you hit the shutter button.

So, a camera that takes stills at 7 mega pixels COULD take images that are 640 pixels wide by 480 pixels high at 24 bits per pixel. But that’s just confusing the matter.

At 25 images per second, a full minute of footage would take up about 10.3Gb of storage. That’s more than one dual layer DvD, for a single second of video footage. Again this isn’t counting the audio.

And that’s less than standard definition, too!

Understanding is Key

In an effort to understand why video compression is tantamount to film production I did what I do best.

OK, second best.

All right, third best.

Is that even a term?

I’ve written a very short program that calculates how much storage space is required for a video taken at any resolution, colour depth, frame rate and length. All of these variables are provided by the user.

It’s a really simple bit of code, so there are no checks on what the user is entering, it’s assumed that the user is entering valid data. So long as the user enters valid data, the program will calculate the amount of storage space required for the video footage taken at that resolution and colour depth provided.

It’s written in C, one of the most powerful programming languages there is, and my second favourite (after C++). It should be easy to read whether you’re a programmer or not. It’ll need a little extra code to run, dependant on your OS environment, and you’ll need to compile it, too.

The Code

At the minute, I’ve commented out the code for user input. That’s because the code is in it’s initial testing stages. For now, if you run the above code, it’ll tell you how much storage space is required for a video taken at 640*480 pixels, at 24bit colour depth, at 25 frames a second with a total duration of 1 hour.

Give it a go, and tell me what you think.

For those who don’t write software or can’t program, here’s a break down of what it does:

  • 640 (width) * 480 (height) = 307,200 (pixels per frame)
  • 307,200 (pixels per frame) * 24 (colour depth) = 7,372,800 (bits per frame)
  • 7,372,800 (bits per frame) * 25 (frames per second) = 184,320,000 (bits per 1 second of film)
  • 184,320,000 (bits per 1 second of film) * 3600 (number of seconds in 1 hour) = 663,552,000,000  (the size of the resultant video file in bits)
  • 663,552,000,000 is roughly 632,812.50 MB for 1 hour of video.
  • This doesn’t take into account the audio

J

5 Years in the Making

The Problem

Five years ago, I created a software project in C#. The goal was to create a clone of an old computer game called Gorillas. For those who don’t know abut this game, click this link for an article on The Wiki. Most people would have played a variant of this game based around cannons, though.

I’d got the game 90% complete in my time budget. The only things that where missing were textures (I was still only a baby programmer back then), and aiming code.

My not so elegant code for aiming was terrible, to say the least. By pressing left, right, up or down the player could change the position of the projectile (in this case, a banana). When the player pressed the fire button, the banana would be fired out in a straight line from it’s current position. For some reason, I’d felt that I would never be able to put code in that would make this aiming process simple.

Anyone who’s played the original (be it in tank of gorilla form) will know how to use the aiming system: Right to decrease the trajectory and Left to increase it. Simple.

For some reason, my brain couldn’t figure out how this was done. I tried and tried my hardest, but I couldn’t visualise it. At one point, I ended up trying to program a semi circle of points that could be selected by the user, but that went as well as this sentence seems to have done.

The Solution

Last night I was snuggled up in bed, watching an episode of Seinfeld. The episode ended, I turned the DvD player off, then got back into bed and started to fall asleep. All of a sudden the following image popped into my head.

 

Mario and Tanooki are used via Fair Use. No copyright infringment is meant. Both are copyrighted by Nintendo

At first I wasn’t sure what to make of it. Then, I figured out why the axis are there.

Pressing left will decrease the X value, but increase the Y value. Pressing right will increase the X value but decrease the Y value.

Both X and Y have pre-set limits, X can only be between 5 – 20 units in front of Tanooki and Y can only be between 5 – 20 units above Tanooki, for example.

This algorithm will successfully move the projectile (assuming you show it) around your gorilla (or tank, or Tanooki) along a quarter circle in front of it. In pseudocode it might look something like this:

[sourcecode language=”cpp”]
int projectileXPos, projectileYPos;
int upperLimitX, upperLimitY = 20;

// game code in here

switch (key) {
case left:
//without any bounds checking
projectileXPos–;
projectileYPos++;
break;
case right:
//without any bounds checking
projectileXPos++;
projectileYPos–;
}
[/sourcecode]

Calculating the Angle

So, you’re projectile is moving around the character in a quarter circle arc; which is great. But now you want to be able to fire along the correct trajectory? That’s really simple to work out.

If you look back at the image of Tanooki you’ll see a Greek symbol near his face. For those who aren’t familiar, this is symbol is called Theta and in trigonometry it represents an unknown angle. To calculate this angle we’re going to use something called SoH, CaH, ToA.

Copyrighted by processing.org. Used via Fair Use

If you look back again (what’s with all this looking?) at Tanooki, you might be able to see a triangle forming – the X axis and the trajectory forming the adjacent and the Hypotenuse.

We know all three values for the sides of this triangle (we actually only know two, but a quick bit of trig will calculate the Hypotenuse for us), so we can use any part of SoH CaH ToA to work out the angle.

We’ll use ToA for now, as we know both the Adjacent (X value) and the Opposite (Y value). But we could use either, if we worked out the Hypotenuse.

Again with pseudocode, it could look like this:

[sourcecode language=”cpp”]
#include <math.h>

int projectileXPos, projectileYPos;
int upperLimitX, upperLimitY = 20;
double opposite, adjacent, firingAngle;

// working out the angle

switch (key) {
case fire:
opposite = projectileYPos – player.GetYPos();
adjacent = projectileXPos – player.GetXPos() ;
firingAngle = tan(opposite/adjacent);
}
[/sourcecode]

To calculate the Hypotenuse, all you would have to do is basic Pythagoras. Again, in pseudocode it might look like this:

[sourcecode language=”cpp”]
#include <math.h>

int projectileXPos, projectileYPos;
int upperLimitX, upperLimitY = 20;
double opposite, adjacent, hypotenuse;

// working out the hypotenuse

opposite = projectileYPos – Player.GetYPos();
adjacent = projectileXPos – player.GetXPos();
hypotenuse = sqrt((opposite * opposite) + (adjacent * adjacent));
[/sourcecode]

Why Five Years

I know that this is really simple trig, and I know that the code for it is also really simple. For some reason, though it never crossed my mind to code it this way. I have no idea what prompted this “Eureka moment” for me last night, but I’m really glad that it did. Since then, I’ve been finding simple solutions to other coding problems.

I suppose my problem was, at that time, my whole life revolved around that one problem; as such, and to coin an old phrase, I couldn’t see the wood for the trees.  My best advice for anyone confronting a problem with no, obvious solution – regardless of whether it’s coding or math or life or whatever – is this:

Take a step back from it, and look at it from another angle.

If that doesn’t work walk away from it completely. Some of my other problems have actually been solved by me taking a break and going for a long walk.

If all else fails, watch something like Seinfeld.

I’ve found that, Seinfeld is my Plan Nine From Outer Space.

Anyone who has seen a few episodes of the X-Files will know what I mean there.

There’s that little going on, that my sub-concious mind can, and does, wander. This enables me to find the solutions without even thinking about the problems, while still enjoying the show.

More proof, if anyone needed it, that Larry David is a genius

Supposed Recent Flagelation Monkey

Recently

Over the past week or so I’ve been reading a story written by a friend of mine. I’m sure I’ve mentioned this before.

It’s a really good piece of fiction set in the Star Wars universe, shortly after the battle of Hoth. It follows a small band of survivors from the battle as they try to make their way to safety across the ice ball. It also details what happened once the Imperial forces had taken over the Rebel command centre on Hoth, too.

For those unsure, the battle of Hoth took place during the first 30-40 minutes of Star Wars Episode V: The Empire Strikes Back.

Another thing that had happened recently, is that I’ve been bitten by the programming bug.

Ever since graduating, I’ve occasionally had to battle a very intense need to program something, anything. I’ve been writing lots of silly little programs that do very little, and take seconds to compute. I’m thinking of putting more than a  few of them up on my website, but that’ll have to wait until the weekend at least.

One of the (many, many) reasons – aside from being a programmer, of course – I’ve been bitten by this bug, is  because my contract of employment is due to run out in 7 weeks time and that means I’ll be unemployed again. So, I’ve taken this time to air out my programming skills and start earning some major kudos by coming up with as many program ideas as I can.

Side note: “Program” as in to program a computer – is is “Program” or “Programme”? I can never remember

I really want to, finally, get into a games programming role somewhere, and bolstering my portfolio of work with some working titles (even if they are naff) will help me to apply to those jobs.

You see, much like a graphic artist, programmers need a portfolio of work to show off. The final program itself doesn’t really matter, it’s the steps that the programmer has been through to create that program, and the “elegance” of the code.

For instance:

[sourcecode language=”cpp”]
/* famous "hello world" code */
using namespace std;
int main () {
char ch;
cout << "Hello world" << endl;
cin >> ch;
return 0;
}
[/sourcecode]

Is not very elegant as a first time programmer might not know what lines 4 and 6 do. However:

[sourcecode language=”cpp”]
/* famous "hello world" code */
// this code uses a char type called ch
// to hold the input returned by the user
// in an effort to stop the program from
// executing too quickly for the user to
// see it
using namespace std;
int main () {
char ch; //here we create a char
cout << "Hello world" << endl;
cin >> ch; //here we use the char to
//temporarily halt the program
return 0;
}
[/sourcecode]

Makes a lot more sense, as the program’s function is explained to the reader.

Anyway, there are volumes and volumes on code elegance, and I shan’t repeat what they say verbatim.

What Else?

That’s pretty much all that I’ve been up to, to be completely honest. Although, I did purchase the components for a PC upgrade last week. When it was delivered, I checked the invoice details with the items I was sent and it turns out that the company had sent me the wrong ram. This means that my PC has sat idle, without ram throughout the entire weekend. Which is why I haven’t been able to upload any of the code I’ve written recently

That’s about it, really. that’s all I’ve been doing since I last posted.

I’ve another post lined up for later on today/at some point tomorrow, though.

Stay tuned.

Page 1 of 2