Decomposing trimmed surfaces using the Voronoï diagram and a scan line algorithm

DOI10.1016/S0096-3003(97)81666-9MaRDI QIDQ1126660zbMATH OpenOpenAlexFDO

Authors Bernd Hamann, Po-Yu Tsai

Publication date 8 October 1998

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0096-3003(97)81666-9

zbMATH Keywords

grid generationholes in surfacesscan line algorithmtrimmed surfacesVoronoi diagram

Mathematics Subject Classification ID

Computer-aided design (modeling of curves and surfaces) (65D17)

Review text

The authors note that in adapting grids to holes in surfaces, it is of great advantage to compute separate grids around each hole. In order to obtain best situated domains, they compute a generalized Voronoi diagram, i.e., they decompose the given surface into parts such that each point not on the boundary of the parts is closest to one given hole. An algorithm to do this by computing selected perpendicular bisectors of couples of points on the boundary curves of different holes is described. The second problem attacked then is the generation of a grid in one Voronoi domain adapted to the shape of the hole. Examples are given and some problems still to be solved to make the algorithm more efficient are indicated.

Recommendations

• scientific article; zbMATH DE number 1015020
• Efficient rendering of trimmed NURBS surfaces
• Tessellating trimmed NURBS surfaces
• Voronoi diagrams, triangulations and surfaces

Cites work

• An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
• Generalization of Voronoi Diagrams in the Plane
• Geometry processing : intersections, contours, and cubatures
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 48528 (Why is no real title available?)
• scientific article; zbMATH DE number 50847 (Why is no real title available?)
• scientific article; zbMATH DE number 409734 (Why is no real title available?)
• scientific article; zbMATH DE number 1317748 (Why is no real title available?)
• scientific article; zbMATH DE number 491264 (Why is no real title available?)
• Intersection and Closest-Pair Problems for a Set of Planar Discs
• Power Diagrams: Properties, Algorithms and Applications
• Randomized incremental construction of abstract Voronoi diagrams
• Robust, geometrically based, automatic two‐dimensional mesh generation
• Spline conversion for trimmed rational Bézier- and B-spline surfaces
• The bisector of a point and a plane parametric curve

Cited in

(1)

• Swap conditions for dynamic Voronoi diagrams for circles and line segments

This page was built for publication: Decomposing trimmed surfaces using the Voronoï diagram and a scan line algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1126660)