Coordinate Systems and 3D Computer Graphics
Contents |
Intro
Coordinate systems are important in computer graphics. Various coordinate systems are developed using ideas from mathematics, in particular, complex analysis and Partial Differential equations.
One use for these coordinate systems is to build a cage around a complex object, and then move the cage. The goal is to have the resulting object (usually an animated figure) move inside the cage correctly.
Coordinate systems in order of complexity are
- Barycentric Coordinates
- Mean Value Coordinates
- Harmonic Coordinates
- Green Coordinates
Mean Value and Harmonic Coordinates
Mean Value coordinates are simple, but have some flaws in regions where the object is not convex.
Harmonic Coordinates correct this problem. The method is topologically flexible, and is local (effects of motion far away have little effect).
Harmonic coordinates have been used in differential geometry for a long time
The Mean Value coordinates appear to be designed to so that the mapping is a special kind of harmonic coordinates, isothermal coordinates,
See the pixar demo
The paper with details can be found at
See also
Green Coordinates
Link to an interesting article which uses Green Coordinates to transform 3D graphics.
http://www.math.tau.ac.il/~lipmanya/GC/gc.htm http://www.math.tau.ac.il/~lipmanya/GC/gc_techrep.pdf
The advantage of Green coordinates over Harmonic coordinates, is that the normal information is also used. This means that the deformation is more likely to preserve angles, which is important to minimize distortion. Here the goal is to have a mapping which is locally a rotation (or a rotation with a pure scaling), as opposed to a mapping which scales by a large factor in one direction, compared to a small factor in the other. (The local distortion of a linear map is the ratio of the smallest and largest scale factors).
In two dimensions, the mapping is conformal (and a proof is available). This means there is no distortion. In three dimensions, computational results show the distortion is small, but it's an open problem to prove this. The proof would require different techniques from the two dimensional case, since the mapping is not harmonic.
Math ideas in the paper
The main math ideas in the paper can be found on pages 1 and 4. Previous work used the idea of deforming a cage (a box) and moving the points inside to the new cage. This means defining coordinates inside the cage using affine sums of the cage vertices.
The problem with this mapping is that shape is not preserved: the angles between two coordinate lines can change.
It is a well-known mathematical fact that conformal mappings preserve angles. Translating this idea into a way of changing coordinates is explained on page 4 of the paper. (By the way, this idea has been used many times before, in different contexts). The trick is to use Green's third identity. Instead of just using it on one harmonic function, it's used on a few: the special functions x,y,z, i.e. the linear coordinate functions, in the case where the cage is a rectangle. More generally, the affine functions which line up with the cage.
The special thing about this functions is that the outward normal is constant on each face, so one of the terms in Green's third identity becomes a constant.
The paper goes on to derive new coordinate functions in this way.
Discussion
Barycentric coordinates: Coordinates based on a triangle.
Mean value coordinates: Coordinates based on straight line distance.
Harmonic coordinates: are based on solving Laplace's equation. The harmonic coordinates use only vertex information. Then when the vertices are moves, the new coordinate system moves with them.
Green Coordinates also solve Laplace's equation, but the equation uses the normals as well as the vertices. Then, when the vertices move, the new coordinates also use normal information. The result is a new coordinate system which maintains angles. (So this is a conformal mapping).
The 3d graphics people don't discuss conformal mappings. The main reason seems to be that their domains (cages) are polyhedral, so the resulting formulas are discrete sums over edges and (in the case of Green coordinates) normals.
However, a link could be made by specializing formulas for Riemann maps onto polyhedral surfaces.
The main interest in these maps is the generalization to 3D. Here the maps are not conformal, but quasi-conformal. This means some small distortion is introduced, but usually this is not visible for graphics applications.