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