基于骨架关节点约束的交互式局部变形

利用广义元球变形技术,提出一种基于骨架关节点约束的交互式局部变形方法。该方法提取多边形网格模型的骨架关节点并结合模型骨架图结构确定骨架关节点对应的局部区域,计算三维网格点到骨架节点的欧式距离,将约束区域的最大欧氏距离作为约束半径,得到各骨架节点对应的势函数值,通过控制骨架节点的空间位置给出三角形面片点的新坐标位置。实验结果表明,该方法有效保持多边形网络模型的局部特征,并确保了模型变形的直观性和高效性。     

基于测地距离的多边形网格模型约束变形

提出了一种基于测地线的多边形网格模型的约束变形方法.首先给定一系列的变形约束源(可以是点、线或者面)以及约束源的有效半径及变形目标(偏移量、缩放比例、旋转轴和旋转角度),然后通过计算三角形网格的各顶点到约束源的测地距离来确定各顶点的场值,这个场值将作为变形的权值.在基于欧氏距离的传统约束变形中,对某一约束区域的变形往往导致对约束源附近区域不需要的变形结果,而利用测地距离来计算各点的变形权值,可以很好地避免这种现象的出现.实验结果表明,这种变形方法是直观而且有效的.     

基于Metaball的曲面约束变形模型及应用

结合曲面变形技术和Metaball原理,提出了基于Metaball的曲面约束变形模型,将Metaball的势函数表达曲面变形的约束,用它去作用于待变形曲面,通过调整Metaball势函数的约束中心、作用半径、偏移等参数控制曲面的预期变形效果,利用骨架卷积获得平坦光滑的曲面.讨论了约束关系、单个约束的影响、控制约束的相互影响等问题,并举例说明了这个模型的机理和应用.     

采样点模型的布尔运算

提出了一种快速而鲁棒的点模型布尔运算算法.在进行布尔运算之前,首先将点模型中的每个点表示成具有一定半径的面元,并确定它相对于另一个模型表面的内、外及相交关系;然后对相交面元进行全局误差控制下的自适应加密重采样,以求取交线;为了加速面元的内、外及相交关系的检测,对每个模型建立层次结构k-d树.实验结果表明,该方法对于具有不同分辨率以及采样不均匀的点模型也能进行稳定可靠的布尔运算.     

约束四面体部分和三维物体表面重建

该文提出了约束曲面和约束最大空球凸多面体的概念，在此基础上设计了一种在空间区域上约束Delaunay四面体部分的算法，该算法的基本思路是首先对空间区域进行约束最大空球凸多面体剖分，然后在各个约束最大空球凸多面体内部做Delaunay四面体剖分，利用约束Delaunay四面体剖分算法，该文进一步设计了一种三维物体表面重建算法。     

图像的局部约束变形技术

提出了一个基于局部约束的图像变形算法。该算法建立在一个新的C^2连续的变形模型上，局部约束包括单点约束和多点约束，用户可以交互地直接控制变形，实例计算表明，该算法十分灵活、简单和快速、变形效果很好。     

约束四面体剖分和三维物体表面重建

该文提出了约束曲面和约束最大空球凸多面体的概念,在此基础上设计了一种在空间区域上做约束Delaunay四面体剖分的算法。该算法的基本思路是首先对空间区域进行约束最大空球凸多面体剖分,然后在各个约束最大空球凸多面体内部做Delaunay四面体剖分。利用约束Delaunay四面体剖分算法,该文进一步设计了一种三维物体表面重建算法。     

模版特征线匹配的牙齿形状修复

牙齿形状修复是牙科修复CAD系统的核心问题,其中结构特征线,如颈缘线、修复边缘线是决定修复体制造精度的关键要素.针对现有牙齿形状自动修复算法未考虑结构特征线附近的咬合面形状约束以及仅能处理部分缺失情况的问题,提出了结合模版特征线匹配与移动最小二乘变形的修复体曲面重建算法.该算法采用智能剪刀算法半自动指定牙齿预备体上的结构特征线,并采用曲面拟合技术将该结构特征线投影至模版牙齿模型以建立曲线约束;再用近似刚性的移动最小二乘变形算法将模版牙齿模型匹配到牙齿预备体上;最后将移动最小二乘变形算法并行化,实现了以特征线为控制句柄的修复体形状交互设计.实验结果表明,由于引入了曲线约束,文中算法重建的修复体在结构特征线附近可获得更自然的咬合面形态.     

加速基于元球的物体变形方法

为了加速三维物体的变形过程,提出一种基于组件的新方法计算元球的边界体.把每个元球的边界体值存放在数组中,通过查询边界体数组,可以快速求出变形空间内任意一点的影响组件,并计算影响组件的骨架中心到该点的距离以及影响组件相对于该点的所有势函数之和,然后采用移动立方体算法将该点的势函数值与阈值比较,得出变形物体表面顶点的空间坐标值和该顶点的单位法向量.利用OpenGL实现变形物体的绘制过程.     

基于细胞元模型拓扑约束求解

在模型制造领域,对于拓扑约束的求解是一个比较新的课题,以往的研究一直局限在拓扑优化方面。而且对其应用也仅限于模型的定义方面,在模型的声明与约束求解方面却没有得到应用。文章提出一种基于细胞元模型拓扑约束求解方法,通过该方法可以确定模型拓扑声明的关系,文章假设一个模型是由一个或多个细胞元组成的,并且能够用这些细胞元的组合来表示,对模型进行拓扑约束求解就是用来确定细胞模型中的每个细胞元是否是全约束的。要做到这点,文章将每个细胞元用一个布尔变量表示,把拓扑约束问题映射成为布尔可满足性问题。再对新的问题进行求解,从而解决了模型的拓扑约束求解问题。     

基于空间矢量变换的模型约束变形

基于空间矢量线性变换知识,提出了一种新的多边形网格模型变形方法。在三维模型空间选择一点作为约束源,并设置此约束源的影响半径。通过计算约束源与三维模型网格面片顶点之间的距离来确定待变形局部顶点区域。把空间矢量的线性变换应用到网格面片顶点变形所需的向量函数,依此函数直接精确地计算出网格面片顶点的新位置,从而实现模型的变形。通过对算法原理的进一步分析扩展了该变形方法的应用范围。     

Toward Practical Query Evaluation for Constraint Databases

Linear constraint databases (LCDBs) extend relational databases to include linear arithmetic constraints in both relations and queries. A LCDB can also be viewed as a powerful extension of linear programming (LP) where the system of constraints is generalized to a database containing constraints and the objective function is generalized to a relational query containing constraints. Our major concern is query optimization in LCDBs. Traditional database approaches are not adequate for combination with LP technology. Instead, we propose a new query optimization approach, based on statistical estimations and iterated trials of potentially better evaluation plans. The resulting algorithms are not only effective on LCDBs, but also applicable to existing query languages. A number of specific constraint algebra algorithms are also developed: select-project-join for two relations, constraint sort-join and constraint multi-join.     

一种有效的隐式约束动力学布料动画方法

布料动画中,通常采用施加约束的方式限制布料的过度拉伸.已有的研究工作没有充分考虑拉伸约束与弯曲形变之间的关系,构造的动画模型并不完善,无法模拟布料无拉伸而多褶皱的"刚柔"相混的复杂变形效果.针对此问题,提出一种基于隐式约束力的布料动画方法.首先,建立有效的布料弯曲受力模型,并提出一种动态适应性约束方法,能够同时处理布料运动过程中结构和剪切2种不同类型的拉伸,避免单一结构拉伸约束导致的"过剪切"变形或者过约束导致的"刚性"失真效果;建立碰撞约束,避免局部调整穿透质点引起的过度拉伸问题.其次,将各种约束以隐式约束力的形式增加到动力学系统中,采用约束型迭代精化的方法进行求解.实验结果表明,该方法稳定有效,能够在保持布料弯曲形变的前提下,将拉伸控制在合理范围内,真实地刻画布料"易弯抗拉"的变形特征,实现逼真的布料变形动画模拟.     

通用几何约束系统统一建模研究

在几何约束和几何实体的基本约束和欧拉参数表达的基础上,研究了通用几何约束系统的统一建模问题。通过对三维几何实体姿态约束和位置约束解耦性的分析,抽象出球实体、盒体和球盒体三种基本几何实体表达空间几何实体,并以基本约束的组合表达几何约束,形成几何约束模型特有的层次结构;并以有向图管理几何约束系统,可以清晰地反映姿态约束和位置约束的解耦性,实现约束系统的细粒度分解,得到规模更小的求解序列,实现高效求解。方法实现于原型系统WhutVAS中。     

Metaball重叠区域作用效果混合

在表现隐式曲面或曲面变形时，多个Metaball作用的重叠区域常会出现肿胀、褶皱、撕裂等缺陷。前人虽曾通过调整Metaball参数、简单叠加、直接合并等来解决这些问题，但未能得到效果好，且效率高的满意结果，为此，在分析、研究了Metaball单独作用、作用范围重叠的基础上，分别针对点骨架、直线段、曲线段骨架，提出了线性加权和、代数混合、指数加权和方法，用以处理多个Metaball在重叠区域的作用效果混合。实验表明。这些混合方法不但可与曲面的表示方法以及Metaball势函数的形式无关，而且在边界处的过渡较平滑，其效果与效率也得到了实例验证。     

基于约束规划的一类排序问题通用求解方法

多约束排序问题是生产调度中常遇到的问题,传统的优化模型及方法在适应约束改变等方面存在诸多不足。鉴于此,将多约束排序问题定义为约束满足问题,系统设计时将模型定义与求解算法分离,利用约束规划平台的基本约束构建特定领域的抽象约束库,形成可重构的多约束排序问题通用求解框架。应用时,根据问题需求不同可利用抽象约束库快速重构优化模型,针对重构的优化模型配置相应的求解算法即可实现问题求解。应用结果表明,提出的方法通用性强,可满足实际应用的要求。     

雅可比矩阵引导的无翻转体映射生成

目的 体映射建立了两个3维体网格之间的对应关系,是计算机图形学中的重要研究方向。很多应用要求体映射是无翻转的,即其雅可比矩阵的行列式处处大于0。然而,现有的无翻转体映射生成算法经常无法完全消除翻转。挑战主要在于很难在保证满足位置约束的前提下消除映射的翻转。为此,提出一种新的无翻转体映射计算方法,核心是一种新的变形方法。方法 首先放松位置约束,然后在变形过程中通过线搜索的方式保证不产生翻转,最后将网格无翻转地变形到满足位置约束。为实现这个变形过程,提出一种雅可比矩阵引导的变形算法。虽然现有的无翻转体映射方法不能完全消除翻转,但其雅可比矩阵可以作为本文变形算法的指导。此外,优化了位置能量,使得变形网格最终能够满足位置约束要求。为了满足体映射低扭曲的要求,算法最后在固定位置约束的前提下进一步优化了体映射的扭曲能量。结果 对大量复杂网格进行实验,本文算法能够保证生成无翻转的体映射,并且通过多步优化最终结果均能满足给定的位置约束要求。结论 通过与现有其他算法的优点和局限性对比,结果表明本文算法具有较好的鲁棒性。本文算法从一个全新的角度促进了无翻转体映射生成技术的进步与发展。     

一种高效的FDE并行传播算法

约束规划(constraint programming, CP)是表示和求解组合问题的经典范式之一.扩展约束(extensional constraint)或称表约束(table constraint)是约束规划中最为常见的约束类型.绝大多数约束规划问题都可以用表约束表达.在问题求解时,相容性算法用于缩减搜索空间.目前,最为高效的表约束相容性算法是简单表约缩减(simple table reduction, STR)算法簇,如Compact-Table (CT)和STRbit算法.它们在搜索过程中维持广义弧相容(generalized arc consistency, GAC).此外,完全成对相容性(full pairwise consistency, fPWC)是一种比GAC剪枝能力更强的相容性.最为高效的维持fPWC算法是PW-CT算法.多年来,人们提出了多种表约束相容性算法来提高剪枝能力和执行效率.因子分解编码(factor-decomposition encoding, FDE)通过对平凡问题重新编码.它一定程度地扩大了问题模型,使在新的问题上维持相对较弱的GAC等价于在原问题...