检索结果-内蒙古大学图书馆

Improvements to algorithms for computing the Minkowski sum of 3-polytopes

COMPUTER-AIDED DESIGN 2003年第13期35卷 1181-1192页

作者： Wu, YY Shah, JJ Davidson, JK Arizona State Univ Coll Engn & Appl Sci Design Automat Lab Dept Mech & Aerosp Engn Tempe AZ 85287 USA

A Minkowski sum is a geometric operation that is equivalent either to the vector additions of all points in two operands or to the sweeping of one operand around the profile of the other without changing the relative orientation. Applications of Minkowski sums are found in computer graphics, robotics, spatial planning, and CAD. This paper presents two algorithms for computing Minkowski sum of convex polyhedron in three space (3-polytopes). Both algorithms are improvements on current ones found in the literature. One is based on convex hulls and the other on slope diagrams. The original convex hull based Minkowski algorithm is costly, while the original slope diagram based algorithms require the operation of stereographic projection from 3D to 2D for merging the slope diagrams of the two operands. Implmenentation of stereographic projection is complicated which increases the computation time and reduces the accuracy of the geometric information that is needed for constructing the resultant solid. This paper reports on improvements that have been made to these two algorithms and their implementation. These improvements include using vector operations to find the interrelations between points, arcs and regions on a unit sphere for the slope diagram algorithm, and addition of a pre-sorting procedure before constructing convex hull for convex hull based Minkowski sum algorithm. With these improvements, the computation time and complexity for both algorithms have been reduced significantly, and the computational accuracy of the slope diagram algorithm has been improved. This paper also compares these two algorithms to each other and to their original counterparts. The potential for extending these algorithms to higher dimensions is briefly discussed. (C) 2003 Elsevier Ltd. All rights reserved.

关键词： geometric algorithms Minkowski sum convex hull polytopes math modeling of geometric variations

来源：评论

学校读者我要写书评

暂无评论

Optimal and approximate bottleneck Steiner trees

引用

OPERATIONS RESEARCH LETTERS 1996年第5期19卷 217-224页

作者： Ganley, JL Salowe, JS QUESTECH INC FALLS CHURCH VA 22043 USA

Given a set of terminals in the plane, a bottleneck Steiner tree is a tree interconnecting the terminals, in which the length of the longest edge is minimized. The bottleneck Steiner tree problem, or special cases thereof, has applications in facility location and electronic physical design automation. In this paper, we first consider algorithms for computing optimal bottleneck Steiner trees. For a given topology, we give a direct, geometric algorithm that computes an optimal rectilinear bottleneck Steiner tree in O(n(2)) time, which improves on the time complexity of previous algorithms. We also give a linear-time algorithm that, given the output from the previous algorithm, computes a rectilinear Steiner tree with minimum bottleneck length and that, among all trees with minimum bottleneck length, has minimum total length. These topology-specific algorithms provide solutions to many facility location applications, and in combination with a topology enumeration algorithm, can be used to solve the more general problems that arise in other applications. We also describe some difficulties in generalizing these results to the Euclidean problem, and give a simple approximation algorithm for the Euclidean problem. We then consider computation of approximate bottleneck Steiner trees. Specifically, we derive the exact value of the bottleneck Steiner ratio in any distance metric. The bottleneck Steiner ratio is the maximum ratio of the length of the longest edge in a minimum spanning tree to the length of the longest edge in an optimal bottleneck Steiner tree. Thus, the bottleneck Steiner ratio indicates the quality of a minimum spanning tree as an approximation of an optimal bottleneck Steiner tree.

关键词： bottleneck Steiner trees Steiner ratio geometric algorithms tree algorithms minmax multicenter facility location

来源：评论

学校读者我要写书评

暂无评论

IMPLEMENTATION OF A RANDOMIZED ALGORITHM FOR DELAUNAY AND REGULAR TRIANGULATIONS IN 3 DIMENSIONS

引用

COMPUTER AIDED geometric DESIGN 1995年第4期12卷 349-370页

作者： FACELLO, MA UNIV ILLINOIS DEPT COMP SCI URBANA IL 61801 USA

For a set of n points in R3, we can define the Delaunay triangulation of the point set. For each assignment of weights to the points there is a regular triangulation of the point set. We describe the implementation of algorithms to compute the Delaunay triangulation of an unweighted point set and the regular triangulation of a weighted point set. The algorithms run in expected time O(n log n) for uniformly distributed points and other dense point sets. Worst case point sets, which do not occur very often in practice, require O(n2) expected time. The software described in this paper is available via anonymous ftp at ***.

关键词： geometric algorithms GRID GENERATION REGULAR AND DELAUNAY TRIANGULATIONS

来源：评论

学校读者我要写书评

暂无评论

A fan growing algorithm for efficient vertex caching

引用

COMPUTERS & GRAPHICS-UK 2003年第5期27卷 773-789页

作者： Franzetti, T Day, AM Arnold, DB Univ E Anglia Sch Informat Syst Norwich NR4 7JT Norfolk England

In this paper we describe an algorithm to speed up the rendering of triangulated meshes. The gap between the microprocessor's speed and the memory's speed continuously increases so it is important to address, on the software side, the possibilities for reducing this difference. The algorithm reorganises the traversal of the vertex data by taking advantage of the introduction of a vertex cache on the graphics card. By enabling maximum reuse of the vertices in the cache, we reduce the number of bytes that need to be transmitted on the memory-to-processor bus. Our orientation and perimeter constrained fan-growing algorithm can typically give an extra 25% bandwidth saving compared to a standard stripification algorithm. Furthermore, it exhibits cache miss rates per triangle of around 0.65;which means that on average less than one vertex per triangle needs to be loaded from the memory. Our method is similar to a previous approach that uses triangle strips and cache optimisation. The two methods provide equivalent bandwidth savings but our technique can produce significant savings in the execution time. (C) 2003 Elsevier Ltd. All rights reserved.

关键词： graphics processors graphics data structures geometric algorithms

来源：评论

学校读者我要写书评

暂无评论

On the design of traps for feeding 3D parts on vibratory tracks

引用

ROBOTICA 2008年第4期26卷 537-550页

作者： Goemans, Onno C. van der Stappen, A. Frank Univ Utrecht Inst Comp & Informat Sci NL-3508 TB Utrecht Netherlands

In the context of automated feeding (orienting) Of industrial parts, We Study the algorithmic design of traps in the bowl feeder track that filter Out all but one orientation of a given , polyhedral part. We propose a new class of traps that removes it V-shaped portion of the track. The proposed work, advances the state-of-the-art in algorithmic trap design by extending earlier work(1,6,17)-which focuses solely on 2D parts-to 3D parts, and by incorporating a more realistic part motion model in the design algorithm. We exploit the geometric Structure of the design problem and build on concepts computational geometry to obtain an and techniques from efficient algorithm that reports the complete set of valid traps.

关键词： geometric algorithms vibratory bowl trap design

来源：评论

学校读者我要写书评

暂无评论

Continuous point projection to planar freeform curves using spiral curves

引用

VISUAL COMPUTER 2012年第1期28卷 111-123页

作者： Oh, Young-Taek Kim, Yong-Joon Lee, Jieun Kim, Myung-Soo Elber, Gershon Seoul Natl Univ Sch Engn & Comp Sci Seoul 151744 South Korea Chosun Univ Sch Comp Engn Kwangju 501759 South Korea Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

We present an efficient algorithm for projecting a continuously moving query point to a family of planar freeform curves. The algorithm is based on the one-sided Hausdorff distance from the trajectory curve (of the query point) to the planar curves. Using a bounding volume hierarchy (BVH) of the planar curves, we estimate an upper bound (h) over bar of the one-sided Hausdorff distance and eliminate redundant curve segments when they are more than distance (h) over bar away from the trajectory curve. Recursively subdividing the trajectory curve and repeating the same elimination procedure to the BVH of the remaining curves, we can efficiently determine where to project the moving query point. The explicit continuous point projection is then interpreted as a curve reparameterization problem, for which we propose a few simple approximation techniques. Using several experimental results, we demonstrate the effectiveness of the proposed approach.

关键词： Continuous point projection Bounding volume hierarchy Axis-aligned bounding box Line swept sphere Minimum distance Hausdorff distance Culling Curve reparameterization geometric algorithms

来源：评论

学校读者我要写书评

暂无评论

Range Scan Registration Using Reduced Deformable Models

引用

COMPUTER GRAPHICS FORUM 2009年第2期28卷 447-456页

作者： Chang, W. Zwicker, M. Univ Calif San Diego La Jolla CA 92093 USA Univ Bern Inst Informat & Angew Math CH-3012 Bern Switzerland

We present an unsupervised method for registering range scans of deforming, articulated shapes. The key idea is to model the motion of the underlying object using a reduced deformable model. We use a linear skinning model for its simplicity and represent the weight functions on a regular grid localized to the surface geometry. This decouples the deformation model from the surface representation and allows us to deal with the severe occlusion and missing data that is inherent in range scan data. We formulate the registration problem using an objective function that enforces close alignment of the 3D data and includes an intuitive notion of joints. This leads to an optimization problem that we solve using an efficient EM-type algorithm. With our algorithm we obtain smooth deformations that accurately register pairs of range scans with significant motion and occlusion. The main advantages of our approach are that it does not require user specified markers, a template, nor manual segmentation of the surface geometry into rigid parts.

关键词： I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling geometric algorithms

来源：评论

学校读者我要写书评

暂无评论

A Skeleton-Based Approach for Consistent Segmentation Transfer

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 2014年第4期30卷 1053-1070页

作者： Wong, Sai-Keung Yang, Jau-An Ho, Tan-Chi Chuang, Jung-Hong Natl Chiao Tung Univ Dept Comp Sci Hsinchu 300 Taiwan

We present a skeleton-based approach for mapping consistently a segmentation of a source mesh to a target mesh. The source and target meshes are semantically similar but their geometries may be different. We assume that the segmentation of the source mesh and the skeleton correspondence between the meshes are provided. Our method first establishes the skeleton-boundary correspondence and then performs the boundary transfer procedure. The skeleton-boundary correspondence is useful for computing approximately the target boundaries. The boundary transfer procedure aims to produce the segment boundaries of the target mesh such that their geometric details are consistent to the ones of the corresponding source segment boundaries. We have applied our method for various models and compared with the state-of-the-art techniques. Our method computes segment boundaries of the target mesh which are similar to the ones of the source mesh.

关键词： segmentation transfer skeleton correspondence consistent segmentation geometric algorithms skeleton-boundary correspondence

来源：评论

学校读者我要写书评

暂无评论

Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers

引用

ALGORITHMICA 2021年第5期83卷 1316-1351页

作者： Akitaya, Hugo A. Arkin, Esther M. Damian, Mirela Demaine, Erik D. Dujmovic, Vida Flatland, Robin Korman, Matias Palop, Belen Parada, Irene Renssen, Andre van Sacristan, Vera Carleton Univ Ottawa ON Canada SUNY Stony Brook Stony Brook NY 11794 USA Villanova Univ Villanova PA 19085 USA MIT 77 Massachusetts Ave Cambridge MA 02139 USA Univ Ottawa Ottawa ON Canada Siena Coll Loudonville NY USA Tufts Univ Medford MA 02155 USA Univ Valladolid Valladolid Spain TU Eindhoven Eindhoven Netherlands Univ Sydney Sydney NSW Australia Univ Politecn Cataluna Barcelona Spain

We present the first universal reconfiguration algorithm for transforming a modular robot between any two facet-connected square-grid configurations using pivot moves. More precisely, we show that five extra "helper" modules ("musketeers") suffice to reconfigure the remaining n modules between any two given configurations. Our algorithm uses O(n(2)) pivot moves, which is worst-case optimal. Previous reconfiguration algorithms either require less restrictive "sliding" moves, do not preserve facet-connectivity, or for the setting we consider, could only handle a small subset of configurations defined by a local forbidden pattern. Configurations with the forbidden pattern do have disconnected reconfiguration graphs (discrete configuration spaces), and indeed we show that they can have an exponential number of connected components. But forbidding the local pattern throughout the configuration is far from necessary, as we show that just a constant number of added modules (placed to be freely reconfigurable) suffice for universal reconfigurability. We also classify three different models of natural pivot moves that preserve facet-connectivity, and show separations between these models.

关键词： Reconfiguration geometric algorithms Pivoting squares Modular robots

来源：评论

学校读者我要写书评

暂无评论

Filtering Relocations on a Delaunay Triangulation

引用

COMPUTER GRAPHICS FORUM 2009年第5期28卷 1465-1474页

作者： de Castro, Pedro Machado Manhaes Tournois, Jane Alliez, Pierre Devillers, Olivier INRIA Sophia Antipolis Mediterranee France

Updating a Delaunay triangulation when its vertices move is a bottleneck in several domains of application. Rebuilding the whole triangulation front scratch is surprisingly a very viable option compared to relocating the vertices. This can be explained by several recent advances in efficient construction of Delaunay triangulations. However when all points move with a small magnitude, or when only a fraction of the vertices move, rebuilding is no longer the best option. This paper considers the problem of efficiently updating a Delaunay triangulation when its vertices are moving tinder small perturbations. The main contribution is a set of filters based upon the concept of vertex tolerances. Experiments show that filtering relocations is faster than rebuilding the whole triangulation from scratch tinder certain conditions.

关键词： I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling geometric algorithms languages and systems

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：