细分曲面求交交线计算方法的研究

主要针对三角网格的细分曲面求交提出了一种有效的交线计算的方法,该方法适用于任意三角网格的细分曲面中.在利用AABB和二部图进行初始控制网格相交性检测后,利用该方法快速有效地求出细分曲面的交线.     

基于Catmull-Clark细分的曲面布尔运算基础研究

基于Catmull-Clark细分,提出一种对平面四边型网格进行操作的基础布尔运算,包括曲面求交、裁剪和网格级基础布尔运算,首先将细分曲面的求交转换为对一定细分层次的细分控制网格求交,得到满足一定精度要求的交线;采用局部修改交点处的控制网格拓扑结构和控制网格顶点位置的方法,实现了对细分曲面的裁剪;最后提出一种对一定细分层次的四边形控制网格进行操作的布尔运算,称之为细分曲面网格级布尔运算,包括布尔交、布尔并和布尔差3种运算,并给出了运算的基本原则与应用实例.     

一种基于矩形网格加速的曲面裁剪算法

在地质模型中.曲面一般用三角网格来表示.在三维地质建模过程中经常需要对曲面进行裁剪操作,本文描述了一种网格曲面裁剪算法.它是将传统裁剪算法中的曲面三角网格和三角网格求交简化为曲面三角网格和矩形网格求交,由于矩形网格的数据结构简单.查找和定位方便(可以直接根据坐标值定位到所位于的矩形网格单元),算法简练,较大的提高了计算速度.     

改进的布尔方法及其在虚拟ACL手术中的应用

为了实现在虚拟ACL手术中对骨骼模型进行钻孔操作的动态模拟,提出了一种针对面网格模型的改进布尔操作方法.首先对与切割曲面相交的三角形进行细分,并移动切割曲面附近的网格顶点使其位于曲面上,实现模型表面上的布尔操作;然后对切割曲面附近的模型表面进行平滑处理,以消除在顶点移动操作中带来的模型表面锯齿状现象;最后采用前沿推进方法生成模型的内壁网格,并利用基于时间的钻孔深度控制函数实现对钻孔操作过程的动态模拟.该方法消除了近似布尔方法中的"T"型点问题,能够保持模型表面平滑效果和切割边缘尖锐特征,实现了对布尔操作的动态模拟,满足实时性的要求.该方法适用于实时系统中针对面网格模型的动态、交互式布尔操作模拟.     

可展曲面的自动识别与重建

为了重建具有复杂形状的可展曲面模型,得到反映可展曲面几何本质的表示,提出一种可展曲面的自动识别与重建方法.首先计算输入网格模型的平面逼近表示,自动识别出模型的可展区域,并且得到每一个区域的近似可展B样条曲面表示;然后通过迭代曲面扩展和曲面拟合2个步骤,得到一组覆盖模型全部区域的B样条可展曲面片;最后对曲面片裁剪和求交,得到重建的无缝隙的可展曲面网格表示.实例结果表明,该方法能够正确重建原始模型上的折痕或特征线,而且能在一定程度上恢复缺损数据的曲面特征.     

基于网格划分的曲面求交算法

本文综合网格逼近法和追踪法求交的优点，提出了一种曲面求交算法。该算法首先对曲面进行三角形网格划分，再用追踪法求各网格之间的交线，最后拟合成三次参数曲线。     

细分曲面求交裁剪算法研究

基于细分曲面的参数化表示,研究了细分曲面的精确求交、裁剪算法。首先对控制网格建立局部坐标系,将细分曲面表示为一系列小的面片,并对每个控制顶点赋予参数值。然后用改进的轮廓删除法细分控制网格,在关联曲面间进行相交性检测,得到近似交点及其参数值,再用迭代法求得精确解。根据用户指定的裁剪区域确定交线的走向,将被裁剪曲面的控制网格面分为保留面、裁剪面和删除面,设置每个裁剪面的裁剪域,从而实现细分曲面的精确裁剪。算例表明,该文的方法简单、有效。     

基于空间多边形三角剖分的曲面分割求交算法

针对传统曲面分割求交方法存在的平面片的选取、遗漏部分交线段以及交线间断 的问题,提出一种基于空间多边形三角剖分的曲面分割求交算法。以等深度分割方法为基础, 避免了交线不连续的问题,当分割达到一定层次时以空间多边形近似曲面片,并对空间多边形 进行三角剖分,以三角形对的交线近似空间多边形之间的交线,进而以空间多边形的交线近似 曲面片的交线,最终得到相交曲面之间的交线。利用曲面片轮廓构造出的空间多边形更加接近 曲面片的真实形状,提高了逼近精度,同时对空间多边形进行三角剖分,提高了求交精度,进 而降低了丢失交线的可能性。实验验证了该算法比传统的分割法更加精确。     

基于八叉树和混合搜索树的地质曲面快速求交方法

为处理地质界面之间的空间相交关系,提出一种新的针对三角地质曲面的快速求交方法。该方法融合优化八叉树法和OBB搜索树方法,可以更快速准确地剔除远离交线的其他三角形。求交剩余的三角形得到交线,应用三角网局部重构和网格优化算法修正交线附近的三角网,最终分割交线两侧的地质曲面,完成2个地质曲面的离散化求交过程。与AABB、OBB和空间分解法相比,该方法在大数据量三角曲面求交中效率优势明显,可以快速准确处理地质模型构建和分析中的曲面求交问题,为三维地质模型自动化构建的实现提供有效支撑。     

复杂曲面加工精度检验中曲面法矢与刀具扫描体求交算法的研究

提出了一种用于实现矢量与扫描体（代表五轴数控加工铣刀的运动）求交的有效算法,该算法首先对曲面法矢和刀具扫描体进行预处理,将曲面法矢与刀具扫描体之间的求交问题转化为有向线段与三角网格之间的求交计算,然后建立有向线段和三角网格的求交子集,减少了不必要的求交计算,提高了乍法的效率。文中举例说明了该算法在复杂曲面NC精度检验中的应用。     

Approximate straightest path computation and its application in parameterization

This paper proposes an approaching method to compute the straightest path between two vertices on meshes. An initial cutting plane is first constructed using the normal information of the source and destination vertices. Then an optimal cutting plane is iteratively created by comparing with previous path distance. Our study shows that the final straightest path based on this optimal cutting plane is more accurate and insensitive to the mesh boundary. Furthermore, we apply the straightest path result to compute the measured boundary in the parameter domain for mesh parameterization, and we obtain a new computing formula for vertex stretch in the planar parameterization. Experimental results show that our parameterization method can effectively reduce distortions.     

三角网格模型上任意两点间的近似最短路径算法研究

提出一种任意三角网格模型上两点间的近似最短路径算法．该算法首先将三角网格模型表示为带权图结构，然后用Dijkstra算法计算带权图中两顶点间的最短路径，并将其作为网格模型上该两点间最短路径的初始近似．通过不断地迭代对相关三角形边进行自适应细分，并构造每次细分后新的带权图，从而对网格模型上的两点间最短路径进行迭代逼近．该算法效率高，可以很好地控制精度，适用于大型三角网格模型两点间最短路径寻找．文中还讨论了该算法在任意三角网格模型区域划分中的应用．     

Direct boolean intersection between acquired and designed geometry

In this paper, a new shape modeling approach that can enable direct Boolean intersection between acquired and designed geometry without model conversion is presented. At its core is a new method that enables direct intersection and Boolean operations between designed geometry (objects bounded by NURBS and polygonal surfaces) and scanned geometry (objects represented by point cloud data).We use the moving least-squares (MLS) surface as the underlying surface representation for acquired point-sampled geometry. Based on the MLS surface definition, we derive closed formula for computing curvature of planar curves on the MLS surface. A set of intersection algorithms including line and MLS surface intersection, curvature-adaptive plane and MLS surface intersection, and polygonal mesh and MLS surface intersection are successively developed. Further, an algorithm for NURBS and MLS surface intersection is then developed. It first adaptively subdivides NURBS surfaces into polygonal mesh, and then intersects the mesh with the MLS surface. The intersection points are mapped to the NURBS surface through the Gauss-Newton method.Based on the above algorithms, a prototype system has been implemented. Through various examples from the system, we demonstrate that direct Boolean intersection between designed geometry and acquired geometry offers a useful and effective means for the shape modeling applications where point-cloud data is involved.     

Smooth tool path generation for 5-axis machining of triangular mesh surface with nonzero genus

NC machining of a nonzero genus triangular mesh surface is being more widely confronted than before in the manufacturing field. At present, due to the complexity of geometry computation related to tool path generation, only one path pattern of iso-planar type is adopted in real machining of such surface. To improve significantly 5-axis machining of the nonzero genus mesh surface, it is necessary to develop a more efficient and robust tool path generation method. In this paper, a new method of generating spiral or contour-parallel tool path is proposed, which is inspired by the cylindrical helix or circle which are a set of parallel lines on the rectangular region obtained by unwrapping the cylinder. According to this idea, the effective data structure and algorithm are first designed to transform a nonzero genus surface into a genus-0 surface such that the conformal map method can be used to build the bidirectional mapping between the genus-0 surface and the rectangular region. In this rectangular region, the issues of spiral or contour-parallel tool path generation fall into the category of simple straight path planning. Accordingly, the formula for calculating the parameter increment for the guide line is derived by the difference scheme on the mesh surface and an accuracy improvement method is proposed based on the edge curve interpolation for determining the cutter contact (CC) point. These guarantee that the generated tool path can meet nicely the machining requirement. To improve further the kinematic and dynamic performance of 5-axis machine tool, a method for optimizing tool orientation is also preliminarily investigated. Finally, the experiments are performed to demonstrate the proposed method and show that it can generate nicely the spiral tool path or contour-parallel tool path on the nonzero genus mesh surface and also can guarantee the smooth change of tool orientation.     

针对面模型的顶点移动切割算法研究

传统的基于面模型的切割算法容易产生劣质三角形,且运行效率不高,因此提出顶点移动的算法解决该问题。该算法首先确定切割路径,求出相交交点;根据判定准则确定需要移动的顶点;对移动顶点后的面模型进行网格重构。分别从算法的运行效率和切割后的效果演示2个方面将传统算法与移动顶点算法进行了全面的比较。利用Vc和OpenGL对算法进行了验证,结果表明,采用顶点移动算法对于多次切割和复杂模型可以大大提高运行效率,且可获得良好的虚拟切割效果。     

Spherical cuts for integer programming problems

We introduce a new family of valid inequalities for general linear integer programming problems, based on the distance of the relaxed solution to the closest integral point. We show that these are valid cuts, establish some relations with Balas' intersection cuts, and show that a straightforward cutting plane algorithm derived from either spherical or intersection cuts will in general only converge if a suitable Gomory‐type strengthening is put in place.     

A mapping-based approach to eliminating self-intersection of offset paths on mesh surfaces for CNC machining

Geometrically, a tool path can be generated by successively offsetting its adjacent path on the surface with a given path interval, which preferably starts from one of the surface boundaries or a primary curve. The key issues involved in offset path planning are the generation of raw offset paths and the elimination of the self-intersection of raw offset paths. Most researches available in this area are focused on how to generate the raw offset paths, however, the latter, especially how to eliminate the self-intersection of the offset paths on mesh surfaces, has not been sufficiently addressed. In this paper, a mapping-based approach to eliminating the self-intersection of offset paths is proposed for the CNC machining of mesh surfaces. The method first flattens the mesh surface onto a predefined plane by using a mesh mapping technique, and then taking the mapping as a guide, the offset paths are also naturally mapped onto the plane, from which those invalid self-intersection loops can be effectively identified and eliminated. To handle the issue of self-intersection for all types of offset path, a notion of local loop is introduced to detect and eliminate the invalid self-intersection loops. After that the planar paths are inversely mapped into the physical space and the final tool paths used for the machining of mesh surface are obtained. Meanwhile, in order to improve the kinematic and dynamic performance of the machine tool when machining along the generated offset paths, a method for rounding the sharp corners of tool paths, which result from the process of eliminating the self-intersection of raw offset paths, is also preliminarily investigated. Finally, the proposed method is validated by the results of simulations and machining experiments.     

六面体体元网格三维地质模型剖切算法

针对常用的六面体体元网格三维地质模型,提出了一种求剖切面的算法.首先,采用分层投影求交点的方式,将地质体模型与切割面投影到同一平面,三维空间下的地质体模型与切割面的剖切转化为二维平面上的四边形网格与切线段求交点的运算.为减少判交次数,先根据切线走势判断可能存在交点的区域,再对可能区域进行精确判交.其次,找到并求出不能通过投影方式得到的交点.然后,将得到的所有交点按规则组成四边形网格,对每个四边形三角化处理得到TIN形式的剖切面.最后,对该TIN面进行显示.实验证明了对六面体体元网格三维地质模型剖切的可行性.     

装配机器人系统快速碰撞检测算法

提出一种面向操作手段装配系统的快速碰撞检测算法。该算法以机器人运动学和空间解析几何为基础,将判断机械手手臂与障碍物是否发生碰撞问题转化为直线段与有界平面是否存在公共点的简单解析几何问题,并以PUMA560操作手为例对算法加以说明,该算法不仅适用于静态的障碍物已知的环境,而且适用于障碍物运动规律已知的动态环境,减少了碰撞检测占用的时间,提高了路径规划的效率。     

基于侧影轮廓的三维模型快速重建

提出一种基于侧影轮廓进行三维模型重建的新方法,将传统的三维锥形交叉问题转换成二维轮廓交叉问题。首先,将不同视角下的二维侧影轮廓反投影到若干个平行的三维平面上,然后在三维平面上计算所有反投影轮廓的交叉轮廓,最后对相邻三维平面上的交叉轮廓进行匹配并重建物体的表面。理论分析和实验结果表明该算法的时间复杂度和视角数目呈线性关系。由于该方法主要以增加视角数目来提高模型的精确度,所以比三维锥形交叉的方法能更快速地重建物体精确的三维模型。