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. -- --