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

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

基于扫描跟踪元的快速碰撞检测

针对扫描实体在碰撞检测中的应用,提出一种基于扫描跟踪元的快速碰撞检测算法.首先根据运动模型上的采样点构造扫描元曲线群;然后沿着运动路径建立截平面,通过截平面与扫描元曲线群的交点构建特殊平面网格,提取出该平面网格的外轮廓顶点集;最后通过外轮廓点集构造扫描跟踪元.通过扫描跟踪元与环境的相交性检测,能快速、有效地检测出碰撞区域和碰撞时间.实验结果表明,该算法能在保证高精度检测的前提下有效地减少计算量,提高工作效率,因而具有较高的应用价值.     

Identifying faces in a 2D line drawing representing a manifold object

A straightforward way to illustrate a 3D model is to use a line drawing. Faces in a 2D line drawing provide important information for reconstructing its 3D geometry. Manifold objects belong to a class of common solids and most solid systems are based on manifold geometry. In this paper, a new method is proposed for finding faces from single 2D line drawings representing manifolds. The face identification is formulated based on a property of manifolds: each edge of a manifold is shared exactly by two faces. The two main steps in our method are (1) searching for cycles from a line drawing and (2) searching for faces from the cycles. In order to speed up the face identification procedure, a number of properties, most of which relate to planar manifold geometry in line drawings, are presented to identify most of the cycles that are or are not real faces in a drawing, thus reducing the number of unknown cycles in the second searching. Schemes to deal with manifolds with curved faces and manifolds each represented by two or more disjoint graphs are also proposed. The experimental results show that our method can handle manifolds previous methods can handle, as well as those they cannot.     

A Topological Approach to Voxelization

We present a novel approach to voxelization, based on intersecting the input primitives against intersection targets in the voxel grid. Instead of relying on geometric proximity measures, our approach is topological in nature, i.e., it builds on the connectivity and separability properties of the input and the intersection targets. We discuss voxelization of curves and surfaces in both 2D and 3D, and derive intersection targets that produce voxelizations with various connectivity, separability and thinness properties. The simplicity of our method allows for easy proofs of these properties. Our approach is directly applicable to curved primitives, and it is independent of input tessellation.     

基于三视图的曲面体重建技术

根据空间二次曲线的投影特征，首先利用“五点法”分两步来构造投影曲线，得到投影二次曲线的几何参数表达式，然后应用“点对应匹配法”由各视图相应的投影曲线构造空间二次曲线的坐标式参数方程，并同时构造出空间曲线边的支撑平面，从而建立与三视图相对应的曲面体线框模型，最后，提取线框模型中的面信息，并根据二流形体的性质和莫比乌斯法则（Moebius rule)以及正投影规律，对候选面进行组合判定，将实用面进行装配，得到重建结果的实体模型，这种方法将处理对象拓展到了任意投影方位下的二次曲线。     

The equation of the curved edge for isoparametric cubic finite elements

We derive the equation of the actual curve that results when a curved edge is approximated using an isopaiametric cubic finite element. This implied curve depends only on the parameters of the nodes associated with the curved side and does not depend on the shape of the element or on the basis functions used. By choosing a special set of basis functions for a nine-parameter cubic triangle we obtain an isoparametric transformation with a simple form that lends itself to elementary analysis. For triangular finite elements, both the Lagrange and Hermite interpolants are considered. A special case is described which permits an important class of cubic curves to be exactly matched very simply by an appropriate choice of mid-side nodes.     

Handling sectional views in volume-based approach to automatically construct 3D solid from 2D views

This paper presents an algorithm for solid model reconstruction from 2D sectional views based on volume-ba`sed approach. None of the existing work in automatic reconstruction from 2D orthographic views have addressed sectional views in detail. It is believed that the volume-based approach is better suited to handle different types of sectional views. The volume-based approach constructs the 3D solid by a boolean combination of elementary solids. The elementary solids are formed by sweep operation on loops identified in the input views. The only adjustment to be made for the presence of sectional views is in the identification of loops that would form the elemental solids. In the algorithm, the conventions of engineering drawing for sectional views, are used to identify the loops correctly. The algorithm is simple and intuitive in nature. Results have been obtained for full sections, offset sections and half sections. Future work will address other types of sectional views such as removed and revolved sections and broken-out sections.     

任意摆放的二次曲面体的三维重建

本文采用特征点匹配的方法,先由二维视力获取三维空间的点和曲线,然后经过一系列线性运算得出三维曲面。本算法可对任意二次曲面进行三维重建,不仅对曲面的空间摆放沿有限制,而且对曲面自身的对称性也无要求。因此,可将重建对象扩展为圆柱、椭圆柱、球、椭球、双曲面、抛物面等。本文给出的算例表明了算法的有效性。     

Image‐based modeling of 3D objects with curved surfaces

This paper addresses an image‐based method for modeling 3D objects with curved surfaces based on the non‐uniform rational B‐splines (NURBS) representation. The user fits the feature curves on a few calibrated images with 2D NURBS curves using the interactive user interface. Then, 3D NURBS curves are constructed by stereo reconstruction of the corresponding feature curves. Using these as building blocks, NURBS surfaces are reconstructed by the known surface building methods including bilinear surfaces, ruled surfaces, generalized cylinders, and surfaces of revolution. In addition to them, we also employ various advanced techniques, including skinned surfaces, swept surfaces, and boundary patches. Based on these surface modeling techniques, it is possible to build various types of 3D shape models with textured curved surfaces without much effort. Copyright © 2007 John Wiley & Sons, Ltd.     

Image-Swept Volumes

Many graphical objects can be represented by swept volumes (including its subset — generalised cylinders) by sweeping 2D or 3D templates along 3D trajectories. In this paper, we present a new approach for constructing swept volumes using image templates. We utilise scalar fields as our underlying data type, and employ volume ray casting techniques for rendering swept volumes in their original sweeping specifications as well as in their voxelised approximations. In addition to some simple image‐swept volumes, we also treat multi‐channel image templates, video templates, generalised sweeps, and self‐intersecting trajectories. This approach enables us to model swept volumes with heterogeneous interiors and amorphous effects. It also facilitates the use of constructive volume geometry for creating complex scenes in both modelling and rendering space.     

NURBS扫描体的逼近算法研究

提供了一种NURBS扫描体的逼近方法。该方法主要步骤：(1)通过系列平面切割,把NURBS曲面(实体)进行降维处理,变成平面曲线;(2)为曲线设置局部标架;(3)在局部标架下求出每一曲线在每一时刻的极值点后将其转换成原曲线的奇异点;(4)使用marching cubes算法剔除扫描体内部点,保留扫描体边界上的奇异点;(5)由所有保留点拟合成奇异曲面。本算法能较好地逼近NURBS扫描体,其逼近精度可通过控制切割精度和扫描过程中时间间隔的选取而得到有效控制。     

Recognizing 3D Objects Using Tactile Sensing and Curve Invariants

A general paradigm for recognizing 3D objects is offered, and applied to some geometric primitives (spheres, cylinders, cones, and tori). The assumption is that a curve on the surface, or a pair of intersecting curves, was measured with high accuracy (for instance, by a sensory robot). Differential invariants of the curve(s) are then used to recognize the surface. The motivation is twofold: the output of some devices is not surface range data, but such curves. Also, a considerable speedup is obtained by using curve data, as opposed to surface data which usually contains a much higher number of points.We survey global, algebraic methods for recognizing surfaces, and point out their limitations. After introducing some notions from differential geometry and elimination theory, the differential and semi-differential approaches to the problem are described, and novel invariants which are based on the curve's curvature and torsion are derived.     

Domain decomposition method for elliptic mixed boundary value problems

A method for solving the elliptic second order mixed boundary value problem is discussed. The finite element problem is divided into subproblems, associated with subregions into which the region has been partitioned, and an auxiliary problem connected with intersect curves. The subproblems are solved directly, while the auxiliary problem is handled by a conjugate gradient method. The rate of the convergence of the cg-method is discussed also for the cases when the Neumann and Dirichlet boundary conditions change at points belonging to the intersecting curves. Results from numerical experiments are also reported.     

Detection of loops and singularities of surface intersections

Two surface patches intersecting each other generally at a set of points (singularities), form open curves or closed loops. While open curves are easily located by following the boundary curves of the two patches, closed loops and singularities pose a robustness challenge since such points or loops can easily be missed by any subdivision or marching-based intersection algorithms, especially when the intersecting patches are flat and ill-positioned. This paper presents a topological method to detect the existence of closed loops or singularities when two flat surface patches intersect each other. The algorithm is based on an oriented distance function defined between two intersecting surfaces. The distance function is evaluated in a vector field to identify the existence of singular points of the distance function since these singular points indicate possible existence of closed intersection loops. The algorithm detects the existence rather than the absence of closed loops and singularities. This algorithm requires general C² parametric surfaces.     

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.     

Display of profiled sweep objects

A class of free-form solids called profiled sweep objects is defined by four parametric curves: a 2D contour (cross-section), a 3D trajectory (spine), and two profile curves, which control the scaling of the contour as it moves along the trajectory. Subclasses of this are profiled prisms, which have a linear trajectory, and profiled generalized cylinders, which have an arbitrary 3D trajectory. First an exact definition of profiled sweep object, is presented and their relation with common sweep objects is described. Then a method is given for the construction of planar approximations of these objects that can be used for fast display generation. Finally, ray-tracing algorithms are given that directly use the exact definition for high-quality display.     

A flexible multi-volume shader framework for arbitrarily intersecting multi-resolution datasets

We present a powerful framework for 3D-texture-based rendering of multiple arbitrarily intersecting volumetric datasets. Each volume is represented by a multi-resolution octree-based structure and we use out-of-core techniques to support extremely large volumes. Users define a set of convex polyhedral volume lenses, which may be associated with one or more volumetric datasets. The volumes or the lenses can be interactively moved around while the region inside each lens is rendered using interactively defined multi-volume shaders. Our rendering pipeline splits each lens into multiple convex regions such that each region is homogenous and contains a fixed number of volumes. Each such region is further split by the brick boundaries of the associated octree representations. The resulting puzzle of lens fragments is sorted in front-to-back or back-to-front order using a combination of a view-dependent octree traversal and a GPU-based depth peeling technique. Our current implementation uses slice-based volume rendering and allows interactive roaming through multiple intersecting multi-gigabyte volumes.     

Partitioning polyhedral objects into nonintersecting parts

An algorithm is described for partitioning intersecting polyhedrons into disjoint pieces and, more generally, removing intersections from sets of planar polygons embedded in three space. Polygons, or faces, need not be convex and may contain multiple holes. Intersections are removed by considering pairs of faces and slicing the faces apart along their regions of intersection. To reduce the number of face pairs examined, bounding boxes around groups of faces are checked for overlap. The intersection algorithm also computes set-theoretic operations on polyhedrons. Information gathered during face cutting is used to determine which portions of the original boundaries may be present in the result of an intersection, a union, or a difference of solids. The method includes provisions to detect and in some cases overcome, the effects of numerical inaccuracy on the topological decisions that the algorithm must make. The regions in which ambiguous results are possible are flagged so that the user can take appropriate action