Archgrove - Implicit Definition

Well, despite embedding a couple of “bonus questions” into yesterdays post, I didn’t receive any answers. I’ll have to make the next ones easier! Anyway, here are the answers.

Question 1: What has become common since DirectX 6 that means DirectX 9 doesn’t need good colour key support?

The answer I was specifically looking for was “hardware accelerated alpha blending”. I would also have taken “transparency” and partial credit would be given for “3D cards”.

Alpha blending is the composition of two images together so that one of them appears to be translucent on top of the other. You’ve all seen the effects –smoke that clouds your vision, see through water etc. Whilst simple mathematically, these operations are pretty CPU intensive. Say we’re going to draw image A over image B, with image A slightly translucent. We have to read every pixel from image A, and blend the colour values with image B, to produce our final image. Even if you only run at 800×600 resolution, that’s 800*600 = 480000 pixels to read twice (one for each image), and the same amount of the actual blending operations – every frame!

Here’s another “Stuff you might want to know”^TM aside.

When someone sends you an image via email, and might notice your paint program opening it as “24 bit”, and if you’re au-fait with graphics, you might have even seen “32 bit”. These “bits” refer to the colours in each pixel the image. Most of the time, 24 bit images are enough – 8 bits for red, 8 bits for green and 8 bits for blue produce all the colours your eye can resolve. So what’s the extra 8 for in 32 bit images? Why – alpha! These 8 bits say, “When you composite this image onto another one, here’s how translucent this pixel is”. These 8 bits are called the “alpha channel”.

The hardware of yore wasn’t really sophisticated enough to handle the operations required for alpha blending, but they did implement colour keying (as a concept, it turns up remarkably often). But today, with the advent of graphics cards that can do a bazillion blended polygons, having specific functionality for colour keying would be redundant. Programs are now expected to just provide an alpha channel for their images, and where they want to “see though” (in the way that colour keys provided), you just set your alpha bits to 100% transparent.

So, specific colour keying functionality in graphics APIs has largely gone the way of the dodo, to be replaced by something more flexible and useful. Vive la progress!

Question 2: Can you tell me why the final phase, which draws the plugin window and the control bar, doesn’t need to use the colour key drawing object?

The answer is basically “As the plugin window and control bar are rectangular, we don’t need to composite them in with colour keys – they cut right out without needing to be see through anywhere”.

This one required a bit of lateral thinking. We know from the first article that we’re now drawing straight onto the AC window – as such, we don’t need to draw onto a big “buffer” first, which will then be copied across. If we did need such a buffer, we’d still have to use colour keys (otherwise, the background of the buffer would completely cover the AC window). Additionally, because all the images we’re drawing are rectangular, and don’t have any see through portions, we don’t have to deal with colour keying for them either! So, we don’t need colour keying at all for the final phase of composition.

I hope that’s not too confusing!

As to further writing, I’ve had requests to make a post about how the memory locations (“memlocs”) are actually found. This is a pretty involved topic, but I’ll try and write something today; maybe I’ll even include a “find your own memloc” quiz! Wow, this just gets better and better, doesn’t it?

Well, yesterdays article seems to have gone down quite well. So, as promised, here’s part 2, wherein colour keying is restored, code is demonstrated, and more screenshots are taken! Before continuing, I’ll ask those of you who didn’t read yesterday’s instalment to head on over. Go on – we’ll wait.

Sigh. OK, for those of you who didn’t bother, here’s a summary anyway.

Last time, on Decal Trek: The Next Implementation, we had just finished recreating suitable objects that will allow us draw onto the screen again. We’d tested our new objects, found some problems, and experimented with solutions to them. Eventually, we decided to cajole the old objects into accepting us. When we left off, we’d basically got everything work, except the colour keying.

The best way to solve a problem is to not have that problem at all. So, the first question is “why do we need colour keying at all”? Well, let’s explain how Decal puts things together – most UI rendering systems work in this way, so this is a N for the price of 1 education (with large N)!

The UI system is made up of lots of different components. Buttons, text boxes, check controls and others. These are all individual objects. Lets have a look at them, in an idealised form, one at a time.

Very nice. 3 controls all rendered onto a piece of paper, one at a time. This is pretty much how Decal works – we have lots of controls, and they’re drawn onto the “paper” of your AC window. But, Decal doesn’t look like a lot of controls all floating around on their own. The controls are organised into groups. Lets do that – put our controls onto our tab page, just like in game.

Hmm. Not bad. As we can see, the button control works fantastically – it blends in perfectly. This is an artefact of the way the drawing works – it only deals with copying rectangles around. There is no other reasonable way. Computers like squares, everything can always be contained within a square, and it’s bloody hard to find the shape of some text saying “Hello”! So, we draw squares round everything, cut them out, and stick them onto the tab box.

So, as the button control is a square, we could cut it out perfectly. However, the checkbox isn’t quite a square – it’s a circle and some text. When we cut it out and drew it into the tab box, the background came with it, and gave us that nasty white box. So, let’s make white the colour key. When we copy over the rectangle, we’ll copy over every bit of the colour except when it’s white.

Great! We didn’t bring the white with us, and because none of the control actually used white, it looks fine. Colour keys to the rescue! I hope this demonstrates their idea, need and functioning, so here’s a bonus question for astute readers: What has become common since DirectX 6 that means DirectX 9 doesn’t need good colour key support?

Having established the need for colour keys, let’s work out how to implement them in Decal again. We know we have our Decal image that we need to draw. As explained above, this image is put together out of lots of little images (the control objects) – this is called “composition”. We need to get colour keys working again for this composition phase.

Our main task yesterday reopened a route that allows us to use some of the old techniques that were locked off to us. We can now ask each object for a “DC” – a special object that the old fashioned drawing code uses. Because we can now get this DC, we can use some functions Microsoft provided in Windows that will largely do the colour keying for us. So, let’s change our drawing objects to use this DC during composition.

[Sound of keyboard]

Great! It seems to work! Except…oh dear. Once again, the ugly head of performance has been raised. It’s not as bad as yesterday, but it still gives a bit of problem, especially for old computers. As many AC players are still on older machines, we’re going to have to look at this. Wouldn’t life be so much easier if everyone upgraded his or her machines bi-monthly like us developers?

Taking stock (programming involves a lot of stopping and thinking to make sure one’s taking the right road), we remember that the objects we used yesterday were drawing at a nice speed. Our new DC rendering is somewhat slow. We read over our results, and look at our image.

Hmmm. There isn’t really a lot of the colour key present. This suggests that, perhaps, the colour key isn’t used everywhere. In fact, all the controls that are square don’t seem to use it at all! What if, instead of using our new, perfect, drawing object everywhere, we could sometimes the old, imperfect but fast one?

[Sound of keyboard]

Done! The drawing object can now choose which method it uses. That’s a good start – but the drawing object is concerned only with drawing. We’ll have to tell it what to use, and when. So, we’ll update all the image drawing, and some of the composition code, to only use the slow colour key method when it’s strictly necessary. We’ll analyse each image when it’s loaded to see if it needs a colour key, and configure the compositor never to use the colour key on the final phase (when it’s not needed). Bonus question 2: Can you tell me why the final phase, which draws the plugin window and the control bar, doesn’t need to use the colour key drawing object?

Superb – the colour key rendering is only performed when required now! We’re done. Let’s look at the results.

That looks pretty damn good, and whilst not quite as fast as the old Decal, is fast enough for now. Code wise, today’s changes are longer than yesterday – this is often the way with programming. We got 99% of the way there with 2 lines, then it took dozens to get the last 1%. In fact, writing it took 2 passes – one to test the idea, which produced functional, but messy code. Messy code will make it hard for the next person to get anywhere, so it was rewritten to be neater and more flexible for future users. For those interested in what the actual programming looks like, you can see changes I made in this file.

This concludes this short article pair on fixing the renderer. If people find these interesting, I can certainly write up some more on other parts of the system. Throw me some ideas, and I’ll try and respond.

Adam Wright (as Asriel)

A while ago, I avidly played a MMORPG called Asheron’s Call, from Turbine Games. Indeed, so great a fan was I that I collaborated with a group of others in the creation and maintenance of what is still one of the most advanced “third party” systems for any game. Consisting of custom network, GUI, input and management APIs, it integrated so perfectly into the AC client that it’s indistinguishable from the ingame system. It became very popular, and is called Decal.

Recently, AC released a new expansion pack, “Throne of Destiny”, in which Turbine significantly reworked the client. Well, our wonderful integration is no longer quite so perfect. In fact, it’s entirely broken. So, along with much of the same crew as before, we return to stick that Decal back onto AC, that it might continue to provide useful tools without (we hope) allowing a great deal of evil.

As I’ve just returned from a fortnight of moor walking, I figured I’d jump in with something I’m reasonably familiar with – the actual display of the GUI components. As this article is targeted at people who might not be programmers, I’ll quickly go over the concepts you’ll need to understand. Experienced folk can ignore this bit, and I ask their forgiveness for my (over) simplifications.

When you play Asheron’s Call, you’re sitting in front of a computer. This might sound obvious, but at the end of the day, computers are incredibly stupid. All they can do it go through a huge list of instructions, stepping from one to the next, adding a number, moving it around in memory, and little more. As you can imagine, with such limited capacity, it takes a lot of these instructions to get anything done. Millions, in fact. Hundreds of millions.

As humans, we find that very hard to deal with. After all, when I want to write down “Hello” onto a piece of paper, I don’t create a huge list of instructions telling me how to move my hand one millimetre at a time – I just do it! So, we make it easier to program our computers by writing languages that help us express what we want to do more clearly.

A popular method of doing this is via “object oriented languages”. These languages let us talk to the computer in terms we can more easily deal with. Rather than a big list of instructions, we can say “Take this “Hello” object and “Draw” it onto this “Paper” object”. The people who programmed the “Paper” object have already dealt with the drawing instructions for us, making our job much clearer, so we can get things done!

In Decal, we deal with a lot of objects. There are objects representing plugins, controls on the screen, events from the game and many others. When we’ve finished creating all these objects, we “compile” our objects back into these huge lists of instructions that we can send to you, the player.

We also deal with some objects we didn’t write, some that are provided by Turbine. This is the task of finding the fabled “memlocs”. Turbine wrote lots of objects of their own, and compiled them into Asheron’s Call. We can’t see them, as all we have are the big instruction lists. When finding the “memory locations”, we go through these lists, and work out which chunks of it belong to which object. We can then note them down and use them just like Turbine did.

Right, back to the problem. When the new client was released, one of the major changes was the graphics update. To facilitate this, a change was made, from DirectX 6 (a set of objects that deal with graphics and multimedia) to DirectX 9. Our original code worked with DirectX 6, and it doesn’t much like Direct X 9.

So, what’s first? Well, lets explain how Decal gets from our hearts to your screen in the first place. When you run Decal, it sets up “hooks” into your system that sit and watching what you run. They don’t do anything until they see AC start up, when they suddenly spring to life, and step in. “Excuse me, AC”, they say, “I’ll just stop you for a second”. Before the poor game knows what’s happened, BAM, it’s over! We’ve been inside it, and looked around. We find the objects that it’s creating (in this case, the graphics objects), and we replace them with some of our own.

Our fake objects are so perfect that when AC wakes up, it doesn’t know what’s happened. It carries merrily on, using our new objects when it would have used its own. Except that the new objects are secretly reporting everything to us, so we know what’s happening. When the graphics object reports to us that it’s drawing your screen, we wait until it’s done, and again step in at the last moment. It’s in this period that we can draw onto your screen. This is the code that was broken when they upgraded the graphics engine.

So, how do we fix this? Well, the first thing we need is some new fake objects, ones that’ll work with DirectX 9. They’re easy to create, and after that’s done (more by Hazridi before I came back), we end up with an AC that we can draw on again. To prove these new objects work, we’ll draw a test.

Great, we can draw inside AC again. Next up, we need to start putting in the original graphics. We’ll hook up our old GUI objects with our new drawing object, and we get…

Hmmm. That text looks suspicious. What’s going on here!? Well, after poking around, it turns out that our new fake objects are not quite so indistinguishable from the real ones anymore. When we sneak in and try and draw, the objects AC created are fighting back! DirectX 9 does not allow a lot of what DirectX 6 does, and as such, our old techniques are not quite so effective. So, let’s sit back, take stock, and examine the options.

In our corner, we have a set of graphics designed for drawing onto an object that no longer exists. In fact, all plugins are likely to be using a similar system to us. That means we can’t just change our code and walk on – all the plugins will break! We need to find a solution that will keep everyone happy. After some thought, three options come to mind…

1. We could stop using the objects, and do everything ourselves
2. We could try and update half our code so that it integrates better with the new system. Perhaps rather than drawing right onto the screen, we could create a 3D model and draw onto that?
3. We could blackmail the original objects into letting us do what we want

As with all such choices, there are no right or wrong answers. All our options are equally plausible, so we’ll have to try them all.

[Sound of keyboard]

OK! After option 1, we have a problem. By bypassing the way that we’re “meant” to work, we have massively slowed the system down. You see, if we refuse to use the objects we’re given, we have to manually look at all the images and decide what to paint, and where. But your system doesn’t like this – it hates people looking at images that have already been created. As such, everything slows down to a crawl (in fact, only 1 frame per second). So, option 1 in a failure, and 100 lines of code vanish into the recycle bin.

Option 2! This one sounds fun, it has 3D in the title! After clattering away for a while, option 2 does work, but has a similar problem to option 1. In converting our old style image to a new style 3D object, we have to do a lot of work every frame. Decal redraws itself all the time (as do plugin HUDS), so we have to constantly convert between what we already can do, and what we need for the new client. End result, 1 frame per second again. Sigh. 150 lines down the tube.

So, option 3 it is. Now, being honest, most of the performance problems from options 1 and 2 have been in preserving what we call the “colour key”. When Decal draws onto your screen, it keeps a special colour as “transparent”, so then when plugins appear on your screen, this colour disappears and you can see the game underneath. Old versions of the DirectX did this for us, but the ability is largely gone from DirectX 9. Options 1 and 2 ended up having to create big copies of the screen, and draw onto them, them put them back onto the game again, obeying this colour key.

But, if we manage to persuade AC that we can draw right onto it again, we’ve solved most of our problems – we don’t have to deal with big copies! After some fiddling, it turns out that the back buffer (the bit that it actually drawn onto by AC every frame) is almost right for what we want. So, we use our fake objects to force AC to create a back buffer that’s right for us. It’s still good enough for AC not to notice, and it lets us work our magic. Hence, our end result.

Those of you with good vision will notice some lurid turquoise in that image. That’s the colour key inside the plugin windows – our option 3 doesn’t quite solve that. So, tune in another day, and you might find part deux, whereby hideous colours are banished forever!

Oh, and for those of you interested, the end solution was 2 lines. Yes, 0.7% of the code written for this project. So, when reading programs, remember – for every line of code you see, there are at least 10 dead lines lying somewhere by the roadside. Salute these dead lines, and remember, they died in the cause of good software.

Adam Wright (As Asriel)

PS – There are several other people working on bringing Decal back to you. In truth, what I’ve done here is a minor part of a much larger operation.

PPS – A study in software creation will resume soon!

Disclaimer - This is “code in progress” and may not reflect actual code delivered to the end product. So if it still takes another month to finish, don’t blame us.

Now we have a more detailed specification of the problem, it’s time to start thinking about how we’re going to solve it. A problem is only really solved if the customer thinks that it is – a solution that is perfectly valid to you might be totally unintelligible to them.

In the past, I had a tendency to solve the problem from my perspective. To take an example, when developing a web CMS, who wouldn’t view a website hierarchy as a list of “entities”, with “container entities” and “file entities”! Files and folders are so archaic, right? These new metadata tagged virtual representations are much easier to work with!

Well, to me, yes. But to the person who just wants to make their website attractive to Mom and Pop purchasers, no. They deal in a totally different set of concepts, and as they’re the users we must take both our technological expertise, and marry it with their end user expertise. In other words, write software they can use, and get the most out of (rather than spend their whole life in just 10% of your work because the other 90% is too confusing).

Step 2 : Think about it not just as a programmer, but as a user

This is probably why the current “free software” is fantastic for those of us in the hacker fraternity. We have the same mindset as the people that wrote it, and will clearly see that a “shortcut” is actually a symbolic link added by the file system, and not a pretty icon with an arrow on it. But 99% of end users don’t care – they just want to have Word run whether they click on the “desktop” Word, the “Start Menu” Word, or even a Word document.

As we’re going to design both an end user application and a programming, we get to see two user types in this project, hence satisfying both our geek side and our pragmatic side. This is a trick I’ve come to use on boring projects. If the software you’re writing is the most tedious piece of work you’ve ever seen, view it as a challenge in programming terms. Yet another online form processor? No! A chance to construct an elegant method of validating form input!

Of course, this can lead you down the route of ego massaging. A beautiful technical design, but either no solution or a solution that took 10 times as long as just writing the damn thing. I’ll discuss this next time, when we look at the specifics of the API design.

As mentioned earlier, the end goal is a Spell checking application that I can leave running in the background, and call into life at a keystroke for quickly checking and correcting a word. All well and good, so let’s fire up Visual Studio and get to it!

Oh, wait. This idea was meant to create me a new development style that fixed problems I had with my old style. I guess I’d better stop and think about it first.

The first thing I notice is the project, whilst simple on the surface, is not very well defined. I’m spell checking something, but I’m not sure what.

Step 1 : Actual programming is a step in solving another problem, not the problem unto itself

Whilst I (and other people) program just for fun, 99.9% of the time, we’re solving a problem. So, let’s go back to the “client”, and work out what we’re actually doing.

It turns out that I want to spell check individual English words, checking them both for typographical errors and for spelling errors caused by not knowing how to spell it other than by phonetically guessing. I want this both in a small tray application for windows, that I can use for a “click, type and correct” problem, but I also want a reusable API I can embed into my other programs. Hey, I’m a geek! Because I’m also an awkward, typical client, I won’t know if it’s what I want until I see it and ask for something entirely different.

So, let’s get our customer requirements down in a list.

I want.

• A spell checking API
• That works for English words (But maybe other languages later)
• Corrects typographical errors
• Corrects phonetic spellings to real spellings
• Is reusable in many different application types

I also want.

• A spell checking application
• That sits in my Windows system tray
• Pops up when I click on it/press a hotkey
• Lets me type in a word
• Quickly tells me it’s correct, or provides the correct spelling for me

Right, now we’ve got a real customer specification, something I was previously quite bad at acquiring. Of course, in the real world, I won’t be the customer, but it’s the best I can do for now.