Good Advices

Insert Post Here

2011-11-28T12:00:00.001-08:00

Insert shame-faced regret at not updating blog more here

Please release me

2010-11-12T12:44:00.000-08:00

Ship it, ship it, ship it! Spiff v0.1.0 (yes, I'm being cautious) out now, you can grab the jar from https://github.com/revbingo/SPIFF/downloads.

Spiff: The competition

2010-09-21T22:01:00.000-07:00

In the intervening years between the first inception of Spiff (yes, I'm going camel case, upper case everywhere just won't do) and it's subsequent revival (and re-revival), a couple of competitors have appeared in the same space.

Closest in spirit to Spiff is Preon. It even states it's aim "to be to binary encoded data what Hibernate is to relational databases, and JAXB to XML", which pretty much sums up what I want with Spiff. Where Preon differs is in it's extensive use of annotations to do what Spiff does in it's format definition file (which Spiff calls an .adf file - Arbitrary Data Format). Preon will examine your classes and derive the data format from the order and types of annotated fields in the class. It also uses annotations to derive looping and conditional logic.

I'll admit that I've not used Preon - partly through fear of polluting my ideas about what Spiff could and should do, and partly in case I decided it was better than Spiff and just decided to call the whole thing off. So any discussion of it's merits and drawbacks are truly superficial. My general impression is that it's reliance on annotations are a little hairy - when you're expressing logic in annotations, things look a little awkward. Spiff trades off compactness (having everything described in the code) for readability and also portability. The event dispatching and class binding mechanism means that one .adf file can be used to populate classes of any shape without needing to respecify the file format. This also highlights the fact that it looks like Preon expects the classes to fully describe the file format, which is rarely what you want in the code. One of the use cases that led to me starting to write Spiff was wanting to get little pieces of the data without having to worry about the rest of the file format. And thus were .jump and .skip begat.

On the other side, the Google lads are also in the frame with protobuf. Protobuf is interesting in that it uses something analogous to the .adf file to describe the format. Where it differs is that it will generate classes for you to serialize and deserialize the format. That's something that Spiff might be capable of one day, but I like the idea of being able to write arbitrary POJOs and map the data onto them, rather than having objects in my code whose sole purpose is as marshallers. Also, it's largely oriented towards message-passing, that is, describing a message that will be passed between two systems, such as in RPC, where the user is in control of both ends of the transaction. To that end, the .proto definitions are reliant on using the underlying protobuf grammar for the message, for instance to recognise repeated blocks of data, and don't have some of the flexibility to express more complicated relationships between parts of the file.

I see a couple of strong points in Spiff from this. Portability of .adf files is possibly the biggest. Once someone has defined an .adf for, say, a .bmp file, or an ItunesDB file, anyone else can take that and use it to bind all or part of that data to their own classes. The other is flexibility, in hopefully being able to express all the things that can make binary file formats tricky to work with. I guess first step is to have a working product...

Spiff!

2010-09-21T21:45:00.000-07:00

Ok, I'm back on Spiff. I mean it this time. Repeat after me - "I will ship software, I will ship software, I will ship software".

Coming back to code after a little time is an interesting experience. Almost every time you can guarantee a few nuggets of insight that hadn't occurred previously.

Today's lesson: if it's difficult writing a unit test for (usual suspects being the FileNotFoundExceptions and if(x == null)) conditions), it's probably not worth having in the code.

I'm not normally one for striving for 100% code coverage with tests. Like all things that fall under the agile/XP umbrella, if you're doing it by the book, you're doing it wrong. There isn't a book that tells you how you should be working on your projects.

However, in this instance, I thought it would be an interesting exercise to try and get up to 100%. By getting OCD on the unit tests, I found at least two conditions in my code that couldn't actually occur:

a null check on an object right after it's constructor was called, and
an exception thrown from code where I was using dynamic assignment where static assignment was sufficient.

In the latter case, I had

try {
   lib = Class.forName("java.lang.Math");
} catch (ClassNotFoundException e) {
   //how do I get here?
}

Can you write a test that exercises the catch block? Nope. This was a remnant of old code that hadn't been cleaned up. What I should have been doing was

lib = java.lang.Math.class;

which doesn't throw any exception.

It's good to remember that adding test cases is not the only way to get closer to 100% code coverage - deleting code does just as well.

How final is final?

2010-09-21T13:48:00.000-07:00

One interesting tidbit from Spiff development. How final is

final int x = 1

? Answer: Not very, if you're using reflection. Field.setAccessible(true) will soon get you round any awkward encapsulation issues.

So, newly armed with that knowledge, what's printed out here?

public class HowFinal {
    private final int x = 1;
    
    public static void main(String[] args) throws Exception {
        HowFinal howFinal = new HowFinal();
        Field f = howFinal.getClass().getDeclaredField("x");
        f.setAccessible(true);
        f.set(howFinal,2);
        System.out.println(howFinal.getX());
        System.out.println(f.get(howFinal));
    }

    public int getX() {
        return x;
    }
}

The answer, unexpectedly, is

1
2

Er, so x was final after all? Sort of. The compiler inlines constants at compile time, so as far as the runtime JVM is concerned, getX() contains the code return 1;. Querying the field via reflection shows it's true value of 2.

Is there any question whose answer doesn't start with "it depends"?

Spiff on Github

2010-09-21T12:57:00.001-07:00

Spiff is now available to download/fork/whatever at GitHub. The GitHub site also has a wiki with some instructions for getting started.

Current state is pre-pre-pre-pre-alpha. That is, it doesn't really work, I'm rebuilding some of the core parts, but it's there for anyone who wants to snoop. Ship early, ship often!

In (Re-)Development: SPIFF

2010-01-10T00:56:00.000-08:00

Shipping is a Feature. A feature that, to be fair, most (all) of my personal software projects have dropped from scope at some point along the way.

One such project was SPIFF. Originally the less pronounceable "SPADF" (Simple Parser for Aribtrary Data Formats), and developed about 4 years ago, the aim was to have a simple way to get data out of those nasty binary file formats that employ obscure things like, y'know, bytes. I mean, why store your integer in 4 bytes when you could wrap it in an xml file?

<?xml version="1.0" encoding="utf-8"?>
<root>
    <data type="integer">1</data>
</root>

At the time, I was trying to parse out id3 tags from MP3 files, and compare them to data in an ITunesDB file, both of which employ such ruthless, egregious efficiency. In trying to implement parsers for both these formats, the alarm bells told me that there had to be an easier way. What I wanted to do was define the data format and it's rules in a simple way, and then have some standard bit of code do the hard work. At that time, my desire was to have something like a SAX parser, to which I could listen for events and do work appropriately when the data I needed popped out.

At the heart of it was a JavaCC generated parser, which would read a file that defined a data format:

int                     headerSize
short                   version
byte                    flags
int                     stringLength
string(stringLength)    description

and spit out a sequence of Instruction objects that knew how to parse each of these things, and fire events as necessary. Of course, file formats aren't that simple. Even in the basic example above, there's a need to evaluate one element based on the value of another - the description field has a length defined in the int that comes before it. Likewise, in any non-trivial file format, there's a need for conditionals, loops and jumps, almost always based on a value from elsewhere in the file. SPIFF lets users define these these using a dot in front of keywords:

.if(version==1.0) {
   byte    flags
} .else {
   short   biggerFlags
}

Jel is employed under the covers to deal with evaluation of expressions. Any values that have been defined previously in the file can be used in an expression, and the ampersand can be used to reference the position of that value in the file. For instance, in a 24-bit bitmap, each "row" of pixels (defined by 3 bytes) is padded to a boundary on a multiple of 4. So it's necessary to do things like:

.repeat(pixelHeight) {
    .mark(startOfRow)
    .repeat(pixelWidth) {
        ubyte    rgbBlue
        ubyte    rgbGreen
        ubyte    rgbRed
    }
    .skip (&rgbRed - &startOfRow - 1) % 4
}

You could also insert arbitrary groupings into the format, which would fire an event in the parser that you could use to change state, pretty much like nested elements in an XML file.

One feature that didn't make it into SPIFF was that old "shipping". The code sat in my svn repo doing precisely nothing (I never did get back to that project with the ITunesDB either). Spurred on by the realisation that I never actually finish anything, I recently picked up SPIFF again, with the aim of turning it into something more like JAXB, where the parser can populate (or even generate) an annotated object graph.

Hence, consider this the first in a series of posts covering aspects of the ongoing development of SPIFF, and my attempt to at least get it in the public domain.

Irkonomics

2009-11-05T12:32:00.000-08:00

Tonight, I have done a bad thing. A very bad thing. Not bad evil bad. Or bad naughty bad. But bad depressing bad. I fired up my old laptop, my trusty Acer 5003WLMi. The little fella wasn't packing too much punch any more, especially trying to do Eclipse plugin development, and the battery had gone south, so a couple of months ago he was shunted under the sofa in favour of a new shiny Acer 6930G. Dual core Intel P7450, 4GB RAM, 320GB disk, Nvidia card - the new recruit is a perky number. Finally I can turn on Compiz effects. The wireless is rock solid. I've got more disk that I know what to do with. I certainly got bang for my buck.

But it has a dark side to it. It appears that in a bid to save money, Acer have manufactured the 6930G without any human ever laying a hand on it's sorry little shell. For if they had, they would have found it immediately that the Acer 6930G is probably the most uncomfortable laptop I've ever had the misfortune to use. For the last two months, I've convinced myself that it's not that bad. But getting the old 5003WLMi out again has me weeping into my trackpad with it's smooth curves.

Of course, you don't need melodramatics and hyperbole, so here's the facts:

The trackpad. Oh the trackpad. The trackpad is so bad it demands... A SUBLIST....

It's left of centre. Fail.

It doesn't have a defined edge. It's just kind of sunken. Want edge scrolling? Forget it. Oh, except for there's a little ridge down one part that sort of tells you where the edge scrolling should be. Want tap zones? Really? Not here you don't. Of course, you can have them, just don't expect to find them without tapping 10 times.

The sensitivity is terrible

It's bumpy. Yeah, I know, you can't even understand what I'm trying to tell you, right? The plastic on the top panel has little ~~raised bumps~~dimples, and that texture is also on the trackpad. I'm a guitar player, so the tips of my fingers aren't exactly Fairy Soft, and yet still I get sore fingers.

The front edge of the laptop is sharp. You know, that bit where you rest the edge of your hand when you're using the trackpad. "Hey, you know what this laptop needs? Sharp bits where you put your hands! Yeah!"

The screen only tilts back to 45 degrees. "Hey you know what users of this laptop need? A sore neck when they're using it standing up! Yeah!"

My kids could use the keyboard as a trampoline, it's that bouncy

"Hey, you know what programmers will love? The PgUp/PgDown/Home/End keys out the way at the bottom of the number pad! While you're doing that, why not stick the PgUp key right next to the right arrow key. You know, so that you always hit the frickin' thing when you're trying to just move along the line! Yeah!"

So, in summary, you want a great performing laptop for not much money? Buy an Acer 6930G. Just don't ever use another laptop, lest you should remember what you're missing.

Adventures in 3D: Part X - On the move

2009-04-27T05:08:00.000-07:00

Yay, so we've finally got to the point where we can move a camera around in our scene, thanks to matrices. In the last post, we used a TransformMatrix to convert the world z-coordinate to something relative to the camera position, albeit with a hard coded view point. Now we just need to start hooking that into something that allows us to change that viewpoint. The ThreeDeePanel class already contains a worldToCamera variable that stores the transform matrix representing the camera view. Let's do things properly now - it's not hard to imagine that a camera is going to have a few different properties, so let's create a Camera class. Let's also represent the position as a Point instead of the raw transform matrix.

public class Camera {

 private Point position;
 
 public Camera(Point p) {
  position = p;
 }
 
 public Point getPosition() {
  return position; 
 }
}

Then we keep an instance of the Camera in the ThreeDeePanel class, and provide a method for other classes to get at it. We also need to calculate the corresponding Matrix from the camera's viewpoint before calling project():

Camera camera = new Camera(new Point(0,0,-300));

public void getCamera(Point p) {
        return camera;
}

protected void paintComponent(Graphics g) {
        ...
        TransformMatrix worldToCameraTransform = TransformMatrix.getWorldToCamera(camera.getPosition());
        for(Primitive poly : renderScene){
  poly.project(worldToCameraTransform);
  poly.draw(g2);
 }
        ...
}

In the ThreeDee class, which is doing all the input, I'm going to listen out for the cursor keys (assuming we're in the MOVE_CAMERA state), grab the camera and change it's position:

private int CAMERA_SPEED = 3;

public ThreeDee() {
    ...
    panel.addKeyListener(new KeyAdapter() {
        public void keyPressed(KeyEvent e) {
           ....
  } else if (moveState == MoveState.MOVE_CAMERA) {
 boolean ctrlDown = ((e.getModifiersEx() & MouseEvent.CTRL_DOWN_MASK) == MouseEvent.CTRL_DOWN_MASK);
 Camera camera = panel.getCamera();
 switch(e.getKeyCode()) {
 case(KeyEvent.VK_UP):
  if(ctrlDown) {
   camera.getPosition().y += CAMERA_SPEED;
  } else {
   camera.getPosition().z += CAMERA_SPEED;
  }
  break;
 case(KeyEvent.VK_DOWN):
  if(ctrlDown) {
   camera.getPosition().y -= CAMERA_SPEED;
  } else {
   camera.getPosition().z -= CAMERA_SPEED;
  }
  break;
 case(KeyEvent.VK_RIGHT):
  camera.getPosition().x += CAMERA_SPEED;
  break;
 case(KeyEvent.VK_LEFT):
  camera.getPosition().x -= CAMERA_SPEED;
  break;
 }
}

Give that a go, and you should have a moving camera! However, move around a bit and you'll probably notice a problem. The canBeCulled() method in the Triangle class is still using a hard coded viewpoint to decide whether a face is away from the viewer, so if you move up alongside the object, you'll see that it's rear end is missing. We just need to adjust that method to take the new viewpoint into account (again, don't forget to change the method signature in the Primitive interface):

public boolean canBeCulled(Point camera) {
 if (WIREFRAME) return false;

 Vector viewer = camera.vectorTo(getPosition());
 double cull = normal.dotProduct(viewer);
 return (cull > 0);
}

As funky as this is, there is the small problem of only being able to look straight ahead. With the point where the camera is, we also need to store some information about which way it's pointing. The camera ought to be free to rotate around any of the axes - look left and right, up and down, and roll side to side. These are commonly know as yaw, pitch and roll. The good news is that these are simply rotations, which we already know how to deal with. What's slightly different is that we're no longer rotating around the world origin, but instead treating the camera as the origin. Also, going right back to the discussion in Part I, the rotation of the objects in the world is opposite to the camera rotation - turning the camera 90 degrees right is like rotating the world 90 degrees left.

We'll store the rotation of the camera as three angles, alpha, beta and gamma, which represent the rotation around the X, Y and Z axes respectively. It's worth considering exactly what that means, to save confusion later. Rotation around the X axis is the looking up and down (pitch) - it's easy to see the "X" and immediately think it ought to be side-to-side motion. Likewise, rotation around Y is looking side-to-side (yaw), and around Z is roll. I'll add a rotate() method to the Camera to change those angles:

public void rotate(double da, double db, double dg) {
 alpha += da;
 beta += db;
 gamma += dg;
}

Now we just need to be able to get the appropriate RotationMatrix that represents those angles. Given rotation matrices Rx, Ry and Rz for each of the three axes, the total rotation is simply Rz.(Ry.Rx). Note that we multiply Rx and Ry first, then multiply by Rz. Why? Because applying rotations in different orders gives different results. Imagine you're looking at a point straight ahead. First, look up 45 degrees. Then look right 45 degrees. Then roll over 90 degrees. You're now looking at a point "top right" of where you were originally, and with your head tilted to one side. Start again, but this time do the "roll" first. You'll actually end up (if you've done it properly...) looking at a point "top left" of where you were. The secret is in the fact that "up" and "right" are relative to which way you're already facing. If you're on your feet and tilt your head backwards to look up, it really is "up". If you were lying on your side on the ground and tilted your head back, you'd actually still be looking along the ground. You would actually have to look "right" to look "up".

So, I'll add a new method to RotationMatrix to get an instance that represents alpha,beta,gamma, which we'll do by getting instances for each axis and multiplying them together.

public static RotationMatrix getInstance(double alpha, double beta, double gamma) {
 return RotationMatrix.getInstance(gamma, RotationAxis.Z).times
  (RotationMatrix.getInstance(beta, RotationAxis.Y).times
  (RotationMatrix.getInstance(alpha, RotationAxis.X)));
}

Finally, we implement a getCameraRotation() method on Camera to get that matrix, and multiply it by the position transform matrix we created above to give the final transform from world to camera. Note that the method signature for project changes to take a base Matrix type. Also, we need to change our RotationMatrix class (and any code that calls it) to use homogenous coordinates, so that we can multiply a RotationMatrix and TransformMatrix. We know that this is pretty simple, just add a row and column to each matrix, with a 1 in the bottom right corner (in hindsight, there's no need for RotationMatrix and TransformMatrix to be different types, really we should just use the base Matrix class. Ah well, you live and learn)

public RotationMatrix getCameraTransform() {
        Matrix translation = TransformMatrix.getWorldToCamera(position);
 return RotationMatrix.getInstance(alpha, beta, gamma).times(translation);
}

and in ThreeDeePanel:

Matrix worldToCameraTransform = camera.getCameraTransform();

This is all very well, but it doesn't actually do much yet. All we have to do though, is wire it up to the input listeners. Whilst in the MOVE_CAMERA state, dragging the mouse will look left,right,up,down, and moving the scroll wheel will roll.

public void mouseDragged(MouseEvent e) {
        ...
        case MOVE_CAMERA:
  panel.getCamera().rotate(dy * RADIAN,dx * RADIAN,0.0);
 }
}

and the same sort of thing in mouseWheelMoved() for the roll. Note that dx (moving the mouse left and right) affects the Y axis rotation, and vice versa, for the reasons we discussed above.

Run that, and you too can look around the back of your object! Take care to check whether the rotation is what you expect, as it's not always obvious. Matrix multiplication is not commutative - AB is not the same as BA - and if you've got something in the wrong order, it'll generally manifest itself here as the axis of rotation being wrong. For instance, you may find that instead of the object rotating around the camera, the camera rotates around the object.

You may also notice that the scene "stretches" when it's rotated towards the edge of the screen. This is related to the focal length. If the effect looks unnatural, try increasing the focal length - a shorter focal length effectively gives you more of a "fish-eye" look.

Now you've managed to get around the back, you've probably also noticed a few problems with the z-order. Remember that we're sorting, and therefore drawing, the screen by (world) z position, which is fine as long as we're looking in the +ve z direction. As soon as we move elsewhere, that becomes useless - we now need to sort by z order relative to the camera. That means we need to be converting from world space to camera space before doing the sorting.

Let's also take the opportunity to tidy up the Triangle class. We're currently marshalling vertex data between arrays and matrices, whereas we could just keep the vertex data as a matrix and be done with it. For convenience, I'll add methods to the Vector and Point classes to convert to/from matrices.

As well as storing the world coordinates, we'll also keep a matrix of the view coordinates in Triangle. These will be populated in the project() method, which now needs to move in the pipeline to a point before we do the z-order sorting.

public class Triangle extends Primitive {
        // vertices of the triangle in world space
 Matrix[] vertices = new Matrix[3];
 Matrix[] viewVertices = new Matrix[3];
      
        public void project(Matrix worldToCamera) {
  
  for (int i = 0; i < 3; i++) {
   viewVertices[i] = persMatrix.times(worldToCamera.times(vertices[i]));

   if(viewVertices[i].data[2][0] < 0) {
    draw = false;
    return;
   }
   
   xPoints[i] = (int) (viewVertices[i].data[0][0] / viewVertices[i].data[3][0]);
   yPoints[i] = (int) (viewVertices[i].data[1][0] / viewVertices[i].data[3][0]);
  }
 }
}

The doPipeline() method now consists of backfaceCulling(), project(), sortForZOrder(), lightScene(). All we need to do now is change getZOrder() in Triangle to return the z order from the (view coords) viewVertices array instead of the (world coords) vertices array.

public double getZOrder() {
 return getAverage(viewVertices, 2);
}

@Override
public Point getPosition() {
 return new Point(getAverage(vertices, 0), getAverage(vertices, 1), getAverage(vertices, 2));
}
 
private double getAverage(Matrix[] matrices, int index){
 return (matrices[0].data[index][0] + matrices[1].data[index][0] + matrices[2].data[index][0])/3; 
}

There, all sorted. We're gradually getting there. Unfortunately, it seems that for every bit we add, it throws up another couple of problems to solve. But we love solving problems, right? Right?! Put the kettle on, make a cup of tea, download the source, and let's ponder.

Adventures in 3D: Part IX - A Bit Of Perspective

2009-04-21T05:18:00.000-07:00

Stick with it 3D fans, we're getting there.

One thing we cheated at way back in Part I was perspective. Until now, everything has been drawn using parallel projection. That is, there is no perspective, everything appears the same size regardless of how far away it is. That works fine when you're looking at a single object, where the difference in distance between the front and the back of the object is small enough to be negligible in terms of how your brain perceives the image, but when you start adding objects into the scene in the background, it's a problem.

Thankfully, perspective is very simple to do. We're actually going to do this twice. For a first pass, we'll do the simplest possible thing, which is to just do the calculations explicitly, and with a hardcoded viewpoint. Hopefully your alarm bells will be ringing at the sight of the work "hardcode", so then we'll look at the more proper solution, which involves our old friend, the matrix.

So, first solution. We already have a project() method in the Triangle class, which is used to convert the 3D model's x,y,z (double) coordinates into the screen's x,y (integer) coordinates. Remember that perspective does not affect the 3D model in any way, everything stays where it is. Perspective is simply an effect of projection, so this is exactly where we need to be doing the perspective calculations. And what does "perspective" actually mean for our projection? Think about a wireframe cube rendered in 3D with perspective. The back face of the box, which is at a greater Z distance, will appear smaller than the front face - the left and right sides of the back face have smaller x values (assume the x and y axes are through the centre of the box), and the top and bottom sides of the back face have smaller y values. So it's clearly an adjustment of X and Y coordinates as a function of Z, we just need to figure out what that adjustment is. Time for a diagram.

The vertical line in the middle represents the screen onto which the model is projected - the camera C is at some distance z' behind that screen, and the point P is at a distance z beyond that screen, and distance y above the axis. Drawing a line from C to P represents our line of sight, and you can see that it intersects the screen at a distance y' above the axis. Our job is to figure out the distance y'. Cast your mind back to school maths classes, and the idea of similar triangles. The theory of similar triangles says that two triangles with the same angles will have sides that are in proportion. Therefore, y'/z' = y/(z+z'), which rearranged slightly gives the equation

           z'
y' = y * -----
         z + z'

From that, you can see that as z tends towards zero (i.e. the object moves nearer the plane of projection), the second term becomes z'/z', which is 1, and so y'=y. Working out z is fairly easy, we just need to remember that it's the distance from the screen to the object, which, if we decide the screen is somewhere other than z=0, is not the same as the z coordinate in the world space. In other words, z = zworld - zscreen . We also need z' - this is actually a fairly abitrary number, representing the focal length. The lower this number, the more pronounced the perspective effect.

So, let's stick that into some code. We define a viewpoint that represents the position of the viewer, and a focal length (z' from the diagram), in this case determined pretty much by trial and error - this value gives a decent sense of depth without looking unrealistic. As the focal length is fixed, and the viewpoint will potentially move, we calculate the position of our "screen" as being the position of the camera plus the focal length. Then, the relative z distance is calculated (z in the diagram), being the distance from the screen to the object. Finally, we use those values to calculate the perspective correction as defined above.


private Point viewpoint = new Point(0,0,-300);
double focalLength = 300;

public void project() {
        double zScreen = viewpoint.z + focalLength;
 for (int i = 0; i < 3; i++) {
  double zDistance = z[i] - zScreen;
  double perspective = focalLength / (focalLength + zDistance);
  xPoints[i] = (int) (x[i] * perspective);
  yPoints[i] = (int) (y[i] * perspective);
 }
}

If you spin the scene objects now, you should get some sense of perspective. If you can't really see anything, you may want to lower the focal length value so the effect is more pronounced.

That's all well and good, but there's another way to achieve the same effect, and it's going to set us up a bit better for getting the camera moving around. We're going to use a matrix to perform the same sort of maths.

Last time we used a matrix it was for rotation, and was a 3x3 matrix which acted on 1x3 matrix (the point). Now we're going to use a transformation matrix to translate points, both in 3D and 2D. Recall that if we're working with a 3x3 matrix on a point x,y,z, then matrix multiplication means the output for each coordinate is of the form Ax + By + Cz. However, in the case of translation, we often need to just add or subtract a constant that is not a function of position. This may sound familiar, for this is the definition of an affine transformation, which we've already been happily using to move the origin into the centre of the screen. To do affine transforms, we need to introduce homogenous coordinates. There is, I'm sure, lots of complicated geometry mathematics that can be used to describe homogenous coordinates - see that Wikipedia page for starters - but really you can just think of it as a hack to allow transformations of the form Ax + By + Cz + D. You do two things: add a column to the translation matrix containing the constants to add to each coordinate, and add a 4th row, with the value, 1 to the vector matrix. Easy. Here's an example:

|1 0 0 30 ||x|    |x + 30|
|0 1 0 10 ||y|    |y + 10|
|0 0 1 -10||z| => |z - 10|
|0 0 0  1 ||1|    |  1   |

Hopefully you can see how this can start getting us towards the idea of a moveable camera. The translation coordinates in the 4th column will come from the position of the camera, and the result will be to move the world coordinates to coordinates relative to the camera. We did the same thing in our first method in calculating (focalLength + zDistance), albeit only for the z axis. You can see that with the matrix method, we can very easily take the x and y coordinates into account as well.

Let's add some code. I create a new TransformationMatrix class, and simply have a static method worldToCamera(Point view) that, given a camera position, will return a matrix of the form:

|1 0 0 -view.x|
|0 1 0 -view.y|
|0 0 1 -view.z|
|0 0 0    1   |

That code is

public class TransformMatrix extends Matrix {

    private TransformMatrix(double[][] data) {
 super(data);
    }
 
    public static TransformMatrix getWorldToCamera(Point view) {
 return new TransformMatrix(new double[][] { {1,0,0,-view.x}, {0,1,0,-view.y}, {0,0,1,-view.z}, {0,0,0,1}});
    }
}

Note that the view coordinates are negated. If the camera is at z=10, and a world point is at z=20, the point will be 10 units from the camera i.e. z = zworld - zcamera. We'll pass in a matrix to the project() method to use for the transform from world to camera (don't forget to make that change in the Primitive interface too). For now you can just pick a camera position and hard code it in the call to project(). When we get round to moving the camera, that matrix will be recalculated each time.

So how does this help us with perspective? It doesn't yet. We also need to factor in that focalLength. In our world-to-camera transform, we're going to end up with a z-coordinate, z', that is the distance from the camera to the point. In the first effort above, we had zDistance, which was the distance from the screen to the point, and focalLength which was the distance from camera to screen. That means that:

z' = focalLength + zDistance

How very handy. The perspective calculation is now:

double perspective = focalLength / z';

We can express that in a matrix multiplication as well. The trick here is to use the homogenous coordinate (normally called w) to store that perspective calculation (w') and then it's a simple case of applying that to x' and y'. Just one other thing we have to think about - as we're multiplying matrices, we need to express the perspective as a multiplication of z' rather than dividing by it, so we simply turn it upside down, and instead of multiplying x' by w', we divide.

That means the perspective calculation can be applied as a matrix, although in our simple case it's nothing more than a way of dividing z' by the focal length. The benefit of using the matrix is that you could potentially encode other operations in there in future to apply different effects. Here's what the matrix looks like, and the result of applying that to homogenous coordinates:

| 1  0  0  0|| x' |    |  x'  |
| 0  1  0  0|| y' |    |  y'  |
| 0  0  1  0|| z' | => |  z'  |
| 0  0 1/f 0|| w' |    | z'/f | => wp

Let's recap:

Given a point x,y,z, we add the homogenous coordinate (which is just a 1) to give a vector matrix x,y,z,w.

The world-to-camera transform matrix is applied to give the coordinates x',y',z',w', which are the coordinates of the point relative to the camera position, and where w' is still just a 1.

The perspective matrix is applied to calculate wp, which is the perspective correction factor

Divide x' and y' by wp to give the final x and y coordinates

Sounds slight complicated, but it's really not doing anything more than we've already done. Again, the benefit is in being able to encode other transformations in the matrices, which should come in useful shortly.

In code, it's straightforward. We'll add a new method getPerspective(double focalLength) to the TransformMatrix class to return a matrix that divides z' by the focalLength:

public static TransformMatrix getPerspective(double focalLength) {
 return new TransformMatrix(new double[][] { {1,0,0,0}, {0,1,0,0}, {0,0,1,0}, {0,0,1/focalLength, 0} });
}

Then in the Triangle class:

public void project(TransformMatrix worldToCamera) {
  
 for (int i = 0; i < 3; i++) {
  Matrix point = new Matrix(new double[][] { {x[i]}, {y[i]}, {z[i]}, {1}});
  Matrix result = worldToCamera.times(point);
   
  Matrix finalPoints = TransformMatrix.getPerspective(FOCALLENGTH).times(result);
   
  xPoints[i] = (int) (finalPoints.get(0,0) / finalPoints.get(3,0));
  yPoints[i] = (int) (finalPoints.get(1,0) / finalPoints.get(3,0));
 }
}

Of course, result is just an intermediate, and the perspective matrix never changes given a fixed focal length, so if you're the sort of coder who hates to see waste, you can store the perspective matrix in the Triangle class, and do the whole lot in one go:

private final TransformMatrix persMatrix = TransformMatrix.getPerspective(focalLength);

public void project(TransformMatrix worldToCamera) {
        ...
       Matrix finalPoints = persMatrix.times(worldToCamera.times(point));
        ...
}

Download the source and see for yourself.

One final thing for this episode - I promise. If you move your camera to a position that means objects going behind the camera, you'll see things go a bit pear-shaped because we're trying to render objects that should not be in the view. So there needs to be some sort of check to ensure polygons that are behind the camera are not drawn. That's easy enough, any object which has a negative z' (remember, z' is relative to the camera) should not be drawn. This is slightly tricky, because we need to tell the draw() method that. I'm going to hack it for now, and use an instance variable boolean draw = true;. So then in project(), we do the check:

if(finalPoints.get(2,0) < 0) {
 draw = false;
 return;
}

and in draw():


public void draw(Graphics2D graphics) {
    if(draw == false) {
     draw = true;
     return;
    }
    ...
}

Note that we reset the draw variable once we've decided not to draw the polygon, so that it can be considered for drawing again in the next frame.

That's a fair slice of stuff for what was really a quite simple bit of functionality. Next time we'll start getting that camera moving, and also think a bit more seriously about that last point.

Adventures in 3D: Part VIII - A Light Touch

2009-04-19T11:53:00.000-07:00

(Yet again, I'm deviating from the original aim of getting a camera persepective working. But this is pretty cool, so hopefully you'll forgive)

First, a confessional. There was a pretty fundamental error in the Point class, in that vectorTo() was implemented such that vectors were actually backwards. D'oh. Which explained why, when I actually took the time to think about where lights were coming from and how the scene was lit, things were the wrong way round. That's fixed now, along with a couple of other things that were also wrong in compensation for that error. At least it's a good lesson in taking the time to properly consider such fundamentals, rather than ploughing on with whatever works... On the positive side, all the concepts introduced thus far still stand.

Anyway, so far, the lighting on this object has been pretty dumb. The light we've modelled is just a Vector, so any object anywhere in the scene is lit from the same direction and at the same intensity, and it's also pretty boring white light. We're going to spice things up a bit. In a 3D scene, there can be various types of lighting with different characteristics of where and how the light is cast. In our case, we're going to implement two types of light - ambient light and spotlights.

Ambient lights are super super easy. They're just a background level of light that's present everywhere. It doesn't come from a point, doesn't point in any particular direction, doesn't change in intensity. Think of it like daylight on a cloudy day - the light is just kind of there, without coming from any particular place.

To make life easier, we have an abstract Light superclass. This says that a light usually has a colour, a position and a direction, although, in the case of an ambient light, we just ignore those last two. What the Light class doesn't define is how the light affects the surfaces it falls on. For that, we have an abstract light(Lightable s) method, which returns a Color, being the colour (remember that brightness is one component of a colour) that this light contributes to that surface. The Lightable interface defines two methods, getNormal() and getPosition() - any object (in our case, a Primitive) that wants to be lit must implement these two methods so that the lights can tell where the surface is and which way it's facing. You can easily see that this interface could need to define other methods in the future for more sophisticated lighting - for instance, the light() method may need to know the absorptive or reflective properties of a surface.

The AmbientLight class only holds one thing - the colour of the light. The implementation of the light() method is dead simple, because the light that the AmbientLight contributes to each surface is simply it's colour. No need to worry about which way the surface is facing or how far away it is.

public class AmbientLight extends Light {

 public AmbientLight(Color color) {
  this.color = color;
 }

 @Override
 public Color light(Lightable s) {
  return this.color;
 }
}

Our Triangle class has a lightPolygon() method, which is where we ask all the lights in the scene to tell us what they will contribute to the final colour of this polygon. It's just a loop calling light(this) for each light. The colour from each light is added together to get a final colour to render.

public void lightPolygon(LightScene lights) {
 litColor = Color.black;
 for(Light light : lights) {
   litColor = addColor(litColor, light.light(this));
 }
}

The addColor() method is also very simple - just add each RGB component separately, naturally making sure that the component values don't go above 255.

private Color addColor(Color c1, Color c2) {
 return new Color(Math.min(255, c1.getRed() + c2.getRed()),
   Math.min(255, c1.getGreen() + c2.getGreen()),
   Math.min(255, c1.getBlue() + c2.getBlue()));
}

Put all that together, and define an AmbientLight with a muted colour. You don't want the ambient light to be too bright, or else it will just wash out all the other colours in the scene. I'm going to use RGB(0,0,30). The effect this has is to show up all the objects in the scene in a dark blue base light. If nothing else, it's handy for making sure that your objects are being rendered, where previously they would not have been painted if you got the lighting coordinates wrong.

Now let's try something far more interesting, the spotlight. Spotlights have a number of properties - the position of the light, the direction the light points, what colour it is, and the angle that the light spreads out at. For a more realistic representation, we also want to define how quickly the light falls off from full intensity around the edge. The first three are already taken care of in our Light superclass. The second two will be implemented in the Spotlight class, and I'll call them fullIntensityAngle and falloffAngle. For a light defined with a fullIntensityAngle of 20 and falloffAngle of 15, that means that surfaces within 20 degrees of the centre line of the light will be lit at full intensity, and surfaces another 15 degrees beyond that will be lit at an intensity proportional to their distance from the centre line. At 35 degrees from the centre and beyond, there's no light contributed from the spotlight.

There are two main calculations to do. The first is the standard calculation we're used to, work out which way the surface faces, and if it's facing away from the light, just return Color.BLACK (as far as adding lights is concerned, Color.BLACK is a null result).

double dtFace = s.getNormal().normalise().dotProduct(lightNormal);
if(dtFace >= 0) return Color.BLACK;

where lightNormal is the normalised vector pointing in the direction of the light.

Next, get a vector from the light to the surface, normalise it and calculate the dot product with lightNormal. For vectors of unit length, the dot product of the two gives the cosine of the angle between the two. At this point, we could use Math.acos() to convert back to an angle and figure out if it's within the spread of our light. But acos is a pretty expensive operation, so instead of comparing angles, we just compare raw cosine values (the cosine of the spread angle is calculated in the constructor or when the angles are changed) to see if the surface is outside the range. If it is, again, return Color.BLACK.

Point lightSource = this.getPosition();
Vector lightToPoly = lightSource.vectorTo(s.getPosition());
double dtPosition = lightToPoly.normalise().dotProduct(lightNormal);
if(dtPosition < cosFullSpread) return Color.BLACK;

Ok, now we're down to just the points that are actually lit. At this point, we will do that acos() operation to get the angle. This makes things simple as it's a straight comparison of angles to determine how to light the surface, and is also important because it means that when we calculate the falloff, it's linear with angle, rather than the cosine.

Within the spread of the fullIntensityAngle, the surfaces are light at the brightness determined by the direction they face, as usual. In the "fall off zone", the intensity of the light dims the further away you get from the centre, so we calculate a falloffFactor, which is a number from 0.0 to 1.0, by which we'll multiply the brightness in the final colour. Note that in the final colour, we create a HSB colour, which has the same hue and saturation as the specified light colour, and just scale the brightness.

double angle = Math.acos(dtPosition) * (180/Math.PI);

double fullSpreadAngle = fullIntensityAngle + falloffAngle;
double falloffFactor = 1;
if (angle >= fullIntensityAngle && angle <= fullSpreadAngle) {
   falloffFactor -= ((angle - fullIntensityAngle)/(falloffAngle)); 
}  
litColor = Color.getHSBColor(colorHue, 
                      colorSaturation, 
                   (float) (Math.abs(dtFace) * falloffFactor * colorBrightness)); 
return litColor;

Throw all this together, sprinkle a few different colour lights around, use a bit of artistic licence to add some other code (see below), and what do you get?

There is no denying that's pretty damn sexy. We can also do one more thing to bring colour to the scene, and that's to give the polygons themselves some colour. We'll assign a base colour to each polygon, and adjust the final lit colour to account for the surface colour. That adjustment is not immediately obvious, but if you consider a few cases it becomes apparent, especially if you think about the colour components as floats 0.0-1.0 instead of the traditional integer 0-255. For instance, a pure white surface (1.0,1.0,1.0) lit by a pure red light (1.0,0.0,0.0) will appear pure red (1.0,0.0,0.0). A pure red surface lit by a pure blue light (0.0,0.0,1.0) will appear black (0.0,0.0,0.0) - a red surface absorbs all blue wavelengths. A black surface always appears black, even if lit with white light. If we write those out, it should become clear:

(1,1,1) lit by (1,0,0) = (1,0,0)
(1,0,0) lit by (0,0,1) = (0,0,0)
(0,0,0) lit by (x,y,z) = (0,0,0)

It is, of course, multiplication of the colour components. A quick multiplyColour method:

private Color multiplyColor(Color c1, Color c2) {
        float[] c1Comp = c1.getColorComponents(null);
 float[] c2Comp = c2.getColorComponents(null);
 return new Color(c1Comp[0] * c2Comp[0], 
   c1Comp[1] * c2Comp[1],
   c1Comp[2] * c2Comp[2]);
}

and then apply that to the lit colour:

litColor = multiplyColor(litColor, surfaceColor);

and then you have coloured polygons:

As Shed Seven once sang, it's getting better all the time.

Cut out the middle man and just download the source. Not least because there's plenty of other tinkering I've done with the code. Of most interest:

There's a new BasicSceneObject, XYPlane, which provides the "back wall" effect. Notice that the rotate() method is overriden, with no implementation, which means it stays static whilst the other objects in the scene rotate in front of it.
The pipeline was previously using ArrayLists to store the list of polygons. The problem with this is that the backface culling does a remove() on the list, which is not very efficient for ArrayLists, because they then have to shuffle other objects in the list down the backing array. By changing to a LinkedList, for which removals are O(1) (simply change pointers), performance is improved.
For some sexy debugging, the InfoPanel class allows us to draw some basic info in the top left of the panel
Now we've got spotlights in the scene, it's useful to be able to move them around. There are some extra controls that you can use to control the scene:
Space cycles through modes of 1) rotating objects, 2) moving the focus point of the current light, 3) moving the position of the current light, 4) moving the camera (wait, not yet!).
In MOVE_OBJECT mode, clicking and dragging rotates X and Y axes. Using the scroll wheel (or edge drag on a touchpad) rotates the axis
In MOVE_LIGHT_POSITION mode, clicking and dragging moves the light source position in XY. Holding CTRL whilst doing so moves the light backwards and forwards.
In MOVE_LIGHT_DIRECTION mode, clicking and dragging moves the focus point of the light in XY. Holding CTRL whilst doing so moves the focus point backwards and forwards. Using the scroll wheel changes the size of the falloffAngle of the light, and holding CTRL while scrolling changes the fullIntensityAngle.
In both MOVE_LIGHT_POSITION and MOVE_LIGHT_DIRECTION, pressing N will cycle control through available spotlights (Warning: this is a bit of hackery - if you don't have a spotlight in the scene, this will go into an infinite loop...)
In all modes, clicking the mouse will toggle between wireframe and full mode.

That's a decent slab of work. A simple one for next time - adding some perspective.

Adventures in 3D: Part VII - Matrix Revolutions

2009-04-08T12:00:00.000-07:00

(What dastardly cunning, a piece about matrices on the 10th anniversary of The Matrix)

I already warned you that there was matrix maths coming up, so hold on to your hats. Once you've got to know them, you'll see that the principle of matrices is actually pretty simple, in that they just encode relatively complex equations in a simple form. Teaching matrix maths is outside the scope of this series, so I'll trust you'll do your own reading and just dive on in. I've also borrowed a Matrix class, as building our own is sure to be more of an education in bugfixing than 3D graphics.

Our ultimate aim at the moment is to change our viewpoint - the code at the moment has us fixed in one position and able to spin the world. We want to fix the world and be able to move around it, you know, like this. But first we'll slide in gently with using matrices, as they're a handy way to handle rotation.

Naturally you can, at the drop of a hat, quote the formula for rotation of points around an axis in 3D. Around the X axis, that is

y[i] = (y[i] * Math.cos(r)) - (z[i] * Math.sin(r));
z[i] = (z[i] * Math.cos(r)) + (y[i] * Math.sin(r));

Assuming we represent our 3D points as a column matrix [x,y,z]T, these two equations can be neatly made into a matrix:

| 1    0      0   |
| 0 cos(r) -sin(r)| 
| 0 sin(r)  cos(r)|

and we can also do the same for rotation around Y and Z axes:

|cos(r)  0  sin(r)|
|   0    1    0   | 
|-sin(r) 0  cos(r)|

|cos(r) -sin(r) 0 |
|sin(r) cos(r)  0 | 
|   0    0      1 |

So with our new Matrix class we can, for any given angle r, construct a matrix that encodes the rotation around the appropriate axis. When rotate() is called on the BasicSceneObject, we can build that matrix, and I'll add an overloaded form of rotate() on the abstract SceneObject so we can pass in that matrix to do the rotation. We push our points into a 1x3 matrix, multiply that by the 3x3 rotation matrix, then get the values from the result matrix and put those back into our points.

public void rotate(RotationMatrix rotationMatrix) {
 Matrix[] points = new Matrix[3];
 
 for(int i=0;i<3;i++) {
  points[i] = new Matrix(new double[][] {{x[i]}, {y[i]}, {z[i]}});
  Matrix result = rotationMatrix.times(points[i]);
  x[i] = result.get(0,0);
  y[i] = result.get(1,0);
  z[i] = result.get(2,0);
 }
 
 normal = getNormal().normalise();
}

To build the rotation matrix, I created a RotationMatrix class, which is really just a utility class for building the matrices specified above, given an angle and an axis of rotation.

public static RotationMatrix getInstance(double theta, RotationAxis axis) {
 switch(axis) {
  case X:
   return new RotationMatrix(new double[][]  {
                  {1,   0,          0},
    {0,cos(theta),-sin(theta)},
    {0,sin(theta),cos(theta)} });
  case Y:
   return new RotationMatrix(new double[][] { 
    {cos(theta),0,sin(theta)},
    {0,         1,    0},
    {-sin(theta),0,cos(theta)} });
  case Z:
   return new RotationMatrix(new double[][] {
           {cos(theta),-sin(theta),0},
    {sin(theta),cos(theta),0},
    {0,         0,         1} });
 }
 return null;
}

The final piece is to create the matrix and pass it to rotate() when the mouse is moved.

RotationMatrix yRot = RotationMatrix.getInstance(xangle, RotationAxis.Y);
RotationMatrix xRot = RotationMatrix.getInstance(yangle, RotationAxis.X);
for (SceneObject d : scene) {
 d.rotate(yRot);
 d.rotate(xRot);
}

Give that a bash, and watch in amazement as your scene does exactly the same thing that it's always done. Except in a bit of a neater way. Which is no bad thing, right? But we can make it even better than that. One lovely property of matrices is that if you have two matrices to do two rotations, you can just multiply the two matrices and get a single matrix that does both rotations in one step:

RotationMatrix yRot = RotationMatrix.getInstance(xangle, RotationAxis.Y);
RotationMatrix xRot = RotationMatrix.getInstance(yangle, RotationAxis.X);
RotationMatrix totalRot = xRot.times(yRot);
for (SceneObject d : scene) {
 d.rotate(totalRot);
}

Great stuff. I love you matrices. If you love matrices too, download the source.

Adventures in 3D: Interlude

2009-04-04T13:02:00.000-07:00

As mentioned in the intro to this series, this is largely an unplanned foray into 3D graphics, and the code presented here is as I write it, without necessarily being the best or neatest way to do things. At this point, I feel a need to do some refactoring on the code to try and make a solid base to build on further. These bits are not necessarily necessary or instructive, so feel free to skip this bit if you like, although if you're going to carry on I suggest you download the source so that future entries make sense. Even if you do continue reading, there are some bits that I'm simply going to point out rather than describe why I've made those decisions.

So far we've only created one object, our lonely spheroid. Naturally you are already deep into planning your own FPS that will, like, totally make Halo look like Wolfenstein in comparison, and so we'll need to start thinking about creating and managing multiple objects. An object is simply a bunch of polygons that are glued together - when the object moves 3 units to the left, all the polygons in that object move 3 units to the left. Let's change the class hierarchies around a bit. Top of the tree is a SceneObject, something that can be a) rotated and b) drawn. That extends to two classes. A BasicSceneObject is an object such as a sphere or a cube, or some other 3D shape we may wish to create. BasicSceneObjects are really just a way of group together the other type of SceneObject, which is a Primitive, the 2D polygons that make up that object - to all intents and purposes, this is our Triangle class, although we could choose to render objects with squares, pentagons, or icosagons if we so choose.

The BasicSceneObject class defines how to draw and rotate multiple Primitives - just loop over every Primitive in the object, and also allows a method to get at it's polygons. This becomes important because when sorting for z-order, we need to consider all polygons in the scene together at the same time, for instance if two objects overlap. The BSO also defines offsets for x,y,z, which defines where the object is in the world, and a translate() method to move the object.

Now we've got a basis for objects, we can add some concrete object classes. We simply extend BasicSceneObject, and in the constructor define how to build it in terms of Primitives. So there's a Spheroid object, which just uses the code we had in createScene() previously, and a Cuboid. The Cuboid just defines 12 polygons (6 faces of 2 triangles). The createScene() method now just becomes pretty simple:

    BasicSceneObject sphere = new Spheroid(100,60,60,50);
    sphere.translate(-100, -30, 100);
    BasicSceneObject sphere2 = new Spheroid(40,30,10,50);
    sphere2.translate(50, 20, -10);    
    BasicSceneObject cube = new Cuboid(40,40,40);
    cube.translate(100, 100, 30);
    
    scene.add(sphere);
    scene.add(sphere2);
    scene.add(cube);

On the lighting front, until now the light has simply been a hardcoded vector in the Triangle class. Now there's a LightScene object, which could contain multiple Lights. A Light has a direction, a position (which is not yet taken into account), and a colour (also not used yet), and as things progress may have some other characteristics specific to a particular type of lighting (e.g. an ambient light, spotlight etc.). The LightScene is passed to a light() method on the Primitive class to decide what color the polygon should be rendered with.

The final notable change is that you may have noticed the Y-axis problem. That is, traditionally the Y axis points up. But in Java 2D, the Y axis goes down the screen, so essentially we're rendering the scene upside down. There's a simple answer to this, and it's back in the AffineTransform class we first met way back in Part I. That time, we cheated by moving the axis origin to the centre of the screen with the Graphics2D.translate() method, so we never had to actually touch the AffineTransform ourselves. This time, we'll create an actual AffineTransform which represents a matrix:

    |  1    0   width/2  |
    |  0   -1  height/2  |
    |  0    0     1      |

which, once you've famliarised yourself with matrix maths, you'll see means

x' = x + (width/2)
y' = -y + (height/2)

Although we're not explicitly stating it as such, this is a model-to-device transformation, the last step in our pipeline. As a minor optimisation, the AffineTransform object is created ahead of time and reused in each call to paintComponent(), rather than a new Transform object being created each time. However, as the panel can be resized, we catch the call to setBounds() and recreate the Transform when required.

Now that things are a bit better defined, download the source and let's move on.

Adventures in 3D: Part VI - Faster Pussycat! Cull! Cull!

2009-03-31T21:07:00.000-07:00

Oh look, the return of the Adventures in 3D series - you might want to start at the beginning

Last time out, we had a nice shaded sphere spinning around. First things first, a sphere is very boring to rotate - if it weren't for the polygons, you wouldn't even notice. So lets jam a little bit of maths in there so that it's a bit more obvious. In the createScene() method, add a factor to the calculation of each Point position to modify the rotundness. Note the 0.8 and 0.4. This will give you something akin to a Trebor Softmint.

points[phi][theta] = new Point(radius * Math.cos(stp * phi)
   * Math.sin(stp * theta), radius * 0.8 * Math.sin(stp * phi)
   * Math.sin(stp * theta), radius * 0.4 * Math.cos(stp * theta));

If you have any sense of adventure, you will probably already have played around with the line

int STP = 60;

in the createScene() method. This line determines how many latitude/longtitude sections the sphere is divided into, and therefore, the higher this number, the more polygons that make up the sphere, and the smoother it will appear. With a value of 10, the sphere has a total of 100 polygons and will appear very obviously made up of triangles, much like the 3D graphics of yore. A value of 100 will give you something much better looking, using 10000 polygons. Of course, this is all a trade-off - the time to render 10000 polygons is not insignificant, and you'll find that the rotation is much less responsive.

Polygon count is the rawest measure of 3D graphics performance. More polygons, in theory, equals better graphics. But you can't just up the numbers, because it all takes time. So you can try to find a way to render polygons on the screen quicker, or you can reduce the number of polygons you have to render. If you want to take the latter, you can either make your graphics less detailed, or you can just plain cheat. Guess which option we're going for?

In any given frame in our 3D scene, there are a bunch of polygons that we're just not going to see, which are those on the other side of the shape, facing away from us. In the case of a sphere, that's fully half of all the polygons we're drawing every frame which we don't need to draw. So there's a simple conclusion - let's not draw them. This is Backface Culling.

Working out which faces you don't have to draw turns out to be very simple. You'll remember that in Part IV we discussed normals, which are vectors telling us which way a polygon is facing, and the dot product, which tells us something about whether two vectors are pointing the same way or not. To check for a backwards facing polygon, we'll compare it's vector normal to a vector that represents the direction we're looking in. In the Triangle class:


 private Vector viewer = new Vector(0,0,-1);
 
 public void draw(Graphics2D graphics) {
    Vector normal = getNormal().normalise();
  
    //backface culling
    double cull = normal.dotProduct(viewer);
    if(cull > 0) return;

    ...rest of the method...
 }

Quite simply, get the vector normal for this polygon, normalise it (not strictly necessary here, but we'll reuse it later), and then find the dot product with the view vector. Remember that a result of zero means that one vector is orthogonal (i.e. at 90 degrees) to the other. A result of greater than zero means that they form an angle less than 90 degrees, and so if the view vector is pointing away from the viewer, so is the vector normal, to some extent. If that's the case here, we return from the method, so this polygon is not drawn at all on screen.

There's one gotcha here - for the normal to point in the expected direction, the points in your polygons must be defined in a clockwise direction. If you define the points anti-clockwise, things can still work, but the vector normal for polygons facing away from you will point towards you, so the check becomes if(cull < 0) instead.

Let's do some unscientific testing. I added some code (the static getAndResetDrawnCount() method) to the Triangle class so we can keep count of how many polygons have actually been drawn, and retrieve that to display at the end of each frame render. I also added some very simple timing code to time how long each frame takes to display.

Without backface culling present (and using an STP value of 100), the output shows that all 10000 polygons were rendered, and the time varies but a quick eye grep suggests it averages (on my machine) around 27-30ms. When the two lines of culling code are added, the average number of objects actually drawn to the screen drops to around 5080, and the average time is somewhere around 15ms - as you might expect if it's doing half the work.

By now you must surely be taking your seat in the pantheon of the 3D gods. If not, cheat by downloading the source. In either case, we'll be coming back to earth with a bump next time when we look at introducing a camera. Warning: contains matrix maths.

Hot Gigolo (#324)

2009-02-11T13:44:00.000-08:00

For many years I've led an extraordinary double life. You wouldn't think it to look at me, but hiding under my mild mannered exterior is the equally mild mannered Reverend Bingo. The good Reverend goes back at least 13 years now, to my first steps on the net during my university years. Heck, I even used it on some Telnet MUD type thing, the name of which is lost to time and memory. Over the years many have found deep meaning to the name - some kind of comment on the church and their relationship with modern culture - but the name wasn't my invention. I seem to have borrowed it and never quite got round to giving it back.

Generally I shorten it to revbingo, as in the url for this blog, and as far as I'm concerned it's everything a netname should be. It's short, it's fairly memorable, it's interestingly cryptic and it's slightly silly without being downright embarrassing ("Ok Grandma, write this down - it's H-O-T-G-I-G-O-L-O-3-2-4 at gmail.com"). Most importantly, it's unique - I haven't found a website yet where I couldn't register with it as a username.

At least, I thought it was unique. One thing I've never really done in those 13 years is to google for "revbingo". Let's give it a go, eh? First two results, Amazon review. That's me alright - that book was terrible. Flickr, me. RateMyCover, me. Ubuntu Forums, me. Accidentally formatted my Sansa, m... wait! I've never owned a Sansa, let alone wiped one accidentally. Twitter, me. Spring RCP (ugh), me. Ubuntu again, me. Launchpad, me. Zoomr, me. MoneySupermarket - not me. Xandros - not me. Rudius - not me. Someone somewhere is polluting my brand.

Now, having borrowed the name in the first place, I guess I ought to not be surprised if a few other people use it too. But it brings home the importance we place on identity, especially in a context like the internet where real identity is all too difficult to establish. How does someone googling for me on the net know what's me and what's not? There's nothing about the other posts that particularly concern me. I guess I could live with folks thinking that I had reversed into a van or tried to install Half-Life on Linux (although let's be clear, I would never admit to having been a Linux n00b :). It's just that it's not me. The fact that these other uses only pop up here and there in amongst my own usage make it even more likely that someone would believe it's me.

Which makes me wonder, where have these people gone since? Have they discovered that I've already taken that username on gmail, twitter, flickr et al and gone for something else? (In a slight panic, I've just bought up www.revbingo.com). Did they decide that revbingo was a really poor username?

I guess there's nothing else for it. Just call me HotGigolo324.

Case in point

2008-10-27T13:10:00.000-07:00

This definitely comes under the Bin Of Knowledge heading. In a google I found many people with this problem, but no mention of my particular solution, so maybe this will help at least a handful of folks out there.

I have an Xbox360 through which I stream content from a LaCie EDMini NAS disk, which serves up files via TwonkyMedia. To be honest, it's usually music, but last night I felt the urge to do some learning and so decided to watch some episodes of Meet The GIMP (highly recommended by the way, if you enjoy listening to earnest Germans discuss the finer details of sRGB colour space - and who doesn't?). These come as .mp4 files, but the Xbox mysteriously didn't seem to recognise them, even though they're supposed to be supported. That was until I downloaded one episode that had an .MP4 extension (note the capitalisation), which did appear.

This led to one of those "tch, I know this isn't going to work, but I'll try it on the crazy off-chance" moments, where I renamed the files to end with the .MP4 extension instead of .mp4. And voila, there they were on the Xbox.

I'm not sure where the problem lies on this one, whether the Xbox or Twonky, but don't say I don't give you things.

Adventures in 3D: Part V - Law and Z-Order

2008-08-31T12:40:00.001-07:00

At the end of Part IV, we finally had a rotating sphere that had some nice lighting from one side. But there was a problem. If you turned the sphere, you'd almost certainly see sections where it looked like you were looking through the sphere at the surfaces on the back side.

There's a simple reason for this, and a simple fix. The problem is that we're just drawing polygons relatively willy nilly to the screen - the order in which they appear in the ArrayList that we use for the scene. So in some cases we draw the front side polygons, but then also draw the back side polygons, which just appears over the top of the front side. What we need to do is make sure that anything at the back is drawn first, then anything in front of it is drawn last. This is z-ordering.

The fact that we've got all our scene objects in an ArrayList is very handy. We can just use Collections.sort() to sort our list into Z-order before we draw the polygons. To ease things along, I'm going to rearrange the class hierarchy sightly (read: the original design wasn't really thought through). I'll implement an abstract superclass SceneObject - anything that is in our scene, whether it be Points, Triangles, Spaceships, whatever, needs to be a) Drawable, and b) Comparable, so we can work out the order to draw it. So our scene now becomes an ArrayList<SceneObject> instead of ArrayList<Drawable>. To make the compareTo() method work, it'll also have an abstract method getZOrder(), which will be used in the comparison. Because it's declared in the superclass, it means I can still compare Points with Triangles and Spaceships with Pineapples, at least as far as Z order is concerned.

import java.awt.Graphics2D;

public abstract class SceneObject implements Drawable, Comparable<SceneObject> {

 @Override
 public abstract void draw(Graphics2D g);
 public abstract double getZOrder();
 
 @Override
 public int compareTo(SceneObject o) {
  double zOrder1 = this.getZOrder();
  double zOrder2 = o.getZOrder();
  if(zOrder1 == zOrder2){
   return 0;
  }else{
   return (zOrder1 > zOrder2) ? -1 : 1;
  }
 }
 
}

To keep things simple, we just work out the average z distance for the Triangle and use that value. In more complicated 3D scenes, it is of course possible for triangles to overlap, but we'll assume here that everything tessalates nicely. So implementing the getZOrder() method in our Triangle class is very easy.

 public double getZOrder() {
  return (z[0] + z[1] + z[2])/3;
 }

Now that all that's done, the panel class just calls Collections.sort(scene) before actually drawing the scene. Note that in terms of performance it's probably hard to do much better than Collections.sort(). As one last change, let's light the sphere from the front, so that you can see the whole thing in all it's glory. That just means changing the light vector from (1,0,0) to (0,0,1). You can also check that your z-ordering is working by moving it to (0,0,-1). If the light is behind the sphere, and your polygons are being painted correctly, you should see nothing.

Yes, you are l33t. If you have failed at being l33t, you can at least pretend by downloading the source. Then you can move on to Part VI - Faster Pussycat! Cull! Cull!

Adventures in 3D: Part IV - Let There Be Light

2008-08-31T01:29:00.000-07:00

<SwissToni> You see, creating 3D objects is like making love to a beautiful woman</SwissToni>. You've got to set the mood, a bit of gentle lighting here and there, create some contrast.

Simple lighting is actually easy stuff, just wave hello to our friend, the Vector. Remember from Part I that the Vector simply consists of measurements along the x,y,z axes, and you can crunch some numbers to get a couple of useful things out of it, which we'll come to.

Consider a single light source in our scene. It's easy enough to see that any faces that are pointing directly towards the light will be fully lit, and any that are pointing away from the light will be in the dark. In between those, faces that are at some angle towards the light will be partially lit, in some proportion that is a function of that angle.

In 3D space, you can get an idea of how much a given face is pointing in a chosen direction by calculating the dot product. The dot product gives you just a number (a scalar value). If you vectors are of unit length, then the dot product will range from -1 (the vectors are in opposite directions) to 0 (the vectors are at right angles to each other) to +1 (the vectors are in the same direction). The dot product is stupidly easy to work out, it's just multiplication and addition. Given vectors A(x,y,z) and B(x',y',z'), the dot product is defined as:

A.B = x*x' + y*y' + z*z'

Let's start putting this into our code. We'll need to define a Vector class, which is just x,y,z values, plus a method to calculate that dot product.

public class Vector {

 public double x;
 public double y;
 public double z;
 
 public Vector(double x, double y, double z){
  this.x = x;
  this.y = y;
  this.z = z;
 }
 
 public double dotProduct(Vector other){
  return this.x * other.x + this.y * other.y + this.z * other.z;
 }
}

So far, so good. We know we need to calculate the dot product, but what Vectors are we using? One is obviously going to be a Vector representing the direction of the light, and that's simple because we just need to define an arbitrary Vector. What we need to know is how that compares to the direction that each surface in our scene is pointing. For that, we need to calculate the cross product. The cross product of two vectors results in another Vector that points at right angles to those original Vectors. Again, it's startlingly simple to work out. Take A(x,y,z) and B(x',y',z') again, and you can define a new Vector C(x'',y'',z'') where:

x'' = y*z' - z*y'
y'' = z*x' - x*z'
z'' = x*y' - y*x'

So let's add that into our Vector class as well:

public Vector crossProduct(Vector other){

  Vector v = new Vector();

  v.x = (this.y * other.z) - (this.z * other.y);
  v.y = (this.z * other.x) - (this.x * other.z);
  v.z = (this.x * other.y) - (this.y * other.x);
  
  return v;
 }

Given two vectors in the plane of our triangle, the cross product will give you a vector that points perpendicular to the triangle (a.k.a the Surface Normal). And how do you get two Vectors in the plane of the triangle? Simple, just work out vectors between the points of the triangle. A Vector is just the difference between two points. We can add a useful method to our Point class to return a Vector given another Point.

public Vector vectorTo(Point p){
  return new Vector(this.x - p.x, this.y - p.y, this.z - p.z);
 }

and given that method, we can take the three points in our triangle, calculate two vectors, get their cross product and wa la, you have your surface normal. A bit like this...

 public Vector getNormal(){
  
  Point p1 = new Point(x[0], y[0], z[0]);
  Point p2 = new Point(x[1], y[1], z[1]);
  Point p3 = new Point(x[2], y[2], z[2]);
  
  Vector edge1 = p2.vectorTo(p1);
  Vector edge2 = p3.vectorTo(p2);

  
  return edge1.crossProduct(edge2);
 }

Note that the creation of the Points and use of the vectorTo() method could actually be done away with, and we could just create a vector using e.g. new Vector(x[1]-x[0],y[1]-y[0],z[1]-z[0]), but it helps demonstrate the concepts.

Right, we have our surface normal, and we have our arbitrary light vector. Let's for now say that the light vector L is (1,0,0) i.e. the light is from the right. We're going to get the dot product to see just how parallel they are, and then use that to create a colour to use for the triangle. For now we'll just stick with greyscale, and it makes sense to use Hue,Saturation,Brightness (HSB) instead of RGB - then we can just alter the Brightness based on the dot product. When setting the colour, Brightness needs to be between 0.0 and 1.0, so we'll need to deal with vectors of unit length, otherwise the dot product will be outside that range. That calls for normalisation. To normalise a vector simply means to keep it pointing in the same direction, but make it's length equal to 1. Don't confuse normals (perpendicular vectors) with normalised vectors (vectors scaled to unit length). Let's add a couple of methods to the Vector class.

  public Vector normalise () {
     return scale (1.0 / Math.sqrt (dotProduct(this)));
  }


  public Vector scale (double scale) {
     return new Vector (x * scale, y * scale, z * scale);
  }

The scale() method just scales the vector along each axis. Note the trick to get the length of the vector - the dot product of a vector with itself is the length squared. With these methods, we can now make sure that we're dealing with two unit vectors in the Triangle's draw() method. To summarise the whole thing again - we'll take the triangle's surface normal and normalise it, then take the light vector and normalise it, then find the dot product between the two. Given that they're both normalised, we'll get a number between -1 and 1, which will be used to set the brightness of the colour that's used to draw the polygon.

     double dt = getNormal().normalise().dotProduct(normLight);
     Color c = Color.getHSBColor(0.0f, 0.0f, (float) dt);
     graphics.setColor(c);
     graphics.fillPolygon(xPoints, yPoints, 3);

FAIL! Well, two thirds fail at least. It's looking fairly cool on the left side, not so hot on the right side. That's because everything on the right hand side is returning a number less than zero, which obviously causes the getHSBColor() method to go a bit crazy (actually, I'm surprised it didn't just bork altogether). So we plainly need to have some sort of check in there to make sure we only deal with positive numbers. Or wait, do we? Remember that we set our light source at (1,0,0), so the light should be coming from the right - right? The thing is, the surface normals for polygons will be pointing to the right. The light vector is coming from the right, pointing left. So actually, the correct polygons to be lit are those that have negative dot products i.e. the vectors are in opposite directions. So let's add a quick check. Anything with a zero or positive dot product is on the dark side of the sphere, so we'll just draw them black.

     Color c = (dt < 0) ?
      Color.getHSBColor(0.0f, 0.0f, (float) Math.abs(dt)) :
      Color.BLACK;

I like! If you like too, download the source.

Wait a second though. Have a go at rotating the object. Sure, it's prettily lit, but at some point you'll find something a bit odd going on. In Part V - Law And Z-Order, we'll talk Z-order.

Adventures in 3D: Part III - Poly Filler

2008-08-30T12:43:00.001-07:00

Right, you've done parts I and II, and you've got some rotating points. Remember that in Part I, we discussed that we were going to build our scenes out of triangles. Luckily for us, we also mentioned that a triangle is just 3 points. If you can rotate a point, you can rotate a triangle.

To start with, we'll throw together a Triangle class. It'll have arrays to store the coordinates for each point, and when we rotate it we just need to apply the rotation to each element of the array.

import java.awt.Graphics2D;

public class Triangle implements Drawable {

double[] x = new double[3];
double[] y = new double[3];
double[] z = new double[3];

public Triangle(double x1, double y1, double z1, double x2, double y2, double z2,
        double x3, double y3, double z3){
x[0] = x1;
x[1] = x2;
x[2] = x3;
y[0] = y1;
y[1] = y2;
y[2] = y3;
z[0] = z1;
z[1] = z2;
z[2] = z3;
}

public void draw(Graphics2D graphics){
}

public void rotateZ(double radians){
  double[] sx = x.clone();
  for(int i = 0; i < 3 ;i++){
  x[i] = (sx[i] * Math.cos(radians)) - (y[i] * Math.sin(radians));
  y[i] = (y[i] * Math.cos(radians)) + (sx[i] * Math.sin(radians));
}
}

Don't forget that when it comes to storing the original points in the rotation, assignment of an array is by reference, so you need to use .clone() to get a copy of the array instead of a reference to the original. Again, a shrinking triangle will be a sign that you'd missed something.

We're also implementing Drawable, so we need to specify how to draw this triangle. Luckily that's pretty simple, it's just a case of drawing a polygon between the appropriate points. The only slight difficulty is that drawPolygon() expects arrays of integers, and we're storing the points as doubles, so we'll need to do a quick cast into new arrays before we can draw the object.

public void draw(Graphics2D graphics){

   for(int i=0;i < 3;i++){
      xPoints[i] = (int) x[i];
      yPoints[i] = (int) y[i];
   }


   graphics.setColor(Color.WHITE);
   graphics.drawPolygon(xPoints, yPoints, 3);
}

Last thing to do is to actually create some triangles to draw. We could do something really simple, but let's push the boat out and create a sphere. I won't go into the details too much, but it just involves creating points by latitude and longitude, creating squares from neighbouring points, and then breaking that square down into 2 triangles, which are added to the scene. The STP variable determines how small those squares are, and so ultimately how smooth your object looks - at the cost of speed, natch. Play around with it and see what works.

    private ArrayList<Drawable> createScene(){
int STP = 60;
double stp = Math.PI * 2 / STP;
double radius = 100;
ArrayList<Drawable> scene = new ArrayList<Drawable>();

Point[][] points = new Point[STP][(STP/2)+1];
for(int phi = 0; phi < STP; phi++){
    for(int theta = 0; theta < (STP/2)+1; theta++){
        points[phi][theta] = new Point(
                  radius * Math.cos(stp*phi) * Math.sin(stp*theta),
                  radius * Math.sin(stp*phi) * Math.sin(stp*theta),
                  radius * Math.cos(stp*theta));
    }
}

for(int x = 0; x < STP; x++){
    for(int y = 0; y < (STP/2); y++){
        int xx = (x+1)%STP;
        int yy = (y+1);
        Point p1 = points[x][y];
        Point p2 = points[xx][y];
        Point p3 = points[x][yy];
        Point p4 = points[xx][yy];
        Triangle t = new Triangle(p1.x, p1.y, p1.z, 
                        p2.x, p2.y, p2.z, 
                        p3.x, p3.y, p3.z);
        Triangle t2 = new Triangle(p2.x, p2.y, p2.z, 
                        p4.x, p4.y, p4.z, 
                        p3.x, p3.y, p3.z);
        scene.add(t);
        scene.add(t2);
    }
}

return scene;
}

Some other slight adjustments to be made. In our laziness we assumed in the mouseDragged() method that we were dealing with Points, but our scene is now made up of Triangles, so that needs to be changed. You might also want to change the axes of rotation to whatever feels natural, now that you've only gone and created a freakin' wireframe sphere that rotates when you drag it! Download the source

One final thing - instead of wireframe, let's actually fill the polygons and create a solid object. Just replace graphics.drawPolygon() with graphics.fillPolygon().

Uhhhh. Wait. Now we've just got a big blob. That's not nearly as cool. Don't panic though, in Part IV - Let There Be Light, we'll look at how to give this thing some definition.

Adventures in 3D: Part II - Round We Go

2008-08-30T08:39:00.000-07:00

[The next in a series on simple 3D graphics in Java. You might want to read the Intro, and Part I - The Basics]

In Part I, we got some spots. Not too impressive, and certainly not very 3D. But let's build on that, and start making those spots move. Our aim is to have something rotating when we move the mouse, so let's look at rotation.

If you want to talk rotation, you need to talk sine and cosine. Remembering back to school days and trigonometry, sine and cosine together describe a circle. If you want to know the x,y of any point around a circle of unit radius, you just need to look at the angle from the horizontal - the cosine of that angle tells you x, and the sine of the angle gives you y. If the circle is not unit radius, you just multiply accordingly. In simple terms:

x = r cos t
y = r sin t

where t is the angle. That's all very well, but if we're going to do arbitrary rotations, you need to talk in terms of the delta i.e. the change in angle, and not just an absolute angle. Thankfully, that's not overly difficult either. I know I said I wouldn't delve too much into the maths, but this is useful to know. You have a point x,y, which with the equations above you can talk about in terms of an (unknown) angle t. Now, you want to rotate that point around an axis (the Z axis) by an arbitrary angle, which we'll call dt, and that will give you a new point x',y'. That new point you can talk about in terms of an (unknown) angle t'. Put all that together, and you come up with:

x' = r cos t'
y' = r sin t'

But t' is just t + dt, so:

x' = r cos (t + dt)
y' = r sin (t + dt)

Naturally, your maths teacher forced you to constantly chant the formulas:

cos (t + dt) = cos t * cos dt - sin t * sin dt
sin (t + dt) = sin t * cos dt + cos t * sin dt

With a little bit of substitution and refactoring, you arrive at:

x' = x * cos dt - y * sin dt
y' = y * cos dt + x * sin dt

and before you know it, you can talk about x' and y' purely in terms of the old position (x,y) and the angle you've rotated through (dt).

Let's plug that into our Point class. We'll create a method called rotateZ() which will accept an angle as a parameter. The method will then move the point from x,y to x', y' by applying the formulas above.

public void rotateZ(double angle){
    double x0 = x;
    x = (x0 * Math.cos(angle) - y * Math.sin(angle));
    y = (y * Math.cos(angle) + x0 * Math.sin(angle));
}

Notice that we save the initial value of x in another variable beforehand. Otherwise, we modify x in the first formula, and the formula for y will be messed up. If your scene appears to shrink as you rotate it, you've probably made that mistake.

Sweet. Now we just have to do something to invoke this method and get our points moving. We're going to do this fairly simply, by adding a MouseMotionListener to the panel. When the mouse is dragged i.e. the button is down, we'll measure how far the mouse has travelled from it's last position, and then rotate all the points in our scene that number of degrees. Naturally we'll convert it into radians first (you are working in radians, right? Right??).

public void mouseDragged(MouseEvent e) {
   int x = e.getX();
   int dx = x - oldX;
   oldX = x;
   double angle = dx * radian;
   for(Drawable d : scene){
       Point p = (Point) d;
       p.rotateZ(angle);
   }
   panel.repaint();
}

Of course, don't forget to a) store the last known X position for next time, and more importantly b) repaint the panel once the rotation is done so you can see the result of your hard work.

If it all works, you should now have a bunch of spots that rotate when you drag the mouse left and right! It gets better. Let's say that when you move up and down, we should rotate around the X axis. Well, that's easy peasy - we just shift the axes so Y becomes Z and X becomes Y, and then reuse the same equation (think about the Right Hand Rule). So you can plug that formula in as well and link that to the mouse movement in the y direction. If you're lazy, you could just download the source

Wait, what's that? It looks like it's rotating in 3D? Well sure it does! Congrats space cadet, you're well on the way. Best take a look at Part III - Poly Filler before you explode with excitement.

Adventures in 3D: Part I - The Basics

2008-08-30T05:54:00.000-07:00

[If you haven't already, you might want to read the Intro]

So, let's set off with some fairly modest aims - we just want to produce a simple 3D scene that we can rotate using the mouse. There's a few simple concepts that we'll need to get under our belts to do that. Thankfully, most of them are little more than GCSE maths. If you want to really get a grasp on these, you could do a lot worse than this page.

Let's also put a disclaimer on this. This is my first real dive into this sort of stuff, and I make no claim to be an expert, or that what's included here is necessarily the fastest, easiest or correctest way to achieve the aims. It's just a gentle amble trying to discover the key concepts and hopefully get something out the other end that looks reasonable.

First concept: the Point. A Point is exactly what you'd think it would be, a point in space. It consists of x, y and z coordinates, and it can be translated in some way to another point in space. It has location, but no length, and no direction.

Second concept: the Vector. A Vector can sometimes look suspiciously like a Point, but it's important not to confuse them. Like a Point, a Vector consists of x,y,z components, but the key difference is that these indicate a change in those axes, not a point. Think of it as an arrow. So a Vector (2,4,5) goes 2 units along the X axis, and 4 units along the Y axis, and 5 units along the Z axis. It has a direction, and it has a length, but it doesn't exist in any particular location. In that sense it's the precise opposite of a Point. You can do funky things with a Vector. You can take another Vector and calculate their dot product, which gives you a measure of how orthogonal they are. You can also take another Vector and find their cross product, which will result in another Vector which points at right angles to the first two. You can take a Vector and scale it, to double it's length, or halve it's length, or make it's length equal to one, a.k.a. normalisation. Under the covers, all of these things involve nothing more than a bit of multiplication, but they are immensely powerful.

Third concept: the 3 sided polygon, a.k.a the Triangle. Triangles are useful things for 3D graphics, because they are coplanar. Safe to say, everything we build we'll make out of triangles in 3D space. All a triangle consists of is three Points. From those Points, you can work out what the edges look like, and represent them as Vectors, and with those Vectors you can work out a cross product to get a Vector that points perpendicular to the triangle.

Fourth and final concept: Coordinate systems. A coordinate system simply means that you agree on the numbers you're going to use to define your x,y,z values. When it comes to 3D graphics, you're usually concerned with at least two coordinate systems. World coordinates tell you where the object is in absolute space. If the object is not moving, its world coordinates remain the same. But if you're moving the camera around it, the object moves on screen, so it must be moving in some coordinate system. That's your view coordinates - the position of the object in relation to your eye. If your eye (the camera) moves, the object moves in your view coordinates. Generally, the two are equal and opposite. Let's say I'm looking at the front face of a cube, and I want to see the right hand side of it. I could do two things to achieve the same effect. I could stay still and turn the cube 90 degrees clockwise, which would involve changing it's world coordinates. Or I could leave the cube alone and move myself 90 degrees anti-clockwise, which would be a change in my view coordinates. Either way, the result with regards to the cube is the same. In the following examples, our viewpoint will stay the same, and we'll just rotate the object in space. If we wanted, we could achieve the same thing by keeping the same world coordinates and moving the camera instead.

Right, let's get cracking on some code. We're working in Java, so first thing we're going to want is a JFrame and a JPanel to draw our scene on. This is pretty standard stuff. Standard practice is to override the JComponent's paintComponent() method, call super.paintComponent(), and then do our business. We'll use one little trick here. We'll generally be creating stuff centred around the origin, which is at point (0,0,0). The problem is that as far as the Java2D libraries are concerned, the point (0,0) is the top left of the screen, so everything we do will be squeezed up in that corner. We could load our equations involving coordinates with some kind of offset to push it into the middle of the screen, but the Graphics2D object offers us an easier solution, the AffineTransform. The Javadoc looks a little scary, but ultimately it's just a way to tell Java2D to automatically do the offset for us without having to think about it in the calculations. It's made even easier by helper methods such as translate() which mean you don't even have to get your hands dirty in matrix maths. So if we specify graphics.translate(panel.getWidth()/2, panel.getHeight()/2), then anything that we draw at (0,0) will be in the middle of the panel, and not the top left.

We'll have to draw something, otherwise we'll just get a black screen, so let's plot some Points. That gives us an opportunity to write a class to model our first concept, the Point. As we already said, it just has three coordinates, so those are just instance members of our class. Let's not bother with getters and setters, it's just unnecessary bloat, and those equations are going to look pretty ugly otherwise. This isn't Enterprise Code now, you know.

I'm also going to define an interface, Drawable, with a single method draw(Graphics2D) which any objects, be they Points or Triangles or whatever, will implement. In the case of the Point, we're just going to draw that point at the x,y coordinates, and ignore the z component. You might call it lazy, I call it Parallel Projection. We'll store all the objects to be drawn in an ArrayList of Drawables, and then the panel just has to iterate that list and ask each object in turn to draw itself.

I think we're ready to go - download the source. So, we bung all this together, and what do you get?

Yup, that's, errr, impressive alright. Still, we've got the basic code in place, let's head to Part II - Round We Go.

Adventures in 3D: Intro

2008-08-30T05:45:00.000-07:00

Always on the lookout for something to mess around with codewise, I settled on the idea of venturing into the world of 3D graphics. In the days of Blitz Basic on the Amiga, school lessons in trigonometry inspired me to get as far as a spinning wireframe cube, but I've never really delved into the Java graphics libraries in any great depth.

Of course, Java has a fully featured and ready made 3D library, but that's no fun at all! I'm the sort of guy who likes to understand the nuts and bolts before moving on to the shortcuts, so I decided to have a go at everything from first principles (read: maths).

Just a couple of days into it, I've got some fairly simple yet fairly spiffy stuff going on, so it struck me as something worth putting back into the bin of knowledge, and blogging it may just concrete some of the concepts into my head a bit more. There's plenty of other reading material out there, so I'm not going to dwell too much on the mathematics, but hopefully it might give you a foot up to get you started.

A disclaimer though - I'm learning this as I go too, so I make no guarantees that this is necessarily the right or best or fastest way to do things. It's more an exercise in understanding the concepts rather than trying to write the most elegant/fastest/shortest code.

Let's start at Part I - The Basics

Pretty Persuaded

2008-08-30T00:56:00.000-07:00

Question: What is the greatest piece of silence ever captured on record? Answer: Forget John Cage and his lengthy 4'33". It's that brief pause on R.E.M.'s Lifes Rich Pageant that is bookended with the sharp departure of Begin The Begin and the jangling, diving intro to These Days. It's so utterly imprinted on my brain that to have one song without the other, and that magical non-audible glue in the middle, is like Morecambe without Wise.

I bring this up for no good reason other than because I was reminded of it this week when it failed to materialise during the band's performance at the Southampton Rose Bowl. However, as a whole, it rocked. I won't go on at length about my teenage obsession with the band (the Out Of Time, AFTP era), but safe to say that as the years have gone on, they've lost a certain relevance, and certainly the last time I saw them live (the Up tour), it was a disappointment.

No disappointment this time though, utterly brilliant. Sure, bit too many "greatest hits" for my liking, but also a decent smattering of the good stuff, and the new songs from Accelerate are great on the CD, and even better live.

The set list (in album order, it's the only way I can remember these things)

Pretty Persuasion
7 Chinese Bros
Auctioneer (Another Engine)
Begin The Begin (not followed by These Days though, boooo)
Fall On Me
It's The End Of The World As We Know It (And I Feel Fine)
The One I Love
Orange Crush
Losing My Religion
Drive
Ignoreland (a definite highlight)
Man On The Moon
Nightswimming
What's The Frequency, Kenneth?
Let Me In (Mike, Scott McCaughey and Bill Rieflin on acoustic guitars, all crowded around Peter on keyboard)
Electrolite
Imitation of Life
Living Well Is The Best Revenge
Man-Sized Wreath
Hollow Man
Supernatural Superserious
Horse To Water
I'm Gonna DJ
The Great Beyond
Animal

Nothing from Chronic Town or Murmur, nothing from Up, save Michael's acapella version of the first two lines from 'Hope' whilst Mike prepared himself to play Nightswimming, which was a shame - I like Up. Also nothing from Around The Sun - no-one missed it.

Consider R.E.M. back on the playlist.

The Mysterious Case of the Disappearing Downloads

2008-06-26T12:23:00.000-07:00

One for the internet knowledge bin. For a little while now, Firefox (both 2.0 and the freshly installed 3.0) has been forgetting my downloads. That is, the files are downloaded to my chosen location, but as soon as they're done, they disappear from both the usual Firefox downloads window, and the neat (and very highly recommended) Download Statusbar add-on.

I checked the immediate culprit - the Privacy tab in the preferences has a tick box labelled "Remember what I've downloaded". But that was ticked, so it can't be that. I checked it wasn't the fault of other plugins. Not that either. So I kind of resigned myself to having to skip to the desktop to retrieve my downloads, promising that next time I'd try and figure it out properly.

Anyways, tonight my patience ran out. And it turns out to be very simple - that tick box looked ticked, but given that when I clicked on it first time it stayed ticked, it suggests that really Firefox considered it to not be set.

In summary, for those not paying attention, give it a few clicks to get it in sync, and wa la, downloads back to normal again. Easy.

I was blind, but now I see

2008-04-07T08:38:00.000-07:00

We're now a while into life with Hardy x86_64, and so far so good. However, it's not been entirely without hiccup.

The decision to include Firefox 3 as standard was a brave but perhaps foolhardy move. A sizeable enough number of extensions are not compatible with FF3 - although I'm pleased that Foxmarks is now available, at least if you sign up to the beta. My usual mouse gestures extension isn't compatible, although I found a replacement. Unfortunately enough, that replacement (FireGestures) was good for 3b4, but not 3b5, which has just been pushed down the pipes, which means that currently I'm having to do without mouse gestures. For me it's no great shakes, as I only have one or two that I use, but if you're a heavy user, it's going to be a problem.

The other issue I've had in Firefox3 is with scaled images. Any images that used height and width tags to scale the image would appear as just a black rectangle - viewing the image full size would work. The issue is described in bug #182038. In summary, it seems there are three possible fixes: xulrunner1.9 has a fix that may or may not work for you; otherwise, try editing your /etc/X11/xorg.conf file and in the "Device" section adding:

Option "AccelMethod" "EXA"

And if that doesn't work (and for me, with SiS onboard graphics, it crashed X), you can try instead adding:

Option "XAANoOffscreenPixmaps" "true"

I've no idea what this does or if it might cause any other problems, but it did the business for me.

Ah, that feels good...

2008-04-03T03:31:00.000-07:00

Is there any better feeling than finally finding an elegant answer to a problem that's previously forced you to use dirty hacks? The freedom that comes from getting to strip out line after line of filthy code and replace it with a single line that does the job properly.

XSLT is my latest flirtation. I've used it a bit before, but I've come back to it to solve a couple of problems at work, and the more I use it, the more powerful and elegant it becomes. In my line of work, we do an awful lot of XML processing, especially converting to CSV, and up until now it's largely been writing and rewriting SAX handlers to do the job. This has been the default option because, well, someone's already done the hard work before, so the quickest route to get something done is to copy another SAX handler, tweak it, and job done. But it's slow and difficult to maintain, even with the best written code (and believe me, a lot of our SAX handlers are far from it). XSLT is really what should have been used from the very start.

Anyway, that problem. We use a third party product as our core system, and a large part of what we do is to take reports from that system as XML, and turn them into something that a lowly user could make sense of (read: CSV). I really want to push the use of XSLT to do this, and set about doing some proof of concept stuff. This was all going very well, until I came across a set of reports that appear to use some sort of generic MS database export - the namespace declaration is:

<xml xmlns:s='uuid:BDC6E3F0-6DA3-11d1-A2A3-00AA00C14882'
xmlns:dt='uuid:C2F41010-65B3-11d1-A29F-00AA00C14882'
xmlns:rs='urn:schemas-microsoft-com:rowset'
xmlns:z='#RowsetSchema'>

The sharp eyed amongst you will notice that the declaration of the z namespace involves a relative path to an embedded schema,which is a deprecated practice. This is no bad thing, but given this xml fragment:

<z:row someAttr="someData" />

and this stylesheet fragment:

<xsl:template match="z:row">

Xalan appears to throw a bit of a wobbly:

A node test that matches either NCName:* or QName was expected

It seems this is Xalan specific - other XSLT processors handle it just fine. So, the obvious solution is to switch processors right? Well, maybe, but dammit, I use Xalan for other stuff, I'm not prepared to let this stand in the way. Removing the # from the namespace declaration in both the stylesheet and the xml makes it work.

I spent a while looking at this, and finally came up with a dirty old hack - the use of a HashFilterInputStream. That's right, it's that dirty, a FilterInputStream that filters out the hash, so the resulting namespace is simply "RowsetSchema". Dirty, but it worked, as long as you weren't expecting a hash sign to occur anywhere else in the document. Believe me, I had sleepless nights over this one.

Thankfully, on another pass over the problem, I finally found a much more agreeable solution. Make no mistake, it's still a bit of a hack and no replacement for Xalan actually getting fixed, but at the very least it meant I didn't have to rely on my Java code to do the right thing before processing the transform. The solution is this - where you reference a tag in the dodgy namespace, explicitly test for the node-name() and namespace-uri() as strings, rather than letting Xalan do the name resolution.

So where you may have previously used:

<xsl:template match="z:row">

you should instead do the explicit test:

<xsl:template match="node-name()='row' and namespace-uri()='#RowsetSchema'">

You're welcome.

Ubuntu uh-oh

2008-03-30T14:08:00.000-07:00

Uh oh, it's happened again. Upgrade fever strikes. You see, my laptop is an AMD64, and it struck me that I was running a 32 bit OS. I've flirted with 64 bit before with XP 64, and the benefit just didn't justify the hassle of getting things working. That said, it also struck me that if I was ever going to install the 64 bit version, it would be an awful lot easier to do it now, whilst I was still in fairly virgin territory, than a year down the line when reinstalling everything would be a PITA.

So, deep breath, quick read of the Ubuntu forums to make sure I wasn't diving in to a complete mess, and off we go with downloading the ISO - it's times like this that an employer's huge bandwidth and a 1Gb USB stick come in useful.

Nothing to report from the install step (apart from the DUH moment of taking 20 minutes to figure out why GParted is complaining that I haven't selected any root partitions), and soon we're off and running. My old friend, the wireless, is back to haunt me, but I'm a veteran now, and it's less than 30 minutes before it's working using the Restricted Driver Manager.

The most remarkable thing about the 64 bit version is that it's pretty unremarkable. Apart from the well documented lack of Flash for 64bit Firefox - which is easily remedied - everything works as you might expect. There's no great shakes as far as performance goes, at least not in day-to-day use, but I get a warm fuzzy feeling knowing that those extra 32 bits in my CPU, which until now have been sitting idle, waiting for the day when they'd be called into action, are now busy helping out.

I promise that I'm at the end of upgrades and installations now. Not least because the other half is getting a bit bored of finding everything has changed yet again.

Ubuntu upgrade

2008-03-22T04:55:00.000-07:00

No sooner is Ubuntu up and running than I spy that the beta of Hardy Heron is available. I've finally got a nice stable system, I've found all the bits and pieces I need, I've customised it just nicely. There's no point in upgrading for the sake of it, is there? Errm, well yes actually, there is - because I can!

Thankfully, Ubuntu's update manager works pretty seamlessly - select your updates, click install, away it goes. For anyone not familiar with Linux, installation of software is (by default, at least) from centralised Ubuntu package servers, which means a) no hunting round the net for compatible downloads, and b) a damn big download pipe. It's one of the few places on the net where I actually get some use out the bandwidth I pay for. For Hardy, the total download was around 780MB, taking a mere 20 minutes. It wasn't all that long ago when I'd wait that long for a single MP3. The installation itself was pretty straightforward too - should the distribution be about to overwrite config files that you may have changed manually, it'll pop up a window allowing you to do a diff and check out the differences, then either accept one of the versions or try and do a merge. An hour or so later, Hardy is installed and ready to go.

Admittedly there's nothing incredibly exciting about Hardy, the most noticeable change for me being the inclusion of Firefox 3 beta 4 as standard. This is a pretty bold move by Ubuntu - unfortunate in that a significant number of my add-ons (Foxmarks, Gmail Manager, All-in-One gestures) aren't yet compatible. However, Hardy does also bring with it a new Screen Resolution app, which may go some way to assuaging my complaints about getting the basics right. It's nice to know that the Ubuntu community is taking my opinions seriously.

The worst sin commited was the sudden non-workiness of the good old wireless card, and the fact that the ndiswrapper solution that did the job last time failed to revive it. With a bit more poking around, I resorted to retrying the kernel's b43 restricted driver and b43-fwcutter package, which also didn't work until I downloaded the updated 4.80 firmware from linuxwireless.org. Suddenly, a flash of light and the wireless card is on. Hooray! Unfortunately though, still no actual sign of a network connection, with ifup reporting errors whenever I tried to bring up eth1. In a wireless-less mire, and sick of going over the same web pages, I was about to give up when a random webpage pointed me at using dmesg to examine the kernel ring buffer. This threw up a whole lot of interesting information, showing that the wireless card was being seen but also being disabled. It also included a helpful line that pointed out that there was still a need to actually press the button on the front of the laptop to enable the wireless. Despite the light already being on, I thought there was no harm in it - and whaddya know, wireless, pure sweet digital-air goodness. As an added bonus, it also appears to be rock-steady, certainly a lot more stable than it was under Gutsy (or Windows for that matter).

Today's last deposit into the bin of knowledge - another thing that stopped working was my configuration for tapping the corners of the touchpad to go back/forward when browsing. I had the synaptics driver set up (in /etc/X11/xorg.conf) to send events 6 and 7 from those taps, which worked with Gutsy. The simple, but ultimately confusing, solution under Hardy was to change this to events 8 and 9. Ours is not to reason why, but it works.

Ubuntu upwards

2008-03-19T14:35:00.000-07:00

I could bang on about getting a wireless card with a Broadcom 4318 chipset in an Acer Aspire going under Ubuntu, but frankly it's a well covered subject already to which I can lend little insight (hint - you need this [Ubuntu forum login required] and this, and I had to modify /etc/network/interfaces to add a gateway route to 192.168.1.1, my router, when eth1 is brought up). Besides, if I'm really honest, it was largely luck rather than judgment that did the trick.

It's been a week or so now since I booted Windows - or am I legally obliged to call it Windoze now? - and I'm not sure I miss it. If I have to score points, the consistent use of oversize fonts by Linux applications irks a little bit, it makes me feel like I'm missing out on screen real estate. Like I said before, I like things dinky. But at least most of them let you change that, just a shame the defaults are a bit clunky. Anyway, I've gone for MgOpen Modata 8 as a system wide font, which compensates slightly and I'm pretty happy with how it looks. The subpixel rendering is nice, Cleartype has never looked good on my laptop screen. Combine with "Glider" controls theme and the Whiteglass pointer scheme (still not sure why my "insert text" pointer has to be so damn thick - just give me 1 pixel wide dammit!), and all in all it's looking pretty sexy, sexier than Windows ever did anyway.

Talking of fonts, one application that doesn't play ball is Amarok, but I suspect that's because it's a KDE app doing it's best to keep up in a GNOME environment. Regardless of that small quirk, Amarok is really quite nifty as a music library organiser and iPod syncer. On Windows, iTunes was just horrible - slow, freeze-prone, sometimes hard to fathom. Oh, and "Gapless Playback Analyser"? Stop that. No really, stop it. Just when you think iTunes is finally getting it together, the bloody Gapless Playback Analyser kicks in and suddenly every mouse click takes 20 seconds. I suspect it works great if you've got 200 files on your local disk, but with 8000 songs on a NAS, it's no fun. On the other hand, you could use Windows Media Player - but if you want to sync your iPod, you'll have to shell out for dopisp, and even then it doesn't support podcasts. I'm sure there's probably other software out there, but I never found it. Well, now I've found Amarok, and it does a good job. No fuss, things just make sense, and it doesn't bork my ipod, which is a bonus. Plus it kindly went away and grabbed a whole ton of album covers, which is nice.

Let's finish with some music - I have Plenty

[Edit: That Amarok font problem - sorted by installing kcontrol, which basically works for all KDE apps. Amarok now looks as sexy as everything else. Consider me pleased]

Ubuntu underway

2008-03-16T14:09:00.000-07:00

Hey, a second post! Bonus.

This week has seen my reintroduction to Linux. My previous incursion into such territory was having Mandrake installed on an old desktop, and it wasn't a wholly pleasant experience. Not wholly unpleasant, but not enough to convert me. The desktop went a couple of years ago to be replaced by a laptop, and I haven't seen fit to reinstall a Linux distro since. It was just a bit too much work, a little bit slow and clunky. But, in a fit of adventurism, assisted by the absence of wife and child, I dug out an Ubuntu live CD I downloaded months ago with good intentions, and decided to give it a whirl. Heretoforth springs my considered thoughts on the subject.

Ubuntu wants to project an image of being easy to use - "Ubuntu just works". No better test of such a thing than to get it installed. I have a certain fascination for the concept of the live CD, which will let your average Joe Punter try out a distro without having to install anything. If only more software would let you do that before it stamps it's size 9's all over your lovingly ordered hard disk and sticks it's chocolate covered fingers in your registry. So you try the live CD, and when you've tried it, and liked it (hopefully), you hit the button that says "Install" and away you go. Alarmingly, this is exactly what I did with Ubuntu, and it really just worked. Admittedly repartioning your disks isn't something your gran would want to do, but the tools were there to do the job without fuss for anyone of reasonably sound mind. Also admittedly, I was rather hoping it would just work, because being a cowboy I didn't bother with the tiresome business of backing up my data. I like that little frisson when the progress bar stalls and the screen blinks - it's sky-diving for nerds. End result, 20 minutes later, the machine reboots, Grub pops up, and we're off. Handshakes and whiskies all round.

The Ubuntu desktop is instantly familiar if you've ever been near a Linux distro before. On the downside, it's in 1024x768, which may as well be 320x200 for all I'm concerned. I like dinky. My laptop can manage 1280x800, and damn it that's what I want. But I can forgive Ubuntu for not knowing that, and there's a handy Screen and Graphics item in the System menu, so it's a quick change. Oh, apart from it's not - there's no option for 1280x800. Suddenly memories of the same thing on Mandrake come flooding back, and my enthusiasm for Linux is slightly dimmed. It's slightly tempting to say that if Linux is to make it as a mainstream desktop OS, this sort of thing has to work out the box. But who are we kidding? The whole point of Linux is that it isn't a mainstream desktop OS, it's an OS for nerds. If your gran started using Debian, it would kind of defy the point.

So let's just admit that here - you use Linux because it's not straightforward. When you see that your choice of resolution isn't in the list, a small trickle of excitement ensues. And when you finally trawl Google and get to type sudo dpkgs-reconfigure -phigh xserver-xorg and press Enter to accept the defaults on lots of obscure options, you are a l33t h4x0r. Of course, this all has it's limits. No-one wants to spend 5 hours on this stuff. That's reserved for the wireless card, and is, of course, a whole other story...

(to be continued...)

A New Hope

2008-03-16T06:34:00.000-07:00

So look, here's the deal. Yes, it's another random, spectacularly normal, person setting up a blog. No, it's probably not going to get updated very often. Yes, there's a reasonable chance that you'll come back in a year and this will still be the only post on here. No, I'm not expecting anyone to read it. All of which sounds like a pretty bad basis on which to start a blog, but allow me to explain.

There's a long tail of blogs out there that were founded on exactly that basis. I've never done the numbers, but I suspect - no, I know - that for every regularly updated, well written, widely read blog, there are 100 that were a wet Sunday afternoon diversion and now sit abandoned, a Christmas puppy that finds its way to the dog's home before New Year's Eve.

The thing is, like those puppies, just because they're in the dog's home, doesn't mean they're useless. Blogs mean different things to different people. It's true that there's an awful lot of mundane cruft out there, but blogs, even those abandoned, are also realising the potential of the internet to be a big bin of knowledge. Blogs sweep up that knowledge that isn't worth knowing, or at least not in the collective sense. No-one needs a wikipedia article about StackOverflowError in java.util.regex.Pattern, or quirks in Weblogic's servlet implementation but when you come across that problem, it sure is useful information.

And that leads me here. I've taken an awful lot from other people - fixes, workarounds, walkthroughs, or just plain advice - and it seems to me that maybe I should get off my butt and put something back in that bin of knowledge. Sure, it might just all go to waste, but perhaps one day, someone will be trawling the 85th page of their Google search on some weird error they've seen, and my blog will give them just a hint on how they might solve it. Job done.

As a side effect, it's also just a useful exercise in writing. I don't do enough of it and I should do more. You never know, I might even improve with time.