Browse Prior Art Database

Method for Accelerating the Rendering of Geometric Models

IP.com Disclosure Number: IPCOM000105771D
Original Publication Date: 1993-Sep-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 6 page(s) / 261K

Publishing Venue

IBM

Related People

Luken, WL: AUTHOR [+2]

Abstract

This work presents a method for converting geometric data from a pointlist data structure into triangle strips. The rate at which models can be drawn on a 3d graphics adapter may be increased by roughly a factor of 3 by using the resulting triangle strips instead of independent polygons derived from the pointlist data structure.

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

Method for Accelerating the Rendering of Geometric Models

      This work presents a method for converting geometric data from
a pointlist data structure into triangle strips.  The rate at which
models can be drawn on a 3d graphics adapter may be increased by
roughly a factor of 3 by using the resulting triangle strips instead
of independent polygons derived from the pointlist data structure.

      The results of geometric solid modelling for curved surfaces
are often represented in the form of a pointlist data structure.
This structure generally includes a list of geometric coordinates
((xi, yi, zi), i = 1 to npoints), and a list of triangles defined by
sets of indices of points within the list of geometric coordinates.
The jth member of this list of triangles may be represented as
(pgind(j, 1), pgind(j, 2), pgind(j, 3)).  In addition, these
components may be accompanied by data representing the surface normal
vectors (nxk, nyk, nzk) at each point (k).  This type of data
structure is very useful for geometric solid modelling because it
provides efficient representations of both the geometric data
defining one of more surfaces as well as the topological structure of
each surface.  For example, each point within the list of geometric
coordinates is typically shared by as many as six or more triangles.

      Although the pointlist data structure is beneficial for
purposes of geometric solid modelling, this structure is incompatible
with the requirements of interactive 3d graphics based on application
programming interfaces (APIs) such as GL* and PHIGS.  These APIs
require the geometric data to be processed in the form of either
polygons (e.g., triangles) or triangle strips.  For the purposes of
these APIs, a polygon is defined by its number of vertices and the
numerical values of the coordinates and normal vector for each
vertex.  That is, the coordinates and normal vectors for each polygon
must be specified explicitly, and not by pointers to another data
structure.

      Likewise, a triangle strip is defined by its number of vertices
and the numerical values of the coordinates and normal vectors for
each vertex.  Each sequence of three successive vertices defines a
triangle.  In addition, the function of swapping the most recent pair
of vertices may be performed at any point after the second vertex.
The result is equivalent to repeating the data for the penultimate
vertex preceding the vertex-swapping function.  Thus, the sequence
(A, B, C, swap, D, E) is equivalent to the sequence (A, B, C, B, D,
E), assuming that the degenerate triangle (BCB) is not visible.

      Graphics adapters such as the GTO adapter for the Risc
System/6000 achieve performance benefits by using triangle strips
instead of polygons.  Except at the ends of a strip, each vertex
within a triangle strip forms part of three triangles.  Consequently,
the effort required for the geometry processing of each vertex is
reduced by a factor of th...