Multi-directional blending for heterogeneous objects

This paper presents a novel multi-directional blending method for heterogeneous object design. Contrary to earlier studies, this paper introduces material blending through multiple features with different heterogeneous material composition. Feature-based method is used to represent and design heterogeneous objects with multi-directional material composition. The Voronoi diagram of multiple curves is constructed to generate bisector of the geometric domain. Then, metamorphosis from the bounding curve to multiple internal curves is performed using dynamic programming based optimization approach in two steps. First, optimum curve matching between internal curves and enclosing Voronoi cells is obtained. Then, an optimum ruling line alignment and insertion technique between the Voronoi diagram and the bounding curve is developed. Metamorphosis through complex concavities is also achieved. Finally, multi-directional material composition is mapped based on a set of relations.     

Parametric G n blending of curves and surfaces

We introduce a simple blending method for parametric curves and surfaces that produces families of parametrically defined, G ⁿ –continuous blending curves and surfaces. The method depends essentially on the parameterizations of the curves/surfaces to be blended. Hence, the flexibility of the method relies on the existence of suitable parameter transformations of the given curves/surfaces. The feasibility of the blending method is shown by several examples. The shape of the blend curve/surface can be changed in a predictable way with the aid of two design parameters (thumb weight and balance).     

平面上可相交凸多边形的Voronoi图

传统的多边形的Voronoi图存在不能相交的问题,以至于无法将其应用于计算机视觉、生态学等领域中的多边形相交情况.为了解决多边形相交情况下的最邻近空间划分问题,提出了可相交凸多边形的Voronoi图.首先定义可相交凸多边形的Voronoi图;然后阐述相交多边形特有的Voronoi边的区域化现象,证明了其发生的充要条件,进一步揭示了相交多边形与不相交多边形之间的关系;最后提出Voronoi图的生成算法,并用代码实现.实验结果表明,该算法能够有效地解决多边形相交的问题,突破了不能相交的限制,为计算机视觉、生态学等领域的实际应用提供了理论基础.     

Dynamic polar diagram

The polar diagram [C.I. Grima, A. Márquez, L. Ortega, A new 2D tessellation for angle problems: The polar diagram, Computational Geometry 34 (2006) 58-74] of a set of points on the plane and the contracted dual of polar diagram (CDPD) [B. Sadeghi Bigham, A. Mohades, The dual of polar diagrams and its extraction, in: International Conference of Computational Methods in Sciences and Engineering ICCMSE, vol. 7, Greece, 2006, pp. 451-454] have been introduced recently. In this paper, we introduce the Dynamic Polar Diagram and present an algorithm to find it using CDPD and a hash structure for point location problem. In the dynamic polar diagram, the points can be added to or removed from the point set. For this problem, a brute-force method runs in O(nlogn) time and also there is a sketch of an algorithm in [C.I. Grima, A. Márquez, L. Ortega, A new 2D tessellation for angle problems: The polar diagram, Computational Geometry 34 (2006) 58-74] that takes O(n) time in all cases (best, average and worst). In our approach, we first determine an area out of which the polar diagram does not change due to insertion or deletion of a site. Then we present a new algorithm to solve the problem in O(kp) time where kp is the number of the sites whose polar regions are affected by the new addition or deletion of p.     

Recognition of docking sites on a protein using β-shape based on Voronoi diagram of atoms

A protein consists of atoms. Given a protein, the automatic recognition of depressed regions on the surface of the protein, often called docking sites or pockets, is important for the analysis of interaction between a protein and a ligand and facilitates fast development of new drugs.Presented in this paper is a geometric approach for the detection of docking sites using β-shape which is based on the Voronoi diagram for atoms in Euclidean distance metric. We first propose a geometric construct called a β-shape which represents the proximity among atoms on the surface of a protein. Then, using the β-shape, which takes the size differences among different atoms into account, we present an algorithm to extract the pockets for the possible docking site on the surface of a protein.     

Rendering traditional mosaics

This paper discusses the principles of traditional mosaics and describes a technique for implementing a digital mosaicing system. The goal of this work is to transform digital images into traditional mosaic-like renderings. We achieve this effect by recovering free-form feature curves from the image and laying rows of tiles along these curves. Composition rules are applied to merge these tiles into an intricate jigsaw that conforms to classical mosaic styles. Mosaic rendering offers the user flexibility over every aspect of this craft, including tile arrangement, shapes, and colors. The result is a system that makes this wonderful craft more flexible and widely accessible than previously possible. Published online: 28 January 2003     

Voronoi图算法及其在混合电路的衬底耦合研究中的应用

提出了对版图进行划分的Ｖｏｒｏｎｏｉ图的算法：将Ｖｏｒｏｎｏｉ图进行变换,通过扫描技术,从下到上对每个点与交点进行处理,从而形成变换后的Ｖｏｒｏｎｏｉ图,最后将此图转换为Ｖｏｒｏｎｏｉ图．在计算中,针对集成电路的物理特性,改进了阱区附近的Ｖ图的生成以及多个水平位置点和兼并问题．算法时间复杂度为Ｏ（ｎｌｏｇｎ）,空间复杂度为Ｏ（ｎ）．     

Polygonal extrusion

A sweeping operation called polygonal extrusion is defined to improve the modeling power of CSG-based modeling. It is assumed that a 2D cross-sectional polygon (sweeping polygon) moves in space while its containing plane is kept orthogonal to the tangent direction of the trajectory curve, a planar polygonal chain having no self-intersections. The objective of the paper is to compute the boundary of the swept volume of the sweeping polygon as a set of polygons (or triangles). The most significant challenge to accomplishing this objective is the problem of trimming the swept volume. To solve the trimming problem, 2D-curve offsetting methods are employed. Two algorithms are presented for polygonal extrusion that are based on different offsetting methods, the Voronoi diagram and PWID offset. The proposed algorithms have been implemented and tested with various examples. Published online: 28 January 2003     

Higher-order Voronoi diagrams on triangulated surfaces

We study the complexity of higher-order Voronoi diagrams on triangulated surfaces under the geodesic distance, when the sites may be polygonal domains of constant complexity. More precisely, we show that on a surface defined by n triangles the sum of the combinatorial complexities of the order-j Voronoi diagrams of m sites, for j=1,…,k, is O(k²n²+k²m+knm), which is asymptotically tight in the worst case.     

The normalform of a space curve and its application to surface design

x )=0 with ∥▿h∥=1. The normalform function h is (unlike the latter cases) not differentiable at curve points. Despite of this disadvantage the normalform is a suitable tool for designing surfaces which can be treated as common implicit surfaces. Many examples (bisector surfaces, constant distance sum/product surfaces, metamorphoses, blending surfaces, smooth approximation surfaces) demonstrate applications of the normalform to surface design. Published online: 25 July 2001     

Voronoi Approach to Recursive Generation of Tool Path for SLS

Assuming that a Voronoi diagram of slice area is obtained, topological structures of all Voronoi edges and Voronoi polygons are used to accelerate the offsetting process. Once walk line intersects with one of Voronoi edges of the starting Voronoi object, the next starting Voronoi object is acquired through the topology relationship. Experimental results show the approach is effective and simple.     

基于Voronoi 图和三角剖分的闭合曲线重建

以Voronoi图和Delaunay三角剖分为基础,针对二维闭合曲线集的采样点集,提出一种曲线重建算法。该算法按给定采样密度对曲线集进行采样,从而用一条或多条线段准确地重建曲线集,将采样点密集程度的度量定义为点集的本地特征值度量,以此要求采样达到一定的密集程度。理论分析证明该算法的时间复杂度为O(nlogn)。     

利用Voronoi图构建多级TIN

由于地形地貌的复杂性,地形高程点的数据量往往很大。由离散高程点生成的TIN同样也具有相当大的数据量,这严重制约了TIN的分析、三维可视化等处理速度。为此,文中根据LOD的设计思想,采用逐级综合,生成多级TIN。随后,将多级TIN进行合并,统一存储,消除了冗余数据。采用局部更新、分级调用的策略使得处理速度显著提高,且受数据量的影响很小,可以较好地应用在地理信息系统中。     

Binary decision diagrams in theory and practice

Decision diagrams (DDs) are the state-of-the-art data structure in VLSI CAD and have been successfully applied in many other fields. DDs are widely used and are also integrated in commercial tools. This special section comprises six contributed articles on various aspects of the theory and application of DDs. As preparation for these contributions, the present article reviews the basic definitions of binary decision diagrams (BDDs). We provide a brief overview and study theoretical and practical aspects. Basic properties of BDDs are discussed and manipulation algorithms are described. Extensions of BDDs are investigated and by this we give a deeper insight into the basic data structure. Finally we outline several applications of BDDs and their extensions and suggest a number of articles and books for those who wish to pursue the topic in more depth. Published online: 15 May 2001