Fast and Robust Point Containment Queries on Trimmed Surface DOI: XXXXXXX.XXXXXXX ISBN: 978-1-4503-XXXX-X/18/06 1257 CCS: Computing methodologies Parametric curve and surface models

Anchang Bao, Enya Shen, Jianmin Wang · 2025

Read Fast and Robust Point Containment Queries on Trimmed Surface DOI: XXXXXXX.XXXXXXX ISBN: 978-1-4503-XXXX-X/18/06 1257 CCS: Computing methodologies Parametric curve and surface models by Anchang Bao, Enya Shen, Jianmin Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-25159.txt.

Introduction

Anchang Bao, Enya Shen, and Jianmin Wang speed up point in or out tests on trimmed faces, a base task in CAD work. Past ways such as ray casts and broad wind counts can be slow or frail. Their way rests on a loop form of the wind count for a trimmed face.

In place of costly curve cuts, an oval bound on each curve span lets the count run in line time. For faces that wrap in a loop, trim curves are lifted to a cover space so counts stay true for loops that can not shrink. Tests show large speed gains over past wind tools, with strong hold in noise, open edges, and wrap cases.

Catalog record

CREATORAnchang Bao, Enya Shen, Jianmin Wang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-25159

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fast and Robust Point Containment Queries on Trimmed Surface DOI: XXXXXXX.XXXXXXX ISBN: 978-1-4503-XXXX-X/18/06 1257 CCS: Computing methodologies Parametric curve and surface models Anchang Bao, Enya Shen, Jianmin Wang Abstract . Point containment queries on trimmed surfaces are fundamental to CAD modeling, solid geometry processing, and surface tessellation. Existing approaches—such as ray casting and generalized winding numbers—often face limitations in robustness and computational efficiency. We propose a fast and numerically stable method for performing containment queries on trimmed surfaces, including those with periodic parameterizations. Our approach introduces a recursive winding number computation scheme that replaces costly curve subdivision with an ellipse-based bound for Bézier segments, enabling linear-time evaluation. For periodic surfaces, we lift trimming curves to the universal covering space, allowing accurate and consistent winding number computation even for non-contractible or discontinuous loops in parameter domain. Experiments show that our method achieves substantial speedups over existing winding-number algorithms while maintaining high robustness in the presence of geometric noise, open boundaries, and periodic topologies. We further demonstrate its effectiveness in processing real B-Rep models and in robust tessellation of trimmed surfaces. Figure 1. We proposed an efficient winding number computation method for parametric curves and generalize to the periodic domain by lifting curves to the universal covering space. With this proposed method, we developed fast and robust point containment queries on trimmed surfaces. First row : Illustration of the winding number computation method described in section 4 . The red point is the testing point and the colored curves are ellipses used in our algorithms. Different from the Spainhour et al. 2024 , we utilize a more flexible ellipse bound, enabling linear time Bézier curves evaluation and O(1) inclusion test. Second row : By lifting curves to the universal covering space, we correctly compute the winding number on the periodic domain. With the proposed method, we can handle containment queries on the periodic trimmed surface robustly. Given open boundary curves, we present the winding number field calculated in covering space and parametric space respectively. 1. Introduction Trimmed surfaces play a central role in free-form modeling and are commonly represented using Boundary Representation (B-Rep), the industry standard for free-form solids ( Pratt et al. 2001 ) . Unlike ordinary spline patches, a trimmed surface is defined by an underlying geometric surface and a set of boundary curves that restrict its visible region. Processing boundary-represented solids lies at the core of free-form modeling, yet one key limitation of B-Rep is the absence of explicit containment relations between solids. As a result, containment tests become essential whenever inclusion relations are required. A fundamental instance of this task is determining whether a point on the underlying geometric surface lies within its trimmed region—known as a containment query on a trimmed surface. Figure 2 illustrates containment queries on a trimmed torus, a problem with broad applications in computer graphics, including CAD model processing, B-Rep ray tracing, and tessellation of trimmed surfaces. Figure 2. Containment queries on a trimmed torus. The opaque region represents the retained surface, while the translucent part is trimmed away. Points on the torus are randomly sampled; those inside the trimmed region are marked in red, and those outside are shown in green. Containment queries arise in a variety of CAD and modeling contexts. During Boolean operations between parametrically represented solids, numerous intersection edges are generated (Figure 3 ). Curve segments that lie on the underlying geometric surface but outside the trimmed region must be removed, which requires point–surface containment tests. Similarly, in ray-traced rendering of B-Rep models, rays may intersect the underlying surface at positions that must be verified as belonging to the trimmed region. Containment queries are also integral to trimmed-surface tessellation, where sample points in the parameter domain are classified as inside or outside the trimmed region before rendering. In B-Rep, curves on surfaces are represented by a pair of mappings: a curve in physical space and its corresponding projection in the parameter domain, known as a p-curve . With p-curves, containment testing on non-periodic surfaces reduces to a 2D inside–outside test in the parameter domain. Ray-casting methods are commonly used for this purpose, but they are prone to corner cases and numerical instability. Winding-number–based methods, in contrast, are more robust but computationally expensive. Containment queries on periodic domains are particularly challenging because the underlying topology alters how boundaries are represented. For example, when the geometric surface is cylindrical (Figure 4 ), the trimmed region is defined by separation loops. In such cases, the p-curves may not form closed loops in parameter domain, making standard trimming techniques such as ray casting or direct winding-number evaluation inadequate. In this paper, we present a fast and robust framework for containment queries on trimmed surfaces. To ensure robustness against geometric and numerical errors, we adopt the winding number as the criterion for inside–outside classification. We introduce an efficient acceleration structure for winding-number evaluation based on ellipse bounds of Bézier curves, and extend the formulation to periodic domains by lifting the computation to the universal covering space. Our main contributions are as follows: • We introduce a novel recursive scheme that accelerates winding-number evaluation by bounding Bézier segments with ellipse regions, avoiding O(n^{2}) curve subdivision and achieving linear-time complexity. • We formulate containment queries on periodic surfaces in the universal covering space, enabling robust computation for loops that are non-contractible or discontinuous in parameter domain. • We demonstrate the use of our algorithm for robust tessellation of trimmed surfaces and interactive design of complex periodic geometries. The remainder of this paper is organized as follows. Section 2 reviews previous work on containment queries and curve evaluation. Section 3 presents the preliminaries. Section 4 details the proposed winding-number computation and its extension to periodic domains. Section 5 reports experimental comparisons and applications. Section 6 discusses limitations and directions for future work, and Section 7 concludes the paper. Figure 3. Topological intersection between two faces. Extraneous portions of the intersection curve must be removed using point–surface containment queries. 2. Related Work 2.1. Containment Queries for Non-Parametric Boundaries We first review containment query methods developed for non-parametric geometries such as line segments, polygons, and triangular meshes. These problems have been extensively studied in the computer graphics community, primarily through two families of techniques: ray casting and winding number computation. Ray casting. Ray casting is the most widely used approach for point-in-solid classification, both in two-dimensional polygons and three-dimensional meshes. The method shoots a ray from the test point in a fixed direction and counts intersections with the object boundary. By the Jordan curve theorem, an odd number of crossings indicates an interior point, while an even number indicates an exterior one. Ray casting can be accelerated through spatial data structures such as KD-trees and bounding volume hierarchies (BVH) ( Rubin and Whitted 1980 ; Goldsmith and Salmon 1987 ) . For rendering purposes, modern frameworks also support GPU acceleration and parallel ray traversal ( Parker et al. 2010 ) . Despite its success in photo-realistic rendering, ray casting suffers from robustness issues in geometry processing. It fails for open or non-manifold boundaries, since the Jordan theorem applies only to closed curves. In practice, ray-casting failures often occur at degenerate intersections, coincident edges, or geometric inconsistencies (Figure 5 ).

Read the complete text