SmallWorld


So. I’m currently attempting to write the graphics primitives for smallworld. I have

The gear that translates from math coordinates to screen coordinates.
This is important, because most of the time the “circles” will be oval in user-land. You can’t just transform the geometry, because that means that the strokes and fonts get transformed as well. Happily, java has an AffineTransform class which has a method to transform a Java2D Shape object. You manage the underlying geometry on the unit circle, get the shape, transform it, and then stroke the shape as the final step. “The Gear” that does this is a method whose job it is to get the affine transform that converts a unit circle onto a given bounding box.
A Complex class
In addition to providing methods, having a complex class allows you to see what is in math land and what’s in screen land. I consistently use “Complex” for math co-ordinates, and “Point” for screen coordinates.
A matrix class
Rather than writing or using some über matrix class, I have gone minimal. The class handles 2×2 complex matrices, and that’s all. It holds the coordinates in an array of 8 doubles. The main job of the class, really, is to hold my decisions about whether the matrix is by row or by column – to keep track of which elements hold the parts of A, B,C and D.

I am assuming a single-threaded model, and so my scratch variables are all static final. This might be a mistake.

A moebus transformation class
Extends matrix, includes obvious gear.
A circle class
Extends matrix. We represent projective circles as per my bible and cookbook: Hans Schwerdtfeger’s “The Geometry of Complex Numbers”.

I have a little test app. Below the canvas are two sliders. One does a elliptic transform with fixed points at (-1,0)(1,0), and one does a rotation around (0,0). There’s a button to refers the order in which the transforms are composed. The app draws various things – point, lines and whatnot – transformed by the sliders. It correctly handles the java “Insets” and borders.

Currently I am trying to get circles drawing correctly.

The method for doing this has signature:

public Shape getShape(Shape clip)

Why do we need to pass the clip in? Because a circle may be “inside-out” when projected stereographically onto the plane. It will be inside-out if the inside of the circle covers the point at infinity. To make this happen, the “shape” returned by this method is the circle (drawn anticlockwise) and the clipping boundary (drawn clockwise). To keep any stroking from being visible, I take the clip rectangle of the canvas and add a 50-pixel fudge factor around it. If no-one is using strokewidths of 100 or more, I’m ok. Of course, this clip rectangle has to be converted into math space in order for it to be correct when its converted back again.

Now … working out if a circle is inside out or not is straightforward for circles. Circles are represented by a hermitian matrix

Γ(z) = Az(z*) + Bz + C(z*) + D

The “inside” of the circle is when Γ(z) is positive (or is it negative?), the border of the circle is at Γ(z) = 0. A circle is an inside-out circle when Re(A) < 0.

But I'm having difficulty with lines. It's not arbitrary. When a circle is smoothly transformed from a positive to a negative circle (the circle passes over the point at infinity), it's important to fill the correct side of the line. One check might be: find the value of c(0) and work it out from there, but this fails if the line passes through 0.

I'm suspecting that I'll have to do something like:

Find the line Γ' at right-angles to the line Γ which passes through 0. The construction of this line will automagically take into account the "direction" of Γ. In the matrix representation of Γ', A and D will both be zero, and C will simply be the conjugate of B. So you should be able to work out which side of circle Γ should be filled from that.

Drawing the shape is another issue. It will be something like:

Work out where the line Γ intersects the boundaries of the clipping rectangle (extended off the screen). Note that in the case of horizontal and vertical lines, this will be NaN.
Choose to use either the spots where Γ hits the vertical edges of the clip rect, or the spots where it hits the horizontal edges. Note that these may be off screen. …
No, actually that won't work well. What I really want to do is construct a triangle from the correct corner of the bounding box (which is off screen, remember) to …
No, that won't work either. Drat. My cases are:

  • Horizontal line
  • Horizontal line entirely off screen
  • Vertical line
  • Vertical line entirely off screen
  • Line passing through diagonally adjacent corners
  • Line passing through diagonally adjacent corners of the bbox
  • Line that can safely be represented as going through horizontally opposite sides of the bbox
  • Line that can safely be represented as going through horizontally opposite sides of the bbox, but owing to its vertical position it is off screen
  • Line that can safely be represented as going through vertically opposite sides of the bbox
  • Line that can safely be represented as going through vertically opposite sides of the bbox, but owing to its horizontal position it is off screen

Times 2, because the “filled” half plane may be either side of the line. Note that the “entirely off screen” lines are all the same: either a null shape is returned, or the bounding box as a shape.

Sigh. This kind of code is a drag to test, because you never know if you might have missed some weird combination that makes your screen flicker as the parameters pass over a badly-handled spot.

I do think that all cases can be done as a triangle that extends off screen, except for horizontal and vertical lines, which are easy to test for.

—-

Hang on. I have a clip rect. I have a method that will tell me if a point is “inside” the circle. All I have to do is find out if the corners of the rectangle are inside or outside, and work from there. There are 14 cases, not including cases where the line passes through a corner.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: