Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
825 views
in Technique[技术] by (71.8m points)

algorithm - How do I get a 3D cross section of a 4D mesh?

I have a polychoron represented as a four-dimensional mesh, stored with the face-vertex method. All the faces are triangles. How can I get a three-dimensional cross-section of the figure?

The closest thing I've found is this question, but it's one dimension short.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

Working with 4 dimensions are a bit difficult.

The only way to solve the problem is finding dimensional analogies.

Let's start from 2D

A convex 2D polygon has convex 1D sides: line segments.

The cross-section of a filled convex polygon is a line segment.

Calculate the intersection points of your poligons edges with the intersecting line, you'll get two intersections for a convex polygon, and the cross section will be a line segment.

To do this easily transform the coordinates so you do the cross section on the Y axis of the coordinate system. The two points of the edge is A and B. Their coordinates are a1, a2 and b1, b2.

If the signs of a1 and b1 is the same, (aka a1*b1 > 0) the edge won't intersect the Y axis.

Otherwise calculate k = a1/(a1-b1).

Then the coordinate of the intersection point will be: (0; (1-k)*a2+k*b2)

As I said for convex polygons you'll get two intersection points, connect the two point to get the 1D cross section.

Now let's generalize to 3D

A convex 3D mesh has convex 2D sides: triangles.

Again, transform the coordinates to make the operation easier. Let's get the cross section of the mesh on the Y-Z plane, so the X coordinates will be zero again.

Get the cross sections of the triangles. Using the algorithm above for each edge of them. Since we have 3 dimensions the endpoints of the edge will have the coordinates a1, a2, a3 and b1, b2, b3. If a1*b1<0 we have an intersection point. So

Let k = a1 / (a1 - b1)

The coordinate of the intersection point is (0; (1-k)*a2+k*b2; (1-k)*a3+k*b3). Store this coordinate, but also store the index of A and B points of the mesh (the edge index). It'll be useful later.

For each triangle this will yield a line segment.

Now you'll need to connect these cross section line segments to a polygon. That's why we stored the edge indexes along with the intersection points. You have a set of lines and you can match their endpoints by the stored edge index, so you can connect them into a polygon.

Now let's generalize to 4D

A convex 4D mesh has convex 3D "sides": tetrahedrons. (note probably your face-vertex representation is incorrect)

Again, transform the coordinates to make the operation easier. Let's get the cross section of the mesh on the Y-Z-W hyperplane, so the X coordinates will be zero again.

Get the cross sections of the tetrahedrons. Using the algorithm above for each face of them. Since we have 4 dimensions the endpoints of the edge will have the coordinates a1, a2, a3, a4 and b1, b2, b3, b4. If a1*b1<0 we have an intersection point. So

Let k = a1 / (a1 - b1)

The coordinate of the intersection point is (0; (1-k)*a2+k*b2; (1-k)*a3+k*b3; (1-k)*a4+k*b4).

For each triangle of a tetrahedron this will yield a line segment. For each tetrahedron this will yield a triangle. For each edge of these triangles also store the index of A, B and C points of the triangle of the 3D mesh (the face index) the line segment originates from. It'll be useful later.

Now you'll need to connect these cross section triangles to a 3D mesh. That's why we stored the face indexes along with the intersection edges. You have a set of triangles and you can match their edges by the stored face index, so you can connect them into a triangle mesh.

For concave 4D meshes you may have get multiple 3D meshes.


Hope you see the analogy.

The concrete implementation will be a bit diffcult, you'll need to take care of all corner cases (division by zero cases, floating point errors, etc).


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...