[diagrams] inverse transpose, and distinguishing points and vectors

Brent Yorgey byorgey at seas.upenn.edu
Tue Nov 23 10:39:51 EST 2010

Hi all,

I just pushed a bunch of big patches so I thought I'd write a quick
email to explain what I did (and record it for posterity).  Note that
a bunch of the tests are now quite broken, but at least it all
compiles, and I'm 90% sure the bugs are minor. ;-) (And I'll be
working on fixing them ASAP.)

The first change is that bounding region transformations are now
computed much more simply using the inverse transpose -- it turns out
that when transforming a space by an affine transformation T, normal
(perpendicular) vectors transform as the inverse transpose of T.  I
think Ryan linked to a web page to this effect a while ago, but I
finally understand why + how it applies.  To accomplish this,
transformations now carry along a little 2x2 matrix of *four* linear
maps -- the transformation, its inverse, its transpose, and its
inverse transpose.  Taking the inverse or transpose of a
transformation just corresponds to flipping the matrix
appropriately. =)

While making this change I stumbled across another big problem -- we
were not properly distinguishing between *points* (which should be
affected by translations) and *vectors* (which should not!).  So I

  (1) switched back to representing transformations as a linear map +
      a translation, instead of as projective transformations.  We
      are only able to support affine transformations anyway, AND this
      representation makes it a lot easier to selectively apply or
      ignore the translational component depending on whether we are
      transforming points or vectors.

  (2) Added a new type

    newtype Point v = P v

      which represents points in the vector space v, and went through
      applying this type appropriately.  It's a bit annoying at first
      to have to distinguish like this, but the added mental clarity
      is worth it. =)

Unfortunately, (1) means that the Ellipse module is now broken (sorry,
Scott!) since it depended on the internals of how we were representing
transformations.  However, I'm not sure but I think it may be simpler
to implement now that the transpose is available -- I think part of
what it was doing before was manually computing the transpose.  Scott,
if you have any time to fix it, feel free, but otherwise I can also
probably spend some time staring at it and figure out how to fix it.


More information about the diagrams mailing list