14 replies to this topic

[ChristerSwahn]

In my 3D logic I'm somewhat annoyed by the inefficiency and (mostly theoretical) risk of inconsistent values in representing 3D directions with 3-valued vectors as I am doing. (I write theoretical since the code is stable, but still.)

I'm probably not going to rewrite it but I'm intrigued by the problem, what is the optimal way to represent a direction in 3D, i.e. with as little space, redundancy and invalid value cases as possible, and if possible no normalization checks and renormalization operations needed?

(With direction I mean just the direction, i.e. not including position in space nor any roll (rotation around the direction vector itself). For instance a line (ray) can be represented by a point and a direction.)

An idea is to use a rotation in the x-y-plane (represented by a signed int A that is the nominator in the fraction A/PI, giving the interval [+- PI]), plus a half-circle rotation in z-space (represented by a signed int B in B/(PI/2), giving the interval [+- PI/2]). There are no invalid nor un-normalized values so that's good. But it's not fully optimal in terms of bit representation:
- the z-space-rotation has twice the angular precision of the x-y-rotation which is a little irregular,
- even more irregular is that the closer the direction gets to the Z axis the greater the angular precision,
- at the directions +Z and -Z, A has no meaning (all values of A are equally valid).

And using this representation in actual 3D code seems less than efficient. Every time it's used two divisions and floating point conversions seem to be required. And how would you efficiently apply an arbitrary rotation to it?

Your thoughts?

Edited by ChristerSwahn, 02 July 2012 - 03:43 AM.

[Radikalizm]

I believe you're worrying too much. In my eyes this is pretty much a non-issue

You're talking about this "theoretical" risk and inefficiency of using a 3-component vector for expressing direction, and I assume that you're talking about the precision-errors which floating point number representations can introduce. (correct me if I'm wrong)
This precision error however is so tiny that it is completed negligible when working with numbers in a sensible range, as is the case with normalized vectors. The cost for normalization is a reasonable price to pay, and normalization checks could be minimized by using principles from contract-based design where you make assumptions that your input is always of a desired form, and where it's the user's responsibility to provide correct input at all times (a normalized vector in this case)

When it comes to size in memory, invalid values and redundancy cases you'll always end up with scenarios where you'll trade out one beneficial property for another (as you've shown with your rotation approach), and it comes down to specific usage cases to determine which property gets the highest priority. A very simple example would be storing a normalized vector as 2 components and reconstructing the 3rd component later on, at the expense of having to do a more costly sqrt instruction to do so. This would be viable for example if memory usage is of higher importance to you than computational costs.

So in the end I see absolutely no harm in using plain old normalized vectors for representing a direction as they've proven their usefulness over and over. However, if you were to find an overall better way of representing direction I'd be very glad to hear it

[clb]

The problems with using normalized 3D vectors to represent direction are:
- takes 3xfloats when only two are needed.
- after manipulating the direction, the result can drift to be non-normalized.

A more optimal compact representation of directions that doesn't suffer from the above problems is to use spherical coordinates: https://github.com/juj/MathGeoLib/blob/master/src/Math/float3.h#L284 . These are a set of two scalars (azimuth, inclination) which are rotation angles that represent the direction. This is similar to using polar coordinates in the 2D case. This reduces the space restriction to 2xfloats, and there's no way to drift the values to produce invalid non-directions. Using spherical coordinates is very effective e.g. when streaming data through network, to minimize data requirements (e.g. kNet uses these).

The problems with spherical coordinates are
- you can't do arithmetic directly on them without converting them to vector form first. E.g. rotating a direction represented by spherical coordinates by a quaternion/matrix is convoluted.
- conversion between spherical<->euclidean is much slower than re-normalizing a direction vector.

Because you'd have to the costly conversion between spherical<->euclidean at every point where you do math on them, it's far easier and faster to just use normalized euclidean direction vectors, and re-normalize at key points to avoid drifting.

[ChristerSwahn]

It's not that I'm worrying, as I wrote I find it an intriguing problem. Call it academic interest! ;-)

Thanks for the input clb. But after some more thought it turns out that the redundancy and inconsistent angular precision of spherical coordinates is analogous to the problem of projecting a spherical surface on a plane (e.g. the world map). Spherical coordinates essentially project the sphere surface onto a rectangle (from [-PI,-PI/2] to [PI,PI/2]). The closer to the poles of the sphere the more compact/redundant the values get.

However if we project the sphere surface onto a circle this problem is avoided. And this can be represented using regular 2D polar coordinates. (To explain: Picture a circular world map (or elliptic, doesn't matter). Instead of longitude and latitude coordinates to represent a position (which is what 'spherical coordinates' do), use polar coordinates around the map center.)

It is still not perfect in that the angular precision is not uniform (its highest near the origin, lowest at the circle edge) but apart from that it appears optimal to me. Except for the duplicate values at the circle edge (half the circle edge represents the same directions as the other half), there are no redundant values and we have a 1:1 bijection between the representation value space and 3D direction space. And if using signed integers as in the original post there are no invalid values.

As you say this would not be practical to use in calculations but I think it might be useful as a stable way to represent directions in persistent storage or IO.

Edited by ChristerSwahn, 02 July 2012 - 06:49 AM.

[Álvaro]

The problem of mapping a sphere onto some flat shape has been studied in enormous depth because it's a central problem in cartography. I am not entirely sure what projection you are describing, but you should probably read this Wikipedia page to see what's out there.

[ChristerSwahn]

Yes but in contrast to cartography this problem is about a discrete geometric representation, and luckily the metric/fidelity and aesthetic requirements of cartographic projections can be ignored. Reading up on them my proposal seems to be a variation of azimuthal projection.

(Anyhow, by now I'm satisfied that achieving uniform precision seems to be impossible algebraically. ;-) )

[taby]

I'm totally lost here. Are you focusing on using the 2D Cartesian coordinates <x, y> primarily, when it comes to working on your disk? Are you using plain old azimuthal projection where you simply suppress the height (ie. http://www.mathworks...2.html#f11-8415 ), or are you doing something manually to make sure that the latitude density doesn't increase toward the equator (ie. http://en.wikipedia....tant_projection)? If you're using plain old azimuthal projection, then you're simply swapping the "precision waste" along theta at the poles for "precision waste" along phi at the equator, right?

I wonder if it's useful to think about why Regge calculus totally abandons orthogonal coordinate systems for a relational triangulation.

Edited by taby, 02 July 2012 - 03:37 PM.

[ChristerSwahn]

My idea in the first post was essentially spherical coordinates, which as a pure value space can be thought of as two-dimensional vector (rectangle from [-PI,-PI/2] to [PI,PI/2]). A better solution but not perfect one seems to be to use the azimuthal projection variation I described.

In this (academic) exercise what I was striving for was essentially a bit representation of a 3D-direction with no redundancies, no invalid nor un-normalized values and if possible uniform precision.

[taby]

Right, no, I was confused and still am. Are you using something like http://en.wikipedia....area_projection ? What I mean to say is... you're looking for an equal area projection, right? Is that the point of this? What projection did you use? I'm asking because it's interesting to me, and I'll probably play around with it too.

I understand where you're coming from when you noted that a variable is effectively wasted when Cartesian coordinates are used to describe positions on the unit sphere, and I understand where you're coming from when you noted that the coordinate singularity in spherical coordinates cause non-uniform precision along the latitudes in terms of near the poles vs near the equator.

I ran into something pretty similar recently, whereby if I had taken the singularities as real concrete things, then I would have been moving (in terms of a constant angle per step, dtheta) much slower at the poles than at the equator. I didn't take the singularities to be real concrete things though, and I didn't measure angles along just latitudes and longitudes (I measured my angles along great circles, of arbitrary orientation). It didn't really get rid of the "precision waste", but it did get rid of some problems.

Edited by taby, 02 July 2012 - 04:02 PM.

[ChristerSwahn]

Nice that I'm not the only one that finds such problems exciting! ;-)

It was the Equidistant Azumuthal Projection I was considering (your second link). After some more thought on it, yes you're perfectly right! While it is possible to construct the projection so that there are no redundancies except at two poles, swapping one projection for the other will probably only move the dense and sparse precision areas around. Orthogonal coordinate systems will probably always produce varying angular precision over a curved surface.

I started thinking about it another way. Since we're looking for a discrete geometric representation of points on a unit sphere surface, preferably with uniform distribution, why not state the problem as a discrete maths problem: for a given number N of representation bits, find an enumeration of 2^N points on the unit sphere surface that are as equidistant as possible, and for which the translation to and from the the bit representation can be done algorithmically (worst case) or algebraically (best case).

This problem seems to be a special case of Spherical Code: http://en.wikipedia.org/wiki/Spherical_code
Such as Spherical Covering: http://neilsloane.com/coverings/index.html

Another approach could be the Circle Packing problem: http://mathworld.wolfram.com/CirclePacking.html

It still seems there is no algebraic (i.e. non-iterative) solution however. :-/

(3D applications' renditions of spheres could also be interesting to look into - how do they map spheres to polygons?)

[Hodgman]

Optimal representation of [...]?

The generic answer, where [...] is any kind of data at all is: it depends on what kind of transformations you need to do on that data.

The usual suspects for direction are: 3D vectors, 4D vectors, Euler-angles/spherical coordinates and quaternions... but each is better for different tasks. Furthermore, each of these can be in Structure-of-Arrays or Array-of-Structures layouts, and again, each is better for different tasks.
So -- there's no answer without knowing what kind of tasks you're performing using these directions

From your first post, it sounds like your task is to compress them into the most efficient storage format? If so, you could just run your regular normalized XYZ vectors though ZLIB (p.s. sorry for the tongue-in-cheek post)

Edited by Hodgman, 03 July 2012 - 03:43 AM.

[ChristerSwahn]

From your first post, it sounds like your task is to compress them into the most efficient storage format? If so, you could just run your regular normalized XYZ vectors though ZLIB (p.s. sorry for the tongue-in-cheek post)

No it's rather about optimal value representation. (An analogous discussion would be: Are floats an optimal or close-to-optimal representation of Real values given an N bit word to store it in?)

But computability would be nice, which the approach I found in the last post appears not to be. The best approach that's still practical still seems to be the

Equidistant Azumuthal Projection.

[Hodgman]

Are floats an optimal or close-to-optimal representation of Real values given an N bit word to store it in?

Which Real values? If I take the real number line between 1.0 and 2.0 and evenly distribute 16 million points on it, then a 24-bit integer would map them simply and accurately, but a 32-bit float will quantize them down to about 8 million discrete points...
However, if I use the values between 0.0 and 1.0, then the float can map about a billion (non-uniformly distributed) discrete points, so it depends on the data

But computability would be nice

Which computations though? E.g. If I've got 1000 pairs of directions, which I want to process into 1000 average directions (i.e. the direction half-way between the two paired inputs), then if the directions are stored as vectors, I can simply add and renormalize and get the correct result (except in cases where there is no defined result, such as two opposite directions), which is so efficient in terms of processing that the program will be bottlenecked on RAM access speeds.
To contrast, if the directions were stored in an Equidistant Azumuthal Projection, then simply averaging those values doesn't give the correct result like it did with vectors, so it's less optimal for this particular transform.

However, seeing that the simple vector version should be bottlenecked by the cache/RAM rather than the CPU, you might want to investigate a data format with less bits (like your projection) and see if you can perform the conversion to vector "for free" (i.e. if the extra CPU time doing the conversions is less than the cache-miss times, in which case you can perform those computations for no increase to the total running time). At this point though, we're stepping out of academic theory-land, and onto real-world hardware that requires an empirical approach to finding the optimal solution via profiling.

Edited by Hodgman, 03 July 2012 - 06:58 AM.

[ChristerSwahn]

Hodgman - all fair points, if you're looking for an optimal representation for a given specific kind of computation.

[Álvaro]

Talking about optimal representations can only be done if one fully defines the criterion for optimality; and, whatever it is, you will probably get an optimal representation that suffers in some other aspect. I think it's more interesting to talk about useful representations, instead.

There is a useful representation that is used all the time in Computer Graphics: cube mapping. If you have 32 bits to represent a diretion in 3D, you can think of the sphere as having an inscribed cube. Divide each face in 26754x26754 little squares and identify a direction with the little square it falls in. 26754*26754*6 = 4294659096, which means you are using more than 99.99% of the possible bit combinations. Conversion back and forth is pretty straight forward and the variation in resolution at different parts of the sphere is tolerable.

Edited by alvaro, 03 July 2012 - 09:35 AM.