×
Song, Xiaowen; Sederberg, Thomas W.; Zheng, Jianmin; Farouki, Rida T.; Hass, Joel

Linear perturbation methods for topologically consistent representations of free-form surface intersections. (English) Zbl 1069.65567

Comput. Aided Geom. Des. 21, No. 3, 303-319 (2004).
Summary: By applying displacement maps to slightly perturb two free-form surfaces, one can ensure exact agreement between the images in \(\mathbb R^3\) of parameter-domain approximations to their curve of intersection. Thus, at the expense of slightly altering the surfaces in the vicinity of their intersection, a perfect matching of the surface trimming curves is guaranteed. This exact agreement of contiguous trimmed surfaces is essential to achieving topologically consistent solid model constructions through Boolean operations, and has a profound impact on the efficiency and reliability of applications such as meshing, rendering, and computing volumetric properties. Moreover, the control point perturbations require only the solution of a linear system for their determination. The basic principles of this approach to topologically consistent surface trimming curves are described, and example results from the implementation of a simple instance of the method are presented.

Cited in 10 Documents

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry

Keywords:

surface intersections; trimmed surfaces; control point perturbations; topological consistency; geometric continuity

Software:

BPOLY
Cite Review PDF
Full Text: DOI

References:

[1] Biermann, H.; Kristjansson, D.; Zorin, D., Approximate Boolean operations on free-form solids, (Proceedings of SIGGRAPH 2001 (2001), ACM), 185-194
[2] Cho, W. J.; Maekawa, T.; Patrikalakis, N. M.; Peraire, J., Topologically reliable approximation of trimmed polynomial surface patches, Graph. Model Image Process., 61, 84-109 (1999) · Zbl 0979.68582
[3] DeRose, A. D., Composing Bézier simplexes, ACM Trans. Graph., 7, 198-221 (1988) · Zbl 0657.65027
[4] Farin, G., Curves and Surfaces for Computer Aided Geometric Design (1997), Academic Press: Academic Press New York · Zbl 0919.68120
[5] Farouki, R. T.; Goodman, T. N.T., On the optimal stability of the Bernstein basis, Math. Comput., 65, 1553-1566 (1996) · Zbl 0853.65051
[6] Farouki, R. T.; Rajan, V. T., On the numerical condition of polynomials in Bernstein form, Computer Aided Geometric Design, 4, 191-216 (1987) · Zbl 0636.65012
[7] Farouki, R. T.; Rajan, V. T., Algorithms for polynomials in Bernstein form, Computer Aided Geometric Design, 5, 1-26 (1988) · Zbl 0648.65007
[8] Farouki, R. T., The characterization of parametric surface sections, Computer Vis. Graph. Image Process., 33, 209-236 (1986) · Zbl 0631.65012
[9] Farouki, R. T., Trimmed surface algorithms for the evaluation and interrogation of solid boundary representations, IBM J. Res. Develop., 31, 314-334 (1987)
[10] Farouki, R. T., Closing the gap between CAD model and downstream application, SIAM News, 32, 5, 1-3 (1999), (Report on the SIAM Workshop on Integration of CAD and CFD, UC Davis, April 12-13, 1999)
[11] Gonzalez-Vega, L.; Necula, I., Efficient topology determination of implicitly defined algebraic plane curves, Computer Aided Geometric Design, 19, 719-743 (2002) · Zbl 1043.68105
[12] Grandine, T. A.; Klein, F. W., A new approach to the surface intersection problem, Computer Aided Geometric Design, 14, 111-134 (1997) · Zbl 0906.68151
[13] Hamann, B.; Tsai, P. Y., A tessellation algorithm for the representation of trimmed NURBS surfaces with arbitrary trimming curves, Computer-Aided Design, 28, 461-472 (1996)
[14] Hu, Y. P.; Sun, T. C., Moving a B-spline surface to a curve—a trimmed surface matching algorithm, Computer-Aided Design, 29, 449-455 (1997)
[15] Katz, S.; Sederberg, T. W., Genus of the intersection curve of two rational surface patches, Computer Aided Geometric Design, 5, 253-258 (1988) · Zbl 0648.65011
[16] Lane, J. M.; Riesenfeld, R. F., Bounds on a polynomial, BIT, 21, 112-117 (1981) · Zbl 0472.65041
[17] Litke, N.; Levin, A.; Schröder, P., Trimming for subdivision surfaces, Computer Aided Geometric Design, 18, 463-481 (2001) · Zbl 0970.68185
[18] Patrikalakis, N. M.; Maekawa, T., Intersection problems, (Farin, G.; Hoschek, J.; Kim, M.-S., Handbook of Computer Aided Geometric Design (2002), North-Holland: North-Holland Amsterdam), 623-649
[19] Rockwood, A. P.; Heaton, K.; Davis, T., Real-time rendering of trimmed surfaces, (Proceedings of SIGGRAPH 89 (1989), ACM), 107-116
[20] Sederberg, T. W.; Nishita, T., Geometric Hermite approximation of surface patch intersection curves, Computer Aided Geometric Design, 8, 97-114 (1991) · Zbl 0738.65005
[21] Sederberg, T.W., 1983. Implicit and parametric curves and surfaces for computer aided geometric design, PhD Thesis, Purdue University; Sederberg, T.W., 1983. Implicit and parametric curves and surfaces for computer aided geometric design, PhD Thesis, Purdue University
[22] Seidel, R., The nature and meaning of perturbations in geometric computing, Discrete Comput. Geom., 19, 1-17 (1998) · Zbl 0892.68100
[23] Sherbrooke, E. C.; Patrikalakis, N. M., Computation of the solutions of nonlinear polynomial systems, Computer Aided Geometric Design, 10, 379-405 (1993) · Zbl 0817.65035
[24] Speer, T.; Kuppe, M.; Hoschek, J., Global reparameterization for curve approximation, Computer Aided Geometric Design, 15, 869-877 (1998) · Zbl 0910.68214
[25] Tsai, Y.-F.; Farouki, R. T., Algorithm 812: BPOLY: An object-oriented library of numerical algorithms for polynomials in Bernstein form, ACM Trans. Math. Software, 27, 267-296 (2001) · Zbl 1070.65515
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.