Code Story

Wednesday, June 20, 2007

Smoke me a ‘Clipper’ I’ll be back for Breakfast

When we observe the world we live in, we see things more or less in order. Generally, objects which are closer to us look bigger than those which are far away from us. We see opaque objects close to us obscure objects behind them, as they should. We take these features of our real-world visual system for granted. The developer is quite simply awesome.

Just imagine for one second that on an average day, while you are walking down the street, and without being under the influence of anything, you see a car, for example, which is quite far from you showing through a building which is right in front of you, or you see a tree which is behind a wall showing right through the wall. I’m sure someone out there would say that this is normal and that’s what they see all the time, but I’m talking about the majority of people who are awake and not the exceptional supermen and superwomen with x-ray vision. Nor am I talking about Ace Rimmer from Red Dwarf, the super version of Arnold Rimmer, who would simply say: “You can’t see through objects? Smoke me a kipper can you do that? I’ll be back for breakfast.”, what a guy!

Enter the world of solid 3D graphics development before the introduction of hardware acceleration with fast ZBuffers or WBuffers.

Just before these Buffers were efficient enough for use in interactive 3D products, we had to sort the scene by time-consuming software techniques (or by hand as we called it), or find clever tricks to avoid this situation altogether for rendering and viewing a moving 3D scene.

The idea is very simple; realtime interactive 3D graphics systems normally generate 20-30 frames per second for smooth animation. When a frame is ready to be drawn on screen a distance value for each 3D polygon is kept for sorting it within the scene according to its depth or distance from the viewer. This way, we can draw the farthest polygons first, then the nearest last. This is called the Painter’s algorithm, which relied on fast sorting algorithms such as Hash Tables, I'm not talking about the more complex algorithms that became popular later such as Binary Space Partitioning Trees or BSP Trees for short, these were slightly different and didn't fall exactly into the painter's algorithm technique. The Painter’s algorithm kind of worked, but caused problems when there was a discrepancy in polygon sizes and orientations. You could sometimes see a small far polygon showing through a larger one in front of it! Not a pretty sight, nor is it reassuring. I mean it doesn’t give you confidence if you see a flying plane with parts of its cockpit showing through the under-carriage. Just imagine if this happened in real life on a normal flight from London to New York. But there were many 3D products out there that had this problem which created very surreal environments indeed.

There are ways to avoid this problem by splitting the large polygons to make them smaller and ensuring most polygons are roughly the same size, or using other mathematical techniques; however, this needed more processing power at the time when it was scarce.

Some programmers tried to solve this problem in the most peculiar way. One of the very successful flight simulator products I later worked on used Bubble Sort for its Painter’s algorithm! Bubble Sort was mainly used to teach the concept of sorting to new programmers and is applied mainly on small lists of objects. But to use it for sorting 3D scenes of thousands of polygons many times a second was just crazy. Bubble Sort needs many passes through the lists to complete the task, the programmer who came up with this ”ingenious” method to reduce the processing time required per frame must be presented with the award: “I don’t give a damn” for coding. The code would do one pass per frame meaning that it would take a while before any object is completely sorted. You could actually see the 3D object rearranging itself every time you rotated the scene. It was really funny to watch. I had never seen an F16 or SU27 looking like a chicken shaking water out of its feathers when this Bubble Sorting kicked in for a few seconds. I can’t believe this was acceptable for a commercial product and no one even complained! I still have a copy of the original code which I keep for its entertainment value.

As I was working to better these techniques, a 3D graphics modeller joined my team as an apprentice. He was introduced to the team and was told I was the lead-developer and the one who was responsible for the technology. This meant that he would come to interrupt me every few minutes with a new question about the technology which he was using. It made it worse that he sounded like he was constantly under the influence of something or another! I mean, he sounded like Ozzy Ozbourne on Valium. Every sentence of his had to include one or more from the following subset: Duuuuuuuuuuuuude, Whatevaaa, Yeaaaaaah Riiiiiight, Cooooooooooool and Yaaaaa Maaaaaaaaan. He would often sing Satisfaction by the Rolling Stones with his face close right up to the fan because “it made a coooooooool noise maaaaaaaaan”. Don't ask. Just ignore this, as we all did.

While I was working on a 3D morphing concept which I had read about in one of ACM SigGraph publications, and was still trying to work out what on Earth Barycentric Coordinates were, the graphics modeller came over to my desk and said (Ozzy style):

Modeller: Hi maaaaaan, the clipping doesn’t work
Me: The clipping?
Modeller: Yeah maaaaaan, come and have a look duuuuude
Me: Look “maaaaaan”, this is called the sorting….
Modeller: Whateva
Me:…not the clipping. You have a small polygon next to a very large one. Cut the large polygon in half, can you do that?

Modeller: [in shock]

He went to his desk and 15 minutes later he came back:

Modeller: Heeey maaaaan, the clipping doesn’t work.
Me: It’s the sorting…
Modeller: Whateva

I went to his computer to see what he was on about. I was surprised to see that he now had two large polygons, not one, next to a very small one, which obviously would cause problems for the primitive sorting algorithms, so I said:

Me: If someone gives you a long piece of wood and says it is too long, cut it in half, what would you do? Do you cut it long ways so you end up with *two* long pieces?

Modeller: [in shock].

He seemed that he could not get no satisfaction from my answer.

Me: Cut the polygon across, not long ways! Then I went into Ace Rimmer mode just to confuse him and pay him back for all his Rolling Stones stunts, and said: “You can’t do that? Smoke me a kipper can you do that? I’ll be back for breakfast.”

Modeller: [long pause] then shouting at the top of his voice: THIS GUY IS WEIRD MAAAAAAAAAAAAAAAAAAN.

I’m weird?

Well, gradually he understood what I was on about, but still could not understand why our planes looked like ruffled chickens every now and then. I honestly didn’t want to get into the sorting algorithms with him, I mean he thought I was weird telling him to cut long polygons in half to get the sorting to work properly, what would he have said if I started talking about Bubble Sort or worse: Binary Space Partitioning Trees. I’d rather smoke him a smegging kipper.