Meshes from Surfaces

Generalization

The problem can be viewed generally as one of tessellation. That is given a shape tessellate it. This is then extended to include shapes with holes.

Since holes can be made from the subtraction operation then a description of the shape including the holes can be turned into a shape with inner parts subtracted from the main shape.

So now the tessellation could be achieved by tessellating the main shape, then subtracting the inner holes. Applying some mesh re balancing algorithm on the mesh to have balances simplexes.

Mesh Re Balancing

Given a mesh, re tessellate it so that the triangles are balanced. This would require boundary/surfaces to be constrained so that the tessellation does not change the geometry. The advantage of such an operator in the linked simplex mesh is that it is generic. It is written once and used for any other algorithm or situation that needs it.

Contrast this with other algorithms which first have to connect the mesh (to an equivalent linked simplex structure).

Triangle Strips and Fans and Meshes

This operation would be incredibly useful on linked simplex meshes. The applications for rendering are interesting.

The process of forming triangle strips from a triangle mesh is the game. It is known to be NP hard. How the linked nature of the mesh could be of use in the algorithms I do not know and will have to look into this. <TODO>

Mesh Subtraction

The subtraction of one mesh from another is definitely a general operation and is used in clipping algorithms. Although models with holes can be described, since the tessellation is undefined it is easier to identify the ssurfaces of the objects and use a generic operator to get the outcome, rather than think of the end resulting tessellation and try to directly tessellate two or more surfaces. For example if there are two holes.

Surfaces and Half Spaces

Half spaces and the surface can be used to define a shape.

One strategy is to tessellate all the points as a convex hull, then iterate over the surfaces and each of its half spaces, deleting simplexes that are not in the shape by following the surface.

This will cut the convex mesh so that the target shape will be one of the mesh partitions. For example in 2D consider an inner hole cut out. The cutting out of a hole produces two meshes, one with say a circle and the other with the remaining mesh.

This could be viewed as subtraction. However all points need to already exist in the mesh so this operation is specific to the linked simplex mesh.

3D

In 2D a polygon can be given as an ordered list of points. This is actually a list of lines, So the half space information can be included. In 3D we need a list of polygons. Obviously a surface is one dimension less than the space it is in.

In 3D the surfaces have to be able to be joined together, so the list of polygons must be logically consistent. Exclude T-intersections, so the algorithm can work in 3D.

ie
Build a convex linked simplex mesh in 3D with the points. Let the polygons have the correct winding so that their orientation is outward. Iterate over the list of polygons deleting the neighboring simplexes.

Now the polygons are not simplexes and are not convex. So a sub algorithm is needed to guarantee the inner surface of the mesh corresponds with the polygon. Then iterate over this inner surface deleting simplexes.

Here is an example of polygons which form a consistent mesh. These can be fed into the algorithm as there are no T intersections.

Each polygon could be tessellated into triangular surface with the correct winding. Then this surface could be realized in the convex mesh of all the points, then apply clipping. We need the surface to be broken into triangles as these make up the surface of the tetrahedrons in the linked simplex mesh.

Surfaces from Points

The humble point cloud is still a great way to visualize a surface. The problem with points is with depth. For example OpenGL displays points independent of depth with the same intensity. Point clouds are not realistic too.

Once a mesh has been found there are many different algorithms to smooth it. For example in 3D there are Bernstein patches. So a strategy is to construct a skeleton of points and then apply such an algorithm to generate the skin.

Generate a skeleton of points on the surface
Use a surface generation algorithm with this set of points.

Surfaces from sweeping points thorough time with parametric equations are hard to describe some surfaces, for example the two holed donut.

Essentially the idea is to generate surfaces from a point cloud. The points have no assumed order - contrast this with sweeps and other methods.

For closed surfaces that define a partition we can use convex tessellation.

Convex tessellation on the surface points.
Cut away simplexes that are outside the partition to generate the skeleton.

When a solid mesh is used with the tessellation then integration (summing of areas and volumes) is possible. For example the algorithm to generate the skin could then locally allow the surface (or mesh region) to be integrated, as at a basic level any amount of points on the outside skin can be generated from such algorithms.

<TODO>

Implement a Klein bottle in software.
Implement a 2 hole donut.
Find a partition function to describe the donut. Generate points on the surface and tessellate the convex hull. Then cut away tetrahedrons outside the donut.