Оптимальное вращение 3D-модели для 2D-проекции - PullRequest
3 голосов
/ 03 июня 2010

Я ищу способ определения оптимального поворота X / Y / Z набора вершин для рендеринга (с использованием координат X / Y, игнорируя Z) на 2D-холсте.

У меня была пара идей, одна из которых была чисто грубой силой, включающей выполнение трехмерного цикла в диапазоне от 0..359 (с шагом 1 или более, в зависимости от требований к результатам / скорости) на съемочной площадке. вершин, измеряя разницу между минимальным и максимальным значениями по обеим осям X / Y, сохраняя самые высокие пары результатов / вращения и используя самую эффективную пару.

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

Используя вторую идею, возможно, используя первые, скажем, 3 итерации, сохраняя требуемый угол поворота и усредняя по 3, можно получить более точный результат, поскольку он учитывает не только один поворот, но и верхние 3 ' пар.

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

Ответы [ 2 ]

3 голосов
/ 04 июня 2010

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

Интуитивно, это находит ось, вокруг которой труднее всего вращать точки, то есть, вокруг которых вершины наиболее «разложены».

Без конкретного определения того, что вы считаете оптимальным, невозможно сказать, насколько хорошо работает этот метод. Тем не менее, он имеет несколько желательных свойств:

  • Если вершины копланарны, этот метод является оптимальным, поскольку он всегда выравнивает эту плоскость по плоскости x-y.

  • Если вершины расположены в прямоугольной рамке, кратчайший размер рамки выравнивается по оси Z.

РЕДАКТИРОВАТЬ: Вот более подробная информация о том, как реализовать этот подход.

Сначала назначьте массу каждой вершине. Я буду обсуждать варианты, как это сделать ниже. Затем вычислите центр масс вашего набора вершин. Затем переведите все свои вершины в -1 раз в центр масс, чтобы новый центр масс стал теперь (0,0,0).

Вычислить момент тензора инерции. Это матрица 3х3, элементы которой задаются формулами, которые можно найти в Википедии. Формулы зависят только от позиций вершин и от назначенных вами масс.

Теперь вам нужно диагонализировать тензор инерции. Поскольку он является симметричным положительно определенным, это можно сделать, найдя его собственные векторы и собственные значения. К сожалению, численные алгоритмы для их нахождения, как правило, сложны; самый прямой подход требует нахождения корней кубического многочлена. Однако нахождение собственных значений и собственных векторов матрицы является чрезвычайно распространенной проблемой, и любой пакет линейной алгебры, достойный его соли, будет поставляться с кодом, который может сделать это за вас (например, пакет линейной алгебры с открытым исходным кодом Eigen имеет SelfAdjointEigenSolver.) также можно найти более легкий код, специализированный для случая 3x3, в Интернете.

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

Теперь по поводу выбора массы. Самое простое, что нужно сделать, это дать всем вершинам массу 1. Если у вас есть только облако точек, это, вероятно, хорошее решение.

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

0 голосов
/ 04 июня 2010

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

В http://203.208.166.84/masudhasan/cgta_silhouette.pdf вы можете найти

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

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

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

Вы не указали приблизительное количество вершин. Но, как всегда, комбинаторное решение не рекомендуется для неограниченных (или больших) величин.

...