% 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 work in:
% * 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/
%
% Paul S. Heckbert - http://www.cs.cmu.edu/~ph
% and Michael Garland - http://www.cs.cmu.edu/~garland
% $Revision: 4.8$
% 28 Oct 1997
%
% 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 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 bibtex but before the last two runs of latex,
% 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
% ----------------------
@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",
}
@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{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",
}
@Article{Chew89,
author = "L. Paul Chew",
title = "Constrained {Delaunay} Triangulations",
journal = "Algorithmica",
year = "1989",
volume = "4",
pages = "97--108",
}
@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",
}
@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{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 = jan,
}
@Article{d-fecld-81,
author = "G. Dutton",
title = "Fractal enhancement of cartographic line detail",
journal = "The American Cartographer",
volume = "8",
year = "1981",
pages = "23--40",
keywords = "implementing algorithms, computer graphics,
cartography, algebraic geometry, fractals,
construction, similarity, shape, boundary
representation, curves",
}
@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",
}
@InProceedings{dm-epigd-80,
author = "G. Dutton and S. Morehouse",
title = "Extraction of polygonal information from gridded
data",
booktitle = "Proc. 4th Internat. Sympos. Comput.-Assist. Cartog.
(Auto-Carto)",
address = "Falls Church, VA",
year = "1980",
pages = "320--327",
keywords = "implementing algorithms, image processing,
cartography, construction, shape, contours, polygonal
chains, topological, curves",
update = "93.05 freimer",
}
@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 = sep,
year = "1995",
note = "CMU-CS-95-181,
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 = "very short version of Garland95tr",
}
@Article{Garland9x,
author = "Michael Garland and Paul S. Heckbert",
title = "Fast Triangular 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",
}
@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{Hanrahan91,
author = "Pat Hanrahan and David Salzman and Larry Aupperle",
title = "A Rapid Hierarchical Radiosity Algorithm",
month = jul,
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",
}
@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",
}
@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 = "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 = "http://www.cs.cmu.edu/~ph",
keywords = "height field, manifold, non-manifold, triangulation,
mesh, decimation, refinement, multiresolution
modeling",
}
@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, http://www.cs.ubc.ca/tr/1992/TR-92-07,
code at
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 = apr,
year = "1992",
keywords = "simplification, approximation, curve, computational
geometry, convex hull",
note = "TR-92-07, http://www.cs.ubc.ca/tr/1992/TR-92-07,
code at
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{Hughes91,
author = "Peter Hughes",
title = "Building a Terrain Renderer",
journal = "Computers in Physics",
year = "1991",
pages = "434--437",
month = jul # "/" # aug,
annote = "describes pyramid techniques used to create {"}Mars
Navigator{"} interactive videodisk",
}
@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.",
}
@TechReport{Johnson97tr,
author = "Andrew Johnson and Martial Hebert",
title = "Control of Polygonal Mesh Resolution for 3-{D} Cmputer
Vision",
institution = "Robotics Institute, Carnegie Mellon U.",
month = feb,
year = "1997",
note = "CMU-RI-TR-96-20,
http://www.ius.cs.cmu.edu/IUS/clash_usr0/aej/www/papers/TR-96-20.ps.gz",
annote = "may also appear at
http://www.cs.cmu.edu/Reports/robotics.html at a
later date",
keywords = "surface simplification, edge collapse, uniform
sampling",
}
@Article{Kajiya85,
author = "James T. Kajiya",
title = "Anisotropic Reflection Models",
journal = "Computer Graphics (SIGGRAPH '85 Proc.)",
volume = "19",
number = "3",
month = jul,
year = "1985",
pages = "15--21",
keywords = "texture mapping, level of detail",
annote = "frame mapping",
}
@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{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 = jul,
}
@InProceedings{McDonald97forest,
author = "Timothy P. McDonald",
title = "A System for Drawing Synthetic Images of Forested
Landscapes",
booktitle = "? conference",
month = feb,
year = "1997",
note = "See
http://so4702.usfs.auburn.edu/research/prob4/standviews.html
for pictures",
keywords = "triangulated irregular network, tree, forestry,
clearcut",
}
@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",
}
@InProceedings{Pajon95a,
author = "J. L. Pajon and Y. Collenot and X. Lhomme and N.
Tsingos and F. Sillion and P. Guilloteau and P.
Vuyslteker and G. Grillon and D. David",
title = "Building and Exploiting Levels of Detail: An Overview
and Some {VRML} Experiments",
booktitle = "VRML '95, First Annual Symposium on the Virtual
Reality Modeling Language",
conferenceurl = "http://rosebud.sdsc.edu/Events/vrml95/",
year = "1995",
month = dec,
pages = "117--122",
}
@InProceedings{Perlin84,
author = "Ken Perlin",
title = "A Unified Texture/Reflectance Model",
booktitle = "SIGGRAPH '84 Advanced Image Synthesis seminar notes",
month = jul,
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 = jul,
year = "1985",
keywords = "antialiasing, filter, blur",
annote = "generalizing Crow's summed-area tables to higher order
filter kernels",
}
@Article{Polis92iuw,
author = "M. F. Polis and D. M. McKeown Jr.",
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 = "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 = nov,
pages = "267--277",
note = "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 = jul,
year = "1995",
pages = "57--65",
keywords = "simulator, terrain, cartography",
note = "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.",
}
@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{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 = mar,
}
@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{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 = jul,
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 = jul,
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 http://www.cs.rpi.edu:80/~martink/",
annote = "includes triangulated mesh decimation software,
marching cubes",
}
@InProceedings{Snoeyink97strip,
author = "Jack Snoeyink and Bettina Speckmann",
title = "Easy triangle strips for {TIN} terrain models",
booktitle = "Ninth Canadian Conference on Computational Geometry",
year = "1997",
keywords = "terrain, triangulation",
}
@Book{Spivak79,
keyword = "differential geometry",
author = "Michael Spivak",
title = "A Comprehensive Introduction to Differential
Geometry",
publisher = "Publish or Perish, Inc.",
year = "1979",
}
@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 = jul,
keywords = "model simplification, automatic mesh generation,
constrained triangulation, levels-of-detail, shape
interpolation",
}
@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",
}
@InProceedings{Wiley97bsp,
title = "Multiresolution {BSP} trees applied to terrain,
transparency, and general objects",
author = "Charles Wiley and III A. T. Campbell and Stephen
Szygenda and Donald Fussell and Fred Hudson",
booktitle = "Graphics Interface",
year = "1997",
month = may,
pages = "88--96",
note = "http://www.dgp.toronto.edu/gi/gi97/proceedings/papers/WCSFH/",
}
@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 = jul,
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 = jun,
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 = jul,
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 = jul,
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 = jun,
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 = jul,
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 = oct,
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 = jun,
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,
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 = jul,
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",
}
% Less verbose version for tight situations
@InProceedings{Rossignac93B,
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",
year = "1993",
pages = "455--465",
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,
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,
http://www.research.ibm.com/xw-p4205-rc19638.html",
}
@Misc{IBM95ia,
author = "IBM",
title = "{IBM 3D Interaction Accelerator}",
year = "1995",
note = "Commercial software,
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 = nov,
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 = jul,
year = "1991",
journal = "Computer Graphics (SIGGRAPH '91 Proc.)",
volume = "25",
number = "4",
pages = "51--60",
keywords = "mesh generation",
}
@InCollection{Garlick90,
author = "B. Garlick and D. Baum and J. Winget",
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",
note = "http://www.cc.gatech.edu/gvu/people/Phd/Charles.Patterson/research/gsii/gsii.html",
annote = "multiresolution model creation (clustering) not fully
automated",
}
@Article{Gortler93wave,
author = "Steven J. Gortler and Peter Schr{\"o}der and Michael
F. Cohen and Pat Hanrahan",
title = "Wavelet Radiosity",
journal = "Computer Graphics (SIGGRAPH '93 Proc.)",
month = aug,
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",
}
@Article{Sudarsky96,
author = "Oded Sudarsky and Craig Gotsman",
title = "Output-Sensitive Visibility Algorithms for Dynamic
Scenes with Applications to Virtual Reality",
journal = "Computer Graphics Forum",
note = "Proc. Eurographics '96",
volume = "15",
number = "3",
month = aug,
year = "1996",
keywords = "z-buffer pyramid, lazy evaluation",
}
@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 = jun,
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,
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",
}
@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 = jun,
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,
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 = "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 = "ftp://ftp.disi.unige.it/pub/puppo/PS/issv95.ps.Z",
annote = "Also available from Pisa:
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 = jul,
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 = jul,
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 Comput. 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 " # jul,
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 = mar,
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 = jun,
}
@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 = "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 = "ftp://ftp.disi.unige.it/person/MarzanoP/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 = nov,
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, terrain, surface
approximation",
}
@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",
keywords = "surface approximation, terrain",
}
@InProceedings{Hinker93,
author = "Paul Hinker and Charles Hansen",
title = "Geometric Optimization",
booktitle = "Proc. Visualization '93",
month = oct,
year = "1993",
address = "San Jose, CA",
pages = "189--195",
keywords = "surface simplification",
note = "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,
http://www.cs.washington.edu/research/projects/grail2/www/pub/pub-author.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 = "http://www.cs.washington.edu/research/projects/grail2/www/pub/pub-author.html",
}
@Article{Lounsbery97,
author = "Michael Lounsbery and Tony D. DeRose and Joe Warren",
title = "Multiresolution Analysis for Surfaces of Arbitrary
Topological Type",
keywords = "surface, wavelet",
journal = "ACM Trans. on Graphics",
volume = "16",
number = "1",
pages = "34--73",
note = "http://www.cs.washington.edu/research/projects/grail2/www/pub/pub-author.html",
annote = "submitted in 1995",
}
@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 = "http://www.cs.washington.edu/research/projects/grail2/www/pub/pub-author.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",
note = "http://research.microsoft.com/~hoppe/",
}
@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 = "http://research.microsoft.com/~hoppe/",
}
@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 = jul,
pages = "295--302",
keywords = "subdivision surface, curved surface fitting",
note = "http://research.microsoft.com/~hoppe/",
}
@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 = "http://research.microsoft.com/~hoppe/",
}
@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 = "http://research.microsoft.com/~hoppe/",
}
@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 = jun,
year = "1995",
address = "Vancouver, B.C.",
keywords = "multiresolution, Delaunay triangulation",
note = "Also available as Utrecht University tech report
UU-CS-1995-12,
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{Lawson84sphere,
author = "C. L. Lawson",
title = "${C}^1$ Surface Interpolation For Scattered Data on a
Sphere",
journal = "Rocky Mountain Journal of Mathematics",
pages = "177--202",
year = "1984",
volume = "14",
number = "1",
keywords = "triangulation, sphere, c1",
annote = "Triangulates sphere using incremental algorithm with
switching. Switching rule is to make the quadrilateral
convex with respect to the sphere.",
}
@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",
}
@Book{Lawson95,
author = "C. L. Lawson and R. J. Hanson",
year = "1995",
title = "Solving Least Squares Problems",
series = "Classics in Applied Mathematics",
publisher = "SIAM",
address = "Philadelphia",
keywords = "survey, fitting",
}
@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,
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",
}
@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
http://www.gisworld.com/book/Cart_Map.html,
chapter on line generalization",
}
@Misc{ESRIInc,
author = "Environmental Systems Research Institute, Inc.
(ESRI)",
title = "Arc/Info geographic information system software",
note = "http://www.esri.com",
keywords = "surface approximation, cartography",
annote = "system for PC's. One of its commands, latticetin, is a
hybrid feature/refinement height field approximation
algorithm.
http://www.esri.com/resources/papers/papers.html#LISTAI",
}
@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 {TIN}s and {DEM}s",
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{\"u}rich",
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 = mar,
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 = sep,
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 = jul # "-" # sep,
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",
}
@InCollection{Hamann93curv,
author = "Bernd Hamann",
title = "Curvature Approximation for Triangulated Surfaces",
booktitle = "Geometric Modelling",
editor = "G. Farin and others",
series = "Computing Supplementum 8",
publisher = "Springer-Verlag",
year = "1993",
pages = "139--153",
keywords = "surface simplification",
annote = "presentation at: {"}First Dagstuhl Seminar on
Geometric Modelling,{"} Dagstuhl, Germany, July 1991.",
}
@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 = jun,
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 = jul,
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{Franklin93tinc,
author = "W. Randolph Franklin",
title = "tin.c",
institution = "Rensselaer Polytechnic Inst.",
note = "C code,
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",
}
@InCollection{Franklin96elev,
author = "W. Randolph Franklin",
title = "Elevation Data Operations",
booktitle = "Computational Cartography Seminar?",
address = "Dagstuhl",
month = nov,
year = "1996",
note = "ftp://ftp.cs.rpi.edu/pub/franklin/dagstuhl.ps.gz",
keywords = "terrain, surface simplification, TIN, compression,
visibility",
}
@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{\"o}nnimann 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{\"o}nnimann",
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 = jul,
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 = "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,
ftp://ftp.cs.duke.edu/dist/techreport/1994/1994-21.ps.Z)",
}
@TechReport{Agarwal94tr,
author = "Pankaj K. {Agarwal} and Subhash Suri.",
year = "1994",
location = "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,
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 = jun,
year = "1994",
note = "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,
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
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 " # jul,
year = "1990",
address = "Z{\"u}rich",
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,
http://gams.nist.gov/acmd/Staff/JBernal/index.html",
month = apr,
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 = "Brian Von Herzen and Alan H. Barr",
title = "Accurate Triangulations of Deformed, Intersecting
Surfaces",
journal = "Computer Graphics (SIGGRAPH '87 Proceedings)",
volume = "21",
number = "4",
month = jul,
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,
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 = jun,
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 = jun,
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 = jun,
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 = jul,
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 = jun,
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 = jun,
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 = "Eduardo F. D'Azevedo and R. Bruce 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 = "Eduardo 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 = "Eduardo F. D'Azevedo",
title = "Optimal triangular mesh generation by coordinate
transformation",
journal = "SIAM J. Sci. Stat. Comput.",
volume = "12",
number = "4",
month = jul,
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 = "Eduardo F. D'Azevedo and R. Bruce 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{\"o}rg Gottschalk",
title = "Die Generalisierung von Isolinien als Ergebnis der
Generalisierung von Fl{\"a}schen",
journal = "Zeitschrift f{\"u}r 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 Russell 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 = "http://www.computer.org/pubs/cg&a/articles/g30064.pdf",
annote = "Online version 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
http://www.spie.org/web/abstracts/2300/2359.html
and
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 = nov,
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
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,
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 = jul,
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{\"u}rich CS tech report 230,
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 = sep,
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 = "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,
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 = "K. Kalik and W. Wendland",
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 = "Peter Alfeld",
year = "1988",
title = "Scattered Data Interpolation in Three or More
Variables",
institution = "Department of Mathematics, University of Utah",
}
@InCollection{Barnhill77,
author = "Robert E. Barnhill",
year = "1977",
title = "Representation and Approximation of Surfaces",
pages = "69--120",
booktitle = "Mathematical Software III",
publisher = "Academic Press",
}
@InCollection{Cheney86,
author = "E. W. Cheney",
year = "1986",
title = "Algorithms for Approximation",
pages = "67--80",
booktitle = "Approximation Theory",
series = "Proceedings of Symposia in Applied Mathematics",
volume = "36",
editor = "Carl de Boor",
publisher = "AMS",
}
@Article{Franke82sdi,
author = "Richard Franke",
title = "Scattered Data Interpolation: Tests of Some Methods",
journal = "Mathematics of Computation",
volume = "38",
number = "157",
month = jan,
year = "1982",
pages = "181--200",
keywords = "surface fitting, surface approximation",
abstract = "This paper is concerned with the evaluation of methods
for scattered data interpolation and some of the
results of the tests when applied to a number of
different methods. The process involves evaluation of
the methods in terms of timing, storage, accuracy,
visual pleasantness of the surface, and ease of
implementation. To indicate the flavor of the type of
results obtained, we give a summary table and
representative perspective plots of several surfaces.",
annote = "Empirical comparison of 32 global & local scattered
data interp algs. Summary of his 370 page Naval
Postgraduate School technical report.",
}
@InCollection{Franke87sda,
author = "Richard Franke",
title = "Recent advances in the approximation of surfaces from
scattered data",
booktitle = "Topics in Multivariate Approximation",
publisher = "Academic Press",
address = "New York",
year = "1987",
editor = "C. K. Chui and L. L. Schumaker and F. I. Utreras",
pages = "79--98",
keywords = "multiquadric interpolation, subset selection",
}
@InCollection{Franke87bib,
author = "Richard Franke and Larry L. Schumaker",
title = "A Bibliography of Multivariate Approximation",
pages = "275--335",
booktitle = "Topics in Multivariate Approximation",
year = "1987",
editor = "C. K. Chui and L. L. Schumaker and F. I. Utreras",
publisher = "Academic Press",
}
@InCollection{Franke91sdi,
author = "Richard Franke and Gregory M. Nielson",
title = "Scattered data interpolation and applications: a
tutorial and survey",
booktitle = "Geometric modelling: methods and applications",
editor = "H. Hagen and D. Roller",
publisher = "Springer-Verlag",
year = "1991",
pages = "131--160",
}
@InCollection{Schumaker76fit,
author = "Larry L. Schumaker",
title = "Fitting Surfaces to Scattered Data",
booktitle = "Approximation Theory II",
editor = "G. G. Lorentz and others",
publisher = "Academic Press",
year = "1976",
pages = "203--268",
keywords = "surface fitting, surface approximation, thin plate
spline",
note = "good survey of scattered data interpolation and
approximation, both global and local methods",
}
@Article{Schumaker93sa,
author = "Larry L. Schumaker",
title = "Computing Optimal Triangulations Using Simulated
Annealing",
journal = "Computer Aided Geometric Design",
volume = "10",
number = "3--4",
month = aug,
year = "1993",
pages = "329--345",
keywords = "surface approximation",
}
@InCollection{Baszenski91sa,
author = "G. Baszenski and L. L. Schumaker",
title = "Use of simulated annealing to construct triangular
facet surfaces",
editor = "P.-J. Laurent and A. Le M\'ehaut\'e and L. L.
Schumaker",
booktitle = "Curves and Surfaces",
publisher = "Academic Press",
year = "1991",
pages = "27--32",
keywords = "triangulation",
}
@InCollection{Sabin80contour,
author = "M. A. Sabin",
year = "1980",
title = "Contouring: {A} Review of Methods for Scattered Data",
booktitle = "Mathematical Methods in Computer Graphics and Design",
editor = "K. W. Brodlie",
publisher = "Academic Press",
}
@Book{Thisted88,
author = "Ronald A. Thisted",
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 = "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 = "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 = "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 = jun,
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 = jul,
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,
http://www.ius.cs.cmu.edu/usr/users/aej/www/research/modeling.html,
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",
}
@Misc{Akeley90tomesh,
author = "Kurt Akeley and Paul Haeberli and D. Burns",
title = "/usr/people/4Dgifts/iristools/libgutil/tomesh.c",
note = "C code for SGI machines",
year = "1996",
keywords = "triangle strip, geometry compression",
annote = "greedy algorithm attempts to minimize number of
triangle strips",
}
@Misc{Evans9xstrip,
title = "A Software Tool To Produce Efficient Triangle Strips",
author = "Francine Evans and Steven Skiena and Amitabh
Varshney",
note = "http://www.cs.sunysb.edu/~evans/stripe.html",
}
@InProceedings{Arkin94ham,
author = "E. M. Arkin and M. Held and J. S. B. Mitchell and S.
S. Skiena",
title = "Hamiltonian Triangulations for Fast Rendering",
editor = "J.~van Leeuwen",
booktitle = "Algorithms -- ESA'94",
series = "LNCS 855",
address = "Utrecht, NL",
month = sep,
year = "1994",
pages = "36--47",
update = "95.01 held",
keywords = "computational geometry, triangle strip, geometry
compression",
annote = "find minimum number of triangle strips (Hamiltonian
cover)",
}
@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,
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,
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 = "C. Rocchini P. Cignoni 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,
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 = sep,
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",
}
@Article{InnovMetric,
key = "InnovMetric",
title = "{InnovMetric}",
note = "Commercial software,
http://www.innovmetric.com",
}
@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 = jul,
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 = mar,
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 = "Mar\'{\i}a-Elena Algorri and Francis 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
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
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
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{\"u}cke 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 = "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 = jul,
year = "1996",
keywords = "computer vision, range data",
note = "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 = jan,
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 = "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,
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,
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
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",
}
@InProceedings{Fjallstrom86,
author = "Per-Olof Fj{\"a}llstr{\"o}m",
title = "Smoothing of Polyhedral Models",
booktitle = "COMPGEOM: Annual ACM Symposium on Computational
Geometry",
year = "1986",
pages = "226--235",
keywords = "IMAGE PART FORM, LARGE DIMENSIONALITY",
}
@TechReport{Fjallstrom91tr,
author = "Per-Olof Fj{\"a}llstr{\"o}m",
title = "Polyhedral Approximation of Bivariate Functions",
institution = "Dept. of Computer and Information Science,
Link{\"o}ping U, Sweden",
note = "LiTH-IDA-R-91-24",
month = aug,
year = "1991",
keywords = "computational geometry, surface approximation, height
field",
abstract = "Given a set V of n points drawn from a bivariate
function and a non-negative scalar d, we want to find a
smallest subset, V', of V, such that a polyhedral
surface interpolating V', does not deviate more than d
from any point in V. A greedy heuristic, requiring
0(n2log n) time and [theta](n) space, is presented.",
annote = "Also accepted to the Third Canadian Conference on
Computational Geometry, Vancouver, B.C., Canada August
5-10, 1991. Similar to DeFloriani83.",
}
@InProceedings{Fjallstrom91can,
author = "Per-Olof Fj{\"a}llstr{\"o}m",
title = "Polyhedral approximation of bivariate functions",
booktitle = "Proc. 3rd Canadian Conf. Computational Geometry",
month = aug,
year = "1991",
pages = "187--190",
keywords = "computational geometry, surface approximation, height
field",
annote = "Similar to DeFloriani83. Nearly identical to
Fjallstrom91tr.",
}
@Article{Fjallstrom93,
author = "Per-Olof Fj{\"a}llstr{\"o}m",
title = "Evaluation of a {Delaunay}-based method for surface
approximation",
journal = "Computer-Aided Design",
volume = "25",
number = "11",
year = "1993",
pages = "711--719",
keywords = "computational geometry, surface approximation, height
field, greedy insertion",
annote = "Similar to DeFloriani83. Expanded version of
Fjallstrom91can with more emphasis on estimating
optimal solution size and evaluating the quality of
greedy insertion's approximations.",
}
@InCollection{Nielson97trisurv,
author = "Gregory M. Nielson",
title = "Tools for Triangulations and Tetrahedrizations and
Constructing Functions Defined over Them",
booktitle = "Scientific Visualization: Overviews, Methodologies,
and Techniques",
editor = "Gregory M. Nielson and Hans Hagen and Heinrich
Mueller",
publisher = "IEEE Comput. Soc. Press",
year = "1997",
}
@TechReport{Erikson96simp,
author = "Carl Erikson",
title = "Polygonal Simplification: An Overview",
school = "Dept. of CS, U. of North Carolina, Chapel Hill",
year = "1996",
note = "TR 96-016",
keywords = "surface simplification",
note = "ftp://ftp.cs.unc.edu/pub/publications/techreports/96.html",
annote = "33 pages",
}
@InProceedings{Low97,
author = "Kok-Lim Low and Tiow-Seng Tan",
title = "Model Simplification Using Vertex-Clustering",
booktitle = "1997 Symposium on Interactive 3D Graphics",
publisher = "ACM SIGGRAPH",
year = "1997",
keywords = "surface simplification",
note = "To appear, http://www.iscs.nus.sg/~tants/",
}
@Misc{siscat96,
title = "Siscat",
note = "http://www.oslo.sintef.no/siscat/",
keywords = "scattered data interpolation, geophysical modeling,
meteorological modeling, terrain modeling",
annote = "large C++ subroutine library for scattered data
interpolation and surface modeling",
year = "1996",
}
@InProceedings{Arge97oo,
author = "E. Arge and {\O}. Hjelle",
title = "Object-Oriented Scattered Data Modelling with Siscat",
booktitle = "Modern Software Tools for Scientific Computing",
editor = "E. Arge and A. M. Bruaset and H. P. Langtangen",
publisher = "Birkh{\"a}user",
year = "1997",
annote = "http://www.oslo.sintef.no/SciTools96",
}
@InProceedings{Arge97tools,
author = "E. Arge and {\O}. Hjelle",
title = "Software tools for modelling scattered data",
booktitle = "Numerical Methods and Software Tools in Industrial
Mathematics",
editor = "M. D{\ae}hlen and A. Tveito",
publisher = "Birkh{\"a}user",
pages = "47--62",
year = "1997",
}
@InProceedings{Fremming97,
author = "N. P. Fremming and {\O}. Hjelle and C. Tarrou",
title = "Surface modelling from scattered geological data",
booktitle = "Numerical Methods and Software Tools in Industrial
Mathematics",
editor = "M. D{\ae}hlen and A. Tveito",
publisher = "Birkh{\"a}user",
pages = "305--320",
year = "1997",
}
@InCollection{Schaufler95,
author = "Schaufler and W. Sturzlinger",
booktitle = "Virtual Environments '95 (Eurographics)",
year = "1995",
annote = "similar to Rossignac-Borrel",
}
@InProceedings{Maciel95,
author = "Paulo W. C. Maciel and Peter Shirley",
title = "Visual Navigation of Large Environments Using Textured
Clusters",
pages = "95--102",
booktitle = "1995 Symposium on Interactive {3D} Graphics",
year = "1995",
month = apr,
}
@InProceedings{Xia96,
author = "Julie C. Xia and Amitabh Varshney",
title = "Dynamic View-Dependent Simplification for Polygonal
Models",
pages = "327--334",
booktitle = "Proceedings of Visualization '96",
year = "1996",
month = oct,
}
@InProceedings{Klein96,
author = "Reinhard Klein and Gunther Liebich and W.
Stra{\ss}er",
title = "Mesh Reduction with Error Control",
pages = "311--318",
booktitle = "Proceedings of Visualization '96",
year = "1996",
month = oct,
}
@InProceedings{Aliaga96,
author = "Daniel G. Aliaga",
title = "Visualization of Complex Models Using Dynamic
Texture-based Simplification",
pages = "101--106",
booktitle = "Proceedings of Visualization '96",
year = "1996",
month = oct,
}
@Article{Agishtein:1991:SSR,
author = "Michael E. Agishtein and Alexander A. Migdal",
title = "Smooth surface reconstruction from scattered data
points",
pages = "29--39",
journal = "Computers and Graphics",
volume = "15",
number = "1",
year = "1991",
keywords = "delaunay triangulation",
}
@Article{Leu88,
author = "J.-G. Leu and L. Chen",
title = "Polygonal approximation of 2-{D} shapes through
boundary merging",
journal = "Pattern Recognition Letters",
year = "1988",
volume = "7",
number = "4",
pages = "231--238",
month = apr,
}
@Article{Boxer93,
author = "Laurence Boxer and Chun-Shi Chang and Russ Miller and
Andrew Rau-Chaplin",
title = "Polygonal approximation by boundary reduction",
journal = "Pattern Recognition Letters",
year = "1993",
volume = "14",
number = "2",
pages = "111--119",
month = feb,
}
@Article{Hughes96,
author = "Merlin Hughes and Anselmo A. Lastra and Edward Saxe",
title = "Simplification of Global-Illumination Meshes",
journal = "Computer Graphics Forum",
note = "Proc. Eurographics '96",
year = "1996",
volume = "15",
number = "3",
pages = "339--345",
month = aug,
}
@Article{fwe-tdamg-70,
author = "C. O. Frederick and Y. C. Wong and F. W. Edge",
title = "Two-dimensional Automatic Mesh Generation for
Structural Analysis",
journal = "Internat. J. Numer. Methods Eng.",
volume = "2",
year = "1970",
pages = "133--144",
keywords = "Delaunay trianglation",
annote = "Triangulation of set of specified points. Builds
triangles on edges to surround each point in turn. When
building on edge $AB$ point $C$ which maximizes $\angle
ACB$ is picked. DT! They didn't know they were
computing the Delaunay triang. Earliest published
Delaunay trianglation algorithm?",
}
@InProceedings{Garland97,
author = "Michael Garland and Paul S. Heckbert",
title = "Surface Simplification Using Quadric Error Metrics",
booktitle = "SIGGRAPH 97 Proc.",
year = "1997",
month = aug,
pages = "209--216",
note = "http://www.cs.cmu.edu/~garland/quadrics/",
}
@InProceedings{Luebke97,
author = "David Luebke and Carl Erikson",
title = "View-Dependent Simplification of Arbitrary Polygonal
Environments",
booktitle = "SIGGRAPH 97 Proc.",
year = "1997",
month = aug,
pages = "199--208",
}
@InProceedings{Hoppe97vdr,
author = "Hugues Hoppe",
title = "View-Dependent Refinement of Progressive Meshes",
pages = "189--198",
booktitle = "SIGGRAPH 97 Proc.",
year = "1997",
month = aug,
note = "http://research.microsoft.com/~hoppe/",
}
@InProceedings{Popovic97psc,
author = "Jovan Popovi\'c and Hugues Hoppe",
title = "Progressive Simplicial Complexes",
pages = "217--224",
booktitle = "SIGGRAPH 97 Proc.",
year = "1997",
note = "http://research.microsoft.com/~hoppe/",
}
@TechReport{Krus97tr,
author = "Mike Krus",
title = "Maillages Polygonaux et Niveaux de {D}/'etails:
/'etude bibliographique",
institution = "LIMSI/CNRS, Orsay, France",
number = "97-10",
month = may,
year = "1997",
note = "http://www.limsi.fr:80/Individu/krus/",
annote = "in French. 59 pp. Title: Polygonal Meshes and Levels
of Detail. Survey of techniques for creating levels of
detail for virtual reality by simplification or with
imposters. Reviews the conditions under which methods
can be used in current rendering software",
}
@InProceedings{Cohen97map,
author = "Jonathan Cohen and Dinesh Manocha and Marc Olano",
title = "Simplifying Polygonal Models Using Successive
Mappings",
booktitle = "Second CGC Workshop on Computational Geometry",
month = oct,
year = "1997",
address = "Duke University",
keywords = "surface simplification",
}