Interactive Graphics Systems


Triangle meshes models


There exist very efficient algorithms for mesh compression, optimizing the transmission time over the network, for instance. See Pajarola'99



As we have seen, a triangle mesh is usually represented with two lists or arrays: one for triangles and one for vertices. Every triangle has three vertex pointers (as other information like color), and each vertex is represented by its (x,y,z) coordinates.

A point cloud model is just an array or list of points. Each point may have additional information apart from its coordinates, such as color, normal vector, etc. The basic difference with triangle meshes is that there is no information about point connectivity.

A volume model (voxelization) is an array containing information on a regular N x N x N mesh of uniform cells that divide a universe cube in space. This mesh consists of cells, all having the same size, limited by mesh edges and vertices. There are a number of variants of volume models (encoding one or more objects using information of mesh vertices inside / outside object, encoding one or more objects using information of mesh vertices inside /outside object and information about intersection points and normal vectors between object surface and mesh edges, etc.). Here we focus on volume models that represent scalar fields, storing a scalar value in each mesh vertex: array [0..N, 0..N, 0..N] of float. A particular case of volume models that represent scalar fields is distances fields. In this case, the value stored at each mesh vertex is the value of the distance (signed or unsigned) to the object surface being represented. Instead, we say that a voxelization is binary if information stored in vertices is just in / out.

We can convert a triangle mesh in a point cloud simply removing the list of triangles. If the triangle mesh contains too large triangles, a more precise sampling that generates points inside triangles may help.

On the other side, converting a point model into a triangle mesh is not so trivial. This is called the reconstruction problem. There are several solutions, like Alpha Shapes algorithms (and derivatives from them), discrete membrane reduction-based algorithms or Hornung and Kobbelt algorithms, based on calculate the minimum cut of distances field delimited by a discrete crust. Point clouds can be operated and visualized, see for instance the PointShop project: www.pointshop.com

Calculate a volume model (field of distances) from a triangle mesh is not so complex. It needs the minimum distance from each point in the mesh to triangles of the mesh. This calculations can be accelerated by obtaining, in first place, the distance from cell's vertices that contain surface's triangles to the mesh itself, and then these values are extended to the rest of the vertices of the mesh.

There exist two classical algorithms that allow transforming a volume model to a triangle mesh: the Marching Cubes algorithm and the Dual Contouring algorithm. More information about these algorithms in section 2.5.

Volume models are often interesting as an intermediate model for performing some operations:

Some further reading