THREE.js Обнаружение смежных граней из точки пересечения Raycaster - PullRequest
Новая
       26

THREE.js Обнаружение смежных граней из точки пересечения Raycaster

0 голосов
/ 23 января 2019

У меня есть Mesh, созданный с помощью BufferGeometry.У меня также есть координаты, где моя мышь пересекает 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 отнимают слишком много времени на каждой итерации для грани.

Есть ли способ улучшить этот алгоритм,или есть лучший алгоритм, чтобы использовать для обнаружения смежных лиц?

Edit

Я получил некоторую помощь от слабого канала THREE.js и изменил алгоритм для использования Three's 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);
}

Когда я проверял это в своем приложении,Я заметил, что производительность значительно улучшилась по сравнению с предыдущей версией.Однако мне все еще интересно, смогу ли я улучшить это дальше.

1 Ответ

0 голосов
/ 24 января 2019

Кажется, это классическая проблема ближайших соседей.

Вы можете сузить поиск, быстро найдя ближайшие треугольники в данной точке, построив иерархию ограничивающего объема (BVH) для сетки, например, AABB-дерево.

BVH:https://en.m.wikipedia.org/wiki/Bounding_volume_hierarchy

AABB-Tree: https://www.azurefromthetrenches.com/introductory-guide-to-aabb-tree-collision-detection/

Затем вы можете запросить BVH запрос диапазона, используя сферу или прямоугольник заданного радиуса.Это равносильно обходу BVH с использованием «запроса» сферы / блока, который используется для быстрого и очень раннего удаления узлов ограничивающего объема, которые не обрезают «запрос» сферы / блока.В конце тест на реальное расстояние или пересечение проводится только с треугольниками, чьи BV пересекают «запрос» сферы / прямоугольника, как правило, очень небольшую часть треугольников.

Сложность запроса к BVH равна O (log n) в отличие от вашего подхода, который равен O (n).

...