Browse Prior Art Database

Smoothing Method for Polygonal Data

IP.com Disclosure Number: IPCOM000118118D
Original Publication Date: 1996-Sep-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 4 page(s) / 126K

Publishing Venue

IBM

Related People

Koide, A: AUTHOR [+3]

Abstract

Disclosed is a method for smoothing polyhedral data by exchanging edge connections and moving vertex positions according to a smoothness measure which is defined by the deflection angles of the adjacent faces and edge lengths. The proposed method is useful in smoothing isosurfaces generated from 3D medical images such as CT and MR and as a pre-process for generating multi-resolutional polyhedral data.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 45% of the total text.

Smoothing Method for Polygonal Data

      Disclosed is a method for smoothing polyhedral data by
exchanging edge connections and moving vertex positions according to
a smoothness measure which is defined by the deflection angles of the
adjacent faces and edge lengths.  The proposed method is useful in
smoothing isosurfaces generated from 3D medical images such as CT and
MR and as a pre-process for generating multi-resolutional polyhedral
data.

      Smoothness Measure - Let t_ij be the angles between the normal
vectors of the adjacent faces i and j and l_ij be the length of the
edge between them.  Then define the smoothness measure M by the sums
(see Eqs. (1), (2), or (3)).  The claimed measures are dependent on
only the geometrical shape of polyhedral data and are independent
from how their polygonal faces are triangulated.  The key point of
our smoothness measures is that the expansion of the angle dependent
part into the power series starts with a quadratic power.  Therefore,
more variations of smoothness measures are possible.  Eqs. (2) and
(3) have the advantage in their faster computation because we have
for the normal vectors of faces n_i and n_j (see Eq. (4)).  The
invention claims that the connection of edges is exchanged and moves
the position of vertices by minimizing the above-mentioned smoothness
measure M or some target functions which include M.  The examples of
the target functions which include M are Eqs. (5) and (6) where Eq.
(7) and S are total surfaces of polyhedral data.  These target
functions are  more effective because the measures (1), (2), and (3)
are affected by scaling but the functions (5) and (6) are independent
from scaling.

      Exchange of Edge Connections - The invention claims the
previous smoothness measures and the following stack-based
optimization methods as a key part for exchanging edge connections.
In the following,  we assume every face is made by a triangle.

      Step of Edge Exchange Check - Here we describe the step of
checking whether we should exchange edge connections or not.  Let
x1x2 be the edge of interest and x3 and x4 be opposite vertices of
two triangles which are adjacent to it.  That is to say, we have two
triangles, x1x2x3 and x2x1x4, for a given edge x1x2.  Compute a
smoothness measure M or target function for the original edge
connection and the new connection where the edge x1x2 is deleted and
the edge x3x4 is inserted.  If the new connection gives a smaller
value of the smoothness measure or target function, the edge
connection is exchanged.  Since the exchange of edge connection
changes normal vectors, the edges x1x3, x3x2, x2x4, and x4x1
contribute to the change of the smoothness measure M.

      Stack Method - The order in scanning edges is very important
since the proposed method is essentially the optimization of a
smoothness measure M or a target function.  The following stack
methods are claimed  as practical optimization procedur...