Polyhedrons, many many polyhedrons...

[knighty]

Sorry for being late. Busy at work.

I saw no reason to do otherwise, as you do.

It's true that the method you use is more elegant but the one I use is not as complicated as it looks. It's main advantage is that it is straightforward to generalize to higher dimensions. It's not obvious to me how to generalize the method using spherical trigonometry identities.

For instance the polyhedron with U=V=W=1 is repreoduced below using these data.

It is not an uniform polyhedron. It is still possible to make it uniform by using other values for U,V and W but they will not be the same.

I rendered them in Mathematica 2.0, 20 years ago. I calculated the intersections of the face planes of the cuboctahedron, with one such a plane. The regions you get, you can use by rotating them according to the symmetry group of the cuboc. If anyone find them useful I can pull out the coordinates of the vertices. The same for the 59 icosahedron stellations.

That would be nice.

[JosLeys]

To Knighty:
It's not obvious to me either to do spherical trigonometry on the 3-sphere, so I'm still wondering how you put it together in 4D.
As far as I can see you took 4 hyperplanes that form the fundamental domain (also known as the Goursat tetrahedron): a, b, nc and nd being their normals.
You took a to be <1,0,0,0> and b=<0,1,0,0>.
The angles between the planes give 5 equations for 6 unknowns, but one component of a vector can be chosen freely.
As far as I can see you took the angles between planes to be:
a-b: pi/2, a-c: pi/5, a-d: pi/2, b-c: pi/3, b-d: pi/3, c-d:pi/2.

...and I'm puzzled at why this should be so! I have a hard time visualizing what the angles between the 4D hyperplanes should be!

Anyway, choosing the fourth coordinate of nd to be zero, I arrive at your expressions for nc and nd.

The points on the sphere can be derived from the cross products in four dimensions, which requires three vectors.

What I do not understand is why your four points, pabc, pbdc etc. stem from the cross products abc, bdc, cda, dba and not something else like acb, cdb or dcb..the choice is endless!!

[puntopunto]

In case someone needs them

The coordinates of the vertices of all Johnson solids. In the document: name of the polyhedron,vertices,face indices

http://www.stitchstitch.info/m3d/JohnsonSolids.docx

[knighty]

Hi!
Thank you very much puntopunto.

To Knighty:
It's not obvious to me either to do spherical trigonometry on the 3-sphere, so I'm still wondering how you put it together in 4D.
As far as I can see you took 4 hyperplanes that form the fundamental domain (also known as the Goursat tetrahedron): a, b, nc and nd being their normals.
You took a to be <1,0,0,0> and b=<0,1,0,0>.
The angles between the planes give 5 equations for 6 unknowns, but one component of a vector can be chosen freely.
As far as I can see you took the angles between planes to be:
a-b: pi/2, a-c: pi/5, a-d: pi/2, b-c: pi/3, b-d: pi/3, c-d:pi/2.

...and I'm puzzled at why this should be so! I have a hard time visualizing what the angles between the 4D hyperplanes should be!

Anyway, choosing the fourth coordinate of nd to be zero, I arrive at your expressions for nc and nd.

The angle between two hyperplanes is given by the normals to thos e hyperplane. It's 2D whatever the dimension of the hyperplane is. the two normal vectors define a 2D plane (obviousely this plane is perpendicular to the hyperplanes and in our case it goes through the origin) which intersection with the two hyperplanes gives two lines. The angle between these two lines is exactly the angle between the two hyperplanes.

The general method I use is as follow:
- I require the hyperplanes to have normals pointing inside the fundamental domain. having 4 hyperplanes, they divide the 4D space into 2^4=16 sectors. Only one sector is such that the normal vectors to the hyperplanes all point inside the sector.
- A consequance of the first requirement is that the half lines of the fundamental domain are on the positive side of the opposit hyperplane.
- I also require that the positive part of the w axis be the intersection of hyperplanes a,b and c. It will be on the positive side of the hyperplane d.
- because the angles between our hyperplanes are always <=PI/2, the fundamental domain is small enough to fit inside the first 1/16 sector where all coordinates are positive . (this is the same as the first octant in 3D or the first quadrant in 2D). That is why i take the (componenet wise) absolute value of the vector product to get the vertices. That way I haven't to worry about the order of the vectors as they appear in the vector product.

Let the planes a:(a0,a1,a2,a3); b:(b0,b1,b2,b3); c:(c0,c1,c2,c3) and d:(d0,d1,d2,d3) be the normal vectors to the hyperplanes. We have a total of 16 unknowns. There are 6 angles (that are deduced from the coxeter diagram including those that are equal to pi/2). Those angles give 6 linear equations (such that a.b=-cos(angle(a,b))). We also want the normal vectors to be noralized which give a set of 4 nonlinear equations. We will need a mean to fix the 6 remaining degrees of freedom (which correspond to the set of orthonormal matrices in 4D). The simplest method I could think of is to set some of the components to 0 like this:
a:(a0,0,0,0); b:(b0,b1,0,0); c:(c0,c1,c2,0) and d:(d0,d1,d2,d3).
Then solve the system of equations.
Because of the 4 nonlinear equations, one have to be careful abou the signs in order to keep the fundamental plane inside the first 1/16 sector. In the case of polychora: a0=1; b0<=0; b1>0; c0,c1<=0; c2>0; d0,d1,d2<=0 and d3>0. (in the hyperbolic case one can verify that d3 must be <0 also).

In practice and in order to simplify the calculation (made by hand) I always group the perpendicular hyperplanes to be processed first. for example, if there is a angle of pi/2 I choose it to be the angle between a and b so their components will be (1,0,0,0) and (0,1,0,0). And so on... a-c then b-c then a-d ...etc.

The points on the sphere can be derived from the cross products in four dimensions, which requires three vectors.

What I do not understand is why your four points, pabc, pbdc etc. stem from the cross products abc, bdc, cda, dba and not something else like acb, cdb or dcb..the choice is endless!!

That is the part where i was lost . In fact given three vectors a,b and c, their dot products *(a,b,c), *(b,c,a) and *(c,a,b) are equal. those are even permutations. The other permutations of a,b,c which are odd give a vector with same magnitude but opposit direction.
The requirements I did, garantee that all the vertices have only positive coordinates. This way I don't have to worry about the right order for the cross products. I just take the absolute value.

[JosLeys]

Knighty, again, thanks for your time.
If you think I'm stalking you with all these questions, just say so!

One thing you did not answer is this :
We have four hyperplanes : a,b,c and d.
We take the angle between a and b to be pi/2.
We take the angle between a and c to be pi/n, n being what you call 'Type'
Between b and c it's pi/3.
So far so good, that is how it is for the 3D case also.
Where I am lost is how you determine what the angle should be between d and a,b and c....

[knighty]

Knighty, again, thanks for your time.
If you think I'm stalking you with all these questions, just say so!

Thank you too.
There is no problem. I'm glad to answer any question.

One thing you did not answer is this :
We have four hyperplanes : a,b,c and d.
We take the angle between a and b to be pi/2.
We take the angle between a and c to be pi/n, n being what you call 'Type'
Between b and c it's pi/3.
So far so good, that is how it is for the 3D case also.
Where I am lost is how you determine what the angle should be between d and a,b and c....

I just took the Coxeter group diagram as it appears in for wikipedia.
Following your post, your naming is:

 n
*-*-*-*
a c b d

Therefore the angles should be:
(a,c)=PI/n
(a,b)=PI/2
(a,d)=PI/2
(b,c)=PI/3
(b,d)=PI/3
(c,d)=PI/2

For one I took this naming convention for the fragmentarium shaders:

 n
*-*-*-*
a d b c

where n=3,4 or 5.
Therefore the angles are:
(a,b)=PI/2
(a,c)=PI/2
(a,d)=PI/n
(b,c)=PI/3
(b,d)=PI/3
(c,d)=PI/2

This is how I solve for the hyperplanes. I begin with:
a=(a0,0,0,0)
b=(b0,b1,0,0)
c=(c0,c1,c2,0)
d=(d0,d1,d2,d3)

|a|=1 => a0=1

<a|b>=0 and |b|=1 => b0=0 and b1=1

<a|c>=0 => c0=0
<b|c>=c1=-cos(PI/3)=-1/2 => c1=-1/2
|c|=1 => c2=+-sqrt(1-c1²)=+-sqrt(1-1/4)=+-sqrt(3)/2 which is +-sin(PI/3). In order for the fundamental domain to remain in 1/16 sector I have to choose the positive solution.

<a|d>=d0=-cos(PI/n)
<b|d>=d1=-cos(PI/3)=-1/2
<c|d>=c1*d1+c2*d2=0 => d2=-c1*d1/c2=-1/2*1/sqrt(3)
|d|=1 => d3=+-sqrt(1-d0²-d1²-d2²) i have to choose the positive solution so:
d3=sqrt(2/3-cos²(PI/n))

Finally:
a=(1,0,0,0)
b=(0,1,0,0)
c=(0,-1/2, sqrt(3)/2, 0)
d=(-cos(PI/n), -1/2, -1/2*1/sqrt(3), sqrt(2/3-cos²(PI/n)))

I think I am finally beginning to understand how the 4D cross product works (thanks to your stalking  ):
Let M be the matrix which rows are the vectors a,b,c,d.
First the determinant of M have to be positive. Well, I don't really know why but maybe it means that our fundamental domain is correctly oriented w.r.t. the hyperplanes normal vectors.

Now, each vertex A,B,C,D should be the vector obtained from the determinant of a matrix obtained itself from M but where the line corresponding to the hyperplane's normal opposit to the vertex is replaced with the row: (e₀,e₁,e₂,e₃). where e_i are the basis vectors. for example:

    | a0  0  0  0 |
    | b0 b1  0  0 |
C = | e₀ e₁  e₂ e₃ | = a0*b1*(e₂*d3 - e₃*d2)
    | d0 d1 d2 d3 |

This way the signs should be correct. I gess it is a little bit different in the hyperbolic case.

[JosLeys]

Knighty, I'm with you so far!
Merrily continuing my stalking, I now come to your magic formula for the distances which I've been looking at for quite some time without success.

Here we go : in 3D, the distance from the origin of the point on our ray is r.

We first promote our point to 4D through inverse stereographic projection.
Next we do all the folding around the hyperplanes to get our 4D point between those planes.
So our 4D point has changed position and if we now bring it back to 3D through stereographic projection it will be at another location than its original 3D location.

How then can the original distance from the origin, r, feature in your magic distance formula?

[knighty]

Short explanation for now. I'll try to give a more detailed one tomorrow.
The "magic" formula is just for converting distances on the 3-sphere -which are angles- to the projection space: Given a point on the projection space and a distance on the 3-sphere, what distance on the projection plane that corresponds? This is a 2D problem. we only need to do solve it on the plane defined by the original point and the w axis.

After having folded the point, the distance from that folded point to the polychora is computed on the 3-sphere (in practice it is the sine and cosine of that spherical distance that is actually computed). That distance doesn't depend on the position of the point on the sphere. Therefore we can use the "magic" formula using the original point (on the projection space) to do the conversion.

[knighty]

Here is a graphic that shows the logical steps in computing the DE:
1- Zp is our initial point in our flat space (projection space).
2- Zs is the inverse stereographic projection of Zp.
3- Zf is the Zs transformed (rotation and folding).
4- We measure the angle (spherical distance) between Zf and a feature of our polyhedra (here a vertex V in this case the cosine of the angle is <Zf|V>. both Zf and V are not necessarily in the plane of the graphic).
5- "transport" the angle towards Zs.
6- We get the point Zg
7- Zg is pojected back to the projection space which gives Good.
The distance estimate is the length of the segment Zp-Good.



It is possible to deduce a better "magic" formula than the one I used by noticing that the angle Zs-Pc-Zg is half of the angle Zs-O-Zg .

[JosLeys]

Am I right in saying that this produces a distance estimate that is always smaller or equal than the actual distance?
I'm sure it does not produce the exact distance, or am I wrong?

[knighty]

Yes, It doesn't give the exact distance. The DE have to be conservative. Indded, the obatined unbounding volume is in reality a sphere which center is 0.5*(Good+Bad) and radius 0.5*|Bad-Good|. The DE is the distance from Zp to that sphere. It is still possible to use that sphere in raymarching but I don't think it gives a huge speedup if any.

[JosLeys]

One way to get the exact distance could be as follows :
-promote the point to 4D
-Do the folding and keep track of what happens (note down the reflections, if any)
-Fold the vertex point with the inverse sequence of the folding above.
-Stereographically project the folded vertex point to 3D
-The distance is then from our original 3D point to the folded/projected vertex point.

This is probably somewhat more involved for the distance to the segments.

[knighty]

Maybe I'm wrong but I don't think that the Obtained DE is conservative. There would be some overestimations. The unbounding sphere I described in the previous post is garanteed to contain no vertices (so is the DE because the corresponding sphere is inside the unbounding sphere). It is "tangent" to only one vertex. The obtained sphere with your method would have some parts that are outside the unbounding sphere which may contain other vertices.

Keeping track of the different transformation can be achieved with a matrix. Each time a transformation occurs it's matrix representation (it's inverse actually IIRC) is mutiplied with that matrix.

[JosLeys]

What I was thinking of is the analog with one dimension less: the stereographic projection on a 2D plane of the vertices of a polyhedron in the circumscribed sphere.

Any point in the plane, through inverse stereographic projection will end up in some triangle on the sphere (see image below). Through a series of foldings, it will end up in the green, fundamental triangle.
The inverse series of foldings will put the fundamental triangle in the triangle of our point. So if we take the stereographic projection of the folded vertex, which in this case is one of the vertices of the triangle, we can read the exact distance in the 2D plane friom the distance betwee our original point in the 2D plane, and the stereographic projection of the polyhedron vertex.

In fact, this could give the exact distance to the segments also by 'backfolding' the vertices of the fundamental triangle (tetrahedron in the 4D case), and transforming the normal vectors. We can then work directly in the folded fundamental triangle...

[knighty]

You will have to consider not only the copy of the fundamental domain containig the point but also the neighbours of that copy. The attached picture shows the stereographic projection of the tiled sphere wrt the symmetry group of the dodecahedron. The blue points are all copies of each other through the symmetry group. It's clear that the red dots are closer to feature points in the neighbouring cells instead of the point that is in the same cell.