## Sunday, 31 August 2008

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

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 + z + z)/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

<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, y, z);  Point p2 = new Point(x, y, z);  Point p3 = new Point(x, y, z);    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-x,y-y,z-z), 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;`

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.

## Saturday, 30 August 2008

### Adventures in 3D: Part III - Poly Filler

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;double[] y = new double;double[] z = new double;public Triangle(double x1, double y1, double z1, double x2, double y2, double z2,        double x3, double y3, double z3){x = x1;x = x2;x = x3;y = y1;y = y2;y = y3;z = z1;z = z2;z = 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

[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

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.

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

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.