Chelton's Convex Mesh Algorithm : Orientation and Movement

Orientation and Movement

The tessellation has a current state. A virtual primitive shape and the mesh is the current state. This is made up of two components.

1. The cp which is a pointer to the current primitive shape.
2. The orientation which is one possible position of the primitive shape relative to the primitive shape in the mesh. (ie a permutation of the primitive shape)

2D Orientation and Movement

Consider a triangle. You can rotate it in three possible positions. Naturally you give the state two operations : rotate anticlockwise and rotate clockwise.

The orientation is naturally coupled with movement through the tessellation. For example consider movement through a 2D tessellation. There is only ever two possible movements relative to the current triangle pointer. Move left or move right.

Here movement from one triangle to another leaves the inner pointer bordering where it came from. This seemed to me the obvious way to define movement.

The following operators allow you to move freely in the 2D triangular mesh.

• anticlockwise
• clockwise
• moveleft
• moveright
• movedown

These operators are not minimal. The clockwise operator is equivalent to the anticlockwise operator applied twice. Moving left is equivalent to clockwise movement and down. Moving right is equivalent to anticlockwise movement and down. So by defining two operators anticlockwise and down we can build the other operators.

3D Orientation and Movement

In 3D the situation is similar. Consider rotation of the virtual tetrahedron. Since an orientation is described by its base, rotating the virtual tetrahedron is equivalent to moving a triangle over a tetrahedron's surface.

Since a tetrahedron surface is in 2D and the operators work in 2D the operators can be used to freely move about in orientation on the tetrahedrons surface. In 3D I have kept the operators name move to mean a move in 2D but restricted to the current tetrahedrons surface.

But a real move is moving from one primitive shape to another. In 3D there are three such possible movements corresponding to the three sides opposite the orientation's base triangle.

1. tetmoveleft
2. tetmoveright
3. tetmovedown

As an aid in seeing the tetrahedrons orientation the orientation triangle can be drawn in different colors in the front and back faces. The green tip is the up direction. Green-Red is seeing the tetrahedron face from the outside and Green-Purple is looking into the tetrahedron.

The tet move preserves the orientation in the sense that the orientation is fully defined from one move to the next because the base pointer borders the triangle of the previous tetrahedron.

At first I considered doing moves without regard to the orientation but from an algorithms and users perspective you may then have to ask which orientation I am in. So having orientation fully defined between tet moves made sense.

It is now possible to move freely within the tetrahedron mesh with the following operators.

• anticlockwise
• clockwise
• moveleft
• moveright
• movedown
• tetmoveleft
• tetmoveright
• tetmovedown

With the minimal operators and the others in terms of these

• anticlockwise
• movedown
• tetmovedown

Maybe each tessellation dimension adds a minimal operator. From a coding perspective this means only n operators need to be defined for movement in n-dimensions which is less code to write.

3D Operators

In 2D there are two movement operators and two orientation operators. In 3D three more operators were added. The data structures become more difficult to manage.

The simplest representation of an orientation is by a permutation of its points. Operators are defined on this and the linked data structure.

For operators effecting the tetrahedrons surface only the virtual tetrahedrons permutation state only needs to be changed.

Surface Transversal Operators

Permutation of the virtual tetrahedron.

Movement of cp Operators

These operators are between two adjacent tetrahedrons x and y where x is where cp points to. Unlike the surface transversal functions are applied to solve for the virtual tetrahedron. This is related to finding the inverse of a virtual tetrahedron. Here are the functions.

y.p_i^-1(x.p_i)   for i=0..2
y.n₃^-1(cp)

The inverses on the points asks given this point what is its local index. Similarly given the neighbor what is its local index.

If you were wondering why the neighbors inverse is used, its because of the primitive shape data structure where an index of a point is opposite its neighbor's face. This just happened to be a convenient way of getting the fourth index, other ways are possible such as subtracting the other indexes from {0,1,2,3} and the remaining index is the fourth index.

Boundary Transversal Operators and Operators in General

Are Operators Needed for this Algorithm

With a current pointer cp everything could be implemented so there may not be a need to explicitly have a virtual primitive shape with the orientation. So from a minimalist point of view the answer is no.

Having said that there use in the algorithm is important as they suggest solutions. For example determining the fan of a point to the mesh is made easier by their existence.

For debugging purposes such as mesh verification, visually checking orientations, half space orientation, and experimenting with movement in the mesh they are very useful. Indeed many math systems put operators as part of their axioms and then build the theory. They may also possess computational advantages that I am not aware of.

Theoretically they are important in looking at the algorithm in different dimensions. Notably a higher dimension uses operators of the lower dimension. Further a operation in one dimension can be explained or generalized with the use of operators - see Rotation.

Operator Names and Symbols

Since the list of operators grew in 3D I decided to use symbols for the operators as they make a list of operations so much more concise. While these operators probably form groups I have not looked at them from a maths perspective but rather an operational perspective.

Someday I hope to bump into a mathematician who knows heaps about the operators movements and properties, but for now I am just trying to get this thing working.

V is abbreviation for virtual, B is abbreviation for the boundary and T is abbreviation for tetrahedron. AC and C are short for anticlockwise and clockwise. L for left, R for right and D for down.

Rotation

Rotation in 2D is rotation about a point, and generalizes in 3D to rotation about a line. This became apparent when I was building the boundary transversal operators.

Let the operators base be on the boundary. By definition the operator V_B orientates the virtual shape towards the boundary if it exists by rotating the current virtual shape.

In 2D
    B_L=V_L...V_C
    B_R=V_R...V_AC

In 3D
    B_D=T_D...V_RV_RV_AC   or   T_D...V_LV_LV_A
    B_L=V_CB_D
    B_R=V_ACB_D

These even work in degenerate cases where the adjacent surface is on the same tetrahedron.