Of internet communities and hair..

Browsing around the 'net, I found some really wierd community websites/boards. Though now it makes perfect logical sense, but I really found this particular board pretty interesting: Link


I find amazing comradeship among long hairs. Walk into a bus, you'll immediately be noticed by another ponytail, not that I'm making one yet. Though of course, I find the "super groomed", "super silky" hair that kids try to emulate really gross. Hair should be allowed to grow as it wants to, what's the kick in spending 45 mins a day trying to get your hair silky smooth and steady?

PS: That guy in the picture is, unfortunately, not me. :-)
PPS: I know this sort of breaks the tradition of semi-technical posts that I have set with the last few ones.. Its unlikely I will post anything this idiotic in the near future.. :-)
PPPS: I really had nothing to post about, and was feeling generally bored. :-)

Effective optimizations for graphic programmers

Warning: The post contains a bit of technical stuff, along with some source code. Read on if you're interested.

I don't claim to be an expert, or even an intermediate in the vast field of graphic programming, but here are a few cool optimizations/replacements that I have been using for common math functions. This list is by no means complete, and by no means are most of the optimizations my inventions. If anyone wishes to suggest any more, please feel free to do so.

Graphic programming, 2D as well as 3D, involves extensive use of math, especially Vectors and Matrices. And it therefore extensively uses several math functions, like trigonometric ratios, squares and square-roots etc. Vectors also extensively involve "inverse-square-root" i.e. 1/sqrt(x) i.e. one divided by square root. This invSqrt is used in everything from finding magnitudes to finding angles between vectors, projections etc. The main point of this paragraph is that graphics heavily utilize math.

Now before we can make the next Doom3 engine, we need to first get the engine up-to-the-mark. Its no good having a fantastic engine intended for games, only to find it running like a slide-show on even high-end systems. The reason John Carmack is famous is because he has written all the game engines of id software, famous for the Doom, Wolf3D, Quake-series, Doom3 engines/games, and reading his code reveals some amazing tricks and optimizations. All the code upto Quake-3 (inclusive) has been made Open-Source under GPL, so you can try downloading and taking a peek if you're interested. I recommend that. So it turns out that most math functions can be hacked a lot to gain a great deal of optimization and speed.

A) Inverse Square Root
First I look at the famous "Inverse-Square-Root" function that was first seen in Quake-3 and is based on the Newton-Raphson method for approximating functions. The function in this case is 1/sqrt(x). To read in detail about how this works, you can see this and this (more technical). The code:

float InvSqrt(float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x; // get bits for floating value
i = 0x5f375a86- (i>>1); // gives initial guess y0
x = *(float*)&i; // convert bits back to float
x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
return x;
}
Test Result: I had tested this before using it in my code. For calculating the inverse square roots of 500000 numbers, the standard compiler method of 1/sqrt(x) took on an average 132 milliseconds, while the above code took on an average 18 milliseconds.

B) Square Root:
Then digging around Quake's source, I found an optimization for the simple square root function, which is essentially the same thing as above with a little modification. The Code:

float fSqrt(float number) {
long i;
float x, y;
const float f = 1.5F;
x = number * 0.5F;
y = number;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 );
y = * ( float * ) &i;
y = y * ( f - ( x * y * y ) );
y = y * ( f - ( x * y * y ) );
return number * y;
}
Test Result: To calculate the square root of 500000 numbers, the standard compiler function took on an average 110 milliseconds, while the above code took on an average 26 milliseconds.

C) Square, Cube etc.
This I found on my own. This method is best used if you know the exponent (the power to raise to) beforehand. There are two ways of raising a number to a specific power. One is to use the simple compiler pow(x, n) function which raises x to the power n. I've often observed people using this method if 'n' is large.. above 5 or 6, even if they know beforehand (while coding) the power to raise to. So they use the pow() function. The other way is to simply multiply that number as many times as required by itself. So if I want to raise x to 6, I'll do: [x = x*x*x*x*x*x]. Now it might seem odd, since this method looks so ugly (imagine doing that for 15th power), but believe it or not, the speed difference is amazing. Use the second method always, even if you're raising to the 15th power.
Test Result: I performed two separate tests. In each case, as usual, I took 500000 test numbers. I tried simple "squaring" using the pow() compiler function, and it took on an average 45 milliseconds. I tried the other ugly method of x*x, and it took 2 millseconds. I then tried raising 500000 numbers to the 9th power, and the pow() compiler method took on an average 67 milliseconds, while the [x*x*x*x*x*x*x*x*x] method took just 3 milliseconds. This proves this uglier way to be much more efficient.

D) Trigonometric Ratios
This is quite a common trick, and I therefore won't be putting up a result sheet for this one. The idea lies in making a 'lookup table' beforehand for all those trigo functions you are using. This is because the compiler trigo functions are VERY expensive (take time) and its bad to use them while rendering. So suppose we use cosine in our program, what we do is, make a table (array) of all the angles that the program might use and a table (array) of the cosines of those angles. So the speed boost is immediate, as picking a random element in the array (random access) is a very fast operation. Now generally we have an idea of the range of angles that we might use, and the smallest required intervals between each angle, for example, we might just need whole number angles, not fractional angles, thus we need to make, say, just 90 cosines. Or if the smallest step between angles is 0.5 degrees, we need to calculate the cosine of 0.0, 0.5, 1.0, 1.5 and so on.. while the program is starting up. After that we need to just look up the table and get the cosine very quickly. Incase the angle required is not *exactly* present in the table, like we need 13.7 degrees and we have 13.5 deg in the table, it makes sense to pick the cosine of 13.5 and be happy with it, since in Graphic programming, for real-time work it is smart work to make small compromises here and there to gain an great deal of speed.

PS: I think I need to change the blog theme. I tend to write long entries and this theme squeezes the text into a narrow column making it look dauntingly long.

What I've been up to.. procedural programming.

Alright, as usual, I was too lazy to actually carry through my idea of that "Interesting Projects.." column, which I described in my last post, and in another previous post which is also refered to in that previous post of mine. Anyhow, the point is that I probably won't be writing about the Morse Code-based Wireless Network I was developing from scratch, because I've been recently swept off my feet.

Not in 'The Pool', which I should tell you I have discontinued swimming in for a variety of reasons, but in my mind. I was hanging out at a friend's, and he showed me the video of a game by Will Wright (of The Sims fame) called Spore. The video was actually Wright's presentation at the Annual Game Development Conference where he presented his (and his team's) demo. I've never actually *awaited eagerly* the release of any game, or any movie, but this time, I do believe we are about to see a really revolutionary game which I just can't wait to get my hands on. I am probably not interested too much in the game, but in its source code and the concept that it uses to do the incredible things it does. Now that probably would be expected from a devoted game programmer, but how would you react if you could play a game where you see the entire universe in real-time, zoom in to any of the trillion^n stars with full detail, land on any of the near-infinite planets with full detail, control the evolution of species right from the stage of a single-celled organism to a developed animal, blow up planets with a *Death-Ray*, basically do whatever you want? All in real-time. Just imagine the amount of processing that would be required to simulate each and every cell/living-being, every planet, asteroid, comet, star, galaxy in the whole universe, every 50 milliseconds? Imagine the amount of storage required to store the data of all those things, all those cells and animals etc etc.. let's take a guess.. 40 Gigabytes? 40 Terabytes? Much more? Absolutely correct. Much more is indeed the amount it would take to store all that. So what am I talking about? What if I tell you that there exists a method to store all that data in about 10-15 bytes? That method is called Procedural Programming, where all the data required is generated on the fly.

Ever wondered why your games are always growing in size? Unreal 2000 came in about 1 CD, Unreal 2003 came in 3 CDs, Unreal 2004 came in 6 CDs, GTA San-Andreas takes about 6 GB of hard-disk space, and it goes on.. Why? The reason lies in the fact that the gamers are always demanding more realistic environments, we're not satisfied by barriers inside games, where you hit an invisible wall and can't go explore outside it. So they're making more detailed games, generating each and every building inside a city so that a player can explore all of them, generating textures on walls, basically generating everything beforehand. So if GTA-SA with just the measly amount of detail it has, takes 6 GB of space for code and data, imagine what the game I described in the above paragraph would take. In comes procedural programming. Procedural programming, as the name suggests, generates all the content on-the-fly. Each and every building is generated on the fly if required, all those textures are rendered on-the-spot if required. Now here is the important point, it doesn't simply generate *all* the buildings. It only generates what is *visible* to the player. How do you know if the universe still exists behind your back? This is the fundamental beauty of procedural programming. The time taken to render a single building or stuff like that is really quite small. As you may realise, procedural universes make a few compromises, but give you back much more. For example, with the simplest model I've described, its not possible to allow the player to *hear* a very loud bang at a place that he can't see, but neat programming tricks and hacks mostly tackle all those limitations.

At the heart of a procedural engine lies a seeded (or pseudo) random number generator, which essentially takes in a number and gives out a random number, except that the same random number is returned if the same original number is entered. So if I enter 5, it might return, say, 3.5. If I enter 23, it might return, say, 75. But every time I enter 5, it will always return 3.5, every time I enter 23, it will always return 75. That's why its a *seeded* random generator. The entered number, called the seed, gives us the same final number each time. So here a starting seed number is used, say A, and passed to a random number generator. The output number, say B, might be used to give us the number of buildings in the city. Now we iterate (loop) as many times as B (no. of buildings) and increment a particular variable, say 'i', by one each time. Inside each loop, we can pass the sum of B and I to the random generator, to get a particular number, say C, whose first two digits might give us the X coordinate of the building, and next two digits give the Y coordinate, and the next two digits, say D, are the seed for each building. Now we pass D into the random gen and get another number that might describe the properties of the building etc. And using a straight-forward technique we check which all points are visible to the player, and we generate only those buildings using the properties generated from D. All from a simple single number. As you can see, this need not end at just buildings, we can keep using the numbers after each random generation for more details, number of windows, number of people working in it, type of flooring, and the level of detail can be infinite. All from a single, say, two-digit number.

Obviously GTA-SA cannot be made using this method because the developers want a particular scripted story to play out, and the city generated in the above example is randomly generated. So trying to get a *particular* city, say, New York, using simple procedural generation would be worse than looking for a grain of sand in all the beaches of the universe. The entire city is generated from a single seed number, if we change the starting seed number (A) then the entire city changes, in all aspects. Big games have begun to use this kind of approach for small things, like making the textures on the walls, making rocks etc. But Spore is the first game that uses this approach for the entire game at the level it works on i.e. the universe.

Read up Procedural Generation on Wikipedia to get a better idea (and links to better descriptions). So what I'm upto is a universe-in-a-nutshell (literally!) thing, in the most efficient way. BTW, just as a side-info, procedural programming is almost as old as computers are. Ever heard of demoscene games (called demo-games) that work and look as good as Unreal 2003 and are all packed in just 96 KB (including the executable)? Look at .kkrieger. Demoscenes have been around ever since computers were first found as little electronic things like the Commodore, probably earlier.

I've been doing nothing else with my life, just programming, staring at TV since it has nothing interesting to watch, and sleeping.

Coming soon..

Okay, contrary to popular perception that I perished in 'The Pool', I am very much alive and have been unable to blog due to hectic study schedules, general laziness, and a one and a half week viral fever (presumably contracted from the water I greedily gulped down while I was drowning in 'The Pool'). The third reason (Grr..) wrecked up my last and best prepared-for paper, which was today morning. Wracked with weakness and stuff during the examination.. took lot more time to solve even simple problems. Anyhow, I'm not going to mope about stupid stuff like that on the blog.

The post is entitled "Coming soon..", so let me justify it. This is intended as an annoucement of the forthcoming series of posts called "Interesting Projects". Sorry, can't think of a better name. You may wonder why I'm announcing this thing a second time, since I've already done that in my previous post. There are two reaons, a technical reason, and the second, a tad bit smarter. Technical but stupid reason, I just mentioned in the previous post that I had 'planned' to start something of this sort, not actually concretely decided anything. :-) The other reason is because I wish to tell you a bit about what my first "Interesting Projects" post is going to be and how it works. Don't say "awww". This is not a thriller movie. The interesting project I'm working on right now is making my own simple Wireless LAN connection between computers, from scratch. I'm not making it using any existing standards, nor am I using any device or ready-made stuff. I'm figuring out the hardware circuits, software and the logic. Loads of fun..

I'm not targetting efficiency or stuff like that, and since my first baby-step is intended to be a basic chat-program between two systems, I am going to use my favorite code: Morse Code. :-) I've already developed the software to encode and decode. Concept is simple:

"The person types a message in plain English, then the encoder first converts it into a modified Morse code I've devised, and then it sends through the Parallel Port (Printer port) a signal to the transmitting circuit I'm building. If an on-signal is sent to two pins in the port, then the circuit generates a high-frequency wave, and if its a one pin signal, then it generate a low frequency wave, each of the same time duration.

(Side Note: This is, in my opinion, better for computers since this way it can send all alphabets at nearly the same speed, and computers can differenciate between frequencies very well. Common way is to send a short pulse for a 'dit' and a long one for a 'dah'. This takes longer due to obvious reasons)

Now these waves are transmitted wirelessly, caught by the reciever circuit which works exactly the reverse way, and the computer will show the decoded English message."

:-) Very elementary, but I intend to chuck Morse code and start becoming a bit more ambitious by transmitting in 8-bit ASCII later. The hardware is still a little buggy. I'll post the final circuit diagrams later. Again, I assure you nothing's going to be too technical. I'll mark the paragraphs that are going to technical so that you can skip them. :-)

Swim-lessons Saga: Part I

I planned to write a post about how I almost drowned in the deep end yesterday, but then thought it something too trivial and stupid to post, but then decided that since this was sorta like a personal blog, and since I didn't care if people read my swimming sagas and giggle, here it is.


Scene: Swimming Pool
Time: 4:45 PM
Location: 6 feet end of the pool

I bloody well drowned yesterday.. not just the first time fear of the deep end, but really. We were starting that part of the pool yesterday.. diving in from the sidewalks one by one, and the trainer was supposed to be in the pool, watching us and pulling us out after we exhausted our air supply. I know, an experienced swimmer can go across the pool in one gulp of air, but I'm hardly a swimmer yet. Anyhow, when my turn came, the trainer suddenly got distracted and went off somewhere when I dived, and unfortunately in that very dive from the sidewalks, I sort of made a bad jump and lost my so-called balance in water and starting going 'into' the 6 feet deep water head first and rotating along the body axis, instead of floating flat. And the stupid Goggles get yanked off my head each time I dive in because of the sheer force of the water hitting the face. So I somehow managed to push myself up against the floor and barely managed to float to the top somehow. And then that guy comes over and 'pulls' me out again. I drank a bit of that dirty (chemical) water, as I was out of breath by the time I came out, I was at the bottom for almost 5-6 seconds, swinging my hands and legs to and fro like a madman. ;-) Hand and leg movements take a lot of your breath away.

As for my progress in swimming, today was my 5th day, because I was down with some fever and cold for 2 days.. possibly due to the pool. As of now I can sort of swim and get to the other end of the shallows in one breath.. I've finally begun to float across the pool quite decently, though my swimming style presently is more like a crazy ballet of a mad-man. If I did it outside the pool, I'd probably get lynched and taken to a mental asylum.

I'm really bad at talking about my experiences etc, so sorry if I've disappointed anyone reading this blog with some hopes of a nice post. I enjoy writing technical posts and talking about technical stuff or music. :-) I'm planning to start a series of 'Interesting Projects' that I'm currently doing once my DCE paper gets over on the 30th... so that might be something that is worth reading, rather than stupid banters of a lousy beginner in swimming. Don't worry, its not going to be too technical.

Floating across the pool humming Rammstein

Yeah, today was my first swimming lesson, and by the end of the one hour session, I was lazily floating across the pool like a corpse, humming Feuer Frei! by Rammstein and re-playing VH1-MTV's Midnight Headbanger's Ball in my head. That's the only neat thing I've seen on VH1 apart from their occasional Classic Rock programmes. Most of the time they show only stupid Rap & Pop music, can't bear it. As of now, Headbanger's Ball show is the best source for people who can't download videos from the net due to *grumble, grumble* stupid data transfer limits and general disinclination to pay like 900 p.m just to be able to download some song videos. Let it become Free, then I'll switch over plans. :-) The show comes on VH1 at an excellent unearthly (sort of) hour of 12:00 AM every Friday-Saturday joints, that is, it comes from 12:00 - 1:00 AM on early Saturday mornings.

Presently I'm sort of cursing myself at rejecting the swimming goggles and opening my eyes all the time underwater, which was highly chlorinated. Net result, I had such an eye-irritation that I had to sleep for 3 hours instead of the planned study in order to be able to keep my eyes open now. I enjoyed swimming of course, one gets hooked up to semi-weightlessness after a while. I would have kept my eyes closed underwater had small kids decided not to continuously collide with me mid-way as if simulating the Kinetic Theory of Gases. I wonder if there exist equations for root mean square speeds inside a swimming pool.

States of Matter: A glaring misconception

I was just discussing matter and fundamental particles with a friend when I realised that something has begun to go wrong and the ignorance among people shows it. They know that what I speak of is true, they've always known it. Yet their minds have decided that matter actually exists in three different 'species', believe it or not.

Classification is the basic and fundamental property of abstraction. It makes life easier, and is invaluable. But, some people begin to believe that the artificial *wall-of-division* between each group is quite concrete. In a similar fashion, many people, especially children have lost touch with the fact that Solids, Liquids and Gases are nothing but atoms with different ranges of force of attraction. There is a very elegant graph, a potential energy vs. distance one, which explains the region of solids, liquids and gases very well, which I shall not go into here.

The point is, everything is made up of a fundamental entity. As of today, we are made to understand that atom is the abstraction that is the fundamental entity. It comprises of sub-atomic particles, but essentially, the atom as a whole is what is a repeating unit. Logically quite strange, since atoms vary in sizes, which immediately discards that repeating-unit property. Hence the logical reasoning is that there exists an entity which is elementary. I am not in a position to give you the Truth. In the Age of Reason (circa Aristotle), we were made to believe that whatever cannot be divided any more, say by crushing repeatedly, is the fundamental Truth. In the Age of Science (circa Dalton), we were explained atoms scientifically. And it goes on till today. Now, the terms Solids, Liquids and Gases were created for the sake of abstraction of physical & chemical behaviour since mostly all gases showed nearly similar properties, with just a few variations in quantification of properties. But the essence, that everything is just atoms is true. Hence people who say that Solids 'convert' to liquids and so on, blindly thinking it to be one independent species converting to another are not justified in thinking so.