Потеря точности координатных значений вертексов при вращении

[Qlin]

Ну хорошо, пусть у нас есть 3D-редактор, а в нем создан куб с целочисленными координатами. Существуют ось и такой угол, что если данный объект провращать на него, координаты должны стать иррациональными. Однако любой стандартный 3D-софт не допускает ни иррациональности, ни вообще бесконечных дробей. Выход из затруднительной ситуации видится в том, что когда невозможно получить точное число, берется его приближенное значение, но тут возникает следующая подпроблема. Широко известна ошибка, когда у некоторого полигона с числом сторон более $3$ не все вертексы оказываются лежащими в одной плоскости. Она может возникать по разным причинам (в частности, когда 3д-моделлер взялся прописывать все координаты вручную, и прописал их неверно). Но если приближать координатные значения после вращения, эта ошибка всплывет неизбежно. Выход видится в том, чтобы разбивать всё на треугольники. Эффект от этого разбиения ожидается следующий: мы хотим, чтоб наблюдатель после вращения видел невооруженным глазом ровный полигон, а на самом деле составляющие его треугольники попадут не в одну, а немножко разные плоскости. Но вращая раз за разом данную конструкцию мы все более проигрываем в точности, и изначально ровные полигоны после нескольких итераций могут легко оказаться сложенными в бумажный самолетик. Здесь же по соседству должны жить и ошибки освещения, когда при определенном расположении источников и интенсивности может проступить треугольная сущность "ровных" граней геометрических объектов.

А как во всех этих 3дс_максах, SketchUp'ах и прочих 3д редакторах решены данные проблемы? Есть версии? Есть методики? Есть идеи?

[rockclimber]

Элементарно, Ватсон. Вместо вычисления $(a + b) + c$ вычисляйте $a + (b + c)$. Думаю, очевидно, что $a$ здесь - начальное положение, а $b$ и $c$ - повороты.

[arseniiv]

Qlin в сообщении #1319662 писал(а):

Но вращая раз за разом данную конструкцию мы все более проигрываем в точности

Это устраняется хранением оригинальных координат отдельно от текущего применённого преобразования. Если поворачивается некоторый подобъект, бывает так, что для него хранится своё собственное преобразование, отдельное от глобального (и вообще для каждого объекта; в двумерной векторной графике такой подход тоже нередок из-за плюсиков модульности).

Qlin в сообщении #1319662 писал(а):

Здесь же по соседству должны жить и ошибки освещения, когда при определенном расположении источников и интенсивности может проступить треугольная сущность "ровных" граней геометрических объектов.

Только при простейших алгоритмах освещения.

Qlin в сообщении #1319662 писал(а):

А как во всех этих 3дс_максах, SketchUp'ах и прочих 3д редакторах решены данные проблемы? Есть версии? Есть методики? Есть идеи?

Есть идея: посмотрите код опенсорсных из них (Blender?). Вряд ли тут есть те, кто знаком с их кодом заранее, так что это в любом случае кому-то придётся делать.

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

-- Чт июн 14, 2018 01:24:37 --

rockclimber в сообщении #1319669 писал(а):

вычисляйте $a + (b + c)$. Думаю, очевидно, что $a$ здесь - начальное положение, а $b$ и $c$ - повороты

Тут, кстати, может поступить возражение «тогда мы получим когда-нибудь оператор, который не просто поворачивает, а ещё и растягивает и т. п.», так что сразу ответим и на него: если, например, использовать кватернионы, можно исправлять накапливающуюся ошибку их нормированием (конечно, часть её останется, но зато мы просто физически не сможем провести неортогональное преобразование, хотя и не совсем то); так как у них есть и другие полезные свойства, обычно оперируют как раз ими, переводя в матрицы лишь в некоторых случаях.

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

[rockclimber]

arseniiv в сообщении #1319670 писал(а):

Тут, кстати, может поступить возражение «тогда мы получим когда-нибудь оператор, который не просто поворачивает, а ещё и растягивает и т. п.»

Сначала надо определить "источник" операторов. Если взять типовой кейс использования 3Д-редакторов и игр ("инициировали" объект с точными координатами, а потом как-то крутили его руками с помощью манипулятора "мышь") и вспомнить, насколько порядков точность позиционирования мыши мышцами руки отстает от точности вычислений с плавающей точкой, то может оказаться, что проблемы-то и нет.

[arseniiv]

Да, ещё и это.

[Pavia]

Qlin

Qlin в сообщении #1319662 писал(а):

Но если приближать координатные значения после вращения, эта ошибка всплывет неизбежно.

Два раза сближать. С начало по одной оси потом по другой.

Qlin в сообщении #1319662 писал(а):

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

Смысла нету. Ну лежат они в разных плоскостях, и что с того? Какие алгоритмы от этого пострадают?

Qlin в сообщении #1319662 писал(а):

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

В большинстве случаев наблюдатель будет видеть ровный полигон. Ошибка у вас в расчётах 0,0005 а на экране выводится условная условная 1 или 0,5. Так вот даже если увеличить масштаб, то он не увидит разницы. Просто потому что не будет объектов относительно которых он мог бы сравнить.
А если это циклический процесс. То просто хранят начальные значения и каждый период начинают с них.

Qlin в сообщении #1319662 писал(а):

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

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

Qlin в сообщении #1319662 писал(а):

Здесь же по соседству должны жить и ошибки освещения, когда при определенном расположении источников и интенсивности может проступить треугольная сущность "ровных" граней геометрических объектов.

Есть такие. После всех вращений считают освещение. Рассчитывают нормали от соседних полигонов, а после усредняют.

[Dmitriy40]

Мне кажется эта проблема лишь следствие гораздо более общей: конечной точности представления вещественных чисел. И единым универсальным методом её не вылечить. Для каждого оператора (вращение, сдвиг, масштабирование, расчёт освещения, и т.д.) решение может быть своим, обеспечивающим достаточную на практике точность. Не идеальную. Но достаточную. Появится у вас задача где не хватит double точности чисел - можно перейти на учетверённую точность, на стократную, на любую достаточную.
В конце концов даже банально точно сложить несколько вещественных чисел в общем случае невозможно, для такого банального действия придумывали специальные алгоритмы компенсации погрешностей.
В общем универсального метода нет (кроме повышения разрядности представления чисел вплоть до бесконечности), но для каждого преобразования можно подобрать достаточно на практике точный алгоритм.

[sergey83]

А я знаю эту проблему. Только в моем случае она выглядела не так.
Рассказываю. Есть в CAD системах такой объект как группа, ну или блок. Он задается матрицей. Причем не обычной матрицей, а ортогональной, но не ортонормированной. А у ортогональной матрицы легко найти обратную матрицу - транспонированием.
Т.е. при вещественных операциях, поворотах, растяжениях и т.п. нужно, чтобы эта матрица опорных векторов оставалась ортогональной.
Там точность порядка $10^{-7}$
Так вот, накапливается вычислительная ошибка и матрица перестает быть ортогональной. Если в функцию отправить неортогональную матрицу, то будет ошибка.
А что мы, программисты, делаем? А мы тупо подравниваем матрицу. Есть же ортогонализация матрицы по Грамму ― Шмидту.

[arseniiv]

Может статься, что вы делаете что-то не так.

sergey83 в сообщении #1321013 писал(а):

Причем не обычной матрицей, а ортогональной, но не ортонормированной.

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

[arseniiv]

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