% spiral 10 0 0 -100 -15 61 -78 -83 -3 -56 -30 -89 -33 73 -68 -11 92 38 11 -3 94 33 -82 14 56 4 -63 78 0 0 100Please note: to use our script, you must start with integers, small enough (~<1000) to be cubed without overflow. This is not because of a limitation in sp.cpp, but because the preprocessing uses a convex hull program that assumes integer input.
Let us say that the above data is stored in a file s10:
% spiral 10 > s10Then running the Unix shell script
% convex.sh s10will produce these files:
In order to make the script run from raw coordinates directly to graphics without user intervention, the source is always fixed to the the 0th vertex of the 0th face. Of course the user can select any particular source vertex of the polyhedron as previously described.
Both the pre- and the post-processing is performed by an altered version of chull.c from Computational Geometry in C, Chapter 4, which we call cullsp.c. The chullsp.c program is used to compute the hull, to output the 2D info, and finally to prepare the shortest paths as 3D polygonal chains. The three different uses of chullsp.c are controlled by flags on the command line. Here is the full script for convex.sh:
#! /usr/local/bin/bash # # Shell script convex.sh for finding shortest paths on the surface # of a convex polyhedron. # # Written by Biliana Kaneva and Joseph O'Rourke, Copyright 2000. # # The input FNAME is assumed to be a raw list of 3D coordinates # of points. The script first computes the convex hull, then creates # the input file for sp, then runs sp, then creates a geomview file # for viewing the results. if [ "$#" -eq "0" ] then echo "Syntax: convex.sh datafile" exit 1 fi FNAME=$1 echo "Working on file 3D data file $FNAME" # 1. Compute the 3D convex hull chullsp -o < "$FNAME" > "$FNAME".geom echo "Convex hull computed and written to $FNAME.geom" # 2. Create the 2D input file chullsp < "$FNAME" > "$FNAME".in # Fix the source vertex to be the 0th (local index) vertex of the 0th face. echo "0 0" >> "$FNAME".in echo "Input file of 2D triangles written to $FNAME.in" # 3. Run sp. echo "Starting to run sp..." sp < "$FNAME".in > "$FNAME".out echo "...Finished running sp." # 4. Append the original 3D data to the end of the sp output file. cat "$FNAME" >> "$FNAME".out echo "$FNAME.out written." # 5. Create geomview oogl commands to draw the shortest paths chullsp -g < "$FNAME".out > "$FNAME".vect echo "Geomview file $FNAME.vect of shortest paths written." # 6. Invoke geomeview on the polyhedron and shortest paths files. echo "Invoking Geomview..." geomview "$FNAME".vect "$FNAME".geom &This shell program and the chullsp.c file were added to the code distribution 3 Sep 00.
#! /usr/local/bin/bash # # Shell script terrain.sh for finding shortest paths on the surface # of a terrain. # # Written by Biliana Kaneva and Joseph O'Rourke, Copyright 2000. # # The input FNAME is assumed to be a raw list of x,y,height coordinates # of points over a terrain. First the Delaunay triangulation is # computed (via the 3D hull program chullsp.c). Then the remainder # is similar to the design of convex.sh. if [ "$#" -eq "0" ] then echo "Syntax: terrain.sh datafile" exit 1 fi FNAME=$1 echo "Working on file 3D data file $FNAME" # 1. Compute the Delaunay triangulation chullsp -on < "$FNAME" > "$FNAME".geom echo "Delaunay triangulation computed and terrain written to $FNAME.geom" # 2. Create the 2D input file chullsp -tn < "$FNAME" > "$FNAME".in # Fix the source vertex to be the 0th (local index) vertex of the 0th face. echo "0 0" >> "$FNAME".in echo "Input file of 2D triangles written to $FNAME.in" # 3. Run sp. echo "Starting to run sp..." sp < "$FNAME".in > "$FNAME".out echo "...Finished running sp." mv info "$FNAME".info mv count "$FNAME".count # 4. Append the original 3D data to the end of the sp output file. cat "$FNAME" >> "$FNAME".out echo "$FNAME.out written." # 5. Create geomview oogl commands to draw the shortest paths chullsp -gn < "$FNAME".out > "$FNAME".vect echo "Geomview file $FNAME.vect of shortest paths written." # 6. Invoke geomeview on the polyhedron and shortest paths files. echo "Invoking Geomview..." geomview "$FNAME".vect "$FNAME".geom &
We specify orthogonal polyhedra by a colletion of cubes.
The cubes are specified by a 3D ASCII picture drawn in a file,
using the symbols
'*' and '-', where '*' represents a cube and '-' an empty space.
The first line in the file is in the form of 'x, y, z',
for each coordinate depth. Thus there are z layers stacked in the
z-direction, with each layer x by y, where x is the horizontal
dimension and y the vertical.
For example,
represents a polyhedron composed of two levels (z depth), an x depth of 4 and a y depth of 3. The first level is composed of 1 row of cubes and the second level, of 1 column of cubes.4 3 2 **** ---- ---- ---* ---* ---*
Lets say the above data is stored in a file called poly. Running the Unix shell script
% ortho.sh poly
(The latter two files are produced when DOUTPUT is #defined in sp.cpp.) In addition, Geomview is invoked immediately to display the results. In order to make the script run from raw coordinates directly to graphics without user intervention, the source is always fixed to the the 0th vertex of the 0th face. Of course the user can select any particular source vertex of the polyhedron as previously described.
Ortho.c runs twice, once with the `-i' flag (i for input),
and once with the `-o' flag (o for output).
First ortho.c -i creates the .geom and .in files.
After sp.cpp uses the .in file to create a .out file,
ortho.c -o uses the .out file to create a .vect
file for viewing the shortest paths on GeomView.
Here is the full script ortho.sh:
#! /local/bin/bash # #Shell script ortho.sh for finding shortest paths on the surface of an orthogonal polyhedron. # #Written by Biliana Kaneva, Joseph O'Rourke and Veronica Morales. # #The input FNAME is assumed to be a raw list of 'symbol' data. The script first reads the data, #triangulates the cubes and counts the faces, vertices and edges. It creates the input, '.in', file #for use by sp.cpp. # #sp.cpp runs and produces the a '.out' file with data on the shortest paths. # #Then, ortho.c uses the sp.cpp output to create a '.vect' file for viewing the paths in GeomView. if [ "$#" -eq "0" ] then echo "Syntax: ortho.sh datafile" exit 1 fi FNAME=$1 echo "Working on raw symbol data file $FNAME" #1.Read data and compute faces and vertices. ortho -i "$FNAME" echo "Finished .geom and .in files" #2.Pass to sp.cpp echo "Starting sp..." sp < "$FNAME".in > "$FNAME".out echo "Finished sp. '.out' file completed" #3.Run ortho with .out and produce a .vect file for GeomView echo "Running ortho again..." ortho -o "$FNAME" echo ".vect file written" #4.Open GeomView echo "Opening GeomView and displaying results" geomview "$FNAME".geom "$FNAME".vect&As of 4 Sep 00 I have not yet prepared the terrain softare for distribution, but if you are desperate, write to me and I'll send it in it current unsatisfactory state.