Mesh orientability
A mesh
is orientable if all triangles are oriented towards the same side; in
other words, normal vectors for all triangles, which are calculated
using orientation of the three edges belonging to a triangle, must
point consistently to the same side of the mesh.
A mesh is
orientable if, for all half-edge having one neighbor half-edge alone,
both half-edges have opposite senses (two neighbor half-edges share
the same two faces). The algorithm must walk all triangles, and for
each triangle, it must walk its three half-edges. Now, current
half-edge must be found inside the remaining triangles in the mesh.
The mesh is orientable if, for all half-edge which a neighbor
half-edge has been found, both have opposite senses.
Indirectly,
we are extending topological information stored in the mesh. For the
starting mesh we only stored the adjacency relationship F:{V}, and
now we are using the relationships F:{E} and E:{F}, because we need
the half-edges. For other calculations presented below we may need
other relationships like E:{V} and V:{F}. All of them can be easilly
calculated using a walk over the triangle mesh lists.
Calculation
of borders and non-manifold areas
A mesh has
borders if has some half-edges without neighbors. A mesh has
non-manifold edges if we find some half-edge with more than one
neighbor.
Algorithm is as follows:
for each triangle t of the mesh do
SearchCount (t.V1,
t.V2) ; if ni=0 and nd=0 then
AddBorderList (t.V1, t.V2 ) endif
SearchCount (t.V2,
t.V3) ; if ni=0 and nd=0 then
AddBorderList (t.V2, t.V3 ) endif
SearchCount (t.V3,
t.V1) ; if ni=0 and nd=0 then
AddBorderList (t.V3, t.V1 ) endif
endfor
Procedure SearchCount (V,W) searches and counts how many times
the half-edge (V,W) is found in the remaining triangles of the mesh
(excepting t). At the end,
nd is the number of times we have found the half-edge (V,W)
ni is the number of times we have found the half-edge (W,V)
After procedure SearchCount, we have some options:
If nd and ni are null, the edge belongs to the surface's border
If nd=0 and ni=1, the half-edge is correct
If nd=1 and ni=0, we have a non-orientable case
In all other cases, a situation of non-manifold has been detected
In the previous algorithm edges on
the border are stored in a list, but we could have some other lists
and store other kinds of half-edges in them: non-orientable areas,
non-manifold areas
When algorithm is finished and borders have
been detected, we can colorize half-edges in the list in a different
color in order to highlight them, find cycles inside the list and
colorize those cycles with another color, etc.
Quality
of the mesh
The quality of a mesh is measured
by the quality of its triangles. The quality of a triangle can be
measured using its angles:
Q = MinimumAngle / SumAngles (where SumAngles=180)
Or using its edges length:
Q = MinimumEdgeLength / Perimeter
As we can see, the quality Q of a triangle is a value between
zero and 1/3. A value Q=1/3 means an equilateral triangle. Very small
values for Q means degenerate triangles. Using the angle measurement
is generally better, because it can detect isosceles triangles
degeneration with two very small angles (it can be checked that, in
this case, quality using the edge length measurement is not lower
than 1/4).
In a mesh we can search and detect the triangle
with lowest quality, detect and/or colorize areas with triangles with
less quality than a given value, etc. Low-quality triangles (highly
degenerate) may produce some problems in geometric algorithms and
when rendering them.
Self-intersection
detection
It is important to detect if a mesh
is self-intersecting. This is the most complex issue, because
intersection test and checks must be performed on all triangle pairs
of the mesh. As you can see, this test is quadratic. It can be
accelerated with spacial subdivision techniques, sotring triangle
meshes in an octree or BSP tree.
The triangle-triangle test
consists simply of six edge-triangle tests (edges from a triangle
against the edges of the other, and vice versa). Therefore,
edge-triangle test must be optimized. Usually it begins by checking
if one of the edge's extremes is located in a different side of the
supporting plane of the triangle. If so, the thing to do is to test
the orientation of tetrahedra formed with the 5 participant
vertices.
Calculation of topological
features
If the mesh is correct and encloses a
volume (this can be checked with prior tests, checking orientability,
non-borders, non-self-intersecting), we can calculate its topological
features and check if Euler's formula C+V=A+2(S-H) is
satisfied. If the mesh is not correct, many geometric algorirthms
will fail. The only solution in this case is repairing the mesh and
fixing it.
We can know C and V from the number of elements of
both lists. As we know that 3*C=2*A, we can calculate the number of
edges A. With a simple algorithm of vertex flood we can detect the
number of shells S:
S:=0;
while
non-marked vertices remaining do
Choose a first
vertex v ; Mark(v) ; Add all its neighbours (following relationship
V:{V} ) to a stack
while vertices on stack remaining
do
v:=pop(Stack)
Mark (v)
Add all its non-marked neighbours to the stack
endwhile
S:=S+1
endwhile
Finally, the number of handles H
can be known finding its value in the Euler's formula, since we know
the rest of variables at this point.
Tangent
plane and curvatures
The tanget plane to a mesh
at a vertex is the perpendicular plane with respecto to the normal
vector. As we know a way point (the vertex itself), the problem is
equivalent to the problem of calculating the normal vector.
An
option for calculating the normal vector is the calculus of the
normal vector of the “crown” polygon of the vertex, using the
formula teached in VIG (see geometry chapter in VIG disk). The
“crown” polygon of a vertex v in a mesh is the polygon consisting
of all vertices which are located at a one edge distance from v (in
other words, it is the polygon consisting of vertices in list v:{V}
).
A second option for calculating the normal vertex to a
vertex v in a mesh is to calculate the weighted vector of all
neighboring faces to v, depending on its area::
normal := 0
for
each face c neighbor of v do
normal := normal + c.normal / Area(c)
endfor
Normalize(normal)
If we want to estimate the
curvature of a vertex v in the mesh, we can use the method proposed
by Gabriel Taubin: in first place, calculate the normal vector to v
and the tangent plane (pi). Then, for each edge converging to v, we
calculate the plane pi_a as the plane going through a and
perpendicular to pi. This plane pi_a is the normal plane to the
surface at v, and follows a direction. Now, with a simple geoemtric
calculation, we calculate the curvature radious of the normal
section, defined by plane pi_a: within plane pi_a, it is the radious
R of circumference passing through v and the other extreme of edge a,
and which is additionally tangent, at v, to the line at the
intersection of planes pi and pi_a. This radious R has positive sign
if the center of the circumference is on the opposite sense with
respect to the normal vector from point v, and negative sign
otherwise. The normal curvature at v in the direction of edge a is
1/R. Once we have calculated these curvatures for all edges, Taubin
calculates a quadric which approximates the surface at v. Calculating
its values and eigenvectors we have finally the curvatures and
principal directions.
Surface and volume
enclosed by the mesh
When the previous checks
have been performed, and we found that the mesh is correct, then we
can apply the BRep model algorithms in section 2.2.3.