В данной работе рассмотрена задача поиска минимального расстояния между многогранником и точкой, не лежащей внутри него. Предложен алгоритм решения этой задачи и способ его применения в 3D-моделировании.

Ключевые слова: многогранник, расстояние, алгоритм .

Введение

При реализации метода 3D-моделирования Ray Marching необходимым является определение минимального расстояния от некоторой точки до трехмерного объекта [1]. В данной статье предлагается алгоритм поиска такого расстояния от точки до выпуклого многогранника.

Математическая постановка задачи

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

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

Обозначения, используемые в статье

и — точка вне многогранника и многогранник соответственно, между которыми определяется минимальное расстояние;

— плоскость, содержащая произвольные точки , не лежащие на одной прямой;

— расстояние между объектами и , каждый из которых может быть точкой, прямой или плоскостью;

— минимальное расстояние между точкой и выпуклым многогранником ;

, , — координаты точки по осям , , соответственно.

Алгоритм решения

Определим, какие из вершин многогранника являются тремя ближайшими к и назовем их так, что

Проверим выполнение следующего условия:

1. Проекция точки на находится внутри треугольника или на его границе

Рис. 1.

Пусть — проекция на плоскость (рис. 1). Если она находится внутри треугольника или на его границе, то выполнено равенство: (см. доказательство Теоремы 1). Для того, чтобы проверить выполнение этого условия, находим координаты точки .

Зная координаты точек , составляем уравнение плоскости и определяем координаты вектора нормали к ней. Используя координаты точки и координаты направляющего вектора прямой (являющегося вектором нормали ) составляем каноническое уравнение прямой . Зная его и уравнение плоскости определяем координаты точки , которая является точкой пересечения прямой и . Далее проверяем принадлежность точки треугольнику . Метод проверки описан в статье [2]. При выполнении данного условия . Находим его как расстояние между двумя точками в пространстве.

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

2. Проекция точки на прямую принадлежит отрезку

Рис. 2.

Пусть — проекция на прямую (рис. 2). Если принадлежит отрезку , то выполнено равенство: (см. доказательство Теоремы 2). Для проверки выполнения этого условия находим координаты точки .

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

Если выполнена система неравенств: , то принадлежит отрезку .

При выполнении данного условия . Находим его как расстояние между двумя точками в пространстве.

При невыполнении пунктов 1 и 2 (рис. 3) задача сводится к поиску расстояния между и , поскольку расстояние от до не является ни расстоянием от до ближайшей грани , ни расстоянием от до ближайшего ребра .

Рис. 3.

Для проверки корректности данного алгоритма рассмотрим следующие теоремы.

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

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

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

Пусть находится вне треугольника . Следовательно, находится вне грани, которой принадлежит этот треугольник. Эта грань — единственная, принадлежащая плоскости , поскольку многогранник выпуклый. Поэтому не принадлежит многограннику, следовательно, отрезок не является минимальным расстоянием от до многогранника.

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

Доказательство. Пусть — ближайшие к вершины многогранника , при этом ; — прямая, содержащая отрезок ; — проекция точки на ; — проекция точки на .

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

Пусть принадлежит отрезку , совпадает с . В этом случае по теореме 1 минимальное расстояние от до многогранника есть . Поскольку совпадает с , является минимальным расстоянием от до многогранника.

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

Применение данного алгоритма

Ray Marching — одна из относительно новых технологий, используемых для рендеринга трехмерных сцен. При ее реализации для рендеринга непрозрачных объектов можно использовать поля расстояний со знаком, что позволит оптимизировать вычислительный процесс. Поле расстояния — это функция, определяющая расстояние от точки до поверхности объекта [3]. Вышеописанный метод может быть использован для определения минимальных расстояний до любых выпуклых многогранников.

Литература:

1. Ray Marching Distance Fields in Real-time on WebGL. — Текст: электронный // semanticscholar: [сайт]. — URL: https://pdfs.semanticscholar.org/a964/750aa212bd490d258221bc9756e7e58c5317.pdf (дата обращения: 18.07.2020).
2. Weisstein, Eric W. Triangle Interior. — Текст: электронный // mathworld: [сайт]. — URL: https://mathworld.wolfram.com/TriangleInterior.html (дата обращения: 18.07.2020).
3. GPU Ray Marching of Distance Fields / J. T. Lukasz. — Текст: электронный // DTU.compute: [сайт]. — URL: http://www2.imm.dtu.dk/pubdb/edoc/imm6392.pdf (дата обращения: 19.07.2020).