Ворончихин, Е. К. Расстояние от точки до многогранника в пространстве / Е. К. Ворончихин. — Текст : непосредственный // Молодой ученый. — 2020. — № 30 (320). — С. 13-17. — URL: https://moluch.ru/archive/320/72811/ (дата обращения: 17.07.2024).
В данной работе рассмотрена задача поиска минимального расстояния между многогранником и точкой, не лежащей внутри него. Предложен алгоритм решения этой задачи и способ его применения в 3D-моделировании.
При реализации метода 3D-моделирования Ray Marching необходимым является определение минимального расстояния от некоторой точки до трехмерного объекта [1]. В данной статье предлагается алгоритм поиска такого расстояния от точки до выпуклого многогранника.
Математическая постановка задачи
Определение 1.
Пусть дан выпуклый многогранник и точка вне его. Минимальным расстоянием от этой точки до данного многогранника назовем длину отрезка между указанной точкой и ближайшей к ней точкой, принадлежащей многограннику.
Задача.
Втрехмерном евклидовом пространстве найти минимальное расстояние от точки
с известными координатами до выпуклого многогранника
с известными координатами вершин.
Обозначения, используемые в
статье
и
— точка вне многогранника и многогранник соответственно, между которыми определяется минимальное расстояние;
— плоскость, содержащая произвольные точки
, не лежащие на одной прямой;
— расстояние между объектами
и
, каждый из которых может быть точкой, прямой или плоскостью;
— минимальное расстояние между точкой
и выпуклым многогранником
;
,
,
— координаты точки
по осям
,
,
соответственно.
Алгоритм решения
Определим, какие из вершин многогранника
являются тремя ближайшими к
и назовем их
так, что
Проверим выполнение следующего условия:
Проекция точки
на
находится внутри треугольника
или на его границе
Рис. 1.
Пусть
— проекция
на плоскость
(рис. 1). Если она находится внутри треугольника
или на его границе, то выполнено равенство:
(см. доказательство Теоремы 1). Для того, чтобы проверить выполнение этого условия, находим координаты точки
.
Зная координаты точек
, составляем уравнение плоскости
и определяем координаты вектора нормали к ней. Используя координаты точки
и координаты направляющего вектора прямой
(являющегося вектором нормали
) составляем каноническое уравнение прямой
. Зная его и уравнение плоскости
определяем координаты точки
, которая является точкой пересечения прямой
и
. Далее проверяем принадлежность точки
треугольнику
. Метод проверки описан в статье [2]. При выполнении данного условия
. Находим его как расстояние между двумя точками в пространстве.
В случае невыполнения условия пункта 1, переходим к проверке следующего условия.
Проекция точки
на прямую
принадлежит отрезку
Рис. 2.
Пусть
— проекция
на прямую
(рис. 2). Если
принадлежит отрезку
, то выполнено равенство:
(см. доказательство Теоремы 2). Для проверки выполнения этого условия находим координаты точки
.
Для этого определяем координаты вектора
, являющегося направляющим вектором прямой
, и подставляем их в каноническое уравнение прямой
. Далее составляем уравнение плоскости
, проходящей через точку
перпендикулярно прямой
и находим координаты точки пересечения плоскости
с прямой
, являющиеся координатами точки
.
Если выполнена система неравенств:
, то
принадлежит отрезку
.
При выполнении данного условия
. Находим его как расстояние между двумя точками в пространстве.
При невыполнении пунктов 1 и 2 (рис. 3) задача сводится к поиску расстояния между
и
, поскольку расстояние от
до
не является ни расстоянием от
до ближайшей грани
, ни расстоянием от
до ближайшего ребра
.
Рис. 3.
Для проверки корректности данного алгоритма рассмотрим следующие теоремы.
Теорема 1.
Минимальное расстояние от некоторой точки
, лежащей вне выпуклого многогранника, до этого многогранника равно расстоянию от
до ближайшей к ней грани этого многогранника тогда и только тогда, когда проекция точки
на плоскость, содержащую эту грань, принадлежит треугольнику, образованному тремя ближайшими к
вершинами многогранника.
Доказательство
. Пусть
— ближайшие к
вершины многогранника
, при этом
. Пусть
— проекция точки
на
.
Пусть
лежит принадлежит треугольнику
. Тогда
— ближайшая к
точка треугольника
, поскольку
— высота пирамиды
. Поскольку треугольник
принадлежит ближайшей к
грани многогранника, то расстоянием от
до этой грани является длина отрезка
. Расстояние до ближайшей к
грани многогранника меньше, чем расстояние от
до любой другой грани многогранника, следовательно, длина отрезка
и есть минимальное расстояние от
до многогранника.
Пусть
находится вне треугольника
. Следовательно,
находится вне грани, которой принадлежит этот треугольник. Эта грань — единственная, принадлежащая плоскости
, поскольку многогранник выпуклый. Поэтому
не принадлежит многограннику, следовательно, отрезок
не является минимальным расстоянием от
до многогранника.
Теорема 2.
Минимальное расстояние от некоторой точки
, лежащей вне выпуклого многогранника, до этого многогранника равно расстоянию от
до ближайшего к ней ребра этого многогранника тогда и только тогда, когда проекция точки
на прямую, содержащую это ребро, принадлежит этому ребру, а проекция точки
на плоскость, образованную тремя ближайшими к
вершинами многогранника совпадает с проекцией
на ближайшее к ней ребро многогранника или лежит вне треугольника, образованного тремя ближайшими к
вершинами многогранника.
Доказательство.
Пусть
— ближайшие к
вершины многогранника
, при этом
;
— прямая, содержащая отрезок
;
— проекция точки
на
;
— проекция точки
на
.
Пусть
принадлежит отрезку
,
лежит вне треугольника
. Проведем плоскость
, содержащую
и не имеющую общих точек с двумя гранями многогранника, пересекающимися по ребру
. Все точки многогранника, за исключением точек, принадлежащих ребру
, будут находится по другую сторону плоскости
относительно точки
, поэтому расстояние от
до любой точки многогранника будет больше, чем расстояние от
до
. Поскольку
и есть расстояние от
до
и
принадлежит многограннику, длина отрезка
является минимальным расстоянием от
до многогранника.
Пусть
принадлежит отрезку
,
совпадает с
. В этом случае по теореме 1 минимальное расстояние от
до многогранника есть
. Поскольку
совпадает с
,
является минимальным расстоянием от
до многогранника.
Пусть
не принадлежит отрезку
. Отрезок
— единственное ребро многогранника, принадлежащее
, поскольку многогранник выпуклый, следовательно,
не принадлежит многограннику, и поэтому отрезок
не является минимальным расстоянием от
до многогранника.
Применение данного алгоритма
Ray Marching — одна из относительно новых технологий, используемых для рендеринга трехмерных сцен. При ее реализации для рендеринга непрозрачных объектов можно использовать поля расстояний со знаком, что позволит оптимизировать вычислительный процесс. Поле расстояния — это функция, определяющая расстояние от точки до поверхности объекта [3]. Вышеописанный метод может быть использован для определения минимальных расстояний до любых выпуклых многогранников.
Литература:
Ray Marching Distance Fields in Real-time on WebGL. — Текст: электронный // semanticscholar: [сайт]. — URL: https://pdfs.semanticscholar.org/a964/750aa212bd490d258221bc9756e7e58c5317.pdf (дата обращения: 18.07.2020).
Weisstein, Eric W. Triangle Interior. — Текст: электронный // mathworld: [сайт]. — URL: https://mathworld.wolfram.com/TriangleInterior.html (дата обращения: 18.07.2020).
GPU Ray Marching of Distance Fields / J. T. Lukasz. — Текст: электронный // DTU.compute: [сайт]. — URL: http://www2.imm.dtu.dk/pubdb/edoc/imm6392.pdf (дата обращения: 19.07.2020).
Основные термины(генерируются автоматически): минимальное расстояние, многогранник, вершина многогранника, выпуклый многогранник, расстояние, длина отрезка, проекция, треугольник, грань, уравнение плоскости.
Итак, самосовмещение многогранника обязательно является поворотом вокруг оси, проходящей через центр многогранника. Эта ось пересекает наш многогранник в вершине или во внутренней точке ребра или грани. Следовательно, наше самосовмещение переводит в себя...
Что происходит, если пересечь многогранникплоскостью? Что получится в сечении? Какая линия образуется при пересечении поверхности многогранника с плоскостью?
При этом пересечением данной плоскости с каждой граньюмногогранника будет некоторый отрезок.
Выпуклыймногогранник называется правильным, если все его грани – равные правильные многоугольники и в каждой его вершине сходится одно и то же число рёбер. Выпуклыймногогранник правильным называют, Если все его грани собой представляют.
Также многогранник (трех и т. д.) может выглядеть призмой, если задать с вершиной, то как пирамида.
на шесть частей. Краткое графическое построение дано на рисунке 2, а: длинаотрезка дает сторону правильного шестиугольника вписанных в окружность круга с центром .
Искомое расстояние во всех задачах этой группы измеряется длинойотрезка, заключенного между заданными геометрическими фигурами и перпендикулярного к одной из них или одновременно к обеим.
Построить проекцию искомого отрезка на эту плоскость.
Итак, самосовмещение многогранника обязательно является поворотом вокруг оси, проходящей через центр многогранника. Эта ось пересекает наш многогранник в вершине или во внутренней точке ребра или грани. Следовательно, наше самосовмещение переводит в себя...
Что происходит, если пересечь многогранникплоскостью? Что получится в сечении? Какая линия образуется при пересечении поверхности многогранника с плоскостью?
При этом пересечением данной плоскости с каждой граньюмногогранника будет некоторый отрезок.
Выпуклыймногогранник называется правильным, если все его грани – равные правильные многоугольники и в каждой его вершине сходится одно и то же число рёбер. Выпуклыймногогранник правильным называют, Если все его грани собой представляют.
Также многогранник (трех и т. д.) может выглядеть призмой, если задать с вершиной, то как пирамида.
на шесть частей. Краткое графическое построение дано на рисунке 2, а: длинаотрезка дает сторону правильного шестиугольника вписанных в окружность круга с центром .
Искомое расстояние во всех задачах этой группы измеряется длинойотрезка, заключенного между заданными геометрическими фигурами и перпендикулярного к одной из них или одновременно к обеим.
Построить проекцию искомого отрезка на эту плоскость.