## Regular vs. Irregular Vertices in a Mesh

Hi everybody,

Reading about Geometry Processing, I have realized that people in this area are very interested in regular vertices(degree=6) rather than irregular ones.

Can anybody give me reasons why this is an important property? Suppose that we can have a mesh with all regular vertices (genus 1) but with a very poor geometry positioning for the vertices.

So, is there any specific reason why connectivity is this much important regardless of the geometry?

Thanks

-
What does this have to do with Riemannian geometry? – Darsh Ranjan Sep 18 2010 at 3:05
You might want to change the tags for this topic to mathematical modeling, rather than riemannian-geometry, unless you have an explanation for why you feel riemannian-geometry is an appropriate tag. – sleepless in beantown Sep 18 2010 at 4:40

Nima, geometry processing is used in meshes for 3-dimensional modeling of real world structures or physical items.

If you try to create a regularly spaced lattice in 3-dimensions such as $\mathbb{R}^3$, a starting point would be the regions of $\mathbb{Z}^3$ which are enclosed by the object in question. That would be the lattice which contains a point at every integer value of $x, y,$ and $z$ within the object's boundaries. If you connect an edge between every two lattice points that are Euclidean distance $1$ apart, $(\Delta x)^2+(\Delta y)^2+(\Delta z)^2 = 1$, then each vertex will have six edges from it leading to the six lattice points at the relative positions $\Delta x=-1$, $\Delta x=+1$, $\Delta y=-1$, $\Delta y=+1$, $\Delta z=-1$, $\Delta z=+1$.

Notice that the boundaries of such a mesh would be clipped and would not match the boundaries of the object. Such a mesh could be extended by having the outermost lattice-points moved from co-inciding with $(x,y,z) \in \mathbb{Z}^3$ to a position in $\mathbb{R}^3$ which is on the boundary of the object. Now, the lattice is no longer regular, but the vertex connectivity is still regular. (Alternatively, additional lattice points could be added on the object boundary in $\mathbb{R}^3$ and connected with the underlying regular lattice, leading to irregular vertex connectivity.)

This sort of 6-connectivity at vertices in 3-dimensions for lattice simulations allows for simulations such as 3-d lattice Boltzman numerical simulations. This type of 6-connectivity is also known as the Von Neumann neighborhood in cellular automata simulations, and in the 2-dimensional case the analogous 4-connectivity Von Neumann neighborhood for a point at $(a,b)$ are the lattice points $(a-1,b), (a+1,b), (a,b-1),$ and $(a,b+1)$.

It is possible to associate a value at every point of the lattice and allow that value to represent a particular material property.

If you take a solid object represented by a 3-d lattice and model applying a physical pressure to it, then the regular object modeled by a regular lattice with regular geometry will become deformed. The lattice points, originally defined as being located at integer values, can be allowed to move in $\mathbb{R}^3$, associating a real value for each of its 3-dimensional coordinates. Thus, deformation modeling can be carried out, such as when an automobile's fender changes its shape in response to a collision with another object.

In the realm of hydrodynamics and computational fluid dynamics, there are two ways to use lattice models with 6-connectivity at each vertex.

In Eulerian models, the lattice points stay fixed while the values associated with the lattice points are recalculated and changed during each step of the numerical simulation.

In Lagrangian models, the lattice points are defined at particular positions (not necessarily coinciding with integer lattice points in $\mathbb{Z}^3$), and the vertices in the mesh are moved in space during steps of the simulation.

If you give me more information about what specific topic you are studying, or what you wish to use "geometry processing" for (mesh creation?, mesh assessment?, mesh refinement?, mesh validation?), perhaps I could provide more detailed answers.

In response to your comment about which is better, what is better has to be defined in terms of the end goal to be reached: numerical precision, model fidelity to the underlying physical objects, speed of computation.

If the numerical precision of the simulator will blow up with slim triangles (for example, triangles with one angle of less than 5 degrees), then it's better to accept irregular vertices. If the simulation would perform better (faster, fewer errors, etc.) with regular and similar vertex connectivity, then allow the irregular triangles and banish irregular nonconforming vertices. There is always a trade-off to make: precision vs. computational time; computational complexity vs.fidelity to the physical object, etc.

It is easier to calculate "subdivision surfaces" for regular meshes. It is easier to speed up calculations at homogeneous regions by using larger triangulations and to have more accuracy at inhomogeneous regions and irregular boundaries by using smaller triangulations.

Tetrahedral meshing has to use non-identical tetraheda, because it is impossible to completely fill space with identical regular tetrahedra. It is possible to fill space with regular cubes or regular rectangles. That is one reason that 6-connectivity at vertices is frequently used in 3-d meshes.

-
 Thanks for your explanations. I am wondering if we have an arbitrary mesh with some irregular vertices, let's say vertices of degree 12, 15, ..., is there any benefit in doing a remeshing which reduces the variance of the vertice's degrees? Because there are some existing remeshing papers in Computer Graphics that try to remove high valence vertices. Now, I wonder which one is better? 1. a mesh with some irregular vertices but good looking triangles. 2. a remeshing of that mesh with less irregular vertices but with very slim and weird triangles. – Nima Sep 18 2010 at 5:06 @Nima, I would think that "better" has to be defined by your ultimate goal. If the numerical precision of the simulator will blow up with slim triangles (for example, triangles with one angle of less than 5 degrees), then it's better to accept irregular vertices. If the simulation would perform better (faster, fewer errors, etc.) with regular and similar vertex connectivity, then allow the irregular triangles and banish irregular nonconforming vertices. There is always a trade-off to make: precision vs. computational time; computational complexity vs.fidelity to the physical object, etc. – sleepless in beantown Sep 18 2010 at 22:47

Some geometric algorithms work better around regular vertices. For example, Loop subdivision is a procedure to turn a triangular mesh into a smooth surface (i. e., a "subdivision surface"). The amount of smoothness varies, however: IIRC, the normal vector to the surface is continuous everywhere, but the curvature is only continuous away from vertices of degree other than 6.

-
 Exactly, I am looking for reasons such as Loop Subdivision. Now, I can only see Subdivision Surfaces and Mesh Compression. Do you know any more? – Nima Sep 18 2010 at 5:07