------=_Part_8400_175620.1149366900651
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
I had the thought the other day that it would be cool to do a 4D version of
the Megaminx. A little wikipedia and web searching revealed that the word
'polychoron' is a common (though not standard) word for a 4D 'polytope',
which is the word for a generalized d-dimension polygon (a 3D polytope is a
polyhedron). Also, I found that the 120-cell (
http://en.wikipedia.org/wiki/120-cell) is the polychoron that could be
considered the 4D analog of the dodecahedron, which the Megaminx is based
on.
There is a really cool picture of an exploded 120-cell projected into 3D
space about halfway down the page at
http://home.inreach.com/rtowle/Polytopes/polytope.html. This is mostly what
I was thinking about, though I imagined slightly different projection
parameters that would have the closest face hidden like in MC4D. I saw a
picture having projection parameters I like at
http://www.bathsheba.com/math/120cell/, though it isn't a cool exploded
view. The latter is more analogous to how I tried to flatten a 3D
dodecahedron into 2D when thinking about this.
Maybe the Magic120Cell puzzle would be too much with 120 faces. If
they couldn't realistically be distinguished by colors, stickers might have
to be numbered. I have seen a Megaminx with only 6 colors which had colors
repeated on opposite sides. Maybe doing something like that could help,
though it does change the nature of the puzzle (aside: I wonder if repeating
colors, but not on opposite sides, could produce a Megaminx that behaved
exactly as the 12 colored one, since the 1-colored center pieces can't
change position and the other pieces have multiple colors to help
distinguish where they belong. I'll have to think more on that. If it was
the case, maybe colors on a 120cell could even be repeated more than once
without changing the puzzle behavior.?.)
Anyway, if the 120-cell is over the top, other polychora could make good
puzzles. The 4-simplex (http://en.wikipedia.org/wiki/4-simplex) would be
the 4D analog of Pyraminx, and would be easier and less screen-crazy than
MC4D. That puzzle would also be interesting because as I imagine one
projection of it, there would be no center face. There would be 4
icosahedrons all pointing towards an empty center. The 5th icosahedron
would be the hidden face closest to the viewer (think of the 3D to 2D case
of projecting the icosahedron of a Pyraminx to 2D).
An interesting thing about these puzzles is that relative to the orthogonal
coordinate axes, face rotations can affect all coordinates of a sticker.
Just like some face twists on Megaminx can change all 3 coordinates of the
moved stickers, some face twists on Magic120Cell or Magic4Simplex could
change all 4 sticker coordinates. This is unlike the cube puzzles, and it
seems this could make the programming more difficult, e.g. in MC4D you can
reduce face rotations to 3D rotations by simply not dealing with 1 of the 4
coordinates, but this will no longer be possible. This wasn't a problem in
MC5D either, because we limited rotations to those parallel to coordinate
planes and all face rotations only changed 2 coordinate values for
stickers. I don't understand it yet, but apparently 2 quaternions can
represent any general 4D rotation (vs. 1 that is required for 3D
rotations). What I don't know is how to interpret the quaternion parameters
with a geometric meaning, like the rotation plane and rotation angle. For a
3D rotation, the quaternion that represents it has a direct geometrical way
to think about it in terms of an axis of rotation and an angle, but I'm
not sure if the 4D case even has a similar geometrical interpretation. If
anyone has any information on this, I would appreciate it.
Roice
------=_Part_8400_175620.1149366900651
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
Roice Nelson wrote:
> I had the thought the other day that it would be cool to do a 4D
> version of the Megaminx. A little wikipedia and web searching
> revealed that the word 'polychoron' is a common (though not standard)
> word for a 4D 'polytope', which is the word for a generalized
> d-dimension polygon (a 3D polytope is a polyhedron). Also, I found
> that the 120-cell ( http://en.wikipedia.org/wiki/120-cell) is the
> polychoron that could be considered the 4D analog of the dodecahedron,
> which the Megaminx is based on.
Yep. Don and I have both done a bunch of work visualizing the 120 cell
and other regular 4D objects when we were in school together in 1985-86.
In roughly 1992 when we were working on probably our 2nd implementation
of MC4D, we talked a fair amount about puzzle versions of other
polytopes. Don began work on a general engine to produce puzzles from
general 4D polytopes but never finished it. It turns out that not all
regular polytopes slice up nicely into puzzles. If I recall correctly,
the good ones in N-D are those in which D faces meet at each vertex.
Those with more faces result in cuts that generate a bunch of little
"scrap" cells in addition to the normal ones. I think that we agree that
the 120-cell is the most beautiful of the regular 4D polytopes and we
dreamed about seeing its puzzle version.
>
> There is a really cool picture of an exploded 120-cell projected into
> 3D space about halfway down the page at
> http://home.inreach.com/rtowle/Polytopes/polytope.html. This
> is mostly what I was thinking about, though I imagined slightly
> different projection parameters that would have the closest face
> hidden like in MC4D.
I'm fairly sure that that image has the closest face hidden just like in
MC4D otherwise it would overlap the rest of the figure. IOW, it looks
like a pretty good projection for a usable puzzle to me. Note that they
also seem to have removed the next layer of cells which are flattened
even more than the thin ones you can see edge-on. I suppose they did
that to let you see deeper inside. You can see the wide, shallow
indentations where they would nest around the outside. A real 120-cell
with only the outer face removed would have only 12 outwardly facing
pentagons in the shape of a dodecahedron.
> I saw a picture having projection parameters I like at
> http://www.bathsheba.com/math/120cell/, though it isn't a cool
> exploded view. The latter is more analogous to how I tried to flatten
> a 3D dodecahedron into 2D when thinking about this.
This view seems similar to your 5D puzzle in which the wireframe
rendering solves a good deal of the crowding problem. Perhaps a puzzle
version could have a slider that allowed you to quickly hide more or
fewer layers of cells either by making them invisible or turning them
into wireframe mode.
>
> Maybe the Magic120Cell puzzle would be too much with 120 faces. If
> they couldn't realistically be distinguished by colors, stickers might
> have to be numbered.
I'm not completely sure about that but we'd have to test it to be
certain. Perhaps some highlighting tools would help to mitigate the problem.
> I have seen a Megaminx with only 6 colors which had colors repeated on
> opposite sides. Maybe doing something like that could help, though it
> does change the nature of the puzzle (aside: I wonder if repeating
> colors, but not on opposite sides, could produce a Megaminx that
> behaved exactly as the 12 colored one, since the 1-colored center
> pieces can't change position and the other pieces have multiple colors
> to help distinguish where they belong. I'll have to think more on
> that. If it was the case, maybe colors on a 120cell could even be
> repeated more than once without changing the puzzle behavior.?.)
Even if you can do that, it seems like it would make it harder to solve
than simply allowing 120 unique colors.
>
> Anyway, if the 120-cell is over the top, other polychora could make
> good puzzles.
Even though the display would be crowded, it may not be as bad as MC5D
and could have some advantages that might make it easier to solve than
the 4D cube for the same reasons that the Megaminx seems easier to solve
than the original Rubik's cube due to the additional space in which you
can sequester some parts while working on others.
> The 4-simplex ( http://en.wikipedia.org/wiki/4-simplex) would be the
> 4D analog of Pyraminx, and would be easier and less screen-crazy than
> MC4D. That puzzle would also be interesting because as I imagine one
> projection of it, there would be no center face. There would be 4
> icosahedrons all pointing towards an empty center. The 5th
> icosahedron would be the hidden face closest to the viewer (think of
> the 3D to 2D case of projecting the icosahedron of a Pyraminx to 2D).
Icosahedral pieces? Is that right? I'd definitely love to try my hand at
solving this one since I can usually intuit my way to solving the 3D
version fairly quickly.
>
> An interesting thing about these puzzles is that relative to the
> orthogonal coordinate axes, face rotations can affect all coordinates
> of a sticker. Just like some face twists on Megaminx can change all 3
> coordinates of the moved stickers, some face twists on Magic120Cell or
> Magic4Simplex could change all 4 sticker coordinates. This is unlike
> the cube puzzles, and it seems this could make the programming more
> difficult, e.g. in MC4D you can reduce face rotations to 3D rotations
> by simply not dealing with 1 of the 4 coordinates, but this will no
> longer be possible. This wasn't a problem in MC5D either, because we
> limited rotations to those parallel to coordinate planes and all face
> rotations only changed 2 coordinate values for stickers. I don't
> understand it yet, but apparently 2 quaternions can represent any
> general 4D rotation (vs. 1 that is required for 3D rotations). What I
> don't know is how to interpret the quaternion parameters with a
> geometric meaning, like the rotation plane and rotation angle. For a
> 3D rotation, the quaternion that represents it has a direct
> geometrical way to think about it in terms of an axis of rotation and
> an angle, but I'm not sure if the 4D case even has a similar
> geometrical interpretation. If anyone has any information on this, I
> would appreciate it.\
My understanding is that even though quaternions do generalize, the
property that makes them useful for managing 3D rotations is just a
quirk that does not generalize. OTOH, arbitrary N-dimensional rotation
matrices are not terribly difficult to deal with. Essentially all you
need to do is specify the particular 2D plane in which you want to
rotate and the amount of rotation you want and you can build the matrix
directly from that. Don is really good with all of this stuff and his
vec_h.c program can generate a C macro library with functions for doing
all of the matrix math in whatever dimension you want.
-Melinda
On Sat, Jun 03, 2006 at 06:39:47PM -0700, Melinda Green wrote:
> Roice Nelson wrote:
> > I had the thought the other day that it would be cool to do a 4D
> > version of the Megaminx. A little wikipedia and web searching
> > revealed that the word 'polychoron' is a common (though not standard)
> > word for a 4D 'polytope', which is the word for a generalized
> > d-dimension polygon (a 3D polytope is a polyhedron). Also, I found
> > that the 120-cell ( http://en.wikipedia.org/wiki/120-cell) is the
> > polychoron that could be considered the 4D analog of the dodecahedron,
> > which the Megaminx is based on.
> Yep. Don and I have both done a bunch of work visualizing the 120 cell
> and other regular 4D objects when we were in school together in 1985-86.
> In roughly 1992 when we were working on probably our 2nd implementation
> of MC4D, we talked a fair amount about puzzle versions of other
> polytopes. Don began work on a general engine to produce puzzles from
> general 4D polytopes but never finished it. It turns out that not all
> regular polytopes slice up nicely into puzzles. If I recall correctly,
> the good ones in N-D are those in which D faces meet at each vertex.
> Those with more faces result in cuts that generate a bunch of little
> "scrap" cells in addition to the normal ones.
Wow, your memory is good. I didn't remember that at all,
but it makes sense-- try to make a rubik's-like puzzle out of an octahedron
or icosahedron, it would suck.
> I think that we agree that
> the 120-cell is the most beautiful of the regular 4D polytopes and we
> dreamed about seeing its puzzle version.
> >
> > There is a really cool picture of an exploded 120-cell projected into
> > 3D space about halfway down the page at
> > http://home.inreach.com/rtowle/Polytopes/polytope.html. This
> > is mostly what I was thinking about, though I imagined slightly
> > different projection parameters that would have the closest face
> > hidden like in MC4D.
> I'm fairly sure that that image has the closest face hidden just like in
> MC4D otherwise it would overlap the rest of the figure. IOW, it looks
> like a pretty good projection for a usable puzzle to me. Note that they
> also seem to have removed the next layer of cells which are flattened
> even more than the thin ones you can see edge-on. I suppose they did
> that to let you see deeper inside. You can see the wide, shallow
> indentations where they would nest around the outside. A real 120-cell
> with only the outer face removed would have only 12 outwardly facing
> pentagons in the shape of a dodecahedron.
I think that picture is an orthogonal projection,
showing only the "front" 60 of the 120 cells.
> > I saw a picture having projection parameters I like at
> > http://www.bathsheba.com/math/120cell/, though it isn't a cool
> > exploded view. The latter is more analogous to how I tried to flatten
> > a 3D dodecahedron into 2D when thinking about this.
> This view seems similar to your 5D puzzle in which the wireframe
> rendering solves a good deal of the crowding problem. Perhaps a puzzle
> version could have a slider that allowed you to quickly hide more or
> fewer layers of cells either by making them invisible or turning them
> into wireframe mode.
> >
> > Maybe the Magic120Cell puzzle would be too much with 120 faces. If
> > they couldn't realistically be distinguished by colors, stickers might
> > have to be numbered.
> I'm not completely sure about that but we'd have to test it to be
> certain. Perhaps some highlighting tools would help to mitigate the problem.
> > I have seen a Megaminx with only 6 colors which had colors repeated on
> > opposite sides. Maybe doing something like that could help, though it
> > does change the nature of the puzzle (aside: I wonder if repeating
> > colors, but not on opposite sides, could produce a Megaminx that
> > behaved exactly as the 12 colored one, since the 1-colored center
> > pieces can't change position and the other pieces have multiple colors
> > to help distinguish where they belong. I'll have to think more on
> > that. If it was the case, maybe colors on a 120cell could even be
> > repeated more than once without changing the puzzle behavior.?.)
> Even if you can do that, it seems like it would make it harder to solve
> than simply allowing 120 unique colors.
> >
> > Anyway, if the 120-cell is over the top, other polychora could make
> > good puzzles.
> Even though the display would be crowded, it may not be as bad as MC5D
> and could have some advantages that might make it easier to solve than
> the 4D cube for the same reasons that the Megaminx seems easier to solve
> than the original Rubik's cube due to the additional space in which you
> can sequester some parts while working on others.
Yeah, I bet the 120-cell would be a lot easier than the hypercube...
provided you can find where the hell you are trying to put stuff.
I agree, a clever highlighting scheme would be the key to making it feasible
for a human.
And talk about tedious ... I think what you'd see is essentially
120 megaminxes, each with 1+12+30+20=63 hyperstickers,
for a total of 120*63=7560 hyperstickers...
compared to only 10*3^4=810 for MagicCube5d,
and 12*3^5=2916 for MagicCube6d.
Another thing to think about-- you can use various kinds of
hyperprisms, too. I rendered a bunch of these and they look
like they would be decent puzzles... e.g. a dodecahedral prism,
or a pentagonal-prism-prism-- in fact they look just like MagicCube4D
at first glance.
Some of the twists would have to be limited appropriately.
> > The 4-simplex ( http://en.wikipedia.org/wiki/4-simplex) would be the
> > 4D analog of Pyraminx, and would be easier and less screen-crazy than
> > MC4D. That puzzle would also be interesting because as I imagine one
> > projection of it, there would be no center face. There would be 4
> > icosahedrons all pointing towards an empty center. The 5th
> > icosahedron would be the hidden face closest to the viewer (think of
> > the 3D to 2D case of projecting the icosahedron of a Pyraminx to 2D).
> Icosahedral pieces? Is that right? I'd definitely love to try my hand at
> solving this one since I can usually intuit my way to solving the 3D
> version fairly quickly.
> >
> > An interesting thing about these puzzles is that relative to the
> > orthogonal coordinate axes, face rotations can affect all coordinates
> > of a sticker. Just like some face twists on Megaminx can change all 3
> > coordinates of the moved stickers, some face twists on Magic120Cell or
> > Magic4Simplex could change all 4 sticker coordinates. This is unlike
> > the cube puzzles, and it seems this could make the programming more
> > difficult, e.g. in MC4D you can reduce face rotations to 3D rotations
> > by simply not dealing with 1 of the 4 coordinates, but this will no
> > longer be possible. This wasn't a problem in MC5D either, because we
> > limited rotations to those parallel to coordinate planes and all face
> > rotations only changed 2 coordinate values for stickers. I don't
> > understand it yet, but apparently 2 quaternions can represent any
> > general 4D rotation (vs. 1 that is required for 3D rotations). What I
> > don't know is how to interpret the quaternion parameters with a
> > geometric meaning, like the rotation plane and rotation angle. For a
> > 3D rotation, the quaternion that represents it has a direct
> > geometrical way to think about it in terms of an axis of rotation and
> > an angle, but I'm not sure if the 4D case even has a similar
> > geometrical interpretation. If anyone has any information on this, I
> > would appreciate it.\
> My understanding is that even though quaternions do generalize, the
> property that makes them useful for managing 3D rotations is just a
> quirk that does not generalize. OTOH, arbitrary N-dimensional rotation
> matrices are not terribly difficult to deal with. Essentially all you
> need to do is specify the particular 2D plane in which you want to
> rotate and the amount of rotation you want and you can build the matrix
> directly from that. Don is really good with all of this stuff and his
> vec_h.c program can generate a C macro library with functions for doing
> all of the matrix math in whatever dimension you want.
I haven't heard of the 2-quaternions-to-represent-abitrary-4D-rotation thing
before, but my guess is it's the familiar
rotate-followed-by-translate scheme commonly used to express rigid
transformations in euclidean or hyperbolic space
(commonly used internally in hyperbolic
browsers and other programs like Tyler and my hyperbolic tesselations applet).
That is, the first unit quaternion R (the "rotate" part)
would express an arbitrary rotation in the xyz hyperplane,
and the second unit quaternion T (the "translate" part)
specifies the unit coordinates where (0,0,0,1) should go
using the most direct rotation that takes it there
(which feels like a translation).
Actually I'm lying-- probably T needs to be the coordinates
of the halfway point on the arc between (0,0,0,1) and where
it's being taken (since if you interpret it as the fully rotated
image of (0,0,0,1), then T=(0,0,0,-1) would be ambiguous).
Then every T will represent the same orientation as -T,
which is typical for quaternion representations.
To factor an arbitrary 4d rotation matrix into such R,T,
first figure out T (this can be easily extracted
from the last row of the matrix, except when
the last row of the matrix is (0,0,0,-1) in which case I'd have
to think about it more),
then multiply the original matrix by the inverse of T's matrix,
to get R's matrix, from which you can get the quaternion R
in the usual way (i.e. look it up in Graphics Gems).
So if you want to work with this R,T representation
instead of matrices, you'd need to figure out three formulas:
1. How to apply the rotation R,T to arbitrary coords (x,y,z,w)
2. Given rotations R0,T0 and R1,T1, find their composition R,T
3. Given a rotation R,T, find its inverse R',T'
(i.e. R',T' such that R,T composed with R',T' is the identity).
It would be interesting to see these formulas;
I wonder if they collapse into something nice.
I always prefer to compose from left to right,
since I think that's a lot less confusing than the alternative.
So
(x,y,z,w) * (R0,T0) * (R1,R1)
would mean first rotate the coords by (R0,T0)
and then rotate the resulting coords by (R1,T1)...
so the composition (R,T) = (R0,T0) * (R1,R1)
would mean the single rotation that does that.
Don
------=_Part_10704_19743594.1149923358850
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
Thanks for the cool comments Melinda and Don. I have just a couple inlines
below.
On 6/3/06, Melinda Green
> > The 4-simplex ( http://en.wikipedia.org/wiki/4-simplex) would be the
> > 4D analog of Pyraminx, and would be easier and less screen-crazy than
> > MC4D. That puzzle would also be interesting because as I imagine one
> > projection of it, there would be no center face. There would be 4
> > icosahedrons all pointing towards an empty center. The 5th
> > icosahedron would be the hidden face closest to the viewer (think of
> > the 3D to 2D case of projecting the icosahedron of a Pyraminx to 2D).
> Icosahedral pieces? Is that right? I'd definitely love to try my hand at
> solving this one since I can usually intuit my way to solving the 3D
> version fairly quickly.
Oops... After reading Don's email today, I saw I had used the wrong term
here. I should have realized when Melinda questioned it. Replace all the
uses of "icosahedron" with "tetrahedron" to get what I was meaning by the 4D
analog of Pyraminx.
On 6/9/06, Don Hatch
> So if you want to work with this R,T representation
> instead of matrices, you'd need to figure out three formulas:
> 1. How to apply the rotation R,T to arbitrary coords (x,y,z,w)
> 2. Given rotations R0,T0 and R1,T1, find their composition R,T
> 3. Given a rotation R,T, find its inverse R',T'
> (i.e. R',T' such that R,T composed with R',T' is the identity).
> It would be interesting to see these formulas;
> I wonder if they collapse into something nice.
I don't know if you have ever used the C++ boost library, but I found some
information there that might help answer these questions. They have a
quaternion library, whose main page is here:
http://www.boost.org/libs/math/quaternion/index.html
An example file using this library to convert 2 quaternions to a 4D rotation
matrix (which helps answer 1) is here:
http://www.boost.org/libs/math/quaternion/HSO4.hpp
From a wikipedia article (http://en.wikipedia.org/wiki/Quaternion_rotation),
I gathered the answer to 2 is that the composition of rotations is still
done by quaternion multiplication like you would do for 3D rotations. In
this case, I think you would just multiply all 4 quaternions in succession.
I bet the finding the inverse is straightforward for this reason too.
But I'd like to take the path of least resistance first in any playing I
might do with this stuff, and it sounds like that is probably using standard
rotational matrices.
I liked the prism suggestion btw. I hadn't thought of that...
Roice
------=_Part_10704_19743594.1149923358850
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline> The 4-simplex ( http://en.wikipedia.org/wiki/4-simplex
) would be the
> 4D analog of Pyraminx, and would be easier and less screen-crazy than
> MC4D. That puzzle would also be interesting because as I imagine one
> projection of it, there would be no center face. There would be 4
> icosahedrons all pointing towards an empty center. The 5th
> icosahedron would be the hidden face closest to the viewer (think of
> the 3D to 2D case of projecting the icosahedron of a Pyraminx to 2D).
Icosahedral pieces? Is that right? I'd definitely love to try my hand at
solving this one since I can usually intuit my way to solving the 3D
version fairly quickly.
> instead of matrices, you'd need to figure out three formulas:
> 1. How to apply the rotation R,T to arbitrary coords (x,y,z,w)
> 2. Given rotations R0,T0 and R1,T1, find their composition R,T
> 3. Given a rotation R,T, find its inverse R',T'
> (i.e. R',T' such that R,T composed with R',T' is the identity).
> It would be interesting to see these formulas;
> I wonder if they collapse into something nice.
------=_Part_10704_19743594.1149923358850--