regtet computes a regular tetrahedralization of a set of points in 3-d space,i. e. a Delaunay tetrahedralization with weights.
If no weights are present a Delaunay tetrahedralization is computed.
This page documents the FORTRAN program regtet, not the regtet Mathematica encapsulation, which is documented here.
This documentation about input/output variables, etc., is derived from comments in the driver program main (much of it copied verbatum).
The original regtet software by J. Bernal can be downloaded here. Any questions regarding the FORTRAN should be directed to the author and not to us! (We are just using the program, we are very grateful thank you, but did not develop it and can take no credit nor give any help with it, thank you very much).
Note that if weights are present and degeneracies exist there may be points whose Power cells are not 3-dimensional.
Computations in regtet are done in exact arithmetic whenever floating point arithmetic (done in double precision) does not seem appropriate.
Files Used by regtet
|File Name||File Type||Description|
Flags that control how regtet works.
If not present, will prompt interactively and will write the file prompts.tentative
|pnts-wghts||INPUT||Required list of coordinates (and, optionally, weights).|
|points-off||INPUT||Optional list of points (integers) to be turned "off".|
|prompts.tentative||OUTPUT||If prompts.data is missing, then the values input in response to interactive prompts are written to this file in a format that is compatible with its being used in the future as prompts.data|
|tetrahedra||OUTPUT||Described below separately.|
|bigbox-pnts||OUTPUT||If bigbox=.true. then the input data points (the contents of the file pnts-wghts are written to this file. This can only happen if reccor=.true (see prompts.data file).|
regtet Input Files
|Contents of the file: prompts.data|
|1||Y,N||Y = Delaunay (no weights) (sets delaun=.true.) |
N = Regular tetrahedralization (with weights) (sets delaun=.false.)
Y = Some inputs to be inactive (the list of point indices will be in the file points-off. (sets pntoff=.true.)
N = No inputs to be inactive (sets pntoff=.false.)
|3||Y,N||Y = Use "flipping history algorithm" (sets flphis=.true.) |
N = Use "shishkebab" algorithm (sets flphis=.false.)
|4||Y,N||Y = output includes artificial tetrehedra (only if flipping history used) (sets artfcl=.true.; otherwise artfcl=.false.)|
|5||Y,N||Y = input points randomly (sets random=.true.)|
N = use order given (sets random=.false.)
|5a||s1 s2 s3 s4||Four random seeds. this line should only be present if prior line is "Y"|
Y = Points that define a rectangular regular grid on the surface of a rectangular polyhedron that contains set of input points will be part of the set for which tetrahedralization is to be computed; dimensions of polyhedron and choice of points that define grid are according to specifications provided by user. (sets reccor=.true.; literally SD includes SP)
N = Points that define a rectangular regular grid on the surface of a rectangular polyhedron that contains the set of input points will not be part of the set for which a tetrahedralization is to be computed. (sets reccor=.false.; literally SD does not include SP)
If N then the next three lines should be omitted.
|6a||wlenx, wleny, wlenz|
If xmax, ymax, zmax are the maximum values of the x, y, and z coordinates of the input points, respectively, and xmin, ymin, zmin are the minimum values, then for positive numbers wlenx, wleny, wlenz (provided by user), the eight vertices of the the polyhedron will be:
(xmin-wlenx, ymin-wleny, zmin-wlenz)
If not delaunay; if Delaunay, omit this line. |
If this is a regular tetrahedralization (not a Delaunay), then if wmin is the minimum value of the weights of the input points then for a real number wlenw (provided by user) a weight equal to wmin - wlenw is assigned by the program to each point in the rectangular grid on the surface of the polyhedron.
For positive integer naddl, for each facet of the
polyhedron a set of naddl × naddl points is generated by program
This set defines a rectangular regular grid on the facet and contains the four vertices of the facet; the points in the union of the six sets thus generated define the rectangular grid on the surface of the polyhedron; naddl can not be less than 2; if it equals 2 then the grid is defined exactly by the 8 vertices of the polyhedron.
Omit this line unless delaun=.false.
Y = check points for redundancy (requires additional time) (sets redchk=.true.)
N = don't check for redundancy (sets redchk=.false.)
This line should be omitted unless the regular grid is requested in line 6 (two or more lines earlier).
Y=save points used to define the grid to a file (sets bigbox=.true.)
N=don't save points to a file (sets bigbox=.true.)
|8||0-9||An integer icfig 0 to 9 indicating the number of significant figures to the right of the decimal point for the coordinates. The total number of significant figures can be up to 14 with no more than 9 digits on either side of the decimal point.|
|8a||0-9||An integer iwfig 0 to 9 indicating the number of significant figures to the right of the
decimal point for the weights. The total number of significant figures can be up to 14 with no more than 9 digits on either side of the decimal point.
This line should be omitted for pure Delaunay Tetrahedralizations.
|Contents of the file: pnts-wgts|
|1||x1,y1,z1,w1||Coordinates and optional weight (FORTRAN free form)|
|2||x2,y2,z2,w2||Coordinates and optional weight (FORTRAN free form)|
|…||…||Additional data points to end of file.|
regtet Output Files
|Contents of output file: tetrahedra|
|Each line of this figure represents a single "record" in the output file. The width of the boxes and the colors are purely illustrative and have no significance. Each value in the output is discussed in the following paragraphs. Ellipses (…) indicate that certain output fields have been skipped.|
|The ideli, ipnti,...,iredi are integer flags 1/0 that indicate whether the corresponding boolean is .true. (1) or .false. (0). (FORTRAN 7(1x,I1) format) These values are echoes of the same flags as they are set in the prompts.data file, above.|
nd is the number of vertices in the orignal data set (defined by the number of points in the pnts-wgts file.
nt is the number of tetrahedra in the solution, and also determines the number of lines of data in icon(..) on the subsequent lines of this file.
icfig and iwfig are the integer number of digits precision requested in the final two lines of the prompts.data file.
nd, nt, icfig, and iwfig are on the same line as integers in FORTRAN free (*) format.
iwfig is not present unless delaun=.false. (ideli=0).
icon(j,k) contains the indices of the kth tetrahedron on a single line as eight 10-character integers, icon(1,j) in characters 1-10, ..., icon(8,j) in characters 71-80. (FORTRAN 8I10)
If artfcl=flphis=.true. then tetrahedra in this list are those in the final tetrahedralization for SO (equal to SU) together with the flipping history tetrahedra, i. e. tetrahedra that at some point during the execution of the program were part of a tetrahedralization for SO but that are not part of the final tetrahedralization.
If artfcl=.true. and flphis=.false. then tetrahedra in this list are just those in the final tetrahedralization for SO (equal to SU).
If artfcl=.false. then tetrahedra in this list are those in the final tetrahedralization for SO (equal to SD).
For each j, j = 1, ..., nt, if icon(5,j)<0 (this can only occur if artfcl=.true.) then tetrahedron j is not in the final tetrahedralization for SO, it was in a previous tetrahedralization (it was eliminated) and its vertices are the points -icon(5,j), icon(6,j), icon(7,j), and icon(8,j) in SO.
If, in addition, flphis=.true. the tetrahedra by which tetrahedron j was replaced through a flip can be identified as follows: for each i, i = 1, ..., 4, if icon(i,j) > 0 then tetrahedron icon(i,j) is one of those tetrahedra.
For each j, j = 1, ..., nt, if icon(5,j)>0 then tetrahedron j is in the final tetrahedralization for SO, and its vertices are the points icon(5,j), icon(6,j), icon(7,j), icon(8,j) in SO.
The tetrahedra in the final tetrahedralization that share a facet with tetrahedron j can be identified as follows: for each i, i = 1, ..., 4, if icon(i,j)>0 is positive then tetrahedron icon(i,j) is one of those tetrahedra.
For each j, j = 1, ..., nt, the vertices of tetrahedron j are ordered as follows: when viewed from vertex icon(5,j) (-icon(5,j) if icon(5,j)<0) the other three vertices icon(6,j), icon(7,j), icon(8,j) appear in this order in a clockwise direction around the circle that contains them.
For each j, j = 1, ..., nt, if tetrahedron j is in the final tetrahedralization, i. e. icon(5,j)>0, then the tetrahedra in the final tetrahedralization that share a facet with tetrahedron j are ordered as follows: for each i, i = 1, ..., 4, if icon(i,j)>0, tetrahedron j shares with tetrahedron icon(i,j) the facet of tetrahedron j that does not contain vertex icon(i+4,j).
is(i) indicates how the ith point in SO was processed by the program as follows:
if is(i)=0 then point i was not considered as a vertex for tetrahedralization;
if is(i)>0 then point i is part of the final tetrahedralization for SO, i. e. there is at least one tetrahedron in the final tetrahedralization with point i as a vertex, and tetrahedron is(i) is one such tetrahedron (actually if point i is in SA then is(i) is always positive);
if is(i)<-8 then point i was found to be redundant as the program was trying to insert it into the current tetrahedralization because a point previously inserted (point -is(i) in SO if artfcl=.true. (SO=SU), point -is(i)-8 in SO if artfcl=.false. (SO=SD)) was identical to it and either the weight of the previously inserted point was larger or equal to the weight of point i or there were no weights;
if is(i)=-2 then point i had been inserted by the program into the tetrahedralization but was found to be redundant because another point was later inserted by the program that was identical to point i and whose weight was larger than that of point i (this case is not possible if there are no weights);
if is(i)=-3 then point i was found to be redundant in the sense of a Regular tetrahedralization as the program was trying to insert it into the current tetrahedralization because of its weight as compared to the weights of the vertices of the tetrahedron in the current tetrahedralization that contains it even though it was not identical to a previously inserted point (this case is not possible if there are no weights);
if is(i)=-4 then point i had been inserted by the program into the tetrahedralization but was found to be redundant in the sense of a Regular tetrahedralization because of the weight of another point, not identical to point i, that was later inserted by the program together with the weights of three other previously inserted points as compared to the weight of point i (this case is not possible if there are no weights).
If reccor=.True. then wlenx,wleny, wlenz, and wlenw (if delaun=.false.) echo what is provided in the input file. (FORTRAN Free (*) output format)
If reccor=.false. then this line is omitted.
If reccor=.true. then naddl is a positive integer greater than 1 provided by the user to be used by the program to determine the set SP.
If reccor=.false. then this line is omitted.
The points in SP define a rectangular regular grid on the surface of a rectangular polyhedron that contains SI in its interior.
For each facet of the polyhedron a set of naddl × naddl points is generated by the program that defines a rectangular regular grid on the facet and that contains the four vertices of the facet. SP is then the union of the six sets thus generated (one per facet). It then follows that the number of points in SP must be 6(naddl-2)(naddl-2)+12(naddl-2)+8 = 6(naddl)(naddl)-12(naddl)+8. It also follows that if naddl equals 2 then the points in SP are exactly the 8 vertices of the polyhedron.