Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Method for Replacing Vertex Normals Caused by Degenerate Surface Representations in a Computer Graphics System

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

Publishing Venue

IBM

Related People

Einkauf, MA: AUTHOR [+2]

Abstract

In recent years, computer graphics systems have begun to offer parametric surfaces as a convenient method to describe complex surfaces. Such surfaces are defined by a relatively low number of "knots" and associated control points. The knots are defined in a two-dimensional parametric space (u,v), while the control points are defined in normal Cartesian space (x,y,z). This data describes the general contour of the surface. Via a mapping function, the control points and knots produce a set of vertices that closely approximate the actual surface. This process is called "tesselation" (see Fig. 1). The entire surface is comprised of connected "patches". Each patch is typically displayed as a sequence of connected triangle meshes.

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

Method for Replacing Vertex Normals Caused by Degenerate Surface
Representations in a Computer Graphics System

      In recent years, computer graphics systems have begun  to
offer parametric surfaces as a convenient method to describe complex
surfaces.  Such surfaces are defined by a relatively low number of
"knots" and associated control points.  The knots are defined in a
two-dimensional parametric space (u,v), while the control points are
defined in normal Cartesian space (x,y,z).  This data describes the
general contour of the surface.  Via a mapping function, the control
points and knots produce a set of vertices that closely approximate
the actual surface.  This process is called "tesselation" (see Fig.
1).  The entire surface is comprised of connected "patches".  Each
patch is typically displayed as a sequence of connected triangle
meshes.

      The tesselation process computes, with each vertex, a vector
perpendicular to the surface at the vertex (i.e., the "vertex normal"
or "normal").  The normal may be used in lighting calculations to
produce a color for the vertex, thus enhancing the realism of the
displayed surface.   Some sets of knots and control points can
produce meshes in which some vertices are "identical or almost
identical" (hereafter, this condition will simply be called
"identical").  (Triangles in the mesh which have two or more
identical vertices are known as "degenerate" triangles.) For these
vertices, the normals computed are very small in length, or actually
have 0 length (i.e., "degenerate normals").  Using degenerate normals
in the lighting calculations produces almost random colors, which can
be very noticeable on the displayed surface.

      Fig. 2 shows a surface patch with no, one and multiple
degenera- cies.  Fig. 2ii shows vertices 7 and 9 as identical - which
causes triangle 7-8-9 to be degenerate. Fig. 2iii shows vertices 7, 8
and 9 as identical - which causes triangles 6-7-8, 7-8-9, and 8-9-10
to be degenerate.

      The method disclosed herein provides for the replacement of
degenerate normals with a normal which more accurately describes the
actual surface normal at the vertex.  Recall that the surface is
represented by patches, while each patch is represented by triangle
meshes.
      The algorithm follows, in a C-like pseudocode.
         Avg_Normal.x = 0;
         Avg_Normal.y = 0;
         Avg_Normal.z = 1;
         Vertices_Processed = 0;
         Prev_Normal_Degenerate = TRUE;
         Magnitude_Degenerate_Normal_Squared = .00000000001;
         For (Each Patch) {
           For (Each Vertex of Patch) {
             Normal_Degenerate = FALSE;
             Magnitude_Vtx_Normal_Squared =

      Continued:
(Vtx_Normal.x*Vtx_
normal.x)
(Vtx_Normal.y*Vtx_
normal.y)
(Vtx_Normal.z*Vtx_normal.z)
   Magnitude_Avg_Normal_Squared =
(Avg_Normal.x*Avg_
normal.x)
(Avg_Normal....