I/O Creation

1. Convex Polyhedra

% 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     100

Let us say that the above data is stored in a file s10:

% spiral 10 > s10

% convex.sh s10

• s10.geom: Geomview OOGL input file describing the 3D hull.
• s10.in: Input file formatted for sp.cpp.
• s10.out: Output file created by sp.cpp.
• s10.vect: Geomview OOGL file describing the shortest paths.
• s10.info: Some basic information output by the program on the number of cones at each level.
• s10.count: Time and maximum memory usage for the run.

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 &

2. Terrains

#! /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 &

3. Orthogonal Polyhedra

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,

4 3 2

****
----
----

---*
---*
---*

Lets say the above data is stored in a file called poly. Running the Unix shell script

% ortho.sh poly

• poly.geom: Geomview OOGL input file describing the 3D hull.
• poly.in: Input file formatted for sp.cpp.
• poly.out: Output file created by sp.cpp.
• poly.vect: Geomview OOGL file describing the shortest paths.
• poly.info: Some basic information output by the program on the number of cones at each level.
• poly.count: Time and maximum memory usage for the run.

(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&