Проверить, находится ли куб внутри сферы — самый быстрый метод

Есть ли более быстрый способ проверить, находится ли куб, выровненный по оси, внутри сферы, чем проверять отдельно, находятся ли 8 углов внутри сферы?

Я иду по октодереву, проверяя, пересекаются ли его кубические листы или заключены ли они в сферу. Я нашел метод пересечения здесь: Тест пересечения кубической сферы?

Я надеялся найти более эффективный способ проверки на вложенность. В конце концов мне нужен тест, который возвращает одно из трех состояний:

  1. вне Сферы
  2. пересекающаяся сфера
  3. внутри сферы

Кубы определяются двумя точками, сфера - ее центром и радиусом.


hittest geometry octree
person BoshWash    schedule 15.08.2013    source источник
comment
Вероятно, вы проверяете много кубов или много сфер, так как для вас важна скорость. Иногда можно амортизировать сложность за счет набора объектов, поэтому имеет значение, много ли у вас сфер или много кубов. Пожалуйста, уточните, каких объектов много, и имеют ли они одинаковый размер или разные размеры.   -  person Michael    schedule 21.08.2013

Ответы (2)


arrow_upward
3
arrow_downward

Чтобы определить, находится ли куб полностью внутри сферы, можно обойтись проверкой только одной вершины — самой дальней от центра сферы. Вы можете определить, какую вершину тестировать, сравнив центральные точки куба и сферы. Например, если задан куб с центром в точке (cx,cy,cz) и полудлиной ребра l, а также сфера в точке (sx,sy,sz) с радиусом r, точка для проверки будет

tx = cx + ( cx > sx ? l : -l );
ty = cy + ( cy > sy ? l : -l );
tz = cz + ( cz > sz ? l : -l );

Однако сравнение углов куба со сферой не позволит выявить все случаи пересечения — рассмотрим куб от (-5,-5,-5) до (5,5,5) и сферу в точках (0,0, 6) с радиусом 2. Два объема пересекаются, но ни одна вершина не находится внутри сферы.

Я бы выбрал многопроходный подход:

  1. Проверка выровненного по осям ограничивающего прямоугольника сферы относительно куба — очень простая проверка с быстрым отклонением для явно не пересекающихся случаев.
  2. Проверить, лежит ли центр сферы внутри куба
  3. Эта возможность может быть исключена в вашей системе, но вы также должны выполнить проверку ограничивающей рамки для случая, когда сфера полностью находится внутри куба.
  4. На данный момент у нас нет другого выбора, кроме как проверить пересечения между сферой и кубом. лица.

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

person ryanm    schedule 16.08.2013

arrow_upward
0
arrow_downward

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

person Jon List    schedule 15.08.2013
comment
Представьте себе сферу, которая выровнена по оси с центром куба достаточно близко, чтобы сфера едва касалась центра грани куба. В этом случае. Расстояние между центром куба и сферой меньше радиуса + диагонали куба, но они вообще не пересекаются. - person Tyler Shellberg; 27.04.2020