随着三维传感技术和三维建模软件的快速发展,数字化三维几何模型急剧增加,成为了继图像之后的新一代多媒体数据类型,广泛应用于各个领域,为计算机图形学的发展和应用提供了新的机遇与挑战。本文将大量涌现的三维模型和已经大量存在的二维模型统一称为形状。随着形状数据的日益增多,如何实现对形状的分析和理解逐渐成为了计算机视觉、计算机图形学和科学数据可视化等领域的研究热点问题。本文针对二维形状的几何切割问题和三维形状的对应问题展开研究,主要工作如下:(1)针对二维几何形状之间的可反转链式几何切割问题,第一个提出了一个快速的筛选机制和一个完全自动的构造算法。该筛选机制从形状大数据集中快速地挑选出可能具有可反转链式几何切割的潜在形状对,作为后续构造算法的输入形状对。构造算法自动地计算两个输入形状之间的最佳近似可反转链式几何切割,使得形状边界经过微小的变形后,具有精确的切割。最后,我们用三维打印制造形状块,并为它们添加合适的连接器,得到真正的益智玩具。本文提出的筛选机制和构造算法探索、构造和制造出了大量有趣的可反转链式几何切割,极大地扩展了几何切割问题研究的形状范围,使得几何切割问题不再局限于简单的多边形或没有意义的几何形状。(2)针对近似等距的三维几何形状之间的全局稠密点对应问题,我们采用前沿的函数映射的表示方式,将形状对应问题转化为一个带描述子、区域和正交约束的优化问题并直接高效求解。我们将该优化模型分别应用于单个近似自等距形状的全局内蕴对称性检测和两个内蕴对称形状之间的近似等距对应。应用该优化模型的主要挑战在于构建充足可靠的约束,使得最优解对于非等距变形具有更强的鲁棒性。为了克服这个挑战,我们致力于提取充分可靠的区域约束。针对全局内蕴对称性检测问题,首先,提取稀疏可靠的初始区域约束,随后通过一个投票策略得到更多的区域约束。针对近似等距对应问题,基于形状具有内蕴对称性的假设,分别提取每个形状的对称轴和肢端点,组成了稳定而又分布广泛的特征点集,通过计算两个形状的特征点集之间的对应,得到了均匀分布的区域约束。在形状对应基准点集上的实验结果显示,对于各种类型的在一定程度上偏离严格等距的形状,本文的方法能够提高对应的精度。(3)针对具有大变形的三维几何形状之间的局部稀疏点对应问题,提出了一种结合了曲线骨架图和形状子结构的形状对应算法。由于形状的曲线骨架图是形状几何和结构的简洁抽象,更适用于提取大变形形状之间的语义对应,我们致力于建立两个骨架之间的特征节点对应。由于孤立的形状部件的几何性质不再相似,我们转而去提取和比较显著的形状子结构,即在一组语义相关的骨架中重复出现的骨架子图——部件布局。首先,提取骨架的内蕴反射对称轴,用以指导生成部件布局。随后,对于来自两个骨架的任意两个部件布局,对齐朝向,归一化姿势差异,以用于匹配。最后,评估所有部件布局对的匹配并将其累积到骨架特征节点的对应中。在各种各样大变形的形状对上的实验结果显示,本文的方法显著地提高了语义对应的效率和精度。