Computing surface normals in projected 2-manifolds

Discuss interdimensional programming, Java applets and so forth.

Computing surface normals in projected 2-manifolds

Hi All,

I have a little problem I'm trying to solve in my polytope viewer. The basic idea is this: I want to render some 4D objects with curved surfaces (e.g., the cubinder) by approximating said surfaces with ridges. These ridges are projected from 4D to 3D, and then broken up into triangles so that povray can render them. For best results, I'd like to interpolate surface normals in the resulting 2-manifold, so that it will actually appear as a smooth surface instead of a faceted surface.

However, here's a little problem here: a 2-manifold projected from 4D can be oriented either way (surface normal pointing one direction or its opposite direction). For individual ridges, we can simply pick any direction and it will be fine; however, to have consistent interpolation between adjacent ridges (triangles), there needs to be a way to consistently pick a normal direction so that adjacent ridges will be oriented the same way. (Otherwise, normal interpolation will go haywire.) But there is no guarantee that the projected 2-manifold is actually orientable! (E.g., if one projects the Klein bottle...)

Barring non-orientable surfaces, is there an efficient algorithm to compute surface normals such that the normals for each ridge will be consistent with its neighbours? Normally, for auto-generated 3D surfaces, this is not a problem because the generating code already knows which way the normals should point; the problem here is that we are projecting from 4D, and in 4D 2-manifolds don't have "surface normals". So we are given a set of ridges (triangles) projected to 3D, and we need to consistently compute surface normals for them.

Any hints?
quickfur
Pentonian

Posts: 2559
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Computing surface normals in projected 2-manifolds

Pick a point inside the object, then the normal for any face points away from that point if the number of other faces crossed by the line segment joining the point to the face is even, otherwise it points towards the point.

Alternatively pick a point outside, and do the same but reversing away from/towards.

I'm not sure exactly what you wanted though, so I'm assuming I got the right idea

Keiji

Posts: 1962
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Computing surface normals in projected 2-manifolds

Hayate wrote:Pick a point inside the object, then the normal for any face points away from that point if the number of other faces crossed by the line segment joining the point to the face is even, otherwise it points towards the point.

Alternatively pick a point outside, and do the same but reversing away from/towards.

The problem is that there may not be an "inside" at all. This is a 2-manifold that may form only a part of a 4D object's surface, so it may only be an incomplete patch. So there is no well-defined "inside". For example, if we approximate the ridge of a duocylinder with polygons, and project it into 3-space, which direction should be the "inside"? In 4-space, there is no inside because the entire manifold lies on the surface of the object. In the 3-space projection, there may not be an inside either, since the projected image probably will not enclose any 3D volume.

And there will also be visibility clipping on it.
quickfur
Pentonian

Posts: 2559
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Computing surface normals in projected 2-manifolds

Then pick any arbitrary point, render both images and manually pick the best one.

Keiji

Posts: 1962
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Computing surface normals in projected 2-manifolds

Hayate wrote:Then pick any arbitrary point, render both images and manually pick the best one.

No no, the problem is that you have a set of polygons, each with vertices ordered arbitrarily in one of the two possible cyclic orders. The cyclic orders of two adjacent polygons are not guaranteed to have the same sense (clockwise/counterclockwise). The problem here is to find an algorithm that reorders (if necessary) the cyclic order of some of the polygons so that the resulting set has cyclic orders of the same sense.

It doesn't matter which sense we pick, as long as it is consistent across all polygons in the set.

Once the polygons have compatible cyclic orders, we can then form the cross products of 3 vertices in each polygon in that order, and the resultant normals will be guaranteed to be compatible with each other.

To understand why this is necessary, consider, say, a mesh of 6 triangles that tile a nonplanar hexagon. If we just blindly take the cross products of the triangle vertices in any order, some normals will point up and some will point down. We can't sanely interpolate normals in this case, because they will vary from a positive vector to a negative vector where there is no actual "flip" in the surface's curvature. (You may also get zero at some points, which is ridiculous.) So we must reorient the triangles so that the normals always points up (or down, it doesn't matter which as long as all of the triangles have normals pointing the same way).

Of course, this doesn't work if the surface is non-orientable.
quickfur
Pentonian

Posts: 2559
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Computing surface normals in projected 2-manifolds

quickfur wrote:To understand why this is necessary, consider, say, a mesh of 6 triangles that tile a nonplanar hexagon. If we just blindly take the cross products of the triangle vertices in any order, some normals will point up and some will point down. We can't sanely interpolate normals in this case, because they will vary from a positive vector to a negative vector where there is no actual "flip" in the surface's curvature. (You may also get zero at some points, which is ridiculous.) So we must reorient the triangles so that the normals always points up (or down, it doesn't matter which as long as all of the triangles have normals pointing the same way).

My algorithm works for this example - perhaps you didn't understand the idea or are the conditions different for 4D objects?

Keiji

Posts: 1962
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Computing surface normals in projected 2-manifolds

Hayate wrote:My algorithm works for this example - perhaps you didn't understand the idea or are the conditions different for 4D objects?

Did I misunderstand what you meant? You said "render both images" - of what? A single face, or the entire 2-manifold? What did you mean by "manually pick" - run the program N times to correctly render N faces? Maybe I misunderstood what you meant, but manually picking (i.e. by the user) an orientation for each face is not feasible, because I may be using hundreds and thousands of faces to represent a projected 2-manifold.

In any case, don't worry about it... I've found a way to solve this problem, and I have code that's working. It only works with orientable manifolds; it works by recursively orienting a face relative to its neighbours (we can't do this relative to the space it's immersed in, because a 2-manifold in 4D has infinite possible orientations). Once projected, this results in an oriented 2-manifold in 3-space, with its faces compatibly oriented relative to each other, so this works for normal interpolation.

Well, what's the point of rambling, when an actual rendered image will do:

This is a cubinder, projected into 3-space, viewed at an angle in 4D. I turned off visibility clipping so that you can see the cylindrical cells. It's actually a 4,24-duoprism, with normal interpolation applied to the rings of 24 rectangular ridges so that it approximates the curved ridges of the cubinder.

Here's another view of it:

Note that these are perspective projections, so you get a fair amount of foreshortening.

Actually, there is another kind of "interpolation" being applied here: the cubinder also has a 3-manifold in the shape of a square torus; this manifold is approximated by 24 square prisms. This fact is hidden by the fact that my program also does "virtual ridge" removal: a ridge is considered "virtual" if it lies between cells that approximate a 3-manifold. Virtual ridges are rendered only if they lie between a cell facing the 4D viewpoint and a cell facing away from the 4D viewpoint (IOW, it lies on the projection envelope). They need to be rendered in this case so that the cubinder is "capped" properly by squares in the rendered image, but they are hidden in other cases since the 3-manifold should appear smoothed, not ridged.

There is actually a third kind of "interpolation", which is needed to properly render spherically-curved 4D objects such as spherinders, but I haven't implemented this yet. So, no spherinders as yet. But duocylinders are definitely in. :-) I'll post pictures at another time, once I fix the highly b0rken 4D orientation code (duocylinders are no fun unless you can animate them!)
quickfur
Pentonian

Posts: 2559
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Computing surface normals in projected 2-manifolds

quickfur wrote:
Hayate wrote:My algorithm works for this example - perhaps you didn't understand the idea or are the conditions different for 4D objects?

Did I misunderstand what you meant? You said "render both images" - of what? A single face, or the entire 2-manifold? What did you mean by "manually pick" - run the program N times to correctly render N faces? Maybe I misunderstood what you meant, but manually picking (i.e. by the user) an orientation for each face is not feasible, because I may be using hundreds and thousands of faces to represent a projected 2-manifold.

The algorithm is this:

1. Pick any point with random floating-point coordinates.
2. For each facet in the object, draw a line from the point to the facet.
3. If said line intersects an even number of facets, the normal of the target facet points one way (either towards or away from the point), otherwise it points the other way.
4. If by mere fluke the line happens to be perpendicular to the normal, it is impossible to solve the orientation for that facet, so pick a different point and try again (though this is very unlikely to happen since the point had random floating-point coordinates).
5. Render the image with those normals.
6. Repeat 1-5, reversing the directions of the normals.
7. Now you have two images, a right one and a wrong one. Manually pick the correct image.

But, I'm glad you solved the problem anyway - very nice images of the cubinder there!

Keiji

Posts: 1962
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Computing surface normals in projected 2-manifolds

Hayate wrote:[...]The algorithm is this:

1. Pick any point with random floating-point coordinates.
2. For each facet in the object, draw a line from the point to the facet.
3. If said line intersects an even number of facets, the normal of the target facet points one way (either towards or away from the point), otherwise it points the other way.
4. If by mere fluke the line happens to be perpendicular to the normal, it is impossible to solve the orientation for that facet, so pick a different point and try again (though this is very unlikely to happen since the point had random floating-point coordinates).
5. Render the image with those normals.
6. Repeat 1-5, reversing the directions of the normals.
7. Now you have two images, a right one and a wrong one. Manually pick the correct image.

Actually, I'm quite aware of this algorithm; however, it doesn't work in this case because the 2-manifolds I'm dealing with, which are perhaps better called 2-manifold patches, are not necessarily closed. In fact, after projecting to 3D, they may even self-intersect. So the number of intersections with a line does not give any information about how it should be oriented.

But, I'm glad you solved the problem anyway - very nice images of the cubinder there!

Thanks! Oh, is there a way to upload images to HDDB? I'd like to post some of these images there.
quickfur
Pentonian

Posts: 2559
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Keiji