多边形中心点向量的二次插值变形算法

多不动点约束下的网格变形算法需要用户确定不动点和操作点,针对该问题,提出多边形中心点向量的二次插值变形算法。该算法根据源、目标多边形中心点向量间旋转经过的面积与2个向量间的差值建立相似度函数,在变形过程中采用二次贝塞尔插值方法,在对应过程中利用改进的动态规划算法。实验结果表明,该算法可减少变形过程中多边形内部扭曲的程度,且计算量小、对应时间短、变形效果自然。     

曲线插值约束的LOOP细分曲面

提出基于Loop细分方法的曲线插值方法,不需要修改细分规则,只需以插值曲线的控制多边形为中心多边形,向其两侧构造对称三角网格带,该对称三角网格带将收敛于插值曲线。因此,包含有该三角网格带的多面体网格的极限曲面将经过插值曲线。若要插值多条相交曲线只需在交点处构造全对称三角网格。运用该方法可在三角网格生成的细分曲面中插值多达六条的相交曲线。     

优化变形能的平面多边形同构剖分

平面多边形间的同构三角剖分是平面形状渐进过渡与插值的基础,降低对应三角形的变形程度是获得高质量应用的关键.文中提出一种基于变形能优化的2个平面多边形的同构剖分算法,其中包含同构剖分生成和变形能最小化2个模块.首先根据用户指定的对应特征点对多边形进行顶点重采样,得到顶点一一对应的2个多边形;然后利用带约束的Delaunay剖分对其中的一个多边形进行三角化,得到源网格;再用重心坐标将源网格的内部顶点嵌入到另一个多边形得到同构剖分(目标网格);最后逐一检查三角形的变形能,对源网格中变形能超过阈值的三角形进行细分,用同构剖分模块生成新的目标网格.实验及数据统计分析表明,该算法可以得到较好的同构三角剖分,提升网格质量,并能很好地避免纹理细节失真.     

基于Hermite插值的网格拼接和融合

网格模型的拼接和融合是3维形状编辑和造型中的一个重要方面。基于Hermite插值技术,提出一种适用于具有一般边界点空间分布的三角网格模型之间无缝光滑拼接和融合方法。首先查找网格模型待拼接区域的边缘点集,并利用二次B样条曲线插值边缘点集分别得到边缘曲线;然后对边缘曲线进行Hermite插值得到拼接区域连续曲面;最后对拼接曲面分别进行三角网格化和Laplacian光顺平滑处理以实现网格模型的光滑拼接和融合。由于利用B样条曲线插值待拼接模型边界,本文方法适用于具有各种不同边界情形的网格模型拼接和融合,它不仅仅可以处理平面边界曲线情形也可以处理空间边界曲线情形。结合Hermite曲面插值拼接过渡区域,使得产生的拼接网格能光滑地衔接待拼接模型。实验结果表明,本文方法能够有效地实现三角网格模型的光滑拼接、模型修复和模型融合。     

基于Hermite插值的网格拼接和融合-CIDE2013

网格模型的拼接和融合是3维形状编辑和造型中的一个重要方面。基于Hermite插值技术,提出了一种适用于具有一般边界点空间分布的三角网格模型之间无缝光滑拼接和融合方法。首先查找网格模型待拼接区域的边缘点集,并利用二次B样条曲线插值边缘点集分别得到边缘曲线;然后对边缘曲线进行Hermite插值得到拼接区域连续曲面;最后对拼接曲面分别进行三角网格化和Laplacian光顺平滑处理以实现网格模型的光滑拼接和融合。由于利用B样条曲线插值待拼接模型边界,本文方法适用于具有各种不同边界情形的网格模型拼接和融合,它不仅仅可以处理平面边界曲线情形也可以处理空间边界曲线情形。结合Hermite曲面插值拼接过渡区域,使得产生的拼接网格能光滑地衔接待拼接模型。实验结果表明,本文方法能够有效地实现三角网格模型的光滑拼接、模型修复和模型融合。     

具有直线结构保护的网格化图像拼接

目的 基于网格变形的图像配准方式,针对待拼接图片重叠区域的视差具有一定的容忍性,并且能够适应更复杂的图像拼接场景。在NISwGSP （natural image stitching with the global similarity prior）算法基础上提出了一种具有直线结构保护的图像拼接算法（MISwLP）,该算法通过提取图片中的直线结构并施加约束,可以得到视觉效果自然、畸变较小的图像拼接结果。方法 首先对图片进行网格划分,建立网格优化模型,针对网格顶点坐标集定义能量函数,在保证图片重叠区域高度对齐的同时,对网格进行相似性连续约束,并辅以直线结构约束,最后使用共轭梯度最小二乘法求解得到最优网格顶点集,指导网格变形。结果 针对不同场景下的图片进行拼接实验,同时和几种比较流行的图像拼接软件和算法进行比较。结果表明,同经典拼接算法,比如Autostitch相比,基于网格优化的图像拼接算法能够适应更加复杂的多平面场景,在减小投影失真和对齐误差方面表现更好;同现在比较好的几种网格拼接算法,比如SPHP （shape-preserving half-projective warps for image stitching）、APAP （as-projective-as-possible image stitching with moving DLT）、NISwGSP等的比较,MISwLP算法不仅能够很好地对齐图像和避免投影失真,并且能够保持图像重叠区域到非重叠区域的一致性,即保护原图中的直线结构。结论 提出了一种基于网格优化的直线约束方法,对于具有显著几何结构的图像拼接场景,能够较好地保护拼接后图像中原有的直线结构,具有较好的应用价值。     

一种基于轮廓多边形的图像变形算法

文中利用两条任意折线构成两个控制多边形,得到两条Ｂｅｉｚｅｒ曲线,利用两曲线作为控制线对图像轮廓多边形的网格控制点进行映射,最后利用一个快速有效的插值算法进行目标－源映射,描绘各个像素点实现变形效果,实验证明,该算法快速有效,结果形象逼真,具有一定的实用价值。     

具有边界约束的多重形状变形方法

推广了基于内在形状插值的多边形渐变算法,提出了具有边界约束的多重形状变形方法.基于内在形状插值是公认的对2D形状插值具有良好效果,但是该算法仅适合于闭多边形的插值,不适合曲线形状的插值.通过在约束方程中引进边界控制条件得到适合一般曲线形状的插值算法,并利用具有指定边界约束的变换和形状插值器的构造,使该算法适合具有任意指定边界的多重2D曲线形状的混合变形.实验表明该算的视觉效果良好,可直接用于角色动画设计系统.     

基于三角基的平面多边形变形

本文讲解在VC 6.0环境下解通过对初始多边形和目标多边形进行Delaunay三角剖分,给出描述三角形网格各顶点空间位置的内在结构矩阵,然后插值相应的三角网格结构矩阵,实现多边形之间的形状变化。     

基于网格优化的隐式曲面自适应多边形化

隐式曲面多边形化是隐式曲面绘制的一种常用算法.基于网格优化的隐式曲面快速自适应多边形化算法,首先用多边形化算法生成一个粗糙的初始网格,再利用网格优化方法从网格顶点位置、规则性和网格法向三个方面对粗糙网格进行调整,最后根据网格的局部曲率用多边形细分策略细分优化后的网格.实验结果表明,该算法在网格生成速度和网格规则性上都胜于Marching Cubes的多边形化算法,恢复的隐式曲面能较好地反映形状特征.     

一种改进的网格多边形online探索算法

针对网格多边形机器人online探索问题,在分析现有成果的基础上,结合SmartDFS算法,并通过扩大机器人视觉范围,使其范围限定在给定的单位网格内。通过区分不同类型的网格,确定遍历的优先级别以设计出不同的探索策略,提出SmartDFS-OPT算法。该算法将网格多边形online探索问题求解算法的竞争比从5/4降低为7/6,达到了理论分析结果的下界,使机器人的online遍历路径长度达到最短,因而是求解该问题的一个最优算法。该算法将有助于那些基于机器人探索未知环境的智能设备的研发与应用。     

Using interpolation to improve path planning: The Field D* algorithm

We present an interpolation‐based planning and replanning algorithm for generating low‐cost paths through uniform and nonuniform resolution grids. Most grid‐based path planners use discrete state transitions that artificially constrain an agent's motion to a small set of possible headings (e.g., 0, π/4, π/2, etc.). As a result, even “optimal” grid‐based planners produce unnatural, suboptimal paths. Our approach uses linear interpolation during planning to calculate accurate path cost estimates for arbitrary positions within each grid cell and produce paths with a range of continuous headings. Consequently, it is particularly well suited to planning low‐cost trajectories for mobile robots. In this paper, we introduce a version of the algorithm for uniform resolution grids and a version for nonuniform resolution grids. Together, these approaches address two of the most significant shortcomings of grid‐based path planning: the quality of the paths produced and the memory and computational requirements of planning over grids. We demonstrate our approaches on a number of example planning problems, compare them to related algorithms, and present several implementations on real robotic systems.     

基于边界约束的空间复杂曲面重构算法

针对克里金(Kriging)算法在复杂地质构造应用中的局限性,提出了一种基于边界约束的复杂曲面插值方法.其基本思想是将断层多边形作为层面边界的约束条件,根据种子点与待插值点穿越多边形的关系为依据,判断待插值点与控制点之间的空间拓扑关系,并将满足条件的种子点利用克里金算法进行插值计算.通过实际数据的测试,解决了传统的网格化插值方案层位与断层无法严格相交以及多重逆掩断层构造的层面拟合等难题,为等值线绘制、地质块状模型构建等提供了新的思路.     

有向回路法和网格法:多边形内外点判别的新算法

该文把简单多边形视作一个有向回路,利用多边形的环绕方向和区域划分提出了两种判别内外点的新算法:有向回路法和网格法。有向回路法利用了多边形的方向性,在某些情况下可以不必遍历多边形的所有边。该算法程序简单,时间复杂度为O(n),平均性能优于复杂度为Θ(n)的射线法和标号法,但只能处理凸多边形。网格法是有向回路法的改进算法,利用了多边形的方向性和区域划分。网格法将n边形的包围盒划分为(n-1)×(n-1)个网格:如果待处理的点在某个网格内,则仅根据经过该网格的所有边就可以判断该点的内外性。网格法可以处理任意简单多边形,包括带孔的多边形;最坏情况下的时间复杂度为O(lgn),空间复杂度为Θ(n2)。     

A Hybrid Lagrangian/Eulerian Collocated Velocity Advection and Projection Method for Fluid Simulation

We present a hybrid particle/grid approach for simulating incompressible fluids on collocated velocity grids. Our approach supports both particle-based Lagrangian advection in very detailed regions of the flow and efficient Eulerian grid-based advection in other regions of the flow. A novel Backward Semi-Lagrangian method is derived to improve accuracy of grid based advection. Our approach utilizes the implicit formula associated with solutions of the inviscid Burgers’ equation. We solve this equation using Newton's method enabled by C¹ continuous grid interpolation. We enforce incompressibility over collocated, rather than staggered grids. Our projection technique is variational and designed for B-spline interpolation over regular grids where multiquadratic interpolation is used for velocity and multilinear interpolation for pressure. Despite our use of regular grids, we extend the variational technique to allow for cut-cell definition of irregular flow domains for both Dirichlet and free surface boundary conditions.     

Fast, memory-efficient cell location in unstructured grids for visualization

Applying certain visualization techniques to datasets described on unstructured grids requires the interpolation of variables of interest at arbitrary locations within the dataset's domain of definition. Typical solutions to the problem of finding the grid element enclosing a given interpolation point make use of a variety of spatial subdivision schemes. However, existing solutions are memory- intensive, do not scale well to large grids, or do not work reliably on grids describing complex geometries. In this paper, we propose a data structure and associated construction algorithm for fast cell location in unstructured grids, and apply it to the interpolation problem. Based on the concept of bounding interval hierarchies, the proposed approach is memory-efficient, fast and numerically robust. We examine the performance characteristics of the proposed approach and compare it to existing approaches using a number of benchmark problems related to vector field visualization. Furthermore, we demonstrate that our approach can successfully accommodate large datasets, and discuss application to visualization on both CPUs and GPUs.     

基于等值线的海区网格插值算法研究

为了将人类长期海洋观测所获取的矢量等值线数据与遥感反演等所获取的栅格数据进行比对运算,存在由等值线到海区网格的插值需求.以海洋表层水温矢量等值线为例,运用具有层次嵌套关系的三级分辨率海区网格,对等值线进行了离散化,通过建立离散点与海区网格之间的空问索引关系,并运用顾及方向的单点移面平均加权法,进行了海区网格点插值运算过程的研究.     

基于插值A*算法的路径规划

提出一个基于插值的路径规划算法-插值A*.此算法可以在每个栅格路径代价不一致的情况下生成一条平滑路径.由于大多数基于栅格算法规划的路径只能从一个栅格中心到另一栅格中心,也就限制了路径的方向只能是倍数,所以所谓最优路径其实是次优的.插值A*算法在路径规划时,使用线形插值来计算出更精确的路径代价,由此产生更优路径.     

具有线性精度的Cuberille方法

针对Cuberille方法精度低、显示效果差的缺点，将Cuberille方法形成的小立方体侧面边界作为骨架，在其基础上蒙上一层多边形网格．多边形网格通过扩张小立方体的侧面得到，这种扩张可以弥补由Cuberille方法造成的误差，从而使多边形网格具有线性精度．详细讨论了如何确定多边形网格顶点的位置、法向量以及多边形网格的构造方法，所构造的多边形网格具有明确的几何意义．最后，分析了算法的复杂性，并且以具体实例对新方法和Marching Cube方法及Cuberille方法在显示效果和时间消耗上进行了比较．