An image contest announcement

Featured

The course is over, the presentations are over (well except for one) and the grades have been assigned … but there’s still one more thing for the Mathematical Visualization WS 2013 participants before I close up this blog.

The Problem has to do with  conform!, the movie on conformal maps which I’m in the process of finishing up.  There’s a section involving an inflated letter “A” where I need your help to produce a better texture image.  This “A” is a topological torus and as such can be unrolled conformally onto the euclidean plane.  Like most of the texture maps in the movie, to begin with this one is based on a checkerboard.  And that works for the first half of the section.  But once we’ve found the conformal structure (which is a rectangle with aspect ratio almost exactly 17:14), it’s time for a new texture image, since the end of the section tessellates the rectangle to cover the whole euclidean plane.  That’s too many little black and white squares when the checkerboard image is used, as I think the following image makes clear:

InflatedAAndTessellationChbd

In an effort to create a better texture I naturally thought of the MVWS13 student project Escher Painter from Sophia Lee and Martin Swiontek Brzezinski which is designed to deal with just this situation.  I first convinced Martin to add a feature to allow the fundamental domain to be rectangular not just square (Thanks, Martin!) and I then gave the dimensions 17 x 14, as mentioned above.  I worked some more and produced the following image, based on an Escher print of interlocked fish/bird  (group O)  included in the Handbook of Regular Patterns , p. 176, by Peter Stevens — a resource I used a lot during the course.  I admit it’s not very professional but I think the end result is still more pleasing than the checkerboard hell above.

letterATexture-martin-03

which tessellates as follows.   Well, actually I used 2×2 copies to cover the “A”, since otherwise it’s too hard to identify what one sees on the surface of the “A”.escherA-tessellation-01

 

The Contest. The idea now is to get you involved to produce something better for this purpose.  Here’s how to proceed:

  1. Use Escher Painter, referenced above.   Martin, the developer,  has declared himself prepared to answer your questions if you do want to participate in the contest.
  2. Enter the aspect ratio of 17 x 14 in the number fields provided.
  3. Begin with the default group O.  But you can also choose groups which are compatible with O — which in this case means there are no rotation centers of order 3 or higher, and preferably no mirrors.  When you save the image (see below) you’ll need to save a translational unit, which may involve more than one fundamental domain.
  4. Choose paint mode. Experiment with the painting tool, combining the size and the transparency for lots of different effects. Notice also the cool “undo” and “redo” buttons. I recommend using a strong dark outline for your forms.  My first attempt above doesn’t have strong enough outlines, I think.
  5. Also note that if you have to stop and restart, you can save the state of your painting using the “Save project” button at the top of the panel and restore it with the “Load project” button.
  6. When you are satisfied with the result, save the image.
    1. Use the camera zoom tool so that one translational unit fills as much of the graphics window as possible.
    2. I found the best way to be not to use the “File->export->image” option in jReality, but on my Mac I used the Grab application, chose to grab the selection, and then very carefully drag a rectangle from the upper left corner of one translation cell to the lower right corner (the pixels at these corners should be identical parts of the pattern.) if you don’t have access to such a tool, use “File->Export->Image…” and … sigh … I’ll have to extract the translational unit myself.
    3. Email me the result.
  7. Optionally, save the “project” file using the “Save project” button and email me the result.  I’ll handle saving the image.
  8. I’m not aware of any copyright issues involved in producing images in this way which resemble original Escher images.  Does anyone know better?
  9. The contest deadline is Monday July 14 at 12 pm.  The winning image (subject to approval by the movie team) will be used in the movie for the end of this section, and the winner will be credited in the movie credits.

 

11-13.02 Final week: GA, project presentations, …

Featured

May 1, 2014:  I’m finally getting the projects available as webstarts on the homepage for the course. Please let me know if you encounter problems running them.

Breaking news: Those of you who attended the last few weeks of lectures know that one of my hobby-horses is geometric algebra, projective GA to be exact.  As part of my missionary work I’ve worked up a proposal for a tutorial on the subject at an upcoming international conference.  You can see it here.  Feedback on content and appearance welcome.

This is the last week of classes!  It will be a little different than usual, since two group projects will be presented, one on Tuesday and on on Thursday, both at 10:15.   From 11:00 Mr. Gunn will continue lecturing on geometric algebra and will also make some final remarks on technical details of project completion. The projects being presented are:

  • Tuesday: “Packing circles on a cylinder” by Michael Gubik and Nick Bremer
  • Thursday: “The Shadow Problem for 2-Surfaces” by Tatiana Grandon

 Details of project completion.  Before doing anything else, review the project guidelines given here.  They are from last year’s course, but they continue to apply to this year’s projects. In order to simplify the publication of the projects (via Java webstart technology), I need your help.  First, make sure you have organized your source code correctly  (see point 3 below). Furthermore,  to generate an entry in the course website where the project is pictured and described, I need to get two small files from each team.   I have added some files to the teacher’s git repository in order to streamline this process, see points 4+ below. As you complete your project, but no later than the first week of April, please make sure you have carried out the following directions.  If you finish early, please let me know! Then I can check that everything works and if not, give you a chance to correct things.  It will be much more difficult to effect the grading process if the project is only ready on the day of the presentation! Thanks in advance for your cooperation!

  1. Note: In this discussion, when you are asked to create files or packages involving the string “nnmm“, it should be replaced with the two 2-digit student numbers for the team members, for example “1723″ or “0208″.
  2. Update to the teacher’s git repository.  Your project must run using the latest teacher’s repository code! If you are having problems updating to this repository (as wingthor does), there is now an alternative as follows:
    1.  Instead of having you work directly with the source classes for the template package(s), I’ve made a jar file named mv13-template.jar and checked it in with the other jar files in the lib folder of the repository.
    2. There are two ways to access this jar file. The first is preferred since it allows you to check for updates more easily.
      1. In eclipse: In the git repository browser,  fetch the teacher’s repository (it should be listed under “Remotes“).  Back in package explorer, select the project and look at the history view. You should see near the top of the list an entry for the teacher’s repository you just fetched.  Look for a recent commit for the teacher’s repository with the comment “Add jar file for the template package”, or “Update jar file for the template package.”  Use right mouse (context menu) and select “Cherry pick”, this should just bring over the desired jar file to the lib folder.
      2. If you want to get this jar file directly without using eclipse or git, use this link.  Download the file and copy it into the lib folder of your git project.
    3. Once the jar file is in the lib folder of your project, add it to your classpath in Eclipse (using Project properties->Java build path->Libraries).
      1. Then, either delete the template package (and all subpackages) in the Package Explorer, or configure the build path (in the tab labeled “Order and Export”) so that mv13-template.jar comes before the src folder of the project.
    4. If this approach works for you, you can delete the template package completely from your git project, and push the result to your remote repository, so that I only fetch the code you have written and not the template stuff.
    5. To view the source code of the classes in the jar remember:
      1. In Package Explorer, navigate to “Referenced Libraries”.
      2. Find “mv13-template.jar” and open it via the little triangle to its left side.
      3. The classes you see can be opened and looked at (though not written) in the same way as .java files can.
  3. Setup your package structure as follows — please follow these directions!
    1. Make sure that your project application is a subclass of template.Assignment. This is important to guarantee that the webstarts function correctly. Furthermore, if there are problems in the Assignment class, your application will be fixed when I fix this class.
    2. Make sure that all the code that you have written that is needed to run your application is contained in a single Java package, named reasonable something like studentnnmm.project. (You are allowed to have subpackages in this package.) This is important, since I’ll create a jar file for your webstart from this  package/folder.
    3. Your on-line documentation: should be a html file in the same folder as your project, whose name includes the string “nnmm” – otherwise there may be name collisions when I collect these html files into one place.  Please try to include nnmm in all filenames which are associated to your on-line documentation.
      1. If your html file does not load any other local files, it can be left in the same directory as the .java class.
      2. If however it refers to other local files (such as a screen shot of your project), then please create a subfolder named html in your project folder and put all the html-related files into this folder.  Then I know which files I have to collect! Remember to change the return value for the getDocumentationFile() to reflect this change.
      3. Example, if you have a doc file named doc007.html and it refers to a screenshot ss007.png, put both into a folder named html and change getDocumentationFile() to return “html/doc007.html“.
    4. If you use extra jar files in your project, be sure you check them into your repository (you can put them into the lib folder) and that they are included in the .classpath in your repository.  (This will be the case if you have your eclipse build path set up to include this jar.)  I’ll have to identify these jars and copy them to the webstart site.
  4. Run your application and create a representative image (256 x 192) of your application.  Use the “File->Export->Image…” menu item to do this.
    • In the file dialog you will probably need to unclick the constrained shape icon to allow these two dimensions to be entered separately from each other.  Save the image with the name projectPic-nnmm.png in the project folder you created above.
  5. Copy the file projectDesc.txt from template.project to your own project folder (created above) and edit it as follows:
    1. Replace the string “nnmm” by your student numbers where it occurs.
    2. Replace the string “Twirly objects based on spherical point groups” with the title of your project.
    3. Change the descriptive paragraph at the end to be a description of your project with approximately the same number of characters/words.
    4. Notice there is also a commented-out text for your presentation slides.  If you want your presentation slides to be available on the course web-site, please email them to me and I will activate this link in the documentation.
  6. Presentation slides can also be checked into your git repository.  If I find a file named studentsnnmmSlides.pdf then I will stash it away and link it to the project documentation on the website, so that visitors can also look at the slides of your presentation. (Again “nnmm” should be replaced by your 2-digit student numbers.)
  7. Commit the new files you’ve created and then push to your remote git repository.
  8. Send me an email to notify me that you’ve completed this phase.
  9. When I next fetch from your respository, I’ll receive the small image and the html fragment. I will generate a jar file from your project package and collect these in a single place where I can then invoke them to run the jar files as webstarts. I will use the image and text to construct the list of student projects for the web-site. I’ll construct a jnlp file to start your application as a webstart. There is currently one example on the course web-site here, you can consult it to see what I need all these pieces for.
  10. Deadline: Teams presenting in April are expected to have this all done by 24 hours after your presentation.  Please understand that I cannot complete the grading process until the above directions have been satisfactorily completed.  I’m going on vacation on Friday April 11 and I want to leave my desk “clean” when I go!

04-06.14 More geometric algebra

Featured

Note: the April project presentations have been shifted to run from Monday, April 7 to Wednesday, April 9.  (No one had signed up for Thursday and there was interest in Monday.)

If you’re wondering what I’m expecting in the project, take a look (again) at EvaluationFormMVWS13 based on last year’s projects.

On Tuesday February 4 Mr. Gunn continued to develop the geometric algebra he began the previous week.  In particular he focused on sandwich operators in the geometric algebra of $\mathbb{R}^3$.  He reviewed the sandwiches with a 1-vector as bread, and showed they are rotations of 180 degrees around the vector.  (These are called half-turns in English or Umwendungen in German).  He then looked into the product of two unit 1-vectors $\mathbf{u}$ and $\mathbf{v}$, which gives rise to a sandwich, rotating around the common perpendicular of $\mathbf{u}$ and $\mathbf{v}$, through twice the angle separating the vectors. Such an element is called a rotor, and has the form \[\cos{\frac{\alpha}{2}} + \sin{\frac{\alpha}{2}} \mathbf{U} \] where $\mathbf{U} := \dfrac{\mathbf{u} \wedge \mathbf{v}}{\sin{\frac{\alpha}{2}}}$ is the normalized form of the plane spanned by the 1-vectors.  There is again an exponential form for such rotors: \[\cos{\frac{\alpha}{2}} + \sin{\frac{\alpha}{2}} \mathbf{U} =e^{\frac{\alpha}{2}\mathbf{U}}\]

Mr. Gunn then gave an overview of the steps remaining to obtain the geometric algebra of the Euclidean plane $\mathbf{E}^2$ from the geometric algebra of the euclidean vector space $\mathbb{R}^3$:

  1. Replace the standard exterior algebra based on the join operator $\vee$ with the dual exterior algebra based on the meet operator $\wedge$.
  2. Projectivize the vector space structure of the exterior algebra to obtain an exterior algebra describing the subspace structure of projective space $P(\mathbb{R}^3)$ instead of the vector space $\mathbb{R}^3$.
  3. Replace the standard inner product $+++$ with the “slightly” degenerate inner product $++0$.

Notationally: instead of the Clifford algebra $Cl(\mathbb{R}_{3,0,0})$ we need the Clifford algebra $P(Cl(\mathbb{R}^*_{2,0,1}))$.  Here, the triple $(3,0,0)$ represents an inner product with signature +++ while $(2,1,0)$ represents one with signature $++-$ and $(2,0,1)$ represents signature $++0$.  The latter is important for the euclidean plane.  To motivate this fact Mr. Gunn turned to a  a speedy review of the geometry of lines in the plane.

Review of lines in the plane. A line whose equation is $ax+by+c=0$ is represented by the vector $\mathbf{v} := [a,b,c]$ or any positive multiple.  The oppositely oriented line is obtained by $-\mathbf{v}$ or any negative multiple. The normal vector to the line is the vector $(-b, a)$. I can normalize  line equations so that $a^2+b^2=1$ (except the  triple $(0,0,c)$ which represents the ideal line of the euclidean plane). For two such normalized euclidean lines, it’s then easy to see that $\mathbf{u} \cdot \mathbf{v} := a_u a_v + b_u b_v$ is the cosine of the angle between the two lines. Notice that this inner product does not involve the $c-$ coordinate.  It’s signature is $(2,0,1)$.  The important point is that the angle between two lines is totally determined by this inner product, even though it is “degenerate”.

Course Log

Featured

This post contains a running “table of contents” of the lectures and tutorial meetings of the course. Also at the top I will post any urgent messages which you need to be aware of.  Note: The entries in this log are in reverse order (latest first) to make it easier to keep up to date, so you don’t have to scroll to the end to see the latest entry.

ATTENTION: There is now a Doodle for the project presentations which will be held April 8-10 before lectures start for the summer semester.  Please register for a date.

11-13.01 Final week, project presentations …

04-06.01 More Geometric algebra …

28-30.01 Geometric algebra introduction …

21-23.01 Napier’s laws, project progress …

14-16.01  Spherical trigonometry, Shape of Space …

7-9.01  Project description

17-19.12  Magic Theorems and more …

10-12.12  Still more Symmetry Groups.

3-5.12  Wallpaper Groups and More …

26-28.11 More Symmetries and Groups, Assignment5 …

19-21.11 Symmetries and Groups, Assignment4 …

12-14.11 Geometry factories, Assignment3 …

5-7.11 jReality scene graph, Assignment2, …

29.10 Tutorial: Using gitorious, Part II

26.10 Assignment1: Cubic Choreography

22-24.10 Matrices and Motions

17.10 Tutorial: Using gitorious, Part I

17.10 To Infinity and Back: Introducing Projective Geometry

15.10  Tutorial: Getting started with the tools.

15.10 Apps, Animations, Artifacts … : An Overview of Mathematical Visualization

 

 

Introduction to projective geometric algebra, III

[Question to my readers: is there a way to get a compact enumeration in this blog?  If I write a list using the list menu item in the wordpress editor, the entries are    v e r y    f a r     a p a r t.

This post picks up where the last one left off.  Our task here is to present the essentials of projective geometric algebra and use to obtain a metric-neutral formulation of the solution to the problem discussed in the previous two posts.

Projective space to the rescue. To obtain the projective models of the metric planes of interest, begin with the  vector space $\mathbb{R^3}$ and projectivize it to produce the real projective plane $\mathbf{P}^2$.  Define an exterior algebra $\bigwedge{\mathbf{P}^2}$ by defining the points of $\mathbf{P}^2$ to be the 1-vectors.  Take the scalar field $\mathbb{R}$ as the 0-vectors.  Create the higher grades using the anti-symmetric wedge product $\wedge$.  $\mathbf{x} \wedge \mathbf{y}$ is a 2-vector,  the joining line of the arguments. The wedge of three linearly independent points $\mathbf{x} \wedge \mathbf{y} \wedge \mathbf{z}$ is the projective plane itself, and is called a pseudo-scalar.

Duality to the rescue. We can do the same with the dual algebra.  Then the 1-vectors are lines and the wedge operation is the meet of two lines. By a little bit of abstract nonsense, we can in fact restrict our attention to one of these algebras and "import" the other wedge product when we need it (by using Poincare duality, the details are in my thesis).  For our purposes we write the join operator as $\vee$ and the meet operator as $\wedge$ (note this choice is motivated to be consistent with the related set-theoretic operations union $\cup$ and intersection $\cap$). For a good intro to exterior algebras see this wikipedia article.

Adding a metric. To work in the metric relations, we have to incorporate the inner product with this outer product.  To do so we define three different signatures for our inner product: (+++), (++-), and (++0), which corresponds to elliptic, hyperbolic and euclidean plane, resp.  Write the inner product of two 1-vectors with respect to the chosen inner product as $\mathbf{m}\cdot \mathbf{n}$.  We begin with the dual exterior algebra (where 1-vectors are lines) and define a geometric product on the 1-vectors via: \[  \mathbf{m}\mathbf{n} := \mathbf{m}\cdot \mathbf{n} + \mathbf{m}\wedge \mathbf{n}\]  Note that this product is the sum of a 0-vector (a scalar) and a 2-vector. This product can be extended to all grades just by writing every k-vector as a sum of products of orthogonal basis 1-vectors (which is always possible), and reducing the products whenever the square of a basis 1-vector occurs (since the square of a 1-vector is a scalar).  In this way one obtains an associative algebra, called the Clifford or geometric algebra, characterized by its signature.  This is the projective geometric algebra we have been promising to describe.  We denote the three algebras of interest as $\mathcal{C}_\kappa$ where $\kappa$ takes on the three values of $\{-1,0,1\}$ (hyperbolic, euclidean, elliptic, resp.) To be precise, we work with an orthonormal basis for the  1-vectors $\{\mathbf{e_0}, \mathbf{e_1},\mathbf{e_2}\}$ with the metric relations given by $ \mathbf{e_0}^2 = \kappa$, $ \mathbf{e_1}^2= \mathbf{e_2}^2 = 1$.

Why (++0) is euclidean: In $\mathbb{R}^2$, consider two  lines $m_{1} : a_{1}x+b_{1}y+c_{1}=0$ and $m_{2} : a_{2}x+b_{2}y+c_{2}=0$.  Assuming WLOG $a_{i}^{2}+b_{i}^{2} = 1$, then $\cos{\alpha} = a_{1}a_{2}+b_{1}b_{2}$, where $\alpha$ is the angle between the two lines: changing the $c$ coefficient translates the line but does not change the angle it makes to other lines. That means, the $c$ coefficient makes no difference when we measure the angle between two lines.  Thus $(++0)$ is the correct choice for the inner product for euclidean planar geometry.

Why we have to use the dual algebra: If you’re wondering why we started with the dual exterior algebra, that answer is: because that’s how God make the world we live in.  Euclidean lines are less degenerate than euclidean points.  If you try to start with the standard exterior algebra (where 1-vectors are points) you cannot obtain euclidean geometry; you end up with dual euclidean geometry, in which points are less degenerate than lines, which does not at all match up with the space we live in.  (It’s a fascinating space in its own right and I hope to post something on it in the near future.)

Normalizing. It’s useful to work with normalized points and lines.  To obtain this normalization, notice that $\mathbf{m}^2$ for a 1-vector or 2-vector is a scalar. Define the norm $\|\mathbf{m}\| := \sqrt{| \mathbf{m}^2 |}$.  Then when $\| \mathbf{m} \| \neq 0$, $\dfrac{\mathbf{m}}{\| \mathbf{m}^2 \|}$ has unit norm.  For the three metric geometries we are working with, the proper points and lines always can be normalized to have square -1 and +1, resp. (In  fact, that can serve as a definition of what it means to be proper.)

Implementing the construction. Here are the steps of the construction, translated into $\mathcal{C}_\kappa$.   The elements in the above diagram have been embedded in the natural way into the Clifford algebra as 1- or 2-vectors. We assume that all points and lines are normalized in the formulas which follow, since it simplifies the formulas.  (Normalizing ideal points is a tricky issue which we skip over in this abbreviated account.  See my thesis.)  For example, this allows us the find midpoints and angle bisectors by simply adding together the two arguments.  In the formulas below, $\mathbf{X}$ is an arbitrary point or line.  $\mathbf{R_x}$ is the geometric reflection in the line $\mathbf{x}$. $\mathbf{R_C}$ is the desired rotation around the point $\mathbf{C}$. The exceptional configurations have not been taken into account in this description.

$\begin{align} \mathbf{M} &:= \mathbf{m} \wedge \mathbf{m’} &&\text{Intersection of the two lines}  \\ \mathbf{a} &:= \mathbf{A} \vee \mathbf{A’} &&\text{joining line of the two points} \\ \mathbf{A_m} &:= \mathbf{A} + \mathbf{A’} && \text{midpoint of the two points} \\ \mathbf{r} &:= \mathbf{A_m} \mathbf{a} &&\text{perpendicular bisector of AA’} \\ \mathbf{c} &:= \mathbf{m} + \mathbf{m’} &&\text{angle bisector of the two lines} \\ \mathbf{C} &:= \mathbf{r} \wedge \mathbf{c} && \text{center of rotation} \\ \mathbf{s} &:= \mathbf{A} \vee \mathbf{C} && \text{one reflection line} \\  \mathbf{R_s}(\mathbf{X}) &:= \mathbf{s} \mathbf{X} \mathbf{s} &&\text{reflection in line} \mathbf{~s} \\ \mathbf{R_C} &:= \mathbf{c} (\mathbf{s} \mathbf{X} \mathbf{s}) \mathbf{c} &&\text{desired rotation: product of two reflections}    \end{align}$

References: my thesisa euclidean extract

Exercise.  Express the exceptional configurations described in the previous post, in terms of the geometric algebra description above.

Remarks on isometries as rotors instead of matrices.  I’d like to close this post by discussing the representation of isometries in the context of PGA (projective geometric algebra).  Note from the above formulae that a reflection in a proper line can be written as a “sandwich operator” with the line as the “bread” (appearing on left and right) and the object to be reflected as the meat (in the middle).  This should be familiar to readers who know about the representation of quaternions as sandwich operations. Concatenating an even number of such reflections leads to direct isometries, as the expression for the rotation $\mathbf{R_C}$ above also shows.

Terminology. A product of 1-vectors is called a versor; a product of proper 1-vectors is a proper versor.  A proper versor is then an isometry of the geometry, and any such isometry may be written as a versor.  A product of an even number of 1-vectors is called an even versor; every direct isometry represents a direct isometry, and (with a few exceptions) vice-versa.   An even versor is also called a rotor, due to the obvious connection to rotational motion.  The set of proper rotors, normalized to have norm 1, forms a group, the spin group of the algebra, written Spin.  The full set of proper versors also forms a group, the pin group, written Pin.

Notation. In order to express the sandwich operation with a k-versor succinctly, we write the versor as $\mathbf{g} := \mathbf{m}_1 \mathbf{m}_2 … \mathbf{m}_k$, where each $\mathbf{m}_i$ is a 1-vector.  Then the sandwich operation can be written as $\mathbf{g} \mathbf{X} \widetilde{\mathbf{g}}$ where $\widetilde{\mathbf{g}} = \mathbf{m}_k … \mathbf{m}_2 \mathbf{m}_1$ is the reversal of $\mathbf{g}$ and is obtained by reversing the order of the products in the definition of the element.

Advantages of this approach. The existence of a versor representation for isometries in the metric space (or plane, as here), means that one no longer needs to rely on linear algebra for this representation. No more matrices!  Seriously, the advantages of the versor approach are worth pointing out. We restrict our attention to the two dimensional case we have been discussing to make things easy to understand; but the observant reader can easily extrapolate to higher dimensions.  In the first place, the representation is grade-independent, meaning the meat of the sandwich can be any grade; the result of the sandwich operation will represent the isometry applied to the meat.  Compare this to linear algebra, where the transformation matrix for an isometry applied to a point is not the same as that applied to a plane (one is the adjoint of the other).  A further advantage of the versor formulation is that the the isometry can be read off from its versor representation.  For example,  for a 1-versor, the isometry is the reflection in the line which the versor represents.  For a rotor, the isometry is a rotation whose center is given by the grade-2 part of the versor, through an angle equal to $2\arccos(s)$ where $s$ is the grade-0 part (scalar) of the rotor. (We are assuming the rotor has been normalized to have unit norm).  If you have ever tried to read off from a 3×3 matrix the center and angle of a rotation, you’ll appreciate how convenient this second advantage is.

The final advantage of the versor representation is that every rotor has an exponential representation (just as a unit quaternion does).  Since $\mathbf{P}^2=-1$ for a proper point $\mathbf{P}$, the expression $e^{t\mathbf{P}}$ can be evaluated just as if $\mathbf{P}$ were the complex unit $i$, and one obtains $\cos{t} + \sin{t}\mathbf{P}$ as the result.  In fact, when you activate the time slider of the webstart associated to this post (see this post),  the interpolated isometry is calculated using the exponential representation of the motion described here (although of course when it comes to drawing the rotated line, it has to be converted into a matrix and shipped over to the graphics card, which is still living in the old world of vectors and matrices.)

The following figure shows 20 equal steps in the interpolation of the isometry obtained in this way.  The interpolated lines are are drawn as transparent objects to reduce the clutter in the image. You can see that the envelope of the moving line is a circle.

isometryWithCAEucInterp-01

If you’re still with me, I hope that you have gotten a taste of how projective geometric algebra can be a powerful, practical, and elegant tool for doing geometry in a metric-neutral way.

Introduction to projective geometric algebra, II

This post builds on the previous one, but returns to the original problem of finding the axis of a hyperbolic isometry.  We show that by using the projective model of hyperbolic geometry one can directly adapt the euclidean solution to obtain the hyperbolic solution also.

The hyperbolic case. The webstart, as explained above, also includes an option to switch the metric to elliptic or hyperbolic We want now to discuss the latter option.  Then the figure includes the unit circle, the boundary of the hyperbolic plane, as the following figure shows:

isometryWithCAhypSm-01

Does the description of the euclidean construction carry over to the hyperbolic case pictured above?  Clearly there are some constraints on the configuration if there is to be a solution.  For example, the points $\mathbf{A}$ and $\mathbf{A’}$ must be hyperbolic points, and the lines $\mathbf{m}$ and $\mathbf{m’}$ must also be hyperbolic.  But their intersection $\mathbf{M}$ does not need to be hyperbolic; it can be ideal (lie on the unit circle) or also hyper-ideal (lie outside).  Assuming these conditions are met, as they are in the above figure, how does the construction proceed?

The definition of the perpendicular bisector $\mathbf{r}$ is valid.  But what is the angle bisector $\mathbf{c}$ of an angle which, as in this case,  lies outside the hyperbolic disk?  As in the euclidean case, the traditional approach to hyperbolic geometry does not define this.  However, in the projective model one can define it meaningfully.  To do so, one must invoke an involutive correlation $\mathbf{\Pi}$ (a fancy name for a transformation which switches points and lines,  and whose square is the identity) on the projective plane known as the polarity on the metric quadric.  This transformation sends a point $\mathbf{P}$ to the line $\mathbf{P^\perp}$ consisting  of points whose inner product with $\mathbf{P}$ is 0, the orthogonal complement with respect to the hyperbolic metric.

The result is that one obtains a second model of the hyperbolic plane in the exterior of the unit disk, in which the roles of point and line have been reversed.  Then, for example, the point $\mathbf{M}$ when it lies outside the hyperbolic plane, is polar  to the common orthogonal line of $\mathbf{m}$ and $\mathbf{m’}$ inside the hyperbolic disk, and the angle bisector of these two lines is polar to the midpoint of this common orthogonal segment.  Proceeding in this way, one can show that the desired metric properties can be “mirrored” from the exterior of the hyperbolic plane to the interior and hence that the construction given above also solves the given problem for the hyperbolic plane too, although some of the steps may look unfamiliar, since they may involve polar entities, but the metric relations remain unchanged.  A full discussion of this phenomena lies beyond the scope of this post, but hopefully you can get a sense of how the polarity operator in effect produces two hyperbolic planes such that every metric relationship in one is mirrored (with points and lines reversed) in the other.

We leave the same positive conclusion for the elliptic plane for the never-tiring reader.  Here the situation is simplified since there are no real ideal points, every point of the projective plane is also a point of the elliptic plane and any configuration of the initial data is valid, and the construction carried out in the euclidean case goes through here without difficulties.

Having shown that the projective model of these three metric planes provides a reliable basis for solving the construction problem posed in the first post, and doing so in a metric-neutral way, the next post will provide the promised introduction to projective geometric algebra, by giving a (metric-neutral) algebraic formulation of the construction which has formed the content of this and the previous post.

Introduction to projective geometric algebra, I

At a student seminar at the TU Berlin in fall 2013, the following problem in plane geometry  was posed, “Given a point lying on a line, and a second point lying on a second line, find the unique direct isometry mapping the first point/line pair to the second.”  The original context was the hyperbolic plane, in thinking about the problem I realized I could solve it in a metric-neutral way, and this blog post and its sequels present that solution. I chose the title since the solution is based on an nifty tool called projective geometric algebra (PGA), and I can’t think of a better introduction to PGA than working out a concrete example like this one.  Buckle your seat belts and enjoy the ride!

What I want to do in this post:

  1. Demonstrate an interactive application for playing with this problem.
  2. Derive a solution for the problem in the euclidean plane.
  3. Discuss some exceptional configurations and show how they can be handled within the context of the projective model of euclidean geometry in a seamless fashion.
  4. Indicate how the approach leads to a “cool tool”: projective geometric algebra, a subject for a future post.

I’ve also implemented this result in a jReality webstart application.  If you start this application up, you should see a picture like the following:

isometryWithCAeuc-01

Directions for using the webstart. To begin with, you may need to display the control panel to the left of the graphics window. To do this, select the menu item “Window->Left slot” (and deselect “Window->right slot” if you wish).  This is necessary due to a heightened security in Java 7 which prevents correct reading of the built-in property file (which should set these window slots properly.)

If you’re using the webstart application, you can drag any of the three points $\mathbf{A}$, $\mathbf{A’}$ and $\mathbf{M}$ and the diagram adjusts accordingly.  Use the slider labeled time to see how the rotation acts, also to confirm that the rotation actually does what is claimed. Furthermore, to reverse the orientation of either line $\mathbf{m}$ or $\mathbf{m’}$, click on the line; the orientation arrow on the line should flip and the angle bisector $\mathbf{c}$ switches accordingly to the supplementary angle.  Finally, you can switch the metric used using the combo box on the left inspector panel to choose the hyperbolic or elliptic metric also.  The given data remains the same, but the construction is carried out using this metric instead of the euclidean one.  This “metric neutral” capability will be more fully discussed in a later blog.

Return to the geometric problem. Here we want to focus on the challenge of finding a euclidean isometry which moves the point $\mathbf{A}$ to the point $\mathbf{A’}$, and the line $\mathbf{m}$ to the line $\mathbf{m’}$.  (The two lines should be thought of as oriented, so that the orientation is preserved by the isometry.) We claim that the solution is a rotation around point $\mathbf{C}$,  the intersection of line  $\mathbf{r}$ (cyan) and line $\mathbf{c}$ (green). $\mathbf{r}$ is the perpendicular bisector of the segment $\mathbf{AA’}$, while $\mathbf{c}$ is the angle bisector of the angle formed by $\mathbf{m}$ and $\mathbf{m’}$.

Indeed, the center $\mathbf{C}$ of a rotation moving $\mathbf{A}$ to  $\mathbf{A’}$ must lie the same distance to both points, which is the defining condition of $\mathbf{r}$.  Similarly, since the desired rotation maps $\mathbf{m}$ to $\mathbf{m’}$,  the closest point of $\mathbf{m}$ to $\mathbf{C}$ is mapped to the closest point of $\mathbf{m’}$ to $\mathbf{C}$, hence $\mathbf{C}$ lies the same distance to both points.  This condition is satisfied exactly by points on the angle bisector $\mathbf{c}$ of the two lines. (Here one must be careful to specify which angle bisector one means. This depends on the relative orientation of the two lines, and is easy to determine.) Hence the center of the desired rotation must lie on $\mathbf{r}$ and on $\mathbf{c}$, so it is the intersection of these two lines, as shown in the diagram.

Once the center has been found, it´s not hard to express the desired rotation as the composition of two reflections in lines passing through $\mathbf{C}$: first in the line $\mathbf{s}$ (red) followed by reflection in line $\mathbf{r}$ (cyan).  Why does this produce the desired rotation? Clearly reflection in $\mathbf{s}$ fixes $\mathbf{A}$ while that in $\mathbf{c}$ maps $\mathbf{A}$ to $\mathbf{A’}$.  Since $\mathbf{C}$ is fixed by the composition, it must be the rotation we are looking for.  Writing the reflection in line $\mathbf{s}$ as $\mathbf{R_s}$, the rotation is then the composition $\mathbf{R_C} := \mathbf{R_c}\circ \mathbf{R_s}$.

Exceptional configurations. It’s interesting to review the construction for possible exceptional configurations.  For example, $\mathbf{m}$ and $\mathbf{m’}$ may be parallel; then their intersection $\mathbf{M}$ is a so-called point at infinity or, more neutrally,  ideal point.  What is the angle bisector $\mathbf{c}$ in this case?  If the two lines have different orientations (that is, translate one to the other and compare the orientations), then the angle bisector $\mathbf{c}$ is the mid-line, parallel to both, and the construction continues as before.  If not, then $\mathbf{c}$ is the line at infinity itself (!), and the construction continues as before.

Or, $\mathbf{c}$ and $\mathbf{r}$ may be parallel; then their intersection $\mathbf{C}$ is a so-called point at infinity or ideal point, and $\mathbf{s}$, since it goes through $\mathbf{C}$ too, is also parallel to these lines.  Hence the product of the two reflections is not a rotation but a translation.  A bit poetically, one can say, a euclidean translation is a rotation around a point at infinity — by a vanishing angle!

A further exceptional configuration can occur if the lines $\mathbf{r}$ and $\mathbf{c}$ are the same line.  Then they don’t have a well-defined intersection.  It’s not hard to see that this can happen only when $\mathbf{A}$ and $\mathbf{A’}$ lie the same distance from $\mathbf{M}$, so I can rotate $\mathbf{A}$ into $\mathbf{A’}$ by a rotation around $\mathbf{M}$.  Now, if the  orientations of $\mathbf{m}$ and $\mathbf{m’}$ are preserved when I perform this rotation, then it is the desired rotation, and I can construct it by setting $\mathbf{C}$ to $\mathbf{M}$ and continuing as before; if not, the desired rotation center is found by constructing the perpendicular line $\mathbf{a}$ to $\mathbf{m}$ at $\mathbf{A}$; then the intersection of $\mathbf{a}$ and $\mathbf{c}$ is the desired rotation center $\mathbf{C}$ and the construction can continue as before.

Are there other exceptional configurations?  Please post as comment any other ones you find!

The path to geometric algebra. The observant reader will not have missed noting that the correct solution of the exceptional configurations described above proceeded a bit magically.  In particular, finding the correct solution for the first two configurations involved the ideal points and line of the euclidean plane.  These are concepts which are not necessarily associated to euclidean geometry.  That they can be used is due to the discovery by Arthur Cayley and Felix Klein in the 1860′s that projective space can be converted into a metric space in many ways by selecting a quadratic form, the so-called Absolute of the metric space.  Details lie outside the scope of this blog, see my thesis, chapter 4. This Cayley-Klein construction can be directly applied when the quadratic form is non-degenerate, and produces most importantly elliptic (or spherical) and hyperbolic space of any dimension.  It also works for euclidean space, but requires a degenerate quadratic form (some subspaces consist of points with vanishing norm).

For this post, the relevant object is the projective model of the euclidean plane.  Then the points of vanishing norm form a line, the so-called ideal line of the euclidean plane. Parallel lines meet in points of this line. This circumstance allowed us to handle the first two exceptional configurations above, where we sought the intersection of two parallel lines. In almost every euclidean construction or proof there arise such configurations, which have to be handled separately if one is relying of “traditional” euclidean geometry, but which in the context of “projective” euclidean geometry can be handled uniformly. For this reason, the projective model of euclidean geometry has clear advantages over the traditional approach.  In order to carry this out in a rigorous fashion, its useful to translate things into in the correct algebraic setting.

The traditional way of proving that the construction outlined above is correct relies on converting the steps into expressions in vector analysis of the plane.  This approach avoids mention of ideal points and line, and is limited to the euclidean setting.  Is there a better algebraic tool for the job?  In fact, there is a much more comprehensive algebraic structure — which includes vector analysis as a small sub-algebra — such that every step of the above construction can be expressed by a single compact expression. Furthermore, even though the steps of the construction are made based on the euclidean metric, the resulting expressions also provide a correct representation of the same construction when the underlying metric is elliptic or hyperbolic. The differences that arise express naturally the differences between these metrics.  For example, in elliptic space there are no parallel lines. This “metric neutrality” is an expression of  the Cayley-Klein construction underlying this approach. The webstart application allows the user to use these other metrics and confirm that the result is, in fact, metric neutral.

The same comments made regarding the projective model of the euclidean plane apply also to the hyperbolic plane.  Instead of having just one line of ideal elements, in the hyperbolic case there are a circle’s worth of ideal points and lines, and beyond them a second model of hyperbolic geometry, the polar hyperbolic plane, described briefly above. They are not part of the traditional definition of the hyperbolic plane, but can be integrated in an effortless way into the standard model of the hyperbolic plane with the advantage that all projective elements have a significance in hyperbolic geometry, not just the points of the unit disk.  This geometry can also be integrated into the algebraic structure mentioned above.

This algebraic structure is called projective geometric algebra.  I’ll share the details of this algebraic “translation” of our construction problem here in a subsequent post on this blog.

28-30.01.14 Geometric algebra

Here’s a link to a gallery of projects which relate mathematics and art.

On Tuesday January 28 Mr. Gunn continued his discussion of the geometric algebra of $\mathbb{R}^2$.  He showed that reflections and rotations can be written as sandwich operators.  For example, reflection of the vector $\mathbf{u}$ in the vector $\mathbf{v}$ can be written $\mathbf{v}\mathbf{u}\mathbf{v}$. This is a sandwich, whose bread is $\mathbf{v}$ and whose meat is $\mathbf{u}$. By concatenating two reflections one obtains another sandwich operator for a rotation around the origin by an angle $\alpha$.

To obtain this rotation formula, define $\mathbf{R} := \mathbf{v}_2 \mathbf{v}_1$ be the geometric product of two unit vectors which meet at an angle of $\dfrac{\alpha}{2}$, CCW from $\mathbf{v}_1$ to $\mathbf{v}_2$. Then we showed in the previous lecture that $\mathbf{R} = \cos{\dfrac{\alpha}{2}} + \sin{\dfrac{\alpha}{2}}\mathbf{I}$.  (Recall that $\mathbf{I} = \mathbf{e}_1 \mathbf{e}_2$ is the pseudoscalar of the algebra).   Recall  that the concatenation of two reflections is a rotation around the meeting point of the lines, through twice the angle between the lines. Then the desired rotation can be written as the concatenation of reflections in these two vectors: $\mathbf{v}_2(\mathbf{v}_1 \mathbf{u} \mathbf{v}_1)\mathbf{v}_2$.  Since the geometric product is associative we can reparenthesize to obtain $(\mathbf{v}_2 \mathbf{v}_1 ) \mathbf{u} (\mathbf{v}_1\mathbf{v}_2)$.  Finally,  let $\mathbf{\widetilde{R}} = \mathbf{v}_1 \mathbf{v}_2$ denote the reversal of $\mathbf{R}$, the element obtained by reversing the order of all geometric products in $\mathbf{R}$.   Then the formula for the rotation reads \mathbf{R}\mathbf{u}\mathbf{\widetilde{R}}$.  The element $\mathbf{R}$ is called a rotor.

21-23.01 Napier’s laws, project progress

On Tuesday 21.01 Mr. Gunn continued his discussion of spherical trigonometry with an overview of Napier’s laws (which arise when an angle or side is a right angle).  He then showed the mathematical animation Not Knot, which builds on the ideas of the video Shape of Space to delve into the hyperbolic structure on a knot complement.  This led to a mention of Scott Kim, who designed the logo for the video.  You can find lots more of his nifty calligraphic inversions on his web site.

On Thursday 23.01 Mr. Gunn complained about two forms of new technology used by the Deutsche Bahn.  He then discussed the evaluation forms he collected on Thursday.  This led him to share memories of another evaluation several decades ago when he first taught a college course; the results were convinced him to give up teaching and seek a programming job.  These memories led him — through the magic of free association — to recount his encounters with two basketball legends, Michael Jordan and Earl “the Pearl” Monroe.  He managed to pull himself out of Memory Lane, however, and spent the rest of the hour presenting an introduction to geometric algebra which he hopes to work up into a short script.

14-16.01 Spherical trigonometry, the shape of space, …

Attention: There is now a Doodle for the project presentations which will be held April 8-10 before lectures start for the summer semester.  Please register for a date.

Snow math art:  Check out this series of photos in the Süddeutsche Zeitung. For example: snowart

Coming up next week:  The course evaluation forms are available.  You can fill them out during the lecture next week either on Tuesday or Thursday, I’ll provide time at the end of the lecture for this purpose.

Tuesday 14.01: I continued the derivation of spherical trigonometry begun last week in connection with the presentation on the Schatz linkage.  The motivation was to be able to solve for the various angles which appear in the motion of this linkage.  The approach I took can also be found in these lecture notes for Geometrie I from Boris Springborn, in particular, pages 5 and 6.

Thursday 16.01: We had the pleasure of hearing a lecture from Jeff Weeks, who is visiting the math department this week.  Jeff talked about “The Shape of Space” and demonstrated his entertaining and educational topology software, which can be found here.

7-9.01.2014 Assignment6: Project description

Today in class I presented a project which I have been working on, on and off, for several years.  It is a visualization of the Schatz linkage.  You can access the webstart I showed here. The video I showed at the beginning of the class can be seen here. The pictures of the wooden oloid which Thomas Neukirchner made can be found here. Thomas’s diagrams and plywood models of the oloid can be found here.  The latest edition of Paul Schatz’s book Die Welt ist Umstülpbar: Rhythmusforschung und Technik can be found here on Amazon.  If you are interested in this theme then mark your calender for April 4-6, when there will be a weekend event in Berlin devoted to themes related to Paul Schatz’s research.  A few more details can be found here.

On Thursday, Jan. 9, we will take some time to evaluate this “project presentation” in regard to the various criteria mentioned in the evaluation handout.  Be there or be square!  I will also discuss the half-edge data structure and demonstrate some advanced features of the discretegroup package, and, if time permits, more!

Assignment 6: As discussed in class on our final meeting before the holidays, the next assignment is not a programming assignment but rather a planning assignment.  I ask you to enter a description of your project as a comment to this blog post.  Use the account name studentmv with the clever password.  Please  sign your comment with either your name(s) or with your student number(s).  Your comments are due as usual on Friday at midnight.  (That’s Friday Jan. 10).   The details of the description are provided below, but first comes a “news flash” regarding a change in the way property files are handled in the basic template.Assignment class.

Improved way to provide property files. Although I didn’t do much work over the holiday break, I did play around some with webstarts — enough to realize that the current way that property files are handled doesn’t work with webstart technology.  So I’ve figured out a new way to handle property files that does work with webstarts, and has other advantages.  Here’s how it works:

  • If you have a class named MyAssignment.java that inherits from template.Assignment, then store off the properties in a file named myAssignment.xml (note the leading lower case letter!) in the same folder as MyAssignment.java. Implement the method getPropertiesFile() to return null.  Or, remove your implementation of the method, it’s no longer an abstract method and by default it returns null.
  • That’s all you have to do.  Now your class should read the property file correctly whether run “normally” or as a webstart application (which your project application will ultimately need to do).
  • Please try this out to make sure it works for you — if you don’t change anything the old code will continue to work but you should get used to using the new approach.

What to include in your description. 

  1. Mathematics. The description should begin with the mathematical content of the project.  Try to be as precise and accurate.  Zoom in gently — make clear to which domain of mathematics this content belongs.  Use technical language if necessary to specify this.  If possible, include one or two references (either articles or books) which provide a more detailed description of the context of your project.  None of the projects exists “in a vacuum”, give a pointer to your point(s) of departure.
  2. Software design. Begin this section by a statement describing the concrete goal of your project.  For example, “We intend to create an application to allow the user to explore the 3-dimensional kaleidoscopes introduced above [in the mathematical section].”  Describe then the software tools and building blocks you think you will need in order to realize this aim, and how they will be put together.  For example, building blocks might include “jReality geometry factories, the de.jtem.halfedge package, and the de.jtem.discretegroup package”; additionally indicate which parts of these building blocks you will use and how they will be combined.  Think if this as the blueprint for your project.  Of course at this stage of the planning it shouldn’t be too detailed.
  3. User experience. Finally, briefly indicate how you envision a typical “usage cycle” of your program.  What choices does the user have, how can he/she interact with the software sketched in the previous section?  Can the user save the state of the program from one invocation to the next? Will you rely on sliders and dials, or have you ideas for innovative interactive tools?  Will your application be particularly aimed at the PORTAL? Will there be a connection to 3D printing?