 |
Consistent Embedding Guaranteed Edge Contraction
Multiresolution modeling is a technique for representing a model with different levels of detail so that the level of detail actually necessary can be rendered. As the complexity of geometric models increases, multiresolution representation of a surface is crucial to achieve realtime rendering in interactive graphics applications. These application include scientific visualization, virtual reality, Computer Aided Design(CAD), flight simulator, and etc.
A number of methods for simplifying a polygonal surface, which is essential to multiresolution repersentation, have been developed over the years. However, they are notorious for introducing inconsistent embedding(self-intersections) which can be fatal for later operations. One popular method, edge contraction, is not exception. With this motivation, we are developing surface simplification using edge contraction which guarantees correct embedding in an efficient way. In addition, we are going to use hierarchical data structure, Directed Acyclic Graph(DAG), to efficiently process query operations, which consist of selecting a complex representing the object according to some user-defined resolution requirements.
What Is a Problem ?
As shown in below figures, a subtle self-intersection may occur when two
different lobes of the surface pass very near one another. The edge contraction
may result in trangles which are pierced by the other lobe. This implies that
searching another surface within the region affected by the contraction,
cannot be done by checking only vertices near the edge to be contracted.
These errors become more feasible as surface meshes get more complex, which
is usual in scientific visualization. We propose simplification method using
edge contraction which guarantees consistent embedding(no self-intersection).
Our approach
A leading idea is constructing BSP tree to decompose bounded space containing
a surface into a set of convex cells, which is easily decomposed into
triangles(2D) or tetrahedra(3D). Checking orientation change to prevent wrong
embedding is also unique feature of our approach. The overview of the edge
contraction algorithm which guarantees consistent embedding is illustrated
in the above figure.
challenging work
To partition a 3 dimensional polyhedral complexes in a robust and consistent
way is not trivial matter. To deal with this problem we adopted robust
splitting scheme, which computes the result using mostly symbolic manipulations
and further reduce any numerical computations as much as possible. Another work
to be done is how to deal with the situation that there is no edge to be
contractible. Proper retriangulation is expected to be a solution.
|
|
|
