Browse Prior Art Database

High-Speed Polygon Data Volume Reduction Algorithm

IP.com Disclosure Number: IPCOM000120151D
Original Publication Date: 1991-Mar-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 6 page(s) / 179K

IBM

Related People

Doi, A: AUTHOR [+2]

Abstract

Methods of triangulating equi-valued surfaces may be classified into four categories: (a) parallel-contour-map methods (1,2), (b) a propagation method (1), (c) tetrahedral-cell methods (3,4,5), and (d) a marching cube algorithm (6). Here an equi-valued surface is defined as a set of points that satisfies the equation F(x,y,z) - C = 0 (1) where F(x,y,z) is a spatial function and C is a constant.

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

High-Speed Polygon Data Volume Reduction Algorithm

Methods of triangulating equi-valued  surfaces may be
classified into four categories: (a) parallel-contour-map methods
(1,2), (b) a propagation method (1), (c) tetrahedral-cell methods
(3,4,5), and (d) a marching cube algorithm (6).  Here an equi-valued
surface is defined as a set of points that satisfies the equation
F(x,y,z) - C = 0                           (1)
where F(x,y,z) is a spatial function and C is a constant.

When the user applies the methods of triangulating equivalued
surfaces for a large quantity of data on 3D grid, a gigantic number
of polygonal data are usually generated. In this document, we first
present the data structure of polyhedral approximation.   We then
present an data volume reduction method by post-processing that gives
a high quality of triangulation.  The method is applicable to the
results approximated by all triangulating methods.
Data Structure for Polyhedral Approximation

We use the following data structure to describe the data volume
reduction algorithm.  Each polyhedral data item consists of a
triangle table and a vertex table.   Here we restricted all the faces
of the polyhedral data to triangles, in order to simplify graphic
synthesis.

The vertex table is an array of the coordinates of the vertices
on the equivalued surface and their surface normals.  Each vertex has
a unique identifier; no repetition of identical coordinates is
allowed in the vertex table. The surface normal is used for smoothly
shaded image synthesis according to Gouraud's and Phong's method (7).

The triangle table is an array of triangles, each of which is
represented by the identifiers of its three vertices.  The vertex
identifiers are the pointers to the vertex table.  All triangles are
appropriately oriented in the data structure.

In most graphics applications, it is sufficient to scan the
triangle table and process each item by using the corresponding data
in the vertex table.  Although the edge table is not given in our
data structure, the edges are implicitly represented in the triangle
table; any two vertices of a triangle form an edge.
Data Volume Reduction

Now, we describe a systematic post-processing method for
removing overly short edges and small triangles from the produced
polyhedral data.

The principle is to contract any edge or triangle that is
judged removable into a single effective vertex.  The criterion for
removable edges and triangles is as follows:
d < D,   v  > V                           (2) and
(3)

(Image Omitted)

Here d is the edge length and v the scalar product of surface normals
between two adjacent vertices.  D, V, and H are user-defined
threshold parameters.  As explained in the Appendix, condition (3)
ensures that the distance of the...