The University of New South Wales
November 2001
Final Examination

COMP9018

• This is a take-home exam.
• You have until 12 noon Friday 23rd November unless by previous arrangement.
• Time allowed: 24 hours.
• Number of Questions: 5
• Answer All Questions
• Total number of marks: 100
• You are NOT allowed to talk about this exam, its contents or any queries relating to it to anyone other than the two lecturers, Tim Lambert, or Waleed Kadous, until 3pm Friday 23rd November.
• Any questions are to be sent by e-mail to Tim Lambert for questions 2 or 3, and Waleed Kadous for any other questions.
• Please check your e-mail for any updates/changes/general posts relating to the exam.
• You may hand in answers to the first four questions at the school office. Make sure it goes to Waleed's pigeonhole.
• You can also use the give command to hand in your answers. The answer to each question must be handed in separately. The command for question 1 is:
% give cs9018 q1 <files>


Your answer should be in postscript, pdf or html format. If it is in html format, GIF, PNG and JPEG format files are also allowed.

• The code for question 5 must be handed in using give.

Question 1 (15 marks)

Write two to three sentences on the differences between the following:
1.
Forward kinematics and inverse kinematics.
2.
Eye space and object space texture coordinate generation.
3.
Compiled vertex arrays and vertex arrays.
4.
5.
Radiosity and Monte Carlo Ray Tracing.

Question 2 (15 marks)

In this question you'll be carrying out the moral equivalent'' of de Casteljau's algorithm on quaternions.
1.
Find the unit quaternions q0, for rotation about the x axis by q1, for rotation about the y axis by and q2, for rotation about the z axis by .
2.
Using slerp, find the quaternion half way between q0 and q1.
3.
Find the midpoint (t=1/2) of the quadratic bezier with control points q0, q1 and q2.
For full marks you should express the answers exactly (like rather than 1.414). You might find these trigonometric identities useful:

Question 3 (15 marks)

Compute the B spline basis function N0,3(u) for the knot vector .

Hint: Look at the lecture notes on B-spline Basis functions.

Question 4 (35 marks)

At the end of this question are two extracts from Harry Potter and the Philosopher's Stone. In this question you are to contrast how you would solve the problem of rendering a Quidditch game sequence in the context of a movie (when you can afford to spend an hour rendering each frame) and a computer game (where you have to render in real time).

Both the movie and computer game versions of Harry Potter are being released next week, so you could look at previews on the net if you need some inspiration, but you should base your answers on the extracts from the book below.

The theme that should run for your answer is the differing approaches that you would take for the game and the movie. That doesn't mean you shouldn't mention stuff that would be the same, but we are emost interested in what you would do differently and why.

Your answer should touch on hardware, software, rendering and modeling. You don't have worry about designing a user interface for the game (or the movie for that matter :-)

Quidditch rules

As seven o'clock drew nearer. Harry left the castle and set off towards the Quidditch pitch in the dusk. He'd never been inside the stadium before. Hundreds of seats were raised in stands around the pitch so that the spectators were high enough to see what was going on. At either end of the pitch were three golden poles with hoops on the end. They reminded Harry of the little plastic sticks Muggle children blew bubbles through, except that they were fifty feet high.

Too eager to fly again to wait for Wood, Harry mounted his broomstick and kicked off from the ground. What a feeling--he swooped in and out of the goal posts and then sped up and down the pitch. The Nimbus Two Thousand turned wherever he wanted at his lightest touch.

Hey, Potter, come down!'

Oliver Wood had arrived. He was carrying a large wooden crate under his arm. Harry landed next to him.

Very nice,' said Wood, his eyes glinting. I see what McGonagall meant ... you really are a natural. I'm just going to teach you the rules this evening, then you'll be joining team prac- tise three times a week.'

He opened the crate. Inside were four different-sized balls.

Right,' said Wood. Now, Quidditch is easy enough to under- stand, even if it's not too easy to play. There are seven players on each side. Three of them are called Chasers.'

Three Chasers,' Harry repeated, as Wood took out a bright-red ball about the size of a football. I

This ball's called the Quaffle; said Wood. The Chasers throw the Quaffle to each other and try and get it through one of the hoops to score a goal. Ten points every time the Quaffle goes through one of the hoops. Follow me?'

The Chasers throw the Quaffle and put it through the hoops to score,' Harry recited. So--that's sort of like basketball on broom- sticks with six hoops, isn't it?'

What's basketball?' said Wood curiously.

Never mind,' said Harry quickly.

Now, there's another player on each side who's called the Keeper--I'm Keeper for Gryffindor. I have to fly around our hoops and stop the other team from scoring.'

Three Chasers, one Keeper,' said Harry, who was determined to remember it all. And they play with the Quaffle. OK, got that. So what are they for?' He pointed at the three balls left inside the box.

I'll show you now,' said Wood. Take this.'

He handed Harry a small club, a bit like a rounders bat.

I'm going to show you what the Bludgers do,' Wood said. These two are the Bludgers.'

He showed Harry two identical balls, jet black and slightly smaller than the red Quaffle. Harry noticed that they seemed to be straining to escape the straps holding them inside the box.

Stand back,' Wood warned Harry. He bent down and freed one of the Bludgers.

At once, the black ball rose high in the air and then pelted straight at Harry's face. Harry swung at it with the bat to stop it breaking his nose and sent it zig-zagging away into the air--it zoomed around their heads and then shot at Wood, who dived on top of it and managed to pin it to the ground.

See?' Wood panted, forcing the struggling Bludger back into the crate and strapping it down safely. The Bludgers rocket around trying to knock players off their brooms. Thats why you have two Beaters on each team--the Weasley twins are ours--its their job to protect their side from the Bludgers and try and knock them towards the other team. So--think you've got all that?'

Three Chasers try and score with the Quaffle; the Keeper guards the goal posts; the Beaters keep the Bludgers away trom their team,' Harry reeled off.

Very good,' said Wood.

Er--have the Bludgers ever killed anyone?' Harry asked, hop- ing he sounded offhand. .

Never at Hogwarts. We've had a couple of broken jaws but nothing worse than that. Now, the last member of the team is the Seeker. That's you. And you don't have to worry about the Quaffle or the Bludgers--'

--unless they crack my head open.'

Don't worry, the Weasleys are more than a match tor the Bludgers--I mean, they're like a pair of human Bludgers them- selves.'

Wood reached into the crate and took out the fourth and last ball. Compared with the Quaffle and the Bludgers, it was tiny, about the size of a large walnut. It was bright gold and had little fluttering silver wings.

This' said Wood, is the Golden Snitch, and its the most important ball of the lot. It's very hard to catch because it's so fast and difficult to see. It's the Seeker's job to catch it. You've got to weave in and out of the Chasers, Beaters, Bludgers and Quaffle to get it before the other team's Seeker, because whichever Seeker catches the Snitch wins his team an extra hundred and fitty points, so they nearly always win. That's why Seekers get fouled so much. A game of Quidditch only ends when the Snitch is caught, so it can go on for ages--I think the record is three months, they had to keep bringing on substitutes so the players could get some sleep.

Well, that's it--any questions?'

Harry shook his head. He understood what he had to do all right it was doing it that was going to be the problem.

A Quidditch game

Madam Hooch gave a loud blast on her silver whistle.

Fifteen brooms rose up, high, high into the air. They were off.

And the Quaffle is taken immediately by Angelina Johnson of Gryffindor--what an excellent Chaser that girl is, and rather attractive, too -'

JORDAN!'

Sorry, Professor.'

The Weasley twins' friend. Lee Jordan, was doing the commen- tary for the match, closely watched by Professor McGonagall.

And she's really belting along up there, a neat pass to Alicia Spinnet, a good find of Oliver Wood's, last year only a reserve - back to Johnson and--no, Slytherin have taken the Quaffle, Slytherin Captain Marcus Flint gains the Quaffle and off he goes - Flint flying like an eagle up there--he's going to sc- no, stopped by an excellent move by Gryffindor Keeper Wood and Gryffindor take the Quaffle--that's Chaser Katie Bell of Gryffindor there, nice dive around Flint, off up the field and--OUCH--that must have hurt, hit in the back of the head by a Bludger--Quaffle taken by Slytherin--that's Adrian Pucey speeding off towards the goal posts, but he's blocked by a second Bludger--sent his way by Fred or George Weasley, can't tell which--nice play by the Gryffindor Beater, anyway, and Johnson back in possession of the Quaffle, a clear field ahead and off she goes--she's really flying--dodges a speeding Bludger--the goal posts are ahead--come on, now, Angelina--Keeper Bletchley dives--misses--GRYFFINDOR SCORE!'

Gryffindor cheers filled the cold air, with howls and moans from the Slytherins.

Budge up there, move along.'

Hagrid!'

Ron and Hermione squeezed together to give Hagrid enough space to join them.

Bin watchin' from me hut,' said Hagrid, patting a large pair of binoculars round his neck, But it isn't the same as bein' in the crowd. No sign of the Snitch yet, eh?'

Nope,' said Ron. Harry hasn't had much to do yet.'

Kept outta trouble, though, that's somethin',' said Hagrid, raising his binoculars and peering skywards at the speck that was Harry.

Way up above them. Harry was gliding over the game, squinting about for some sign of the Snitch. This was part of his and Wood's game plan.

Keep out of the way until you catch sight of the Snitch,' Wood had said. We don't want you attacked before you have to be.'

When Angelina had scored, Harry had done a couple of loop- the-loops to let off his feelings. Now he was back to staring around for the Snitch. Once he caught sight of a flash of gold but it was just a reflection from one of the Weasleys' wristwatches, and once a Bludger decided to come pelting his way, more like a cannon ball than anything, but Harry dodged it and Fred Weasley came chasing after it.

All right there. Harry?' he had time to yell, as he beat the Bludger furiously towards Marcus Flint.

Slytherin in possession,' Lee Jordan was saying, Chaser Pucey ducks two Bludgers, two Weasleys and Chaser Bell and speeds towards the--wait a moment--was that the Snitch?'

A murmur ran through the crowd as Adrian Pucey dropped the Quaffle, too busy looking over his shoulder at the flash of gold that had passed his left ear.

Harry saw it. In a great rush of excitement he dived downwards after the streak of gold. Slytherin Seeker Terence Higgs had seen it too. Neck and neck they hurtled towards the Snitch--all the Chasers seemed to have forgotten what they were supposed to be doing as they hung in mid-air to watch.

Harry was faster than Higgs--he could see the little round ball, wings fluttering, darting up ahead--he put on an extra spurt of speed--

WHAM! A roar of rage echoed from the Gryffindors below-- Marcus Flint had blocked Harry on purpose and Harry's broom span off course. Harry holding on for dear life.

Foul!' screamed the Gryffindors.

Madam Hooch spoke angrily to Flint and then ordered a free shot at the goal posts for Gryffindor. But in all the confusion, of course, the Golden Snitch had disappeared from sight again.

Down in the stands. Dean Thomas was yelling, Send him off, ref! Red card!'

This isn't football, Dean,' Ron reminded him. You can't send people off in Quidditch--and what's a red card?'

But Hagrid was on Dean's side.

They oughta change the rules, Flint coulda knocked Harry outta the air.'

Lee Jordan was finding it difficult not to take sides.

So--after that obvious and disgusting bit of cheating--'

Jordan!' growled Professor McGonagall.

I mean, after that open and revolting foul--'

Jordan, I'm warning you-'

All right, all right. Flint nearly kills the Gryffindor Seeker, which could happen to anyone, I'm sure, so a penalty to Gryffindor, taken by Spinnet, who puts it away, no trouble, and we continue play, Gryffindor still in possession.'

It was as Harry dodged another Bludger which went spinning dangerously past his head that it happened. His broom gave a sud- den, frightening lurch. For a split second, he thought he was going to fall. He gripped the broom tightly with both his hands and knees. He'd never felt anything like that.

It happened again. It was as though the broom was trying to buck him off. But Nimbus Two Thousands did not suddenly decide to buck their riders off. Harry tried to turn back towards the Gryffindor goal posts; he had half a mind to ask Wood to call time out--and then he realised that his broom was completely out of his control. He couldn't turn it. He couldn't direct it at all. It was zig-zagging through the air and every now and then making violent swishing movements which almost unseated him.

Lee was still commentating.

Slytherin in possession--Flint with the Quaffle--passes Spinnet--passes Bell--hit hard in the face by a Bludger, hope it broke his nose--only joking. Professor--Slytherin score--oh no ...'

The Slytherins were cheering. No one seemed to have noticed that Harry's broom was behaving strangely. It was carrying him slowly higher, away from the game, jerking and twitching as it went.

Dunno what Harry thinks he's doing,' Hagrid mumbled. He stared through his binoculars. If I didn' know better, I'd say he'd lost control of his broom ... but he can't have ...'

Suddenly, people were pointing up at Harry all over the stands. His broom had started to roll over and over, with him only just managing to hold on. Then the whole crowd gasped. Harry's broom had given a wild jerk and Harry swung off it. He was now dangling from it, holding on with only one hand.

Did something happen to it when Flint blocked him?' Seamus whispered.

Can't have,' Hagrid said, his voice shaking. Can't nothing interfere with a broomstick except powerful Dark magic--no kid could do that to a Nimbus Two Thousand.'

At these words, Hermione seized Hagrid's binoculars, but instead of looking up at Harry, she started looking frantically at the crowd.

What are you doing?' moaned Ron, grey-faced.

I knew it,' Hermione gasped, Snape--look.'

Ron grabbed the binoculars. Snape was in the middle of the stands opposite them. He had his eyes fixed on Harry and was muttering non-stop under his breath.

He's doing something--jinxing the broom,' said Hermione.

What should we do?'

Leave it to me.'

Before Ron could say another word, Hermione had disap- peared. Ron turned the binoculars back on Harry His broom was vibrating so hard, it was almost impossible for him to hang on much longer. The whole crowd were on their feet, watching, terri- fied, as the Weasleys flew up to try and pull Harry safely on to one of their brooms, but it was no good--every time they got near him, the broom would jump higher still. They dropped lower and circled beneath him, obviously hoping to catch him if he fell. Marcus Flint seized the Quaffle and scored five times without any- one noticing.

Come on, Hermione,' Ron muttered desperately

Hermione had fought her way across to the stand where Snape stood and was now racing long the row behind him; she didn't even stop to say sorry as she knocked Professor Quirrell head first into the row in front. Reaching Snape, she crouched down, pulled out her wand and whispered a few, well-chosen words. Bright blue flames shot from her wand on to the hem of Snape's robes.

It took perhaps thirty seconds for Snape to realise that he was on fire. A sudden yelp told her she had done her job. Scooping the fire off him into a little jar in her pocket she scrambled back along the row--Snape would never know what had happened.

It was enough. Up in the air, Harry was suddenly able to clam- ber back on to his broom.

Neville, you can look!' Ron said. Neville had been sobbing into Hagrid's jacket for the last five minutes.

Harry was speeding towards the ground when the crowd saw him clap his hand to his mouth as though he was about to be sick - he hit the pitch on all fours--coughed--and something gold fell into his hand.

I've got the Snitch!' he shouted, waving it above his head, and the game ended in complete confusion.

He didn't catch it, he nearly swallowed it,' Flint was still howl- ing twenty minutes later, but it made no difference--Harry hadn't broken any rules and Lee Jordan was still happily shouting the result--Gryffindor had won by one hundred and seventy points to sixty Harry heard none of this, tho-ugh. He was being made a cup of strong tea back in Hagrid's hut, with Ron and Hermione.

Question 5 (20 marks)

This question involves writing a small OpenGL program. You may write the program in either Java or C. If it is in Java, it must be called Q5.java. If it is C, it must be called q5.c. You should include a Makefile that will compile it either way. Here's an (obfuscated) demonstration solution (in Java). You are to write a program that contains the following:
• A ground square, extending from (-5,0,-5) to (5, 0, 5). It's kd is (0.4, 0.4, 0.4).
• A spinning triangle, that spins at 1 degree per frame anticlockwise around the y axis. The program begins with the triangle having the vertices: (-1, 1, 0), (1,1,0) and (0, 2, 0). Its kd is green (0,1,0).
• A light source that rotates about the y axis by 1 degree per frame clockwise. Its initial position is (0,5,5). Its y value remains unchanged. The light source is full intensity (ie. (1,1,1). For convenience, the light source is also visually represented by a cube with sides length of 0.4 units. This cube is not lit. It is simply coloured as (0.6,0.6,0.6). This cube itself has no impact on the lighting of the scene.
The viewer is at (0, 10,10) , looking at (0,0,0) with the up vector being (0,1,0). It is in perspective projection with a y field of view of 60 degrees and an aspect ratio of 1. The window is pixels. The triangle casts a shadow onto the ground plane. The only source of light is the one already mentioned, assume there is no ambient light.
1.
What is the most appropriate means of rendering the shadow in this case? Consider these approaches: (i) projected shadows (ii) shadow map (iii) shadow volumes. In particular, consider simplicity, since you're going to have to write it yourself. (3 marks)
2.
Do we need a stencil buffer to render this scene if we use projected shadows? If not, why not? (2 marks)
3.
Write the program to create the scene described above. (15 marks).

Notes:

• It's not that hard. The interesting bit of the program supplied (i.e. the part that was not cut and pasted) was less than 70 lines long.
• The demonstration code available from the subject Web page may be useful. You are allowed to use other code from the Web, as long as you acknowledge.
• If you are going to use glMultMatrix (hint!), then remember that it takes values in column-major order as a single dimensional array. The array is arranged as:

• Do not use any OpenGL extensions. The code must comply with the OpenGL 1.1 spec.