Piecewise optimal triangulation for the approximation of scattered data in the plane

Martin Bertram; James C. Barnes; Bernd Hamann; Kenneth I. Joy; Helmut Pottmann; Dilinur Wushour

doi:10.1016/S0167-8396(00)00026-1

Piecewise optimal triangulation for the approximation of scattered data in the plane

Martin Bertram, James C. Barnes, Bernd Hamann, Kenneth I. Joy, Helmut Pottmann, Dilinur Wushour

Research output: Contribution to journal › Article › peer-review

9 Scopus citations

Abstract

We present an efficient algorithm to obtain a triangulated graph surface for scattered points (x_i y_i)^T, i = 1, ..., n, with associated function values f_i. The maximal distance between the triangulated graph surface and the function values is measured in z-direction (z = f(x, y)) and lies within a user-defined tolerance. The number of triangles is minimized locally by adapting their shapes to different second-degree least squares approximations of the underlying data. The method consists of three major steps: (i) subdividing the given discrete data set into clusters such that each cluster can be approximated by a quadratic polynomial within a prescribed tolerance; (ii) optimally triangulating the graph surface of each quadratic polynomial; and (iii) `stitching' the triangulations of all graph surfaces together. We also discuss modifications of the algorithm that are necessary to deal with discrete data points, without connectivity information, originating from a general two-manifold surface, i.e., a surface in three-dimensional space that is not necessarily a graph surface.

Original language	English (US)
Pages (from-to)	767-787
Number of pages	21
Journal	Computer Aided Geometric Design
Volume	17
Issue number	8
DOIs	https://doi.org/10.1016/S0167-8396(00)00026-1
State	Published - Sep 2000
Externally published	Yes

Bibliographical note

Funding Information:
This work was performed under the auspices of the U.S. Department of Energy by University of California Lawrence Livermore National Laboratory under contract No. W-7405-Eng-48. This work was supported by the National Science Foundation under contracts ACI 9624034 and ACI 9983641 (CAREER Awards), through the Large Scientific and Software Data Set Visualization (LSSDSV) program under contract ACI 9982251, and through the National Partnership for Advanced Computational Infrastructure (NPACI); the Office of Naval Research under contract N00014-97-1-0222; the Army Research Office under contract ARO 36598-MA-RIP; the NASA Ames Research Center through an NRA award under contract NAG2-1216; the Lawrence Livermore National Laboratory under ASCI ASAP Level-2 Memorandum Agreement B347878 and under Memorandum Agreement B503159; and the North Atlantic Treaty Organization (NATO) under contract CRG.971628 awarded to the University of California, Davis. We also acknowledge the support of ALSTOM Schilling Robotics, Chevron, General Atomics, Silicon Graphics, Inc. and ST Microelectronics, Inc. We thank the members of the Visualization Thrust at the Center for Image Processing and Integrated Computing (CIPIC) at the University of California, Davis, and the members of the Data Exploration Group at the Center for Applied Scientific Computing (CASC) at the Lawrence Livermore National Laboratory.

ASJC Scopus subject areas

Modeling and Simulation
Automotive Engineering
Aerospace Engineering
Computer Graphics and Computer-Aided Design

Access to Document

10.1016/S0167-8396(00)00026-1

Cite this

@article{34a8825b0d094ba88228475b87505204,

title = "Piecewise optimal triangulation for the approximation of scattered data in the plane",

abstract = "We present an efficient algorithm to obtain a triangulated graph surface for scattered points (xi yi)T, i = 1, ..., n, with associated function values fi. The maximal distance between the triangulated graph surface and the function values is measured in z-direction (z = f(x, y)) and lies within a user-defined tolerance. The number of triangles is minimized locally by adapting their shapes to different second-degree least squares approximations of the underlying data. The method consists of three major steps: (i) subdividing the given discrete data set into clusters such that each cluster can be approximated by a quadratic polynomial within a prescribed tolerance; (ii) optimally triangulating the graph surface of each quadratic polynomial; and (iii) `stitching' the triangulations of all graph surfaces together. We also discuss modifications of the algorithm that are necessary to deal with discrete data points, without connectivity information, originating from a general two-manifold surface, i.e., a surface in three-dimensional space that is not necessarily a graph surface.",

author = "Martin Bertram and Barnes, {James C.} and Bernd Hamann and Joy, {Kenneth I.} and Helmut Pottmann and Dilinur Wushour",

note = "Funding Information: This work was performed under the auspices of the U.S. Department of Energy by University of California Lawrence Livermore National Laboratory under contract No. W-7405-Eng-48. This work was supported by the National Science Foundation under contracts ACI 9624034 and ACI 9983641 (CAREER Awards), through the Large Scientific and Software Data Set Visualization (LSSDSV) program under contract ACI 9982251, and through the National Partnership for Advanced Computational Infrastructure (NPACI); the Office of Naval Research under contract N00014-97-1-0222; the Army Research Office under contract ARO 36598-MA-RIP; the NASA Ames Research Center through an NRA award under contract NAG2-1216; the Lawrence Livermore National Laboratory under ASCI ASAP Level-2 Memorandum Agreement B347878 and under Memorandum Agreement B503159; and the North Atlantic Treaty Organization (NATO) under contract CRG.971628 awarded to the University of California, Davis. We also acknowledge the support of ALSTOM Schilling Robotics, Chevron, General Atomics, Silicon Graphics, Inc. and ST Microelectronics, Inc. We thank the members of the Visualization Thrust at the Center for Image Processing and Integrated Computing (CIPIC) at the University of California, Davis, and the members of the Data Exploration Group at the Center for Applied Scientific Computing (CASC) at the Lawrence Livermore National Laboratory.",

year = "2000",

month = sep,

doi = "10.1016/S0167-8396(00)00026-1",

language = "English (US)",

volume = "17",

pages = "767--787",

journal = "Computer Aided Geometric Design",

issn = "0167-8396",

publisher = "Elsevier",

number = "8",

}

TY - JOUR

T1 - Piecewise optimal triangulation for the approximation of scattered data in the plane

AU - Bertram, Martin

AU - Barnes, James C.

AU - Hamann, Bernd

AU - Joy, Kenneth I.

AU - Pottmann, Helmut

AU - Wushour, Dilinur

N1 - Funding Information: This work was performed under the auspices of the U.S. Department of Energy by University of California Lawrence Livermore National Laboratory under contract No. W-7405-Eng-48. This work was supported by the National Science Foundation under contracts ACI 9624034 and ACI 9983641 (CAREER Awards), through the Large Scientific and Software Data Set Visualization (LSSDSV) program under contract ACI 9982251, and through the National Partnership for Advanced Computational Infrastructure (NPACI); the Office of Naval Research under contract N00014-97-1-0222; the Army Research Office under contract ARO 36598-MA-RIP; the NASA Ames Research Center through an NRA award under contract NAG2-1216; the Lawrence Livermore National Laboratory under ASCI ASAP Level-2 Memorandum Agreement B347878 and under Memorandum Agreement B503159; and the North Atlantic Treaty Organization (NATO) under contract CRG.971628 awarded to the University of California, Davis. We also acknowledge the support of ALSTOM Schilling Robotics, Chevron, General Atomics, Silicon Graphics, Inc. and ST Microelectronics, Inc. We thank the members of the Visualization Thrust at the Center for Image Processing and Integrated Computing (CIPIC) at the University of California, Davis, and the members of the Data Exploration Group at the Center for Applied Scientific Computing (CASC) at the Lawrence Livermore National Laboratory.

PY - 2000/9

Y1 - 2000/9

N2 - We present an efficient algorithm to obtain a triangulated graph surface for scattered points (xi yi)T, i = 1, ..., n, with associated function values fi. The maximal distance between the triangulated graph surface and the function values is measured in z-direction (z = f(x, y)) and lies within a user-defined tolerance. The number of triangles is minimized locally by adapting their shapes to different second-degree least squares approximations of the underlying data. The method consists of three major steps: (i) subdividing the given discrete data set into clusters such that each cluster can be approximated by a quadratic polynomial within a prescribed tolerance; (ii) optimally triangulating the graph surface of each quadratic polynomial; and (iii) `stitching' the triangulations of all graph surfaces together. We also discuss modifications of the algorithm that are necessary to deal with discrete data points, without connectivity information, originating from a general two-manifold surface, i.e., a surface in three-dimensional space that is not necessarily a graph surface.

AB - We present an efficient algorithm to obtain a triangulated graph surface for scattered points (xi yi)T, i = 1, ..., n, with associated function values fi. The maximal distance between the triangulated graph surface and the function values is measured in z-direction (z = f(x, y)) and lies within a user-defined tolerance. The number of triangles is minimized locally by adapting their shapes to different second-degree least squares approximations of the underlying data. The method consists of three major steps: (i) subdividing the given discrete data set into clusters such that each cluster can be approximated by a quadratic polynomial within a prescribed tolerance; (ii) optimally triangulating the graph surface of each quadratic polynomial; and (iii) `stitching' the triangulations of all graph surfaces together. We also discuss modifications of the algorithm that are necessary to deal with discrete data points, without connectivity information, originating from a general two-manifold surface, i.e., a surface in three-dimensional space that is not necessarily a graph surface.

UR - http://www.scopus.com/inward/record.url?scp=0034276341&partnerID=8YFLogxK

U2 - 10.1016/S0167-8396(00)00026-1

DO - 10.1016/S0167-8396(00)00026-1

M3 - Article

AN - SCOPUS:0034276341

SN - 0167-8396

VL - 17

SP - 767

EP - 787

JO - Computer Aided Geometric Design

JF - Computer Aided Geometric Design

IS - 8

ER -

Piecewise optimal triangulation for the approximation of scattered data in the plane

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this