Extraction of cylinders and cones from minimal point sets

We propose new algebraic methods for extracting cylinders and cones from minimal point sets, including oriented points. More precisely, we are interested in computing efficiently cylinders through a set of three points, one of them being oriented, or through a set of five simple points. We are also interested in computing efficiently cones through a set of two oriented points, through a set of four points, one of them being oriented, or through a set of six points. For these different interpolation problems, we give optimal bounds on the number of solutions. Moreover, we describe algebraic methods targeted to solve these problems efficiently.     

MESSAGE——具有自由曲面造型功能的立体造型系统

MESSAGE是一具有自由曲面造型功能的立体造型系统,它能够处理二次曲面、旋转曲面、 广义sweeping曲面、自由曲面以及由平面和上述曲面围成的三维物体,系统以平面及双三次 有理B样条曲面为基本曲面模型,提供了布尔运算、glue运算及多种局部修改运算.系统还 具有一个独立的几何数据库,可以支持一些重要的工程应用.     

Robust segmentation of primitives from range data in the presenceof geometric degeneracy

This paper addresses a common problem in the segmentation of range images. We present methods for the least-squares fitting of spheres, cylinders, cones, and tori to 3D point data, and their application within a segmentation framework. Least-squares fitting of surfaces other than planes, even of simple geometric type, has rarely been studied. Our main application areas of this research are reverse engineering of solid models from depth-maps and automated 3D inspection where reliable extraction of these surfaces is essential. Our fitting method has the particular advantage of being robust in the presence of geometric degeneracy, i.e., as the principal curvatures of the surfaces being fitted decrease, the results returned naturally become closer and closer to those surfaces of “simpler type”, i.e., planes, cylinders, cones, or spheres, which best describe the data. Many other methods diverge because, in such cases, various parameters or their combination become infinite     

An Energy‐Conserving Hair Reflectance Model

We present a reflectance model for dielectric cylinders with rough surfaces such as human hair fibers. Our model is energy conserving and can evaluate arbitrarily many orders of internal reflection. Accounting for compression and contraction of specular cones produces a new longitudinal scattering function which is non‐Gaussian and includes an off‐specular peak. Accounting for roughness in the azimuthal direction leads to an integral across the hair fiber which is efficiently evaluated using a Gaussian quadrature. Solving cubic equations is avoided, caustics are included in the model in a consistent fashion, and more accurate colors are predicted by considering many internal pathways.     

Inverse perspective transform using zero-curvature contour points:application to the localization of some generalized cylinders from asingle view

The localization of some kinds of modeled generalized cylinders from a single brightness perspective image is addressed. It is shown how the zero-curvature points of their contours can be used to solve the inverse perspective problem. Three key theorems about the perspective projection of space curves and of the limbs of a straight homogeneous generalized cylinder whose scaling function has at least one zero-curvature point are discussed. In view of the localization of homogeneous generalized cylinders, an algorithm previously developed by the authors which estimates the pose of a line-triplet is adapted. A new theoretical result about the inverse perspective projection of cones of revolution useful for the localization of objects of revolution is presented. The corresponding algorithms have been implemented, and results of experiments demonstrate the feasibility of the proposed localization methods     

Checking similarity of planar figures

Two planar figures aresimilar if a scaled version of one of them can be moved so that it coincides with the second figure. The problem of checking whether two planar figures are similar is relevant to both computational geometry and pattern recognition. An efficient algorithm is known for checking whether two polygonsP andQ are similar⁽¹⁾ The purpose of this note is to give an efficient algorithm for checking whether two planar figuresP andQ are similar when the figures are no longer constrained to be polygons. We give anO(n logn) time algorithm for solving this problem when each figure consists of a collection of (possibly intersecting) straight line segments, circles, and ellipses. Our algorithm can easily be modified for figures which include other geometric patterns as well. We also prove that our algorithm is optimal.This work was partially supported by the Office of Naval Research under Contract N00014-84-K-0502.     

Combinatorial Construction of Seamless Parameter Domains

The problem of seamless parametrization of surfaces is of interest in the context of structured quadrilateral mesh generation and spline-based surface approximation. It has been tackled by a variety of approaches, commonly relying on continuous numerical optimization to ultimately obtain suitable parameter domains. We present a general combinatorial seamless parameter domain construction, free from the potential numerical issues inherent to continuous optimization techniques in practice. The domains are constructed as abstract polygonal complexes which can be embedded in a discrete planar grid space, as unions of unit squares. We ensure that the domain structure matches any prescribed parametrization singularities (cones) and satisfies seamlessness conditions. Surfaces of arbitrary genus are supported. Once a domain suitable for a given surface is constructed, a seamless and locally injective parametrization over this domain can be obtained using existing planar disk mapping techniques, making recourse to Tutte's classical embedding theorem.     

基于遗传算法的平面图画图算法

提出了一种基于遗传算法的新的平面图画图算法，算法将平面图画图问题转化为约束优化问题，用遗传算法求解目标函数的最优解的近似值，从而得到平面图的平面直线画法．新算法的优点是：方法简单，易于实现，画出的图形美观．实验结果表明：算法画出的图形要比文献[8]中的算法画出的图形美观，而其收敛性则要高于标准遗传算法．     

Implementation of two hidden-line algorithms

Two hidden-line elimination programs are described. One removes the hidden lines from vector-type projections of planar-faced 3D objects. This program implements the Loutrel algorithm which has been extended here to solids with multiply-connected faces. The other is applicable to solids bounded by sections of quadric surfaces (i.e. cylinders, cones, spheres, ellipsoids, paraboloids and hyperboloids) and represents an implementation of the Woon algorithm. The latter can be regarded as an extension of the Loutrel algorithm to curved-surface bodies. Both programs generate true, visible-line perspective projections for output on a digital plotter or a vector-type CRT display. The implementation of these algorithms for a variety of computer systems is described.     

Representation of Dupin cyclides using quaternions

Dupin cyclides are surfaces characterized by the property that all their curvature lines are circles or lines. Spheres, circular cylinders, cones and tori are particular examples. We introduce a bilinear rational Bézier-like formula with quaternion weights for parametrizing principal patches of Dupin cyclides. The proposed construction is not affine invariant but it is Möbius invariant, has lower degrees compared with the standard representation, and it is convenient for offsetting. Several important properties of Dupin cyclides can be recovered in terms of closed quaternion formulas: implicit equation, principal curvatures, representation as canal surfaces. Advantages of this approach are demonstrated by deriving a new formula for the Willmore energy of a principal patch.     

Inverse Displacement Mapping

Inverse displacement mapping is a variant of displacement mapping which does not actually perturb the geometry of the surface being mapped. It is thus a true texture mapping technique which can be applied during rendering without breaking viewing pipeline discipline. The method works by first projecting probing rays into texture space and solving for a ray-texture intersection there. Shadows can also be determined by mapping a probe from the intersection point towards the light source into texture space and seeing if an intersection results. Our implementation uses as much knowledge about the base surface as possible to speed up the ray-surface intersection calculation. We have limited our treatment to spheres, cones, cylinders and planes, and our rendering method to ray casting, in order to contain the scope of this work up to the present. The inverse displacement mapping technique can, however, be applied more widely, for example as part of a full ray-tracer, and also as part of the rendering pipeline for a wider class of smooth surfaces.     

基于辐射屏蔽体的建模及可视化研究

辐射屏蔽体可用直角三角柱、圆锥台体等一些基本的三维几何图形来描述。该文以直角三角柱、圆柱体为例说明了三维图形的建模及绘制过程。对于一次函数的几何图形，先确定其顶点的空间位置，然后由所定的顶点画出每个面，最后组合成三维实体。对于属于二次函数的图形，用空间解析法建立了数学模型。采用空间坐标变换法，在标准位置置上绘制二次函数的图形后，再转换到已知条件所定的位置来显示．可大幅度简化绘制过程。     

水稻稻穗形态建模及其可视化研究

利用一元二次方程曲线来描述弯曲型稻穗穗轴轴心线形态,连接以曲线弦线段为轴心的圆柱,构建了穗轴和枝梗轴的形态模型,通过两个共底面的圆锥体建立小穗谷粒的几何形态模型,实现了稻穗三维显示.模型具有较高的真实感效果,可控性强,可满足稻穗数字化设计的需要.     

Analysis of quadric-surface-based solid models

The author discusses data representations and analytical tools commonly used in solid modelers for three analysis operations: boundary evaluation, image generation, and mechanical property calculation. The methods described are generally applicable to solid models bounded by quadric surfaces (e.g. planes, cylinders, spheres, and cones). Only methods applicable to constructive solid geometry or boundary representation modelers are considered. The author concludes with a review of ongoing research into other analysis operations appropriate for solid modeling representations     

Splines in the parameter domain of surfaces and their application in filament winding

For non-axisymmetric filament winding in the composite industry, it is difficult to automatically design fiber paths with uniform distribution, full coverage, and non-slippage. Geodesics and semi-geodesics are commonly used as non-slippage trajectories in the fiber path design. However, the uniqueness of these curves from the initial conditions severely restricts the freedom of design, which plays an important role in producing high performance parts. This paper presents a new class of trajectories with more freedom by generalizing splines, and gives the conditions to make these splines on cylinders and cones stable. The proposed trajectory has been applied to filament winding on elbows. Practical results show that the fiber distribution is excellent, and the finished product has extremely uniform thickness.     

二射影对应面束与二次曲面

利用正投影法首次系统说明了固有线为底的二射影对应面束,如果平移或 旋转其中之一,可以分别形成各种二次柱面、二次锥面、单叶双曲面和双曲抛物面。二射影 对应面束,如果选择合适的截平面,可以得到两对对应合同线束。合同线束是否同向共面是 二次曲面存在圆截口的充分必要条件。     

Discovery of Intrinsic Primitives on Triangle Meshes

The discovery of meaningful parts of a shape is required for many geometry processing applications, such as parameterization, shape correspondence, and animation. It is natural to consider primitives such as spheres, cylinders and cones as the building blocks of shapes, and thus to discover parts by fitting such primitives to a given surface. This approach, however, will break down if primitive parts have undergone almost‐isometric deformations, as is the case, for example, for articulated human models. We suggest that parts can be discovered instead by finding intrinsic primitives, which we define as parts that posses an approximate intrinsic symmetry. We employ the recently‐developed method of computing discrete approximate Killing vector fields (AKVFs) to discover intrinsic primitives by investigating the relationship between the AKVFs of a composite object and the AKVFs of its parts. We show how to leverage this relationship with a standard clustering method to extract k intrinsic primitives and remaining asymmetric parts of a shape for a given k. We demonstrate the value of this approach for identifying the prominent symmetry generators of the parts of a given shape. Additionally, we show how our method can be modified slightly to segment an entire surface without marking asymmetric connecting regions and compare this approach to state‐of‐the‐art methods using the Princeton Segmentation Benchmark.     

Two algorithms for volume-preserving approximations of surfaces of revolution

The paper deals with volume-preserving approximations of surfaces of revolution. The approximating surfaces are generated only by line segments and circular arcs of a constant radius r. Further, for r > 0, the approximating surfaces are visually C¹ surfaces. For r = 0, developable C⁰ surfaces are obtained (consisting of either congruent cylinders or frustums of cones of revolution). Two algorithms are discussed. The first algorithm preserves the volume enclosed by a surface of revolution and the planes of every two latitude circles; the approximating surface is, however, no longer a surface of revolution. The second algorithm applies an approximating surface of revolution; however, the volume preservation no longer holds globally.