Finding Starting Points for Tracing Surface Intersections

To find starting points for all the intersection curves, one of the surfaces is subdivided into some small surface patches. Based on a correlative algorithm of computing the minimum distance of two surfaces, the intersections of every patch with another surface are detected, and starting points are calculated by dichotomy. This algorithm shows superior efficiency in the computational complexity and number of iterations needed. It can be used to determine exact starting points on all possible solution curves between any kinds of parametric sculptured surfaces.     

Finding Starting Points for Tracing Surface Intersections

1 Introduction Finding out proper starting points for all the intersection curves between two surfaces is a key process in numerical tracing methods for surface-surface intersection (SSI) problems. A number of methods [1] are introduced to calculate the starting points. Cugini et al. [2] introduced the concept of shrinking bounding boxes to calculate starting points. This method is simple and in some cases effective, but it may miss some intersection components. Muellenheim [3] presented an…     

运动曲面求交优化算法

运动曲面求交通常采用曲面求交算法，通过反复迭代求取曲面交线，没有考虑运动曲面自身的特性进行求交简化．由于运动曲面不同运动瞬间的曲面交线之间存在必然联系，因此通过对曲面内在属性分析，提出了运用运动曲面不同运动瞬间曲面交线相似性进行运动曲面求交的优化算法．首先对两个运动曲面的基曲面进行预处理。获取表征曲面交线拓扑的特征点；根据特征点分布图确定不同运动瞬间曲面交线起始点搜索策略，采用跟踪法动态调整步长和跟踪方向求解整个交线环．采用文中方法可以有效地解决运动曲面的子环、奇点遗漏、分支跳跃、乱序跟踪和初始点求取问题，精确、鲁棒、快速地计算出交线．     

参数曲线曲面实奇异点的计算

本文主要讨论了利用Grobner基理论对参数曲线（面）的奇异点进行判断和计算。如果曲线（面）存在奇异点,由定义可知它的导矢（法矢）等于0。因此,曲线（面）奇异点的判定就是方程组的求解问题。由Hilbert弱零点定理可知,若一组多项式方程无公共零点,则其生成理想约化的Grobner基为[1]。在计算时,首先根据Grobner基理论判断 曲线（面）是否存在奇异点。当存在奇异点时,利用区间算法对实奇异点进行隔离和迭代。在确定奇异点的存在性时,根据曲线（曲面）的导矢（法矢）方程的Grobner基直 接进行判断,而不需要求解非线性代数方程组。若曲线曲面存在奇异点,进一步采用区间方法对奇异点进行隔离以确定曲线段或曲面片的正则性。该方法可以得到参数曲线曲面的所有实奇异点且达到任意精度。     

Determining distance to a surface represented in piecewise fashion with surface patches

A previously reported method for finding the points of intersection of a vector and a parametric surface patch is examined. However, before the point of intersection of a vector and a patch can be determined, it is necessary to find the patch (or patches) on a multipatch surface intersected by the vector. A technique is described for determining the patch or patches intersected by a vector, given the patches intersected by a single plane containing the intersecting vector. Once these have been found, the point of intersection can be determined and the distance to the multipatch surface obtained.     

Visualizing nonmanifold and singular implicit surfaces with point clouds

We use octree spatial subdivision to generate point clouds on complex nonmanifold implicit surfaces in order to visualize them. The new spatial subdivision scheme only uses point sampling and an interval exclusion test. The algorithm includes a test for pruning the resulting plotting nodes so that only points in the closest nodes to the surface are used in rendering. This algorithm results in improved image quality compared to the naive use of intervals or affine arithmetic when rendering implicit surfaces, particularly in regions of high curvature. We discuss and compare CPU and GPU versions of the algorithm. We can now render nonmanifold features such as rays, ray-like tubes, cusps, ridges, thin sections that are at arbitrary angles to the octree node edges, and singular points located within plot nodes, all without artifacts. Our previous algorithm could not render these without severe aliasing. The algorithm can render the self-intersection curves of implicit surfaces by exploiting the fact that surfaces are singular where they self-intersect. It can also render the intersection curves of two implicit surfaces. We present new image space and object space algorithms for rendering these intersection curves as contours on one of the surfaces. These algorithms are better at rendering high curvature contours than our previous algorithms. To demonstrate the robustness of the node pruning algorithm we render a number of complex implicit surfaces such as high order polynomial surfaces and Gaussian curvature surfaces. We also compare the algorithm with ray casting interms of speed and image quality. For the surfaces presented here, the point clouds can be computed in seconds to minutes on atypical Intel based PC. Once this is done, the surfaces can be rendered at much higher frame rates to allow some degree of interactive visualization.     

A reliable triangular mesh intersection algorithm and its application in geological modelling

We introduce a reliable intersection algorithm for manifold surface meshes. The proposed algorithm builds conforming surface meshes from a set of intersecting triangulated surfaces. This algorithm effectively handles all degenerate triangle–triangle intersection cases. The key idea of the algorithm is based on an extensive set of triangle–edge intersection cases, combined with an intersection curve tracking method. The intersection operations do not rely on global spatial search operations and no remeshing steps are needed. The intersection curves are introduced into each surface mesh using a unique curve imprinting algorithm. The imprinting algorithm naturally handles degenerate intersection cases of many surfaces at an edge or at a point. The algorithm produces a consistent mesh data structure for subsequent mesh optimization operations. The mesh intersection algorithm is used within a general framework for modelling and meshing of geological formations, which are essential for reliable mathematical modelling of oil reservoirs.     

Iterative two-step genetic-algorithm-based method for efficient polynomial B-spline surface reconstruction

Surface reconstruction is a very challenging problem arising in a wide variety of applications such as CAD design, data visualization, virtual reality, medical imaging, computer animation, reverse engineering and so on. Given partial information about an unknown surface, its goal is to construct, to the extent possible, a compact representation of the surface model. In most cases, available information about the surface consists of a dense set of (either organized or scattered) 3D data points obtained by using scanner devices, a today’s prevalent technology in many reverse engineering applications. In such a case, surface reconstruction consists of two main stages: (1) surface parameterization and (2) surface fitting. Both tasks are critical in order to recover surface geometry and topology and to obtain a proper fitting to data points. They are also pretty troublesome, leading to a high-dimensional nonlinear optimization problem. In this context, present paper introduces a new method for surface reconstruction from clouds of noisy 3D data points. Our method applies the genetic algorithm paradigm iteratively to fit a given cloud of data points by using strictly polynomial B-spline surfaces. Genetic algorithms are applied in two steps: the first one determines the parametric values of data points; the later computes surface knot vectors. Then, the fitting surface is calculated by least-squares through either SVD (singular value decomposition) or LU methods. The method yields very accurate results even for surfaces with singularities, concavities, complicated shapes or nonzero genus. Six examples including open, semi-closed and closed surfaces with singular points illustrate the good performance of our approach. Our experiments show that our proposal outperforms all previous approaches in terms of accuracy and flexibility.     

Intersecting a freeform surface with a general swept surface

We present efficient and robust algorithms for intersecting a rational parametric freeform surface with a general swept surface. A swept surface is given as a one-parameter family of cross-sectional curves. By computing the intersection between a freeform surface and each cross-sectional curve in the family, we can solve the intersection problem. We propose two approaches, which are closely related to each other. The first approach detects certain critical points on the intersection curve, and then connects them in a correct topology. The second approach converts the intersection problem to that of finding the zero-set of polynomial equations in the parameter space. We first present these algorithms for the special case of intersecting a freeform surface with a ruled surface or a ringed surface. We then consider the intersection with a general swept surface, where each cross-sectional curve may be defined as a rational parametric curve or as an implicit algebraic curve.     

Determining interference between pairs of solids defined constructively in computer animation

This paper presents theory and implementation of a method for detecting interference between a pair of solid objects. Often at times, when performing simulations, two solids may unwittingly interpenetrate each other. The two components of the system presented in this paper are: (1) a surface representation method to model solid objects; and (2) a method for detecting interference. Body representation of a solid in this system is based upon enveloping each solid with surfaces (called positive entities). Most computer aided design (CAD) systems use solid modeling techniques to represent solid objects. Since most solid models use Boolean operations to model complex objects, a method is presented to envelop complex objects with parametric surfaces. A method for tracing intersection curves between two surfaces is also presented. Discontinuities on surfaces are defined as negative entitics in order to extend the method to complex solids. Determining interference is based upon a numerical algorithm for computing points of intersection between boundary curves and parametrized entities. The existence of segments of these curves inside the boundary of positive and negative entities is established by computing the circulation of a function around the boundary curve. Interference between two solids is then detected. No limitations are imposed on the convexity or simplicity of the boundary curves treated.     

Feature‐Preserving Reconstruction of Singular Surfaces

Reconstructing a surface mesh from a set of discrete point samples is a fundamental problem in geometric modeling. It becomes challenging in presence of ‘singularities’ such as boundaries, sharp features, and non‐manifolds. A few of the current research in reconstruction have addressed handling some of these singularities, but a unified approach to handle them all is missing. In this paper we allow the presence of various singularities by requiring that the sampled object is a collection of smooth surface patches with boundaries that can meet or intersect. Our algorithm first identifies and reconstructs the features where singularities occur. Next, it reconstructs the surface patches containing these feature curves. The identification and reconstruction of feature curves are achieved by a novel combination of the Gaussian weighted graph Laplacian and the Reeb graphs. The global reconstruction is achieved by a method akin to the well known Cocone reconstruction, but with weighted Delaunay triangulation that allows protecting the feature samples with balls. We provide various experimental results to demonstrate the effectiveness of our feature‐preserving singular surface reconstruction algorithm.     

曲面实体造型中曲线和曲面交点的求解

求交是曲面实体造型系统中影响拼合算法效率和稳定性的重要因素，而求交算法又是和曲面的几何表示密切相关的。ＮＵＲＢＳ虽然能统一表示所有曲面，但却给二次曲面的求交带来了不必要的复杂性。二次曲面经常在机械零件的设计中被用来描述轴、孔、槽等几何特征，因此它们的求交算法应具有高精度、高效率和高稳定性。为此，对一种实用的二次曲面表示方法——几何法进行了深入研究后，给出了构成二次曲面轮廓的几种二次曲线和空间四次曲线与二次曲面交点的求法。     

Computing medial axes of generic 3D regions bounded by B-spline surfaces

A new approach is presented for computing the interior medial axes of generic regions in R³ bounded by C⁽⁴⁾-smooth parametric B-spline surfaces. The generic structure of the 3D medial axis is a set of smooth surfaces along with a singular set consisting of edge curves, branch curves, fin points and six junction points. In this work, the medial axis singular set is first computed directly from the B-spline representation using a collection of robust higher order techniques. Medial axis surfaces are computed as a time trace of the evolving self-intersection set of the boundary under the the eikonal (grassfire) flow, where the bounding surfaces are dynamically offset along the inward normal direction. The eikonal flow results in special transition points that create, modify or annihilate evolving curve fronts of the (self-) intersection set. The transition points are explicitly identified using the B-spline representation. Evolution of the (self-) intersection set is computed by adapting a method for tracking intersection curves of two different surfaces deforming over generalized offset vector fields. The proposed algorithm accurately computes connected surfaces of the medial axis as well its singular set. This presents a complete solution along with accurate topological structure.     

Generation of Discrete Bicubic G1 B-Spline Ship Hullform Surfaces from a Given Curve Network Using Virtual Iso-Parametric Curves

We propose a method that automatically generates discrete bicubic G1 continuous B-spline surfaces that interpolate the curve network of a ship hullform. First, the curves in the network are classified into two types: boundary curves and "reference curves". The boundary curves correspond to a set of rectangular (or triangular) topological type that can be represented with tensor-product (or degenerate) B-spline surface patches. Next, in the interior of the patches, surface fitting points and cross boundary derivatives are estimated from the reference curves by constructing "virtual" isoparametric curves. Finally, a discrete G1 continuous B-spline surface is generated by a surface fitting algorithm. Several smooth ship hullform surfaces generated from curve networks corresponding to actual ship hullforms demonstrate the quality of the method.     

Tetrahedra Based Adaptive Polygonization of Implicit Surface Patches

This paper presents a tetrahedra based adaptive polygonization technique for tessellating implicit surface patches. An implicit surface patch is defined as an implicit surface bounded by its intersections with a set of clipping surfaces and which lies within an enclosing tetrahedron. To obtain the polygonization of an implicit surface patch, the tetrahedron containing the patch is adaptively subdivided into smaller tetrahedra according to the criteria introduced in the paper. The result is a set of tetrahedra each containing a facet approximating the surface. The intersections between the facets and the clipping surfaces are used to locate the surface patch boundary. Ambiguous results in generating the facets for highly curved surfaces or surfaces with singular points are also addressed. The result of the polygonization is a set of triangular facets that can be used for visualization and numerical analysis. The proposed method is also suitable for locating the intersection of two implicit surfaces.     

On the workspace boundary determination of serial manipulators with non-unilateral constraints

Broadly applicable analytical algorithms for workspace of serial manipulators with non-unilateral constraints are developed and illustrated. The Jacobian row-rank deficiency method is employed to determine the singularities of these manipulators. There are four types of singularity sets: Type I: position Jacobian singularities; Type II: instantaneous singularities that are due to a generalized joint that is reaching its apex; Type III: domain boundary singularities, which are associated with the initial and final values of the time interval; Type IV: coupled singularities, which are associated with a relative singular Jacobian, where the null space is reduced in one sub-matrix due to either of two occurrences: a Type II or a Type III singularity. All of the singular surfaces are hypersurfaces that extend internally and externally the workspace envelope. Intersecting singular surfaces identifies singular curves that partition singular surfaces into subsurfaces, and a perturbation method is used to identify regions (curve segments/surface patches) of the hypersurfaces that are on the boundary. The formulation is illustrated by implementing it to a spatial 3-degree of freedom (DOF) and a spatial 4-DOF manipulator.     

Quart-parametric interpolations for intersecting paths

The intersecting path is an important tool path generation method. This paper proposes an approach for the quart-parametric interpolation of intersecting paths. The objective of our approach is that the intersecting paths for surface machining can be directly interpolated within the computer numerical control (CNC) system. This enables the CNC interpolator to process the intersecting paths without geometric approximation as in existing approaches and take into consideration any specific feedrate profiles and further machining dynamical issues along the path.The interpolation of the intersection of two general parametric surfaces is transferred into interpolation of its projection curves and the time trajectories of four parameters along the intersecting curves are obtained. Our strategy is to carry out the quart-parametric interpolation based on the projection interpolation. The feedrate control method is developed, and then the interpolation algorithms for two projection curves are proposed. An error reduction scheme is presented to alleviate point deviation from the drive parametric surface. Simulations of quart-parametric interpolation have been carried out to verify the effectiveness of the proposed algorithm.     

Performing Efficient NURBS Modeling Operations on the GPU

We present algorithms for evaluating and performing modeling operations on NURBS surfaces using the programmable fragment processor on the Graphics Processing Unit (GPU). We extend our GPU-based NURBS evaluator that evaluates NURBS surfaces to compute exact normals for either standard or rational B-spline surfaces for use in rendering and geometric modeling. We build on these calculations in our new GPU algorithms to perform standard modeling operations such as inverse evaluations, ray intersections, and surface-surface intersections on the GPU. Our modeling algorithms run in real time, enabling the user to sketch on the actual surface to create new features. In addition, the designer can edit the surface by interactively trimming it without the need for retessellation. Our GPU-accelerated algorithm to perform surface-surface intersection operations with NURBS surfaces can output intersection curves in the model space as well as in the parametric spaces of both the intersecting surfaces at interactive rates. We also extend our surface-surface intersection algorithm to evaluate self-intersections in NURBS surfaces.     

Reconstruction of intersecting curved solids from 2D orthographic views

This paper presents a new approach to reconstruct curved solids composed of elementary volumes intersecting with one another from three-view engineering drawings. Intersection curves arising from two intersecting curved surfaces are mostly higher order spatial curves, which cannot be described exactly by 2D orthographic projections and normally represented as smooth curves passing through several key points or even simplified as arcs or lines. Approximated sketches of higher order intersection curves in 2D views result in the invalidation of existing methods that need the exact projection information as input. Based on some heuristic hints, our method is able to recover the complete and correct half-profiles of the intersecting elementary volumes using the least traces left by them, which ensure the correctness of solution solids constructed finally. Several examples are provided to show the validation of the described method.