Полигональная математика

Question

Учитывая список точек, которые образуют простой 2-мерный многоугольник, ориентированный в трехмерном пространстве, и нормаль для этого многоугольника, какой хороший способ определить, какие точки являются конкретными «угловыми» точками?

Например, какая точка находится внизу слева, или внизу справа, или самой верхней точке? Многоугольник может быть ориентирован в любой трехмерной ориентации, поэтому я уверен, что мне нужно что-то сделать с нормальным, но у меня возникают проблемы с правильной математикой.

Спасибо!

Answer 1

Вам нужно больше информации, чтобы принять это решение. Множество (копланарных) точек и нормали недостаточно для того, чтобы дать вам представление о «нижнем левом» или «верхнем правом» или любой такой относительной идентификации.

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

1. Существует ли какая-либо другая информация в трехмерном мире, которую вы можете использовать для получения ссылки на систему координат?

2. Чего вы пытаетесь достичь, зная крайние углы формы?

Answer 2

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

Не забывайте, что хотя нормаль говорит вам, в какую сторону направлен многоугольник, она сама по себе не говорит, какой путь "вверх". Можно повернуть (или «повернуть») вокруг вектора нормали и все еще смотреть в том же направлении.

Именно поэтому большинство систем 3D-рендеринга имеют камеру, которая содержит не только вектор «обзора», но также «восходящий» и «правый» векторы. Изменения в последних двух достигают эффекта «прокручивания» камеры вокруг вектора обзора.

Answer 3

Возможный алгоритм будет

1. Найдите нормаль, которую вы можете сделать, используя перекрестное произведение векторов, соединяющих две пары разных углов

2. Создайте матрицу преобразования, чтобы повернуть многоугольник так, чтобы он был ровнее в пространстве XY (т. Е. Нормально выровнен по оси Z) * ​​1009 *

3. Рассчитать координаты ограничительной рамки или любого другого определения углов, которое вы используете (поскольку многоугольник теперь выровнен в 2D-пространстве, это значительно более простая задача)

4. Примените обратную матрицу преобразования, использованную на шаге 2, для преобразования этих координат обратно в трехмерное пространство.

Answer 4

Вы ищете ограничительную рамку?

Я не уверен, что нормальный имеет какое-либо отношение к тому, что вы спрашиваете.

Чтобы получить ограничивающий прямоугольник, оставьте 4 переменные: MinX, MaxX, MinY, MaxY

Затем выполните цикл по всем вашим точкам, проверив значения X для MaxX и MinX и значения Y для MaxY и MinY, обновив их при необходимости.

Когда цикл завершен, ваш блок определяется как MinX, MinY как верхний левый, MinX, MaxY как верхний правый и т. Д. ...

Ответ на ваш комментарий:

Если вы хотите свою коробку после проекции, вам нужно получить «преобразованные» очки. Затем примените ограничивающую рамку, как указано выше.

Преобразованный обычно подразумевает 2D-координаты экрана после проекции (рендеринга сцены), но это также может означать 2D-точки на любой плоскости, на которую вы проецировали.

Answer 5

Если вы знаете, что многоугольник в 3D является «плоским», вы можете использовать нормаль, чтобы преобразовать все 3D-точки вершин в 2D-представление (точек относительно плана, в котором расположен многоугольник) - но это все еще оставляет вас с определением источника этой системы координат (но это не имеет большого значения для вашей проблемы) и с ориентацией по крайней мере одной из осей (если вы хотите ортогональные оси, вы все равно можете вращать их вокруг Ваше выбранное происхождение) - и вот тут начинается беда. Я бы порекомендовал использовать ось Y вашей 3D-системы координат, спроецировать ее на плоскость и использовать результирующее направление как «вверх» - но тогда у вас возникнут проблемы, если ваш план будет ортогональн к оси Y (теперь вы возможно, вы захотите использовать проецируемую ось Z как "вверх").

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

Answer 6

Если вы можете предположить, что есть какие-то ограничения в отношении форм, то вам, возможно, удастся узнать меньше информации. Например, если ваша фигура была композицией небольшого квадрата с длинным тонким треугольником на одной стороне (то есть простой симметричной геометрией), то вы могли бы сравнить расстояние от каждой точки списка до «центра масс». Наибольшее расстояние будет идентифицировать конус конуса, второй по величине будет две точки, наиболее удаленные от конуса конуса и т. Д. Если бы в списке был какой-то порядок, точки вводятся в порядке против часовой стрелки (около нормальный), вы могли бы определить все точки. Это звучит как немного вычислений, поэтому может быть разумно попытаться включить некоторую дополнительную информацию в ваши фигуры, например, «центр масс» и контрольную точку, которая расположена «вверх» над COM (но не вдоль обычной ). Это даст вам вектор «вверх», который вы можете пересечь с нормалью, чтобы определить, например, некоторые координаты тела. Кроме того, нормаль может быть определена упорядочением списка точек. Если вы не можете предположить что-либо о формах (или даже если формы были симметричны, например), тогда вам потребуется больше данных. Это зависит от ваших ограничений.

Answer 7

У меня глупая идея, но, рискуя получить отрицательный балл, я попробую:

1. Получить минимальное / максимальное значение из каждая трехмерная ось каждого укажите на 2-й полигон. Достаточно одного прохода с циклом / итератором по списку значений для каждой точки, просто заменяя минимальные и максимальные значения по мере продвижения. Конечным результатом является список, который имеет «самые низкие» координаты X, Y, Z и «самые высокие» координаты X, Y, Z.
2. Итерация по этому списку мин / макс значения для создания каждой точки («угол») «ограничительной рамки» вокруг объекта. Результат должно быть поле, которое всегда содержит объект независимо от оси осмотрен или ориентация (нет смысла на многоугольник будет когда-либо превышать максимум или минимум вы собираете).
3. Тогда получи расстояние каждого "2д многоугольник »указывают на каждый угол расположение на «ограничительной рамке»; короче расстояние между точками, «ближе» он к этому «углу».

Далеко не оптимально, конечно, вялый, но, конечно, быстрый. Вы, вероятно, могли бы сделать это во время вращения объекта, просто посмотрев min / max каждого повернутого значения x / y / z и сохранив список этих значений заранее.

Answer 8

Спроецируйте его на плоскость и получите ограничивающий прямоугольник.