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

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

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

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

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

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

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

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

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

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

Спасибо

-Faken

Ответ 1

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

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

Существует три случая:

Точка в T, ближайшая к c, является вершиной из T. Это легко!
Точка в T, ближайшая к c, находится внутри T.
Точка в 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. (Если бы это не так, мы могли бы найти точка p ', которая ближе к c, чем 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, поэтому мы уже проверили его.

Ответ 2

Хорошо, я попробую еще раз.;)

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

Ответ 3

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

Ответ 4

Пересечение между сферой и плоскостью является связным множеством.

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

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

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

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

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

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

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

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

Ответ 5

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

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

веселит

Ответ 6

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

Ответ 7

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