一般多边形网格模型的几何压缩方法

使用Face Fixer方法对由一般多边形网格构成的三维模型拓扑信息进行了压缩,采用3阶自适应算术编码进一步提高压缩比,通过把顶点位置坐标变换到局部坐标系中,结合量化、平行四边形顶点坐标预测以及算术编码来实现三维网格模型几何信息的压缩,在几何模型质量基本没有损失的情况下,获得了很好的压缩性能。

一种高效的一般多边形线段裁剪算法

直线段的裁剪是图形绘制中的基本问题,针对当前主流的直线段裁剪算法,或者不能适应一般多边形窗口的裁剪,或者在复杂裁剪情况下裁剪效率低下的问题,提出了一种高效的一般多边形线段裁剪算法。该算法排除掉明显不在裁剪窗口内的直线段,以及相交于伪交点的情况,再利用改进的交点计数法确定位于窗口内的区间。实验结果表明,该算法不仅具有高效性,还能适应于复杂的裁剪情况。

平面中点对一般多边形的最近邻查询研究

平面中点对一般多边形的最近邻查询问题是要在一般多边形集合中找到查询点的最近邻以及顺序最近邻。针对查询对象的特殊性,以R树作为索引结构,采用一般多边形的凸包组织空间结构。通过判断可见边计算查询点到凸包的最小距离。采用优先队列的方法给出查询点到每个凸包的最小距离的排序,最终找到查询点的最近邻和顺序最近邻。

折线链节点标注技术

针对传统多边形位置关系计算比较烦琐,以及简单多边形的理论难以拓展到一般多边形的问题,提出标注节点状态的方法.通过定义11种位置来描述折线链上每个节点的状态,再采用"线段端点与线段"和"线段端点与邻折线"的标注方法来实现任意折线链的标注,同时利用两线段分割预处理使相交仅发生在端点处,从而使算法更高效;然后给出折线链基本位置关系的节点特征,并且探讨了三维顶点的标注方法.该方法的标注原理简单、方法实用,算法空间和时间复杂度分别为O(n)和O(n2).实验结果表明,该方法对任意形状的折线链都能实现稳定标注;通过搜索节点状态特征可以求解折线链间的相互关系,还可以实现一般折线链的碰撞检测、相交区域计算以及多边形简单化分解等.