Cвободно летающая камера в 3D (OpenGL - EGL, Delphi XE7) , пишу кросс-платформенную графическую библиотеку

[Славян]

Цитата Pavia @ 08.04.15, 14:30

По поводу приближения. Достаточно разбить эллипс на 16 максимум 32 сегмента. Этого хватит что-бы его линеаризовать. С точностью допустимой для вывода на экран с разрешением 1000 точек.
А далее обычным кроссом вычислять.

Рассмотрим, как обычно, самый мерзкий случай: пусть 'рисуем' эллипс 1000*20, а тогда на нижнюю дугу уйдёт 16 сегментов, на половину её - 8 сегментов. Итак, 500*10 приближено 8 сегментами. Представьте какое грубое будет приближение у самой интересной части, у острого разворота!! Впрочем, надо как-то понять вашу фразу "обычным кроссом".
Да и вообще, опираться на экран - плохое решение. Ну вот захотела Татьяна сверхузкий эллипс приблизить ломаной из 20 звеньев. Что ей делать, где=какие узлы выбрать?

[OpenGL]

Цитата Славян @ 08.04.15, 13:46

А вот найти где должны располагаться узлы разбиения, дабы приближение было наиболее точным - вообще неочевидная задача (для меня - точно).

Как понять "наиболее точным"?

Добавлено 08.04.15, 15:56

Цитата Славян @ 08.04.15, 13:46

Разбивать по углам вообще плохо.

Нормально. Углы же не обязательно равными должны быть

[Славян]

Предлагаю рассмотреть вопрос наилучшего приближения чуть подробнее и наглядее. Это, конечно, скорее раздел Алгоритмов, нежели Графики, но всё же близкая и связанная тема:
1.Пусть Таня захотела узкий эллипс разбить на 5;7;... - нечётное число частей.

Прикреплённая картинка

2.Поступив по-простому, начали делить по 72 градуса, с точки (1;0) как в школьной математике:

Прикреплённая картинка

(Рисовал от руки, поэтому чуть-чуть неточно, но вся суть передана.) Как видим, левый конец так сильно отрезался, что он даст самую большую ошибку при расчёте приближения. А при рисовании пропадёт 'угадайка', что это узкий эллипс.
3.А вот примерно так выглядела бы наилучшая аппроксимация нашего объекта:

Прикреплённая картинка

Т.е. мы потратили 2 узла, но поставили их не в самых трудных зонах, а чуть сместив, не давая погрешностям и на длинных кусках вырасти большими! Но как, как угадать = рассчитать, где ставить эти лучшие узлы - не соображу.
Мораль: проблема есть, и она не малая! Это тоже может быть причиной, что GLU-функция gluCylinder имеется, а вот gluEllipticCylinder - нету.

Добавлено 08.04.15, 16:32

Цитата OpenGL @ 08.04.15, 15:55

Как понять "наиболее точным"?

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

Добавлено 08.04.15, 16:37

Цитата OpenGL @ 08.04.15, 15:55

Нормально. Углы же не обязательно равными должны быть

Согласен. Просто "равные углы" сразу пришли в голову. Виноват-с.

[amk]

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

[Славян]

Цитата amk @ 08.04.15, 17:16

Оптимальное по разности площадей...

А значит я напрасно попёрся в площади. Надо было продолжать гнуть линию про приближение контура.

Добавлено 08.04.15, 17:36

Цитата amk @ 08.04.15, 17:16

слишком грубое разбиение

Ну, во-первых, это для наглядности, а, во-вторых, всякое N могут задать и надо иметь возможность строить заданное.

[Блекморша Таня]

OpenGL, Pavia, Славян
Предлагаю внимательно посмотреть текст функции (надеюсь, Delphi-синтаксис для всех читаем?).
В доработанном примере я строю "единичную окружность" (с радиусом =1), разбиваю 2*Pi на заданное число частей, получаю дискрет угла. Отрезки, на которые делится окружность - равны, координаты каждой точки окружности = нормали к текущему сегменту цилиндра.
Эллипсом окружность становится в момент вывода, после glScale, предпочитаю вместо расчетов на CPU изменять своевременно матрицу GPU.
Напомню, линейные преобразования не в силах изменить относительные длины отрезков, эллипс разбит на отрезки равной длины.
То же и с нормалями, они пересчитываются верно, нормализованы, glEnable(GL_NORMALIZE) не забыт.

Уж решите сами, кого из Вас послать к Краснову, кого к NeHe, кого в красную книгу. Намекаю, учебник геометрии за 8-й класс - must have, RFM.



На картинке: 2 наших новых товарища, слева БиКонус, 8 граней, рекомендую. Он почти как цилиндр строится, только нормали к граням считаю через касательную.
Справа Тетраедр (Tetrahedron). Он кажется хилее, но у него есть хорошие знакомые: Октаэдр, Икосаэдр и Додекаэдр.

Сообщение отредактировано: Блекморша Таня - 08.04.15, 18:52

[Славян]

Цитата Блекморша Таня @ 08.04.15, 18:04

Напомню, линейные преобразования не в силах изменить относительные длины отрезков, эллипс разбит на отрезки равной длины.

Неплохое напоминание, но с площадями как раз всё неплохо, а вот длины начинают плясать. Сжав окружность в два раза вдоль OY трудно понять, какой стала её длина!

Добавлено 08.04.15, 18:47

Цитата Блекморша Таня @ 08.04.15, 18:04

линейные преобразования не в силах изменить относительные длины отрезков

Очень простой наглядный пример такой: рассмотрите равносторонний треугольник на корнях 3 степени из 1. Сожмите всё вдоль оси OX в 2 раза. Удивитесь, что раньше длины отрезков относились как 1:1, а сейчас стали плясать.

[amk]

Цитата Славян @ 08.04.15, 17:33

А значит я напрасно попёрся в площади. Надо было продолжать гнуть линию про приближение контура.

Я проверял только три аппроксимации:

1. узлы равномерно распределены по длине кривой - очень плохо аппроксимирует места изгибов;
2. минимальная площадью между кривыми - описанный метод сжатия окружности - хорошо аппроксимирует места изгибов и прост в реализации, дальше используется для сравнений;
3. касательная в каждом узле параллельна хорде, соединяющей соседние с этим узлом узлы - результат тождественен предыдущему;
   На ум приходят ещё два варианта:
4. высота стрелок прогиба всех дуг одинакова - должен давать чуть лучшее приближение в местах изгибов, совсем незначительно ухудшая в остальных местах;
5. минимально максимальное отклонение точек кривой от аппроксимации - результат практически идентичен предыдущему, но сложнее с точки реализации алгоритма.
6. минимален интеграл вдоль кривой квадрата расстояния до ближайшей точки аппроксимации - должен несколько хуже аппроксимировать изгибы, улучшая аппроксимацию участков с малым изгибом.

Если задана максимальная стрелка прогиба, можно просто строить
Если не гнаться за минимальным числом

Сообщение отредактировано: OpenGL - 09.04.15, 03:47

[Блекморша Таня]

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

[amk]

Цитата Блекморша Таня @ 08.04.15, 18:04

Эллипсом окружность становится в момент вывода, после glScale, предпочитаю вместо расчетов на CPU изменять своевременно матрицу GPU.
Напомню, линейные преобразования не в силах изменить относительные длины отрезков, эллипс разбит на отрезки равной длины.

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

Кстати, нормали в OpenGL пересчитываются по матрице, отличающейся от матрице пересчёта координат (они получаются друг из друга не очень сложным алгоритмом) поэтому остаются правильными нормалями.

[Славян]

Цитата Блекморша Таня @ 08.04.15, 19:20

Не могу понять, от чего у Вас окружность так сжимается?

Вы же сами написали, что бедете строить=триангулировать разные поверхности. Я рассмотрел частный, но довольно интересный случай: цилиндр, у которого в основании - эллипс. Вам надо будет понять куда ставить узлы, а оказывается задача сия - сложная. Но если вы будете просто повторять всё то, что сделано в OpenGL, то конечно все мои предложения вам - пустые=напрасны.

Добавлено 08.04.15, 19:44

Цитата amk @ 08.04.15, 19:19

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

Оно! В идеале, лучше без квадрата.

Добавлено 08.04.15, 19:45

Цитата Славян @ 08.04.15, 19:39

лучше без квадрата

Но, само собой, по модулю.

Добавлено 08.04.15, 19:47

Цитата Славян @ 08.04.15, 19:39

Но, само собой, по модулю.

Тьфу, расстояние это и есть разность по модулю.

[amk]

Цитата Славян @ 08.04.15, 19:39

Оно! В идеале, лучше без квадрата.

Цитата Славян @ 08.04.15, 19:39

Но, само собой, по модулю.

Этот вариант практически не отличается от аппроксимации круга многоугольником с последующим сжатием/растяжением.

[Блекморша Таня]

На фото, слева-направо: Тетраэдр (Tetrahedron), Октаэдр (Octahedron), Икосаэдр (Icosahedron), Додекаэдр (Dodecahedron).
Их товарищ Гексаэдр (Hexahedron), по кличке Куб (Cube) на подходе. Он то у меня есть, но его построение я хочу органично вписать в структуру семейства правильных многогранников (Polyhedron), чтобы строились они одной функцией, как можно проще, быстрее и понятнее.

Кстати, про движок форума и полезные клавиатурные комбинации. Если вы видите надпись "[+] Скрытый текст" ниже, нажмите быстро Alt-F4 3 раза, надпись исчезнет.

Скрытый текст

Я трепетно отношусь к построению правильных многогранников, ведь до меня этим занимались Платон и Кеплер, например ontologicheskie-progulki.
Говорят, через эти построения можно познать структуру вселенной, а также сдать экзамен по геометрии.

Я решила демки пока выкладывать только под Win, ввиду отсутствия у читателей темы планшетов и смартфонов под Android (!? ёпрст). Если у кого есть мобильные устройства - напишите, начну публиковать apk снова.
В демке фигуры анимированы, забавно вращаются по 3-м осям. Бегать там можно, только на крокодила не наступайте. Цифры слева верху - FPS и прочее, о них уже писала выше. Кнопки справа - это для планшета, но и под Win они работают.
Мне не нравится идея единой концепции интерфейса приложения под мышь/клавиатуру и тачскрин. Я бы лучше разделила, на планшете Gesture будет правильнее для управления.
MC for Windows: mc.zip 1.9 MB https://yadi.sk/d/tBKQxaV7ff8KW

Сообщение отредактировано: Блекморша Таня - 09.04.15, 16:58

[Славян]

Нам следует ожидать построения полуправильных?

[Блекморша Таня]

Pavia

Цитата

По поводу приближения. Достаточно разбить эллипс на 16 максимум 32 сегмента. Этого хватит что-бы его линеаризовать. С точностью допустимой для вывода на экран с разрешением 1000 точек.
А далее обычным кроссом вычислять.

Это Вы точно заметили - я решаю практическую задачу построения набора 3D примитивов и вывода их на экран. Мои условия таковы, что готовых библиотек либо нет, либо меня не устраивают, а доступные примеры сложнее перевести чем написать заново. Обсуждаемая здесь кое-кем задача "точной аппроксимации криволинейных поверхностей" - совсем мимо темы.
Поэтому для цилиндра (который иногда может и быть эллипическим, если задано) я закладываю единственный параметр - число разбиений по углу. В простых примерах, что были на картинках у цилиндра 32 сегмента. На практике, я планирую вычислять видимый размер объекта на экране, и в зависимости от этого его детализировать. Число разбиений выражу функцией от размера грани на экране. Скажем так, у далеких цилиндрических объектов число разбиений будет всего 4/6, у ближних порядка 16/32, а те к которым приблизились вплотную носом - порядка 128/512. Задача формулируется так: минимизировать число трианглов отображаемых на экране в сцене, при этом детализировать отрисовку ближних объектов на уровне построения примитивов.
Кросс (Cross, векторное произведение) я использую для расчета нормалей вертексов. Но для цилиндра в процессе его построения по моему алгоритму у меня уже есть готовая нормаль, её не нужно вычислять дополнительно.
***
Практика - критерий истины. Пишите еще.