Newton 引擎按形状排序软接触候选对确定性接触排序的设计、实现与性能权衡【免费下载链接】newtonAn open-source, GPU-accelerated physics simulation engine built upon NVIDIA Warp, specifically targeting roboticists and simulation researchers.项目地址: https://gitcode.com/GitHub_Trending/newton9/newton本文围绕 Newton 物理引擎 changelog 片段 4141.changed.1.md 所记录的核心变更展开软接触soft contact候选对开始在每一个设备CPU / CUDA上按形状shape排序。文章将深入其底层实现——64 位接触排序键的位布局、基于 Warp 基数排序的ContactSorter、软接触流的接入方式并解析该变更带来的行为影响与性能权衡。读完本文你将理解 Newton 接触管线中确定性排序的完整链路以及为什么此类排序变更会在浮点容差和容量溢出时产生可观察的结果差异。一、变更记录解读一条 changelog 背后的三层信息4141.changed.1.md 的原文只有一句话Sort soft-contact candidate pairs by shape on every device. Results can shift within floating-point tolerance, and when contact capacity overflows the retained subset can differ. Faster on scenes with many shapes or worlds; a little slower on small dense-contact scenes.这条记录事实上包含三层工程信息变更内容软接触候选对在窄相narrow phase之后按形状索引排序且该行为在所有设备上统一生效on every device结果语义排序会重排接触数组因此浮点计算本身不变但结果可在浮点容差范围内发生偏移当接触数量超出预分配容量capacity overflow时被保留的接触子集会因排序而不同性能特性在形状多、world 多的场景中更快在形状少、接触密集的小场景中略慢。这三点均可在仓库源码中得到印证。变更对应的接触排序机制是本文的核心其实现分布在newton/_src/geometry/下的contact_sort.py、contact_data.py以及窄相与软接触管线中。二、排序键如何把按形状排序编码进一个 int64按形状排序在实现上并不是直接比较两个 shape 索引而是为每个接触构造一个64 位字典序排序键再对键做基数排序。键的构造定义在 contact_data.pyCONTACT_SORT_SUB_KEY_BITS 23 CONTACT_SORT_MAX_SHAPE_INDEX_BITS 20 wp.func def make_contact_sort_key(shape_a, shape_b, sort_sub_key, shape_index_bits) - wp.int64: ...其位布局来自源码 docstring为[22 2b : 23 b] shape_a (b bits) [22 b : 23] shape_b (b bits) [22 : 0] sort_sub_key (23 bits, 最大 8,388,607)其中b contact_sort_shape_index_bits(shape_count)即按模型实际形状数量动态计算的位宽最多 20 位对应 1,048,575 个形状索引上限。位 63 恒为 0保证 int64 的字典序与 uint64 一致。超过位宽的取值会被静默掩码mask因此各接触路径必须保证其子键不超限网格三角形接触(tri_idx 1) | 1约 22 有效位SDF 接触(edge_idx 2) | (mode 1)约 21 有效位流体静力学hydroelastic接触((voxel_idx * 5 face_idx) 1) | source约 21 有效位。sort_sub_key编码边/三角形/顶点索引等细分信息保证同一个形状对内部也能得到稳定顺序。这一位布局的正确性由 test_contact_reduction_global.py 中的test_sort_key_bit_layout、test_sort_key_shape_index_bits、test_sort_key_overflow_masking等测试直接验证。三、排序执行器ContactSorter与 Warp 基数排序拿到排序键后真正的排序工作由 contact_sort.py 中的ContactSorter完成。它的设计要点如下源码 docstring 均有明确说明3.1 整体机制backup → radix sort → gather 三步每次排序固定执行三步_backup_simple_kernel/_backup_full_kernel把有效接触从live 数组拷贝进预分配的 scratch 缓冲并写入排序键与初始索引wp.utils.radix_sort_pairs(keys, indices, n, end_bit...)对键做基数排序得到排列perm_gather_simple_kernel/_gather_full_kernel按perm把接触字段从 scratch 写回 live 数组。关键实现细节哨兵键sentinel排序始终覆盖完整容量缓冲0x7FFFFFFFFFFFFFFF作为哨兵填到队尾这是为了 CUDA graph 捕获兼容两次 kernel launch 取代 N 次拷贝每个接触布局用一个wp.struct同时持有 live 数组与 scratch 数组将原先N 次 wp.copy N 次 kernel launch压缩为固定 2 次 launch与接触字段数量无关无主机同步、可被 CUDA graph 捕获这是引擎与wp.ScopedDevice、CUDA graph 录制兼容的关键约束key_bit_count参数限制基数排序只扫描被占用的低若干位取值范围 [1, 64]超出会抛ValueError减少基数排序趟数而不改变全容量捕获行为。3.2 两套 APIsort_simple与sort_fullContactSorter对外提供两条排序路径对应两种接触布局方法对应管线排序字段sort_simple简化窄相写入器NarrowPhase.launchpair、position、normal、penetration、可选tangent、可选match_indexsort_full完整碰撞管线CollisionPipeline.collideshape0、shape1、point0、point1、offset0、offset1、normal、margin0、margin1、tids、可选stiffness/damping/friction、可选match_indexmatch_index由 contact_match.py 中的ContactMatcher提供排序时随其他接触字段一并置换从而保证跨帧接触匹配与排序结果一致。ContactSorter还暴露sorted_keys_view排序后的键视图以及两个供ContactMatcher复用的 scratch 缓冲scratch_pos_world/scratch_normal仅在两帧之间的空闲窗口可用源码注释明确警告在窗口外写入会破坏下一次排序。四、接入点软接触流如何被按形状排序4.1 软接触流的产出soft_contacts_sdf.py软接触软体/布料粒子与形状的接触由 soft_contacts_sdf.py 与 kernels.py 中的create_soft_contacts写出。这些写入器通过原子计数器把记录追加进统一软接触流其数组包括soft_contact_count、soft_contact_tids、soft_contact_particle、soft_contact_indices、soft_contact_barycentric、soft_contact_shape、soft_contact_body_pos、soft_contact_body_vel、soft_contact_normal等。其中soft_contact_shape记录的正是每个接触所属的形状索引——这就是按形状排序排序键中的shape_a字段的来源。由于 GPU 线程调度顺序不确定写入流的原始顺序与线程执行顺序相关这正是引入确定性排序的动机。4.2 排序键的写入narrow_phase.py与collide.py两个写入路径都会为每个接触生成排序键简化路径在 narrow_phase.py 的_write_contact_simple_at_index中调用make_contact_sort_key_with_bits(shape_a, shape_b, sort_sub_key, shape_index_bits, sub_key_bits)写入contact_sort_key完整路径在 collide.py 中写入out_sort_key。两个管线各自持有ContactSorter实例见narrow_phase.py第 2634 行与collide.py第 1833 行附近的构造并在帧内调用sort_simple/sort_full如narrow_phase.py第 3606 行附近。整体调用顺序在 contact_match.py 的文档中有明确约定ContactMatcher.match(...)必须在ContactSorter.sort_full(...)之前执行随后match_index会随接触一起被排序置换。五、行为影响浮点容差、容量溢出与性能权衡changelog 中提到的三点影响对应如下工程解释1. 结果可在浮点容差范围内偏移。排序只改变接触数组的存储顺序不改变每个接触的几何与力学数值但求解器按顺序处理接触时浮点累加顺序变化会使结果在浮点容差内轻微偏移。这属于正常现象而非回归。2. 容量溢出时保留子集可能不同。接触数组按capacity预分配超出容量后的记录会被丢弃源码中write_contact_simple对index contact_max直接返回。由于溢出时哪些接触被丢弃取决于写入顺序而写入顺序此前依赖 GPU 线程调度排序后写入顺序变为按形状确定的顺序因此被保留的子集与未排序版本可能不同。这正是 changelog 提醒用户注意的行为语义。3. 性能特性。排序本身有开销但在形状多、world 多的场景中按形状聚合的接触顺序能改善后续接触约简contact_reduction_global.py 中以(shape_a, shape_b, bin_id)为哈希键、接触匹配与求解器的访存局部性因此整体更快而小规模高密度接触场景中排序开销占比相对更高会略有变慢。这是典型的以排序开销换取确定性 访存亲和的工程权衡。六、变更的工程形态Towncrier changelog 片段该文件是 Towncrier 格式的 changelog 片段见 changelog/README.md以4141作为 issue 编号标识符、.changed表示变更类别、.1用于同 issue 下的多片段区分。这类片段在发布分支上由 Towncrier 合并进CHANGELOG.md因此它本身是简短的一句话但其技术语义由上述源码链完整支撑。同目录下的 4141.changed.md 记录的是同一 issue 中SolverVBD刚柔接触与可变形弹性的 CUDA 加速两者共同构成该 issue 的完整变更集。七、小结与验证路径Newton 的按形状排序软接触候选对是一次典型的确定性工程改造用ContactData的sort_sub_key与形状索引构造 64 位排序键由ContactSorter以backup → 基数排序 → gather两步 kernel 的方式在 CUDA graph 可捕获、无主机同步的前提下完成全量确定性排序并统一作用于简化与完整两条接触管线及软接触流。其正确性由位布局、溢出掩码、形状位宽等单元测试newton/tests/test_contact_reduction_global.py保障。如需深入验证建议按以下路径阅读源码排序键位布局与常量contact_data.py排序执行器与哨兵机制contact_sort.py软接触流产出soft_contacts_sdf.py、kernels.py排序键写入与排序调用narrow_phase.py、collide.py确定性校验测试test_contact_reduction_global.py。在升级使用该变更的版本时请记住两条注意事项对结果做逐位比对时应放宽到浮点容差依赖容量溢出后保留哪些接触的仿真其行为可能与旧版本略有不同。【免费下载链接】newtonAn open-source, GPU-accelerated physics simulation engine built upon NVIDIA Warp, specifically targeting roboticists and simulation researchers.项目地址: https://gitcode.com/GitHub_Trending/newton9/newton创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
Newton 引擎按形状排序软接触候选对确定性接触排序的设计、实现与性能权衡【免费下载链接】newtonAn open-source, GPU-accelerated physics simulation engine built upon NVIDIA Warp, specifically targeting roboticists and simulation researchers.项目地址: https://gitcode.com/GitHub_Trending/newton9/newton本文围绕 Newton 物理引擎 changelog 片段 4141.changed.1.md 所记录的核心变更展开软接触soft contact候选对开始在每一个设备CPU / CUDA上按形状shape排序。文章将深入其底层实现——64 位接触排序键的位布局、基于 Warp 基数排序的ContactSorter、软接触流的接入方式并解析该变更带来的行为影响与性能权衡。读完本文你将理解 Newton 接触管线中确定性排序的完整链路以及为什么此类排序变更会在浮点容差和容量溢出时产生可观察的结果差异。一、变更记录解读一条 changelog 背后的三层信息4141.changed.1.md 的原文只有一句话Sort soft-contact candidate pairs by shape on every device. Results can shift within floating-point tolerance, and when contact capacity overflows the retained subset can differ. Faster on scenes with many shapes or worlds; a little slower on small dense-contact scenes.这条记录事实上包含三层工程信息变更内容软接触候选对在窄相narrow phase之后按形状索引排序且该行为在所有设备上统一生效on every device结果语义排序会重排接触数组因此浮点计算本身不变但结果可在浮点容差范围内发生偏移当接触数量超出预分配容量capacity overflow时被保留的接触子集会因排序而不同性能特性在形状多、world 多的场景中更快在形状少、接触密集的小场景中略慢。这三点均可在仓库源码中得到印证。变更对应的接触排序机制是本文的核心其实现分布在newton/_src/geometry/下的contact_sort.py、contact_data.py以及窄相与软接触管线中。二、排序键如何把按形状排序编码进一个 int64按形状排序在实现上并不是直接比较两个 shape 索引而是为每个接触构造一个64 位字典序排序键再对键做基数排序。键的构造定义在 contact_data.pyCONTACT_SORT_SUB_KEY_BITS 23 CONTACT_SORT_MAX_SHAPE_INDEX_BITS 20 wp.func def make_contact_sort_key(shape_a, shape_b, sort_sub_key, shape_index_bits) - wp.int64: ...其位布局来自源码 docstring为[22 2b : 23 b] shape_a (b bits) [22 b : 23] shape_b (b bits) [22 : 0] sort_sub_key (23 bits, 最大 8,388,607)其中b contact_sort_shape_index_bits(shape_count)即按模型实际形状数量动态计算的位宽最多 20 位对应 1,048,575 个形状索引上限。位 63 恒为 0保证 int64 的字典序与 uint64 一致。超过位宽的取值会被静默掩码mask因此各接触路径必须保证其子键不超限网格三角形接触(tri_idx 1) | 1约 22 有效位SDF 接触(edge_idx 2) | (mode 1)约 21 有效位流体静力学hydroelastic接触((voxel_idx * 5 face_idx) 1) | source约 21 有效位。sort_sub_key编码边/三角形/顶点索引等细分信息保证同一个形状对内部也能得到稳定顺序。这一位布局的正确性由 test_contact_reduction_global.py 中的test_sort_key_bit_layout、test_sort_key_shape_index_bits、test_sort_key_overflow_masking等测试直接验证。三、排序执行器ContactSorter与 Warp 基数排序拿到排序键后真正的排序工作由 contact_sort.py 中的ContactSorter完成。它的设计要点如下源码 docstring 均有明确说明3.1 整体机制backup → radix sort → gather 三步每次排序固定执行三步_backup_simple_kernel/_backup_full_kernel把有效接触从live 数组拷贝进预分配的 scratch 缓冲并写入排序键与初始索引wp.utils.radix_sort_pairs(keys, indices, n, end_bit...)对键做基数排序得到排列perm_gather_simple_kernel/_gather_full_kernel按perm把接触字段从 scratch 写回 live 数组。关键实现细节哨兵键sentinel排序始终覆盖完整容量缓冲0x7FFFFFFFFFFFFFFF作为哨兵填到队尾这是为了 CUDA graph 捕获兼容两次 kernel launch 取代 N 次拷贝每个接触布局用一个wp.struct同时持有 live 数组与 scratch 数组将原先N 次 wp.copy N 次 kernel launch压缩为固定 2 次 launch与接触字段数量无关无主机同步、可被 CUDA graph 捕获这是引擎与wp.ScopedDevice、CUDA graph 录制兼容的关键约束key_bit_count参数限制基数排序只扫描被占用的低若干位取值范围 [1, 64]超出会抛ValueError减少基数排序趟数而不改变全容量捕获行为。3.2 两套 APIsort_simple与sort_fullContactSorter对外提供两条排序路径对应两种接触布局方法对应管线排序字段sort_simple简化窄相写入器NarrowPhase.launchpair、position、normal、penetration、可选tangent、可选match_indexsort_full完整碰撞管线CollisionPipeline.collideshape0、shape1、point0、point1、offset0、offset1、normal、margin0、margin1、tids、可选stiffness/damping/friction、可选match_indexmatch_index由 contact_match.py 中的ContactMatcher提供排序时随其他接触字段一并置换从而保证跨帧接触匹配与排序结果一致。ContactSorter还暴露sorted_keys_view排序后的键视图以及两个供ContactMatcher复用的 scratch 缓冲scratch_pos_world/scratch_normal仅在两帧之间的空闲窗口可用源码注释明确警告在窗口外写入会破坏下一次排序。四、接入点软接触流如何被按形状排序4.1 软接触流的产出soft_contacts_sdf.py软接触软体/布料粒子与形状的接触由 soft_contacts_sdf.py 与 kernels.py 中的create_soft_contacts写出。这些写入器通过原子计数器把记录追加进统一软接触流其数组包括soft_contact_count、soft_contact_tids、soft_contact_particle、soft_contact_indices、soft_contact_barycentric、soft_contact_shape、soft_contact_body_pos、soft_contact_body_vel、soft_contact_normal等。其中soft_contact_shape记录的正是每个接触所属的形状索引——这就是按形状排序排序键中的shape_a字段的来源。由于 GPU 线程调度顺序不确定写入流的原始顺序与线程执行顺序相关这正是引入确定性排序的动机。4.2 排序键的写入narrow_phase.py与collide.py两个写入路径都会为每个接触生成排序键简化路径在 narrow_phase.py 的_write_contact_simple_at_index中调用make_contact_sort_key_with_bits(shape_a, shape_b, sort_sub_key, shape_index_bits, sub_key_bits)写入contact_sort_key完整路径在 collide.py 中写入out_sort_key。两个管线各自持有ContactSorter实例见narrow_phase.py第 2634 行与collide.py第 1833 行附近的构造并在帧内调用sort_simple/sort_full如narrow_phase.py第 3606 行附近。整体调用顺序在 contact_match.py 的文档中有明确约定ContactMatcher.match(...)必须在ContactSorter.sort_full(...)之前执行随后match_index会随接触一起被排序置换。五、行为影响浮点容差、容量溢出与性能权衡changelog 中提到的三点影响对应如下工程解释1. 结果可在浮点容差范围内偏移。排序只改变接触数组的存储顺序不改变每个接触的几何与力学数值但求解器按顺序处理接触时浮点累加顺序变化会使结果在浮点容差内轻微偏移。这属于正常现象而非回归。2. 容量溢出时保留子集可能不同。接触数组按capacity预分配超出容量后的记录会被丢弃源码中write_contact_simple对index contact_max直接返回。由于溢出时哪些接触被丢弃取决于写入顺序而写入顺序此前依赖 GPU 线程调度排序后写入顺序变为按形状确定的顺序因此被保留的子集与未排序版本可能不同。这正是 changelog 提醒用户注意的行为语义。3. 性能特性。排序本身有开销但在形状多、world 多的场景中按形状聚合的接触顺序能改善后续接触约简contact_reduction_global.py 中以(shape_a, shape_b, bin_id)为哈希键、接触匹配与求解器的访存局部性因此整体更快而小规模高密度接触场景中排序开销占比相对更高会略有变慢。这是典型的以排序开销换取确定性 访存亲和的工程权衡。六、变更的工程形态Towncrier changelog 片段该文件是 Towncrier 格式的 changelog 片段见 changelog/README.md以4141作为 issue 编号标识符、.changed表示变更类别、.1用于同 issue 下的多片段区分。这类片段在发布分支上由 Towncrier 合并进CHANGELOG.md因此它本身是简短的一句话但其技术语义由上述源码链完整支撑。同目录下的 4141.changed.md 记录的是同一 issue 中SolverVBD刚柔接触与可变形弹性的 CUDA 加速两者共同构成该 issue 的完整变更集。七、小结与验证路径Newton 的按形状排序软接触候选对是一次典型的确定性工程改造用ContactData的sort_sub_key与形状索引构造 64 位排序键由ContactSorter以backup → 基数排序 → gather两步 kernel 的方式在 CUDA graph 可捕获、无主机同步的前提下完成全量确定性排序并统一作用于简化与完整两条接触管线及软接触流。其正确性由位布局、溢出掩码、形状位宽等单元测试newton/tests/test_contact_reduction_global.py保障。如需深入验证建议按以下路径阅读源码排序键位布局与常量contact_data.py排序执行器与哨兵机制contact_sort.py软接触流产出soft_contacts_sdf.py、kernels.py排序键写入与排序调用narrow_phase.py、collide.py确定性校验测试test_contact_reduction_global.py。在升级使用该变更的版本时请记住两条注意事项对结果做逐位比对时应放宽到浮点容差依赖容量溢出后保留哪些接触的仿真其行为可能与旧版本略有不同。【免费下载链接】newtonAn open-source, GPU-accelerated physics simulation engine built upon NVIDIA Warp, specifically targeting roboticists and simulation researchers.项目地址: https://gitcode.com/GitHub_Trending/newton9/newton创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
