Browse Prior Art Database

Method of Thinning Polygonal Volume Data for Scientific Visualization

IP.com Disclosure Number: IPCOM000104342D
Original Publication Date: 1993-Apr-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 6 page(s) / 159K

Publishing Venue

IBM

Related People

Doi, A: AUTHOR [+3]

Abstract

Disclosed is an algorithm for reducing the volume of polygonal data without causing deterioration of the image quality. When the triangulation of equi-valued surfaces is applied to a large quantity of data on the 3D grids, an enormous volume of polygonal data is usually generated. The disclosed method significantly reduces this volume by merging polygons without significantly distorting the shape of the surface. It is applicable to the results of all triangulation methods [1,2,3].

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

Method of Thinning Polygonal Volume Data for Scientific Visualization

      Disclosed is an algorithm for reducing the volume of polygonal
data without causing deterioration of the image quality.  When the
triangulation of equi-valued surfaces is applied to a large quantity
of data on the 3D grids, an enormous volume of polygonal data is
usually generated.  The disclosed method significantly reduces this
volume by merging polygons without significantly distorting the shape
of the surface.  It is applicable to the results of all triangulation
methods [1,2,3].

      Here, an equi-valued surface is defined as a set of points that
satisfies the equation F(x,y,z) - C = 0, where F(x,y,z) is a spatial
function and C is a constant.  The faces of polyhedral data are
restricted to triangles in order to simplify graphic synthesis.

      The volume of polygonal data is reduced systematically.  The
principle is to merge the three vertices of a triangle that is judged
to be removable into a single vertex at, for example, the barycenter
of the removed triangle (Fig. 1).  The criteria for non-removable
triangles are as follows (Fig. 2).  If a triangle does not satisfy
any of these conditions, it is removed from the polyhedral faces;
that is to say, a data structure corresponding to the triangle on the
faces is removed.

* v > V
where v is the inner product of the two surface normals at
both ends of each of the three edges forming the examined
triangle.  If the faces of the polyhedra are smooth, many
triangles forming the faces can be removed without serious
deformation of its shape.

* m > M
where m is the number of times that the triangle is merged.
Since each merging process decreases the accuracy of the
coordinates on the surface, this number is restricted
reasonably by m.

* ntv < 2    or    nev - ntv = 1
at all the vertices of the three triangles that share one
of the edges forming the triangle, where ntv is the number
of triangles that share the vertex, and nev is the number
of edges that share the vertex.  These conditions are
necessary to avoid changing the shape of a cut end of the
surface, by leaving polygons on the cut end unchanged.

* ntv <=  3
at all the vertices opposite to the three edges of the
triangle.  This condition is necessary to avoid generating
a wrong vertex as a result of the merging process.

* nte > 2
on all the edges connecting one of the three vertices of
the removed triangles, where nte is the number of triangles
having one of the edges.  If faces split two ways from a
polyhedral faces, this condition leaves the shape
unchanged.

If the merging process is applied only to eliminate
excessively small triangles, the following condition is used
instead of the first item ( v > V ) as a criterion for
non-removable triangles.

* s > S
where s is the area of the triangle.

Here V,M, and S are the user-defined threshold parameters.

      The disclosed method uses the following data structures to make
it ea...