Note: this problem has now been solved using the inverse transpose (see the last section below); this page is still here just for historical reference.

The problem

We've chosen to represent bounding regions for diagrams in a functional style. A bounding region for a vector space V with scalar type S is a function h : V -> S such that h(v)v is the shortest vector in the direction of v whose perpendicular hyperplane completely contains the region.

For example, to represent a circular region of radius 2, we use h(v) = 2/|v|, since multiplying any vector v by 2/|v| gives a vector in the direction of v of length 2, which brings us to the edge of the circle.

The problem is how to transform h along with a diagram when applying some sort of transformation. It is not hard to transform h when applying a transformation T which preserves angles. Then we have (Th)(v) = h(T^-1^ v). However, this does not work for transformations which do not preserve angles (such as shears and non-uniform scalings).

(Illustration of the problem goes here.)

Options

As discussed in this thread:

Buckle down and work really hard and figure out how to do it. Pros: this would be awesome. Cons: we don't even know if it's possible.
Only allow angle-preserving transformations. Pros: this option is simplest. Cons: might be too restrictive.
Switch to a different representation of bounding regions that will integrate better with general transformations. Pros: ability to do general transformations. Cons: probably a lot of work, and the current representation seems so elegant and functional, it would be a shame to give it up.

For the moment, at least, the consensus seems to be that we should keep pushing on (1).

Explorations and possible solutions

Other representations of bounding regions

There is another possibility for representing bounding regions functionally. Instead of giving the distance to the nearest enclosing hyperplane (h), we could give the distance (again as a multiple of the length of the input vector) to the boundary itself. Call this function e : V -> S. For circles, h(v) = e(v), but it should be clear that they are not the same for more complicated shapes. It seems that e(v) should be much simpler to transform than h(v). e(v) and h(v) are also dual in a sense: we have

 e(v) = min,,v' in V,, { (h(v')v').v / (v.v) }

or something like that (basically, the minimum over all other vectors of the projection of h onto v), whereas h(v) can be defined in exactly the same way in terms of e(v) but using max instead of min. Unfortunately this doesn't seem very practical from a computational point of view.

Transforming hyperplanes

If we restrict ourselves to transformations that preserve parallel lines (which includes all affine transformations but not projective transformations in general) then we may proceed as follows to compute (Th)(v):

Compute some appropriate representation of the hyperplane containing the endpoint of v and perpendicular to v, call it H.
Compute T^-1^(H), call it H'. The important point is that due to our insistence that T preserves parallelism, any hyperplane parallel to H' is sent by T to a hyperplane parallel to H.
Find v' perpendicular to, with its endpoint contained in, H', and compute s = h(v').
Compute T(v') and scale s according to (a) how much T shrinks or expands v' and (b) by projecting T(v') back onto v.

The above ought to be worked out in a bit more detail but this is the basic idea. I think this will work as long as we are willing to restrict ourselves to affine transformations, which is probably just fine. This is based on an idea of Ryan Yates.

The outstanding issues seem to be:

How to compute step (1)? What is an appropriate representation of a hyperplane in general?
Work out the details of step (4). Does it really work?

For step (1), perhaps see Gram-Schmidt process, and also this exchange from the #haskell IRC channel on 30 Sep 2010:

18:18:27 <byorgey> given a vector v in an inner product space, how might I go about computing a basis for the hyperplane orthogonal to v?
18:18:45 <Veinor> ask #math? :D
18:19:02 --- join: dnolen (~davidnole@cpe-68-173-254-181.nyc.res.rr.com) joined #haskell
18:19:09 * byorgey shudders
18:19:11 <ddarius> byorgey: for all basis vectors b, keep b if b ^ v /= 0
18:20:00 --- join: c_wraith (~c_wraith@209.237.247.90) joined #haskell
18:20:01 <byorgey> ddarius: ^ is inner product?
18:20:10 <Cale> byorgey: Well, pick random vectors and subtract off the orthogonal projection onto the subspace spanned by v
18:20:11 <benmachine> isn't ^ usually used for cross product
18:20:11 <ddarius> byorgey: Wedge product.
18:20:13 <benmachine> or is that v
18:20:24 * benmachine always just used, you know, cross
18:20:30 <ddarius> Of course, the dual of v will be a blade that represents the hyperplane orthogonal to it already...
18:20:50 <aristid> so google found IOSpec for me http://www.cse.chalmers.se/~wouter/repos/IOSpec/index.html
18:20:53 <ddarius> b ^ v = b . dual(v)
18:21:08 <byorgey> ddarius: where can I read about this?
18:21:28 <Veinor> byorgey: for each basis vector b, compute b - proj_v b
18:21:36 <byorgey> can I apply affine transformations to such duals?
18:21:47 <Veinor> (I don't know anything about vector spaces besides R^n)
18:22:42 <ddarius> http://geocalc.clas.asu.edu/  (mathematical/physics), http://www.mrao.cam.ac.uk/~clifford/ (physics), http://www.science.uva.nl/ga/ (computer science)
18:22:47 <ddarius> byorgey: ^
18:23:36 <benmachine> haskell-src-exts' fixity resolution is super-brokwn
18:23:39 <benmachine> *broken
18:23:45 <benmachine> well, fairly broken anyway
18:24:12 <ddarius> byorgey: I recommend starting here: http://geocalc.clas.asu.edu/html/Intro.html and here: http://www.science.uva.nl/ga/publications/index.html
18:25:14 <ddarius> byorgey: This deceptively named paper is rather useful a bit later on: http://www.science.uva.nl/ga/publications/content_publications.html#leo_inner

Inverse transpose

See this page. Is it really that simple? Note we can carry along the inverse transpose in the same way that we currently carry along the inverse, so we don't have to resort to extracting matrix representations.

See also Subject 5.27 in http://www.faqs.org/faqs/graphics/algorithms-faq/ .

Diagrams/Dev/Bounds

Contents