Planet_E (9 стр)

Neptune
> Треугольник НЕ виден, если все три его вершины НЕ видны.
Ты это серьёзно? :-D

SNVampyre
> Ты это серьёзно? :-D
Это я попытался упростить более неочевидную задачу о пересечении BBox-а и усечённой пирамиды камеры (видать перестарался:)). Где-то наткнулся на вполне приличную статью, в ней предлагали проверять все вершины бибокса на нахождение по внутреннюю сторону каждой из плоскостей камеры. Бибокс виден, если видна хотя бы одна его вершина, т.е. лежит по внутреннюю сторону каждой из плоскостей, и таким образом оказывается внутри пирамиды. Так вот это неправильно. Камера может смотреть в упор в одну из стенок бибокса, и при этом ни одна вершина не попадёт в пирамиду. Правильный алгоритм - от противного. Бибокс НЕ виден, если он весь целиком, т.е. все его 8 вершин, лежат по внешнюю сторону хотя бы одной из плоскостей пирамиды. Хотя в некоторых редких случаях это может давать ложные видимости, но зато не даёт ложных отсечений.

У меня треугольник виден, если видны все его три вершины. Если условие выполняется, он заносится в буфер-вектор. Отсечка такая, потому что проверяю видимость не на экране, а на прямоугольнике чуть меньше экрана.

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

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

Сейчас думаю, как более правильно определить видимость на экране.

PS Трансляция Z, X.

registr
> Сейчас думаю, как более правильно определить видимость на экране.
Что тут думать? Порезал по граням. Если после отсечения что-то осталось, то треугольник виден.

SNVampyre
> Порезал по граням. Если после отсечения что-то осталось, то треугольник виден.
Что значит порезать по граням? Неясно.

registr
> У меня треугольник виден, если видны все его три вершины.
Вот это неправильно. Что, если две вершины ушли за край экрана, а третья всё ещё видна? Часть треугольника-то будет видна. Не надо его обрезать, как предлагает SNVampyre (если я правильно понял), это пустая трата сил и производительности. Видюха успеет тасячу таких треугольников нарисовать, прежде чем ты посчитаешь новые вершины. Треугольник весь надлежит рисовать, если видна даже самая маленькая его часть.
registr
> Проблема кроется в том, что если очень близко приближаться к треугольнику, его
> вершины выйдут за экран, но он все равно будет виден.
Это и есть та ошибка, с которой я сам столкнулся. Решение уже описал. В твоём случае алгоритм такой: треугольник НЕ виден, если все три его вершины лежат по одну из границ экрана. Иначе заносим его в буфер.
Вообще, лучше проверяй видимость не в экранных координатах, а в мировых. Не надо каждый раз проектировать вершину на экран, чтобы определить её видимость, это медленно. Построй пирамиду камеры: ближняя плоскость отсечки, дальняя плоскость отсечки, и 4 боковые плоскости, расходящиеся веером из точки, в которой камера. Эти 6 плоскостей описываются вектором нормали n и параметром расстояния от начала координат d. Их можно вычислить из матрицы камеры (могу дать код), т.о. пирамида будет автомаически следовать за движением и поворотом камеры. Проверить, попала ли точка в пирамиду, просто: если она лежит по внутреннюю сторону всех 6 граней (т.е. dot(PointCoord, n) + d > 0), то точка внутри пирамиды и видна. Ну а для треугольника так: если все три вершины лежат по внешнюю сторону хотя бы одной грани, то треугольник НЕ виден. Можно сделать бесконечную камеру, игнорируя проверку с дальней плоскостью.
Такая проверка быстрее проекции на экран и отечения прямоугольником - всего-то три умножения и три сложения на вершину. Но всё равно, каждый треугольник отсекать на ЦПУ - это убийство возможностей современной видюхи. Если захочешь получить рельеф с детализацией 100к треугольников, получишь слайд-шоу. Отсекать по видимости нужно не каждый полигон, и здоровый массив полигонов (батч), прорисовывающий квадратный (или треугольный в твоём случае) кусок поверхности. Динамически строить вершинный буфер тоже не надо, каждый батч имеет свой статический буфер, созданный один раз.

registr
> На первом этапе я определяю лицевую сторону сферы (как лицевая сторона Луны.)
Тоже не правильно. А если за краем планеты будет торчать высокая гора? Она тогда тоже отсечётся. Вон сейчас у тебя заметно, как исчезают треугольники на краю сферы, которые должны быть ещё видны. А что будет, если приземлиться и посмотреть вдоль горизонта? Отсекать надо треугольники, все три вершины которых спрятались за сферой планеты (если рельеф имеет неотрицательную высоту, отсчитываемую от радиуса планеты). Тут код посложнее, но его можно "сообразить", нарисовав всё на бумажке, простая векторная геометрия. Могу поделиться:)

Neptune
> Не надо его обрезать, как предлагает SNVampyre (если я правильно понял), это
> пустая трата сил и производительности.
Ну если стоит такая задача, то именно так и надо. Например, если это квад портала. Процессор легко справится с парой тысяч порталов в кадре.
А треугольники, которые рисуются, конечно не надо резать, достаточно теста по сфере, описывающей модель или её кусок.

registr
> Что значит порезать по граням? Неясно.
Может тебе тогда рановато делать движок? :)

Neptune
> > У меня треугольник виден, если видны все его три вершины.
Это я глюканул, треугольник виден, если видна хотя бы одна его вершина. Ну да ладно.

Neptune
> Построй пирамиду камеры: ближняя плоскость отсечки, дальняя плоскость отсечки,
> и 4 боковые плоскости, расходящиеся веером из точки, в которой камера.
Это есть объем наблюдения с помощью плоскостей отсечения. Мне непонятно следующее: как задавать заднюю плоскость отсечки. Допустим, я задаю ее так, что она проходит через центр сферы и отсекает ее вторую нелицевую половину. Но если скажем я буду приближаться, то и плоскость отсечки должна ко мне приближаться. Если я приземляюсь как у тебя, плоскость отсечки опять должна изменяться.

SNVampyre
> Может тебе тогда рановато делать движок? :)
Может быть, а может и не быть :)

Neptune
Не проще ли создать буфер выбора, задать точку в центре экрана и ее окрестности равные половине высоты и половине ширины экрана. В буфер выбора попадут все треугольники в проекции, независемо как расположены их вершины. Только вот я не знаю, проверяет ли "выбор" глубину. Если да, то в буфер будут заноситься только видимые треугольники.

registr
> Мне непонятно следующее: как задавать заднюю плоскость отсечки. Допустим, я
> задаю ее так, что она проходит через центр сферы и отсекает ее вторую нелицевую
> половину. Но если скажем я буду приближаться, то и плоскость отсечки должна ко
> мне приближаться. Если я приземляюсь как у тебя, плоскость отсечки опять должна
> изменяться.
На заднюю плоскость вообще забей. Не надо ею отсекать планету, правильного отсечения никогда не получится. Треугольники за горизонтом отсекай сферой планеты, как я описал в посте 125.

registr
> Не проще ли создать буфер выбора, задать точку в центре экрана и ее окрестности
> равные половине высоты и половине ширины экрана. В буфер выбора попадут все
> треугольники в проекции, независемо как расположены их вершины. Только вот я не
> знаю, проверяет ли "выбор" глубину. Если да, то в буфер будут заноситься только
> видимые треугольники.
Т.е. ты хочешь сначала нарисовать абсолютно все треугольники, получить список видимых, и потом нарисовать только их? О_о

Помню обещал сравнить разные методы сегментации сферы на основе икосаэдра, так вот - выполняю обещание )

Оценки качества - чем меньше - тем лучше.
По отношению максимальной длины хорды сегмента к минимальной на разных уровнях сегментации:

По отношению максимального периметра сегмента к минимальному на разных уровнях сегментации:

По отношению максимальной площади сегмента к минимальной на разных уровнях сегментации:

В ходе экспериментов без специальных оптимизаций среднее время вычисления координат узла для ISG-метода сегментации составило 0.0076 мс., для прямого метода сегментации по граням икосаэдра – 0.0033 мс., для итеративного метода сегментации – 0.5731 мс.

ПС. ISG-метод основан на особой сегментной системе координат и является прямым, подробности в докладе: M.L. Grishin. The direct method of the sphere segmenting at 3d-modeling of the Earth surface. / 4th International Conference Earth From Space: The Most effective Solutions. Abstracts. 2009. – P. 109-110. – ISBN 978-5-9518-0378-8.

Напиши подробную статью про метод ISG, найти сборник трудов конференции часто практически невозможно.

Линк на тезисы: http://arts-union.ru/articles/altmer/tesys_en.htm

Статью как-нибудь позже напишу.

А что это за алгоритм ISG? Построение геосферы нерекурсивным методом?

Да, рекурсия не требуется, ни в явном, ни в скрытом в численных методах виде.