Spheriosity Alpha 3 Released!

January 13, 2009

Today I finally managed to release the next instalment of Spheriosity. For those who don’t know Spheriosity is the Java program I wrote to be an emulation of spherical geometry and it is geared toward students in higher geometry classes or anyone interested in learning about spherical geometry. The latest release has many new features. Here are a few of them:

  • Midpoint plotting
  • Ability to draw spherical circles
  • Improved line length measurement tools
  • Ability to rename points

To give it a try head on over to our SourceForge page and download away. Spheriosity requires Java3D >= 1.4 and Java >= 1.5 . For those interested in hearing more about the latest release then keep reading.

The reason that I decided to release it as alpha is because I think there are still too many features I would like to add to the next version. Also, I have been reading about XML lately and think I might change the file format over to use an XML based one for saving spheres. Changing to XML will probably not be terribly difficult, but it does involve my needing to actually do it and then write some acompanying tests. More importantly it will, yet again, break backwards compatibility with file reading.

Hopefully, the next version I release can be beta quality. Also, I am still looking for people who would be interested in helping with development. It would be great to have other people to bounce ideas off of and check the code out to make sure there are as few errors as possible. Additionally, I don’t always have time to work on the project and getting a few more people would help it have some more consistent development.

At any rate I hope everyone enjoys the latest release and if you have any feedback please let me know either via this blog or the Spheriosity SourceForge page. Thanks!

Spheriosity Work Continues

January 5, 2009

This is just a quick update about my recent work on Spheriosity. I had promised myself that I would release a version over my winter break from college. Today I finally had time to sit down with the code and start working through a few bugs. I fixed most of the bugs that I know about, and now I have moved on into commenting and writing unit tests.

It was a bit of a struggle to motivate myself to write the current group of units tests, which is probably why they aren’t already written. I will write them though, and it will help keep Spheriosity more stable in the long run so it’s a worthwhile goal.

After the unit tests are done I plan to add one last feature which will handle midpoints of lines. This should be a snap to implement and it has been on my list for a while.

Finally, I will do a major update to the user documentation which will include a proof reading 🙂 .

After all that I will release the new version. I’m not sure whether I consider this alpha or beta. I’m going to have to give it some more consideration. It looks pretty likely that I will finish this all within the next two weeks so hopefully all goes according to plan 🙂 .

Spheriosity and Ant Build Files

August 18, 2008

While I was on vacation a few weeks ago I decided that I wanted all of the code in Spheriosity to look pretty inside an 80 character emacs buffer. I started out coding it in Eclipse (reluctantly) because it was the only way I could get the Java3D stuff to compile and I didn’t have time to play around with getting it to work command line. I planned to still use Eclipse even after the 80 character conversion, but alas the code does not like right in Eclipse anymore. So I decided to bite the bullet and start coding in emacs again.

This meant that I had to have a way to build the code from the command line so, naturally, I turned to ant since that seems to be the ‘Java way’ to compile projects larger than Hello World. I have very mixed feelings about Ant which is most of the reason for my post. The XML configuration does not do much for me. I don’t like the way XML config files (especially the way Ant does it) look. They all seem to be too syntax heavy for what they are trying to do. Prior to using Ant I had used make, which now that I have used Ant, I like even more than I did before. The simplicity of make is enough in itself to make (no pun intended) me want to use it. I want this project to be open source, and easy to build so I needed to use Ant. After messing around with things I was able to get Ant to do what I want well enough, but it seemed a lot harder than it needed to be. Maybe it is just because I am not used to it *shrugs*

Another thing about Ant which upset me is how long it takes to simply start running a target. I have had it take up to a second or two just to run a target that deletes the built source code. I could have typed in the remove command in that amount of time (with the aid of tab completion). This may sound like a trivial matter… a few second here or there, what’s the big deal? Well, when I am testing either the build script itself or parts of the code those few seconds for each recompile or clean or whatever start to take up a substantial amount of time.

Maybe I am judging it prematurely. Only time will tell. I will continue to use it and perhaps it will grow on me 🙂 .

Intersection of Spherical Circles (Finally!)

July 23, 2008

For the past two weeks I have been pondering on and off how I would calculate the location of the intersection of two spherical circles. I really want Spheriosity to be as complete as possible and having the intersection tool only work on Spherical lines/line segments seems like a real lame idea. So I have finally devised an algorithm which can correctly determine the intersection points. I will give a brief overview of it here. I will leave out details about different parts of the algorithm which I feel are either trivial or would need their own blog post to explain ;).

So we start with two circles… What are the possibilities for their arrangements in terms of intersections:

  1. The most simple is if the circles are not anywhere near each other and don’t intersect.
  2. One circle could be “inside” the other. In this case the circles obviously do not intersect.

    One circle inside the other

    One circle inside the other

  3. The two circles could intersect only in one spot. This could happen in a number of ways:
    • Case 1:

      First Intersection Case

      First Intersection Case

    • Case 2:

      Intersection Case 2

      Intersection Case 2

  4. Then there is the case where the circles intersect twice. This is perhaps the most common case in terms of what users will see, but since the other cases are easy to construct we must also deal with them.

So that loosely describes my problem and the different scenarios that need to be considered. So… on to the solution! Much of this boils down to finding the intersection of two planes. Each circle on the sphere defines it’s own plane which basically slices the sphere, and the intersection of that plane and the sphere could also be used to form the circle. So the intersection of the planes formed by both circles forms a line which, if it goes through the sphere, can be used to find our points of intersection.

Defining that line of intersection turned out to be the largest problem. It was easy enough to get a vector going in the correct direction but I still needed a point to form the line and perform any sort of calculation on it. Here are the steps I take to find the intersection and make sure one actually exists:

  1. Consider two circles AB and CD (defined by center point and radius point).
  2. Find the normal vector to the planes formed by each circle. We will call these vectors a and c
  3. Take a x c if the magnitude squared of the resulting vector is 0 you can stop now because the planes are parallel, and the circles could not possibly intersect (or are coincident).
  4. Form an axis of rotation, r, between points A and C.
  5. For both circles form lines by rotating their respective center points forward and back by the angle formed between their center points, the center of the sphere, and their radius points. (call these lines l and m.
  6. Find the intersection of lines l and m and call this point I
  7. Find the intersection of the line formed by using point I and the cross product of a and c with the sphere.
  8. Consider the following cases:
    • Case 1: Line does not intersect the sphere: no intersection points
    • Case 2: Line intersects once with the sphere: one intersection point
    • Case 3: Line intersects twice with the sphere: two intersection points

There you have it! I know I left some details out, but writing out every single step would make this a really long post ;).

Java3D, the PickRay, and the PickCylinderRay

July 14, 2008

Today I was struggling to figure out why I could not highlight a line segment in Spheriosity. After much fiddling around I discovered that the problem only occurred when I was using a PickRay to select objects instead of my normal PickCanvas. For those that don’t know a PickCanvas is made to pick objects based on the x and y coordinates of the cursor and a PickRay has to be defined with a starting point and vector indicating its direction. I was a bit disappointed because I thought I had already solved this problem. The general problem here is: ‘How do I take the cursor location and select something in a Java3D BranchGroup?’

My final solution to this problem was to use a PickCylinderRay, which defines an infinite cylinder going in a defined direction from a defined starting point and with a defined radius. Switching to the PickCylinderRay actually solved more than one of my problems. Previously when I was using the PickCanvas I found it very difficult to select objects at times. Especially the line segments (LineStripArrays) . I know that you can set different tolerances to the PickCanvas but I was having a heck of a time getting that happy. The only problem I ran in to with the PickCylinderRay was that if the radius was too large it would pick objects that weren’t even close to the cursor. However, this makes sense 🙂 Here is what the code looks like to define the vector from the camera to the cursor:

public void getCameraToMouseVec(Canvas3D myCanvas, Point clickPos,
                                Point3d cameraPoint, Vector3d dir)
     Point3d mousePos = new Point3d();

     //Getting current mouse and camera locations
     myCanvas.getPixelLocationInImagePlate(clickPos.x, clickPos.y, mousePos);

     //This block of code converts our image plate coordinates out to virtual world coordinates because
     //that's ultimately what we care about.
     Transform3D motion = new Transform3D();

     //We do this convertion for both the camera and for the mouse position.

     //Get the three components of the vector going from the camera location to the eye
     dir.x = (mousePos.x - cameraPoint.x);
     dir.y = (mousePos.y - cameraPoint.y);
     dir.z = (mousePos.z - cameraPoint.z);

So after this function completes the variables cameraPoint and dir will be set to the correct values to call .setShapeCylinderRay() of the PickTool class . Here is a sample of the code which takes the output of the previously displayed function and uses it to make a selection:

public void mousePressed(MouseEvent arg0) //Called be Java through MouseListener interface
     //In Spheriosity I actually declare these once for the class and reuse them
     Point3d tmpPoint = new Point3d();
     Vector3d tmpVec  = new Vector3d();

     //I assume that 'myMainBranchGroup' is a member of the class that this function is in
     //and is the BranchGrounp we want to be picking from.
     PickTool myPicker = new PickTool(myMainBranchGroup);

     //I also assume that 'myCanvas' is a member of this class
     getCameraToMouseVec(this.myCanvas, arg0.getPoint(), tmpPoint, tmpVec);

     //Use the data gathered from getCameraToMouseVec to make the PickCylinderRay
     myPicker.setShapeCylinderRay(tmpPoint, tmpVec, .1f);

     PickResult result = myPicker.pickClosest();

     ... code to handle what was selected ...

There you have it! That is how I solved my little problem with PickRays not working. I’m glad I stumbled upon the original problem because I truly think this solution works much better given the rest of the code base in Spheriosity.

There are a few things to note here. One is that the .1f in the .setShapeCylinderRay() function should be changed depending on your needs (it determines the radius of the cylinder). Lower values mean the cursor has to be closer to the object higher values mean the cursor can be further away. Also the output of the getCameraToMouseVec() function could also be used to define a PickRay if that is truly what you want.

Hopefully this was able to help one or two people trying to select things in Java3D. If not… well at least it serves as a bit of rationale for some of what I have done with Spheriosity 😀

Spheriosity and Efficiency

July 12, 2008

I spent some time today trying to add, what I think, would be a neat feature in Spheriosity. The feature would let you see the line or circle you are about to create when you are trying to make new lines and circles. Currently you just select the end points and then the program draws the line. With this feature, after you select the first point Spheriosity will show you were the line or circle will end up after you place the second point.

I figured this would be pretty simple and that I wouldn’t run into any of the efficiency issues I constantly worry about. Unfortunately I did… This took me completely by surprise because with the point moving feature everything seems to happen quite smoothly! So it was tough for me to believe that now this feature was slow.

I further inspected the code to find that the difference was in how point moving vs. how this feature was implemented. The way the code is currently structured is that all user related activities are fed through a state machine. The different states are like MovePointState , DrawPointState etc.. Each state extends a base class with 6 or 7 (can’t remember exact number) abstract functions. The class which receives all mouse related events then forwards the appropriate data to the functions of the current. Any given state can ignore functions it does not need by simply implementing them as an empty function block:

public void addPoint(Point3f newPt) {}

The function I currently use to get data from the mouse have the following function headers:

 * @param mouseEvent - MouseEvent sent by Java
 * @param worldLoc   - Pointer location mapped to the surface of the sphere
public void newMouseLoc(MouseEvent mouseEvent, Point3f worldLoc);

Java can give you the new location of the mouse in one of two different ways, but now both at once. By implementing the MouseMotionListener interface there are two functions. mouseDragged and mouseMoved. Even though the mouse is being moved while you are dragging in Java choose to implement it such that only one function or the other is called at once. So both mouseMoved and mouseDragged call my function [newMouseLoc]  . In mouseMoved I house the code which determines what lines or points get highlighted depending on the current state. In mouse dragged I simply pass right along the data to newMouseLoc.

So, the MovePointState gets the data from mouseDragged where the only overhead is the calculation I have to do in order to convert the mouse location to the surface of the sphere (quite a large calculation…) Where as in mouseMoved I did the same calculation as in mouseDragged and also did an intersection test with Java3D to see what, if anything, needed to be highlighted. Since part of that intersection test probably involved math that was already done to map the the user click to the sphere… Now… if this calculation was just happening once or twice I’m sure you would never notice. Unfortunately it happens every time the cursor moves. That in itself doesn’t make the the program lag though. Also added to the mix is that to draw each line we really make a bunch of small lines (100 to be exact) because a line on the sphere isn’t the same as the Euclidean version Java3D provides. So now we have that calculation coupled with the code that figures out the end points for the 100 lines and at the very least a for loop with 100 iterations … all each time the cursor moves!

This is why I worry about optimizing Spheriosity. I do my best to keep the code clean, but no one wants to use a slow program.

In terms of a solution to this problem… I moved some of the calculations around so I am doing less math to figure out what to highlight or not, and that seems to solve most of the issues. I still want to optimize it some more as I think I am approaching a dangerous threshold for minimum requirements 🙂 to run the program.

Spheriosty and Parallel Transport on the Sphere

July 11, 2008

Today I was writing some unit tests for Spheriosity and I discovered a flaw with the code that currently handles parallel transported lines. For those of you who are unfamiliar with the concept of parallel transport I will do my best at describing this to you.

Basically start with any two intersecting lines:

Two intersecting lines

Two intersecting lines

Now, slide the first line along the second keeping the angle between the two lines the same. You have just parallel transported your first line! By definition parallel transport merely keeps the angle between those two lines the same as they move.

Parallel transported line

Parallel transported line

Why is that so dang special? But wait! Isn’t that just a fancy way to say “keep the lines parallel”? Well, on the Euclidean plane, yes. However on a sphere there is no such thing as parallel. Two straight lines [known as great circles on a sphere] will always intersect. If you don’t believe me you can always try it out for yourself. Any true mathematician probably doesn’t believe me, as I have not provided a proof 🙂 .

Parallel transport of a great circle

Parallel transport of a great circle

Notice in the above picture that we have transported along the horizontal line. It is obvious that the original line (right line) and the transported line (left line) will intersect.

It is also interesting to note that on a sphere parallel transport is really the same as rotation! (Awesome… I know!) So where to rotate… well you can probably figure it out by simply looking at the sphere, but we want to try and put it in writing.  In order to find the axis to rotate on we have to imagine vectors going from the center of our sphere to the two end points that define our line of transport. Lets call those vectors a and b. Then, we take do: a x b (a cross b) and get some vector c. If we place vector c at the center of the sphere then we get our axis of rotation. Let call this primary axis just so we have name for it

So in the context of Spheriosity I want to take a line of transport, a line to transport and a cursor location and transport the ‘line to transport’ to where the cursor is, but making sure it is with respect to the ‘line of transport’. Translating the cursor location to a line parallel transporting is not a one step process, sadly. Since I don’t know where the cursor will be I had to find a way to map out the cursor location to the line being transported. [A big thanks to my professor who figured this one out]

  1. We use the point provided by the user and the axis of rotation for the line of transport to give us a new axis of rotation. Just to have some order here lets call the user point U, the first axis of rotation primary axis, the line of transport line AB, original line we are transporting line CD, and the new axis of rotation secondary axis
  2. Next we measure the angle between the primary axis and the vector defined from the center of the sphere to point C
  3. Now plot the point which is the intersection of the axis of rotation with the sphere. There are two poential points, so plot whichever one you wish. We will call this point E. Rotate point E with the secondary axis by the angle computed from step 2
  4. Now the first point is in place. We will call this point F. We measure the angle between the vectors defined by going from the center of the sphere to point F and point C.
  5. Using the angle from step 4 we rotate point D using the primary axis
  6. Enjoy the glory of seeing the line parallel transported

There are actually some problems with that method. The first of which is figuring out which direction to rotate point D. The .angle() function of the Vector3f class in Java3D only returns an angle from 0 to PI. The way I figure this out is actually by use of tangent vectors and dot products. To get the tangent vector I actually cheat and only approximate the angle vector by rotating the point C a very small amount (.0001 radians) with the primary axis and use the original point C and the rotated point C to make my vector (vector t). Yes, a crude trick, but it’s quick and easy. Next I define a vector from the center of the sphere to the point the cursor is at (vector c). I take the dot product of t and c,  and if the dot product is negative I know to take the angle from .angle() and rotate that in the opposite direction. Perhaps I will write a separate entry and how the dot product is my hero, but for now you will have to trust that it makes sense 🙂 .

The last issue, which I just discovered today, is that if the line we want to transport has one of it’s endpoints as the axis of rotation the aforementioned method does not work. So I simply special case this, and rotate the end point which isn’t the axis of rotation(point D) by the angle formed by the vectors made from the center of the sphere to the cursor point, and point D. Then I use the same tangent vector trick to figure out which way to rotate.

That’s all for now. Hopefully you at least understand parallel transport a little better :). Please let me know if some of that was unclear and I will do my best to make it sound better.