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

On soft predicates in subdivision motion planning

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2015年第8期48卷 589-605页

作者： Wang, Cong Chiang, Yi-Jen Yap, Chee NYU Polytech Sch Engn Dept Comp Sci & Engn Brooklyn NY 11201 USA NYU Dept Comp Sci New York NY USA

We propose to design new algorithms for motion planning problems using the well-known Domain subdivision paradigm, coupled with "soft" predicates. Unlike the traditional exact predicates in computational geometry, our primitives are only exact in the limit. We introduce the notion of resolution-exact algorithms in motion planning: such an algorithm has an "accuracy" constant K > 1, and takes an arbitrary input "resolution" parameter epsilon > 0 such that: if there is a path with clearance K epsilon, it will output a path with clearance epsilon/K;if there are no paths with clearance epsilon/K, it reports "NO PATH". Besides the focus on soft predicates, our framework also admits a variety of global search strategies including forms of the A* search and probabilistic search. Our algorithms are theoretically sound, practical, easy to implement, without implementation gaps, and have adaptive complexity. Our deterministic and probabilistic strategies avoid the Halting Problem of current probabilistically complete algorithms. We develop the first provably resolution-exact algorithms for motion-planning problems in SE(2) = R-2 x S-1. To validate this approach, we implement our algorithms and the experiments demonstrate the efficiency of our approach, even compared to probabilistic algorithms. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Exact algorithms subdivision algorithms Motion planning Soft predicates Resolution-exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Interpolatory, solid subdivision of unstructured hexahedral meshes

引用

VISUAL COMPUTER 2004年第6期20卷 418-436页

作者： McDonnell, KT Chang, YS Qin, H SUNY Stony Brook Dept Comp Sci Stony Brook NY 11794 USA

This paper presents a new, volumetric subdivision scheme for interpolation of arbitrary hexahedral meshes. To date, nearly every existing volumetric subdivision scheme is approximating, i.e., with each application of the subdivision algorithm, the geometry shrinks away from its control mesh. Often, an approximating algorithm is undesirable and inappropriate, producing unsatisfactory results for certain applications in solid modeling and engineering design (e.g., finite element meshing). We address this lack of smooth, interpolatory subdivision algorithms by devising a new scheme founded upon the concept of tri-cubic Lagrange interpolating polynomials. We show that our algorithm is a natural generalization of the butterfly subdivision surface scheme to a tri-variate, volumetric setting.

关键词： subdivision algorithms geometric and topological representations solid modeling multiresolution models volumetric meshes

来源：评论

学校读者我要写书评

暂无评论

Tangent driven interpolative subdivision

引用

COMPUTERS & GRAPHICS-UK 2007年第5期31卷 737-749页

作者： Stoddard, Jacob Bergeron, R. Daniel House, Donald Univ New Hampshire Durham NH 03824 USA Texas A&M Univ College Stn TX 77843 USA

This paper explores a new family of 2D interpolating subdivision schemes that calculate subdivision points from tangent specifications. In this approach each level of subdivision drives the curve toward its specified tangents. The paper describes the underlying algorithmic formulation, and outlines a number of variations, which differ in how subdivision points are computed from tangents or in how tangents are derived. The different characteristics of these variations are shown to provide an interesting range of shapes, giving a high degree of artistic control. Each variation is shown to guarantee C1 continuity except for special identifiable cases, and some of these variations can produce circles. A number of examples are explored that demonstrate the power of the approach as a modeling tool for constructing complex curves, and a comparison is made with curves produced by the Kobbelt subdivision scheme. (C) 2007 Elsevier Ltd. All rights reserved.

关键词： curve modeling curve generation subdivision algorithms

来源：评论

学校读者我要写书评

暂无评论

The complexity of subdivision for diameter-distance tests

引用

JOURNAL OF SYMBOLIC COMPUTATION 2020年 101卷 1-27页

作者： Burr, Michael Gao, Shuhong Tsigaridas, Elias Clemson Univ Sch Math & Stat Sci Clemson SC 29634 USA UPMC Univ Paris 06 Sorbonne Univ CNRS INRIALab Informat Paris 6 LIP6Equipe PolSys 4 Pl Jussieu F-75252 Paris 05 France

We present a general framework for analyzing the complexity of subdivision-based algorithms whose tests are based on the sizes of regions and their distance to certain sets (often varieties) intrinsic to the problem under study. We call such tests diameter-distance tests. We illustrate that diameter-distance tests are common in the literature by proving that many interval arithmetic-based tests are, in fact, diameter-distance tests. For this class of algorithms, we provide both non-adaptive bounds for the complexity, based on separation bounds, as well as adaptive bounds, by applying the framework of continuous amortization. Using this structure, we provide the first complexity analysis for the algorithm by Plantinga and Vegeter for approximating real implicit curves and surfaces. We present both adaptive and nonadaptive a prioriworst-case bounds on the complexity of this algorithm both in terms of the number of subregions constructed and in terms of the bit complexity for the construction. Finally, we construct families of hypersurfaces to prove that our bounds are tight. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： Algorithmic complexity Worst case bit-complexity subdivision algorithms Continuous amortization Adaptive complexity Separation bounds

来源：评论

学校读者我要写书评

暂无评论

Smoothness of subdivision Surfaces with Boundary

引用

CONSTRUCTIVE APPROXIMATION 2015年第1期42卷 1-29页

作者： Biermann, Henning Grundel, Sara Zorin, Denis NYU Courant Inst Math Sci New York NY 10003 USA Max Planck Onstitute Dynam Complex Tech Syst D-39106 Magdeburg Germany

subdivision rules for meshes with boundary are essential for practical applications of subdivision surfaces. These rules have to result in piecewise -continuous boundary limit curves and ensure -continuity of the surface itself. Extending the theory of Zorin (Constr Approx 16(3):359-397, 2000), we present in this paper general necessary and sufficient conditions for -continuity of subdivision schemes for surfaces with boundary, and specialize these to practically applicable sufficient conditions for -continuity. We use these conditions to show that certain boundary rules for Loop and Catmull-Clark are in fact continuous.

关键词： subdivision algorithms Boundary rules C-1-analysis Characteristic maps Loop Catmull-Clark

来源：评论

学校读者我要写书评

暂无评论

On the convergence of convolved vector subdivision schemes

引用

APPLIED NUMERICAL MATHEMATICS 2004年第4期51卷 477-486页

作者： Conti, C Univ Florence Dipartimento Energet Sergio Stecco Florence Italy

The aim of this paper is to discuss the use of convolution to build new families of refinable functions and thus new families of subdivision algorithms. In particular, we first generalise a result given in [C. Conti, K. Jetter, in: A. Cohen, R. Rabut, L.L. Schumaker (Eds.), Curves and Surfaces Fitting, Saint Malo, 1999, Vanderbilt University Press, Nashville, TN, 2000, pp. 135-142] where, following a too restrictive definition of convergence, it is proved that convolution of two refinable function vectors, which give rise to convergent subdivision schemes, generates a convolved scheme which is again convergent. Then, we discuss the use of convolution to construct refinable bases suitable to interpolate directions given by difference of control points. This turns out to be useful, for example, in algebraic numerical grid generation methods such as the one discussed in [C. Conti, R. Morandi, in: Proceedings of MASCOT/02, IMACS Ser. Comput. Appl. Math., IMACS, New Brunswick, NJ, 2003, pp. 75-82]. (C) 2004 IMACS. Published by Elsevier B.V. All rights reserved.

关键词： refinable function vectors subdivision algorithms convolution

来源：评论

学校读者我要写书评

暂无评论

SIMPLE REGULARITY CRITERIA FOR subdivision SCHEMES

引用

SIAM JOURNAL ON MATHEMATICAL ANALYSIS 1992年第6期23卷 1544-1576页

作者： RIOUL, O

Convergent subdivision schemes arise in several fields of applied mathematics (computer-aided geometric design, fractals, compactly supported wavelets) and signal processing (multiresolution decomposition, filter banks). In this paper, a polynomial description is used to study the existence and Holder regularity of limit functions of binary subdivision schemes. Sharp regularity estimates are derived;they are optimal in most cases. They can easily be implemented on a computer, and simulations show that the exact regularity order is accurately determined after a few iterations. Connection is made to regularity estimates of solutions to two-scale difference equations as derived by Daubechies and Lagarias, and other known Fourier-based estimates. The former are often optimal, while the latter are optimal only for a subclass of symmetric limit functions.

关键词： subdivision algorithms HOLDER REGULARITY SOBOLEV REGULARITY 2-SCALE DIFFERENCE EQUATIONS WAVELETS

来源：评论

学校读者我要写书评

暂无评论

THE subdivision ALGORITHM FOR GENERATING CURVES AND ITS PROPERTIES

引用

Applied Mathematics(A Journal of Chinese Universities) 1994年第2期9卷 169-176页

作者：吴宗敏叶青刘剑平 1. Department of Mathematics Fudan University 200433 Shanghai 2. East China University of Chemical Technology 200237 Shanghai

In the application of CAD/CAM. the target form of a curve, which is used for plotting or as the data supplied for CAM, is s set of points on (or near by) the curve,Using the subdivision algorithm, the procedure of curve generation from Control points→Mathematical form of the curve→Points on(or near by) the curve which is used in most systems for curve design, is simplified in this paper to Control points→Points on(or near by) the curve. We also discuss the conditions of shape preserving, polynomial reproducing, continuity as well as the convergent properties of the target curve.

关键词： 65D17 Curve generation subdivision algorithms shape preserving polynomial reproducing continuiyt convergence

来源：评论

学校读者我要写书评

暂无评论

An alternative method for constructing interpolatory subdivision from approximating subdivision

引用

COMPUTER AIDED GEOMETRIC DESIGN 2012年第7期29卷 474-484页

作者： Li, Xin Zheng, Jianmin Nanyang Technol Univ Sch Comp Engn Singapore 639798 Singapore Univ Sci & Technol China Dept Math Hefei Anhui Peoples R China

This paper presents a new perspective for constructing interpolatory subdivision from primal approximating subdivision. The basic idea is constructing the subdivision rule for new inserted vertices of a new interpolatory subdivision scheme based on an approximating subdivision algorithm applied to a local configuration of the mesh with one vertex updated for interpolation of the vertex. This idea is demonstrated by presenting two new interpolatory subdivision schemes based on Catmull-Clark subdivision for an arbitrary polygonal mesh and Loop subdivision for a triangular mesh. respectively. These algorithms are simple and have a small stencil for computing new points. The new perspective also shows a link between those classic approximating and interpolatory subdivision algorithms such as cubic B-spline curve subdivision and the four-point interpolatory subdivision. Catmull-Clark subdivision and Kobbelt's interpolatory scheme, and Loop subdivision and the butterfly algorithm. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Geometric modeling subdivision algorithms Approximating subdivision Interpolatory subdivision

来源：评论

学校读者我要写书评

暂无评论

On the convergence of convolved vector subdivision schemes

On the convergence of convolved vector subdivision schemes

引用

2nd Meeting on Applied Scientific Computing and Tools

作者： Conti, C Univ Florence Dipartimento Energet Sergio Stecco Florence Italy

关键词： refinable function vectors subdivision algorithms convolution

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：