【摘要】 本发明提供一种三角网格曲面模型的空间查询方法，首先将表达产品型面信息的三角面片数据与索引结构中的结点均表达成相应的四维点对象，通过选择插入位置、采用四维聚类分簇方法实现结点分裂、索引结构中结点轴向包围盒及对应四维点对象调整等步骤对四维点对象进行空间聚类划分，实现三角网格曲面中三角面片的空间聚类划分，建立三角网格曲面模型索引结构，基于该结构可提高离散三角网格曲面模型各种空间查询操作效率，有效提高产品逆向工程数据处理速度，并保证处理结果的稳定性与准确性。 【专利类型】发明授权 【申请人】山东理工大学 【申请人类型】学校 【申请人地址】255086 山东省淄博市高新技术产业开发区高创园D座1012室 【申请人地区】中国 【申请人城市】淄博市 【申请人区县】张店区 【申请号】CN200810159748.0 【申请日】2008-11-12 【申请年份】2008 【公开公告号】CN101430693B 【公开公告日】2010-08-11 【公开公告年份】2010 【授权公告号】CN101430693B 【授权公告日】2010-08-11 【授权公告年份】2010.0 【IPC分类号】G06F17/30; G06T17/00 【发明人】孙殿柱; 田中朝; 李心成; 李延瑞 【主权项内容】一种三角网格曲面模型的空间查询方法，其特征在于包含以下步骤：一、从三角网格曲面模型数据文件读取三角网格曲面模型数据并建立数据结点，为每个三角面片建立轴向包围盒，根据轴向包围盒中心及轴向包围盒外接球半径将数据结点处理成四维点对象，建立数据结点链表；二、基于三角面片的轴向包围盒及对应的四维点对象，建立三角网格曲面模型索引结构，其步骤为：为结点选择插入位置、采用四维聚类分簇方法实现结点分裂、索引结构中结点轴向包围盒及对应四维点对象调整，其中：为结点选择插入位置的步骤具体是：1)指定要插入的新结点和插入层号，2)设当前结点为current_node，如果索引结构为空则返回空，否则令current_node为索引结构根结点、当前层号为1；3)令current_node的每个子结点包含欲插入到索引结构的新结点，计算包含新结点后结点的轴向包围盒外接球半径，与原结点外接球半径相比较，以外接球半径增量最小的结点作为current_node；4)如果存在大于或等于2个结点在包含新结点后符合外接球增量最小，则计算外接球增量最小的结点在插入新结点后与其兄弟结点的外接球重叠度增量，并选择重叠度增量较小的子结点作为current_node；5)如果存在大于或等于2个外接球重叠度增量最小的结点，则选择包含新结点后外接球半径最小的结点作为current_node，令当前层号加1；6)返回步骤3)直到当前层号等于新结点欲插入的层号；索引结构中结点轴向包围盒及对应四维点对象调整的具体步骤是：1)设轴向包围盒发生变化的索引结点为src_node；2)调整索引结点src_node的轴向包围盒，使得src_node的轴向包围盒恰好包含src_node的所有子结点的轴向包围盒，并调整索引结点src_node对应的四维点坐标值；3)若src_node为根索引结点，程序返回，否则执行步骤4)；4)令src_node为src_node的父结点，调整索引结点src_node轴向包围盒，使得src_node的轴向包围盒恰好包含src_node的所有子结点的轴向包围盒，并调整索引结点src_node对应的四维点坐标值，返回步骤3)；三、基于三角网格曲面模型索引结构，采用剪枝策略实现三角面片拓扑近邻三角面片查询和两三角网格曲面模型的相交区域查询，其中：采用剪枝策略查询三角面片拓扑近邻三角面片的具体步骤是：1)设当前结点current_node为三角网格曲面模型索引结构的根索引结点；2)若current_node的轴向包围盒与目标三角面片的轴向包围盒相交则执行步骤3)，若current_node的轴向包围盒与目标三角面片轴向包围盒不相交则返回；3)若current_node为非叶索引结点则执行步骤4)，若current_node为叶索引结点，则依次比较current_node的子结点轴向包围盒与目标三角面片轴向包围盒是否相交，如果不相交则继续比较下一个子结点，如果相交则比较该子结点对应的三角面片是否与目标三角面片存在公共边，若存在公共边则将该子结点添加到目标三角面片的邻接关系表中，若不存公共边在则继续比较下一个子结点，直到比较完current_node所有子结点，程序返回；4)令current_node依次为current_node的子结点，执行步骤2)；采用剪枝策略查询两三角网格曲面模型相交区域的具体步骤是：1)设两三角网格曲面模型分别为S1和S2；2)遍历三角网格曲面模型S1中的三角面片，以S1中的每个三角面片作为目标三角面片执行步骤3)；3)设当前结点current_node为三角网格曲面模型S2的索引结构的根索引结点；4)若current_node的轴向包围盒与目标三角面片的轴向包围盒相交则执行步骤5)，若current_node的轴向包围盒与目标三角面片轴向包围盒不相交则返回；5)若current_node为叶索引结点，则依次比较current_node的子结点轴向包围盒与目标三角面片轴向包围盒是否相交，如果不相交则继续比较下一个子结点，如果相交则对该子结点对应的三角面片与目标三角面片进行求交运算，如果存在交点则将该子结点对应的三角面片标记为相交区域三角面片，同时标记目标三角面片为相交区域三角面片，若不存在则继续比较下一个子结点，直到比较完current_node所有子结点，程序返回，若current_node为非叶索引结点则执行步骤6)；6)令current_node依次为current_node的子结点，执行步骤4)。 【当前权利人】山东理工大学 【当前专利权人地址】山东省淄博市高新技术产业开发区高创园D座1012室 【统一社会信用代码】1237000049557139X7 【被引证次数】1 【被自引次数】1.0 【家族被引证次数】8
