Определение, пересекает ли сфера объект или нет
Мне описало замкнутый объект поверхностное представление треугольников (описанный тремя вершинами, который формирует правило правой руки с нормальным, указывающим на "внешнюю сторону" объекта). Я помещаю сферу некоторого радиуса в 3D пространстве куда-нибудь близко к поверхности объекта. Я хочу определить, пересекает ли сфера объект или нет.
Я думал о 3 способах определить это, но у каждого есть их оборотные стороны, и ни один из них не идеален.
1) Я могу определить "сторону", в которую сфера будет помещенной, оттуда я могу вычислить сетку расстояний от ссылочной плоскости до расстояния, где с объектом сначала встречаются. Я могу сделать то же для противоположной "стороны" сферы и затем просто проверить, больше ли расстояние до объекта всегда, чем расстояние до поверхности сферы. Если расстояние до объекта всегда больше, сфера не пересекает объект ни в одной из точек на сетке.
Преимущество для этого - то, что это довольно быстро, но так как я только вычисляю осторожные точки, не абсолютный. Если разрешение моей сетки является также курсом, существует шанс, что сфера пересечется в точке, которая является промежуточной мои узлы сетки.
2) Я могу взять все вершины всех треугольников и проверить их по уравнению сферы, которую я поместил. Если вершины будут обнаружены в сфере, то сфера абсолютно будет частично в объекте.
Преимущество этого - то, что это довольно быстро, но также и очень подвержено отказу. Сфера могла пересечь объект в треугольнике и пропустить все вершины все вместе.
3) Я могу вычислить кластер точек на поверхности сферы. Я могу тогда проверить, ли каждая точка в объекте или не (использование 3D версии точки в алгоритме полигона). Если какая-либо точка в объекте, часть сферы в объекте.
Преимущество этого - то, что может быть очень правильно, в зависимости от того, сколько точек я использую на поверхности моей сферы (более высокая плотность точек = больше точности). Однако точка в объектном алгоритме является довольно дорогой, особенно когда количество треугольников увеличивается. Этот метод был бы лучшим (даже скажет мне точно, где и сколько из сферы пересекает объект), но это было бы очень медленно.
Есть ли какой-либо алгоритм или метод Вы, парни могут знать для решения такой проблемы? Моей передовой целью является точность, я должен знать, будет ли сфера или не касаться объекта. Также было бы хорошо знать, где сфера затрагивает или по крайней мере общая область. Наконец скорость всегда является хорошей вещью иметь.
Спасибо
- Faken
7 ответов
Это должен быть полный ответ на ваш вопрос. Я не приводил реализацию, поэтому, возможно, потребуется подумать, чтобы избежать ненужных разделений и т. Д. Пожалуйста, попросите разъяснений, если что-то неясно. Я опираюсь на идеи Джона в 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
Это очень похожая проблема, теперь в 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, поэтому мы уже проверили его.
Хорошо, я попробую еще раз. ;)
Если вам нужна точность, и если вы точно знаете вершины, вы можете использовать кратчайшее расстояние до плоскости , чтобы увидеть, касается ли сфера любой из плоскостей, определенных любым набором из трех вершины, которые дают вам ваши треугольники. Для тех, кто это делает, вы увидите, действительно ли точка наибольшего сближения находится внутри треугольника.
Я думаю, вы можете сделать это с помощью CGAL . Сначала вычислите сумму Минковского для сферы и объекта, затем вы можете просто проверить, находится ли центр сферы (как контрольная точка) внутри или вне объекта. Это можно сделать с помощью арифметики произвольной точности, так что вы можете быть точными, если вам нужно.
Пересечение сферы и плоскости представляет собой связное множество.
Следовательно, принимая идею Джона о «ближайшем приближении к плоскости», если сфера и треугольник пересекаются, и если оба замкнуты, то либо:
- ближайшая точка на плоскости лежит внутри треугольника
- сфера пересекает по крайней мере одно из краев треугольника (поскольку в силу связности существует непрерывный путь внутри пересечения плоскости / сферы от некоторой точки внутри треугольника до некоторой точки вне треугольника. Этот путь должен пересекать границу, а точка в что он делает так, лежит в сфере).
Пересечение сферы и линии является связным множеством.
Продлите ребро до линии так же, как мы расширили треугольник до плоскости. Если сфера пересекает ребро, то либо:
- ближайшая точка на прямой лежит внутри ребра;
- сфера пересекает хотя бы одну из вершин треугольника.
Итак, если любая из 4 ближайших точек (1 плоскость, три прямые) лежит в сфере и треугольнике, то, конечно, они пересекаются.В противном случае: если все четыре находятся вне сферы, то два не пересекаются, а если любой из них находится внутри сферы, то они пересекаются, если любая из вершин треугольника лежит в сфере.
К сожалению, выполнение этого для каждого треугольника только говорит вам, пересекаются ли сфера и поверхность твердого тела. Он не учитывает случай, когда сфера полностью находится внутри твердого тела. Итак, наконец (или, возможно, сначала), вы должны также проверить, находится ли центр сферы внутри твердого тела.
Это, конечно, может быть неэффективным - я не специалист в программировании геометрии. И, как указывает Эндрю МакГрегор, вычисления с плавающей запятой не обязательно дают согласованные результаты.
Подойдет ли вам сочетание (2), а также проверка центра треугольной грани как другой вершины?
Проверка пересечения с использованием Bounding Volume может вас заинтересовать. Проверьте это .
Вот страница , на которой рассматриваются алгоритмы по алгоритмам пересечения поверхностей.
ура
Сделайте гибрид. Найдите замкнутый треугольник / точку с помощью метода 2 и проверьте все комбинации пересечений со всеми треугольниками рядом с треугольником.