如何在R中通过3D射线追踪构建动物洞穴空间网络？

背景 #

我有显微CT扫描仪生成的土壤动物洞穴3D三角网格（Wavefront格式），网格包含数千个三角形，每个三角形由三个顶点的XYZ坐标定义，已计算出每个三角形的中心。我的目标是表征洞穴内的“使用区域”及其空间关系，目前考虑两种方案，寻求实现思路：

方案一：射线追踪构建空间网络 #

需求 #

将洞穴内空间关系表示为空间网络：顶点代表三角形，当两个三角形的中心连线仅在洞穴空腔内传播、不穿过填充区域且与网格无任何交点（即存在直接视线）时，绘制一条边。

核心问题及实现思路 #

1. 3D线段与三角形相交检测

• 可基于Möller-Trumbore射线三角形相交算法自行实现，或借助Rvcg等几何处理包的相关函数。该算法能高效判断线段是否与单个三角形相交，并返回交点信息。
• 实现时需排除线段端点落在三角形上的情况，避免误判相邻三角形的连接。

2. 确保视线在洞穴空腔内

• 对每一对待检测的三角形中心连线，取线段中点，判断该点是否处于洞穴内部：
  • 方法：从中点向任意方向发射一条射线，统计射线与网格三角形的交点数量。若交点数为奇数，则中点在洞穴空腔内；偶数则在填充区。
  • 可利用rgl包的intersect3d函数辅助实现射线与网格的交点统计。

3. 性能优化

由于三角形数量庞大，两两检测复杂度极高：

• 先用spdep::dnearneigh根据3D距离筛选出合理范围内的三角形对，再对候选对进行相交检测，大幅减少计算量。

方案二：正交方向三角化 #

需求 #

对原CT三角形降采样，生成与洞穴路径正交的点并进行三角化，连接这些点的中心（替代射线追踪方案）。

实现思路 #

1. 提取洞穴中心轴线

使用Rvcg包的vcgSkeleton函数提取洞穴网格的中心轴线，以此确定洞穴的走向路径。

2. 生成正交采样点

• 沿着中心轴线的多个位置，生成与轴线垂直的采样平面。
• 计算每个采样平面与洞穴网格的交点，这些交点即为正交方向的采样点。

3. 平面内三角化

对每个采样平面内的2D坐标点，使用tripack或deldir包进行Delaunay三角化，得到正交于洞穴路径的三角网格。

4. 原网格降采样

• 可通过k-means聚类对原三角形中心分组，保留每个聚类的代表点；或根据三角形到中心轴线的距离筛选，保留洞穴“核心区域”的三角形，减少后续计算量。

已完成代码示例 #

library(rgl)

## str(mesh) 应返回包含6个元素的列表，其中mesh$vb和mesh$it为第1、2项
mesh <- rgl::readOBJ("resampled_20_wavefront.obj")

triangle_index_df <- t(mesh$it)       ## 列出网格中所有三角形
coordinates_df    <- t(mesh$vb)[,1:3] ## 所有三角形顶点的XYZ坐标

## 获取第i个三角形的顶点坐标
N_Triangles      <- nrow(triangle_index_df)
Triangle_centres <- matrix(NA, nrow=N_Triangles, ncol=3); colnames(Triangle_centres) <- c("x","y","z") 

## 计算每个三角形的中心
WhichTriangles <- 1:N_Triangles
for (i in 1:N_Triangles)
 { if (i%%1000==0){print(paste(i, "of", N_Triangles))}
 tricoords <- coordinates_df[triangle_index_df[i,],]
 ## 三角形中心坐标
 Cent <- colMeans(coordinates_df[triangle_index_df[i,],], na.rm=T)
 Triangle_centres[i,] <- Cent
 # triangles3d(tricoords,col="red3", alpha=0.4)
 }
shade3d(mesh, col="green4", alpha=0.3)
points3d(Triangle_centres, col='red3')

内容的提问来源于stack exchange，提问作者Tom