% multiresolution modeling and surface simplification bibliography
%
% This is a bibliography, in bibtex format, of multiresolution modeling
% (a.k.a. level of detail modeling), curve and surface simplification, and
% related ideas, including:
% * applied mathematics (approximation theory)
% * computational geometry (triangulation, data structures)
% * computer aided design (surface modeling),
% * computer vision (shape acquisition, surface model fitting)
% * computer graphics (rendering complex scenes,
% visualization, real time, interactive display),
% * simulators (flight/driving, virtual reality),
% * cartography (geographic information systems, terrain models)
%
% The types of surfaces dealt with include height fields (e.g. terrains),
% parametric surfaces, manifolds, manifolds with boundary, and
% non-manifolds (e.g. arbitrary set of possibly intersecting polygons).
% The most common surface simplification methods work with piecewise
% planar triangular meshes, but some methods employ
% curved parametric surfaces.
%
% We have included URL's to papers or software, where known.
% Please send corrections to Heckbert's email address below.
%
% For more web info on multiresolution modeling, see
% http://www.cs.cmu.edu/~garland/multires.html
%
% Paul S. Heckbert - http://www.cs.cmu.edu/~ph
% and Michael Garland - http://www.cs.cmu.edu/~garland
% 19 Nov 1996
%
% with thanks to Joseph Mitchell and Randolph Franklin
@STRING{heckbert_email = "Paul Heckbert, ph+@cs.cmu.edu"}
@STRING{garland_email = "Michael Garland, garland+@cs.cmu.edu"}
% All URLs are escaped with the \URL{} macro. This allows the user to
% format them as they please.
% One simple formatting method for URL's, in Latex, is to simply define
% \def\URL#1{#1}
% and then, after running bibtex, run the following shell script to patch
% up the bbl file.
%
% ----------------------
% # insert discretionary hyphens so that long URLs or other UNIX
% # pathnames won't cause extremely underfull hboxes.
% # also quote the characters #~_& in URL's and pathnames
% cp $1.bbl $1.old.bbl
% sed \
% -e 's/\/~/\/$\\sim$/g' \
% -e 's/\//\/\\discretionary{}{}{}/g' \
% -e 's/\([^\\]\)#/\1\\#/g' \
% -e '/URL/s/_/\\_/g' \
% -e '/URL/s/&/\\&/g' \
% <$1.old.bbl >$1.bbl
% ----------------------
@Book{Spivak79,
keyword = "differential geometry",
author = "Spivak, Michael",
title = "A Comprehensive Introduction to Differential Geometry",
publisher = "Publish or Perish, Inc.",
year = "1979",
}
@Article{Chew89,
author = "L. Paul Chew",
title = "Constrained {Delaunay} Triangulations",
journal = "Algorithmica",
year = 1989,
volume = 4,
pages = "97--108"
}
@Article{Guibas85,
author = "Leonidas Guibas and Jorge Stolfi",
title = "Primitives for the manipulation of general
subdivisions and the computation of {Voronoi}
diagrams",
journal = "ACM Transactions on Graphics",
year = 1985,
volume = 4,
number = 2,
pages = "75--123"
}
@article{Guibas92increm,
author = "Leonidas J. Guibas and Donald E. Knuth and Micha Sharir",
title = "Randomized incremental construction of {Delaunay} and {Voronoi} diagrams",
journal = "Algorithmica",
volume = 7,
year = 1992,
pages = "381--413",
note = {
Also in Proc. 17th Intl. Colloq. --- Automata, Languages, and Programming,
Springer-Verlag, 1990, pp. 414--431},
}
@InProceedings{Guibas90increm,
author = "Leonidas J. Guibas and Donald E. Knuth and Micha Sharir",
title = "Randomized incremental construction of {Delaunay} and
{Voronoi} diagrams",
volume = 443,
series = "Springer-Verlag {LNCS}",
pages = "414--431",
booktitle = "Proc. 17th Intl. Colloq. --- Automata, Languages,
and Programming",
year = 1990,
publisher = "Springer-Verlag",
address = "Berlin"
}
@Article{Mallat89,
author = "Stephane G. Mallat",
title = "A Theory for Multiresolution Signal Decomposition:
The Wavelet Representation",
journal = "IEEE Trans. on Pattern Analysis and Machine
Intelligence",
year = 1989,
volume = 11,
number = 7,
pages = "674--693",
month = "July"
}
@Article{Hughes91,
author = "Peter Hughes",
title = "Building a Terrain Renderer",
journal = "Computers in Physics",
year = 1991,
pages = "434--437",
month = "July/August",
annote = {describes pyramid techniques used to create "Mars Navigator"
interactive videodisk},
}
@Incollection{Lischinski94,
author={Dani Lischinski},
title={Incremental {D}elaunay Triangulation},
booktitle={Graphics Gems IV},
editor={Paul Heckbert},
pages={47--59},
publisher={Academic Press},
year={1994},
address={Boston},
keywords={mesh generation, polygonization, Voronoi diagram,
Delaunay triangulation},
}
@article{Polis92iuw,
AUTHOR = "Polis, M.F. and Jr., D.M.McKeown",
TITLE = "Iterative {TIN} Generation From Digital Elevation Models",
JOURNAL = "DARPA Image Understanding Workshop",
VOLUME = "92",
YEAR = "1992",
PAGES = "885--897"
}
@INPROCEEDINGS{Polis92,
AUTHOR={Michael F. Polis and David M. {McKeown, Jr.}},
TITLE={Iterative {TIN} Generation from Digital Elevation Models},
BOOKTITLE={Conf. on Computer Vision and Pattern Recognition (CVPR '92)},
PUBLISHER={IEEE Comput. Soc. Press},
YEAR={1992},
PAGES={787--790},
NOTE={\URL{http://www.cs.cmu.edu/~MAPSLab}},
keywords={
digital evaluation models, triangulated irregular network,
approximate terrain description, topographic features,
user-supplied error tolerance
},
ABSTRACT={
A technique for producing a triangulated irregular network
(TIN) from a digital elevation model (DEM) is described. The
overall goal is to produce an approximate terrain description
that preserves the major topographic features using a greatly
reduced set of points selected from the original DEM. The TIN
generation process is iterative; at each iteration, areas in
the DEM that lie outside of a user-supplied error tolerance in
the TIN are identified, and points are chosen from the DEM to
more accurately model these areas. Point selection involves the
computation of the difference between the actual DEM and an
approximate DEM. This approximate DEM is calculated by
interpolating elevation points from the TIN.
},
}
@inproceedings{Polis93,
author = "Michael F. Polis and David M. {McKeown, Jr.}",
title = "Issues in Iterative {TIN} Generation to Support Large
Scale Simulations",
BOOKTITLE={Proc. of Auto-Carto 11
(Eleventh Intl. Symp. on Computer-Assisted Cartography)},
year = "1993",
month = "November",
pages = "267--277",
NOTE = {\URL{http://www.cs.cmu.edu/~MAPSLab}},
}
@ARTICLE{Polis95,
AUTHOR={Michael F. Polis and Stephen J. Gifford and David M. {McKeown, Jr.}},
TITLE={Automating the Construction of Large-Scale Virtual Worlds},
JOURNAL={Computer},
MONTH={July},
YEAR={1995},
PAGES={57--65},
KEYWORDS={simulator, terrain, cartography},
NOTE={\URL{http://www.cs.cmu.edu/~MAPSLab}},
ANNOTE={
Also in Proceedings of the ARPA Image Understanding Workshop,
Monterey, CA, Nov. 1994, Morgan Kaufmann Pub., pages 931--946;
and tech report CMU-CS-94-199.
},
}
@Article{Scarlatos92hier,
author = "Lori Scarlatos and Theo Pavlidis",
title = "Hierarchical Triangulation Using Cartographic Coherence",
journal = "CVGIP: Graphical Models and Image Processing",
year = "1992",
volume = "54",
number = "2",
pages = "147--161",
month = "March"
}
@InProceedings{Scarlatos92curv,
author = "Lori L. Scarlatos and Theo Pavlidis",
title = "Optimizing triangulations by curvature equalization",
booktitle = "Proc. Visualization '92",
publisher = "IEEE Comput. Soc. Press",
pages = "333--339",
year = "1992",
}
@PHDTHESIS{Scarlatos93,
AUTHOR={Lori Scarlatos},
TITLE={Spatial Data Representations for Rapid Visualization and Analysis},
SCHOOL={CS Dept, State U. of New York at Stony Brook},
YEAR={1993},
keywords={terrain, surface simplification, hierarchical triangulation,
multiresolution model},
}
@Article{Dunham86,
author = "James George Dunham",
title = "Optimum Uniform Piecewise Linear Approximation of
Planar Curves",
journal = "IEEE Transactions on Pattern Analysis and Machine
Intelligence",
year = "1986",
volume = "8",
number = "1",
pages = "67--75",
month = "January"
}
@INPROCEEDINGS{Ihm91,
author = "Insung Ihm and Bruce Naylor",
title = "Piecewise Linear Approximations of Digitized Space
Curves with Applications",
pages = "545--569",
BOOKTITLE={Scientific Visualization of Physical Phenomena},
EDITOR={N. M. Patrikalakis},
PUBLISHER={Springer-Verlag},
ADDRESS={Tokyo},
YEAR={1991},
ANNOTE={Proc. of CGI 91, Cambridge, MA, 1991.},
}
@ARTICLE{Clark76,
AUTHOR={James H. Clark},
TITLE={Hierarchical Geometric Models for Visible Surface Algorithms},
JOURNAL={CACM},
VOLUME={19},
NUMBER={10},
MONTH={Oct.},
YEAR={1976},
PAGES={547--554},
keywords={bounding volume, spatial data structure},
}
@BOOK{Upstill90,
AUTHOR={Steve Upstill},
TITLE={The Renderman Companion},
PUBLISHER={Addison Wesley},
ADDRESS={Reading, MA},
YEAR={1990},
keywords={geometric modeling},
ANNOTE={Pixar's Renderman subroutine interface for describing scenes to renderers},
}
@ARTICLE{Hanrahan91,
AUTHOR={Pat Hanrahan and David Salzman and Larry Aupperle},
TITLE={A Rapid Hierarchical Radiosity Algorithm},
MONTH={July},
YEAR={1991},
JOURNAL={Computer Graphics
(SIGGRAPH '91 Proc.)},
VOLUME={25},
NUMBER={4},
PAGES={197--206},
ANNOTE={adaptive sampling of kernel in quadtree-like fashion
motivated by Greengard's fast n-body algorithm},
}
@ARTICLE{Turk92,
author = "Greg Turk",
title = "Re-tiling polygonal surfaces",
pages = "55--64",
journal = "Computer Graphics (SIGGRAPH '92 Proc.)",
volume = "26",
number = "2",
year = "1992",
month = "July",
keywords = "model simplification, automatic mesh generation,
constrained triangulation, levels-of-detail, shape
interpolation" ,
}
@Article{Schroeder88,
author = "W. J. Schroeder and M. S. Shephard",
title = "Geometry-based fully automatic mesh generation and the
{Delaunay} triangulation",
journal = "Int. J. Numer. Meth. Eng.",
volume = "26",
year = "1988",
pages = "2503--2515",
}
@ARTICLE{Schroeder92,
author = "William J. Schroeder and Jonathan A. Zarge and William E.
Lorensen" ,
title = "Decimation of triangle meshes",
pages = "65--70",
journal = "Computer Graphics (SIGGRAPH '92 Proc.)",
volume = "26",
number = "2",
year = "1992",
month = "July",
keywords = "geometric modeling, medical imaging, terrain modeling,
volume modeling, multiresolution",
}
@INCOLLECTION{Schroeder94cell,
author = "William J. Schroeder and Boris Yamrom",
title = "A Compact Cell Structure for Scientific Visualization",
pages = "53--59",
booktitle = {SIGGRAPH '94 Course Notes CD-ROM,
Course 4: Advanced Techniques for Scientific Visualization},
publisher={ACM SIGGRAPH},
year = "1994",
month = "July",
keywords = "data structure, polygon",
}
@BOOK{Schroeder96vtk,
TITLE={The Visualization Toolkit, An Object-Oriented Approach To {3D} Graphics},
AUTHOR={Will Schroeder and Ken Martin and Bill Lorensen},
PUBLISHER={Prentice Hall},
YEAR={1996},
NOTE={code at \URL{http://www.cs.rpi.edu:80/~martink/}},
ANNOTE={includes triangulated mesh decimation software, marching cubes},
}
@Article{DeHaemer91,
author = "Michael {DeHaemer, Jr.} and Michael J. Zyda",
title = "Simplification of objects rendered by polygonal
approximations" ,
pages = "175--184",
journal = "Computers and Graphics",
volume = "15",
number = "2",
year = "1991",
}
@Article{Capoyleas91,
author = "V. Capoyleas and G. Rote and G. Woeginger",
title = "Geometric clusterings",
journal = "J. Algorithms",
volume = "12",
year = "1991",
pages = "341--356",
oldlabel = "geom-2217.2",
succeeds = "crw-gc-90",
}
@InProceedings{Capoyleas90,
author = "V. Capoyleas and G. Rote and G. Woeginger",
title = "Geometric clusterings",
booktitle = "Proc. 2nd Canad. Conf. Comput. Geom.",
year = "1990",
pages = "28--31",
oldlabel = "geom-2217.1",
precedes = "crw-gc-91",
}
@InProceedings{Beigbeder91,
author = "Michel Beigbeder and Ghassan Jahami",
title = "Managing levels of detail with textured polygons",
pages = "479--489",
booktitle = "COMPUGRAPHICS '91",
volume = "I",
year = "1991",
conference = "held in Sesimbra, Portugal; 16-20 September 1991",
}
@InProceedings{Haralick77,
author = "R. M. Haralick and L. G. Shapiro",
title = "Decomposition of polygonal shapes by clustering",
booktitle = "IEEE Comput. Soc. Conf. Pattern Recognition Image Process.",
year = "1977",
pages = "183--190",
}
@BOOK{Rosenfeld84,
EDITOR={Azriel Rosenfeld},
TITLE={Multiresolution Image Processing and Analysis},
ANNOTE={Leesberg, VA, July 1982},
PUBLISHER={Springer},
ADDRESS={Berlin},
YEAR={1984},
keywords={image pyramid},
}
@ARTICLE{Kajiya85,
AUTHOR={James T. Kajiya},
TITLE={Anisotropic Reflection Models},
JOURNAL={Computer Graphics
(SIGGRAPH '85 Proc.)},
VOLUME={19},
NUMBER={3},
MONTH={July},
YEAR={1985},
PAGES={15--21},
keywords={texture mapping, level of detail},
ANNOTE={frame mapping},
}
@INPROCEEDINGS{Perlin84,
AUTHOR={Ken Perlin},
TITLE={A Unified Texture/Reflectance Model},
BOOKTITLE={SIGGRAPH '84 Advanced Image Synthesis seminar notes},
MONTH={July},
YEAR={1984},
keywords={texture mapping, bump mapping},
ANNOTE={making microfacet distribution functions consistent
with normal perturbations; hash function},
}
@INPROCEEDINGS{Perlin85,
AUTHOR={Ken Perlin},
TITLE={Course Notes},
BOOKTITLE={SIGGRAPH '85 State of the Art in Image Synthesis seminar notes},
MONTH={July},
YEAR={1985},
keywords={antialiasing, filter, blur},
ANNOTE={generalizing Crow's summed-area tables to higher order filter kernels},
}
@PHDTHESIS{MacDougal84,
AUTHOR={Paul D. MacDougal},
TITLE={Generation and Management of Object Description Hierarchies for
Simplification of Image Generation},
SCHOOL={Ohio State U.},
MONTH={Aug.},
YEAR={1984},
keywords={geometric modeling},
ANNOTE={generate lower level of detail models as a post-process},
}
@ARTICLE{Bergman86,
AUTHOR={Larry Bergman and Henry Fuchs and Eric Grant and Susan Spach},
TITLE={Image Rendering by Adaptive Refinement},
JOURNAL={Computer Graphics
(SIGGRAPH '86 Proc.)},
VOLUME={20},
NUMBER={4},
MONTH={Aug.},
YEAR={1986},
PAGES={29--37},
keywords={image synthesis},
ANNOTE={display low res/cheap during interaction, refine when user pauses},
}
@ARTICLE{Painter89,
AUTHOR={James Painter and Kenneth Sloan},
TITLE={Antialiased Ray Tracing by Adaptive Progressive Refinement},
JOURNAL={Computer Graphics
(SIGGRAPH '89 Proc.)},
VOLUME={23},
NUMBER={3},
MONTH={July},
YEAR={1989},
PAGES={281--288},
keywords={adaptive subdivision, stochastic sampling},
}
@ARTICLE{Rheinboldt80,
AUTHOR={Werner Rheinboldt and Charles K. Mesztenyi},
TITLE={On a Data Structure for Adaptive Finite Element Mesh Refinements},
JOURNAL={ACM Trans. on Math. Software},
VOLUME={6},
NUMBER={2},
MONTH={June},
YEAR={1980},
PAGES={166--187},
keywords={adaptive mesh, restricted quadtree},
}
@INPROCEEDINGS{Bank83,
AUTHOR={Randolph E. Bank and Andrew H. Sherman and Alan Weiser},
TITLE={Refinement Algorithms and Data Structures for Regular Local Mesh Refinement},
BOOKTITLE={Scientific Computing, IMACS Trans. on Scientific Computation},
VOLUME={1},
EDITOR={R. Stepleman et al},
PUBLISHER={North-Holland},
YEAR={1983},
keywords={adaptive mesh, restricted quadtree},
}
@ARTICLE{Westin92,
author = "Stephen H. Westin and James R. Arvo and Kenneth E.
Torrance" ,
title = "Predicting Reflectance Functions From Complex Surfaces",
year = "1992",
month = "July",
volume = "26",
number = "4",
journal = "Computer Graphics (SIGGRAPH '92 Proc.)",
pages = "255--264",
keywords = "monte carlo, shading",
}
@InProceedings{Fournier92,
author = "Alain Fournier",
title = "Normal distribution functions and multiple surfaces",
pages = "45--52",
booktitle = "Graphics Interface '92 Workshop on Local Illumination",
month = "May",
year = "1992",
conference = "held in Vancouver, B.C.; 11 May 1992",
keywords = "local illumination, bump map filtering, mesoscopic level",
annote = "Fournier introduces the concept of distribution of surface
normals to capture the reflection between the microscopic
(Phong, Blinn, Cook) and the macroscopic (geometric) level.
He establishes its parallel with the standard BRDFs and
describes their use to produce with simplicity complex
surface definitions and how to render them efficiently. " ,
}
@ARTICLE{Cabral87,
author = "Brian Cabral and Nelson Max and Rebecca Springmeyer",
title = "Bidirectional Reflection Functions From Surface Bump Maps",
year = "1987",
month = "July",
volume = "21",
number = "4",
journal = "Computer Graphics (SIGGRAPH '87 Proc.)",
pages = "273--281",
}
@ARTICLE{Tanimoto75,
AUTHOR={Steven L. Tanimoto and Theo Pavlidis},
TITLE={A Hierarchical Data Structure for Picture Processing},
JOURNAL={Computer Graphics and Image Processing},
VOLUME={4},
NUMBER={2},
MONTH={June},
YEAR={1975},
PAGES={104--119},
keywords={image pyramid},
}
@ARTICLE{Williams83,
AUTHOR={Lance Williams},
TITLE={Pyramidal Parametrics},
JOURNAL={Computer Graphics
(SIGGRAPH '83 Proc.)},
VOLUME={17},
NUMBER={3},
MONTH={July},
YEAR={1983},
PAGES={1--11},
keywords={texture mapping, antialiasing},
}
@PHDTHESIS{Teller92phd,
AUTHOR={Seth J. Teller},
TITLE={Visibility Computations in Densely Occluded Polyhedral Environments},
SCHOOL={CS Division, UC Berkeley},
MONTH={October},
YEAR={1992},
NOTE={Tech. Report UCB/CSD-92-708},
keywords={computational geometry, architectural walkthrough},
}
@Article{Fournier82fractal,
author = "A. Fournier and D. Fussell and L. Carpenter",
title = "Computer Rendering of Stochastic Models",
pages = "371--384",
journal = "Communications of the ACM",
volume = "25",
number = "6",
year = "1982",
month = "June",
keywords = "I35 stochastic processes, CACM, model natural terrain
stochastic" ,
}
@TECHREPORT{Heckbert89,
AUTHOR={Paul S. Heckbert},
TITLE={Fundamentals of Texture Mapping and Image Warping},
NOTE={Master's thesis, UCB/CSD 89/516,
\URL{http://www.cs.cmu.edu/~ph}},
INSTITUTION={CS Division, EECS Dept, UC Berkeley},
MONTH={May},
YEAR={1989},
ANNOTE={geometric mappings (affine, bilinear, projective),
image resampling theory},
}
@ARTICLE{Lane80,
AUTHOR={Jeffrey M. Lane and Loren C. Carpenter and Turner Whitted and James F. Blinn},
TITLE={Scan Line Methods for Displaying Parametrically Defined Surfaces},
JOURNAL={CACM},
VOLUME={23},
NUMBER={1},
MONTH={Jan.},
YEAR={1980},
PAGES={23--34},
ownerofcopy={ph},
keywords={bicubic patch},
}
@BOOK{Samet90analysis,
AUTHOR={Hanan Samet},
TITLE={The Design and Analysis of Spatial Data Structures},
ADDRESS={Reading, MA},
PUBLISHER={Addison-Wesley},
YEAR={1990},
keywords={quadtree, octree},
}
@BOOK{Samet90appl,
AUTHOR={Hanan Samet},
TITLE={Applications of Spatial Data Structures},
ADDRESS={Reading, MA},
PUBLISHER={Addison-Wesley},
YEAR={1990},
keywords={quadtree, octree},
}
@ARTICLE{Greengard87,
AUTHOR={L. Greengard and V. Rokhlin},
TITLE={A Fast Algorithm for Particle Simulations},
JOURNAL={J. Computational Physics},
VOLUME={73},
YEAR={1987},
PAGES={325--348},
keywords={fast n-body algorithm},
}
@ARTICLE{Cohen88,
AUTHOR={Michael F. Cohen and Shenchang Eric Chen and John R. Wallace and Donald P. Greenberg},
TITLE={A Progressive Refinement Approach to Fast Radiosity Image Generation},
JOURNAL={Computer Graphics
(SIGGRAPH '88 Proc.)},
VOLUME={22},
NUMBER={4},
MONTH={Aug.},
YEAR={1988},
PAGES={75--84},
KEYWORDS={progressive radiosity},
}
@ARTICLE{Arvo87,
author = "James Arvo and David Kirk",
title = "Fast Ray Tracing by Ray Classification",
year = "1987",
month = "July",
volume = "21",
number = "4",
journal = "Computer Graphics (SIGGRAPH '87 Proc.)",
pages = "55--64",
keywords = "octree",
}
@INPROCEEDINGS{Blake87,
AUTHOR={Edwin H. Blake},
TITLE={A Metric for Computing Adaptive Detail in Animated Scenes using
Object-Oriented Programming},
BOOKTITLE={Eurographics `87},
EDITOR={G. Marechal},
PUBLISHER={Elsevier Science Publishers},
YEAR={1987},
KEYWORDS={multiresolution},
ANNOTE={early level of detail selection paper},
}
@INPROCEEDINGS{Funkhouser92,
AUTHOR={Thomas A. Funkhouser and Carlo H. S\'equin and Seth J. Teller},
TITLE={Management of Large Amounts of Data in Interactive
Building Walkthroughs},
BOOKTITLE={1992 Symposium on Interactive {3D} Graphics},
PAGES={11--20},
YEAR={1992},
KEYWORDS={multiresolution, visibility},
NOTE={Special issue of Computer Graphics},
ANNOTE={static level of detail selection algorithm},
}
@ARTICLE{Funkhouser93,
AUTHOR={Thomas A. Funkhouser and Carlo H. S\'equin},
TITLE={Adaptive Display Algorithm for Interactive Frame Rates During
Visualization of Complex Virtual Environments},
JOURNAL={Computer Graphics (SIGGRAPH '93 Proc.)},
YEAR={1993},
KEYWORDS={multiresolution},
ANNOTE={adaptive level of detail selection algorithm},
}
@PHDTHESIS{Funkhouser93phd,
AUTHOR={Thomas A. Funkhouser},
TITLE={Database and Display Algorithms for Interactive Visualization of
Architectural Models},
SCHOOL={CS Division, UC Berkeley},
YEAR={1993},
keywords={multiresolution, architectural walkthrough},
}
@TECHREPORT{Rossignac92,
AUTHOR={Jarek Rossignac and Paul Borrel},
TITLE={Multi-resolution {3D} approximations for rendering complex scenes},
NOTE={IBM Research Report RC 17697.
Also appeared in {\em Modeling in Computer Graphics}, Springer, 1993},
MONTH={Feb.},
YEAR={1992},
INSTITUTION={Yorktown Heights, NY 10598},
KEYWORDS={multiresolution},
ANNOTE={automatic generation and selection algorithms},
}
@INPROCEEDINGS{Rossignac93,
AUTHOR={Jarek Rossignac and Paul Borrel},
TITLE={Multi-resolution {3D} approximations for rendering complex scenes},
BOOKTITLE={Modeling in Computer Graphics: Methods and Applications},
EDITOR={B. Falcidieno and T. Kunii},
PUBLISHER={Springer-Verlag},
ADDRESS={Berlin},
YEAR={1993},
PAGES={455--465},
NOTE={Proc. of Conf., Genoa, Italy, June 1993.
(Also available as IBM Research Report RC 17697,
Feb. 1992, Yorktown Heights, NY 10598)},
KEYWORDS={multiresolution},
ANNOTE={automatic generation and selection algorithms},
}
@TECHREPORT{Schneider94tr,
AUTHOR={Bengt-Olaf Schneider and Paul Borrel and Jai Menon
and Josh Mittleman and Jarek Rossignac},
TITLE={{BRUSH} as a Walkthrough System for Architectural Models},
NOTE={IBM Research Report RC 19638,
\URL{http://www.research.ibm.com/xw-p4205-rc19638.html}},
INSTITUTION={Yorktown Heights, NY 10598},
MONTH={May},
YEAR={1994},
}
@INPROCEEDINGS{Schneider95erw,
AUTHOR={Bengt-Olaf Schneider and Paul Borrel and Jai Menon
and Josh Mittleman and Jarek Rossignac},
TITLE={{BRUSH} as a Walkthrough System for Architectural Models},
BOOKTITLE={Rendering Techniques '95},
publisher={Springer-Verlag},
address={New York},
YEAR={1995},
PAGES={389--399},
NOTE={Proc. of the Fifth Eurographics Workshop on Rendering,
\URL{http://www.research.ibm.com/xw-p4205-rc19638.html}},
}
@MISC{IBM95ia,
AUTHOR={IBM},
TITLE={{IBM 3D Interaction Accelerator}},
YEAR={1995},
NOTE={commercial software, \URL{http://www.research.ibm.com/3dix}},
}
@BOOK{Schachter83,
EDITOR={Bruce J. Schachter},
TITLE={Computer Image Generation},
PUBLISHER={John Wiley and Sons},
CITY={New York},
YEAR={1983},
KEYWORDS={multiresolution, flight simulator},
}
@TECHREPORT{Zyda91,
AUTHOR={Michael J. Zyda},
TITLE={Course Notes, Book 10},
INSTITUTION={Graphics \& Video Laboratory, Dept. of Computer Science,
Naval Postgraduate School, Monterey, CA},
MONTH={November},
YEAR={1991},
KEYWORDS={multiresolution},
ANNOTE={Notes discussing automatic generation and selection algorithms},
}
@ARTICLE{Baum91,
AUTHOR={Daniel R. Baum and Stephen Mann and Kevin P. Smith and James M. Winget},
TITLE={Making Radiosity Usable: Automatic Preprocessing and Meshing Techniques
for the Generation of Accurate Radiosity Solutions},
MONTH={July},
YEAR={1991},
JOURNAL={Computer Graphics
(SIGGRAPH '91 Proc.)},
VOLUME={25},
NUMBER={4},
PAGES={51--60},
keywords={mesh generation},
}
@incollection{Garlick90,
author={Garlick, B. and Baum, D. and Winget, J.},
year={1990},
title={Interactive viewing of large geometric data bases using
multiprocessor graphics workstations},
pages={239--245},
booktitle={Parallel Algorithms and Architectures for {3D} Image Generation},
publisher={ACM SIGGRAPH},
note={Siggraph '90 Course Notes, Vol. 28},
}
@INPROCEEDINGS{Rushmeier93,
AUTHOR={Holly E. Rushmeier and Charles Patterson and Aravindan Veerasamy},
TITLE={Geometric Simplification for Indirect Illumination Calculations},
BOOKTITLE={Proc. Graphics Interface '93},
PUBLISHER={Canadian Inf. Proc. Soc.},
ADDRESS={Toronto, Ontario},
MONTH={May},
YEAR={1993},
PAGES={227--236},
keywords={Monte Carlo, progressive refinement, ray tracing, multiresolution modeling},
ANNOTE={multiresolution model creation (clustering), not fully automated},
}
@ARTICLE{Gortler93wave,
AUTHOR={Steven J. Gortler and Peter Schr\"oder and Michael F. Cohen
and Pat Hanrahan},
TITLE={Wavelet Radiosity},
JOURNAL={Computer Graphics
(SIGGRAPH '93 Proc.)},
MONTH={August},
YEAR={1993},
}
@ARTICLE{Heckbert86,
AUTHOR={Paul S. Heckbert},
TITLE={Survey of Texture Mapping},
JOURNAL={IEEE Computer Graphics and Appl.},
VOLUME={6},
NUMBER={11},
MONTH={Nov.},
YEAR={1986},
PAGES={56--67},
}
@INPROCEEDINGS{Sakas91,
AUTHOR={Georgios Sakas and Matthias Gerth},
TITLE={Sampling and Anti-Aliasing of Discrete {3-D} Volume Density Textures},
BOOKTITLE={Eurographics '91},
PUBLISHER={North-Holland},
ADDRESS={Amsterdam},
YEAR={1991},
PAGES={87--102, 527},
}
@INPROCEEDINGS{Becker93,
AUTHOR={Barry G. Becker and Nelson L. Max},
TITLE={Smooth Transitions between Bump Rendering Algorithms},
BOOKTITLE={SIGGRAPH '93 Proc.},
PUBLISHER={ACM},
YEAR={1993},
PAGES={183--189},
keywords={BRDF, bump mapping, displacement mapping, multiresolution model},
}
@INPROCEEDINGS{Greene93,
AUTHOR={Ned Greene and Michael Kass and Gavin Miller},
TITLE={Hierarchical Z-Buffer Visibility},
BOOKTITLE={SIGGRAPH '93 Proc.},
PUBLISHER={ACM},
YEAR={1993},
PAGES={231--238},
keywords={z-buffer pyramid},
}
@INPROCEEDINGS{Chen93view,
AUTHOR={Shenchang Eric Chen and Lance Williams},
TITLE={View Interpolation for Image Synthesis},
BOOKTITLE={SIGGRAPH '93 Proc.},
PUBLISHER={ACM},
YEAR={1993},
PAGES={279--288},
keywords={image matching, stereo, multiresolution model, image flow},
}
% without accents: Tomas Werner and Roger David Hersch and Vaclav Hlavac
@INPROCEEDINGS{Werner95,
AUTHOR={Tom\'a\v{s} Werner and Roger David Hersch and V\'aclav Hlav\'a\v{c}},
TITLE={Rendering Real-World Objects Using View Interpolation},
BOOKTITLE={Proc. Fifth Intl. Conf.. on Computer Vision (ICCV '95)},
MONTH={June},
YEAR={1995},
PAGES={957--962},
KEYWORDS={computer vision, image synthesis},
}
@TECHREPORT{Poggio92graphics,
AUTHOR={Tomaso Poggio and Roberto Brunelli},
TITLE={A Novel Approach to Graphics},
INSTITUTION={MIT AI Lab},
NOTE={AI memo 1354,
\URL{ftp://publications.ai.mit.edu/ai-publications/1000-1499/AIM-1354.tiff.tar.gz}},
MONTH={Feb.},
YEAR={1992},
ABSTRACT={
We show that we can optimally represent the set of 2D images produced
by the point features of a rigid 3D model as two lines in two
high-dimensional spaces. We then decribe a working recognition system
in which we represent these spaces discretely in a hash table. We can
access this table at run time to find all the groups of model features
that could match a group of image features, accounting for the effects
of sensing error. We also use this representation of a model's images
to demonstrate significant new limitations of two other approaches to
recognition: invariants, and non-accidental properties.
},
KEYWORDS={computer graphics, image synthesis, in-betweening,
memory-based graphics, teleconferencing},
}
@TECHREPORT{Garland95tr,
AUTHOR={Michael Garland and Paul S. Heckbert},
TITLE={Fast Polygonal Approximation of Terrains and Height Fields},
INSTITUTION={CS Dept., Carnegie Mellon U.},
MONTH={Sept.},
YEAR={1995},
NOTE={CMU-CS-95-181, \URL{http://www.cs.cmu.edu/~garland/scape}},
ANNOTE={
also \URL{ftp://reports.adm.cs.cmu.edu/usr/anon/1995/CMU-CS-95-181.ps.GZ,
CMU-CS-95-181A.ps.GZ}},
keywords={surface simplification, Delaunay triangulation,
data-dependent triangulation, triangulated irregular network, TIN,
multiresolution modeling, greedy insertion},
}
@INPROCEEDINGS{Garland96sketch,
AUTHOR={Michael Garland and Paul S. Heckbert},
TITLE={Fast and Flexible Polygonization of Height Fields},
BOOKTITLE={Visual Proceedings, SIGGRAPH 96},
MONTH={Aug.},
YEAR={1996},
PAGES={143},
KEYWORDS={greedy insertion},
ANNOTE={short version of Garland95tr},
}
@ARTICLE{Garland9x,
AUTHOR={Michael Garland and Paul S. Heckbert},
TITLE={Fast Polygonal Approximation of Terrains and Height Fields},
NOTE={submitted for publication},
keywords={surface simplification, Delaunay triangulation,
data-dependent triangulation, triangulated irregular network, TIN,
multiresolution modeling, greedy insertion},
ANNOTE={revised version of Garland95tr},
}
@INPROCEEDINGS{Heckbert94multi,
AUTHOR={Paul S. Heckbert and Michael Garland},
TITLE={Multiresolution Modeling for Fast Rendering},
BOOKTITLE={Proc. Graphics Interface '94},
PUBLISHER={Canadian Inf. Proc. Soc.},
ADDRESS={Banff, Canada},
MONTH={May},
YEAR={1994},
PAGES={43--50},
keywords={level of detail, simplification, approximation},
NOTE={\URL{http://www.cs.cmu.edu/~ph}},
}
@TECHREPORT{Heckbert9xsurvey,
AUTHOR={Paul S. Heckbert and Michael Garland},
TITLE={Survey of Polygonal Surface Simplification Algorithms},
INSTITUTION={CS Dept., Carnegie Mellon U.},
YEAR={to appear},
NOTE={\URL{http://www.cs.cmu.edu/~ph}},
keywords={manifold, non-manifold, triangulation, decimation, refinement,
multiresolution modeling},
}
@INPROCEEDINGS{Taylor94polyg,
AUTHOR={David C. Taylor and William A. Barrett},
TITLE={An Algorithm for Continuous Resolution Polygonalizations of a
Discrete Surface},
BOOKTITLE={Proc. Graphics Interface '94},
PUBLISHER={Canadian Inf. Proc. Soc.},
ADDRESS={Banff, Canada},
MONTH={May},
YEAR={1994},
PAGES={33--42},
keywords={terrain, level of detail, simplification, approximation,
quadtree, multiresolution},
}
@TechReport{Puppo91,
author = "Enrico Puppo and Larry Davis and Daniel DeMenthon and
Y. Ansel Teng",
title = "Parallel Terrain Triangulation Using the {Connection}
{Machine}",
institution = "Center for Automation Research, University of Maryland",
year = 1991,
number = "CAR-TR-561, CS-TR-2693",
address = "College Park, Maryland",
month = "June",
keywords={simplification, approximation, Delaunay triangulation},
}
@INPROCEEDINGS{Puppo92,
AUTHOR={Enrico Puppo and Larry Davis and Daniel DeMenthon and Y. Ansel Teng},
TITLE={Parallel Terrain Triangulation},
BOOKTITLE={Proc. 5th Intl. Symp. on Spatial Data Handling},
MONTH={Aug.},
YEAR={1992},
PAGES={632--641},
keywords={simplification, approximation, Delaunay triangulation,
Connection Machine},
}
@ARTICLE{Puppo94,
AUTHOR={Enrico Puppo and Larry Davis and Daniel DeMenthon and Y. Ansel Teng},
TITLE={Parallel Terrain Triangulation},
JOURNAL={Intl. J. of Geographical Information Systems},
VOLUME={8},
NUMBER={2},
YEAR={1994},
PAGES={105--128},
keywords={simplification, approximation, Delaunay triangulation,
Connection Machine},
}
@INPROCEEDINGS{Puppo95range,
AUTHOR={Enrico Puppo},
YEAR={1995},
TITLE={Segmentation/reconstruction of range images based on piecewise-linear
approximation},
BOOKTITLE={Image Analysis and Processing},
EDITORS={C. Braccini and others},
PUBLISHER={Springer-Verlag},
SERIES={Lecture Notes in Computer Science N.974},
PAGES={367--372},
NOTE={Proceedings 8th Intl. Conf. on Image Analysis and Processing,
Sanremo, Sept. 1995,
\URL{ftp://ftp.disi.unige.it/pub/puppo/PS/iciap95.ps.Z}},
}
@INPROCEEDINGS{Cignoni94volume,
AUTHOR={P. Cignoni and L. De Floriani and C. Montani and E. Puppo
and R. Scopigno},
TITLE={Multiresoultion modeling and visualization of volume data based on
simplicial complexes},
BOOKTITLE={Proceedings 1994 ACM Symposium on Volume Visualization},
MONTH={Oct.},
YEAR={1994},
PAGES={19--26},
NOTE={\URL{ftp://ftp.disi.unige.it/pub/puppo/PS/ACM-VV94.ps.gz}},
}
@INPROCEEDINGS{Cignoni95terrain,
AUTHOR={P. Cignoni and E. Puppo and R. Scopigno},
TITLE={Representation and Visualization of Terrain Surfaces at
Variable Resolution},
BOOKTITLE={Scientific Visualization 95},
PUBLISHER={World Scientific},
YEAR={1995},
PAGES={50--68},
NOTE={\URL{ftp://ftp.disi.unige.it/pub/puppo/PS/issv95.ps.Z}},
ANNOTE={Also available from Pisa:
\URL{http://miles.cnuce.cnr.it/cg/multiresTerrain.html#paper25}},
}
@Article{Dutton77,
author = "Geoffrey Dutton",
title = "An Extensible Approach to Imagery of Gridded Data",
journal = "Computer Graphics",
volume = "11",
number = "2",
month = "July",
year = "1977",
note = "Proc. SIGGRAPH '77",
pages = "159--169",
}
@article{Gold77,
author = "C. M. Gold and T. D. Charters and J. Ramsden",
title = "Automated Contour Mapping using Triangular Element Data
Structures and an Interpolant over each Irregular Triangular Domain.",
journal = "Computer Graphics",
volume = "11",
number = "2",
month = "July",
year = "1977",
note = "Proc. SIGGRAPH '77",
pages = "170--175",
}
@INPROCEEDINGS{Schmitt85,
AUTHOR={Francis Schmitt and Behrouz Gholizadeh},
TITLE={Adaptative Polyhedral Approximation of Digitized Surfaces},
BOOKTITLE={Computer Vision for Robots},
VOLUME={595},
PUBLISHER={SPIE},
YEAR={1985},
PAGES={101--108},
KEYWORDS={surface simplification},
ANNOTE={adaptive refinement of triangulation to fit rectangular mesh in 3-D},
}
@ARTICLE{Schmitt86,
author = "Francis J. M. Schmitt and Brian A. Barsky and Wen-Hui Du",
title = "An Adaptive Subdivision Method for Surface-Fitting from
Sampled Data",
pages = "179--188",
journal = "Computer Graphics (SIGGRAPH '86 Proc.)",
volume = "20",
number = "4",
year = "1986",
month = "Aug.",
keywords = "surface simplification, Bezier patch, continuity, range data,
computer vision",
}
@INPROCEEDINGS{Schmitt91euro,
AUTHOR={Francis Schmitt and Xin Chen},
TITLE={Geometric Modeling from Range Image Data},
BOOKTITLE={Eurographics '91},
PUBLISHER={North-Holland},
ADDRESS={Amsterdam},
YEAR={1991},
PAGES={317--328},
KEYWORDS={gregory patch, surface fitting, computer vision},
}
@InProceedings{Schmitt91cvpr,
author="Francis Schmitt and Xin Chen",
title="Fast Segmentation of Range Images into Planar Regions",
booktitle={Conf. on Computer Vision and Pattern Recognition (CVPR '91)},
month=jun,
year="1991",
publisher="IEEE Comp. Soc. Press",
pages={710--711},
keywords={greedy insertion, surface simplification},
}
@INCOLLECTION{Schmitt91patch,
AUTHOR={Francis Schmitt and Xin Chen and W.-H. Du and F. Sair},
TITLE={Adaptive $G^1$ Approximation of Range Data Using Triangular Patches},
BOOKTITLE={Curves and Surfaces},
EDITOR={P.-J. Laurent and others},
PUBLISHER={Academic Press},
ADDRESS={San Diego},
YEAR={1991},
PAGES={433--436},
KEYWORDS={surface simplification, parametric surface, computer vision},
}
@INCOLLECTION{Chen93range,
AUTHOR={Xin Chen and Francis Schmitt},
TITLE={Adaptive Range Data Approximation by Constrained Surface Triangulation},
BOOKTITLE={Modeling in Computer Graphics: Methods and Applications},
EDITOR={B. Falcidieno and T. Kunii},
PUBLISHER={Springer-Verlag},
ADDRESS={Berlin},
YEAR={1993},
PAGES={95--113},
keywords={surface simplification, computer vision},
}
@InCollection{DeFloriani83,
author = "Leila {De Floriani} and Bianca Falcidieno and Caterina Pienovi",
title = "A {Delaunay}-Based Method for Surface Approximation",
year = "1983",
booktitle = "Eurographics '83",
PUBLISHER={Elsevier Science},
pages = "333--350",
}
@Article{DeFloriani84,
author = "Leila {De Floriani} and Bianca Falcidieno and George Nagy
and Caterina Pienovi" ,
title = "A Hierarchical Structure for Surface Approximation",
pages = "183--193",
journal = "Computers and Graphics",
volume = "8",
number = "2",
year = "1984",
keywords = "hierarchical data structure",
annote = "poor method; too many slivers, too many long edges",
}
@Article{DeFloriani85,
author = "Leila {De Floriani} and Bianca Falcidieno and
Caterina Pienovi",
title = "{Delaunay}-based Representation of Surfaces Defined
over Arbitrarily Shaped Domains",
journal = "Computer Vision, Graphics, and Image Processing",
year = 1985,
volume = 32,
pages = "127--140"
}
@ARTICLE{DeFloriani85select,
AUTHOR={Leila {De Floriani} and Bianca Falcidieno and Caterina Pienovi
and George Nagy},
TITLE={Efficient Selection, Storage, and Retrieval of Irregularly
Distributed Elevation Data},
JOURNAL={Computers and Geosciences},
VOLUME={11},
NUMBER={16},
YEAR={1985},
PAGES={667--673},
keywords={greedy insertion, surface simplification},
}
@inproceedings{DeFloriani86vis
, author = "Leila {De Floriani} and Bianca Falcidieno and Caterina Pienovi
and David Allen and George Nagy"
, title = "A Visibility-Based Model for Terrain Features"
, booktitle = "Proceedings: Second International Symposium on Spatial Data
Handling"
, year = "1986"
, month = "5--10 July"
, pages = "235--250"
, note = "Seattle, Washington"
}
@Article{DeFloriani87,
author = "Leila {De Floriani}",
title = "Surface representations based on triangular grids",
journal = "The Visual Computer",
pages = "27--50",
volume = "3",
number = "1",
month = "Feb.",
year = "1987",
keywords = "triangulation, tree, data structures",
}
@Article{DeFloriani89,
author = "Leila {De Floriani}",
title = "A Pyramidal Data Structure for Triangle-Based Surface Description",
journal = "IEEE Computer Graphics and Appl.",
pages = "67--78",
volume = "9",
number = "2",
month = "March",
year = "1989",
}
@INPROCEEDINGS{DeFloriani92hier,
AUTHOR={Leila {De Floriani} and Enrico Puppo},
TITLE={A hierarchical triangle-based model for terrain description},
BOOKTITLE={Theories and Methods of Spatio-Temporal Reasoning in
Geographic Space},
EDITOR={A. U. Frank and others},
PUBLISHER={Springer-Verlag},
ADDRESS={Berlin},
YEAR={1992},
PAGES={236--251},
ABSTRACT={
A new hierarchical model for representing a terrain is
presented. The model, called a hierarchical triangulated
irregular network (HTIN), is a method for compression of
spatial data and representation of a topographic surface at
successively finer levels of detail. A HTIN is a hierarchy of
triangle-based surface approximations, where each node, except
for the root, is a triangulated irregular network refining a
triangle face belonging to its parent in the hierarchy. The
authors present an encoding structure for a HTIN and describe
an algorithm for its construction.
},
keywords={triangulated irregular network, surface simplification},
ANNOTE={International Conference GIS - From Space to
Territory. Proceedings; Pisa, Italy; 21-23 Sept. 1992;},
}
@Article{DeFloriani92image,
author = "Leila {De Floriani} and P. Jeanne and George Nagy",
title = "Visibility related image features",
journal = "Pattern Recognition Letters",
year = 1992,
volume = 40,
pages = "137--139",
month = "6 Nov"
}
@Article{DeFloriani93image,
author = "Leila {De Floriani} and Philippe Jeanne and George Nagy",
title = "Visibility-Related Image Features",
journal = "Pattern Recognition Letters",
year = 1993,
volume = 13,
pages = "463--470",
month = "June",
}
@InProceedings{DeFloriani93sight,
author = "Leila {De Floriani} and George Nagy and Enrico Puppo",
title = "Computing a line-of-sight network on a terrain model",
pages = "672--681",
booktitle = "Proc. Fifth Int. Symp. Spatial Data Handling",
year = 1993,
address = "Charleston, SC, USA",
month = aug
}
@Article{DeFloriani94sight,
author = "Leila {De Floriani} and Paola Magillo and Enrico Puppo",
title = "Line of Sight Communication on Terrain Models",
journal = {Intl. J. Geographic Information Systems},
year = 1994,
volume = 8,
number = 4,
pages = "329--342"
}
@ARTICLE{DeFloriani9xhier,
AUTHOR={Leila De Floriani and Enrico Puppo},
TITLE={Hierarchical Triangulation for Multiresolution Surface Description},
JOURNAL={ACM Transactions on Graphics},
YEAR={to appear},
NOTE={\URL{ftp://ftp.disi.unige.it/pub/puppo/PS/tog95.ps.Z}},
}
@ARTICLE{DeFloriani9xmultitopo,
AUTHOR={Leila De Floriani and Paola Marzano and Enrico Puppo},
TITLE={Multiresolution Models for Topographic Surface Description},
JOURNAL={The Visual Computer},
YEAR={to appear},
NOTE={\URL{ftp://ftp.disi.unige.it/pub/marzano/POSTSCRIPT/VISUAL-C96.ps}},
}
Article{n-tv-94,
author = "George Nagy",
title = "Terrain Visibility",
journal = "Comput. \& Graphics",
year = 1994,
volume = 18,
number = 6
}
@InProceedings{cdnp91,
author = "M.Cazzanti and Leila {De Floriani} and George Nagy and
Enrico Puppo",
title = "Visibility computation on a triangulated terrain",
pages = "721--728",
booktitle = "Visibility computation on a triangulated terrain",
year = 1991,
address = "Como, Italy",
month = sep
}
@InProceedings{falcidieno-zurich-90,
author = "Bianca Falcidieno and Caterina Pienovi",
title = "A Feature-Based Approach to Terrain Surface Approximation",
crossref="SDDH90",
Pages="190--199",
keywords="TIN",
}
@Article{Bruzzone90,
author = "Elisabetta Bruzzone and Leila {De Floriani}",
title = "Two data structures for building tetrahedralizations",
journal = "The Visual Computer",
pages = "266--283",
volume = "6",
number = "5",
month = "November",
year = "1990",
keywords = "solid modeling, delaunay triangulation",
}
@INPROCEEDINGS{Bertolotto95,
AUTHOR={Michela Bertolotto and Leila {De Floriani} and Paola Marzano},
TITLE={Pyramidal Simplicial Complexes},
BOOKTITLE={Solid Modeling '95, 3rd Symp. on Solid Modeling and Appl.},
MONTH={May},
YEAR={1995},
ADDRESS={Salt Lake City, Utah},
}
@ARTICLE{Peucker75,
AUTHOR={Thomas K. Peucker and David H. Douglas},
TITLE={Detection of Surface-specific Points by Local Parallel Processing of
Discrete Terrain Elevation Data},
JOURNAL={Computer Graphics and Image Processing},
VOLUME={4},
YEAR={1975},
PAGES={375--387},
keywords={digital elevation model, TIN, feature},
}
@INPROCEEDINGS{Peucker78,
AUTHOR={Thomas K. Peucker and Robert J. Fowler and James J. Little and
David M. Mark},
TITLE={The Triangulated Irregular Network},
BOOKTITLE={Proc. of the Digital Terrain Models (DTM) Symposium},
PUBLISHER={American Society of Photogrammetry},
ADDRESS={St. Louis},
MONTH={May},
YEAR={1978},
PAGES={516--540},
keywords={digital elevation model, TIN},
}
@ARTICLE{Lee80triang,
AUTHOR={D.T. Lee and Bruce J. Schachter},
TITLE={Two Algorithms for Constructing a {Delaunay} Triangulation},
JOURNAL={Intl. J. Computer and Information Sciences},
VOLUME={9},
NUMBER={3},
YEAR={1980},
PAGES={219--242},
}
@INPROCEEDINGS{Hinker93,
AUTHOR={Paul Hinker and Charles Hansen},
TITLE={Geometric Optimization},
BOOKTITLE={Proc. Visualization '93},
MONTH={October},
YEAR={1993},
ADDRESS={San Jose, CA},
PAGES={189--195},
KEYWORDS={surface simplification},
NOTE={\URL{http://www.acl.lanl.gov/Viz/vis93_abstract.html}},
}
@ARTICLE{Vemuri94,
AUTHOR={B. C. Vemuri and A. Radisavljevic},
TITLE={Multiresolution Stochastic Hybrid Shape Models with Fractal Priors},
JOURNAL={ACM Trans. on Graphics},
VOLUME={13},
NUMBER={2},
MONTH={Apr.},
YEAR={1994},
PAGES={177--207},
}
@TECHREPORT{Lounsbery93tr,
AUTHOR={Michael Lounsbery and Tony D. DeRose and Joe Warren},
TITLE={Multiresolution Analysis for Surfaces of Arbitrary Topological Type},
keywords={surface, wavelet},
NOTE={
TR 93-10-05b,
\URL{http://www.cs.washington.edu/homes/derose/grail/treasure_bags.html}.
},
INSTITUTION={Dept. of CS \& Eng., U. of Washington},
MONTH={Oct.},
YEAR={1993},
}
@PHDTHESIS{Lounsbery94phd,
AUTHOR={Michael Lounsbery},
TITLE={Multiresolution Analysis for Surfaces of Arbitrary Topological Type},
SCHOOL={Dept. of Computer Science and Engineering, U. of Washington},
YEAR={1994},
keywords={surface, wavelet},
NOTE={\URL{http://www.cs.washington.edu/homes/derose/grail/treasure_bags.html}},
}
@ARTICLE{Lounsbery94,
AUTHOR={Michael Lounsbery and Tony D. DeRose and Joe Warren},
TITLE={Multiresolution Analysis for Surfaces of Arbitrary Topological Type},
keywords={surface, wavelet},
NOTE={
Submitted for publication.
\URL{http://www.cs.washington.edu/homes/derose/grail/treasure_bags.html}},
}
@INPROCEEDINGS{Eck95,
AUTHOR={Matthias Eck and Tony DeRose and Tom Duchamp and
Hugues Hoppe and Michael Lounsbery and Werner Stuetzle},
TITLE={Multiresolution Analysis of Arbitrary Meshes},
BOOKTITLE={SIGGRAPH '95 Proc.},
PUBLISHER={ACM},
MONTH={Aug.},
YEAR={1995},
PAGES={173--182},
NOTE={\URL{http://www.cs.washington.edu/homes/derose/grail/treasure_bags.html}},
keywords={surface, wavelet},
}
@InProceedings{Hoppe92,
author = "Hugues Hoppe and Tony DeRose and Tom Duchamp and John
McDonald and Werner Stuetzle",
title = "Surface reconstruction from unorganized points",
pages = "71--78",
booktitle = "Computer Graphics (SIGGRAPH '92 Proceedings)",
volume = "26",
year = "1992",
month = jul,
keywords = "geometric modeling, surface fitting, 3d shape
recovery, range data analysis",
}
@inproceedings{Hoppe93,
author = "Hugues Hoppe and Tony DeRose and Tom Duchamp and
John McDonald and Werner Stuetzle",
title = "Mesh Optimization",
booktitle = "SIGGRAPH '93 Proc.",
year = "1993",
pages = "19--26",
month = "Aug.",
NOTE={
\URL{http://www.research.microsoft.com/research/graphics/hoppe/papers.html}},
}
@INPROCEEDINGS{Hoppe94subsurf,
AUTHOR={Hugues Hoppe and Tony DeRose and Tom Duchamp and
Mark Halstead and Hubert Jin and John McDonald and Jean Schweitzer
and Werner Stuetzle},
TITLE={Piecewise Smooth Surface Reconstruction},
BOOKTITLE={SIGGRAPH '94 Proc.},
YEAR={1994},
MONTH={July},
PAGES={295--302},
KEYWORDS={subdivision surface, curved surface fitting},
NOTE={
\URL{http://www.research.microsoft.com/research/graphics/hoppe/papers.html}},
}
@PHDTHESIS{Hoppe94phd,
AUTHOR={Hugues Hoppe},
TITLE={Surface Reconstruction from Unorganized Points},
SCHOOL={Dept. of Computer Science and Engineering, U. of Washington},
YEAR={1994},
keywords={optimization, subdivision surface},
NOTE={\URL{http://www.cs.washington.edu/homes/derose/grail/treasure_bags.html}},
}
@INPROCEEDINGS{Hoppe96pm,
AUTHOR={Hugues Hoppe},
TITLE={Progressive Meshes},
BOOKTITLE={SIGGRAPH '96 Proc.},
MONTH={Aug.},
YEAR={1996},
PAGES={99--108},
KEYWORDS={surface simplification, multiresolution model, edge collapse},
NOTE={\URL{http://www.research.microsoft.com/research/graphics/hoppe/papers.html}},
}
@Article{Falby93,
author = "John S. Falby and Michael J. Zyda and David R. Pratt
and Randy L. Mackey",
title = "{NPSNET}: Hierarchical Data Structures for Real-Time
Three-Dimensional Visual Simulation",
journal = "Computers \& Graphics",
year = "1993",
volume = "17",
number = "1",
pages = "65--70",
}
@INPROCEEDINGS{deBerg95,
AUTHOR={Mark de Berg and Katrin Dobrindt},
TITLE={On Levels of Detail in Terrains},
BOOKTITLE={Proc. 11th Annual ACM Symp. on Computational Geometry},
MONTH={June},
YEAR={1995},
ADDRESS={Vancouver, B.C.},
KEYWORDS={multiresolution, Delaunay triangulation},
NOTE={Also available as Utrecht University tech report
UU-CS-1995-12,
\URL{ftp://ftp.cs.ruu.nl/pub/RUU/CS/techreps/CS-1995/}},
}
@techreport{l-gtgac-72
, author = "C. L. Lawson"
, title = "Generation of a triangular grid with applications to contour plotting"
, type = "Memo"
, number = 299
, institution = "Jet Propulsion Lab., California Inst. Tech."
, address = "Pasadena, CA"
, year = 1972
}
@article{l-tt-72
, author = "C. L. Lawson"
, title = "Transforming Triangulations"
, journal = "Discrete Math."
, volume = 3
, year = 1972
, pages = "365--372"
, annote = "Proves that any triangulation of a given set of points
can be transformed into any other by a sequence of
``exchanges''. (If two adjacent triangles form a convex
quadrilateral, replace the included diagonal with the
other one.)"
}
@INPROCEEDINGS{Lawson77,
AUTHOR={Charles L. Lawson},
TITLE={Software for {$C^1$} Surface Interpolation},
BOOKTITLE={Mathematical Software III},
EDITOR={John R. Rice},
PUBLISHER={Academic Press, NY},
YEAR={1977},
NOTE={(Proc. of symp., Madison, WI, Mar. 1977)},
PAGES={161--194},
keywords={scattered data interpolation, Delaunay triangulation,
local optimization procedure},
}
@ARTICLE{Lawson86,
AUTHOR={Charles L. Lawson},
TITLE={Properties of n-dimensional triangulations},
JOURNAL={Computer-Aided Geometric Design},
VOLUME=3,
MONTH={Apr.},
YEAR=1986,
PAGES={231--246},
KEYWORDS={tetrahedron, Delaunay},
}
@TECHREPORT{Lindstrom95,
AUTHOR={Peter Lindstrom and David Koller and Larry F. Hodges and
William Ribarsky and Nick Faust and Gregory Turner},
TITLE={Level-of-detail Management for Real-Time Rendering of Phototextured
Terrain},
INSTITUTION={Graphics, Visualization, and Usability Center, Georgia Tech},
MONTH={},
YEAR={1995},
keywords={texture mapping, geographic information systems},
NOTE={TR 95-06,
\URL{http://www.cc.gatech.edu/gvu/reports/TechReports95.html}},
ABSTRACT={
We present four techniques for real-time level-of-detail reduction of digital
terrain data without loss of visual image quality or detail. Techniques for
reducing polygon count based on distance and terrain roughness provided two-
orders-of-magnitude reduction in the number of polygons rendered for our
sample data: an eight kilometer by eight kilometer data set with four meter
resolution. Techniques for reducing texture data based on distance and
orientation of polygons resulted in a one-order-of-magnitude reduction in the
number of bytes of texture memory for the same data set.
},
}
@InProceedings{Lindstrom96,
author = "Peter Lindstrom and David Koller and William
Ribarsky and Larry F. Hodges and Nick Faust and
Gregory A. Turner",
title = "Real-Time, Continuous Level of Detail Rendering of
Height Fields",
pages = "109--118",
booktitle = "SIGGRAPH '96",
year = 1996,
month = "Aug."
}
@INPROCEEDINGS{Vezina91,
AUTHOR={Guy Vezina and Philip K. Robertson},
TITLE={Terrain Perspectives on a Massively Parallel SIMD Computer},
BOOKTITLE={Scientific Visualization of Physical Phenomena},
EDITOR={N. M. Patrikalakis},
PUBLISHER={Springer-Verlag},
ADDRESS={Tokyo},
YEAR={1991},
PAGES={163--188},
keywords={terrain rendering, texture mapping},
ANNOTE={Proc. of CGI 91, Cambridge, MA, 1991.},
}
@Article{VaughanWhyattBrookes91,
key = "Vaughan et al.",
author = "J. Vaughan and D. Whyatt and G. Brookes",
title = "A Parallel Implementation of the {Douglas}-{Peucker} Line
Simplification Algorithm",
journal = "Software - Practice And Experience",
pages = "331--336",
volume = "21",
number = "3",
month = mar,
year = "1991",
}
@Article{Ramer72,
author = "Urs Ramer",
title = "An iterative procedure for the polygonal approximation
of plane curves",
journal = "Computer Graphics and Image Processing",
volume = "1",
pages = "244--256",
year = "1972",
keywords = "curve fit, curve simplification,
Douglas-Peucker algorithm",
annote = "identical to Douglas-Peucker algorithm",
}
@ARTICLE{Douglas73,
AUTHOR={David H. Douglas and Thomas K. Peucker},
TITLE={Algorithms for the Reduction of the Number of Points Required
to Represent a Digitized Line or Its Caricature},
JOURNAL={The Canadian Cartographer},
VOLUME={10},
NUMBER={2},
MONTH={Dec.},
YEAR={1973},
PAGES={112--122},
keywords={curve simplification},
ANNOTE={see also Ramer72},
}
@TECHREPORT{Catmull78filter,
AUTHOR={Edwin E. Catmull},
TITLE={Geometric Filtering},
INSTITUTION={New York Inst. of Tech. Computer Graphics Lab},
NOTE={TM 2},
MONTH={Mar.},
YEAR={1978},
keywords={curve approximation},
}
@TECHREPORT{Catmull78thin,
AUTHOR={Edwin E. Catmull},
TITLE={Line Thinning},
INSTITUTION={New York Inst. of Tech. Computer Graphics Lab},
NOTE={TM 4},
MONTH={Mar.},
YEAR={1978},
keywords={curve approximation, Douglas-Peucker algorithm},
}
@INPROCEEDINGS{Hershberger92symp,
AUTHOR={John Hershberger and Jack Snoeyink},
TITLE={Speeding Up the {Douglas}-{Peucker} Line-Simplification Algorithm},
BOOKTITLE={Proc. 5th Intl. Symp. on Spatial Data Handling},
VOLUME={1},
EDITOR={P. Bresnahan and others},
ADDRESS={Charleston, SC},
MONTH={Aug.},
YEAR={1992},
PAGES={134--143},
keywords={simplification, approximation, curve, computational geometry,
convex hull},
NOTE={Also available as TR-92-07,
CS Dept, U. of British Columbia,
\URL{http://www.cs.ubc.ca/tr/1992/TR-92-07},
code at \URL{http://www.cs.ubc.ca/spider/snoeyink/papers/papers.html}},
ABSTRACT={
The authors analyze the line simplification algorithm reported
by Douglas and PEUCKER (1973) and show that its worst case is
quadratic in n, the number of input points. Then they give an
algorithm, based on path hulls, that uses the geometric
structure of the problem to attain a worst-case running time
proportional to n log/sub 2/ n, which is the best case of the
Douglas algorithm. They give complete C code and compare the
two algorithms theoretically, by operation counts, and
practically, by machine timings.
},
}
@TECHREPORT{Hershberger92tr,
AUTHOR={John Hershberger and Jack Snoeyink},
TITLE={Speeding Up the {Douglas}-{Peucker} Line-Simplification Algorithm},
INSTITUTION={CS Dept, U. of British Columbia},
MONTH={April},
YEAR={1992},
keywords={simplification, approximation, curve, computational geometry,
convex hull},
NOTE={TR-92-07,
\URL{http://www.cs.ubc.ca/tr/1992/TR-92-07},
code at \URL{http://www.cs.ubc.ca/spider/snoeyink/papers/papers.html}},
ABSTRACT={
We analyze the line simplification algorithm reported by Douglas
and Peucker and show that its worst case is quadratic in n, the
number of input points. Then we give a algorithm, based on path
hulls, that uses the geometric structure of the problem to attain
a worst-case running time proportional to n log_2(n), which is the
best case of the Douglas algorithm. We give complete C code and
compare the two algorithms theoretically, by operation counts, and
practically, by machine timings.
},
}
@Article{McMaster87algs,
author = "Robert B. McMaster",
title = "Automated Line Generalization",
journal = "Cartographica",
volume = "24",
number = "2",
year = "1987",
pages = "74--111",
keywords = "curve simplification, cartography",
}
@ARTICLE{McMaster87compare,
AUTHOR={Robert B. McMaster},
TITLE={The Geometric Properties of Numerical Generalization},
JOURNAL={Geographical Analysis},
VOLUME={19},
NUMBER={4},
MONTH={Oct.},
YEAR={1987},
PAGES={330--346},
keywords={curve simplification, cartography, Douglas-Peucker algorithm},
ANNOTE={9 curve simplification algorithms are compared using several
error metrics. He concludes that Douglas-Peucker yields highest quality,
but it is slow},
}
@ARTICLE{McMaster89book,
KEY={McMaster89book},
EDITOR={Robert B. McMaster},
TITLE={Numerical Generalization in Cartography},
NOTE={Monograph 40},
JOURNAL={Cartographica},
VOLUME={26},
NUMBER={1},
MONTH={Spring},
YEAR={1989},
PUBLISHER={U. of Toronto Press},
}
@BOOK{McMaster92,
AUTHOR={Robert B. McMaster and K. S. Shea},
TITLE={Generalization in Digital Cartography},
PUBLISHER={Assoc. of American Geographers},
ADDRESS={Washington, D.C.},
YEAR={1992},
ANNOTE={abstract at \URL{http://www.gisworld.com/book/Cart_Map.html},
chapter on line generalization},
}
@ARTICLE{Kumler94,
TITLE={An Intensive Comparison of Triangulated Irregular Networks ({TINs})
and Digital Elevation Models ({DEMs})},
AUTHOR={Mark P. Kumler},
NOTE={Monograph 45},
JOURNAL={Cartographica},
VOLUME={31},
NUMBER={2},
MONTH={Summer},
YEAR={1994},
PUBLISHER={U. of Toronto Press},
}
@PHDTHESIS{Kumler92,
TITLE={An intensive comparison of TINs and DEMs},
AUTHOR={Mark P. Kumler},
SCHOOL={Dept. of Geography, U. of California, Santa Barbara},
ANNOTE={181 pages},
YEAR={1992},
}
@INCOLLECTION{Imai88,
AUTHOR={Hiroshi Imai and Masao Iri},
TITLE={Polygonal Approximations of a Curve -- Formulations and Algorithms},
BOOKTITLE={Computational Morphology},
EDITOR={G. T. Toussaint},
PUBLISHER={Elsevier Science},
YEAR={1988},
PAGES={71--86},
keywords={curve simplification, computational geometry},
ANNOTE={nice survey of optimal-quality algorithms for curve simplification},
}
@INPROCEEDINGS{Heller90,
AUTHOR={Martin Heller},
TITLE={Triangulation Algorithms for Adaptive Terrain Modeling},
BOOKTITLE={Proc. 4th Intl. Symp. on Spatial Data Handling},
VOLUME={1},
ADDRESS={Z\"urich},
YEAR={1990},
PAGES={163--174},
keywords={surface simplification, hierarchical triangulation},
ABSTRACT={
Reports on the development of methods to incrementally build
and refine terrain models. To achieve this goal, algorithms
have been created to generate, edit, and visualize TRIANGULAR
meshes. Emphasis was put on practical implementation that
provides feedback for continuous algorithmic exploration and
facilitates the verification of theoretical concepts. Methods
for some basic problems such as efficient searching within a
triangular mesh as well as insertion and subtraction of mesh
points have been studied. They form the basis for novel
algorithms that filter an elevation field to a required
resolution. Adaptive triangular mesh filtering, as this
process is called, is the higher dimensional equivalent of the
well-known method of line simplification. Finally, schemes for
external storage based on self-adjusting amorphous cells and
hierarchical triangular meshes are proposed.
},
}
@TECHREPORT{Heller93,
AUTHOR={Martin Heller},
TITLE={A Synthesis of Triangulation Algorithms},
INSTITUTION={Dept. of Geography, U. of Zurich},
MONTH={Aug.},
YEAR=1993,
ANNOTE={22 pages}
}
@INPROCEEDINGS{Southard91,
AUTHOR={David A. Southard},
TITLE={Piecewise Planar Surface Models from Sampled Data},
BOOKTITLE={Scientific Visualization of Physical Phenomena},
EDITOR={N. M. Patrikalakis},
PUBLISHER={Springer-Verlag},
ADDRESS={Tokyo},
YEAR={1991},
PAGES={667--680},
keywords={surface simplification, terrain},
ANNOTE={Proc. of CGI '91, Cambridge, MA, 1991,
finds features using Laplacian & rank filter, Delaunay triangulation,
data-dependent retriangulation. nice error analysis},
}
@ARTICLE{Fowler79,
AUTHOR={Robert J. Fowler and James J. Little},
TITLE={Automatic Extraction of Irregular Network Digital Terrain Models},
JOURNAL={Computer Graphics (SIGGRAPH '79 Proc.)},
VOLUME={13},
NUMBER={2},
MONTH={Aug.},
YEAR={1979},
PAGES={199--207},
keywords={surface simplification},
}
@INPROCEEDINGS{Chen87,
AUTHOR={Zi-Tan Chen and J. Armando Guevara},
TITLE={Systematic Selection of Very Important Points ({VIP})
from Digital Terrain Model for Constructing Triangular Irregular Networks},
BOOKTITLE={Proc. of Auto-Carto 8
(Eighth Intl. Symp. on Computer-Assisted Cartography)},
EDITOR={N. Chrisman},
ADDRESS={Baltimore, MD},
PUBLISHER={American Congress of Surveying and Mapping},
YEAR={1987},
PAGES={50--56},
keywords={surface simplification},
ANNOTE={one-pass, feature-based method},
}
@ARTICLE{White85,
AUTHOR={Ellen R. White},
TITLE={Assessment of Line-Generalization Algorithms Using Characteristic
Points},
JOURNAL={The American Cartographer},
VOLUME={12},
NUMBER={1},
YEAR={1985},
PAGES={17--27},
keywords={Douglas-Peucker algorithm, curve simplification, cartography},
ANNOTE={perceptual tests of three curve simplification algorithms,
concludes that Douglas-Peucker is best},
}
@BOOK{Duda73,
AUTHOR={Richard O. Duda and Peter E. Hart},
TITLE={Pattern Classification and Scene Analysis},
PUBLISHER={Wiley},
ADDRESS={New York},
YEAR={1973},
keywords={pattern recognition, computer vision},
ANNOTE={
discusses, among many other things, polygonal curve approximation,
describing algorithm similar to Douglas-Peucker, on p. 338.
Discusses least squares fitting.
}
}
@PHDTHESIS{Baumgart74,
AUTHOR={Bruce G. Baumgart},
TITLE={Geometric Modeling for Computer Vision},
NOTE={AIM-249, STAN-CS-74-463},
SCHOOL={CS Dept, Stanford U.},
MONTH={Oct.},
YEAR={1974},
keywords={polyhedron, winged-edge},
ANNOTE={excellent; way ahead of his time},
}
@BOOK{Hamming83,
AUTHOR={Richard W. Hamming},
TITLE={Digital Filters},
PUBLISHER={Prentice-Hall},
ADDRESS={Englewood Cliffs, NJ},
YEAR={1983},
keywords={signal processing, filter},
}
@ARTICLE{Burt81,
AUTHOR={Peter J. Burt},
TITLE={Fast Filter Transforms for Image Processing},
JOURNAL={Computer Graphics and Image Processing},
VOLUME={16},
PAGES={20--51},
YEAR={1981},
KEYWORDS={gaussian filter, image pyramid},
}
@ARTICLE{Green78,
AUTHOR={P. J. Green and R. Sibson},
TITLE={Computing {Dirichlet} Tessellations in the Plane},
JOURNAL={The Computer Journal},
VOLUME={21},
NUMBER={2},
PAGES={168--173},
YEAR={1978},
KEYWORDS={point location, Voronoi diagram, Delaunay triangulation},
}
@ARTICLE{Sibson78,
AUTHOR={R. Sibson},
TITLE={Locally Equiangular Triangulation},
JOURNAL={The Computer Journal},
VOLUME={21},
PAGES={243--245},
YEAR={1978},
KEYWORDS={Delaunay triangulation, optimality},
}
@Book{Cormen90,
author = "Thomas H. Cormen and Charles E. Leiserson and Ronald
L. Rivest",
title = "Introduction to Algorithms",
year = "1990",
address = "Cambridge, MA",
publisher = "MIT Press",
}
@TECHREPORT{Bern92,
AUTHOR={Marshall Bern and David Eppstein},
TITLE={Mesh Generation and Optimal Triangulation},
INSTITUTION={Xerox PARC},
NOTE={CSL-92-1.
Also appeared in ``Computing in Euclidean Geometry'',
F. K. Hwang and D.-Z. Du, eds., World Scientific, 1992},
MONTH={March},
YEAR={1992},
keywords={computational geometry, finite element},
}
@article{Bern93edge
, author = "M. Bern and H. Edelsbrunner and D. Eppstein and S. Mitchell and T. S. Tan"
, title = "Edge insertion for optimal triangulations"
, journal = "Discrete Comput. Geom."
, volume = 10
, number = 1
, year = 1993
, pages = "47--65"
, keywords = "points, triangulation"
, succeeds = "beemt-eiot-92t, beemt-eiot-92i"
, update = "95.05 korneenko"
}
@ARTICLE{Dyn90,
AUTHOR={Nira Dyn and David Levin and Shmuel Rippa},
TITLE={Data Dependent Triangulations for Piecewise Linear Interpolation},
JOURNAL={IMA J. Numer. Anal.},
VOLUME={10},
NUMBER={1},
YEAR={1990},
MONTH={Jan.},
PAGES={137--154},
keywords={long triangles, piecewise linear interpolation,
data dependent triangulations, approximation, long triangles},
ABSTRACT={
Given a set of data points in R2 and corresponding data
values, it is clear that the quality of a piecewise linear
interpolation over triangles depends on the specific
triangulation of the data points. While conventional
triangulation methods depend only on the distribution of the
data points in R2, this paper suggests that the
triangulation should depend on the data values as well.
Several data dependent criteria for defining the triangulation
are discussed and efficient algorithms for computing these
triangulations are presented. It is shown for a variety of
test cases that data dependent triangulations can improve
significantly the quality of approximation and that long and
thin triangles, which are traditionally avoided, are sometimes
very suitable.
},
}
@PHDTHESIS{Rippa90,
AUTHOR={Shmuel Rippa},
TITLE={Piecewise Linear Interpolation and Approximation Schemes Over
Data Dependent Triangulations},
SCHOOL={School of Mathematical Sciences, Tel Aviv U.},
YEAR={1990},
keywords={height field, terrain},
}
@ARTICLE{Rippa92subset,
AUTHOR={Shmuel Rippa},
TITLE={Adaptive Approximation by Piecewise Linear Polynomials on
Triangulations of Subsets of Scattered Data},
JOURNAL={SIAM J. Sci. Stat. Comput.},
VOLUME={13},
NUMBER={5},
MONTH={Sept.},
YEAR={1992},
PAGES={1123--1141},
keywords={surface simplification, least squares fitting},
ABSTRACT={
Given a set V of data points in R2 with corresponding
data values, the problem of adaptive piecewise polynomial
approximation is to choose a subset of points of V, to create
a triangulation of this subset, and to define a piecewise
linear surface over the triangulation such that the deviation
of this surface from the data set is no more than a prescribed
error tolerance. A typical numerical scheme starts with some
initial triangulation and adds more points as necessary until
the resulting piecewise linear surface satisfies the error
bound. In the paper two ingredients of such schemes are
discussed. The first problem is that of constructing a
suitable triangulation of a subset of points. The use of data-
dependent triangulations that depend on the given function
values at the data points is discussed, and some data-
dependent criteria for optimizing a triangulation are
presented and compared to the Delaunay criterion leading to
the well-known Delaunay triangulation. The second problem is
how to select a piecewise linear surface approximating the
given data. The paper uses the least-square approximation to
the data from the space of piecewise linear polynomials
defined over a triangulation of a subset of V. It is proved
that the matrix of the normal equations is always nonsingular
and a bound for its condition number is derived.
}
}
@ARTICLE{Rippa92longthin,
AUTHOR={Shmuel Rippa},
TITLE={Long and Thin Triangles Can Be Good for Linear Interpolation},
JOURNAL={SIAM J. Numer. Anal.},
VOLUME={29},
NUMBER={1},
MONTH={Feb.},
YEAR={1992},
PAGES={257--270},
KEYWORDS={approximation error, mesh, finite element method},
ANNOTE={Contrary to some interpretations of Gregory & Babuska-Aziz, large
angles are not always bad. Gives optimal triangle shape to minimize
approximation error of a given function.},
}
@ARTICLE{Dyn93fem,
AUTHOR={Nira Dyn and Shmuel Rippa},
TITLE={Data-Dependent Triangulations for Scattered Data Interpolation
and Finite Element Approximation},
JOURNAL={Applied Numer. Math.},
VOLUME=12,
YEAR=1993,
PAGES={89--105},
KEYWORDS={triangulation, mesh, approximation theory},
ANNOTE={variational triangulation},
}
@TECHREPORT{Kao91,
AUTHOR={Thomas Kao and David M. Mount and Alan Saalfeld},
TITLE={Dynamic Maintenance of {Delaunay} Triangulations},
NOTE={CS-TR-2585},
INSTITUTION={CS Dept., U. of Maryland at College Park},
MONTH={Jan.},
YEAR={1991},
keywords={computational geometry, incremental Delaunay triangulation},
ABSTRACT={
We describe and analyze the complexity of a
procedure for computing and updating a Delaunay triangulation
of a set of points in the plane subject to Incremental
insertions and deletions. Our method is based on a recent
algorithm of Guibas, Knuth, and Sharir for constructing
Delaunay triangulations by Incremental point insertion only.
Our implementation features several methods that are not
usually present in standard GIS algorithms. Our algorithm
involves: Incremental update: During point insertion or
deletion only the portion of the triangulation affected by the
insertion or deletion is modified.Randomized methods: For
triangulation building or updates involving large collections
of point, randomized techniques are employed to improve the
expected performance of the algorithm, irrespective of the
distribution of points. Persistence: Earlier versions of the
triangulation can be recovered efficiently.
},
}
@INPROCEEDINGS{Lee89,
AUTHOR={Jay Lee},
TITLE={A drop heuristic conversion method for extracting irregular
network for digital elevation models},
BOOKTITLE={GIS/LIS '89 Proc.},
VOLUME={1},
MONTH={Nov.},
YEAR={1989},
PUBLISHER={American Congress on Surveying and Mapping},
PAGES={30--39},
keywords={triangulated irregular network, terrain, surface simplification},
ABSTRACT={
The advantages and disadvantages of various DEMs have been
discussed extensively and authors have concluded that for many
types of applications the triangulated irregular network is
better suited for approximating terrain surfaces because of
its efficiency in data storage and its simple structure for
accommodating irregular data points. While the USGS grid DEM
files are the most widely available digital elevation data, an
efficient conversion algorithm between grid-based DEM and TIN
models becomes more important as TIN models are increasingly
more popular. The author examines and compares several
existing methods of converting grid DEMs to TIN models with a
new method which uses a drop heuristic approach. The drop
heuristic method may be used either to extract TINs from grid
DEM or to reduce the size of an irregularly spaced point set.
},
}
@ARTICLE{Lee91,
AUTHOR={Jay Lee},
TITLE={Comparison of existing methods for building triangular
irregular network models of terrain from grid digital elevation models},
JOURNAL={Intl. J. of Geographical Information Systems},
VOLUME={5},
NUMBER={3},
MONTH={July-Sept.},
YEAR={1991},
PAGES={267--285},
keywords={terrain, triangulated irregular network, TIN},
ABSTRACT={
Triangulated irregular networks (TINs) are increasingly
popular for their efficiency in data storage and their ability
to accommodate irregularly spaced elevation points for many
applications of geographical information systems. The paper
reviews and evaluates various methods for extracting TINs from
dense digital elevation models (DEMs) on a sample DEM. Both
structural and statistical comparisons show that the methods
perform with different rates of success in different settings.
Users of DEM to TIN conversion methods should be aware of the
strengths and weaknesses of the methods in addition to their
own purposes before conducting the conversion.
},
ANNOTE={Compares his drop heuristic algorithm to Chen-Guevara and DeFloriani84},
}
@ARTICLE{Hamann94curve,
AUTHOR={Bernd Hamann and Jiann-Liang Chen},
TITLE={Data point selection for piecewise linear curve approximation},
JOURNAL={Computer-Aided Geometric Design},
VOLUME={11},
NUMBER={3},
MONTH={June},
YEAR={1994},
PAGES={289--301},
keywords={curve fitting, curve simplification, curvature, compression,
volume visualization},
ABSTRACT={
A method for selecting data points from a finite set of curve
points is discussed. The given curve points originate from a
smooth curve and are weighted with respect to a local curvature
measure. The most significant points are selected and used to
approximate the curve. The selected subset of data points is
distributed in such a way that they are uniformly distributed
with respect to integrated absolute curvature. The technique is
tested for various planar curves and is applied to 2D image
compression and volume visualization.
},
}
@ARTICLE{Hamann94decimate,
AUTHOR={Bernd Hamann},
TITLE={A data reduction scheme for triangulated surfaces},
JOURNAL={Computer-Aided Geometric Design},
VOLUME={11},
YEAR={1994},
PAGES={197--214},
keywords={surface simplification, curvature, decimate},
ABSTRACT={
Given a surface triangulation in three-dimensional space, an
algorithm is developed to iteratively remove triangles from the
triangulation. An underlying parametric or implicit surface
representation is not required. An order is introduced on the
set of triangles by considering curvature at their vertices.
Triangles in nearly planar surface regions are prime candidates
for removal. The degree of reduction can be specified by a
percentage or, in the case of bivariate functions, by an error
tolerance.
},
}
@ARTICLE{Hamann94volume,
AUTHOR={Bernd Hamann and Jiann-Liang Chen},
TITLE={Data point selection for piecewise trilinear approximation},
JOURNAL={Computer-Aided Geometric Design},
VOLUME={11},
YEAR={1994},
PAGES={477--489},
keywords={simplification, curvature, volume visualization},
}
@BOOK{Foley90,
TITLE={Computer Graphics: Principles and Practice, 2nd ed.},
AUTHOR={James D. Foley and Andries van Dam and Steven K. Feiner and
John F. Hughes},
PUBLISHER={Addison-Wesley},
ADDRESS={Reading MA},
YEAR={1990},
}
@INCOLLECTION{Jones94,
author = "Michael Jones",
title = "Lessons Learned from Visual Simulation",
pages = "39--71",
booktitle = {SIGGRAPH '94 Course Notes CD-ROM,
Course 14: Designing Real-Time Graphics for Entertainment},
publisher={ACM SIGGRAPH},
year = "1994",
month = "July",
keywords = "simulator, multiresolution, real-time, texture",
}
@ARTICLE{Ballard81,
AUTHOR={Dana H. Ballard},
TITLE={Strip Trees: A Hierarchical Representation for Curves},
JOURNAL={Communications of the ACM},
VOLUME={24},
NUMBER={5},
PAGES={310--321},
YEAR={1981},
keywords={curve simplification, data structure},
}
@Book{Ballard82,
author = "Dana H. Ballard and Christopher M. Brown",
title = "Computer Vision",
publisher = "Prentice Hall",
address = "Englewood Cliffs, NJ",
year = "1982",
}
@PhdThesis{Turner74,
author = "K. J. Turner",
title = "Computer perception of curved objects using a
television camera",
school = "U. of Edinburgh, Scotland",
month = nov,
year = "1974",
}
@MISC{Franklin93,
AUTHOR={W. Randolph Franklin},
TITLE={tin.c},
INSTITUTION={Rensselaer Polytechnic Inst.},
NOTE={C code, \URL{ftp://ftp.cs.rpi.edu/pub/franklin/tin.tar.gz}},
YEAR={1993},
keywords={terrain, surface simplification},
ANNOTE={translated from PL/1 code written in 1973},
}
@article{d-gmpr-84
, author = "G. Dutton"
, title = "Geodesic modelling of planetary relief"
, journal = "Cartographica"
, volume = 21
, year = 1984
, pages = "188--207"
, keywords = "data structuring, terrain modelling, construction, approximation, geodesics, locus approach, implicit data structures, triangulations, polyhedra"
}
@phdthesis{d-ascg-90
, author = "G. Das"
, title = "Approximation schemes in computational geometry"
, type = "Ph.{D}. Thesis"
, school = "University of Wisconsin"
, year = 1990
, keywords = "doctoral thesis"
, annote = {polygonal approximation of convex surfaces is NP-HARD},
}
@inproceedings{dj-mvhpd-90
, author = "G. Das and D. Joseph"
, title = "Minimum vertex hulls for polyhedral domains"
, booktitle = "Proc. 7th Sympos. Theoret. Aspects Comput. Sci."
, series = "Lecture Notes in Computer Science"
, volume = 415
, publisher = "Springer-Verlag"
, year = 1990
, precedes = "dj-mvhpd-92"
, update = "95.01 mitchell"
, annote = {polygonal approximation of convex surfaces is NP-HARD},
}
@article{dj-mvhpd-92
, author = "G. Das and D. Joseph"
, title = "Minimum vertex hulls for polyhedral domains"
, journal = "Theoret. Comput. Sci."
, volume = 103
, year = 1992
, pages = "107--135"
, succeeds = "dj-mvhpd-90"
, update = "95.01 mitchell, 95.01 mitchell"
, annote = {polygonal approximation of convex surfaces is NP-HARD},
}
@inproceedings{dj-cmcnp-90
, author = "G. Das and D. Joseph"
, title = "The complexity of minimum convex nested polyhedra"
, booktitle = "Proc. 2nd Canad. Conf. Comput. Geom."
, year = 1990
, pages = "296--301"
, annote = {polygonal approximation of convex surfaces is NP-HARD},
}
@inproceedings{dg-caitd-95
, author = "Gautam Das and Michael T. Goodrich"
, title = "On the Complexity of Approximating and Illuminating Three-Dimensional Convex Polyhedra"
, booktitle = "Proc. 4th Workshop Algorithms Data Struct."
, series = "Lecture Notes in Computer Science"
, publisher = "Springer-Verlag"
, year = 1995
, note = "To appear"
, keywords = "graph drawing, 3D, convex, polyhedron"
, update = "95.05 mitchell+tamassia"
, annote = {proof that polygonal approximation of convex surfaces is NP-HARD}
}
@inproceedings{ms-saps-92
, author = "Joseph S. B. Mitchell and S. Suri"
, title = "Separation and approximation of polyhedral surfaces"
, booktitle = "Proc. 3rd ACM-SIAM Sympos. Discrete Algorithms"
, year = 1992
, pages = "296--306"
, comments = "To appear, Comput. Geom. Theory Appl."
, succeeds = "ms-saps-91"
, update = "95.01 mitchell"
, annote = {algorithm for approximating convex surfaces within log factor
of optimal}
}
@inproceedings{c-apca-93
, author = "Kenneth L. Clarkson"
, title = "Algorithms for Polytope Covering and Approximation"
, booktitle = "Proc. 3rd Workshop Algorithms Data Struct."
, series = "Lecture Notes in Computer Science"
, volume = 709
, year = 1993
, pages = "246--252"
, update = "93.09 milone+mitchell+smid, 93.05 jones"
, annote = {algorithm for approximating convex surfaces within log factor
of optimal, log of output size}
}
@inproceedings{bg-aoscf-94
, author = {H. Br\"onnimann and M. T. Goodrich}
, title = "Almost Optimal Set Covers in Finite {VC}-Dimension"
, booktitle = "Proc. 10th Annual ACM Symp. on Computational Geometry"
, year = 1994
, pages = "293--302"
, update = "94.09 jones, 94.01 jones"
, annote = {algorithm for approximating convex surfaces within constant factor
of optimal}
}
@inproceedings{b-aops-94
, author = {H. Br\"onnimann}
, title = "Almost Optimal Polyhedral Separators"
, booktitle = "Proc. 10th Annual ACM Symp. on Computational Geometry"
, year = 1994
, pages = "393--394"
, keywords = "video review"
, update = "94.09 jones"
, annote = {related to optimal polygonal approximation of convex surfaces}
}
@techreport{Mitchell93sep,
author={Joseph S. B. Mitchell},
title={Approximation Algorithms for Geometric Separation Problems},
institution={Dept. of Applied Math. and Statistics,
State U. of New York at Stony Brook},
month={July},
year=1993,
annote={polygonal approximation of terrains within log factor of optimal},
}
@INPROCEEDINGS{Silva95,
TITLE={Automatic Generation of Triangular Irregular Networks using Greedy Cuts},
AUTHOR={Cl\'audio T. Silva and Joseph S. B. Mitchell and Arie E. Kaufman},
BOOKTITLE={Proc. Visualization '95},
PUBLISHER={IEEE Comput. Soc. Press},
YEAR={1995},
NOTE={To appear. \URL{http://www.cs.sunysb.edu:80/~csilva/claudio-papers.html}},
}
@inproceedings{Agarwal94soda
, author = "Pankaj K. Agarwal and Subhash Suri"
, title = "Surface Approximation and Geometric Partitions"
, booktitle = "Proc. 5th ACM-SIAM Sympos. Discrete Algorithms"
, year = 1994
, pages = "24--33"
, keywords = "triangulation, ray shooting"
, update = "95.01 mitchell"
, annote={polygonal approximation of terrains within log factor of optimal}
, note={(Also available as Duke U. CS tech report,
\URL{ftp://ftp.cs.duke.edu/dist/techreport/1994/1994-21.ps.Z})}
}
@TECHREPORT{Agarwal94tr,
AUTHOR = "Pankaj K. {Agarwal} and Subhash Suri.",
YEAR = "1994",
LOCATION = "\URL{ftp://ftp.cs.duke.edu/dist/techreport/1994/1994-21.ps.Z}.",
INSTITUTION = "Department of Computer Science, Duke University",
REPORTNUMBER = "Technical report DUKE--TR--1994--21",
TITLE = " Surface approximation and Geometric Partitions",
ABSTRACT = "Motivated by applications in computer graphics, visualization,
and scientific computation, we study the computational complexity of
the following problem:
Given a set $S$ of $n$ points sampled from a bivariate function
$f(x,y)$ and an input parameter $\epsilon > 0$, compute a piecewise linear
function $\Sigma(x,y)$ of minimum complexity (that is, a $xy$-monotone
polyhedral surface, with a minimum number of vertices, edges, or faces)
such that
\[| \Sigma(x_p, y_p) \; - \; z_p | \:\:\leq\:\: \epsilon ,\quad \mbox{ for
all }
(x_p, y_p, z_p) \in S.
\]
We prove that the decision version of this problem is NP-Hard. The main
result of our paper is a polynomial-time approximation algorithm that
computes a piecewise linear surface of size $O(K_o \log K_o )$,
where $K_o$ is the complexity of an optimal surface satisfying
the constraints of the problem.
The technique developed in our paper is more general and applies to several
other problems that deal with partitioning of points (or other objects)
subject to certain geometric %{\em disjointness\/} constraints. For
instance, we get the same approximation bound for the following problem
arising in machine learning: given $n$ `red' and $m$ `blue' points in the
plane, find a minimum number of {\em pairwise disjoint\/} triangles such
that each blue point is covered by some triangle and no red point lies in
any of the triangles.",
KEY = "DukeTR9421",
}
@inproceedings{ghms-apsml-91
, author = "Leonidas J. Guibas and John E. Hershberger and
Joseph S. B. Mitchell and Jack S. Snoeyink"
, title = "Approximating polygons and subdivisions with minimum link paths"
, booktitle = "Proc. 2nd Annu. SIGAL Intl. Sympos. Algorithms"
, series = "Lecture Notes in Computer Science"
, volume = 557
, publisher = "Springer-Verlag"
, year = 1991
, pages = "151--162"
, precedes = "ghms-apsml-93"
, update = "95.01 mitchell"
, annote={approximation of 2-D curves},
}
@article{ghms-apsml-93
, author = "Leonidas J. Guibas and John E. Hershberger
and Joseph S. B. Mitchell and Jack S. Snoeyink"
, title = "Approximating Polygons and Subdivisions with Minimum Link Paths"
, journal = "Intl. J. Comput. Geom. Appl."
, volume = 3
, number = 4
, month = dec
, year = 1993
, pages = "383--415"
, succeeds = "ghms-apsml-91"
, update = "95.01 mitchell"
, annote={the first provably good methods for approximating
monotone polygons},
}
@inproceedings{g-eplfa-94
, author = "M. T. Goodrich"
, title = "Efficient Piecewise-Linear Function Approximation Using the Uniform Metric"
, booktitle = "Proc. 10th Annual ACM Symp. on Computational Geometry"
, year = 1994
, pages = "322--331"
, update = "94.09 jones, 94.01 jones"
, annote={approximating 2-D curves,
version to appear in Discrete & Computational Geometry 14:4 1995},
}
@book{Preparata85
, author = "Franco P. Preparata and Michael I. Shamos"
, title = "Computational Geometry: an Introduction"
, publisher = "Springer-Verlag"
, address = "New York, NY"
, year = 1985
, comments = "2nd printing, 1988"
}
@InProceedings{DeHeIk:91,
author = "H. Delingette and M. Hebert and K. Ikeuchi",
title = "Shape Representation and Image Segmentation Using
Deformable Surfaces",
booktitle={Conf. on Computer Vision and Pattern Recognition (CVPR '91)},
year = "1991",
pages = "467--472",
}
@ARTICLE{Delingette92,
AUTHOR={Herv\'e Delingette and Martial Hebert and Katsushi Ikeuchi},
TITLE={Shape Representation and Image Segmentation Using Deformable Surfaces},
JOURNAL={Image and Vision Computing},
VOLUME={10},
NUMBER={3},
MONTH={Apr.},
YEAR={1992},
PAGES={132--144},
keywords={surface simplification, computer vision},
}
@TECHREPORT{Delingette94tr,
AUTHOR={Herv\'e Delingette},
TITLE={Simplex Meshes: a General Representation for {3D} Shape Reconstruction},
INSTITUTION={INRIA, Sophia Antipolis, France},
MONTH={Mar.},
YEAR={1994},
NOTE={No. 2214,
\URL{http://zenon.inria.fr:8003/epidaure/personnel/delingette/delingette.html}},
keywords={computer vision},
}
@INPROCEEDINGS{Delingette94cvpr,
AUTHOR={Herv\'e Delingette},
TITLE={Simplex Meshes: a General Representation for {3D} Shape Reconstruction},
BOOKTITLE={Conf. on Computer Vision and Pattern Recognition (CVPR '94)},
MONTH={June},
YEAR={1994},
NOTE={\URL{http://zenon.inria.fr:8003/epidaure/personnel/delingette/delingette.html}},
keywords={computer vision},
}
@TECHREPORT{Ikeuchi95spheretr,
AUTHOR={Katsushi Ikeuchi and Martial Hebert},
TITLE={Spherical Representations: from EGI to SAI},
INSTITUTION={CS Dept., Carnegie Mellon U.},
MONTH={Oct.},
YEAR={1995},
NOTE={CMU-CS-95-197, \URL{ftp://reports.adm.cs.cmu.edu/usr/anon/1995/CMU-CS-95-197.ps}},
keywords={computer vision, shape matching, surface curvature},
}
@INPROCEEDINGS{Welch94,
AUTHOR={William Welch and Andrew Witkin},
TITLE={Free-Form Shape Design Using Triangulated Surfaces},
BOOKTITLE={SIGGRAPH '94 Proc.},
PUBLISHER={ACM},
YEAR={1994},
PAGES={247--256},
keywords={fair surface design, adaptive mesh, Delaunay triangulation},
}
@PHDTHESIS{Welch95,
AUTHOR={William Welch},
TITLE={Serious Putty: Topological Design for Variational Curves and Surfaces},
SCHOOL={CS Dept, Carnegie Mellon U.},
MONTH={Dec.},
YEAR={1995},
KEYWORDS={curvature, triangulation, fair surface design, adaptive mesh,
Delaunay triangulation, Laplacian smoothing},
NOTE={CMU-CS-95-217,
\URL{ftp://reports.adm.cs.cmu.edu/usr/anon/1995/CMU-CS-95-217A.ps,
CMU-CS-95-217B.ps, CMU-CS-95-217C.ps},
also \URL{http://www.cs.cmu.edu/afs/cs.cmu.edu/user/claude/www/welch-home.html}},
}
@TECHREPORT{Teng92,
AUTHOR = "Y. Ansel Teng and Larry S. Davis",
TITLE = "Visibility Analysis on Digital Terrain Models
and its Parallel Implementation",
INSTITUTION = "Center for Automation Research,
University of Maryland",
YEAR = "1992",
TYPE = "Technical Report",
NUMBER = "CAR-TR-625",
ADDRESS = "College Park, Maryland",
MONTH = "May",
}
@MastersThesis{j-cbatv-89,
author = "D. M. Jung",
title = "Comparisons between algorithms for terrain visibility",
school = "Rensselaer Polytechnic Institute, Electrical,
Computer, and Systems Engineering Dept",
year = 1989,
}
@MastersThesis{s-vtl-90,
author = "Andrew Shapira",
title = "Visibility and terrain labeling",
school = "Rensselaer Polytechnic Institute, Electrical,
Computer, and Systems Engineering Dept.",
year = 1990,
}
@MastersThesis{n-hlddtm-88,
author = "Hari Nair",
title = " A high-level desription of digital terrain models using visib
ility
information",
school = " Rensselaer Polytechnic Institute, Electrical,
Computer, and Systems Engineering Dept.",
year = 1988
}
@Article{Weibel92,
author = "Robert Weibel",
title = "Models And Experiments for Adaptive
Computer-Assisted Terrain Generalization",
journal = {Cartography and Geographic Information Systems},
year = 1992,
volume = 19,
number = 3,
pages = "133--153"
}
@InProceedings{gold-zurich-90,
author = "Christopher M. Gold",
title = "Space Revisited -- Back to the Basics",
crossref="SDDH90",
Pages="175--189",
keywords="TIN",
}
@InProceedings{elgindy-zurich-90,
author = "Hossam ElGindy",
title = "Optimal Parallel Algorithms for Updating Planar Triangulations"
,
crossref="SDDH90",
Pages="200--208",
keywords="TIN",
}
@InProceedings{chen-zurich-90,
author = "Zi-Tan Chen",
title = "A Quadtree Guides Fast Spatial Searches in Triangular
Irregular Network (TIN)",
Pages="209--215",
crossref="SDDH90",
keywords="TIN",
}
@Proceedings{SDDH90,
Booktitle="4th International Symposium on Spatial Data Handling",
title="4th International Symposium on Spatial Data Handling",
Month="23-27 July",
Year=1990,
Address={Z\"urich},
editor="Kurt Brassel and H. Kishimoto"
}
@Article(peucker-75,
Author="Thomas K. Peucker and Nicholas Chrisman",
Title="Cartographic Data Structures",
Journal="The American Cartographer",
Volume="2",
Number={1 (or 2?)},
Year=1975,
Pages="55--69",
annote={
Chrisman did a nice extension of the Douglas-Peucker-Freeman-Ramer
algorithm that calculates an epsilon for each point. Then you could later
choose your delta, pass down the line filtering the points to get your
desired generalization. Is this it?
},
)
@PhdThesis{j-ssds-89,
author = "Guy Jacobson",
title = "Succinct Static Data Structures",
school = "Carnegie-Mellon",
year = 1989,
month = jan,
note = "Tech Rep CMU-CS-89-112",
keywords={compression},
annote = {
Minimum # bits to represent trees and graphs.
A planar graph can be represented in about 64n bits,
with O(log n) search and adjacency time.
},
}
@Article{t-srg-84,
author = "G. Turan",
title = "Succinct representations of graphs",
journal = "Discrete Applied Math",
year = 1984,
volume = 8,
pages = "289--294",
keywords={compression},
annote = {A planar graph can be represented in about 12n bits},
}
@InBook{j-sstg-89,
author = "Guy Jacobson",
title = "30th Annual Symp. on Foundations of Computer Science",
chapter = "Space-efficient static trees and graphs",
year = 1989,
volume = 30,
pages = {549--554},
keywords={compression},
annote = {
Minimum # bits to represent trees and graphs.
A planar graph can be represented in about 64n bits,
with O(log n) search and adjacency time.
},
abstract={
Data structures that represent static unlabeled trees and
planar graphs are developed. The structures are more space
efficient than conventional pointer-based representations, but
(to within a constant factor) they are just as time efficient
for traversal operations. For trees, the data structures
described are asymptotically optimal: there is no other
structure that encodes n-node trees with fewer bits per node,
as N grows without bound. For planar graphs (and for all graphs
of bounded page number), the data structure described uses
linear space: it is within a constant factor of the most
succinct representation.
},
keywords={computational complexity, data structure, graph theory},
}
@TECHREPORT{Bernal93,
AUTHOR={Javier Bernal},
TITLE={Bibliographic Notes on Voronoi Diagrams},
INSTITUTION={Natl. Inst. of Standards and Tech.},
NOTE={NIST Internal Report 5164,
\URL{http://gams.nist.gov/acmd/Staff/JBernal/index.html}},
MONTH={April},
YEAR={1993},
ANNOTE={bibliography of Voronoi diagram and Delaunay triangulation work,
54 pp.},
}
@ARTICLE{McClure75,
AUTHOR={Donald E. McClure},
TITLE={Nonlinear Segmented Function Approximation and Analysis of Line
Patterns},
JOURNAL={Quarterly of Applied Math.},
VOLUME={33},
NUMBER={1},
MONTH={Apr.},
YEAR={1975},
PAGES={1--37},
keywords={curve simplification, error analysis, approximation theory},
}
@TECHREPORT{McClure76,
AUTHOR={Donald E. McClure},
TITLE={Characterization and Approximation of Optimal Plane Partitions},
INSTITUTION={Brown U.},
NOTE={Pattern Analysis Report 36},
YEAR=1976,
KEYWORDS={triangulation, error analysis},
}
@TECHREPORT{McClure89,
AUTHOR={Donald E. McClure and S. C. Shwartz},
TITLE={A Method of Image Representation Based on Bivariate Splines},
NOTE={CICS-P-113},
MONTH={Mar.},
YEAR={1989},
INSTITUTION={Center for Intelligent Control Systems, MIT},
keywords={triangulation, surface simplification, error analysis,
approximation theory, curvature, Hessian},
ANNOTE={optimal L2 fit of triangulation with fixed 2-D projection
(see also Rippa).
Mathy, no algorithms.},
}
@PHDTHESIS{Nadler85,
AUTHOR={E. J. Nadler},
TITLE={Piecewise Linear Approximation on Triangulations of a Planar Region},
SCHOOL={Div. Applied Math., Brown U.},
NOTE={Pattern Analysis Report 140},
MONTH={May},
YEAR=1985,
KEYWORDS={data-dependent triangulation, curvature, error analysis},
}
@INPROCEEDINGS{Nadler86,
AUTHOR={Edmond Nadler},
TITLE={Piecewise Linear Best {$L_2$} Approximation on Triangulations},
BOOKTITLE={Approximation Theory V},
EDITOR={C. K. Chui and others},
PUBLISHER={Academic Press},
ADDRESS={Boston},
YEAR={1986},
PAGES={499--502},
KEYWORDS={data-dependent triangulation, curvature, error analysis},
}
@BOOK{Pavlidis77,
AUTHOR={Theodosios Pavlidis},
TITLE={Structural Pattern Recognition},
PUBLISHER={Springer-Verlag},
ADDRESS={Berlin},
YEAR={1977},
keywords={computer vision, curve simplification, segmentation},
}
@ARTICLE{Tomek74,
AUTHOR={Ivan Tomek},
TITLE={Two Algorithms for Piecewise-Linear Continuous Approximation of Functions
of One Variable},
JOURNAL={IEEE Trans. Computers},
VOLUME={C-23},
PAGES={445--448},
MONTH={Apr.},
YEAR={1974},
keywords={curve simplification},
}
@BOOK{deBoor78,
AUTHOR={Carl de Boor},
TITLE={A Practical Guide to Splines},
PUBLISHER={Springer},
ADDRESS={Berlin},
YEAR={1978},
}
@Book{Mandelbrot77,
author = "Benoit Mandelbrot",
title = "Fractals -- form, chance, and dimension",
publisher = "Freeman",
address = "San Francisco",
year = "1977",
}
@Book{Marr82,
author = "David Marr",
year = "1982",
title = "Vision",
address = "San Francisco",
publisher = "Freeman",
keywords = {computer vision},
}
@ARTICLE{VonHerzen87,
AUTHOR={Von Herzen, Brian and Alan H. Barr},
TITLE={Accurate Triangulations of Deformed, Intersecting Surfaces},
JOURNAL={Computer Graphics
(SIGGRAPH '87 Proceedings)},
VOLUME={21},
NUMBER={4},
MONTH={July},
YEAR={1987},
PAGES={103--110},
}
@PHDTHESIS{VonHerzen88,
AUTHOR={Brian {Von Herzen}},
TITLE={Applications of Surface Networks to Sampling Problems in Computer
Graphics},
SCHOOL={CS Dept., Caltech},
NOTE={CS-TR-88-15},
YEAR={1988},
keywords={quadtree},
}
@ARTICLE{Gomez79,
AUTHOR={Dora G\'omez and Adolfo Guzm\'an},
TITLE={Digital Model for Three-Dimensional Surface Representation},
JOURNAL={Geo-Processing},
VOLUME={1},
YEAR={1979},
PAGES={53--70},
keywords={triangulation, crack},
}
@INCOLLECTION{Peucker76,
AUTHOR={Thomas K. Peucker},
TITLE={A Theory of the Cartographic Line},
BOOKTITLE={Intl. Yearbook of Cartography},
VOLUME={16},
YEAR={1976},
PAGES={134--143},
}
@INCOLLECTION{Margaliot94,
AUTHOR={Michael Margaliot and Craig Gotsman},
TITLE={Piecewise-Linear Surface Approximation from Noisy Scattered Samples},
BOOKTITLE={Proc. Visualization '92},
PUBLISHER={IEEE Comput. Soc. Press},
YEAR={1994},
PAGES={61--68},
keywords={surface simplification, noise},
}
@INCOLLECTION{Margaliot95,
AUTHOR={Michael Margaliot and Craig Gotsman},
TITLE={Approximation of Smooth Surfaces and Adaptive Sampling by
Piecewise-Linear Interpolants},
BOOKTITLE={Computer Graphics: Developments in Virtual Environments},
EDITOR={Rae Earnshaw and John Vince},
PUBLISHER={Academic Press},
ADDRESS={London},
YEAR={1995},
PAGES={17--27},
keywords={surface simplification, data-dependent triangulation,
adaptive sampling},
ANNOTE={discusses 2 problems: choosing the best triangulation given
a point set, and adaptive sampling of an unknown continuous function
of two variables},
}
@PHDTHESIS{Varshney94,
AUTHOR={Amitabh Varshney},
TITLE={Hierarchical Geometric Approximations},
SCHOOL={Dept. of CS, U. of North Carolina, Chapel Hill},
YEAR={1994},
NOTE={TR-050},
KEYWORDS={molecule, surface simplification},
ANNOTE={fast parallel algorithm for (Connolly) molecule surface generation,
algorithm for simplifying polygonal models},
}
@TECHREPORT{Varshney95,
AUTHOR={Amitabh Varshney and Pankaj K. Agarwal and Frederick P. {Brooks, Jr.}
and William V. Wright and Hans Weber},
TITLE={Generating Levels of Detail for Large-Scale Polygonal Models},
INSTITUTION={Dept. of CS, Duke U.},
YEAR={1995},
MONTH={Aug.},
NOTE={CS-1995-20,
\URL{http://www.cs.duke.edu/department.html#techrept}},
KEYWORDS={computational geometry, surface simplification},
ANNOTE={algorithm from Varshney's PhD thesis},
}
@INPROCEEDINGS{Cosman81,
AUTHOR={Michael A. Cosman and Robert A. Schumacker},
TITLE={System Strategies to Optimize {CIG} Image Content},
BOOKTITLE={Proceedings of the Image II Conference},
MONTH={June},
YEAR={1981},
PUBLISHER={Image Society, Tempe, AZ},
PAGES={463--480},
KEYWORDS={multiresolution model, level of detail, simulator,
visibility, painter's algorithm, antialiasing, transparency, real-time},
ANNOTE={discusses Evans&Sutherland CT-5
simulator design, manual creation of multires. models},
}
@INPROCEEDINGS{Cosman90,
AUTHOR={Michael A. Cosman and Allan E. Mathisen and John A. Robinson},
TITLE={A New Visual System to Support Advanced Requirements},
BOOKTITLE={Proceedings of the 1990 Image V Conference},
MONTH={June},
YEAR={1990},
PUBLISHER={Image Society, Tempe, AZ},
PAGES={371--380},
KEYWORDS={multiresolution model, level of detail, simulator,
terrain, texture mapping, r buffer, z buffer, image warping},
ANNOTE={discusses Evans&Sutherland simulator design. A broad paper},
}
@INPROCEEDINGS{Ferguson90,
AUTHOR={R. L. Ferguson and R. Economy and W. A. Kelley and P. P. Ramos},
TITLE={Continuous Terrain Level of Detail for Visual Simulation},
BOOKTITLE={Proceedings of the 1990 Image V Conference},
MONTH={June},
YEAR={1990},
PUBLISHER={Image Society, Tempe, AZ},
PAGES={145--151},
KEYWORDS={multiresolution model, level of detail, simulator},
}
@ARTICLE{Crow82,
AUTHOR={Franklin C. Crow},
TITLE={A More Flexible Image Generation Environment},
JOURNAL={Computer Graphics (SIGGRAPH '82 Proc.)},
VOLUME={16},
NUMBER={3},
MONTH={July},
YEAR={1982},
PAGES={9--18},
KEYWORDS={level of detail, painter's algorithm},
ANNOTE={one paragraph and a few photos showing levels of detail},
}
@INPROCEEDINGS{Field92,
AUTHOR={David A. Field},
TITLE={Delaunay Criteria for Triangulating Surfaces},
BOOKTITLE={Curves and Surfaces in Computer Vision and Graphics III},
VOLUME={1830},
PUBLISHER={SPIE},
YEAR={1992},
PAGES={237--246},
}
@INPROCEEDINGS{Asano95,
AUTHOR={T. Asano and N. Katoh and E. Lodi and T. Roos},
TITLE={Optimal approximation of monotone curves on a grid},
BOOKTITLE={Seventh Canadian Conf. on Computational Geometry},
ADDRESS={Quebec City},
MONTH={Aug.},
YEAR={1995},
}
@article{ag-aplai-87
, author = "E. Allgower and S. Gnutzmann"
, title = "An algorithm for piecewise linear approximation of an implicitly defined two-dimensional surfaces"
, journal = "SIAM J. Numer. Anal."
, volume = 24
, year = 1987
, pages = "452--469"
, keywords = "surface-approximation"
, update = "95.05 agarwal"
}
@inproceedings{hiir-wolla-89
, author = "M. E. Houle and H. Imai and K. Imai and J.-M. Robert"
, title = "Weighted orthogonal linear {$L_{\infty}$}-approximation and applications"
, booktitle = "Proc. 1st Workshop Algorithms Data Struct."
, series = "Lecture Notes in Computer Science"
, volume = 382
, publisher = "Springer-Verlag"
, year = 1989
, pages = "183--191"
}
@techreport{iky-ltall-87
, author = "H. Imai and K. Kato and P. Yamamoto"
, title = "A linear-time algorithm for linear {$L_{1}$} approximation of points"
, type = "Report"
, number = "CSCE-87-C30"
, institution = "Dept. Comput. Sci. Commun. Engrg., Kyushu Univ."
, address = "Kukuoka, Japan"
, year = 1987
, precedes = "iky-ltall-89"
}
@article{iky-ltall-89
, author = "H. Imai and K. Kato and P. Yamamoto"
, title = "A linear-time algorithm for linear {$L_{1}$} approximation of points"
, journal = "Algorithmica"
, volume = 4
, year = 1989
, pages = "77--96"
, succeeds = "iky-ltall-87"
}
@article{imm-ltaaf-81
, author = "M. Iri and K. Murota and S. Matsui"
, title = "Linear-time approximation algorithms for finding the minimum-weight perfect matching on a plane"
, journal = "Inform. Process. Lett."
, volume = 12
, year = 1981
, pages = "206--209"
}
@inproceedings{rt-laso-92
, author = "J.-M. Robert and G. Toussaint"
, title = "Linear approximation of simple objects"
, booktitle = "Proc. 9th Sympos. Theoret. Aspects Comput. Sci."
, series = "Lecture Notes in Computer Science"
, volume = 577
, publisher = "Springer-Verlag"
, year = 1992
, pages = "233--244"
}
@inproceedings{ykii-avoll-88
, author = "P. Yamamoto and K. Kato and K. Imai and H. Imai"
, title = "Algorithms for vertical and orthogonal {$L_{1}$} linear approximation of points"
, booktitle = "Proc. 4th Annu. ACM Sympos. Comput. Geom."
, year = 1988
, pages = "352--361"
}
@BOOK{Fan90,
AUTHOR={Ting-Jun Fan},
TITLE={Describing and Recognizing 3-D Objects Using Surface Properties},
PUBLISHER={Springer-Verlag},
ADDRESS={New York},
YEAR={1990},
KEYWORDS={computer vision},
ANNOTE={fitting quadrics, discontinuities},
}
@INPROCEEDINGS{Milgram80,
AUTHOR={D. I. Milgram and C. M. Bjorklund},
TITLE={Range Image Processing: Planar Surface Extraction},
BOOKTITLE={Fifth Intl. Joint Conf. on Pattern Recognition},
YEAR={1980},
PAGES={912--919},
}
@INPROCEEDINGS{Faugeras83measure,
AUTHOR={Olivier D. Faugeras and E. Pauchon},
TITLE={Measuring the Shape of 3-D Objects},
BOOKTITLE={Proc. IEEE Intl. Conf. on Computer Vision and Pattern Recognition},
MONTH={June},
YEAR={1983},
PAGES={1--7},
ANNOTE={segment range data into tiny planar triangles},
}
@INPROCEEDINGS{Faugeras83quadratic,
AUTHOR={Olivier D. Faugeras and Martial Hebert and E. Pauchon},
TITLE={Segmentation of Range Data into Planar and Quadratic Patches},
BOOKTITLE={Proc. IEEE Intl. Conf. on Computer Vision and Pattern Recognition},
MONTH={June},
YEAR={1983},
PAGES={8--13},
ANNOTE={uses Faugeras83measure as preprocess, fits with least squares},
}
@article{Faugeras84approx
, author = "Olivier Faugeras and Martial Hebert and P. Mussi and
Jean-Daniel Boissonnat"
, title = "Polyhedral approximation of 3-{D} objects without holes"
, journal = "Computer Vision, Graphics, and Image Processing"
, volume = 25
, year = 1984
, pages = "169--183"
, keywords = {surface simplification, geodesic, computer vision, range data},
}
@ARTICLE{Boissonat84,
AUTHOR={Jean-Daniel Boissonnat},
TITLE={Geometric Structures for Three-Dimensional Shape Representation},
JOURNAL={ACM Trans. on Graphics},
VOLUME={3},
NUMBER={4},
YEAR={1984},
PAGES={266--28},
KEYWORDS={triangulation},
}
@ARTICLE{Ponce87,
AUTHOR={Jean Ponce and Olivier Faugeras},
TITLE={An Object Centered Hierarchical Representation for {3D} Objects:
The Prism Tree},
JOURNAL={Computer Vision, Graphics, and Image Processing},
VOLUME={38},
YEAR={1987},
PAGES={1--28},
KEYWORDS={surface simplification, geodesic, computer vision, range data,
surface intersection, intersection testing},
}
@INPROCEEDINGS{Garcia95,
AUTHOR={M. A. Garcia},
TITLE={Massively Parallel Approximation of Irregular Triangular Meshes
with G1 Parametric Surfaces},
BOOKTITLE={IRREGULAR '95
(Workshop on Parallel Algorithms for Irregularly Structured Problems)},
ADDRESS={Lyon, France},
YEAR={1995},
MONTH={Sep.},
ANNOTE={author at Polytechnic University of Catalonia, Barcelona},
KEYWORDS={surface simplification},
}
@ARTICLE{DAzevedo89siam,
AUTHOR={E. F. D'Azevedo and R. B. Simpson},
TITLE={On Optimal Interpolation Triangle Incidences},
JOURNAL={SIAM J. Sci. Stat. Comput.},
VOLUME=10,
NUMBER=6,
YEAR=1989,
PAGES={1063--1075},
KEYWORDS={triangulation, curvature, structured mesh, Delaunay triangulation},
}
@PHDTHESIS{DAzevedo89phd,
AUTHOR={E. F. D'Azevedo},
TITLE={On Optimal Triangulation for Piecewise Linear Approximation},
SCHOOL={CS Dept., U. of Waterloo, Waterloo, Ontario, Canada},
YEAR=1989,
KEYWORDS={linear interpolation, triangulation, curvature, structured mesh,
Delaunay triangulation},
}
@ARTICLE{DAzevedo91transform,
AUTHOR={E. F. D'Azevedo},
TITLE={Optimal triangular mesh generation by coordinate transformation},
JOURNAL={SIAM J. Sci. Stat. Comput.},
VOLUME={12},
NUMBER={4},
MONTH={July},
YEAR={1991},
PAGES={755--786},
ABSTRACT={
Presents the motivation for and construction of coordinate
transformations that generate optimally efficient meshes for
linear interpolation. The coordinate transformations are
derived from a result in differential geometry characterizing a
'flat' space. The optimality results are demonstrated for some
numerical examples. Adaptive meshes produced by PLTMG (R.E.
Bank, PLTMG: A Software Package for Solving Elliptic Partial
Differential Equations, Society for Industrial and Applied
Mathematics, Philadelphia, PA, 1990) are included for
comparison. The paper concludes that coordinate transformation
is a promising strategy for investigation into more complex
optimal meshing problems in finite element analysis.
},
KEYWORDS={linear interpolation, Delaunay triangulation, differential geometry,
Riemann-Christoffel tensor, curvature, finite element analysis,
structured mesh},
}
@ARTICLE{DAzevedo91gradient,
AUTHOR={E. F. D'Azevedo and R. B. Simpson},
TITLE={On Optimal Triangular Meshes for Minimizing Gradient Error},
VOLUME=59,
JOURNAL={Numerische Mathematik},
YEAR=1991,
PAGES={321--348},
KEYWORDS={linear interpolation, Delaunay triangulation, differential geometry,
Riemann-Christoffel tensor, curvature, finite element analysis,
structured mesh},
}
@ARTICLE{Gottschalk72,
AUTHOR={Hans-J\"org Gottschalk},
TITLE={Die Generalisierung von Isolinien als Ergebnis der Generalisierung
von Fl\"aschen},
JOURNAL={Zeitschrift f\"ur Vermessungswesen},
VOLUME={97},
NUMBER={11},
PAGES={489--494},
YEAR={1972},
NOTE={In German},
ANNOTE={cited by Weibel92 CAGIS,
uses global multiquadric interpolation scheme
on each pass, delete the point of highest error,
},
ABSTRACT={
A method for automatic generalization of contour lines is presented.
A surface z=f(x,y) to be represented by contour lines is given by a well
defined set of points (x,y,z). From this set a subset of points is selected
by means of which the generalized surface is calculated. In this way a
defined set of information can be derived from an initial set corresponding
to given laws, e.g. the law of Topfer.
},
}
@INPROCEEDINGS{Kalvin91spie,
AUTHOR={Alan D. Kalvin and Court B. Cutting and B. Haddad and M. E. Noz},
TITLE={Constructing Topologically Connected Surfaces
for the Comprehensive Analysis of {3D} Medical Structures},
BOOKTITLE={Medical Imaging V: Image Processing},
PUBLISHER={SPIE},
VOLUME={1445},
MONTH={Feb.},
YEAR={1991},
PAGES={247--258},
KEYWORDS={isosurface, marching cubes, winged edge, surface simplification},
ANNOTE={Algorithm:
phase 1: marching cubes with winged edge,
phase 2: merge adjacent coplanar rectangles.
"alligator algorithm", fixes holes & other problems with marching cubes},
}
@INPROCEEDINGS{Kalvin94,
AUTHOR={Alan D. Kalvin and Russell H. Taylor},
TITLE={Superfaces: Polyhedral Approximation with Bounded Error},
BOOKTITLE={Medical Imaging: Image Capture, Formatting, and Display},
PUBLISHER={SPIE},
VOLUME={2164},
PAGES={2--13},
MONTH={Feb.},
YEAR={1994},
KEYWORDS={surface simplification, linear programming, bounded error},
NOTE={(Also IBM Watson Research Center tech report RC 19135)},
}
@ARTICLE{Kalvin96,
AUTHOR={Alan D. Kalvin and Russel H. Taylor},
TITLE={Superfaces:Polygonal Mesh Simplification with Bounded Error},
JOURNAL={IEEE Computer Graphics and Appl.},
VOLUME=16,
NUMBER=3,
MONTH={May},
YEAR=1996,
ABSTRACT={
We describe Superfaces, a domain-independent method for simplifying
polyhedral meshes. The Superfaces algorithm performs the simplification
based on a bounded approximation criterion that produces a simplified
mesh that approximates the original one to within a pre-specified
tolerance. The vertices in the simplified mesh are a proper subset of
the original vertices, so the algorithm is well-suited for creating
hierarchical representations of polyhedra.
We have used the algorithm to simplify isosurfaces derived form medical
CT scans, molecular electron density volume data, and topographic data
of the earth.
},
KEYWORDS={mesh simplification, polyhedral approximation, data reduction},
NOTE={\URL{http://www.computer.org/pubs/cg&a/cg&a.htm}
has corrected figures},
}
@INPROCEEDINGS{Gueziec94spie,
AUTHOR={Andr\'e Gu\'eziec and David Dean},
TITLE={Wrapper: a surface optimization algorithm that preserves highly
curved areas},
BOOKTITLE={Visualization in Biomedical Computing},
PUBLISHER={SPIE},
VOLUME={2359},
MONTH={Oct.},
YEAR={1994},
PAGES={631--642},
ANNOTE={abstract from
\URL{http://www.spie.org/web/abstracts/2300/2359.html}
and \URL{http://www.cwru.edu:80/CWRU/Dept/Dent/orth/ortho/dean/wrapper.html}},
ABSTRACT={
Software to construct polygonal models of anatomical
structures embedded as isosurfaces in 3D medical images
has been available since the mid 1970s. Such models are
used for visualization, simulation, measurements
(single and multi-modality image registration), and
statistics. When working with standard MR- or CT-scans,
the surface obtained can contain several million
triangles. These models contain data an order of
magnitude larger than that which can be efficiently
handled by current workstations or transmitted through
networks. These algorithms generally ignore efficient
combinations that would produce fewer, well shaped
triangles. An efficient algorithm must not create a
larger data structure than present in the raw data.
Recently, much research has been done on the
simplification and optimization of surfaces ([Moore and
Warren, 1991]); [Schroeder et al., 1992]; [Turk, 1992];
[Hoppe et al., 1993]; [Kalvin and Taylor, 1994]). All
of these algorithms satisfy two criteria, consistency
and accuracy, to some degree. Consistent simplification
occurs via predictable patterns. Accuracy is measured
in terms of fidelity to the original surface, and is a
prerequisite for collecting reliable measurements from
the simplified surface. We describe the 'Wrapper'
algorithm that simplifies triangulated surfaces while
preserving the same topological characteristics. We
employ the same simplification operation in all cases.
However, simplification is restricted but not forbidden
in high curvature areas. This hierarchy of operations
results in homogeneous triangle aspect and size. Images
undergoing compression ratios between 10 and 20:1 are
visually identical to full resolution images. More
importantly, the metric accuracy of the simplified
surfaces appears to be unimpaired. Measurements based
upon 'ridge curves; (sensu [Cutting et al., 1993])
extracted on polygonal models were recently introduced
[Ayache et al., 1993]. We compared ridge curves
digitized from full resolution, Wrapper, and volume
subsampled CT-scan isosurfaces. [Dean, 1993] introduced
a method for measuring distances between space curves.
In the best case this method demonstrated that ridge
curves digitized from the Wrapper simplified images
were two orders of magnitude closer to the full
resolution image than those taken from the volume
subsampled images.
},
}
@INPROCEEDINGS{Gueziec95mrcas,
AUTHOR={Andr\'e Gu\'eziec},
TITLE={Surface Simplification with Variable Tolerance},
BOOKTITLE={Second Annual Intl. Symp. on
Medical Robotics and Computer Assisted Surgery (MRCAS '95)},
MONTH={November},
YEAR={1995},
PAGES={132--139},
KEYWORDS={edge collapse, medical imaging, curvature},
}
@ARTICLE{Gueziec95tvcg,
AUTHOR={Andr\'e Gu\'eziec and Robert Hummel},
TITLE={Exploiting Triangulated Surface Extraction Using
Tetrahedral Decomposition},
JOURNAL={IEEE Trans. on Visualization and Computer Graphics},
VOLUME={1},
NUMBER={4},
YEAR={1995},
PAGES={328--342},
KEYWORDS={
B-rep, boundary representation, Marching Cubes, tetrahedral
decomposition, homology theory, surface curvature, lossless surface
compression, surface simplification
},
ABSTRACT={
Beginning with digitized volumetric data, we wish to rapidly and
efficiently extract and represent surfaces defined as isosurfaces in
the interpolated data. The Marching Cubes algorithm is a standard
approach to this problem. We instead perform a decomposition of each
8-cell associated with a voxel into five tetrahedra. Following the
ideas of Kalvin et al. [18], Thirion and Gourdon [30], and extending
the work of Doi and Koide [5], we guarantee the resulting surface
representation to be closed and oriented, defined by a valid
triangulation of the surface of the body, which in turn is presented as
a collection of tetrahedra. The entire surface is "wrapped" by a
collection of triangles, which form a graph structure, and where each
triangle is contained within a single tetrahedron. The representation
is similar to the homology theory that uses simplices embedded in a
manifold to define a closed curve within each tetrahedron.
We introduce data structures based upon a new encoding of the
tetrahedra that are at least four times more compact than the standard
data structures using vertices and triangles. For parallel computing
and improved cache performance, the vertex information is stored local
to the tetrahedra. We can distribute the vertices in such a way that no
tetrahedron ever contains more than one vertex.
We give methods to evaluate surface curvatures and principal directions
at each vertex, whenever these quantities are defined. Finally, we
outline a method for simplifying the surface, that is reducing the
vertex count while preserving the geometry. We compare the
characteristics of our methods with an 8-cell based method, and show
results of surface extractions from CT-scans and MR-scans at full
resolution.
},
ANNOTE={abstract at \URL{http://www.computer.org/pubs/tvcg/tvcg.htm}},
}
@TECHREPORT{Gueziec96tr,
AUTHOR={Andr\'e Gu\'eziec},
TITLE={Surface Simplification Inside a Tolerance Volume},
NOTE={IBM Research Report RC 20440,
\URL{http://www.watson.ibm.com:8080/search_paper.shtml}},
MONTH={Mar.},
YEAR={1996},
INSTITUTION={Yorktown Heights, NY 10598},
ABSTRACT={
We present a technique for simplifying a triangulated surface, or
approximating the surface with another surface of lower triangle count.
The simplification preserves the volume of solids to within machine
accuracy. It favors the construction of near equilateral triangles. We
develop a novel method for accurately reporting the approximation error
between a simplified surface and the original, and respecting
prespecified error tolerances. Rather than a global error for the
entire surface, a positive error value is reported at each vertex. By
linearly blending the error values in between vertices, we define a
volume of space, which we call the error volume, as the union of
spheres of varying radii. The error volume is built dynamically as the
simplification progresses, on top of preexisting error volumes, that it
is required to contain, until it reaches the size of the tolerance
volume. To compute the error volume, we develop constraints on the
error values and minimize a measure of the error volume using linear
programming. To simplify the surface, surface edges respecting certain
geometrical and topological criteria are collapsed into a vertex. The
surrounding surface configuration is changed accordingly, resulting in
a new surface where three edges have been removed. As the error volume
contains all previous surface instances, only the current surface is
needed, and the position of collapsed vertices is safely discarded.
Since the vertex valences vary little, the complexity of the method is
subquadratic in the number of surface vertices, triangles or edges.
Accordingly, the method scales very well 199 from small to large
surfaces. We present results using data from medical imaging (180K
triangles) and the CAD model of a lamp.
},
}
@INPROCEEDINGS{Gourdon95,
AUTHOR={Alexis Gourdon},
TITLE={Simplification of Irregular Surface Meshes in {3D} Medical Images},
BOOKTITLE={Computer Vision, Virtual Reality, and Robotics in Medicine
(CVRMed '95)},
MONTH={Apr.},
YEAR={1995},
PAGES={413--419},
KEYWORDS={surface simplification},
}
@INPROCEEDINGS{Gross95,
TITLE={Fast Multiresolution Surface Meshing},
AUTHOR={Markus H. Gross and R. Gatti and O. Staadt},
MONTH={July},
YEAR={1995},
BOOKTITLE={Proc. IEEE Visualization '95},
KEYWORDS={surface meshing, polygonal approximations,
level of detail, quadtree, wavelet transform,
wavelet space filtering, biorthogonal wavelets,
mean-square error, digital terrain modeling},
ABSTRACT={
We present a new method for adaptive surface meshing
and triangulation which controls the local level-of-detail
of the surface approximation by local spectral estimates.
These estimates are determined by a wavelet representation of the
surface data. The basic idea is to decompose the initial
data set by means of an orthogonal or semi-orthogonal tensor
product wavelet transform (WT) and to analyze the resulting
coefficients. In surface regions, where the partial
energy of the resulting coefficients is low, the polygonal
approximation of the surface can be performed with larger
triangles without loosing too much fine grain details. However,
since the localization of the WT is bound by the Heisenberg
principle the meshing method has to be controlled by the detail
signals rather than directly by the coefficients. The dyadic
scaling of the WT stimulated us to build an hierarchical meshing
algorithm which transforms the initially regular data grid into a
quadtree representation by rejection of unimportant mesh vertices.
The optimum triangulation of the resulting quadtree cells is carried
out by selection from a look-up table. The tree grows recursively
as controlled by detail signals which are computed from a modified
inverse WT.
},
NOTE={(Also ETH Z\"urich CS tech report 230,
\URL{http://www.inf.ethz.ch/publications/tr.html})},
}
@INPROCEEDINGS{Renze95nsf,
AUTHOR={Kevin J. Renze and James H. Oliver},
TITLE={A Decimation Scheme for Unstructured Tessellated Domains},
BOOKTITLE={NSF Design, Manufacturing and Industrial Innovation
Grantees Conference},
ADDRESS={La Jolla, CA},
MONTH={Jan.},
YEAR={1995},
KEYWORDS={surface simplification, volume simplification, mesh generation},
ANNOTE={2 page summary},
}
@PHDTHESIS{Renze95phd,
AUTHOR={Kevin J. Renze},
TITLE={Unstructured Surface and Volume Decimation of Tessellated Domains},
SCHOOL={Dept. of Mech. Eng., Iowa State University, Ames, IA},
YEAR={1995},
KEYWORDS={surface simplification, volume simplification, mesh generation},
ANNOTE={(ISU call number: ISU 1995 ??)},
}
@INPROCEEDINGS{Renze96,
AUTHOR={Kevin J. Renze and James H. Oliver},
TITLE={Generalized Surface and Volume Decimation
for Unstructured Tessellated Domains},
BOOKTITLE={VRAIS '96 (IEEE Virtual Reality Annual Intl. Symp.)},
NOTE={submitted},
MONTH={Mar.},
YEAR={1996},
KEYWORDS={surface simplification, volume simplification, mesh generation},
}
@INPROCEEDINGS{Khan95,
AUTHOR={M. A. Khan and and Judy M. Vance},
TITLE={A Mesh Reduction Approach to Parametric Surface Polygonization},
BOOKTITLE={1995 ASME Design Automation Conf. Proc.},
ADDRESS={Boston, MA},
MONTH={Sept.},
YEAR={1995},
VOLUME={DE-82},
PAGES={41--48},
KEYWORDS={surface simplification, triangulation},
ANNOTE={
Proceedings of the 1995 ASME Design Engineering Technical Conferences:
Advances in Design Automation - 1995
},
}
@MISC{Grossebib,
AUTHOR={Eric Grosse},
TITLE={Bibliography of approximation algorithms},
NOTE={\URL{ftp://netlib.att.com/netlib/master/readme.html}, link=``catalog''},
}
@TECHREPORT{Schikore95,
TITLE={Decimation of {2D} Scalar Data with Error Control},
AUTHOR={D. Schikore and C. Bajaj},
INSTITUTION={CS Dept, Purdue U.},
NOTE={CSD-TR-95-005,
\URL{http://www.cs.purdue.edu/homes/drs/research.html}},
MONTH={Feb.},
YEAR={1995},
ABSTRACT={
Scientific applications frequently use dense scalar data defined over a
2D mesh. Often these meshes are created at a high density in order to
capture the high frequency components of sampled data or to ensure an
error bound in a physical simulation. We present an algorithm which
drastically reduces the number of triangle mesh elements required to
represent a mesh of scalar data values, while maintaining that errors
at each mesh point will not exceed a user-specified bound. The
algorithm deletes vertices and surrounding triangles of the mesh which
can be safely removed without violating the error constraint. The hole
which is left after removal of a vertex is retriangulated with the goal
of minimizing the error introduced into the mesh. Examples using
medical data demonstrate the utility of the decimation algorithm.
Suggested extensions show that the ideas set forth in this paper may be
applied to a wide range of more complex scientific data.
},
}
@ARTICLE{Kalik92,
AUTHOR={Kalik, K. and Wendland, W.},
YEAR={1992},
TITLE={The Approximation of Closed Manifolds by Triangulated Manifolds and the
Triangulation of Closed Manifolds},
JOURNAL={Computing},
VOLUME={47},
PAGES={255--275},
KEYWORDS={approximation theory, finite element method},
ANNOTE={wants to create mesh of curved, parametric triangular patches for
manifold, error analysis of triangulation, worried about acute angles},
}
@BOOK{Watson92,
AUTHOR={David F. Watson},
TITLE={Contouring: A Guide to the Analysis and Display of Spatial Data},
PUBLISHER={Pergamon Press},
ADDRESS={Oxford},
YEAR={1992},
keywords={contour, scattered data interpolation, reconstruction,
nonuniform sampling},
annote={practically oriented survey,
floppy contains BASIC code for 18 interpolation and
6 gradient estimation techniques},
}
@TECHREPORT{Alfeld88,
AUTHOR={Alfeld, Peter},
YEAR={1988},
TITLE={Scattered Data Interpolation in Three or More Variables},
INSTITUTION={Department of Mathematics, University of Utah},
}
@INCOLLECTION{Barnhill77,
AUTHOR={Barnhill, Robert E.},
YEAR={1977},
TITLE={Representation and Approximation of Surfaces},
PAGES={69--120},
BOOKTITLE={Mathematical Software III},
PUBLISHER={Academic Press},
}
@INCOLLECTION{Cheney86,
AUTHOR={Cheney, E. W.},
YEAR={1986},
TITLE={Algorithms for Approximation},
PAGES={67--80},
BOOKTITLE={Approximation Theory},
SERIES={Proceedings of Symposia in Applied Mathematics},
VOLUME={36},
EDITOR={de Boor, Carl},
PUBLISHER={AMS},
}
@INCOLLECTION{Franke87bib,
AUTHOR={Franke, Richard and Schumaker, Larry L.},
TITLE={A Bibliography of Multivariate Approximation},
PAGES={275--335},
BOOKTITLE={Topics in Multivariate Approximation},
YEAR={1987},
EDITOR={Chui, C. K. and Schumaker, L. L. and Utreras, F. I.},
PUBLISHER={Academic Press},
}
@INCOLLECTION{Sabin80contour,
AUTHOR={Sabin, M. A.},
YEAR={1980},
TITLE={Contouring: A Review of Methods for Scattered Data},
BOOKTITLE={Mathematical Methods in Computer Graphics and Design},
EDITOR={Brodlie, K. W.},
PUBLISHER={Academic Press},
}
@BOOK{Thisted88,
AUTHOR={Thisted, Ronald A.},
YEAR={1988},
TITLE={Elements of Statistical Computing: Numerical Computation},
PUBLISHER={Chapman and Hall, New York},
}
@INPROCEEDINGS{He95,
AUTHOR={Taosong He and L. Hong and A. Kaufman and A. Varshney and and S. Wang},
TITLE={Voxel-Based Object Simplification},
BOOKTITLE={Proc. Visualization '95},
PUBLISHER={IEEE Comput. Soc. Press},
YEAR={1995},
NOTE={\URL{http://www.cs.sunysb.edu/~taosong/taosong-papers.html}},
ABSTRACT={
We present a simple, robust, and practical method for object
simplification for applications where gradual elimination of high
frequency details is desired. This is accomplished by sampling and
low-pass filtering the object into multi-resolution volume buffers and
applying the marching cubes algorithm to generate a multi-resolution
triangle-mesh hierarchy. Our method simplifies the genus of an object
and can also help existing object simplification algorithms achieve
better results. At each level of detail a multi-layered mesh is
generated for optional efficient antialiased rendering.
},
}
@ARTICLE{Carter88,
AUTHOR={J. Carter},
TITLE={Digital representation of topographic surfaces},
JOURNAL={Photogrammetric Engineering and Remote Sensing},
YEAR={1988},
VOLUME={54},
NUMBER={11},
PAGES={1577--1580},
}
@INPROCEEDINGS{Fayek94,
AUTHOR={Reda E. Fayek and Andrew K.C. Wong},
TITLE={Triangular mesh model for natural terrain},
BOOKTITLE={Intelligent Robots \& Computer Vision XIII:
Algorithms \& Computer Vision},
PUBLISHER={SPIE},
ADDRESS={Boston, MA},
YEAR={1994},
PAGES={86--95},
NOTE={\URL{http://pami.uwaterloo.ca/~reda/publications.html}},
}
@INPROCEEDINGS{Fayek95,
AUTHOR={Reda E. Fayek and Andrew K.C. Wong},
TITLE={Hierarchical model for natural terrain using topographic
triangular meshes},
BOOKTITLE={Third IASTED Robotics \& Manufacturing},
ADDRESS={Cancun, Mexico},
YEAR={1995},
PAGES={252--255},
NOTE={\URL{http://pami.uwaterloo.ca/~reda/publications.html}},
}
@INPROCEEDINGS{Monga92,
AUTHOR={Olivier Monga and Serge Benayoun and Olivier Faugeras},
TITLE={Using Third Order Derivatives to Extract Ridge Lines in {3D} Images},
BOOKTITLE={Conference on Vision and Pattern Recognition},
MONTH={June},
YEAR={1992},
PUBLISHER={IEEE},
KEYWORDS={curvature, volume model},
}
@PHDTHESIS{Airey90,
AUTHOR={John M. Airey},
TITLE={Increasing Update Rates in the Building Walkthrough System with
Automatic Model-Space Subdivision and Potentially Visible Set Calculations},
SCHOOL={Dept. of CS, U. of North Carolina},
NOTE={TR90-027},
MONTH={July},
YEAR={1990},
KEYWORDS={visibility},
}
@TECHREPORT{Kang95,
AUTHOR={Sing Bing Kang and Andrew E. Johnson and Richard Szeliski},
TITLE={Extraction of Concise and Realistic 3-D Models from Real Data},
INSTITUTION={DEC Cambridge Research Lab},
NOTE={TR 95/7,
\URL{http://www.ius.cs.cmu.edu/usr/users/aej/www/research/modeling.html},
\URL{http://www.research.digital.com/CRL/projects/vision-graphics/scene-sensing.html}
},
MONTH={Oct.},
YEAR={1995},
KEYWORDS={surface simplification, computer vision, range data},
}
@ARTICLE{Peuquet84,
AUTHOR={Donna J. Peuquet},
TITLE={A Conceptual Framework and Comparison of Spatial Data Models},
JOURNAL={Cartographica},
VOLUME={21},
NUMBER={4},
YEAR={1984},
PAGES={66--113},
KEYWORDS={spatial data structure, survey, cartography},
}
@ARTICLE{Douglas86,
AUTHOR={David H. Douglas},
TITLE={Experiments to Locate Ridges and Channels to Create a New Type of
Digital Elevation Model},
JOURNAL={Cartographica},
VOLUME={23},
NUMBER={4},
YEAR={1986},
PAGES={29--61},
KEYWORDS={contour, interpolation, cartography},
}
@INPROCEEDINGS{Deering95,
AUTHOR={Michael Deering},
TITLE={Geometry Compression},
BOOKTITLE={SIGGRAPH '95 Proc.},
PUBLISHER={ACM},
MONTH={Aug.},
YEAR={1995},
PAGES={13--20},
keywords={hardware, triangle strip},
}
AUTHOR={Bernard Chazelle and David P. Dobkin and
Nadia Shouraboura and Ayellet Tal},
TITLE={Strategies for Polyhedral Surface Decomposition:
An Experimental Study},
BOOKTITLE={Proc. 11th Annual ACM Symp.
Computational Geometry},
MONTH={June},
YEAR={1995},
ANNOTE={
copy at UNC:
\URL{http://www.cs.unc.edu/~luebke/simplify/papers/convexDecomp.ps.gz}},
}
@ARTICLE{Ning93,
AUTHOR={Paul Ning and Jules Bloomenthal},
TITLE={An Evaluation of Implicit Surface Tilers},
JOURNAL={Computer Graphics and Applications},
MONTH={Nov.},
YEAR={1993},
PAGES={33--41},
keywords={polygonization, marching cubes},
}
@ARTICLE{Bloomenthal88,
AUTHOR={Jules Bloomenthal},
TITLE={Polygonization of Implicit Surfaces},
JOURNAL={Computer Aided Geometric Design},
VOLUME={5},
YEAR={1988},
PAGES={341--355},
keywords={implicit, parametric, surface, blob, adaptive subdivision, octree},
}
@PHDTHESIS{Catmull74,
AUTHOR={Edwin E. Catmull},
TITLE={A Subdivision Algorithm for Computer Display of Curved Surfaces},
SCHOOL={Dept. of CS, U. of Utah},
MONTH={Dec.},
YEAR={1974},
KEYWORDS={bicubic surface, B-spline, adaptive subdivision, z-buffer,
texture mapping},
}
@INPROCEEDINGS{Waldron95,
AUTHOR={Shayne Waldron},
TITLE={The error in linear interpolation at the vertices of a simplex},
BOOKTITLE={Southeastern-Atlantic Section of SIAM annual meeting},
MONTH={Mar.},
YEAR={1995},
NOTE={Charleston, SC,
\URL{http://www.math.auckland.ac.nz/~waldron/Mypapers/preprints.html}},
ABSTRACT={
A new formula for the error in a map which interpolates to function
values at some set $\gTh\subset\Rn$ from a space of functions which
contains the linear polynomials is given. From it {\it sharp} pointwise
$L_\infty$-bounds for the error in linear interpolation (interpolation
by linear polynomials) to (function values at) the vertices of a
simplex are obtained.
This error formula reflects the geometry in a particularly appealing
way. The error at $x$ not lying on any line connecting points in $\gTh$
is the sum over distinct points $v,w\in\gTh$ of $1/2$ the average of
the second order derivative $D_{v-w}D_{w-v}f$ over the triangle with
vertices $x,v,w$ % $\conv[x,v,w]$ multiplied by some function which
vanishes at all of the points in $\gTh$.
},
KEYWORDS={
Lagrange interpolation, linear interpolation on a triangle, sharp error
bounds, finite elements, multi-point Taylor formula},
}
@TECHREPORT{Taubin96,
AUTHOR={Gabriel Taubin and Jarek Rossignac},
TITLE={Geometric Compression through Topological Surgery},
NOTE={IBM Research Report RC 20340,
\URL{http://www.watson.ibm.com:8080/search_paper.shtml}},
MONTH={Jan.},
YEAR={1996},
INSTITUTION={Yorktown Heights, NY 10598},
KEYWORDS={triangulation},
ABSTRACT={
In this paper we introduce a new compressed representation for
polyhedral models and associated compression and decompression
algorithms. Such a compressed representation significantly reduces the
time required to transmit the model over digital communication
channels, and the amount of space required to store the model. In our
compression scheme a triangulated polyhedron is represented by two
interlocked trees, a spanning trees of vertices, and a spanning tree
of triangles. The connectivity information represented in other
compact schemes, such as triangular strips or generalized triangular
meshes, can be efficiently derived from our representation. The
algorithms described in the paper compress connectivity information to
an average of roughly two bits per triangle. A variable length lossy
compression technique is used for vertex positions, normals, colors,
and texture mappings.
},
}
@TECHREPORT{Cignoni96,
AUTHOR={P. Cignoni, C. Rocchini and R. Scopigno},
TITLE={Metro: measuring error on simplified surfaces},
INSTITUTION={Istituto I.E.I.-C.N.R., Pisa, Italy},
MONTH={Jan.},
YEAR={1996},
NOTE={Technical Report B4-01-01-96,
\URL{http://miles.cnuce.cnr.it/cg/metro.img.html}},
KEYWORDS={surface simplification},
ABSTRACT={
This paper presents a new tool, Metro, designed to compensate for a
deficiency in most of the simplification methods proposed in
literature. Metro allows one to compare the difference between
surfaces (e.g. a triangulated mesh and its decimated representation),
by adopting an approximated approach. It returns both numerical
results and error magnitude visualization.
},
}
@InProceedings{Soucy91ece,
author={Marc Soucy and Denis Laurendeau},
title={Hierarchical Surface Triangulation of Range Data},
booktitle={Proc. of the Canadian Conf. on Electrical and Computer Engineering},
pages={4.4.1--4.4.4},
month={Sept.},
year={1991},
keywords={surface simplification, range data,
constrained Delaunay triangulation},
ANNOTE={for one range image, doing triangulation in 2-D projection,
has details on data structures},
}
@InProceedings{Soucy92icra,
author={Marc Soucy and Alain Croteau and Denis Laurendeau},
title={A multi-resolution surface model for compact representation of
range images},
booktitle={Intl. Conf. on Robotics and Automation},
pages={1701--1706},
month=may,
year={1992},
keywords={surface simplification, range data,
constrained Delaunay triangulation, computer vision},
ANNOTE={for one range image, but does Lawson LOP in 3-D},
}
@InProceedings{Soucy92icpr,
author={Marc Soucy and Denis Laurendeau},
title={Surface Modeling from Dynamic Integration of Multiple Range Views},
booktitle={Proc. 11th Intl. Conf. on Pattern Recognition},
year={1992},
pages={449--452},
keywords={computer vision, range data, zipper},
ANNOTE={nothing on surface simplification},
}
@InProceedings{Soucy92cvpr,
author={Marc Soucy and Denis Laurendeau},
title={Multi-resolution surface modeling from multiple range views},
booktitle={Conf. on Computer Vision and Pattern Recognition (CVPR '92)},
pages={348--353},
month=jun,
year={1992},
keywords={surface simplification, range data, zipper,
constrained Delaunay triangulation},
ANNOTE={for multiple range images, does Lawson LOP in 3-D},
}
@ARTICLE{Soucy95mva,
author={Marc Soucy and Denis Laurendeau},
title={A dynamic integration algorithm to model surfaces from
multiple range views},
journal={Machine Vision and Applications},
volume={8},
number={1},
year={1995},
pages={53--62},
keywords={computer vision, range data, zipper},
ANNOTE={nothing on surface simplification},
}
@ARTICLE{Soucy96cviu,
author={Marc Soucy and Denis Laurendeau},
title={Multiresolution Surface Modeling Based on Hierarchical Triangulation},
journal={Computer Vision and Image Understanding},
volume={63},
number={1},
pages={1--14},
year={1996},
keywords={surface simplification, range data,
constrained Delaunay triangulation},
ANNOTE={more detail than Soucy92cvpr,
contains curvature maximization & discontinuity preservation
discussions, conditions for retriangulation, pseudocode for simplification
algorithm, special handling of contour vertices, complexity analysis},
}
@INPROCEEDINGS{Koh94,
AUTHOR={E. Koh and D. Metaxas and N. Badler},
TITLE={Hierarchical Shape Representation Using Locally
Adaptive Finite Elements},
BOOKTITLE={Proc. ECCV '94},
YEAR={1994},
PAGES={441--446},
KEYWORDS={adaptive mesh, deformable model, surface fitting},
}
@INPROCEEDINGS{Metaxas93gmcv,
AUTHOR={D. Metaxas and E. Koh},
TITLE={Efficient shape representation using deformable models
with locally adaptive finite elements},
BOOKTITLE={Geometric Methods in Computer Vision II},
EDITOR={B.C. Vemuri},
PUBLISHER={SPIE},
VOLUME={2031},
MONTH={July},
YEAR={1993},
PAGES={160--171},
KEYWORDS={adaptive mesh, surface fitting},
}
@ARTICLE{Venkatakrishnan96aiaa,
AUTHOR={V. Venkatakrishnan},
TITLE={Perspective on Unstructured Grid Flow Solvers},
JOURNAL={AIAA Journal},
VOLUME=34,
NUMBER=3,
PAGES={533--547},
MONTH={March},
YEAR={1996},
KEYWORDS={computational fluid dynamics, finite element method,
multigrid},
}
@ARTICLE{Ronfard96,
TITLE={Full-range approximation of triangulated polyhedra},
AUTHOR={R\'emi Ronfard and Jarek Rossignac},
JOURNAL={Computer Graphics Forum},
NOTE={Proc. Eurographics '96},
VOLUME=15,
NUMBER=3,
MONTH={Aug.},
YEAR={1996},
KEYWORDS={surface simplification},
}
@ARTICLE{Algorri96,
TITLE={Mesh Simplification},
AUTHOR={M.-E. Algorri and F. Schmitt??},
JOURNAL={Computer Graphics Forum},
NOTE={Proc. Eurographics '96},
VOLUME=15,
NUMBER=3,
MONTH={Aug.},
YEAR={1996},
KEYWORDS={surface simplification},
}
@ARTICLE{Andujar96,
TITLE={Automatic Generation of Multiresolution Boundary Representations},
AUTHOR={C. Andujar and D. Ayala and P. Brunet and R. Joan-Arinyo and J. Sole},
JOURNAL={Computer Graphics Forum},
NOTE={Proc. Eurographics '96},
VOLUME=15,
NUMBER=3,
MONTH={Aug.},
YEAR={1996},
}
@BOOK{Buttenfield91,
EDITOR={Barbara P. Buttenfield and Robert M. McMaster},
TITLE={Map Generalization: Making Rules for Knowledge Representation},
PUBLISHER={John Wiley \& Sons},
YEAR={1991},
ANNOTE={abstract at \URL{http://www.gisworld.com/book/Cart_Map.html},
emphasis on rules, AI, maps; almost nothing on DEMs},
}
@BOOK{Muller??,
EDITOR={Muller and Lagrange and Weibel},
TITLE={GIS and Generalization: Methodology and Practice},
YEAR={??},
ANNOTE={abstract at \URL{http://www.gisworld.com/book/Gen_GIS.html}},
}
@BOOK{Okabe92,
EDITOR={Atsuyuki Okabe and Barry Boots and Kokichki Sugihara},
TITLE={Spatial Tessellations:
Concepts and Applications of {Voronoi} Diagrams},
PUBLISHER={John Wiley \& Sons},
YEAR={1992},
ANNOTE={abstract at \URL{http://www.gisworld.com/book/Data_Bases.html}},
}
@INPROCEEDINGS{Deveau85,
AUTHOR={Terry J. Deveau},
TITLE={Reducing the Number of Points in a Plane Curve Representation},
BOOKTITLE={Proc. of Auto-Carto 7
(Seventh Intl. Symp. on Computer-Assisted Cartography)},
ADDRESS={Baltimore, MD},
PUBLISHER={American Congress of Surveying and Mapping},
YEAR={1985},
PAGES={152--160},
KEYWORDS={curve simplification},
ANNOTE={compares his/her Tomek-like algorithm with Douglas-Peucker and
Dettori-Falcidieno},
}
@ARTICLE{Dettori82,
AUTHOR={G. Dettori and B. Falcidieno},
TITLE={An Algorithm for Selecting Main Points on a Line},
JOURNAL={Computers and Geosciences},
VOLUME=8,
NUMBER=1,
YEAR=1982,
PAGES={3--10},
KEYWORDS={curve simplification},
ANNOTE={uses convex hull, slow?, see Deveau85},
}
@ARTICLE{Watson81,
AUTHOR={D. F. Watson},
TITLE={Computing the n-dimensional {Delaunay} tessellation with
application to {Voronoi} polytopes},
JOURNAL={Computer J.},
VOLUME={24},
NUMBER={2},
YEAR={1981},
PAGES={167--172},
keywords={incremental Delaunay triangulation},
}
@ARTICLE{Bowyer81,
AUTHOR={A. Bowyer},
TITLE={Computing Dirichlet Tessellations},
JOURNAL={Computer J.},
VOLUME={24},
NUMBER={2},
YEAR={1981},
PAGES={162--166},
keywords={Voronoi, incremental Delaunay triangulation, n-dimensional},
}
@ARTICLE{Borouchaki95,
AUTHOR={Houman Borouchaki and S. H. Lo},
TITLE={Fast Delaunay Triangulation in Three Dimensions},
JOURNAL={Computer Meth. in Applied Mechanics \& Eng.},
VOLUME=128,
YEAR=1995,
PAGES={153--167},
KEYWORDS={point location, Voronoi diagram, circumsphere, optimization},
ANNOTE={walking method for point location can loop, fast incremental
computation of circumcenter},
}
@ARTICLE{Cromley91,
AUTHOR={Robert G. Cromley},
TITLE={Hierarchical Methods of Line Simplification},
JOURNAL={Cartography and Geographic Information Systems},
VOLUME=18,
NUMBER=2,
YEAR=1991,
PAGES={125--131},
KEYWORDS={curve simplification},
ANNOTE={like Ballard and Douglas-Peucker, but retains subdivision tree},
}
@INPROCEEDINGS{Mucke96locate,
AUTHOR={Ernst P. M\"ucke and Isaac Saias and Binhai Zhu},
TITLE={Fast Randomized Point Location Without Preprocessing
in Two-and Three-Dimensional {Delaunay} Triangulations},
BOOKTITLE={12th ACM Symp. on Computational Geometry},
MONTH={May},
YEAR=1996,
NOTE={\URL{ftp://ftp.cfar.umd.edu/TRs/CVL-Reports-1996/TR3621-Mucke.ps.gz}},
ANNOTE={Green-Sibson walking method},
}
@TECHREPORT{Chappuis96,
AUTHOR={Eric Chappuis},
TITLE={Initialisation of 3-D Shape Parameters of 3-D Model Objects},
INSTITUTION={Departement Communications Multimedia,
Institut EURECOM},
MONTH={July},
YEAR=1996,
KEYWORDS={computer vision, range data},
NOTE={\URL{http://www.eurecom.fr/~chappuis/rapport/rapport.html}},
}
@BOOK{Hearnshaw94,
TITLE={Visualization in Geographical Information Systems},
EDITOR={Hilary M. Hearnshaw and David J. Unwin},
PUBLISHER={Wiley \& Sons},
ADDRESS={Chichester, UK},
YEAR={1994},
ANNOTE={Workshop, University of Loughborough, UK, summer 1992},
}
@TechReport{Luebke96,
author = "David Luebke",
title = "Hierarchical structures for dynamic
polygonal simplification",
institution = "Department of Computer Science, University of North
Carolina at Chapel Hill",
year = "1996",
type = "TR",
number = "96-006",
}
@Article{Bajaj96reduc,
author = "Chandrajit Bajaj and Daniel Schikore",
title = "Error-bounded reduction of triangle meshes with
multivariate data",
journal = "SPIE",
volume = "2656",
pages = "34--45",
year = "1996",
}
@InProceedings{Schaufler95,
author = "G. Schaufler and W. St{\"u}rzlinger",
title = "Generating multiple levels of detail from polygonal
geometry models",
booktitle = "Virtual Environments '95 (Eurographics Workshop)",
editor = "M. G{\"o}bel",
pages = "33--41",
publisher = "Springer Verlag",
month = "January",
year = "1995",
}
@InProceedings{Cohen96,
author = "Jonathan Cohen and Amitabh Varshney and Dinesh
Manocha and Greg Turk and Hans Weber and Pankaj
Agarwal and Frederick Brooks and William Wright",
title = "Simplification Envelopes",
pages = "119--128",
booktitle = "SIGGRAPH '96 Proc.",
year = 1996,
month = "Aug.",
keywords = "hierarchical approximation, model simplification,
levels-of-detail generation, shape approximation,
geometric modeling, offsets",
note = "\URL{http://www.cs.unc.edu/~geom/envelope.html}"
}
@TECHREPORT{deBerg95simp
, author = "M. de Berg and M. van Kreveld and S. Schirra"
, title = "A new approach to subdivision simplification"
, institution = "CS Dept, Utrecht U."
, year = 1995
, NOTE={UU-CS-1995-26,
\URL{http://www.cs.ruu.nl/docs/research/publication/TechList2.html}}
, KEYWORDS={curve simplification, computational geometry, cartography}
}
@TECHREPORT{vanKreveld94isoline
, author = "Marc van Kreveld"
, title = "Efficient methods for isoline extraction from a
digital elevation model based on triangulated irregular networks"
, institution = "CS Dept, Utrecht U."
, year = 1994
, NOTE={UU-CS-1994-21,
\URL{http://www.cs.ruu.nl/docs/research/publication/TechList2.html}}
, KEYWORDS={contour map, computational geometry, interval tree, cartography}
}
@TECHREPORT{deBerg96traverse
, author = "Mark de Berg and Marc van Kreveld and Ren\'e van Oostrum
and Mark Overmars"
, title = "Simple traversal of a subdivision without extra storage"
, institution = "CS Dept, Utrecht U."
, year = 1996
, NOTE={UU-CS-1996-17
\URL{http://www.cs.ruu.nl/docs/research/publication/TechList2.html}}
, KEYWORDS={contour map, computational geometry, interval tree, cartography}
, ANNOTE={traversing a planar subdivision without mark bits}
}