## 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 | |

State | Published - Sep 2000 |

## ASJC Scopus subject areas

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