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?
Optimal representation of direction in 3D?
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
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
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.
- 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.
Author
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.
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.
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.
Author
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. ;-) )
(Anyhow, by now I'm satisfied that achieving uniform precision seems to be impossible algebraically. ;-) )
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.
I wonder if it's useful to think about why Regge calculus totally abandons orthogonal coordinate systems for a relational triangulation.
Author
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.
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.
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.
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.
Author
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?)
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?)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
