Summary
For grid terrain data, we propose a Lepp-surface triangulation method that starts with a coarse initial triangulation of the input data, and incrementally adds data points that reduce the worst edge approximation error in the mesh. The method generalizes a previous Lepp-centroid method in two dimensions as follows: for the edge E, having highest error in the mesh, one or two points close to (one or two) terminal edges associated to E, are inserted in the mesh. The edge error is computed by adding the triangle approximation errors of the two triangles that share E, while each triangle error in L 2-norm is computed by using a curvature tensor (good approximation of the surface) at a representative point associated to both triangles. The method produces triangular approximations that capture well the relevant features of the terrain surface by naturally producing well-shaped triangles.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aspert, N., Santa-Cruz, D., Ebrahimi, T.: Mesh: Measuring errors between surfaces using the hausdorff distance. In: Proc. of the IEEE International Conference in Multimedia and Expo., pp. 705–708 (2002)
Bertram, M., Barnes, J.C., Hamann, B., Joy, K.I., Pottmann, H., Wushour, D.: Piecewise optimal triangulation for the approximation of scattered data in the plane. Computer Aided Geometric Design 17(8), 767–787 (2000)
Cignoni, P., Corsini, M., Ranzuglia, G.: Meshlab: an open-source 3d mesh processing system. ERCIM News (73), 45–46 (2008)
DeFloriani, L., Magillo, P., Puppo, E.: Variant: A system for terrain modeling at variable resolution. GeoInformatica 4(3), 287–315 (2000)
Dyn, N., Levin, D., Rippa, S.: Data dependent triangulations for piecewise linear interpolation. IMA Journal of Numerical Analysis 10, 137–154 (1990)
Frey, P.J., Borouchaki, H.: Geometric surface mesh optimization. Computing and Visualization in Science 1(3), 121–133 (1998)
Garland, M.: Multiresolution modeling: Survey & future opportunities. Eurographics State of The Art Report (1999)
Garland, M.: Quadric-based polygonal surface simplification, Ph.D. thesis, Carnegie Mellon University (1999)
Garland, M., Heckbert, P.: Surface simplification using quadric error metrics. In: SIGGRAPH 1997: Proceedings of the 24th annual conference on Computer graphics and interactive techniques, pp. 209–216 (1997)
Garland, M., Heckbert, P.-S.: Fast polygonal approximation of terrains and height fields, Tech. Report CMU-CS-95-181 (1995)
Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., Stuetzle, W.: Mesh optimization. Computer Graphics 27, 19–26 (1993)
Kalogerakis, E., Simari, P., Nowrouzezahrai, D., Singh, K.: Robust statistical estimation of curvature on discretized surfaces. In: SGP 2007: Proceedings of the fifth Eurographics symposium on Geometry processing, Eurographics Association, pp. 13–22 (2007)
Lawson, C.-L.: Software for \(\mathcal{C} ^{1}\) surface interpolation. In: Rice, J.R. (ed.) Mathematical Software III, pp. 161–194 (1977)
Lindstrom, P., Pascucci, V.: Visualization of large terrains made easy. In: Proceedings of IEEE Visualization 2001, pp. 363–370, 574 (2001)
Lindstrom, P., Pascucci, V.: Terrain simplification simplified: a general framework for view-dependent out-of-core visualization. IEEE Transactions on Visualization and Computer Graphics 8(3), 239–254 (2002)
Nadler, E.: Piecewise linear best \(\textit{L}_{2}\) approximation on triangulations. In: Chui, C.K., et al. (eds.) Approximation Theory V, pp. 499–502 (1986)
Pajarola, R., Gobbetti, E.: Survey on semi-regular multiresolution models for interactive terrain rendering. The Visual Computer 23(8), 585–605 (2007)
Rippa, S.: Long and thin triangles can be good for linear interpolation. SIAM Journal on Numerical Analysis 29(1), 257–270 (1992)
Rivara, M.-C.: New longest-edge algorithms for the refinement and/or improvement of unstructured triangulation. International Journal for Numerical Methods in Engineering 40, 3313–3324 (1997)
Rivara, M.-C., Calderon, C.: Lepp terminal centroid method for quality triangulation: A study on a new algorithm. In: Chen, F., Jüttler, B. (eds.) GMP 2008. LNCS, vol. 4975, pp. 215–230. Springer, Heidelberg (2008)
Rivara, M.-C., Hitschfeld, N., Simpson, R.-B.: Terminal edges delaunay (small angle based) algorithm for the quality triangulation problem. Computer-Aided Design 33, 263–277 (2001)
Rivara, M.-C., Palma, M.: New lepp algorithms for quality polygon and volume triangulation: Implementation issues and practical behavior. 220, 543–562 (1997)
Röttger, S., Heidrich, W., Slussallek, P., Seidel, H.-P.: Real-time generation of continuous levels of detail for height fields. In: Proceedings of 1998 International Conference in Central Europe on Computer Graphics and Viaualization, pp. 315–322 (1998)
Shewchuk, J.-R.: What is a good linear element? interpolation, conditioning, and quality measures. In: Proceedings of the 11th International Meshing Roundtable (2002)
Vollmer, J., Mencl, R., Môller, H.: Improved laplacian smoothing of noisy surface meshes. Computer Graphics Forum (Eurographics 1999) 18(3), 131–138 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Coll, N., Guerrieri, M., Rivara, MC., Sellarès, J.A. (2008). Accurate Interpolation of Terrain Surfaces from Over-Sampled Grid Data. In: Garimella, R.V. (eds) Proceedings of the 17th International Meshing Roundtable. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87921-3_21
Download citation
DOI: https://doi.org/10.1007/978-3-540-87921-3_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87920-6
Online ISBN: 978-3-540-87921-3
eBook Packages: EngineeringEngineering (R0)