Defining the new surfaces when performing an extrusion

Discuss interdimensional programming, Java applets and so forth.

Defining the new surfaces when performing an extrusion

Postby daemonflower » Sun Nov 02, 2008 6:14 pm

Hi,

I'm currently puzzling over Rotopes and how to represent them in a program. In particular, I've hit a brick wall when trying to define the new surfaces that are created when an object is extruded along an axis.

My current algorithm works for dimensions up to three. The surfaces of a cube are calculated correctly. For a tesseract it finds only 20 of its 24 surfaces. For a penteract, only 56 surfaces are found instead of 80. So clearly, I'm forgetting something.

My algorithm goes like this:
  • an object is represented by a list. To extrude it, the list is duplicated and each of the new vertices is shifted in the direction of the extrusion.
  • define a rectangular surface for each vertex in the list of the existing vertices, and the next one in the list, and their two extruded "images".
  • define a rectangular surface between the last vertex in the vertex list, and the first, and their two extrusions.
  • copy the list of surfaces that the old object had, replace the old vertices by their images, and add them to the defined surfaces (this is the new cap of a cube, for example).
(In C++, all this is a bit too lengthy to paste it here. You can view my code at http://hyperspace-expl.svn.sourceforge. ... iew=markup , if you like. The extrusion function starts at line 114.)

What am I missing?

Thanks,
If you like this thought, try some more: http://hyperspace-travel.de/blog
daemonflower
Dionian
 
Posts: 18
Joined: Sun Mar 11, 2007 5:10 pm

Re: Defining the new surfaces when performing an extrusion

Postby Keiji » Sun Nov 02, 2008 8:43 pm

Well, you need to take into account that for n dimensions there are n types of hypercell. In 3D, there are vertices, edges and faces; 4D adds cells, 5D adds tera, 6D adds peta and so on.

The pattern is as follows: when you want to extrude something, firstly you duplicate and translate all of all types of hypercell. Then, you also need to create a (k+1)-hypercell for each k-hypercell in the original shape, adding them to the collection.

So, for example, for cube to tesseract:

8 vertices -> 16 vertices
12 edges -> 24 + 8 = 32 edges
6 faces -> 12 + 12 = 24 faces
1 cell -> 2 + 6 = 8 cells
0 tera -> 1 teron
User avatar
Keiji
Administrator
 
Posts: 1984
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Defining the new surfaces when performing an extrusion

Postby quickfur » Mon Nov 03, 2008 7:47 pm

Also keep in mind that in n-dimensional space, the bounding facets are (n-1)-dimensional. 2D faces are bounding only in 3D; in 4D, they are merely "ridges" (they play a role analogous to edges in 3D), and in 5D, they are merely "peaks" (play a role analogous to vertices in 3D). In higher dimensions, they are almost irrelevant, in a sense. So 2D faces are "surfaces" only in 3D; in 4D the surface consists of 3D cells, and in 5D, the surface consists of 4D hypercells, etc..
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Defining the new surfaces when performing an extrusion

Postby daemonflower » Tue Nov 04, 2008 1:02 pm

I'm having some difficulty wrapping my head around this (as is customary when trying to think in higher dimensions).

Do I get this right: Instead of pulling surfaces out of a square to generate a cube, I'd have to pull cells out to generate a tesseract from a cube, tera from a tesseract to generate a penteract, and so on?

I'll have to ponder this for a while to see how I can code this efficiently and elegantly...
If you like this thought, try some more: http://hyperspace-travel.de/blog
daemonflower
Dionian
 
Posts: 18
Joined: Sun Mar 11, 2007 5:10 pm

Re: Defining the new surfaces when performing an extrusion

Postby quickfur » Tue Nov 04, 2008 4:47 pm

daemonflower wrote:I'm having some difficulty wrapping my head around this (as is customary when trying to think in higher dimensions).

Do I get this right: Instead of pulling surfaces out of a square to generate a cube, I'd have to pull cells out to generate a tesseract from a cube, tera from a tesseract to generate a penteract, and so on?

I'll have to ponder this for a while to see how I can code this efficiently and elegantly...

Think of it this way: a line segment (a 1D "cube") is bounded by two points, a square (a 2D "cube") is bounded by 4 edges, and a 3D cube is bounded by 6 square faces. So a 4D cube is bounded by 8 cubic facets (cells), and a 5D cube is bounded by 10 tesseractic hypercells. A 6D cube is bounded by 12 5D cubes, and a 7D cube is bounded by 14 6D cubes, and so forth.

You basically end up with a face lattice: e.g., a 3D cube has 6 square faces, and each face in turn has 4 edges (but they are shared by each pair of adjacent faces), and each edge has 2 vertices. A 4D cube adds one more layer to this: it has 8 cubic cells, each cubic cell has 6 faces, each face has 4 edges, and each edge has 2 vertices. Every time you go up a dimension, you add another layer to the structure.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Defining the new surfaces when performing an extrusion

Postby daemonflower » Tue Nov 04, 2008 6:47 pm

quickfur wrote:Think of it this way: a line segment (a 1D "cube") is bounded by two points, a square (a 2D "cube") is bounded by 4 edges, and a 3D cube is bounded by 6 square faces. So a 4D cube is bounded by 8 cubic facets (cells), and a 5D cube is bounded by 10 tesseractic hypercells. A 6D cube is bounded by 12 5D cubes, and a 7D cube is bounded by 14 6D cubes, and so forth.

That image helps. So to extrude a D+1-hypercube from a D-hypercube, you'd first add a cell that's just a copy of the D-cube shifted along the D+1-axis, and then add 2D D-cubes. The big question here is, is there a simple and generic way to find the 2D vertices each of these D-cubes consists of?

And then: So far we've only talked about hypercubes. It's true that a D-cube is bound by 2D D-1-cubes. But what about other polytopes? For instance, is the extrusion of a tetrahedron into the 4th axis also bounded by cubes? That's hard to believe.

If it isn't, I need a more generic way. Or is the geometry of the surcell determined by the number of extrusions that have been performed before?
If you like this thought, try some more: http://hyperspace-travel.de/blog
daemonflower
Dionian
 
Posts: 18
Joined: Sun Mar 11, 2007 5:10 pm

Re: Defining the new surfaces when performing an extrusion

Postby Keiji » Tue Nov 04, 2008 7:58 pm

daemonflower wrote:The big question here is, is there a simple and generic way to find the 2D vertices each of these D-cubes consists of?


Way to ignore my post completely.

And then: So far we've only talked about hypercubes. It's true that a D-cube is bound by 2D D-1-cubes. But what about other polytopes? For instance, is the extrusion of a tetrahedron into the 4th axis also bounded by cubes? That's hard to believe.


A tetrahedral prism has two tetrahedral cells and four triangular prism cells.
User avatar
Keiji
Administrator
 
Posts: 1984
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Defining the new surfaces when performing an extrusion

Postby quickfur » Tue Nov 04, 2008 8:31 pm

daemonflower wrote:[...]The big question here is, is there a simple and generic way to find the 2D vertices each of these D-cubes consists of?

You mean to find out which vertices correspond with which facet? You can tell by looking at which (D-1) ridges generated this facet.

But if you're talking about solving this in general, then you're trying to solve a problem called face lattice enumeration. For simple polytopes, this is not too hard, but in the general case, this is non-trivial and requires special algorithms. You can find these algorithms online by searching for "face lattice enumeration" or "face enumeration". You could also use an existing library that implements one of these algorithms. I personally use cddlib.

And then: So far we've only talked about hypercubes. It's true that a D-cube is bound by 2D D-1-cubes. But what about other polytopes? For instance, is the extrusion of a tetrahedron into the 4th axis also bounded by cubes? That's hard to believe.

If it isn't, I need a more generic way. Or is the geometry of the surcell determined by the number of extrusions that have been performed before?

When you extrude something, the resulting polytope has a "bottom" facet which is the object you started with, a "top" facet which is a copy of this object, and a number of prisms, one for each facet in the object you started with.

For example, take an icosidodecahedron, which consists of 12 pentagonal faces and 20 triangular faces. If you extrude this polyhedron, you get a polytope with two facets in the shape of icosidodecahedrons, 12 facets in the shape of pentagonal prisms, and 20 facets in the shape of triangular prisms. In other words, the process of extrusion creates (n+1)-dimensional prisms out of each n-dimensional facet in the original object, as well as two copies of the original object.

Another example: the rectified tesseract is a 4D polytope consisting of 8 cuboctahedral cells and 16 tetrahedral cells. If you extrude this object into 5D, you get a 5D polytope with two hypercells in the shape of rectified tesseracts, 8 hypercells as cuboctahedral prisms, and 16 hypercells as tetrahedral prisms. The cuboctahedral prisms in turn consist of two cuboctahedra, 6 cubes (square prisms), and 8 triangular prisms. The tetrahedral prisms in turn consist of two tetrahedra and 4 triangular prisms.

As you can see, the number of elements in a polytope's face lattice increases dramatically as the dimension increases. Polytopes are combinatorial objects, so you're dealing with binomial coefficients and factorials. If you're trying to implement a general algorithm for extrusion, you're probably better off dealing with just the vertices (trivial in the case of extrusion), and running a convex hull algorithm (non-trivial) afterwards. Once you have the convex hull, you can solve the linear programming problem to enumerate the face lattice (again, non-trivial). My advice is to use an existing library instead of tearing out your hair trying to tackle this directly.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Defining the new surfaces when performing an extrusion

Postby daemonflower » Wed Nov 05, 2008 4:30 pm

Sorry if I appear a bit dense. It's a busy week with lots of other things on my mind. And sorry if I appear to ignore answers. My thoughts are wandering along convoluted, almost fractal-like paths and by the time I arrive at a particular question I may have forgotten that there has been an answer before.

Anyway, my current impression is that it's not that hard to extrude the surfaces of an object after all. I had gotten stuck in the idea of computing the new surfaces from only the vertex information, and that is indeed difficult. But I can handle surfaces just like I did vertices: I have a list of surfaces for a D-dimensional object, and all I need to do is add an image shifted along the D+1-axis, and rectangles connecting the surfaces of the original with the image (assuming, of course, that the original object has polygonal surfaces - which, in my computer-generated approximation, it has). Is that what you mean by:
quickfur wrote:You can tell by looking at which (D-1) ridges generated this facet.
When you extrude something, the resulting polytope has a "bottom" facet which is the object you started with, a "top" facet which is a copy of this object, and a number of prisms, one for each facet in the object you started with.
If I more or less reiterate what you've said, it's because I try to translate your language into the actual implementation I'm working on...

Anyway, have I got it now, or am I still fumbling?

And I also should ask about the operations to generate circles, spheres and tori - but I'll leave that to when I'm sure I've understood extrusion, and when I'm actually working on those. Just a general question now: How do you call those operations? Spheration? Toration? :)
If you like this thought, try some more: http://hyperspace-travel.de/blog
daemonflower
Dionian
 
Posts: 18
Joined: Sun Mar 11, 2007 5:10 pm

Re: Defining the new surfaces when performing an extrusion

Postby quickfur » Wed Nov 05, 2008 6:59 pm

daemonflower wrote:[...]Anyway, my current impression is that it's not that hard to extrude the surfaces of an object after all. I had gotten stuck in the idea of computing the new surfaces from only the vertex information, and that is indeed difficult. But I can handle surfaces just like I did vertices: I have a list of surfaces for a D-dimensional object, and all I need to do is add an image shifted along the D+1-axis, and rectangles connecting the surfaces of the original with the image (assuming, of course, that the original object has polygonal surfaces - which, in my computer-generated approximation, it has). Is that what you mean by:
quickfur wrote:You can tell by looking at which (D-1) ridges generated this facet.
When you extrude something, the resulting polytope has a "bottom" facet which is the object you started with, a "top" facet which is a copy of this object, and a number of prisms, one for each facet in the object you started with.
If I more or less reiterate what you've said, it's because I try to translate your language into the actual implementation I'm working on...

Yes, that is correct. Don't forget that each of the surfaces of the original plus its copy and the prisms surrounding it will form a new (D+1)-face, and it is this face that will get extruded in the next iteration. For example, if you extrude a triangle, each edge becomes a square in addition to a second triangle being introduced. This is the triangular prism. Now if you extrude this, each of the triangles will generate triangular prisms, and each of the square faces will generate cubes, and the triangular prism itself will get a second copy. So the result is a polychoron with 2+2 triangular prisms and 3 cubes. This polychoron happens to be the same as the 3,4-duoprism. Now if you extrude this, you get a 5-polytope with 2+4 3,4-duoprisms (2 for the top and bottom hypercells, 4 from extruding the triangular prism cells), and 3 tesseracts.

We could summarize the procedure recursively thus: given an n-polytope Pn with facets F1, F2, ... Fm, the extrusion of Pn, denoted extrusion(Pn), has the facets Pn, Pn (two copies of Pn), extrusion(F1), extrusion(F2), ... extrusion(Fm).

Anyway, have I got it now, or am I still fumbling?

And I also should ask about the operations to generate circles, spheres and tori - but I'll leave that to when I'm sure I've understood extrusion, and when I'm actually working on those. Just a general question now: How do you call those operations? Spheration? Toration? :)

It depends on exactly what you define these operations to be. A circle can be generated in a variety of ways, such as being the "curve of revolution" (the lower-dimensional analog of the solid of revolution) of a displaced point, or as the convex hull of points a fixed distance from the origin. The former generalizes to tori: in 3D, the solid of revolution of a displaced circle is the torus, but the solid of revolution of an origin-centered circle is a sphere. The latter only generates spheres: in any dimension, the convex hull of points a fixed distance from the origin is the n-sphere.

These are not the only possibilities, however. One can, for example, take Cartesian products with circle; for example, the Cartesian product of a polygon and a circle creates what I call a prismic cylinder (I believe Wendy calls them circle-polygon prisms, in a generalized definition of prism), bounded by n cylinders and a polygonal torus. The Cartesian product of two circles is a duocylinder, bounded by two circular tori.

Here one should be aware that whether the starting objects are hollow or solid will make a big difference. Strictly speaking, the Cartesian product of two circles is only the ridge of the duocylinder (the 2-manifold along which its two bounding tori are joined), which is isomorphic to the Clifford torus; the duocylinder itself is the Cartesian product of two discs. The Cartesian product of a sphere and a line gives the curved side of a spherinder, but without its "caps". The actual spherinder itself requires the Cartesian product of a ball and a line. (A sphere is hollow and therefore does not form a bounding surface in 4D; a solid ball is needed for that.)

The Cartesian product of higher-dimensional objects will result in higher-dimensional shapes; for example, the product of a polygon with a ball results in a 5D shape bounded by n spherinders and a polygonal-circular torus.

Besides Cartesian products with round things (which generate other round shapes merely because of roundness of the starting object(s)), there is also the algebraic method of generating round shapes, using the rss() operator (rss = root sum squares = sqrt(x1^2 + x2^2 + x3^2 + ...)). For example, the equation rss(x,y)=1 generates a unit circle; rss(x,y,z)=1 generates a unit sphere, and rss(w,x,y,z)=1 generates a unit glome (3-sphere). rss(x,y)-z=1 generates a cone, so you can see how mixing rss() with other functions will generate a variety of round shapes, possibly with various non-round properties (e.g., the cone is both circular and triangular).
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Defining the new surfaces when performing an extrusion

Postby daemonflower » Wed Nov 05, 2008 8:58 pm

quickfur wrote:Don't forget that each of the surfaces of the original plus its copy and the prisms surrounding it will form a new (D+1)-face, and it is this face that will get extruded in the next iteration.
I'm still not sure we're on the same page here, because you talk about (D+1)-faces. When I say "surfaces", I mean actual 2D surfaces. I don't care about sur-cells of a dimension higher than 2. This is basically because I want to visualize the objects, and I do this in OpenGL, and OpenGL only knows how to draw surfaces, nothing else. *)

I figured, if I take every surface of the original object, and connect it to its extruded image with a new, rectangular surface, the surcell will generate itself. From your answer I'm still not sure if that is the case. I'll just try and see. That won't happen before the weekend, though.
We could summarize the procedure recursively thus: given an n-polytope Pn with facets F1, F2, ... Fm, the extrusion of Pn, denoted extrusion(Pn), has the facets Pn, Pn (two copies of Pn), extrusion(F1), extrusion(F2), ... extrusion(Fm).
Yes, that is exactly the procedure I have in mind: Generating a rotope by repeatedly applying extrusions... and other operations. As to which...
And I also should ask about the operations to generate circles, spheres and tori - but I'll leave that to when I'm sure I've understood extrusion, and when I'm actually working on those. Just a general question now: How do you call those operations? Spheration? Toration? :)

It depends on exactly what you define these operations to be.
As I'm only interested in rotopes right now, I thought these operations had a strict definition, as in http://teamikaria.com/wiki/Rotope. Objects generated by cartesian products are beyond the scope of my program - extruding a polytope into a new dimension is quite different from taking the cartesian product of two polytopes. Let's stay with rotopes - as you can see, they give me headache enough.
A circle can be generated in a variety of ways, such as being the "curve of revolution" (the lower-dimensional analog of the solid of revolution) of a displaced point, or as the convex hull of points a fixed distance from the origin. The former generalizes to tori: in 3D, the solid of revolution of a displaced circle is the torus, but the solid of revolution of an origin-centered circle is a sphere. The latter only generates spheres: in any dimension, the convex hull of points a fixed distance from the origin is the n-sphere.
I'd prefer to generate a circle in the way computer people always do - as a polygonal approximation. So, of course, I'm lying through my teeth if I say I want to do a spheration :)

What I'm having in mind is an operation analogous to extrusion - only that instead of one image the generating object is extruded to n images, all lying on a circle along the new axis. Far from mathematically correct, but works for me. **)
Here one should be aware that whether the starting objects are hollow or solid will make a big difference. Strictly speaking, the Cartesian product of two circles is only the ridge of the duocylinder (the 2-manifold along which its two bounding tori are joined), which is isomorphic to the Clifford torus; the duocylinder itself is the Cartesian product of two discs. The Cartesian product of a sphere and a line gives the curved side of a spherinder, but without its "caps". The actual spherinder itself requires the Cartesian product of a ball and a line. (A sphere is hollow and therefore does not form a bounding surface in 4D; a solid ball is needed for that.)
Which serves to strengthen my gut feeling that I should stay away from visualizing objects generated by the cartesian products - they are way more complicated to treat in a simulation.
Besides Cartesian products with round things (which generate other round shapes merely because of roundness of the starting object(s)), there is also the algebraic method of generating round shapes, using the rss() operator (rss = root sum squares = sqrt(x1^2 + x2^2 + x3^2 + ...)). For example, the equation rss(x,y)=1 generates a unit circle; rss(x,y,z)=1 generates a unit sphere, and rss(w,x,y,z)=1 generates a unit glome (3-sphere). rss(x,y)-z=1 generates a cone, so you can see how mixing rss() with other functions will generate a variety of round shapes, possibly with various non-round properties (e.g., the cone is both circular and triangular).
If I recall my rusty math correctly, what you're describing here is a way of defining a parametrized n-dimensional surface. That's something else I have on the shelf for my 4D viewer, but it will have to wait.

*) Well, technically, OpenGL can draw points and lines too, and even 3D textures, but that's beside the point here. 8)
**) Actually, if it really works for me, remains to be seen.
If you like this thought, try some more: http://hyperspace-travel.de/blog
daemonflower
Dionian
 
Posts: 18
Joined: Sun Mar 11, 2007 5:10 pm

Re: Defining the new surfaces when performing an extrusion

Postby quickfur » Wed Nov 05, 2008 10:12 pm

daemonflower wrote:
quickfur wrote:Don't forget that each of the surfaces of the original plus its copy and the prisms surrounding it will form a new (D+1)-face, and it is this face that will get extruded in the next iteration.
I'm still not sure we're on the same page here, because you talk about (D+1)-faces. When I say "surfaces", I mean actual 2D surfaces. I don't care about sur-cells of a dimension higher than 2. This is basically because I want to visualize the objects, and I do this in OpenGL, and OpenGL only knows how to draw surfaces, nothing else. *)

It is true that GL (or anything else for that matter!) can only render 2D surfaces, since the computer screen is only capable of displaying 2D surfaces! However, if you truly want to visualize higher dimensional objects, it is really necessary to know which 2-faces belong to which surtopes/surcells. In the process of my own learning to visualize 4D objects, I discovered that it is most helpful if the visualization tool could, at the user's request, render the 2-faces belonging to a particular surcell (or particular set of surcells) differently so that its placement and orientation within the whole can be more accurately seen. Often, while contemplating these projections, one desires also to be able to tell the tool, "show me the surcells next to these ones (based on some specified criteria)". In order to do this meaningfully, the program needs to know which 2-faces belong to which surcells.

I figured, if I take every surface of the original object, and connect it to its extruded image with a new, rectangular surface, the surcell will generate itself. From your answer I'm still not sure if that is the case. I'll just try and see. That won't happen before the weekend, though.

I'm not sure what you mean by "the surcell will generate itself"; if you're hoping that the mere juxtaposition of 2-faces rendered by your program will magically make you see the surcells, you may be disappointed. To truly understand a higher-dimensional object, you really need to understand that it consists of bounding (n-1)-dimensional facets, and until you can fully grasp this, the object will not make very much sense: it will just generate an incomprehensible tangle of surfaces on the screen. The lower-dimensional surfaces are really merely incidental, and yield very little information about the true geometry of the polytope in its native space.

That is not to say that rendering merely 2-faces is of no help at all; since what else would we use otherwise? (Line-drawings, as I'm sure you're aware, are almost completely useless in visualizing these polytopes; past a certain point, they just start looking like somebody's hair on a bad hair day and give no useful insight at all.) The point is that you'll probably need to apply enhancements to these faces, such as highlighting faces belonging to a certain surcell, in order for the result to be informative. But in order to do this, you'll need to know what the surcells are: so the program needs to represent them, even if they cannot be directly rendered!

[...]As I'm only interested in rotopes right now, I thought these operations had a strict definition, as in http://teamikaria.com/wiki/Rotope. Objects generated by cartesian products are beyond the scope of my program - extruding a polytope into a new dimension is quite different from taking the cartesian product of two polytopes. Let's stay with rotopes - as you can see, they give me headache enough.

Don't you worry; it takes a while before you can visualize extruded objects naturally, but once you do, it will seem almost trivial in retrospect.

Cartesian products took me a long time to grasp... eventually, the most natural way of visualizing them (to me, at least) is to avoid approaching them from the standpoint of a Cartesian product at all, but to derive them geometrically from something simpler: in the case of the 4D Cartesian products, from examining the structure of the tesseract. In fact, when I finally grokked Cartesian products, it was almost by accident: I was contemplating the structure of the tesseract and comparing it to the extruded tetrahedron (the tetrahedral prism), and it occurred to me that it was possible to dissect the tesseract into two rings of 4 cells each. A little geometric imagination suggests varying the size of these rings by substitution with different polygonal prisms, and before I knew it (literally!) I was dealing with duoprisms, though at the time I didn't know they were duoprisms. In fact, I actually derived the duocylinder this way, as the limit of the duoprisms, without even realizing it was the duocylinder. It was after the fact that I went back to George Olshevsky's website and realized that these objects were actually the duoprisms he was talking about, and it was only after reading up a bit more about duocylinders that it occurred to me that it was the same object that I had re-discovered from a purely geometrical approach.

As a testament to the difficulty (at least to me) of approaching Cartesian products directly, it was only long after the fact that it occurred to me that the duocylinder is the Cartesian product of two circles, being the limit of the Cartesian product of polygons. This was after I had worked out many of its geometrical properties and made wireframe animations of it. I don't think I could possibly have derived any of this if I had only known it as the Cartesian product of two circles.

[...]I'd prefer to generate a circle in the way computer people always do - as a polygonal approximation. So, of course, I'm lying through my teeth if I say I want to do a spheration :)

I'd nitpick with your statement that computer people always generate circles as polygonal approximations---ray-tracing being the notable counter-example---but having created projections of the duocylinder myself using approximating duoprisms, I can fully sympathise with the utility of your approach. :)

What I'm having in mind is an operation analogous to extrusion - only that instead of one image the generating object is extruded to n images, all lying on a circle along the new axis. Far from mathematically correct, but works for me. **)

It's not far from mathematically correct at all. In fact, you've just derived the Cartesian product of a polytope with a circle, without knowing it as such. :) Well, maybe not exactly, but if you start with, say, some polygon in the XY plane, and then "extrude" this polygon along a circle in WZ plane (note that a circle requires two dimensions to "circle" in, otherwise you could only get a line segment)---that is to say, take n copies of the polygon and place them along a circle in the WZ plane, forming a trace of them---then what you get is in fact equivalent to the Cartesian product of the polygon with a circle. If, instead of placing the images along a circular path, you place the images along a polygonal path, why, then, you've just made a duoprism! (See? They're not that hard to understand after all.)

Here one should be aware that whether the starting objects are hollow or solid will make a big difference. Strictly speaking, the Cartesian product of two circles is only the ridge of the duocylinder (the 2-manifold along which its two bounding tori are joined), which is isomorphic to the Clifford torus; the duocylinder itself is the Cartesian product of two discs.[...]
Which serves to strengthen my gut feeling that I should stay away from visualizing objects generated by the cartesian products - they are way more complicated to treat in a simulation.

Not really. You've almost stumbled upon them without even knowing what a Cartesian product looks like. :)

I think this just underscores the fact that trying to visualize a Cartesian product from a purely set-theoretic point of view (a Cartesian product is the set of all ordered tuples of the constituent sets) is almost impossible past 3 dimensions. However, approaching it from a geometrical viewpoint is much easier. If you're fairly comfortable with the structure of the tesseract, the following page may help you see that Cartesian products are really not to be afraid of:

http://eusebeia.dyndns.org/4d/duoprism.html

Besides Cartesian products with round things (which generate other round shapes merely because of roundness of the starting object(s)), there is also the algebraic method of generating round shapes, using the rss() operator [...]
If I recall my rusty math correctly, what you're describing here is a way of defining a parametrized n-dimensional surface. That's something else I have on the shelf for my 4D viewer, but it will have to wait.

No, what this is, is to define a shape as the set of points satisfying a particular equation/inequality. It is not feasible to directly evaluate these equations/inequalities (although it does give us a nice, concise and precise way of expressing a certain class of shapes); rather, certain geometrical properties can be inferred from them by suitable application of algebra and analysis.

Or, to put it simply, they are for the math buffs to drool over, while those programmers among us would rather just deal with polytopic approximations of these things and leave it at that. :)

*) Well, technically, OpenGL can draw points and lines too, and even 3D textures, but that's beside the point here. 8)[...]

Well, OpenGL 3D textures are really only 2D slices of 3D textures, since you can't directly render a 3D texture onto a 2D screen (and I doubt if GL can even project a 3D texture directly without a surface to slice it with).
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Defining the new surfaces when performing an extrusion

Postby Keiji » Thu Nov 06, 2008 2:47 pm

As I'm only interested in rotopes right now, I thought these operations had a strict definition, as in http://teamikaria.com/wiki/Rotope. Objects generated by cartesian products are beyond the scope of my program - extruding a polytope into a new dimension is quite different from taking the cartesian product of two polytopes. Let's stay with rotopes - as you can see, they give me headache enough.


I strongly recommend against using the full set of rotopes as defined on HDDB:
- The immeasurable rotopes are only defined topologically
- The ambiguous rotopes each have at least one point which is never defined to be or not to be in the shape
- The pyramidal tigroids are (as far as I know) not even topologically well defined

You can blame me for all these problems, by the way, since I at-the-time-unknowingly introduced these problems when adding the tapering operation to rotopes, and I regret doing that.

I'd suggest either:
a) ignoring the taper operation and using only the "classic" rotope definition, with extrusion and spheration operations only, which are well defined in all cases, or
b) making your program work with the newer set of bracketopes, which uses square, circular and tegal products, and are well defined in all cases, but does not include the tigroids that you will find in the classic set of rotopes.

Also, the full set of rotopes includes all possible Cartesian products of other rotopes anyway.
User avatar
Keiji
Administrator
 
Posts: 1984
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Defining the new surfaces when performing an extrusion

Postby daemonflower » Mon Nov 24, 2008 4:16 pm

Hayate wrote:I strongly recommend against using the full set of rotopes as defined on HDDB:
- The immeasurable rotopes are only defined topologically
- The ambiguous rotopes each have at least one point which is never defined to be or not to be in the shape
- The pyramidal tigroids are (as far as I know) not even topologically well defined

You can blame me for all these problems, by the way, since I at-the-time-unknowingly introduced these problems when adding the tapering operation to rotopes, and I regret doing that.

I'd suggest either:
a) ignoring the taper operation and using only the "classic" rotope definition, with extrusion and spheration operations only, which are well defined in all cases, or
b) making your program work with the newer set of bracketopes, which uses square, circular and tegal products, and are well defined in all cases, but does not include the tigroids that you will find in the classic set of rotopes.

I have severe difficulties understanding your post. Could you dumb it down a bit for me?

Problem one: I looked up immeasurable and ambiguous rotopes, but their definitions contain more terms I don't understand than terms I do. I'd hazard a guess that immeasurable rotopes are ones which have a taper operation performed on them, but I wouldn't bet much on it.
In order to keep this thread somewhat on-topic, is there a thread anywhere that deals with the basics of rotopes?

Problem two: I don't understand how the taper operations leads to problems at all. At least, not in visualizing rotopes. When I visualize something, I don't care whether all hypervolumes can be calculated (for example). You might consider me an ignoramus because of that attitude, but that's what I'm aiming at - simple visualization, to get an intuitive understanding for higher dimensional objects. I leave the full mathematical understanding to, well, mathematicians. That's not to say I couldn't profit of a better grasp of the maths, of course.
Anyway, the taper operation is the one which lends itself to implementation in software the easiest. It took me less than a weekend to implement it. Extrusion took me way longer (and led me to start this thread in the process). And I have struggled the past weeks with implementing spheration operations properly. Still haven't got it right. So, I'm kind of reluctant to drop taper operations from my program, because then I would be left with... not much.
So what's the problem with objects not being topologically well defined? In terms of visualizing them?

Third problem: I can parse the bracketope definition, but "any shape which can be defined using bracket notation" does not really tell me anything. As far as I can see, there is a tapering operation on bracketopes as well - it just tapers to two opposite points, instead of one. (Is that operation the "tegal product"? I couldn't google anything relevant on that term.) I don't understand how bracketopes fundamentally differ from rotopes. Well, other that there is no operation to generate a torus. I could live without toroidal shapes, although I think they are particularly interesting (but, judging from your post, particularly problematic, too - after all, tigroids are generated by toration operations, aren't they?)
Just as an aside, a question on terminology. Do you include the operation that generates a torus in spheration operations, or not? Just to get a picture of what "classical" rotopes are...

Anyway, to sum it up, I just don't get why tapering operations should be a problem.

Hayate wrote:Also, the full set of rotopes includes all possible Cartesian products of other rotopes anyway.

Now that's good to hear (I think). It's just a different way of arriving at the same point (from a software developer's viewpoint. I don't know if mathematically the two ways are even different.)
If you like this thought, try some more: http://hyperspace-travel.de/blog
daemonflower
Dionian
 
Posts: 18
Joined: Sun Mar 11, 2007 5:10 pm

Re: Defining the new surfaces when performing an extrusion

Postby daemonflower » Mon Nov 24, 2008 4:54 pm

I see that I have to define my terms very carefully when I'm posting here, and I haven't always done that, so I concede the point wherever you called me on it. :)

quickfur wrote:It is true that GL (or anything else for that matter!) can only render 2D surfaces, since the computer screen is only capable of displaying 2D surfaces! However, if you truly want to visualize higher dimensional objects, it is really necessary to know which 2-faces belong to which surtopes/surcells.

That's actually a very good point, and it is taken with gratitude.

To truly understand a higher-dimensional object, you really need to understand that it consists of bounding (n-1)-dimensional facets, and until you can fully grasp this, the object will not make very much sense: it will just generate an incomprehensible tangle of surfaces on the screen. The lower-dimensional surfaces are really merely incidental, and yield very little information about the true geometry of the polytope in its native space.

That is not to say that rendering merely 2-faces is of no help at all; since what else would we use otherwise? (Line-drawings, as I'm sure you're aware, are almost completely useless in visualizing these polytopes; past a certain point, they just start looking like somebody's hair on a bad hair day and give no useful insight at all.)

While I agree that knowing which faces belong to which surcells, I beg to differ on that view. There are two techniques which help me to visualize 4D shapes, even if I don't have that information:
  • Interactively rotating shapes around the rotation planes in four-space
  • Color-coding the vertices according to their depth along the w-coordinate

Which serves to strengthen my gut feeling that I should stay away from visualizing objects generated by the cartesian products - they are way more complicated to treat in a simulation.

Not really. You've almost stumbled upon them without even knowing what a Cartesian product looks like. :)

I think this just underscores the fact that trying to visualize a Cartesian product from a purely set-theoretic point of view (a Cartesian product is the set of all ordered tuples of the constituent sets) is almost impossible past 3 dimensions. However, approaching it from a geometrical viewpoint is much easier. If you're fairly comfortable with the structure of the tesseract, the following page may help you see that Cartesian products are really not to be afraid of:

http://eusebeia.dyndns.org/4d/duoprism.html

Maybe cartesian products aren't hard to understand, but I still believe that they are hard to program. I mean, generically. Of course I'm programming a cartesian product when I perform an extrusion in software - a cartesian product with a square. Tapering is a cartesian product with a triangle, and spheration with a circle. I'm not sure what toration amounts to (is it even a cartesian product?)
Anyway, each of these are special cases. I tried to picture an algorithm to perform a general cartesian product of an arbitrary N-dimensional shape with another arbitrary M-dimensional shape, and failed. The special cases are much easier (although they turned out harder than I thought at first...)
If you like this thought, try some more: http://hyperspace-travel.de/blog
daemonflower
Dionian
 
Posts: 18
Joined: Sun Mar 11, 2007 5:10 pm

Re: Defining the new surfaces when performing an extrusion

Postby quickfur » Mon Nov 24, 2008 8:50 pm

daemonflower wrote:[...]
quickfur wrote:[...]To truly understand a higher-dimensional object, you really need to understand that it consists of bounding (n-1)-dimensional facets, and until you can fully grasp this, the object will not make very much sense: it will just generate an incomprehensible tangle of surfaces on the screen. The lower-dimensional surfaces are really merely incidental, and yield very little information about the true geometry of the polytope in its native space.

That is not to say that rendering merely 2-faces is of no help at all; since what else would we use otherwise? (Line-drawings, as I'm sure you're aware, are almost completely useless in visualizing these polytopes; past a certain point, they just start looking like somebody's hair on a bad hair day and give no useful insight at all.)

While I agree that knowing which faces belong to which surcells, I beg to differ on that view. There are two techniques which help me to visualize 4D shapes, even if I don't have that information:
  • Interactively rotating shapes around the rotation planes in four-space
  • Color-coding the vertices according to their depth along the w-coordinate

Well, I'm not going to argue with you about what works best for you, since you're the only one who can decide that. :) But I do have to say that I've looked at a LOT of line-projections of 4D polytopes before, including interactive rotators and color-coded images, and none of them helped me understand 4D polytopes until one day it dawned upon me that (1) I had to stop thinking in terms of lines and faces, and start thinking in terms of volumes. 4D polytopes are bounded by volumes (hence, 8 cubes bounding a tesseract, etc.), and so surfaces really only amount to the equivalent of skeletal line-drawings. Furthermore, I realized that (2) the reason those line-drawings were so confusing to me was because they did not implement backface culling (in the 4D sense, not in the 3D sense). Once I started thinking about projections with backfaces culled, everything began to make sense. Objects like the 24-cell that I simply could not imagine before suddenly became so simple: in projection, you have 6 octahedra meeting at a vertex, and the outer envelope, which is a rhombic dodecahedron, has 12 flattened octahedra (projected onto each rhombus). This is all a 4D viewer will ever see when looking at a solid 24-cell; the remaining 6 cells are on the far side and are not visible! And they have exactly the same layout as the front cells.

If you've ever tried to visualize a 120-cell without backfaces culled, you'll understand why backface culling is so important. But once you cull the backfaces and think in terms of how the volumes fit together, it is actually not that hard, as I explain here.

Which serves to strengthen my gut feeling that I should stay away from visualizing objects generated by the cartesian products - they are way more complicated to treat in a simulation.

Not really. You've almost stumbled upon them without even knowing what a Cartesian product looks like. :)
[...]

Maybe cartesian products aren't hard to understand, but I still believe that they are hard to program. I mean, generically.

You're kidding, right?

Cartesian products are about the easiest thing you can program in the most generic way. Take the vertices of any n-dimensional polytope, say V1, and take the vertices V2 of any m-dimensional polytope. The vertices of the (n+m)-dimensional Cartesian product of these two are given by points of the form <x1, x2, ... xn, y1, y2, ... yn>, where <x1...xn> and <y1...yn> are all possible combinations of points from V1 and V2, respectively. You just implement this with a nested for-loop and you've got them all. Example:

Code: Select all
for (i=0; i<V1.size; i++) {
    for (j=0; j<V2.size; j++) {
        vector point = concatenate(V1[i], V2[j]);
        result.add_point(point);
    }
}


Once you have the vertices, you just form prisms of each base polytope and attach them around each other. E.g., the Cartesian product of a dodecahedron with a hexagon is a 5D polytope consisting of a ring of 6 dodecahedral prisms and a dodecahedral complex of 5,6-duoprisms (just a scary way of saying 12 5,6-duoprisms laid out in a dodecahedral arrangement). In other words, it's 6 dodecahedral prisms wrapped around a hexagon, and 12 hexagon-pentagon duoprisms wrapped around a dodecahedron.

Of course I'm programming a cartesian product when I perform an extrusion in software - a cartesian product with a square.

No, extrusion is a Cartesian product with a line segment. Cartesian product with a square adds 2 dimensions to the shape, whereas Cartesian product with a line segment adds only 1 dimension. Big difference.

Tapering is a cartesian product with a triangle, and spheration with a circle.

No, that's not right. Tapering cannot be expressed as a Cartesian product, and neither can spheration (although spheration is ill-defined, as far as the current definition used in Rotopes is concerned).

I'm not sure what toration amounts to (is it even a cartesian product?)
Anyway, each of these are special cases. I tried to picture an algorithm to perform a general cartesian product of an arbitrary N-dimensional shape with another arbitrary M-dimensional shape, and failed. The special cases are much easier (although they turned out harder than I thought at first...)

The algorithm is given above. :)

But Cartesian products do not include tapering or spheration, though; if you want those, you need to find other ways of doing it. Tapering is easy; just one a new point, and form triangles with the previous vertices and pyramids with the previous faces, etc.. Spheration... well, we need to define what exactly spheration is, first! :lol:
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Defining the new surfaces when performing an extrusion

Postby daemonflower » Mon Nov 24, 2008 9:59 pm

quickfur wrote:If you've ever tried to visualize a 120-cell without backfaces culled, you'll understand why backface culling is so important. But once you cull the backfaces and think in terms of how the volumes fit together, it is actually not that hard, as I explain here.

Good link, thanks!

Maybe cartesian products aren't hard to understand, but I still believe that they are hard to program. I mean, generically.

You're kidding, right?

Errm no, I wasn't. :oops: Which goes to show that I had not understood cartesian products correctly. Now you put it that way...

Take the vertices of any n-dimensional polytope, say V1, and take the vertices V2 of any m-dimensional polytope. The vertices of the (n+m)-dimensional Cartesian product of these two are given by points of the form <x1, x2, ... xn, y1, y2, ... yn>, where <x1...xn> and <y1...yn> are all possible combinations of points from V1 and V2, respectively. You just implement this with a nested for-loop and you've got them all.

Yes, that's easy.

Once you have the vertices, you just form prisms of each base polytope and attach them around each other. E.g., the Cartesian product of a dodecahedron with a hexagon is a 5D polytope consisting of a ring of 6 dodecahedral prisms and a dodecahedral complex of 5,6-duoprisms (just a scary way of saying 12 5,6-duoprisms laid out in a dodecahedral arrangement). In other words, it's 6 dodecahedral prisms wrapped around a hexagon, and 12 hexagon-pentagon duoprisms wrapped around a dodecahedron.

Not quite as easy, but yes, still no problem.

No, extrusion is a Cartesian product with a line segment. Cartesian product with a square adds 2 dimensions to the shape, whereas Cartesian product with a line segment adds only 1 dimension. Big difference.

Right, my bad. See above.

Tapering is a cartesian product with a triangle, and spheration with a circle.

No, that's not right. Tapering cannot be expressed as a Cartesian product, and neither can spheration (although spheration is ill-defined, as far as the current definition used in Rotopes is concerned).

What is the definition? I could not find it. And what is wrong with it?

This seems to directly contradict

Hayate wrote:Also, the full set of rotopes includes all possible Cartesian products of other rotopes anyway.

Which is correct? Or am I missing something again?

Spheration... well, we need to define what exactly spheration is, first! :lol:

Darnit, spheration. I already noticed that it is trickier than I thought. Isn't there a definition of spheration everyone agrees upon, and can't we just go with that? :)
If you like this thought, try some more: http://hyperspace-travel.de/blog
daemonflower
Dionian
 
Posts: 18
Joined: Sun Mar 11, 2007 5:10 pm

Re: Defining the new surfaces when performing an extrusion

Postby Keiji » Mon Nov 24, 2008 11:34 pm

There's no problem with tapering, and there's no problem with spheration.

The problem lies with when you try to taper something that was previously spherated (and isn't a trivial case i.e. a hypersphere) or when you try to spherate something that was previously tapered. It is in these instances when the operations are ill-defined.

The classic set of rotopes are those which only include the extrusion and spheration operations, so there is no tapering, which means the above problem does not occur.

As far as I can see, there is a tapering operation on bracketopes as well - it just tapers to two opposite points, instead of one. (Is that operation the "tegal product"? I couldn't google anything relevant on that term.)


The operation you describe would be the tegal product of some shape with a line. The tegal product however can do more than just taper to two opposite points, but unfortunately all its other functionality produces 4D or higher shapes which are not so simple to visualize (it took me quite a while before I could understand the meaning of taking the tegal product of two 2D shapes at first).

I don't understand how bracketopes fundamentally differ from rotopes.


By far!

Bracketopes are concerned merely with prismic, tegal and crindal (AKA square, diamond and circular, or max, sum and rss) products of axes. Rotopes are concerned with extrusion and spheration, and possibly tapering. Extrusion and the prismic product with a line is the only actual overlap between the two sets; however, you get a further overlap because spheration happens to do the same thing as crindal product where the arguments are not grouped any further, i.e. they generate a hypersphere. Torii do not exist in the set of bracketopes and crinds and tegums do not exist in the set of rotopes.

(but, judging from your post, particularly problematic, too - after all, tigroids are generated by toration operations, aren't they?)


Tigroids are perfectly well-defined; they were just previously misunderstood (the term strange rotope is thus archaic). The problem comes as I said above with mixing the tapering and spheration operations.

Do you include the operation that generates a torus in spheration operations, or not?


Yes, the spheration operation is used to generate torii; in fact, this is what it usually does, it only generates hyperspheres in the trivial cases of an ungrouped argument.
User avatar
Keiji
Administrator
 
Posts: 1984
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Defining the new surfaces when performing an extrusion

Postby quickfur » Wed Nov 26, 2008 5:39 pm

Hayate wrote:There's no problem with tapering, and there's no problem with spheration.[...]

I have yet to see a precise definition of spheration, even in the case where tapering is not involved.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Defining the new surfaces when performing an extrusion

Postby Keiji » Wed Nov 26, 2008 9:16 pm

In the case of classic rotopes, it's defined by this algorithm.
User avatar
Keiji
Administrator
 
Posts: 1984
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Defining the new surfaces when performing an extrusion

Postby quickfur » Wed Nov 26, 2008 9:55 pm

Hayate wrote:In the case of classic rotopes, it's defined by this algorithm.

Ah, I see. So defining what spheration depends on whether we can express tapering in equation form, since once it is in that form, we can simply apply this definition to it.

Here's a first attempt (it doesn't actually define tapering, but something related, this might help us get to actual tapering): for example, if you have (xy)^z, you expand it by writing (x^2 + y^2 - z^2). IOW, the "exponent" in the notation becomes a negative square term in the group. No constant term is added, unlike the other case. This particular case yields the quadratic cone (the "real" cone, for mathematicians other than geometricists). So it is doing a "tapering" in a sense, but it doesn't stop after the apex and isn't bounded at the base. Maybe somebody can think of a way to add these restrictions.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Defining the new surfaces when performing an extrusion

Postby Keiji » Thu Nov 27, 2008 2:03 am

Subtracting z|z| (that is, z times the absolute value of z) in place of z2 gives a single cone, though it is not bounded.
User avatar
Keiji
Administrator
 
Posts: 1984
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Defining the new surfaces when performing an extrusion

Postby quickfur » Thu Nov 27, 2008 4:37 pm

Hayate wrote:Subtracting z|z| (that is, z times the absolute value of z) in place of z2 gives a single cone, though it is not bounded.

An important question, though, is whether this operation applied to other shapes yields what we think of as a tapering of it (e.g., does subtracting this term from a torus produce a toroidal pyramid?)
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North


Return to Programming

Who is online

Users browsing this forum: No registered users and 5 guests