NetNews Usenet Archive 1992 #20/NN_1992_20.iso/spool/sci/math/11198

Internet Message Format | 1992-09-09 | 4.4 KB

Path: sparky!uunet!haven.umd.edu!darwin.sura.net!zaphod.mps.ohio-state.edu!ub!acsu.buffalo.edu!kriman
From: [e-mail] (Alfred M. Kriman)
Newsgroups: sci.math
Subject: Re: 3 space terahedron-packing
Summary: Square-base cones, then isoceles-right-triangle-base cones.
Message-ID: <[e-mail]>
Date: 10 Sep 92 05:50:52 GMT
References: <f#[e-mail]>
Sender: [e-mail]
Organization: UB
Lines: 66
Nntp-Posting-Host: lictor.acsu.buffalo.edu

In article <f#[e-mail]> [e-mail] (Steven) writes:
>I am trying to implement an interpolation algorthim over 3D space by
>using a "grid" of tetrahedrons. What I need to compute is a complete
>tiling of 3-space with unit length tetrahedrons: ie, given an XYZ
                        ^^^^^^^^^^^ <--- See * below.
>location, identify the four points of the tetrahedron that encloses
>that location in this "packed" space. Obviously any offset or rotation

   This is two problems:
(1) Specifying a tiling of R^3 by tetrahedra;
(2) Defining an algorithm to identify the vertices of the tetrahedron that
    that encloses an arbitrary point.

>of this packing "solution" is also a solution, but I don't care which
>particular tiling I compute as long as it is constant.
 ^^^^^^^^^
* From the context it seems that "don't care which" means you identify all
congruent tilings.  But what do you mean by "unit length" tetrahedra?
If you mean regular (all edges have equal length) then you're in celebrated
company.  Aristotle also thought that 3-space could be tiled by regular
tetrahedra.  I think it had something to do with Democritos's atoms,
maybe the kind that make up solid matter.
   Given that your tetrahedra won't have tetrahedral symmetry, I suggest
the following basis, which at least is simple.
   First divide R^3 into cubes; for each triple of integers i,j,k, the
[i,j,k] cube is the set of points with Cartesian coordinates less than 1
above the point (i,j,k).  I.e.,
[i,j,k] = {(x_1,x_2,x_3) : i <= x_1 < i+1 , j <= x_2 < j+1 , k <= x_3 < k+1}.
   To discuss the rest in words, define "floor" faces and edges of the
[i,j,k] cube as those having one or two coordinates (resp.) minimal.  There
are three of each, and they can be indexed by coordinate.  Thus, the "1"
floor face of the [i,j,k] cube lies in the x_1 = i plane.  The "2" edge of
the [i,j,k] cube is parallel to the x_2 axis (i.e., it is the intersection
of x_1=i , x_3=k), and normal to the "2" floor face.
   Each cube can be divided into three square pyramids in a simple way.  The
points in a cube that are closest to the floor face m are part of pyramid m.
   Similarly, each pyramid of a cube can be split into two tetrahedra on the
basis of the nearest floor edge.  Thus, the tetrahedron [i,j,k,m,n] is the
set of points in the cube [i,j,k], closer to the floor face m, and closest
to the floor edge n.
   It should be evident that m cannot equal n:  being close to floor face
means that x_m - I_m (I_1 = i, I_2 = j, I_3 = k) is _smaller_ than the
corresponding quantities for the remaining two axes.  Squared distance to
the floor edge n is the sum of squares of x_p - I_p, where p are not n.
Clearly, the edge-m distance is determined by excluding the smallest of the
three possible addends, so it is the _farthest_ edge.  Thus, points in the
[...,m,n] tetrahedron have floor edge n closest, and floor edge m farthest.
   The six ways of selecting m,n (different), from {1,2,3} are the six ways
to choose a tetrahedron in a particular cube.

Algorithm:
   From the above reasoning it should be clear how to identify the tetra-
hedron containing any point with coordinates (x_1,x_2,x_3):  The cube is
given by the floor function: I_p = greatest integer not greater than x_p,
for p = 1,2,3.  The tetrahedron is determined by the fractional part:  Of
the three quantities (x_p - I_p), the smallest has p = m, the largest has
p = n.  The point lies in tetrahedron [I_1,I_2,I_3,m,n].  You can compute
the index that is left over (that is not m or n) as o = 6 - m - n , if
you like.
   From the description it should be clear how to compute the vertices:
Two of them are (i,j,k) and (i+1,j+1,k+1), another is (i,j,k) with a unit
added along the n direction, the last is (i,j,k) with units added along
the n and o directions.

ObAncients:  I think the classical proof that pyramid/cone volume is
base_area times height / 3 was based on a decomposition like this.