Regular vs. Irregular Vertices in a Mesh - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T15:42:11Z http://mathoverflow.net/feeds/question/39184 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/39184/regular-vs-irregular-vertices-in-a-mesh Regular vs. Irregular Vertices in a Mesh Nima 2010-09-18T01:21:26Z 2010-09-20T14:33:39Z <p>Hi everybody,</p> <p>Reading about Geometry Processing, I have realized that people in this area are very interested in regular vertices(degree=6) rather than irregular ones.</p> <p>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.</p> <p>So, is there any specific reason why connectivity is this much important regardless of the geometry?</p> <p>Thanks</p> http://mathoverflow.net/questions/39184/regular-vs-irregular-vertices-in-a-mesh/39196#39196 Answer by Darsh Ranjan for Regular vs. Irregular Vertices in a Mesh Darsh Ranjan 2010-09-18T03:29:03Z 2010-09-18T03:29:03Z <p>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. </p> http://mathoverflow.net/questions/39184/regular-vs-irregular-vertices-in-a-mesh/39200#39200 Answer by sleepless in beantown for Regular vs. Irregular Vertices in a Mesh sleepless in beantown 2010-09-18T04:37:03Z 2010-09-20T14:33:39Z <p>Nima, geometry processing is used in meshes for 3-dimensional modeling of real world structures or physical items.</p> <p>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$.</p> <p>Notice that the boundaries of such a mesh would be <em>clipped</em> 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.)</p> <p>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)$.</p> <p>It is possible to associate a value at every point of the lattice and allow that value to represent a particular material property.</p> <p>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.</p> <p>In the realm of hydrodynamics and computational fluid dynamics, there are two ways to use lattice models with 6-connectivity at each vertex.</p> <p>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.</p> <p>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.</p> <p>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.</p> <p>In response to your comment about which is better, what is <strong>better</strong> 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.</p> <p>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 <em>trade-off</em> to make: precision vs. computational time; computational complexity vs.fidelity to the physical object, etc.</p> <p>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.</p> <p>Tetrahedral meshing <em>has</em> 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.</p>