CCD查询基准数据集

该数据集由纽约大学创建，包含6000万条查询，旨在为连续碰撞检测（CCD）算法提供大规模基准。数据集包括手动设计的查询，用于突出挑战性的退化情况，以及从模拟序列中提取的大量真实世界查询。数据集用于评估最先进的CCD算法的准确性、正确性和效率，支持研究高效和正确的CCD算法。

This dataset was created by New York University and contains 60 million queries, serving as a large-scale benchmark for continuous collision detection (CCD) algorithms. It includes manually designed queries that highlight challenging degenerate cases, as well as a large number of real-world queries extracted from simulation sequences. The dataset is used to evaluate the accuracy, correctness, and efficiency of state-of-the-art CCD algorithms, supporting research into efficient and correct CCD algorithms.

搜集汇总

数据集介绍

构建方式

在计算机图形学与科学计算领域，连续碰撞检测（CCD）算法的可靠性至关重要。CCD查询基准数据集的构建融合了人工设计与自动生成的双重策略。研究团队精心设计了超过1.2万个点-三角形和1.5万个边-边查询，这些查询专门针对几何退化情形，如点-点退化、近碰撞、共面运动等，以揭示算法在极端条件下的表现。同时，通过运行非线性弹性仿真，从真实物理模拟序列中自动提取了超过1800万个点-三角形和4100万个边-边查询，覆盖了常见碰撞场景。所有查询的真实碰撞结果均使用Mathematica符号求解器精确计算，确保了基准数据的权威性与可靠性。

特点

该数据集的核心特点在于其规模宏大与场景全面。它不仅包含了海量的仿真查询，以反映实际应用中的普遍情况，还专门构造了具有挑战性的退化案例，能够有效暴露现有CCD算法在数值鲁棒性上的缺陷。数据集为每项查询提供了精确的基准真值，使得对算法正确性（误报与漏报）和效率的定量评估成为可能。尤为重要的是，它首次系统性地揭示了多数现有算法在精度与效率之间的两难困境：要么正确但速度缓慢，要么高效却可能漏检碰撞，为后续研究提供了清晰的改进方向。

使用方法

该数据集主要用于系统评估与比较各类连续碰撞检测算法的性能。研究人员可将待测算法在数据集的所有查询上运行，通过对比算法输出与基准真值，精确统计其误报、漏报数量及平均运行时间，从而全面衡量算法的准确性、保守性和效率。数据集支持对算法参数（如容差）的敏感性分析，并可用于验证新型算法（如论文提出的基于包含函数的二分法）的优越性。此外，其包含的最小分离距离查询，为需要在物理仿真或制造中确保安全间距的应用提供了专门的测试基准。

背景与挑战

背景概述

在计算机图形学与科学计算领域，连续碰撞检测（CCD）是确保动态模拟真实性与稳定性的核心技术。CCD查询基准数据集由Bolun Wang等研究人员于2021年构建，旨在系统评估现有CCD算法的准确性、正确性与效率。该数据集通过手工构造的退化案例与基于物理模拟生成的常见查询，全面覆盖了从简单到复杂的碰撞检测场景。其核心研究问题在于解决传统CCD算法在精度与效率之间的固有矛盾：多数算法或因过于保守而产生大量误报，或为追求速度而引入漏报风险，导致模拟失真。该数据集的发布为CCD算法的标准化测试提供了重要基础，推动了高鲁棒性碰撞检测技术的发展，对物理模拟、动画生成及工程计算等领域产生了深远影响。

当前挑战

CCD查询基准数据集所针对的领域问题在于连续碰撞检测的算法可靠性挑战。现有方法常因浮点运算误差导致漏报或误报，尤其在处理退化几何配置（如共面运动、近碰撞情形）时表现不稳定。数据集的构建过程亦面临多重挑战：首先，需通过符号计算工具（如Mathematica）生成高精度地面真值，但该方法计算成本极高，难以直接应用于实时模拟；其次，手工设计涵盖各类退化情形的查询案例要求对CCD算法的失效模式有深刻理解；此外，从实际物理模拟中提取大规模查询时，需确保数据既能反映真实场景的复杂性，又能有效暴露算法的边界条件缺陷。这些挑战共同凸显了开发兼顾效率与正确性的CCD算法的迫切需求。

常用场景

经典使用场景

在计算机图形学和物理仿真领域，连续碰撞检测（CCD）是确保动态物体交互真实性的核心技术。CCD查询基准数据集通过精心构建的手工查询和仿真生成的查询，为评估CCD算法的准确性、正确性和效率提供了标准化测试平台。该数据集最经典的使用场景在于系统性地验证不同CCD方法在顶点-面片和边-边碰撞检测中的表现，尤其是在处理高速运动物体和几何退化情况时，能够揭示算法在误报与漏报之间的权衡。

解决学术问题

该数据集有效解决了连续碰撞检测研究中长期存在的算法可靠性问题。传统CCD方法往往在效率与正确性之间难以兼顾，要么因计算复杂度过高而难以实用，要么因浮点误差导致漏检或误报。通过提供大规模基准查询和精确地面真值，该数据集使研究者能够定量分析不同算法的性能边界，识别并修复现有方法的缺陷。其意义在于推动了CCD算法向更高鲁棒性发展，为物理仿真、机器人运动规划等需要精确碰撞检测的领域奠定了坚实的实验基础。

衍生相关工作

该数据集的发布催生了多项经典研究工作，特别是在高效保守碰撞检测算法设计方面。基于数据集的评估结果，研究者提出了结合区间根查找和现代谓词设计技术的新型CCD算法，在保持正确性的同时大幅提升运行效率。此外，数据集还启发了对最小间隔检测方法的改进，支持L∞范数下的距离计算，为精密仿真和制造应用提供了新工具。这些衍生工作进一步推动了CCD领域向更严谨的理论基础和更实用的工程实现方向发展。