我有一个使用 BufferGeometry
创建的 Mesh
。
我还有鼠标与 Mesh
相交的坐标,使用 Raycaster
。
我正在尝试检测相交点半径范围内(和接触)的面孔。
一旦我检测到“相切”面孔,我就想给这些面孔上色。因为我正在使用 BufferGeometry
,所以我正在操作我的几何体上的缓冲区属性。
这是我的代码:
let vertexA;
let vertexB;
let vertexC;
let intersection;
const radius = 3;
const color = new THREE.Color('red');
const positionsAttr = mesh.geometry.attributes.position;
const colorAttr = mesh.geometry.attributes.color;
// on every mouseMove event, do below:
vertexA = new THREE.Vector3();
vertexB = new THREE.Vector3();
vertexC = new THREE.Vector3();
intersection = raycaster.intersectObject(mesh).point;
// function to detect tangent edge
function isEdgeTouched(v1, v2, point, radius) {
const line = new THREE.Line3();
const closestPoint = new THREE.Vector3();
line.set(v1, v2);
line.closestPointToPoint(point, true, closestPoint);
return point.distanceTo(closestPoint) < radius;
}
// function to color a face
function colorFace(faceIndex) {
colorAttr.setXYZ(faceIndex * 3 + 0, color.r, color.g, color.b);
colorAttr.setXYZ(faceIndex * 3 + 0, color.r, color.g, color.b);
colorAttr.setXYZ(faceIndex * 3 + 0, color.r, color.g, color.b);
colorAttr.needsUpdate = true;
}
// iterate over each face, color it if tangent
for (let i=0; i < (positionsAttr.count) /3); i++) {
vertexA.fromBufferAttribute(positionsAttr, i * 3 + 0);
vertexB.fromBufferAttribute(positionsAttr, i * 3 + 1);
vertexC.fromBufferAttribute(positionsAttr, i * 3 + 2);
if (isEdgeTouched(vertexA, vertexB, point, radius)
|| isEdgeTouched(vertexA, vertexB, point, radius)
|| isEdgeTouched(vertexA, vertexB, point, radius)) {
colorFace(i);
}
虽然这段代码有效,但它的性能似乎很差,尤其是当我处理具有许多面的几何体时。当我检查 Chrome DevTools 上的性能监视器时,我注意到 isEdgeTouched
和 colorFace
函数在人脸的每次迭代中都占用了太多时间。
有没有办法改进这个算法,或者有更好的算法来检测相邻的人脸?
编辑
我从 THREE.js slack channel 获得了一些帮助,并修改了算法以使用 Three 的 Sphere
。我现在不再进行“边缘”检测,而是检查人脸是否在 Sphere
更新后的代码:
const sphere = new THREE.Sphere(intersection, radius);
// now checking if each vertex of a face is within sphere
// if all are, then color the face at index i
for (let i=0; i < (positionsAttr.count) /3); i++) {
vertexA.fromBufferAttribute(positionsAttr, i * 3 + 0);
vertexB.fromBufferAttribute(positionsAttr, i * 3 + 1);
vertexC.fromBufferAttribute(positionsAttr, i * 3 + 2);
if (sphere.containsPoint(vertexA)
&& sphere.containsPoint(vertexA)
&& sphere.containsPoint(vertexA)) {
colorFace(i);
}
当我在我的应用程序中对此进行测试时,我注意到性能明显比以前的版本有所提高。但是,我仍然想知道是否可以进一步改进这一点。
最佳答案
这似乎是一个经典的最近邻问题。
您可以通过为网格(例如 AABB 树)构建边界体积层次结构 (BVH),非常快速地找到距给定点最近的三 Angular 形来缩小搜索范围。
BVH: https://en.m.wikipedia.org/wiki/Bounding_volume_hierarchy
AABB 树: https://www.azurefromthetrenches.com/introductory-guide-to-aabb-tree-collision-detection/
然后您可以使用给定半径的球体或盒子针对 BVH 进行范围查询。这相当于使用球体/盒子“查询”遍历 BVH,该查询用于快速且非常早地丢弃不剪裁球体/盒子“查询”的边界体积节点。最后,实际距离或相交测试仅使用 BV 与球体/框“查询”相交的三 Angular 形进行,通常是三 Angular 形的一小部分。
BVH 查询的复杂度为 O(log n),而您的方法为 O(n)。
关于javascript - THREE.js 从 raycaster 交点检测相邻面,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54331380/