|
|
A screenshot of Scanalyze running on a Windows platform. Several range images of the head of Michelangelo's David are visible. Each range image represents one SD file (see below for a description of our file formats). A scrollable list of these files is visible in the upper-right corner of the screen. The range images are displayed as shaded surfaces, and all but one of them have already been aligned, so the (false-color) surfaces appear to interpenetrate. In preparation for aligning the last (red) range image, the menu that controls our implementation of the Iterated Closest Points (ICP) algorithm has been brought up in the upper-left corner. Finally, to evaluate the quality of our alignment, a plot has been made through the already-aligned range images in the region above David's right eye. The location of the plot is denoted with a red line on the main display. The plot itself is visible in the lower-right corner. Each range image is plotted in a different color, corresponding to the colors of the surfaces on the main display. In this example, the average alignment error appears to be about 1mm. One important menu that is not shown here controls our global registration algorithm, which spreads any residual alignment errors among all meshes that have been pairwise aligned. |
Scanalyze is an interactive computer graphics application for viewing, editing, aligning, and merging range images to produce dense polygon meshes. It was the primary tool used in the Digital Michelangelo Project (1997-2004) to assemble 3D models of Michelangelo's statues from laser range data. It was also used heavily in the Digital Forma Urbis Romae Project (1999-2006). This software distribution contains the source code for Scanalyze, as well as binaries compiled for SGIs (running IRIX) and PCs (running Linux or Windows). It is being made available for research and commercial use, free of charge, as described at the bottom of this web page.
Scanalyze processes three kinds of files: triangle-mesh PLY files (extension .ply), range-grid PLY files (also with extension .ply), and SD files (extension .sd). Triangle-mesh PLY files encode general triangle meshes as lists of arbitrarily connected 3D vertices, whereas range-grid PLY files and SD files encode range images as rectangular arrays of points. SD files also contain metadata that describes the geometry of the range scanner used to acquire the data. This geometry is used by Scanalyze to derive line-of-sight information for various algorithms. PLY files may also encode range images (in polygon mesh form), but they do not include metadata about the range scanner and thus do not provide line-of-sight information. For more information about PLY files, look at the file format section of the Stanford 3D Scanning Repository web page. For SD files, here is a brief description of the SD format. For more information, look at the source code for Scanalyze, or talk to us.
Scanalyze is capable of displaying hundreds of PLY or SD files at once. It is also capable of computing multi-resolution versions of these files, using one of several mesh simplification algorithms [Rossignac92, Garland97], in order to facilitate viewing of large datasets. Although we have experimented with QSplat [Rusinkiewicz00] as the display engine for Scanalyze, the version we are releasing here uses OpenGL polygon rendering. We therefore recommend running Scanalyze on a machine with hardware OpenGL acceleration. We typically use an SGI Onyx with InfiniteReality graphics or a PC with Nvidia Geforce4 graphics. The largest dataset we have loaded into Scanalyze is our scan of Michelangelo's statue of David, which contains about four hundred SD files totaling 2 billion range samples. Needless to say, for datasets of this size we recommend a computer with plenty of physical memory (at least 1 GB) and swap space (many GB).
Once these PLY or SD files have been loaded, they can be pairwise aligned using a variety of techniques - some manual (i.e. pointing and clicking) and some automatic. The most powerful of these is a a variant [Rusinkiewicz01] of the popular Iterated Closest Point (ICP) algorithm [Besl92]. Pairs of scans can be selected for alignment either automatically (so-called all-pairs alignment) or manually, by choosing two scans from a list. These pairwise alignments can optionally be followed by a global registration step [Pulli99] whose purpose is to spread the alignment error evenly across the available pairs. The new positions and orientations of each PLY or SD file can be stored as a transform file (extension .xf) containing a 4 x 4 matrix. Recently, we have been working on ways to make our mesh alignment more robust. This has lead to a pair of papers that will appear in Proc. 3DIM '03. The first is Geometrically Stable Sampling for the ICP Algorithm, by Natasha Gelfand, Szymon Rusinkiewicz, and Marc Levoy. The second is A Hierarchical Method for Aligning Warped Meshes, by Leslie Ikemoto, Natasha Gelfand, and Marc Levoy. These new algorithms have been incorporated into scanalyze, but are not yet available in the released version.
As explained earlier, an SD file always contains range images, while a PLY may contain range images (in mesh form) or general meshes. Our alignment algorithms can be run on range images or general meshes. If the input files contain strictly range images, then after alignment they can be merged using the VRIP volumetric range image processing algorithm [Curless96] to form a single seamless polygon mesh. This mesh may have arbitrary topological genus, so it can only be stored as a PLY file. The code for VRIP must be downloaded and installed separately from Scanalyze. This code includes two variants of the merging algorithm: one designed for in-core merging of moderate-sized datasets, and a second designed for out-of-core merging of larger datasets. These variants, and the overall alignment and merging pipeline, are described in [Levoy00]. The largest mesh we have created using this pipeline (Michelangelo's statue of St. Matthew) contains 386 million polygons.
After alignment and merging, most meshes still contain holes. The number and size of these holes depends on the geometry of the object being scanned, the number of scans acquired, and the capabilities of the range scanner. Regardless of their size, these holes may have a complex geometry (hundreds of edges) and/or a complex topology (many islands floating in the hole). To address this problem, we have developed a hole filling algorithm based on volumetric diffusion [Davis02]. This algorithm is available as a separate software package called Volfill. The input to this package is a VRI file (extension .vri) containing the output of Scanalyze's VRIP algorithm, but in an intermediate, volumetric form. The output is a PLY file containing a seamless (hole-free) polygon mesh. For more information about VRI files, look at the source code for VRIP, or the hole filler, or talk to us. Sample VRI files are available on the Volfill web page.
In addition to its primary function of aligning and merging polygon meshes, Scanalyze includes simple utilities for examining, plotting, and editing these meshes. These utilities are not intended to replace a general mesh editing package. For this purpose, we frequently use Paraform. Scanalyze also includes software for loading photographic data and projecting this data into the meshes. However, this software is incomplete and not particularly robust.
To summarize, Scanalyze offers the following capabilities:
Scanalyze is research code. We are releasing it mainly to encourage other researchers to compare their pipelines for processing range data against ours and thereby to improve on our algorithms. People may also find Scanalyze useful for aligning and merging range data, but it is not production-quality code. Furthermore, there is no user's manual for Scanalyze. Most of the menu items are self-explanatory, but some will require familiarity with the principal algorithms on which Scanalyze is based.
This said, there are endless possibilities for combining the capabilities of Scanalyze with other software packages. In particular, there are other range image alignment algorithms, surface reconstruction algorithms, mesh decimation algorithms, and hole filling algorithms available commerically and in the research community. One mesh decimation algorithm we have used successfully in our work is OutOfCore simplif, by Cignoni, Rocchini, Montani, and Scopigno.
Finally, although Scanalyze can be used to process range data such as might be produced by a laser rangefinder or machine vision system, it is not a system for producing range data. Please do not send us email asking about 3D scanning technology; we frankly don't have time to answer them. Instead, we suggest looking at the many good web sites out there. A good place to start might be the list of 3D scanners on http://www.geomagic.com/support/resources/. A comprehensive web site on 3D scanning technologies, surface reconstruction algorithms, and places to go for 3D data (including a pointer back to our web pages) is http://w3.impa.br/~pcezar/3dp/original/scan-fausto.html.
Scanalyze was developed over a period of approximately five years in the Stanford Computer Graphics Laboratory. Its principal authors were Kari Pulli and Matt Ginzton. More specifically, the software for aligning range images was developed by Kari Pulli. The parallelization of Brian Curless's vrip package was written by David Koller and Lucas Pereira. The color processing software was written by Szymon Rusinkiewicz. The data conversion modules for the Cyberware, 3D Scanners Ltd., and Cyra Technologies scanners were written by David Koller, Lucas Pereira, and Jeremy Ginsberg, respectively. The graphical user interface and supporting code was written by Kari Pulli, Matt Ginzton, and James Davis, with additional contributions by everybody else working on the project. The code base for Scanalyze also includes some code leftover from "plyview", an earlier software package written by Brian Curless, based on an even earlier package written by Greg Turk. Sean Anderson, Kurt Berglund, and Arjun Rihan wrote additional software and helped debug the package. The latter two worked under the supervision of Stephen Marschner. The Digital Michelangelo Project was directed by Marc Levoy.
[Besl92] Besl, P. and McKay, N.,
A Method for Registration of 3-D Shapes,
IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-14, No. 2, February, 1992, pp. 239-256.[Curless96] A Volumetric Method for Building Complex Models from Range Images
Brian Curless and Marc Levoy
Computer Graphics (SIGGRAPH 96 Proceedings)[Davis02] Filling holes in complex surfaces using volumetric diffusion
James Davis, Steve Marschner, Matt Garr, and Marc Levoy
First International Symposium on 3D Data Processing, Visualization, Transmission, June, 2002.[Garland97] Garland, M., Heckbert, P.S.,
Surface simplification using quadric error metrics,
Computer Graphics (SIGGRAPH 97 Proceedings)[Levoy00] The Digital Michelangelo Project: 3D scanning of large statues
Marc Levoy, Kari Pulli, Brian Curless, Szymon Rusinkiewicz, David Koller, Lucas Pereira,
Matt Ginzton, Sean Anderson, James Davis, Jeremy Ginsberg, Jonathan Shade, and Duane Fulk
Computer Graphics (SIGGRAPH 2000 Proceedings).[Pulli99] Multiview Registration for Large Data Sets
Kari Pulli
Proc. Second International Conference on 3-D Digital Imaging and Modeling (3DIM '99)[Rossignac92] Rossignac, J.R., and Borrel, Paul.,
Multi-Resolution 3D Approximations for Rendering Complex Scenes.
IBM Research Report, February 19, 1992.[Rusinkiewicz00] QSplat: A Multiresolution Point Rendering System for Large Meshes
Szymon Rusinkiewicz and Marc Levoy
Computer Graphics (SIGGRAPH 2000 Proceedings)[Rusinkiewicz01] Efficient Variants of the ICP Algorithm
Szymon Rusinkiewicz and Marc Levoy
Proc. 3DIM 2001
Scanalyze binaries and source code are available for Linux, IRIX, and Windows. The current release of Scanalyze is version 1.0.3.
In addition, Alexander Agathos has assembled a distribution for Windows 7. After unpacking the tar, set the the enviromental variable SCANALYZE_DIR to the directory containing scanalyze.exe. We have not tested this distribution.
The following paragraphs are intended as a quick summary only. Please consult the README file in the source code distribution for a complete description of the different build versions available on each platform.
Download the source code file, uncompress it, and type make. If you do not have Tcl/Tk version 8.0 or greater installed on your computer, you will need to download it. The main Scanalyze distribution compiles cleanly with pre-3.0 versions of g++, but may not build on more recent Linux systems due to STL incompatibilities. Luke Campagnola of Colorado School of Mines has patched Scanalyze to overcome these incompatibilities and provided his code for download: scanalyze-1.0.3-stl_fix.tar.gz (7.6 MBytes). For additional help on building Scanalyze, see the Scanalyze FAQ file.
Download the source code file, uncompress it, and type make. If you do not have Tcl/Tk version 8.0 or greater installed on your computer, you will need to download it.
To compile Scanalyze for Windows, you will need two more packages: SGI's IFL (image format library - 4.2M bytes) and Tcl/Tk version 8.0p2 (1.7M bytes). Unfortunately, under Windows Scanalyze only works with this version of Tcl/Tk, while any version greater than 8.0 will work with Linux or IRIX. You also need Gnu Make; we use the version that comes with Cygwin (13.6M bytes).
To build Scanalyze for Windows, you should:
To run Scanalyze for Windows, you will need two more packages: SGI's IFL (image format library) and Tcl/Tk version 8.0p2 (later versions are not compatible yet).
Note: Scanalyze can be driven either using Tcl commands (at its command prompt) or a mouse. For the latter, a 3-button mouse is required, even on a PC.
An archive of freely available PLY files can be found in the Stanford 3D Scanning Repository. An example dataset of SD files will be available shortly.
We are also distributing our scans of the statues of Michelangelo in PLY (and eventually SD) format, for scientific use only. These datasets require a (free) license, which at present is available only to published researchers or other scholars. Click here for a description of the Digital Michelangelo Project Archive of 3D Models and for instructions on applying for a license.
Copyright � 2002 the Board of Trustees of The Leland Stanford Junior University. All rights reserved.
During the period 1995-2007, this software was covered by the Stanford Computer Graphics Laboratory's custom-written General Software License. This license is royalty-free, nonexclusive, and nontransferable. Click here to view its terms and conditions. In modification of these terms and conditions, users were permitted to distribute or sell derivatives of this software without accounting to Stanford or the developers, and without payment of royalties to Stanford or the developers. However, title and copyright to the software and documentation remained with Stanford, and users were required to acknowledge the contribution of Stanford in any derivatives, as detailed in the license.
For downloads beginning on August 23, 2007, this software is covered by a new General Software License, which is based on the BSD license.
As noted earlier, Scanalyze is research code, not production code. Moreover,
the authors of Scanalyze have long since graduated and left Stanford. We
welcome questions, bug reports, and suggestions, but we do not guarantee timely
responses to them. Email about Scanalyze should be sent to:
scanalyze-question at graphics dot stanford dot edu