Главная Вход в систему Регистрация
Задать вопрос Консультации Пользователи Форум
О системе Помощь
Задать вопрос экспертам
Консультация № 67288
16.12.2006, 20:31
0.00 руб.
0 6 1
Образование
Мир вам, уважаемые эксперты!
Быть может, вы, со свежим взглядом, подскажете мне решение данной проблемы...
Имеется произвольный треугольник в пространстве, заданный координатами своих вершин. Имеется также куб со стороной dx, расположенный вдоль осей координат.
Необходимо определить пересекаются они, или нет.
Беда в том, что сделать это нужно быстро, так как много треугольников и много кубов (это программа - генератор сеток).
Проверять наличие пересечения треугольника с каждым из 16 ребер - слишком долго. Перебирать точки, лежащие в треугольнике с мелким шагом - тоже. А больше мне ничего на ум не идет.
Может есть какое неравенство, определяющее точки, лежащие в треугольнике ?
Короче, буду благодарен любой информации по теме.
С уважением, Лука.

Обсуждение

Неизвестный
18.12.2006, 11:08
общий
это ответ
Здравствуйте, Лука!

А зачем именно кубы нужны? Можно проверять точки пересечения сторон треугольников с плоскостями, перпендикулярными осям координат. Что очень легко спроецировав сторону треугольника (получится отрезок): например для оси X: координата X одного конца будет меньше координаты х поверхности, а другая больше... Если очень хочется, можно при нахождении точки пересечения с плоскостью, определить, гранью какого куба является данная плоскость: Если отрезок пересекаеться с тремя плоскостями (по всем осям Х,У,Z) то он и будет пересекаться с кубом, у которого большее расстояние от центра осей координат. Тут опять идет перебор, но рассчетов значительно меньше.
Неизвестный
21.12.2006, 00:26
общий
Долго добирался до вопросов...Пожалуй, наиболее быстрый способ такой:По вершинам треугольника вычисляются коэффициенты уравнния плоскости, в которой он лежит: Ax+By+Cz+D=0Далее используете простую функциюf(x,y,z) = Ax+By+Cz+DЕсли все вершины куба лежат по одну сторону плосоксти треугольника, то и значение она будет принимать для всех — одного знака. Если принимает значения разных знаков, то — пересекает.
Неизвестный
21.12.2006, 11:39
общий
Плоскость - да пересекает.А треугольник может и не пересекать.Повторюсь: речь о ЧАСТИ плоскости, заключенной в пределах треугольника.
Неизвестный
21.12.2006, 12:03
общий
Ок.Делаете преобразование 3-хмерных координат в 2-мерные (на плоскости, в которой лежит треугольник). И делаете проверку (одного/разного знака) только для тех точек, чьи проекции на плоскость лежат внутри треугольника. Это уже не совсем точно, могут быть ошибки. Зато быстро.Как проверить, что точка лежит внутри треугльника:<i>Либо также смотреть на знак векторных произведений:</i>AB*AD, BC*BD, CA*CD,где ABC — вершины треугольника, D — проверяемая точка.<i>Либо считать площади треугольников:</i>S<sub>ABC</sub> = S<sub>ABD</sub> + S<sub>ADC</sub> + S<sub>DBC</sub> <=> точка лежит внутри треугольникаS<sub>ABC</sub> = [1/2]*|(X<sub>B</sub>-X<sub>A</sub>)(Y<sub>C</sub>-Y<sub>A</sub>)-(X<sub>C</sub>-X<sub>A</sub>)(Y<sub>B</sub>-Y<sub>A</sub>)|
Неизвестный
21.12.2006, 12:07
общий
Итого:<ol><li>Если не все проекции точек лежат внутри треуглоьника, то можно просчитывать для всех ребер (которых, кстати, у куба 12, а не 16).</li><li>Если у всех проекции лежат вне треуглоьника — не пересекает.</li><li>Если у всех — внутри треугольника, смотрим с какой стороны от плоскости они лежат.</li></ol>
Неизвестный
21.12.2006, 14:44
общий
Боюсь, преобразование координат - не самая удачная мысль. Там ведь, как я помню, идут уже тригонометрические функции... а это очень плохо, так как долго. Да и узкие треугольники будут проскакивать "на раз".Тем не менее, спасибо за идеи.
Форма ответа