近日，泰山学堂计算机取向三年级许嘉城同学的投稿文章《P2M: A Fast Solver for Querying Distance from Point to Mesh Surface》（以下简称P2M）被SIGGRAPH journal track录用（Conditionally accept），同时将刊登于图形学顶级期刊ACM Transactions on Graphics。ACM SIGGRAPH是中国计算机学会（CCF）推荐的计算机图形学与多媒体领域A类期刊，中科院分区SCI Top 1区，影响因子7.403。指导老师为计算机科学与技术学院辛士庆副教授。
图 1 所提出的距离查询算法比串行的PQP快5-6倍，比SIMD并行化的FCPW快2-4倍
ACM SIGGRAPH是迄今为止世界上影响最广、规模最大，也是最权威的图形学技术展示和学术会议，平均接受率在21%左右。论文评审流程非常严格，每篇文章需要至少5名相关专家提供详细评审意见。审稿专家对P2M的创新性给予了普遍赞赏和高度肯定，其中有4位审稿人给出了3分的高分。
该文的研究主题是点到网格曲面的最近距离查询（图1），这是多个学科领域共同关心的基础研究课题。在上个世纪80年代和90年代，国内外的专家学者发表了大量学术论文，形成了以“层次包围盒”为关键数据结构的启发式查询方法（BVH）。其中，发表于1999年的PQP算法被认为是针对该问题的最好算法。20多年以来，该问题的研究并未取得实质性进展。该问题的挑战在于网格曲面的不规则性。BVH结构使用类型统一的包围体包裹这些几何基元，尽管解决了规范性的问题，但是包围体无法精准捕捉几何基元的结构特点。正是基于这样的观察，新提出的P2M打破了层次包围盒的传统算法框架，创新性地提出了“以简单基元代理复杂基元”的新颖想法，使用有限数目的顶点代理所有的几何基元，巧妙地将点到三维模型的距离查询问题转化为标准的kd树近邻查询问题。实验结果表明，新方法比经典PQP快5到6倍，比FCPW（注：基于SIMD指令的并行化PQP）快2到4倍，实现了20多年以来在该问题上的首次重大突破。
图 2 许嘉城同学与指导教师辛士庆副教授
面对艰巨的科研任务，许嘉城在自身的不懈坚持与辛士庆老师的鼓励与帮助下，成功攻克一个又一个难题。在提高预处理速度方面，提出包围盒辅助的kd树结构；在提高查询效率方面，提出查询空间与几何基元同时进行编码的策略。辛勤钻研，终成硕果。
参与本文研究的学生还有博士生宗辰（本文共同一作）和博士生宋建涛(本文三作；泰山学堂计算机取向2017级)。此外，山东大学屠长河教授、美国德州农工大学王文平教授和青岛科技大学陈双敏副教授为本文研究做出了重要贡献。
