Определение, пересекает ли сфера объект или нет

Question

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

Я подумал о трех способах определения этого, но у каждого есть свои недостатки, и ни один из них не идеален.

1) Я могу определить «сторону», на которой будет размещена сфера, оттуда я могу рассчитать сетку расстояний от базовой плоскости до расстояния, на котором объект встречается впервые. Я могу сделать то же самое для противоположной «стороны» сферы, а затем просто проверить, всегда ли расстояние до объекта больше, чем расстояние до поверхности сферы. Если расстояние до объекта всегда больше, сфера не пересекает объект ни в одной из точек сетки.

Преимущество в том, что он довольно быстрый, но, поскольку я рассчитываю только дискретные точки, он не абсолютный. Если разрешение моей сетки слишком большое, есть вероятность, что сфера пересечется в точке, которая находится между узлами моей сетки.

2) Я могу взять все вершины всех треугольников и сравнить их с уравнением сферы, которую я поместил. Если вершины обнаружены внутри сферы, сфера будет абсолютно частично внутри объекта.

Преимущество этого в том, что он довольно быстрый, но также очень склонен к сбоям. Сфера может пересекать объект внутри треугольника и пропустить все вершины вместе.

3) Я могу рассчитать кластер точек на поверхности сферы. Затем я могу проверить, находится ли каждая точка внутри объекта или нет (используя трехмерную версию точки внутри алгоритма многоугольника). Если какая-либо одна точка находится внутри объекта, часть сферы находится внутри объекта.

Преимущество этого в том, что оно может быть очень точным, в зависимости от того, сколько точек я использую на поверхности моей сферы (более высокая плотность точек = больше точности). Тем не менее, точка внутри алгоритма объекта довольно дорогая, особенно когда количество треугольников увеличивается. Этот метод был бы лучше (даже сказал бы мне точно, где и сколько сферы пересекает объект), но это будет очень медленно

Есть ли какой-нибудь алгоритм или метод, который вы, ребята, знаете, чтобы решить такую ​​проблему? Моя главная цель - точность, мне нужно знать, будет ли сфера касаться объекта. Также было бы хорошо узнать, где сфера касается или хотя бы общей области. Наконец, скорость - это всегда хорошо.

Спасибо

-Faken

Answer 1

Это должен быть полный ответ на ваш вопрос. Я не дал реализацию, поэтому может потребоваться продумать, чтобы избежать ненужных делений и т. Д. Пожалуйста, уточните, если что-то неясно. Я строю Джона на идеях CashCommons.

Пусть c - центр сферы с радиусом r. Что нам действительно нужно знать, так это то, что любая точка треугольника T (НЕ только три вершины) ближе к c, чем к единицам r?

Есть три случая для рассмотрения:

1. Точка в T, ближайшая к c, является вершиной T. Это просто!
2. Точка в T, ближайшая к c, находится внутри T.
3. Точка в T, ближайшая к c, находится на одном из ребер T.

Определим некоторые переменные:

• c: центр сферы
• r: радиус сферы
• T: наш треугольник
• v1, v2, v3: вершины T
• t: точка в T, ближайшая к c
• P: уникальная плоскость, содержащая v1, v2, v3
• p: точка в P, ближайшая к c

ШАГ 1: Проверьте все вершины треугольника, на случай, если мы находимся в случае 1.

ШАГ 2: найдите p, точку в P, ближайшую к c. Это можно сделать, проецируя c на P.

ШАГ 3: Если мы находимся в случае 2, мы в основном сделали. Поэтому проверьте, находится ли p в T. (Проверить, находится ли точка в данном треугольнике, относительно легко, но я не знаю ЛУЧШЕГО способа сделать это, поэтому я опущу это.) Если это так, проверьте, dist (p, c)> r, и это дает вам ваш ответ.

Это оставляет только случай 3. Итак, предположим, что у нас есть p, и что p отсутствует в T. Теперь мы на самом деле знаем что-то конкретное о p из геометрии: линия c -> p перпендикулярна P. (Если бы не было, мы могли бы точка р ', которая ближе к с, чем р.) Из-за этой перпендикулярности мы можем использовать теорему Пифагора:

Dist(c, z)^2 = Dist(c, z)^2 + D(p, z)^2

для любого z в P. В частности, это верно для z = t.

Так что теперь нам просто нужно найти t и проверить:

D(p,t)^2 <= r^2 - D(c,p)^2

Это очень похожая проблема, теперь в двух измерениях. Нужно найти t в T, которое ближе всего к p и, следовательно, к c. Мы уже проверили, что t не находится внутри T или одной из вершин T. Следовательно, оно должно быть на одном из ребер. Итак, мы можем просто попытаться найти его на каждом краю. Если t не в вершине, то линия t -> p будет перпендикулярна стороне, так что это довольно просто сделать.

ШАГ 4: Для каждой стороны v1 -> v2 треугольника выполните следующее:

4,1. Сегмент линии от v1 до v2 задается как

(x,y,z) = (v1x, v1y, v1z) + s * (v2x - v1x, v2y - v1y, v2z - v1z), 0 <= s <= 1

4.2 Нам нужна линия, лежащая в плоскости P, перпендикулярная v1 -> v2 и содержащая p. Эта строка будет иметь вид

(px, py, pz) + s * (qx, qy, qz)

, поэтому нам просто нужно выбрать вектор q, параллельный плоскости P и перпендикулярный v1 -> v2. Принимая

q = (p-->c) x (v1-->v2)

(т. Е. Перекрестное произведение) должно это сделать, поскольку это будет перпендикулярно нормали P, и, следовательно, параллельно P и перпендикулярно v1 -> v2.

4.3. Решить систему уравнений

(tx,ty,tz) = (v1x, v1y, v1z) + s1 * (v2x - v1x, v2y - v1y, v2z - v1z)
(tx,ty,tz) = (px, py, pz) + s2 * (qx, qy, qz)

чтобы найти t, которое лежит на обеих строках. Это действительно означает решение

v1x + s1 * (v2x - v1x) = px + s2 * qx
v1y + s1 * (v2y - v1y) = py + s2 * qy
v1z + s1 * (v2z - v1z) = pz + s2 * qz

для s1 и s2.

4,4. Если s1 находится между 0 и 1, то мы нашли точку t, которая находится между v1 и v2, и это следует проверить.

* * 4,5 тысячу семьдесят пять. Если s1 не находится между 0 и 1, то один из v1 или v2 был ближайшим к p, поэтому мы уже проверили его.

Answer 2

Пересечение сферы и плоскости - это связное множество.

Следовательно, принимая идею Джона о «самом близком приближении к плоскости», если сфера и треугольник пересекаются и оба замкнуты, то либо:

• ближайшая точка на плоскости лежит внутри треугольника
• сфера пересекает хотя бы одно из ребер треугольника (поскольку благодаря связности существует непрерывный путь в пересечении плоскости / сферы от некоторой точки внутри треугольника до некоторой точки вне треугольника. Этот путь должен пересекать границу и точка, в которой это происходит, лежит в сфере).

Пересечение сферы и линии является связным множеством.

Так что растяните край до линии так же, как мы расширили треугольник до плоскости. Если сфера пересекает край, то либо:

• ближайшая точка на линии лежит внутри края
• сфера пересекает хотя бы одну из вершин треугольника.

Итак, если любая из 4 ближайших точек (1 плоскость, три линии) лежит в сфере и треугольнике, то, конечно, они пересекаются. В противном случае: если все четыре находятся вне сферы, то эти два не пересекаются, и если какой-либо из них находится внутри сферы, то они пересекаются, если любая из вершин треугольника находится в сфере.

К сожалению, выполнение этого для каждого треугольника только говорит вам, пересекаются ли сфера и поверхность твердого тела. Он не рассматривает случай, когда сфера полностью находится внутри твердого тела. Итак, наконец (или, возможно, сначала), вы также должны проверить, находится ли центр сферы внутри твердого тела.

Конечно, это может быть неэффективно - я не эксперт в программировании геометрии. И, как отмечает Эндрю МакГрегор, вычисления с плавающей точкой не обязательно дают согласованные результаты.

Answer 3

Я думаю, что вы можете сделать это с CGAL . Сначала вычислите сумму Минковского для сферы и объекта, затем вы можете просто проверить, находится ли центр сферы (как точка отсчета) внутри или снаружи объекта. Это может быть сделано в произвольной арифметике точности, поэтому вы можете быть точным, если вам нужно.

Answer 4

ОК, попробую еще раз. ;)

Если вам нужна точность и если вы точно знаете вершины, то вы можете использовать кратчайшее расстояние до плоскости , чтобы увидеть, касается ли сфера какой-либо из плоскостей, определенных любым набором из трех вершин, которые дать тебе свои треугольники. Для тех, кто это делает, вы видите, лежит ли точка ближайшего сближения на самом деле внутри треугольника.

Answer 5

Сделать гибрид. Найдите замкнутый треугольник / точку с помощью метода 2 и проверьте все комбинации пересечений со всеми треугольниками вблизи треугольника.

Answer 6

Может ли объединение (2), а также проверка центра треугольной грани работать как другая вершина для вас?

Answer 7

Проверка пересечения с использованием Bounding Volume может вас заинтересовать. Пожалуйста, проверьте это .

Вот страница , в которой рассматриваются алгоритмы алгоритмов пересечения поверхностей.

ура