Browse Prior Art Database

High-Speed Visualization Method Using a Tetrahedral Model With a Link List

IP.com Disclosure Number: IPCOM000102545D
Original Publication Date: 1990-Nov-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 5 page(s) / 148K

Publishing Venue

IBM

Related People

Koyamada, K: AUTHOR

Abstract

Disclosed is a method for efficiently visualizing, unstructured grid data composed of tetrahedral cells with scalar data at each vertex by using a pre-generated list of adjacent cells (a link list). When volume visualization, such as volume rendering, of unstructured grid data is performed by a ray-casting method, it generally takes a lot of CPU-time to search the next cell that a ray encounters because unstructured grid data does not have information about adjacent cells. In the disclosed method, a link list between cells is generated before rendering, which leads to effective volume rendering of the unstructured grid data.

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

High-Speed Visualization Method Using a Tetrahedral Model With a Link List

       Disclosed is a method for efficiently visualizing,
unstructured grid data composed of tetrahedral cells with scalar data
at each vertex by using a pre-generated list of adjacent cells (a
link list). When volume visualization, such as volume rendering, of
unstructured grid data is performed by a ray-casting method, it
generally takes a lot of CPU-time to search the next cell that a ray
encounters because unstructured grid data does not have information
about adjacent cells. In the disclosed method, a link list between
cells is generated before rendering, which leads to effective volume
rendering of the unstructured grid data.

      In this invention, it is assumed that unstructured grid data
are composed entirely of tetrahedral cells, which are expressed by
the tetrahedron-vertex relations shown in Fig. 1. When the data are
composed of generalized cells, such as wedges, or bricks, they are
subdivided into tetrahedral cells by the method described in [1]. The
tetrahedral model describes the above tetrahedron-vertex relations
and data (coordinate and scalar) at each vertex, that is, it
expresses tetrahedral cells independently. On the other hand, the
link list describes how a tetrahedral cell is connected to adjacent
cells at triangular facets. In Fig. 2, the tetrahedral cell labeled 5
connects the cells labeled 20, 17, 1, and 50 at the facets labeled 1,
2, 3, and 4, respectively, as shown in the link list. If a facet does
not connect any tetrahedral cells, '0' is recorded in the
corresponding field of the link list. When the vertex IDs of a
tetrahedral cell are v1, v2, v3, and v4, a facet labeled n (n=1,4) is
defined as follows:
       Facet 1 = ( v2, v3, v4 )
       Facet 2 = ( v3, v4, v1 )
       Facet 3 = ( v4, v1, v2 )
       Facet 4 = ( v1, v2, v3 )

      The process for creating a volume rendering image from
unstructured grid data by using the above-mentioned tetrahedral model
with a link list can be divided into two parts. One is the process
(Process 1) for searching the exterior facets that a viewing ray
encounters first.  The other is the process (Process 2) for shading
computation based on the method which is shown in [2].

      The first process finds the nearest exterior facet to a view
point. To make the search effective, it assigns unique IDs to
exterior facets. The IDs point to parent tetrahedral cells as
follows:
 Exterior facet i = ( Tetrahedral cell ID,  facet ID (1-4) )
The normal vectors of these exterior facets which are needed for
their shading computation, are stored according to the IDs.  By using
this relation, the process can specify the tetrahedral cell that a
viewing ray first encounters. After the shading computation in
tetrahedral cells, the viewing ray reaches a tetrahedral cell that
contains an exit exterior facet. At this point, th...