
 
                          COPYRIGHT NOTICE
 
  This software was developed at the National Institute of Standards
  and Technology (NIST) by employees of the Federal Government in the
  course of their official duties. Pursuant to title 17 Section 105
  of the United States Code this software is not subject to copyright
  protection and is in the public domain.
 
  This is an experimental system.  NIST assumes no responsibility
  whatsoever for its use by other parties, and makes no guarantees,
  expressed or implied, about its quality, reliability, or any other
  characteristic.
 
  We would appreciate acknowledgment if the software is used.
 


                             DISCLAIMER

  Certain commercial products may be identified in this paper in order 
  to adequately describe the subject matter of this work.  Such 
  identification is not intended to imply recommendation or endorsement 
  by the National Institute of Standards and Technology, nor is it 
  intended to imply that the identified products are necessarily the 
  best available for the purpose.



TABLE OF CONTENTS
-----------------

  Introduction

  Installing the Software

  Running The Test Software

  Post-Processing of the Test Output

  Mathematic Code

  Principal Programs and Scripts




INTRODUCTION
------------

Except where noted, the software provided here was developed at the 
National Institute of Standards and Technology as part of our effort
to understand uncertainty and errors in scientific visualization. This
software quantifies the errors in polygonal approximations of some
types of quadric surfaces.  The methods embodied by this software 
and the data produced by this software are described in the paper:

  J. G. Hagedorn, M. Olano and J. E. Terrill, Measuring Errors 
  in Polygonal Representations of Surfaces, in preparation.

We are making this software available in order to provide additional 
information to readers of the paper.

The software is purely for research purposes and we provide it "as-is".  
We do not have the resources to fix bugs or otherwise support the 
software.  We make no claim that this is the best possible 
implementation of these methods.  We have made no great attempt to make 
the software efficient or to make it easy to run or to understand.  This
is research code that evolved to its current state. 

In the same vein, we do not have the resources to fully explain every 
facet of the operation of this software such as the formats of the input
and output files or the command line arguments used by each component.
If necessary, you can find this information by examining the source 
code.

In the sections below, we describe how to unpack the downloaded archive
file and how to build the software.  We also provide scripts and data
that are intended to enable you to run the test cases that are described
in the paper.  The software can be used to run other cases; to do so, 
you will need to examine the scripts provided and modify them to your 
needs.

We also note that this software was implemented and run on a Linux 
system.  If you are trying to build and run this software in some other 
operating system (or perhaps even under some other version of Linux), 
you will probably need to modify the build and run procedures.

This software is self-contained with three exceptions: VTK, R, and
Mathematica. 

The test cases that make use of isosurfaces require VTK - The 
Visualization Toolkit.  VTK can be obtained without charge from:

        http://www.vtk.org/

Information about the installation or use of VTK is beyond the scope of 
these notes.  Our use of VTK is limited to one script (vtkIsoPLY_Conn)
which invokes VTK to produce an isosurface from a gridded data set.

The post-processing of the test data requires the use of the R 
statistical package. R is free software that can be obtained here:

        http://www.r-project.org/

This web site gives information about the installation and use of R.

As described below, Mathematica (http://www.wolfram.com/mathematica) is
used for a portion of our processing. We provide a Mathematica notebook
for this computation.



INSTALLING THE SOFTWARE
-----------------------

First you should download the file:

        polySurfErr.tar.gz 

You should then move this file to a directory under which you want all
of the software to be installed.

Then issue the following command:

        tar -xzvf polySurfErr.tar.gz

If there is some problem with this, try these two commands:

        gunzip polySurfErr.tar.gz
        tar -xvf polySurfErr.tar

This should create a subdirectory called "polySurfErr" with all files 
under that directory.

To build the software issue the following series of commands:

        cd polySurfErr

        cd libnum
        make
        #  A number of warning messages may be displayed.

        cd ../SEutil
        make

        cd ../gridded
        make

        cd ../directPoly
        make

        cd icosahedron
        make


This should complete the compiling and linking of all of the software

Now go back to the directory where you issued the first "tar" command.
If you've just completed the "make" command above, the following 
command should move you to the right directory:

        cd ../../..

So now your current directory should be just above the polySurfErr 
directory.

Choose a name for a new subdirectory where you want to test the 
software. Let's say you want to name that directory "myTests". Then 
issue the command:

        ./polySurfErr/aux/scripts/mkTestDirs myTests

This creates the subdirectory "myTests" and a lot of subdirectories of 
myTests.

Now invoke the script which moves a lot of files from the directory
that the tar command created to your new directory:

        ./polySurfErr/aux/scripts/cpTestFiles  polySurfErr  myTests

This completes the setup needed to run the test cases that we have
provided.



RUNNING THE TEST SOFTWARE
-------------------------

The test cases that we provide are broken down into subdirectories based
on the type of polygonization, the type of quadric surface, and the
subcategory of testing.  There are four subcategories of testing:
       * main tests,
       * big tests (many more triangles),
       * alternate ellipsoid shapes, and
       * alternate ellipsoid polygonization.

If you named your test directory "myTests", here is the directory 
structure that you now have:

  Main Tests:

     Isosurface Polygonizations:
        myTests/IG/E     Ellipsoids
        myTests/IG/PE    Elliptic Paraboliods
        myTests/IG/PH    Hyperbolic Paraboloids
        myTests/IG/H1    Hyperboliods of One Sheet

     Direct Polygonizations:
        myTests/DP/E     Ellipsoids
        myTests/DP/PE    Elliptic Paraboliods
        myTests/DP/PH    Hyperbolic Paraboloids
        myTests/DP/H1    Hyperboliods of One Sheet


  Big Tests:

     Isosurface Polygonizations:
        myTests/IG.big/E     Ellipsoids
        myTests/IG.big/PE    Elliptic Paraboliods
        myTests/IG.big/PH    Hyperbolic Paraboloids
        myTests/IG.big/H1    Hyperboliods of One Sheet

     Direct Polygonizations:
        myTests/DP.big/E     Ellipsoids
        myTests/DP.big/PE    Elliptic Paraboliods
        myTests/DP.big/PH    Hyperbolic Paraboloids
        myTests/DP.big/H1    Hyperboliods of One Sheet

  Alternate Ellipsoid Shapes:
        myTests/IG.altEll/E     Ellipsoids
        myTests/DP.altEll/E     Ellipsoids

  Alternate Ellipsoid Polygonization:
        myTests/DP.altEll.Icos/E  Ellipsoids: icosahedral polygonization


  Post-Processing of Test Results:
        myTests/figsAndModels


Throughout this directory structure there are executable programs, 
scripts, and supporting files that will help run the tests.  In 
particular, in each one of the bottom-level subdirectories (except for
the post-processing directory), there is a script that will run a series
of test cases.  

For each of these scripts to run correctly, your current working 
directory must be where the script resides. All of the scripts have 
names that end in ".run", so it is easy to identify the script in any 
subdirectory.

For example, to run the "main" tests for isosurface polygonizations
of hyperbolic paraboloids, you might do something like this:

        cd myTests/IG/PH

        ls *.run           # this displays the name PH.IG.run

        ./PH.IG.run

The script "PH.IG.run" invokes a program three times to run three 
different hyperbolic paraboloid cases.  The scripts put these programs 
in the background so that they will run concurrently.  If you don't want
that, you should change the script.  All of the test scripts put 
processes in the background because these tests take quite a bit of time
and they were originally run on machines with at least four processors.

As we mentioned above, we use VTK - The Visualization Toolkit to produce
isosurfaces when they are needed. This use of VTK is confined to the 
script named vtkIsoPLY_Conn, which is used for the isosurface test 
cases.

If you want to run all of the test cases, you need to go into each of 
the lowest level subdirectories and invoke the run script.  Because
these scripts run many processes in the background, you will need to
monitor the background processes to see when they are completed. Running
all of the scripts for all of the test cases will take quite a bit of 
CPU time. We don't have exact records for our own runs, but it certainly
took us several CPU-weeks of processor time to run all cases.

You should probably try a few cases to get a feel for how long the runs 
take on your machine.

Each test run produces an output file that contains a single line.  All
of these files have names that end in ".err" (because the results are
measures of error).

There are several other data files that are needed in the generation and
analyses of these test cases:
        * E.quadricTrue.output
        * quadricTrue.output
        * trueShapes.output
These provide information about the true extents, volume, and area of 
the quadric test surfaces.  We provide these data files, but they can be
generated using the program "quadricTrue" and three simple input files. 
To generate these files, move to the "figsAndModels" subdirectory and 
execute these commands:

        cd myTests/figsAndModels
        ./quadricTrue E.onePer.input    > E.quadricTrue.output
        ./quadricTrue all.onePer.input  > quadricTrue.output
        ./quadricTrue main.onePer.input > trueShapes.output



POST-PROCESSING OF THE TEST OUTPUT
----------------------------------

We will describe how we process the output of these test cases to 
produce the graphs and tables that appear in the paper. If you run 
different test cases or otherwise modify how the software is run, you
will need to modify these post-processing procedures.

To get the .err output files into a more useable form, we concatenate
them into several aggregate data files.  We have provided a script to
do this aggregation. To run this script your current working directory
should be the directory that you created for testing the software; in
the example commands above, this directory was called "myTests".  The
script for aggregating the .err files resides in that directory.  To run
the script, move to that directory then issue this command:

        ./gatherErrors

This will create the following files in the current directory:

        * MainIG.ERR   - main isosurface results
        * MainDP.ERR   - main direct polygonization results
        * Main.ERR     - all main results
        * Big.ERR      - big test results
        * AltEll.ERR   - alternate ellipsoid results
        * IcosDP.ERR   - icosahedral polygonization results
        * BothDP.ERR   - main DP and icosahedral polygonization results

In each of these files, each line corresponds to one of the .err files.
So these files are simply aggregations and do not represent any 
additional processing of the error data. After creating these .ERR 
files, the script copies these files into a sub-directory named
"figsAndModels", where the subsequent post-processing takes place.

Further processing of the error data is done with R scripts which reside
in the figsAndModels sub-diretory. These scripts reside in the directory
polySurfErr/aux/scripts/ and all end with ".R".  To execute all of these
scripts, you can move into the figsAndModels sub-directory and invoke
the script named "mkPlots".  So the commands you issue may look like
this:
        cd myTests/figsAndModels
        ./mkPlots

Note that the script mkPlots invokes a command "pdftops" which converts
pages of the PDF files produced by the R scripts to EPS format.  If you
do not have "pdftops", you will need to comment out these lines.


MATHEMATICA CODE
----------------

We also provide a Mathematica notebook to compute the expected change in
isosurface area due to noise in the isosurface data. These results of 
these calculations are reported in the paper.  This notebook is in the
file:
        polySurfErr/aux/mNotebook/mcArea.nb

The first section, "Voxel locations" defines the eight cube corners with
a random variable for the noise in each and defines a function 
'expected' that computes the expected value of a function, f, given 
specified mean and variance for the eight random variables. The second 
section, "Triangle area" computes the expected area of a set of 
triangles within a single cube in the presence of noise. The third 
section, "Expected area for marching cubes cases" defines the triangles 
for each marching cubes case, and the area for each case with and 
without noise. The final section, "Distribution of marching cubes 
cases", assumes the target isosurface is locally planar relative to the 
cube size and considers only cubes that contain a piece of the surface. 

We assume the surface is randomly oriented with respect to the cube, and
the cube may be randomly translated by any offset that still intersects 
the surface. Given those assumptions, we test 1,000,000 random planes to
get an estimate of the distribution of marching cubes cases, and use 
that estimate to compute an overall average area with and without noise,
and expected relative error.



PRINCIPAL PROGRAMS AND SCRIPTS
------------------------------

quadricPolygonErr
        Measures errors of a polygonization relative to a quadric
        surface.  Outputs a .err file.

        This program implements the error metrics described in 
        the paper.

mkQuadricVtkVol
        Creates a gridded data set in vtk format that represents
        a quadric surface.  An isosurface generated at 0.5 should 
        approximate the quadric surface.

vtkIsoPLY_Conn
        A VTK script that generates an isosurface from a gridded
        data set. The output contains only the largest connected
        component of the isosurface and it is written in PLY
        format.

runIGQ
        Runs a series of isosurface test cases.  Invokes the
        programs mkQuadricVtkVol, vtkIsoPLY_Conn, and 
        quadricPolygonErr.

runIGQ.relSp
        A variant of runIGQ.  Used for ?????? cases

runIGQsized
        A variant of runIGQ.  Used for ?????? cases

genDirectQuadricParamFile
        Writes a short parameter file describing a direct 
        polygonization of one of the tested quadric surfaces.

quadricTrue
        Reads a brief description of one of the quadric surface
        test cases and outputs the true X, Y, and Z extents
        of the surface as well as its true volume and area.

quadricSavg
        Creates a direct polygonization of a quadric surface
        and writes out the triangles in .savg format.

seqDPQruns
        Runs a series of direct polygonization tests.  
        Invokes quadricPolygonErr.

genIcosParam
        generates small file describing an icosahedral subdivision 
        of an ellipsoid.  Output file is input to ??????

seqIcosRuns
        Runs a series of icosahedral subdivision tests.  Invokes
        genIcosParam, icosSubdivStretch, and quadricPolygonErr.

icosSubdivStretch
        Subdivides an ellipsoid by stretching an icosahedral 
        subdivision of a sphere.  Outputs a .savg file of
        triangles.

mkTestDirs
        Creates a directory tree for testing the software.

cpTestFiles
        Copies files needed for testing the software into the
        directory tree created by mkTestDirs.

gatherErrors
        This script aggregates the .err files generated in the
        test subdiretories into more manageable files.

mkPlots
        This script generates the plots and tables used in the
        paper from the aggregated error files.

mcArea.nb
        A Mathematica notebook to compute the expected change in
        isosurface area due to noise in the isosurface data, as
        described above.


--
--


