17-03-2014, 06:12 PM
Abstract
This paper proposes a mesh simplification
algorithm base on quadric error metric. Most of the
simplification algorithms use the geometric distance as
their simplification criteria, the distance metric is very
efficient to measure geometric error, but it is difficult
to distinguish important shape features such as a highcurvature
region even though it has a small distance
metric. The curvature is one of the good criteria of
simplification to preserve the shape of an original
model, if the curvature of the vertex is larger, it can
present the geometric features of model well. Besides
curvature, the size of the incident edges around the
vertex can also reflect the geometric feature, if the
edge lengths that adjoin the vertex are larger, it infects
larger area on the surface of the model. We considered
both the local curvature and the size of the incident
edges around the vertex on the basis of the quadric
error metrics, it can reflect changes on the model
surface and still maintain many important geometric
features after large scale simplified.
Keywords: Surface simplification, quadric error
metric, edge collapse, local curvature, incident edges
1. Introduction
Many computer graphics require complex, highly
detailed models which are often represented using
triangle meshes. Current computer graphics
technologies can render very complex scene. However,
for interactive 3D computer graphics, such as virtual
reality application and flight simulation that require
real-time rendering, in these systems 3D polygonal
models with millions of polygons are burdening some
even with fast graphics hardware. In order to reduce
the data quantity of models and improve the
application efficiency, mesh simplification has been
the subject of a great deal of researches.
In recent years, the representative ones in many
algorithms for reducing the number of triangles in a
surface model are vertex clustering[1], vertex
decimation[2], edge collapse[3], region merge[4],
wavelet transform[5] etc. By contrast, the edge
collapse can collapse edge iteratively which induces
minimum error to a new vertex according to some error
measure rules. it can generate continuous level of detail
approximations, support the progressive transmission
and maintain model topology. The efficiency and
robustness can be improved greatly. So edge collapse
is one of the most powerful tools to simplify triangular
or tetrahedral meshes.
The mesh optimization algorithm proposed by
Hoppe in 1993 is the simplification algorithm in which
edge collapse is introduced earliest[3], the algorithm
simplify model by minimizing the global energy
function. Based on the algorithm, Hoppe proposed
progressive meshes algorithm in 1996[6]. The basic
idea of the algorithm is described as followed: the
basic operation is edge collapse in simplifying meshes,
In order to control the quality of progressive meshes,
collect sample set from the surface of original meshes
M to register the information of original meshes,
compute the energy function based on the distance
between X and simplification meshes and the energy
function show the matching degree of simplification
meshes and original meshes, the operation of
simplifying meshes go in guidance of energy
minimization principle. This algorithm has the
disadvantages of complex algorithm implementation,
large amount of calculation and slow speed. To reduce
time complexity, Garland[7] proposed quadric error
metrics method, in this method, the error of contract is
defined as the sum of squared distances between the
new vertex and a set of planes and the set of planes is
the original planes which is correlated with the two
vertexes of collapsed edge. The method has advantages
of simple calculation, high speed and near
simplification model with Hoppe energy optimization
algorithm, but in this method, only the distance factor
is used, often the simplification meshes distribute
uniformly, so the important geometric features on the
surface of model can not be kept after a large amount
of simplification operations. So in 2003,
This paper proposes a mesh simplification
algorithm base on quadric error metric. Most of the
simplification algorithms use the geometric distance as
their simplification criteria, the distance metric is very
efficient to measure geometric error, but it is difficult
to distinguish important shape features such as a highcurvature
region even though it has a small distance
metric. The curvature is one of the good criteria of
simplification to preserve the shape of an original
model, if the curvature of the vertex is larger, it can
present the geometric features of model well. Besides
curvature, the size of the incident edges around the
vertex can also reflect the geometric feature, if the
edge lengths that adjoin the vertex are larger, it infects
larger area on the surface of the model. We considered
both the local curvature and the size of the incident
edges around the vertex on the basis of the quadric
error metrics, it can reflect changes on the model
surface and still maintain many important geometric
features after large scale simplified.
Keywords: Surface simplification, quadric error
metric, edge collapse, local curvature, incident edges
1. Introduction
Many computer graphics require complex, highly
detailed models which are often represented using
triangle meshes. Current computer graphics
technologies can render very complex scene. However,
for interactive 3D computer graphics, such as virtual
reality application and flight simulation that require
real-time rendering, in these systems 3D polygonal
models with millions of polygons are burdening some
even with fast graphics hardware. In order to reduce
the data quantity of models and improve the
application efficiency, mesh simplification has been
the subject of a great deal of researches.
In recent years, the representative ones in many
algorithms for reducing the number of triangles in a
surface model are vertex clustering[1], vertex
decimation[2], edge collapse[3], region merge[4],
wavelet transform[5] etc. By contrast, the edge
collapse can collapse edge iteratively which induces
minimum error to a new vertex according to some error
measure rules. it can generate continuous level of detail
approximations, support the progressive transmission
and maintain model topology. The efficiency and
robustness can be improved greatly. So edge collapse
is one of the most powerful tools to simplify triangular
or tetrahedral meshes.
The mesh optimization algorithm proposed by
Hoppe in 1993 is the simplification algorithm in which
edge collapse is introduced earliest[3], the algorithm
simplify model by minimizing the global energy
function. Based on the algorithm, Hoppe proposed
progressive meshes algorithm in 1996[6]. The basic
idea of the algorithm is described as followed: the
basic operation is edge collapse in simplifying meshes,
In order to control the quality of progressive meshes,
collect sample set from the surface of original meshes
M to register the information of original meshes,
compute the energy function based on the distance
between X and simplification meshes and the energy
function show the matching degree of simplification
meshes and original meshes, the operation of
simplifying meshes go in guidance of energy
minimization principle. This algorithm has the
disadvantages of complex algorithm implementation,
large amount of calculation and slow speed. To reduce
time complexity, Garland[7] proposed quadric error
metrics method, in this method, the error of contract is
defined as the sum of squared distances between the
new vertex and a set of planes and the set of planes is
the original planes which is correlated with the two
vertexes of collapsed edge. The method has advantages
of simple calculation, high speed and near
simplification model with Hoppe energy optimization
algorithm, but in this method, only the distance factor
is used, often the simplification meshes distribute
uniformly, so the important geometric features on the
surface of model can not be kept after a large amount
of simplification operations. So in 2003,