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

Accelerating Access and Operation on Tetrahedral Mesh Using Exclusive-OR Code

IP.com Disclosure Number: IPCOM000103955D
Original Publication Date: 1993-Feb-01
Included in the Prior Art Database: 2005-Mar-18
Document File: 2 page(s) / 79K

Publishing Venue

IBM

Related People

Moriwaki, A: AUTHOR [+2]

Abstract

Disclosed are algorithms that enable a fast access to tetrahedral mesh data, and algorithms that enable a robust raytracing through tetrahedral mesh.

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

Accelerating Access and Operation on Tetrahedral Mesh Using Exclusive-OR Code

      Disclosed are algorithms that enable a fast access to
tetrahedral mesh data, and algorithms that enable a robust raytracing
through tetrahedral mesh.

      Tetrahedral mesh data consists of cells.  A cell is a
tetrahedra, that is specified by four points, or vertices.  Each cell
has four faces.  The direction of the face is from interior to
exterior of the cell.  A face is also specified by four points, three
vertices of the face and the last point of the cell, which shows the
direction.  The representation of a face is not unique.  For example,
consider a cell of points A, B, C and D. Then, one face can be
specified by A,(B,C,D) or A,(C,D,B) or A,(D,B,C).  Another face is
specified by B,(A,D,C) or B,(D,C,A) or B,(C,A,D).  Another face is
C,(D,A,B) or C,(A,B,D) or C,(B,D,A).  The last face is D,(C,B,A) or
D,(B,A,C) or D,(A,C,B).  (The three-tuple is the vertices of the
face.) In order to access data corresponding to a point of face, it
is necessary to determine which point of cell coincide with that
point.  The Exclusive-OR code described bellow enables this
determination process to be implemented with only one machine
instruction, and thus, shortens the access time.

      Consider a tetrahedra specified by four points P0, P1, P2 and
P3, and call point Pn the n-th point of the cell(n = 0,1,2,3).
Consider also a face specified by four points in the form
Q0,(Q1,Q2,Q3), and call point Qn the n-th point of the face(n =
0,1,2,3).  The exclusive-OR code is the rule under which four faces
of tetrahedra P0,P1,P2,P3 are determined as follows.  The first face
of this tetrahedra is P0,(P1,P2,P3).  The second face is
P1,(P0,P3,P2).  The third face is P2,(P3,P0,P1) and the forth face is
P3,(P2,P1,P0).  If a face is the i-th face of a tetrahedra and...