尧图网站建设 
Warp 新增 warp.geometry 模块基于设备端并行与 CUDA Graph 捕获的 Delaunay 边翻转delaunay_edge_flip全解析【免费下载链接】warpA Python framework for GPU-accelerated simulation, robotics, and machine learning.项目地址: https://gitcode.com/GitHub_Trending/warp/warp本篇技术指南围绕 Warp 仓库新增的warp.geometry几何处理模块展开核心讲解其中两个入口用于 2D 三角网格并行、原地 Delaunay 边翻转的warp.geometry.delaunay_edge_flip()以及其支撑性的三角形-三角形邻接构建函数warp.geometry.tri_tri_adjacency()。读完本文你将掌握这两个 API 的完整参数语义、前置条件、与 CUDA Graph 捕获的集成方式以及它们背后的并行算法半边区段、原子声明、设备端收敛循环是如何在 Warp 源码与测试中被实现和验证的。一、模块概览warp.geometry 提供了什么warp.geometry是 Warp 中面向几何处理的新模块模块 docstring 将其定位为“处理 2D/3D 几何及其关联拓扑数据结构如网格的工具函数”并且必须显式导入才能使用import warp.geometry本次新增的核心能力是在设备上CPU 或 CUDA对 2D 三角网格执行并行、原地的 Delaunay 边翻转将非 Delaunay 的内部边逐轮并行翻转直到所有内部边满足 Delaunay 条件或达到最大轮数同时配套提供三角形邻接关系构建工具。两者全程运行在设备端且均支持 CUDA Graph 捕获。公开 API 与内部实现的分层从 warp/geometry.py 可以看到公开模块只是一个薄封装真正的实现位于 warp/_src/geometry.pyfrom warp._src.geometry import delaunay_edge_flip as delaunay_edge_flip from warp._src.geometry import find_triangle_neighbor_edge_index as find_triangle_neighbor_edge_index from warp._src.geometry import tri_tri_adjacency as tri_tri_adjacency而 warp/_src/geometry.py 中还有两处被注释掉的导出# Dont expose these quite yet in case we want to change the naming conventions. # from warp._src.geometry import in_circle as in_circle # from warp._src.geometry import signed_area as signed_area也就是说几何谓词in_circle外接圆判定与signed_area有向面积目前仍是内部可复用但尚未公开的wp.func官方文档 docs/api_reference/warp_geometry.rst 中列出的公开成员共有三个delaunay_edge_flip、find_triangle_neighbor_edge_index、tri_tri_adjacency。二、核心 APIdelaunay_edge_flip 的参数与返回语义delaunay_edge_flip()在 warp/_src/geometry.py 中定义完整签名如下def delaunay_edge_flip( positions: wp.array[wp.vec2], indices: wp.array2d[wp.int32], ref_positions: wp.array[wp.vec2] | None None, max_passes: int 1000, area_epsilon: float 0.0, ref_area_epsilon: float 1.0e-10, ) - wp.array[wp.int32]:参数详解参数类型默认值含义positionswp.array[wp.vec2]一维必填vertex_count个顶点的 2D 坐标不会被修改indiceswp.array2d[wp.int32]形状(num_tris, 3)必填三角形顶点索引原地更新为翻转后的连接关系ref_positionswp.array[wp.vec2]None可选的参考配置顶点坐标。提供后会在参考配置下产生退化三角形的翻转被拒绝适用于“工作网格是参考网格的形变且必须保持非退化”的场景max_passesint1000并行翻转的最大轮数停止条件之一必须 1area_epsilonfloat0.0翻转产生的每个三角形所需的最小有向面积用于防止产生反向inverted或薄片sliver三角形必须有限且非负ref_area_epsilonfloat1.0e-10应用于ref_positions的退化阈值必须有限且非负返回值返回一个位于indices.device上的、形状为(1,)的int32设备数组其中保存被翻转的边总数。注意它不是Python 整数即使网格为空也总是返回设备端累加器见 warp/_src/geometry.py 的空网格分支。在 CUDA Graph 捕获场景下必须在重放replay之后再读取该值。输入前置条件与校验网格必须是流形每条边被 1 或 2 个三角形共享且三角形具有一致的逆时针绕序有向面积为正positions、ref_positions必须与indices在同一设备上否则抛出ValueErrorindices.ndim ! 2或indices.shape[1] ! 3时抛出ValueErrormax_passes 1、area_epsilon/ref_area_epsilon非有限或为负时同样抛出ValueError见 warp/_src/geometry.py。这些校验有对应的测试覆盖warp/tests/geometry/test_delaunay.py 验证了max_passes0/-1、area_epsilon/ref_area_epsilon取-1.0、nan、inf时均被拒绝且被拒绝的调用不会改动输入连接关系。最小可用示例以测试中“薄四边形翻转单条边”的用例warp/tests/geometry/test_delaunay.py为例import numpy as np import warp as wp import warp.geometry points np.array([[-3.0, 0.0], [3.0, 0.0], [0.0, 1.0], [0.0, -1.0]], dtypenp.float32) tris np.array([[0, 1, 2], [1, 0, 3]], dtypenp.int32) # 两个三角形均为逆时针 positions wp.array(points, dtypewp.vec2) indices wp.array(tris, dtypewp.int32) num_flips int(warp.geometry.delaunay_edge_flip(positions, indices).numpy()[0]) print(num_flips) # 1翻转了一条内部边 print(indices.numpy()) # 连接关系已原地更新共享边变为垂直对角线 (2, 3)三、配套工具tri_tri_adjacency 与 find_triangle_neighbor_edge_indextri_tri_adjacency构建三角形邻接表tri_tri_adjacency()warp/_src/geometry.py为三角网格构建三角形-三角形邻接关系签名如下def tri_tri_adjacency( indices: wp.array2d[wp.int32], vertex_count: int | None None, return_neighbor_edge_indices: bool True, ):参数默认值说明indices必填(num_tris, 3)的int32三角形顶点索引数组vertex_countNone网格顶点数。为None时内部通过一次设备端归约推断为“最大顶点索引 1”在 CUDA Graph 捕获上下文中必须显式传入否则抛出RuntimeErrorreturn_neighbor_edge_indicesTrue为True时额外计算并返回每个邻接三角形中共享边对应的局部边索引为False时只构建邻接数组更快且占用内存更少返回值约定return_neighbor_edge_indicesTrue返回(triangle_neighbors, neighbor_edge_indices)两个(num_tris, 3)的int32数组return_neighbor_edge_indicesFalse仅返回单个triangle_neighbors数组。数组语义非常明确warp/_src/geometry.pytriangle_neighbors[t, j]是与三角形t共享“局部顶点j对边”的相邻三角形编号该对边即连接局部顶点(j 1) % 3与(j 2) % 3的边边界边对应位置为-1neighbor_edge_indices[t, j]是该共享边在相邻三角形中的局部边索引。测试用例 warp/tests/geometry/test_delaunay.py 给出了直观验证两个共享边(0, 2)的三角形(0,1,2)与(0,2,3)得到triangle_neighbors[0,1] 1边(0,2)在三角形 0 中位于局部顶点 1 的对侧、neighbor_edge_indices[0,1] 2其余边界边均为-1。find_triangle_neighbor_edge_index按需恢复单条邻接边索引find_triangle_neighbor_edge_index(triangle_neighbors, triangle, neighbor)warp/_src/geometry.py是一个wp.func用于在 kernel 内查找neighbor在triangle的局部边索引返回满足triangle_neighbors[triangle, j] neighbor的j若两者不相邻则返回-1。当tri_tri_adjacency以return_neighbor_edge_indicesFalse调用后可用它按需恢复单个值而不必长期持有neighbor_edge_indices数组。一个完整的邻接构建示例import warp as wp import warp.geometry indices wp.array(np.array([[0, 1, 2], [0, 2, 3]], dtypenp.int32), dtypewp.int32) # 推荐显式传入 vertex_count网格捕获场景下必须传入 triangle_neighbors, neighbor_edge_indices warp.geometry.tri_tri_adjacency( indices, vertex_count4 ) # 只构建邻接、跳过边索引更快、内存更省 triangle_neighbors_only warp.geometry.tri_tri_adjacency( indices, vertex_count4, return_neighbor_edge_indicesFalse )四、算法原理设备端全程无主机同步的并行实现4.1 半边区段基于 counting-sort 的邻接构建tri_tri_adjacency的底层实现warp/_src/geometry.py没有采用全局键排序而是把每条半边按其两个端点中较小者分桶counting sort 思路_count_vertex_edges每个线程一个三角形将三条半边分别计入其较低端点对应的桶计数atomic_addwarp.utils.array_scan对计数做前缀和得到桶偏移_scatter_vertex_edges将每条半边散射进对应桶记录较高端点与打包后的半边编号tri * 3 local_edge_match_vertex_buckets每个线程独占一个顶点的桶区间在桶内两两配对“相同较高端点”的半边写入triangle_neighbors每个顶点的平均度约 6二次内层扫描只遍历少数条目。整个过程通过warp.utils.array_scan与设备端原子操作完成不需要任何主机同步——这为后续的 CUDA Graph 捕获铺平了道路。一个值得注意的约束也因此产生当vertex_countNone时需要通过一次设备端归约_reduce_max_vertex_index推断顶点数再通过.numpy()回读主机端这一主机同步在捕获上下文里是禁止的于是 warp/_src/geometry.py 在device.is_capturing时直接抛出RuntimeError对应的捕获期测试见 warp/tests/geometry/test_delaunay.py。4.2 翻转判定链接条件 外接圆判定单条边是否翻转由_DelaunayFlipper._edge_should_flipwarp/_src/geometry.py决定顺序如下链接条件link condition翻转把边ab换成对角cd生成三角形(c, a, d)与(c, d, b)。只有当四边形a, d, b, c凸、即两个新三角形均有向面积为正时才继续_EdgeFlipper._link_condition_okwarp/_src/geometry.py否则直接返回FalseDelaunay 判定计算in_circle行列式_in_circle_det(pc, pa, pb, pd)warp/_src/geometry.py。对于逆时针三角形(c, a, b)当对侧顶点d落在其外接圆内部时结果为正此时需要翻转 0.0外部或四点共圆则保持原样。这是标准浮点 in-circle 行列式对良态配置准确但如 warp/_src/geometry.py 的 docstring 所述并非精确几何谓词参考配置保护若提供了ref_positions还会检查两个新三角形在参考配置下的有向面积绝对值是否小于ref_area_epsilon若是则拒绝翻转防止参考网格退化。谓词本身的正确性有独立测试验证warp/tests/geometry/test_delaunay.py 在单位直角三角形上确认signed_area对逆时针返回0.5、顺时针返回-0.5in_circle对内点(0.4, 0.4)返回 1、对外点(2.0, 2.0)返回 0。4.3 并行独立集原子声明 位反转优先级为了让每轮能并行翻转尽可能多的互不冲突的边实现采用了声明claim竞争机制_stake_flip_claimswarp/_src/geometry.py每个线程一个三角形检查自己的三条边对满足翻转条件的边计算优先级prio并通过wp.atomic_max竞争其可能读写的四行{t, n, n_bc, n_ad}的“所有权”优先级由_edge_prioritywarp/_src/geometry.py给出。实现要点是朴素地使用t * 3 j虽然唯一但随三角形编号单调——对网格生成器grid、marching cubes、细分等产出的、三角形编号带有空间局部性的网格这会让冲突边链每轮只收敛一行退化到O(n)轮而把非零键的32 位按位反转SWAR 位反转_reverse_bits32warp/_src/geometry.py后既保持双射唯一性、正确性不受影响又打散了与三角形编号的相关性且0被保留为声明数组的“未声明”哨兵_apply_won_flipswarp/_src/geometry.py只有持有对应行声明的边才执行拓扑变更——交换对角、更新triangle_neighbors中四条相关邻接槽位、并重定向两个外侧邻居最后atomic_add累计翻转数。先查声明再读可变拓扑保证并发翻转不会互相污染数据。4.4 设备端收敛循环wp.capture_while翻转的主循环warp/_src/geometry.py每轮执行“清声明 → 竞争声明 → 应用获胜翻转 → 记录轮次”三步而是否进入下一轮由_record_passwarp/_src/geometry.py单线程地把累计翻转数与pass_count max_passes写入设备数组再交给wp.capture_while(condition, _flip_pass)判断wp.capture_while(condition, _flip_pass)wp.capture_whilewarp/_src/context.py在 CUDA Graph 捕获下会记录条件图节点conditional graph nodes否则将条件回读主机端决定何时停止。因此这个收敛循环无需主机同步天然可被 CUDA Graph 捕获。4.5 收敛行为与对抗性测试测试 warp/tests/geometry/test_delaunay.pytest_flip_grid_sheared_converges_in_few_passes专门构造了教科书式的对抗用例编号逐行递增、且每条内部对角线都非 Delaunay 的剪切网格。若优先级退化为单调的t * 3 j声明竞争会沿列级联每轮只解决一行需要num_rows - 1轮而当前实现用max_passes5即可在 40×40 的剪切网格上收敛到 Delaunay验证了期望的O(log n)级轮数。该测试还提示若未来此测试失败应优先检查_edge_priority()是否回归为单调于三角形编号的实现。五、与 CUDA Graph 捕获的深度集成5.1 为什么可以捕获整个管线邻接构建、声明竞争、翻转应用、轮次记录都由设备端 kernel 和wp.capture_while驱动没有中途的主机同步因此可以被wp.ScopedCapture完整记录。测试 warp/tests/geometry/test_delaunay.py 展示了完整的捕获-重放流程。5.2 捕获使用的五个注意点vertex_count必须显式传入tri_tri_adjacency捕获期内不允许None触发的主机回读会抛RuntimeErrorCUDA 条件图节点需要 Toolkit 与驱动 12.4可用wp.is_conditional_graph_supported()检测不支持时测试会跳过warp/tests/geometry/test_delaunay.py捕获前预热分配与模块加载测试在捕获前先跑一次翻转以预热设备分配radix-sort scratch 等并调用wp.load_module(warp.geometry, devicedevice)预加载 kernel避免捕获区内触发首次分配或编译warp/tests/geometry/test_delaunay.py捕获只记录不执行捕获期间网格连接关系保持不变重放后才生效返回值在重放后才有效delaunay_edge_flip返回的设备累加器在捕获模式下记录的是操作而非结果需在wp.capture_launch(capture.graph)之后读取。5.3 捕获示例骨架import warp as wp import warp.geometry # 预热完成模块加载与设备分配 warp.geometry.delaunay_edge_flip( wp.array(points, dtypewp.vec2, devicedevice), wp.array(tris, dtypewp.int32, devicedevice), ) wp.load_module(warp.geometry, devicedevice) with wp.ScopedDevice(device): with wp.ScopedCapture(force_module_loadFalse) as capture: total warp.geometry.delaunay_edge_flip(positions, indices) # tri_tri_adjacency 在捕获内使用时必须显式传 vertex_count wp.capture_launch(capture.graph) print(int(total.numpy()[0])) # 重放后读取翻转总数测试还验证了图的可重放稳定性捕获的图每次重放都会基于当前连接关系重建邻接因此对已是 Delaunay 的网格重放是稳定无操作的第二次重放翻转数为 0。六、仓库内的真实应用FEM 弹性形状优化warp.geometry并非孤立模块它已直接用于仓库的 FEM 示例 warp/examples/fem/example_elastic_shape_optimization.py。该示例在形状优化迭代中实现remesh()每次迭代调用warp.geometry.delaunay_edge_flip改善三角形质量——num_flips int( warp.geometry.delaunay_edge_flip( self._vertex_positions, self._tri_vertex_indices, ref_positionsself._initial_positions, # 参考配置保护 ).numpy()[0] )这里特意把self._initial_positions作为ref_positions传入防止翻转使初始参考配置出现退化三角形翻转数不为 0 时再重建 FEM 空间与场并刻意避免重建Trimesh2D对象——因为边翻转只影响内部边边界结构与投影算子保持有效而重跑拓扑构建会引入非确定性边序、扰动边界投影算子。这个真实用例同时印证了ref_positions参数的设计动机与“原地修改连接关系”的语义。七、测试覆盖与验证方法完整的测试套件位于 warp/tests/geometry/test_delaunay.py其特点是使用独立的 NumPy 参考实现_signed_area、_in_circle_det、_edge_map见该文件 L18-L45验证结果而非对照 Warp 自身实现测试项包括谓词signed_area、in_circle在单位直角三角形上的数值正确性邻接单条共享边的最小网格、grid 网格上的 round-triptriangle_neighbors[n, jn] t互指、vertex_count推断与显式传入结果一致、捕获期内必须显式传vertex_count翻转单条边翻转翻转数恰为 1、共享边变为垂直对角线、带抖动 grid 收敛到 Delaunay 且总面积守恒、顶点集合不变、二次翻转为 0固定点性质、40×40 大网格压力测试并发翻转不破坏邻接、无竞态、剪切网格少轮收敛、已是 Delaunay 的网格保持不变、参考配置退化时拒绝翻转、空网格返回 0、非法参数拒绝且不改变连接、凸多边形扇形网格与星形多边形非凸域边界边保持不变、内部边翻转到固定点、以及完整的 CUDA Graph 捕获-重放一致性测试。其中“固定点”与“面积/顶点守恒”的断言如 warp/tests/geometry/test_delaunay.py是对并行边翻转正确性的强验证翻转只改变对角线不改变顶点集合与总覆盖面积。八、使用注意事项小结务必import warp.geometry该模块不会被import warp自动引入warp/geometry.py网格前提流形、一致的逆时针绕序边界边单三角形共享永远不会被翻转原地语义indices会被修改positions保持不变如需保留原始连接关系请自行拷贝返回值是设备数组急切模式下用.numpy()[0]读取捕获模式下重放后再读ref_positions的适用场景当工作网格是某个参考网格的形变如 FEM 优化迭代时用它防止翻转引入参考配置下的退化三角形捕获约束tri_tri_adjacency在捕获内必须显式传vertex_countCUDA 条件图节点要求 Toolkit 与驱动 12.4捕获前完成模块加载与设备分配预热。总而言之warp.geometry的这次新增changelog 条目 changelog/1797.added.md把传统的串行 Delaunay 边翻转流程整体搬上了设备端从半边区段构建邻接、原子声明并行独立集、位反转优先级加速收敛到wp.capture_while驱动的零主机同步收敛循环为需要在模拟/优化迭代中反复改善网格质量的场景如 FEM 重网格化提供了一条可直接嵌入 CUDA Graph 的高效路径。【免费下载链接】warpA Python framework for GPU-accelerated simulation, robotics, and machine learning.项目地址: https://gitcode.com/GitHub_Trending/warp/warp创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Warp 新增 warp.geometry 模块：基于设备端并行与 CUDA Graph 捕获的 Delaunay 边翻转（delaunay_edge_flip）全解析
Warp 新增 warp.geometry 模块基于设备端并行与 CUDA Graph 捕获的 Delaunay 边翻转delaunay_edge_flip全解析【免费下载链接】warpA Python framework for GPU-accelerated simulation, robotics, and machine learning.项目地址: https://gitcode.com/GitHub_Trending/warp/warp本篇技术指南围绕 Warp 仓库新增的warp.geometry几何处理模块展开核心讲解其中两个入口用于 2D 三角网格并行、原地 Delaunay 边翻转的warp.geometry.delaunay_edge_flip()以及其支撑性的三角形-三角形邻接构建函数warp.geometry.tri_tri_adjacency()。读完本文你将掌握这两个 API 的完整参数语义、前置条件、与 CUDA Graph 捕获的集成方式以及它们背后的并行算法半边区段、原子声明、设备端收敛循环是如何在 Warp 源码与测试中被实现和验证的。一、模块概览warp.geometry 提供了什么warp.geometry是 Warp 中面向几何处理的新模块模块 docstring 将其定位为“处理 2D/3D 几何及其关联拓扑数据结构如网格的工具函数”并且必须显式导入才能使用import warp.geometry本次新增的核心能力是在设备上CPU 或 CUDA对 2D 三角网格执行并行、原地的 Delaunay 边翻转将非 Delaunay 的内部边逐轮并行翻转直到所有内部边满足 Delaunay 条件或达到最大轮数同时配套提供三角形邻接关系构建工具。两者全程运行在设备端且均支持 CUDA Graph 捕获。公开 API 与内部实现的分层从 warp/geometry.py 可以看到公开模块只是一个薄封装真正的实现位于 warp/_src/geometry.pyfrom warp._src.geometry import delaunay_edge_flip as delaunay_edge_flip from warp._src.geometry import find_triangle_neighbor_edge_index as find_triangle_neighbor_edge_index from warp._src.geometry import tri_tri_adjacency as tri_tri_adjacency而 warp/_src/geometry.py 中还有两处被注释掉的导出# Dont expose these quite yet in case we want to change the naming conventions. # from warp._src.geometry import in_circle as in_circle # from warp._src.geometry import signed_area as signed_area也就是说几何谓词in_circle外接圆判定与signed_area有向面积目前仍是内部可复用但尚未公开的wp.func官方文档 docs/api_reference/warp_geometry.rst 中列出的公开成员共有三个delaunay_edge_flip、find_triangle_neighbor_edge_index、tri_tri_adjacency。二、核心 APIdelaunay_edge_flip 的参数与返回语义delaunay_edge_flip()在 warp/_src/geometry.py 中定义完整签名如下def delaunay_edge_flip( positions: wp.array[wp.vec2], indices: wp.array2d[wp.int32], ref_positions: wp.array[wp.vec2] | None None, max_passes: int 1000, area_epsilon: float 0.0, ref_area_epsilon: float 1.0e-10, ) - wp.array[wp.int32]:参数详解参数类型默认值含义positionswp.array[wp.vec2]一维必填vertex_count个顶点的 2D 坐标不会被修改indiceswp.array2d[wp.int32]形状(num_tris, 3)必填三角形顶点索引原地更新为翻转后的连接关系ref_positionswp.array[wp.vec2]None可选的参考配置顶点坐标。提供后会在参考配置下产生退化三角形的翻转被拒绝适用于“工作网格是参考网格的形变且必须保持非退化”的场景max_passesint1000并行翻转的最大轮数停止条件之一必须 1area_epsilonfloat0.0翻转产生的每个三角形所需的最小有向面积用于防止产生反向inverted或薄片sliver三角形必须有限且非负ref_area_epsilonfloat1.0e-10应用于ref_positions的退化阈值必须有限且非负返回值返回一个位于indices.device上的、形状为(1,)的int32设备数组其中保存被翻转的边总数。注意它不是Python 整数即使网格为空也总是返回设备端累加器见 warp/_src/geometry.py 的空网格分支。在 CUDA Graph 捕获场景下必须在重放replay之后再读取该值。输入前置条件与校验网格必须是流形每条边被 1 或 2 个三角形共享且三角形具有一致的逆时针绕序有向面积为正positions、ref_positions必须与indices在同一设备上否则抛出ValueErrorindices.ndim ! 2或indices.shape[1] ! 3时抛出ValueErrormax_passes 1、area_epsilon/ref_area_epsilon非有限或为负时同样抛出ValueError见 warp/_src/geometry.py。这些校验有对应的测试覆盖warp/tests/geometry/test_delaunay.py 验证了max_passes0/-1、area_epsilon/ref_area_epsilon取-1.0、nan、inf时均被拒绝且被拒绝的调用不会改动输入连接关系。最小可用示例以测试中“薄四边形翻转单条边”的用例warp/tests/geometry/test_delaunay.py为例import numpy as np import warp as wp import warp.geometry points np.array([[-3.0, 0.0], [3.0, 0.0], [0.0, 1.0], [0.0, -1.0]], dtypenp.float32) tris np.array([[0, 1, 2], [1, 0, 3]], dtypenp.int32) # 两个三角形均为逆时针 positions wp.array(points, dtypewp.vec2) indices wp.array(tris, dtypewp.int32) num_flips int(warp.geometry.delaunay_edge_flip(positions, indices).numpy()[0]) print(num_flips) # 1翻转了一条内部边 print(indices.numpy()) # 连接关系已原地更新共享边变为垂直对角线 (2, 3)三、配套工具tri_tri_adjacency 与 find_triangle_neighbor_edge_indextri_tri_adjacency构建三角形邻接表tri_tri_adjacency()warp/_src/geometry.py为三角网格构建三角形-三角形邻接关系签名如下def tri_tri_adjacency( indices: wp.array2d[wp.int32], vertex_count: int | None None, return_neighbor_edge_indices: bool True, ):参数默认值说明indices必填(num_tris, 3)的int32三角形顶点索引数组vertex_countNone网格顶点数。为None时内部通过一次设备端归约推断为“最大顶点索引 1”在 CUDA Graph 捕获上下文中必须显式传入否则抛出RuntimeErrorreturn_neighbor_edge_indicesTrue为True时额外计算并返回每个邻接三角形中共享边对应的局部边索引为False时只构建邻接数组更快且占用内存更少返回值约定return_neighbor_edge_indicesTrue返回(triangle_neighbors, neighbor_edge_indices)两个(num_tris, 3)的int32数组return_neighbor_edge_indicesFalse仅返回单个triangle_neighbors数组。数组语义非常明确warp/_src/geometry.pytriangle_neighbors[t, j]是与三角形t共享“局部顶点j对边”的相邻三角形编号该对边即连接局部顶点(j 1) % 3与(j 2) % 3的边边界边对应位置为-1neighbor_edge_indices[t, j]是该共享边在相邻三角形中的局部边索引。测试用例 warp/tests/geometry/test_delaunay.py 给出了直观验证两个共享边(0, 2)的三角形(0,1,2)与(0,2,3)得到triangle_neighbors[0,1] 1边(0,2)在三角形 0 中位于局部顶点 1 的对侧、neighbor_edge_indices[0,1] 2其余边界边均为-1。find_triangle_neighbor_edge_index按需恢复单条邻接边索引find_triangle_neighbor_edge_index(triangle_neighbors, triangle, neighbor)warp/_src/geometry.py是一个wp.func用于在 kernel 内查找neighbor在triangle的局部边索引返回满足triangle_neighbors[triangle, j] neighbor的j若两者不相邻则返回-1。当tri_tri_adjacency以return_neighbor_edge_indicesFalse调用后可用它按需恢复单个值而不必长期持有neighbor_edge_indices数组。一个完整的邻接构建示例import warp as wp import warp.geometry indices wp.array(np.array([[0, 1, 2], [0, 2, 3]], dtypenp.int32), dtypewp.int32) # 推荐显式传入 vertex_count网格捕获场景下必须传入 triangle_neighbors, neighbor_edge_indices warp.geometry.tri_tri_adjacency( indices, vertex_count4 ) # 只构建邻接、跳过边索引更快、内存更省 triangle_neighbors_only warp.geometry.tri_tri_adjacency( indices, vertex_count4, return_neighbor_edge_indicesFalse )四、算法原理设备端全程无主机同步的并行实现4.1 半边区段基于 counting-sort 的邻接构建tri_tri_adjacency的底层实现warp/_src/geometry.py没有采用全局键排序而是把每条半边按其两个端点中较小者分桶counting sort 思路_count_vertex_edges每个线程一个三角形将三条半边分别计入其较低端点对应的桶计数atomic_addwarp.utils.array_scan对计数做前缀和得到桶偏移_scatter_vertex_edges将每条半边散射进对应桶记录较高端点与打包后的半边编号tri * 3 local_edge_match_vertex_buckets每个线程独占一个顶点的桶区间在桶内两两配对“相同较高端点”的半边写入triangle_neighbors每个顶点的平均度约 6二次内层扫描只遍历少数条目。整个过程通过warp.utils.array_scan与设备端原子操作完成不需要任何主机同步——这为后续的 CUDA Graph 捕获铺平了道路。一个值得注意的约束也因此产生当vertex_countNone时需要通过一次设备端归约_reduce_max_vertex_index推断顶点数再通过.numpy()回读主机端这一主机同步在捕获上下文里是禁止的于是 warp/_src/geometry.py 在device.is_capturing时直接抛出RuntimeError对应的捕获期测试见 warp/tests/geometry/test_delaunay.py。4.2 翻转判定链接条件 外接圆判定单条边是否翻转由_DelaunayFlipper._edge_should_flipwarp/_src/geometry.py决定顺序如下链接条件link condition翻转把边ab换成对角cd生成三角形(c, a, d)与(c, d, b)。只有当四边形a, d, b, c凸、即两个新三角形均有向面积为正时才继续_EdgeFlipper._link_condition_okwarp/_src/geometry.py否则直接返回FalseDelaunay 判定计算in_circle行列式_in_circle_det(pc, pa, pb, pd)warp/_src/geometry.py。对于逆时针三角形(c, a, b)当对侧顶点d落在其外接圆内部时结果为正此时需要翻转 0.0外部或四点共圆则保持原样。这是标准浮点 in-circle 行列式对良态配置准确但如 warp/_src/geometry.py 的 docstring 所述并非精确几何谓词参考配置保护若提供了ref_positions还会检查两个新三角形在参考配置下的有向面积绝对值是否小于ref_area_epsilon若是则拒绝翻转防止参考网格退化。谓词本身的正确性有独立测试验证warp/tests/geometry/test_delaunay.py 在单位直角三角形上确认signed_area对逆时针返回0.5、顺时针返回-0.5in_circle对内点(0.4, 0.4)返回 1、对外点(2.0, 2.0)返回 0。4.3 并行独立集原子声明 位反转优先级为了让每轮能并行翻转尽可能多的互不冲突的边实现采用了声明claim竞争机制_stake_flip_claimswarp/_src/geometry.py每个线程一个三角形检查自己的三条边对满足翻转条件的边计算优先级prio并通过wp.atomic_max竞争其可能读写的四行{t, n, n_bc, n_ad}的“所有权”优先级由_edge_prioritywarp/_src/geometry.py给出。实现要点是朴素地使用t * 3 j虽然唯一但随三角形编号单调——对网格生成器grid、marching cubes、细分等产出的、三角形编号带有空间局部性的网格这会让冲突边链每轮只收敛一行退化到O(n)轮而把非零键的32 位按位反转SWAR 位反转_reverse_bits32warp/_src/geometry.py后既保持双射唯一性、正确性不受影响又打散了与三角形编号的相关性且0被保留为声明数组的“未声明”哨兵_apply_won_flipswarp/_src/geometry.py只有持有对应行声明的边才执行拓扑变更——交换对角、更新triangle_neighbors中四条相关邻接槽位、并重定向两个外侧邻居最后atomic_add累计翻转数。先查声明再读可变拓扑保证并发翻转不会互相污染数据。4.4 设备端收敛循环wp.capture_while翻转的主循环warp/_src/geometry.py每轮执行“清声明 → 竞争声明 → 应用获胜翻转 → 记录轮次”三步而是否进入下一轮由_record_passwarp/_src/geometry.py单线程地把累计翻转数与pass_count max_passes写入设备数组再交给wp.capture_while(condition, _flip_pass)判断wp.capture_while(condition, _flip_pass)wp.capture_whilewarp/_src/context.py在 CUDA Graph 捕获下会记录条件图节点conditional graph nodes否则将条件回读主机端决定何时停止。因此这个收敛循环无需主机同步天然可被 CUDA Graph 捕获。4.5 收敛行为与对抗性测试测试 warp/tests/geometry/test_delaunay.pytest_flip_grid_sheared_converges_in_few_passes专门构造了教科书式的对抗用例编号逐行递增、且每条内部对角线都非 Delaunay 的剪切网格。若优先级退化为单调的t * 3 j声明竞争会沿列级联每轮只解决一行需要num_rows - 1轮而当前实现用max_passes5即可在 40×40 的剪切网格上收敛到 Delaunay验证了期望的O(log n)级轮数。该测试还提示若未来此测试失败应优先检查_edge_priority()是否回归为单调于三角形编号的实现。五、与 CUDA Graph 捕获的深度集成5.1 为什么可以捕获整个管线邻接构建、声明竞争、翻转应用、轮次记录都由设备端 kernel 和wp.capture_while驱动没有中途的主机同步因此可以被wp.ScopedCapture完整记录。测试 warp/tests/geometry/test_delaunay.py 展示了完整的捕获-重放流程。5.2 捕获使用的五个注意点vertex_count必须显式传入tri_tri_adjacency捕获期内不允许None触发的主机回读会抛RuntimeErrorCUDA 条件图节点需要 Toolkit 与驱动 12.4可用wp.is_conditional_graph_supported()检测不支持时测试会跳过warp/tests/geometry/test_delaunay.py捕获前预热分配与模块加载测试在捕获前先跑一次翻转以预热设备分配radix-sort scratch 等并调用wp.load_module(warp.geometry, devicedevice)预加载 kernel避免捕获区内触发首次分配或编译warp/tests/geometry/test_delaunay.py捕获只记录不执行捕获期间网格连接关系保持不变重放后才生效返回值在重放后才有效delaunay_edge_flip返回的设备累加器在捕获模式下记录的是操作而非结果需在wp.capture_launch(capture.graph)之后读取。5.3 捕获示例骨架import warp as wp import warp.geometry # 预热完成模块加载与设备分配 warp.geometry.delaunay_edge_flip( wp.array(points, dtypewp.vec2, devicedevice), wp.array(tris, dtypewp.int32, devicedevice), ) wp.load_module(warp.geometry, devicedevice) with wp.ScopedDevice(device): with wp.ScopedCapture(force_module_loadFalse) as capture: total warp.geometry.delaunay_edge_flip(positions, indices) # tri_tri_adjacency 在捕获内使用时必须显式传 vertex_count wp.capture_launch(capture.graph) print(int(total.numpy()[0])) # 重放后读取翻转总数测试还验证了图的可重放稳定性捕获的图每次重放都会基于当前连接关系重建邻接因此对已是 Delaunay 的网格重放是稳定无操作的第二次重放翻转数为 0。六、仓库内的真实应用FEM 弹性形状优化warp.geometry并非孤立模块它已直接用于仓库的 FEM 示例 warp/examples/fem/example_elastic_shape_optimization.py。该示例在形状优化迭代中实现remesh()每次迭代调用warp.geometry.delaunay_edge_flip改善三角形质量——num_flips int( warp.geometry.delaunay_edge_flip( self._vertex_positions, self._tri_vertex_indices, ref_positionsself._initial_positions, # 参考配置保护 ).numpy()[0] )这里特意把self._initial_positions作为ref_positions传入防止翻转使初始参考配置出现退化三角形翻转数不为 0 时再重建 FEM 空间与场并刻意避免重建Trimesh2D对象——因为边翻转只影响内部边边界结构与投影算子保持有效而重跑拓扑构建会引入非确定性边序、扰动边界投影算子。这个真实用例同时印证了ref_positions参数的设计动机与“原地修改连接关系”的语义。七、测试覆盖与验证方法完整的测试套件位于 warp/tests/geometry/test_delaunay.py其特点是使用独立的 NumPy 参考实现_signed_area、_in_circle_det、_edge_map见该文件 L18-L45验证结果而非对照 Warp 自身实现测试项包括谓词signed_area、in_circle在单位直角三角形上的数值正确性邻接单条共享边的最小网格、grid 网格上的 round-triptriangle_neighbors[n, jn] t互指、vertex_count推断与显式传入结果一致、捕获期内必须显式传vertex_count翻转单条边翻转翻转数恰为 1、共享边变为垂直对角线、带抖动 grid 收敛到 Delaunay 且总面积守恒、顶点集合不变、二次翻转为 0固定点性质、40×40 大网格压力测试并发翻转不破坏邻接、无竞态、剪切网格少轮收敛、已是 Delaunay 的网格保持不变、参考配置退化时拒绝翻转、空网格返回 0、非法参数拒绝且不改变连接、凸多边形扇形网格与星形多边形非凸域边界边保持不变、内部边翻转到固定点、以及完整的 CUDA Graph 捕获-重放一致性测试。其中“固定点”与“面积/顶点守恒”的断言如 warp/tests/geometry/test_delaunay.py是对并行边翻转正确性的强验证翻转只改变对角线不改变顶点集合与总覆盖面积。八、使用注意事项小结务必import warp.geometry该模块不会被import warp自动引入warp/geometry.py网格前提流形、一致的逆时针绕序边界边单三角形共享永远不会被翻转原地语义indices会被修改positions保持不变如需保留原始连接关系请自行拷贝返回值是设备数组急切模式下用.numpy()[0]读取捕获模式下重放后再读ref_positions的适用场景当工作网格是某个参考网格的形变如 FEM 优化迭代时用它防止翻转引入参考配置下的退化三角形捕获约束tri_tri_adjacency在捕获内必须显式传vertex_countCUDA 条件图节点要求 Toolkit 与驱动 12.4捕获前完成模块加载与设备分配预热。总而言之warp.geometry的这次新增changelog 条目 changelog/1797.added.md把传统的串行 Delaunay 边翻转流程整体搬上了设备端从半边区段构建邻接、原子声明并行独立集、位反转优先级加速收敛到wp.capture_while驱动的零主机同步收敛循环为需要在模拟/优化迭代中反复改善网格质量的场景如 FEM 重网格化提供了一条可直接嵌入 CUDA Graph 的高效路径。【免费下载链接】warpA Python framework for GPU-accelerated simulation, robotics, and machine learning.项目地址: https://gitcode.com/GitHub_Trending/warp/warp创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考