- Aslan
- Забанен
Aslan
> Вычислять пересечение секторов же просто
Не совсем понял о чем ты.
Вообще, объединение стен порталов которые смотрят в одинаковый сектор в один фрустум это необходимая мера и после объединения фрустум становится не выпуклым и с большим количеством стен. Если стены не объединять, тогда алгоритм зависает когда через один фрустум видно второй от того же сектора...и оба фрустума как видимые друг другу начинают добавлять друг друга в очередь обработки. Может быть попозже я попробую разобраться в этой проблеме
m210
Да,я неточно выразился. Фрустум в 2.5D - это сектор бесконечной окружности, а не сектор карты (область с постоянной высотой)
Портал же задается двумя точками: левый и правый край, так?
Фрустум - сектор бесконечной окружности с вершиной в игроке и крайними лучами, проходящими через края портала. Что же тт сложного построить пересечение?
Aslan
> Портал же задается двумя точками: левый и правый край, так?
Левый, правый, верхний, нижний - 4 плоскости дают фрустум.
Если бы я решал задачу в 2D, я бы и не создал эту тему.
>Что же тт сложного построить пересечение?
Ничего, в конце концов то, что ты спрашиваешь, все я описал в самом первом посте.
Раскрываю секрет фирмы, как делаются порталы.
Входные данные:
1) Портал определенный 3-мя или более точками.
2) Плоскости отсечения, извлеченные из PerspectiveView матрицы
3) Точка расположения камеры
Шаги:
1) Сортируем точки так, чтобы в массиве точки шли по порядку и соответствовали порядку граней
2) Боковыми плоскостями делаем отсечение граней портала. И на пересечении грани и боковой плоскости рождаем новые точки. В движке Q3 это делает функция ClipWindingEpsilon например. В результате получаем набор точек, а вместе с ним и новый набор усеченных граней портала.
3) Из граней полученных на пред. шаге делаем и точки камеры - делаем новые боковые плоскости отсечения (точка камеры + 2 точки грани = 3 точки, что есть достаточно для создания вектора плоскости)
4) Плоскость портала становится новой передней плоскостью отсечения, заднюю плоскость оставляем без изменений
5) Плоскостями из пунктов 3 и 4 отсекам объекты за порталом. При нахождении нового портала переходим к пункту 1
m210
>> Портал же задается двумя точками: левый и правый край, так?
> Левый, правый, верхний, нижний - 4 плоскости дают фрустум
Если две вертикальные и две горизонтальные плоскости, то опять сводится к 2D: брать min/max из dy/dx. Если же произвольные плоскости, то брать max left/ min right для каждой сканлинии, как в Лабиринтах Хулиона
Aslan
Я так до сих пор и не понимаю, как ты в 2D собрался отсекать точки, нахоядиещся выше или ниже камеры?
И видимо зря я скрываю картинки под спойлеры, их никто не видит :(
Вот типичное место с ограничением по видимости:
Вот так оно выглядит без текстур, где видно, какие сектора рисуются (за пределами видимости)
Вот таже самая картина в 2D, где четко видно, в в случае 2D в массив видимости попадет куча всего лишнего (и там могло быть еще пол-карты за кадром)
На втором скриншоте я выделил зеленым цветом предполагаемый AABB, который строится через первый портал, построенный портал выглядит как то так:
Ну и вид со стороны, где четко видно, куда направлены верхняя и нижняя граница фрустума
А вот тут тот же самый портал с другого ракурса, где видно проблему - в такой фрустум попадает слишком много лишнего, но тут уже ничего не поделаешь....хотя идеи все еще появляются, обычно упираюсь либо в дыры, либо в зависание алгоритма-обходчика стен.
Deamon
Спасибо за ответ, поизучаю немного, но я это все уже проделал, за исключением ближней и дальной плоскости - бесполезные абсолютно :)
Проблема то не в том, чтобы построить портал, а в том, чтобы соединить все стены смотрящие в один и тот же сектор в один фрустум (ну или несколько маленьких, если стены не имеют общей точки соединения)
Вот например как тут:
Камера смотрит в пол, находится в одном секторе, а все 4 стены, которые окружают сектор - смотрят в другой сектор
Вот так это выглядит сверху:
В этом случае - в 2D получается угол обзора 360 градусов, верхнюю и нижнюю плоскость тут невозможно построить впринципе...но если сделать из этих 4х стен AABB, после проверки все AABB соединяться в один большой AABB который будет имееть координаты 0,0,screenwidth, screenheight, и построенный через эти точки фрустум будет совпадать с фрустумом камеры...и генеально и просто :)
Т.е. во всем универсальный алгоритм, который имеет конскую погрешность в случаях, если смотреть на стены под углом
m210
Пирамида, с вершиной в камере и онованием в портале в проеции на горизонтальную и вертикальную плоскость - два луча, последнем случае брать min/max от к-та наклона луча dz/dx чтобы посчитать пересечение двух порталов или портала и камеры, камера тоже с вертикальной Oy и ограниченным наклоном, можно задать фрустум как портал
У меня же идея как рендерить рэйкастом
Aslan
> в проеции на горизонтальную и вертикальную плоскость - два луча, последнем
> случае брать min/max от к-та наклона луча dz/dx
Это надо обдумать, но опять же, в 3D нет вертикальной плоскости, там их как минимум две, и поэтому я и написал в самом первом посте - пока смотришь на такой фрустум на стену, которая идет вдоль оси X, то все нормально, а когда разворачиваешь камеру на стену вдоль Y, то все становится плохо. Можно попробовать брать вертикальную плоскость вдоль направлении камеры, но не знаю... Мне кажется, получится тоже самое, что и во всех 100 других попытках сделать правильно :)
Aslan
> меня же идея как рендерить рэйкастом
Это в 10 раз медленнее, проверено. Для более менее быстрого алгоритма, нужно сортировать точки стен по углу, т. е вызывать atan2, который писец какой медленный... Ну или без сортировки запускать 1000 лучей и получать явные дыры, потому что 1000 лучей не хватает тэи даже при этом количестве все тормозит))
m210
> Для более менее быстрого алгоритма, нужно сортировать точки стен по углу, т. е вызывать atan2, который писец какой медленный...
Для того, чтобы сортировать точки по углу, atan2 не нужен.
Даже без деления, в принципе, можно обойтись (правда, не факт, что будет быстрее).
}:+()___ [Smile]
> Даже без деления, в принципе, можно обойтись (правда, не факт, что будет
> быстрее).
Расскажи как, я проверю, быстрее или нет :)
Вот кусок кода рейкаста
Segment segment = segments.get(i);
segment.p1.angle = (float) Math.atan2((segment.p1.y - globalposy), (segment.p1.x - globalposx));
segment.p2.angle = (float) Math.atan2((segment.p2.y - globalposy), (segment.p2.x - globalposx));
double dAngle = (segment.p2.angle - segment.p1.angle);
if ((dAngle <= -(Math.PI)))
dAngle += (2 * Math.PI);
if ((dAngle > Math.PI))
dAngle -= (2 * Math.PI);
segment.p1.begin = (dAngle > 0.0);
segment.p2.begin = !(segment.p1.begin);Смысл такой, что по отсортированным точкам можно определить, какой сегмент перекрывает стоящий рядом при прохождении луча от 0 до 360 гр.
m210
> Расскажи как, я проверю, быстрее или нет :)
Сортировать \(x_i\in[0..1]\) — это то же самое, что сортировать \(\sqrt x_i\), \(x_i^2\), \(x_i^{3.21}\), \(\sin x_i\) и т. п.
Соответственно, atan2 можно заменить вычислительно более простой функцией, сортировка по которой которой даст тот же результат (хинт: отношение двух координат с подходящим знаком + номер квадранта). Более того, чтобы сравнить два угла, совершенно не обязательно эти углы находить, достаточно посмотреть знаки векторных произведений (избавляемся от делений ценой усложнения функции сравнения).
> if ((dAngle <= -(Math.PI))) dAngle += (2 * Math.PI);
Для операций с углами идеально подходит wrap-around арифметика целых чисел (uint32 и т. п.), не в курсе, есть ли в этом языке их поддержка.
m210
> Это в 10 раз медленнее, проверено. Для более менее быстрого алгоритма, нужно сортировать точки стен по углу, т. е вызывать atan2, который писец какой медленный...
это твоя реализация писец, вектора сравниваются псевдовекторным произведением
Чтобы утверждать что чтото в 10 раз медленнее, надо уметь нормально реализовать
> Расскажи как, я проверю, быстрее или нет :)
// Знак числа: // <0: -1 // 0: 0 //>0: 1 int sgn(float x) { return ( ( x>0)-( x<0)); } // нетранзитивное сравнение, не годится для сортировки // Пример: три точки в вершинах равностороннего треугольника с центром в нач коорд // каждый вектор левее соседа справа так по кругу int cmp1( const vec2& v1,const vec2& v2) { return sgn( v1.x*v2.y-v1.y*v2.x); } // транзитивное сравнение, годится для сортировки, возвращает знак, -1 - меньше,0-равно,1-больше // выбираем некоторый вектор v0, считаем те что слева от него < тех что справа // которые с одной стороны сравниваем по cmp1 int cmp2( const vec2& v1,const vec2& v2) { int l1=cmp1( v1,v0),l2=cmp1( v2,v0); if( l1!=l2) return sgn( l1-l2); return cmp1( v1,v2); }
UPD. Это для общего случая произвольных векторов,
НО тебе нужны лишь вершины, попадающие во фрустум, т.е. лежащие в секторе окружности с углом<180 с центром в камере, для них cmp1 транзитивно, всего 2 умножения на сравнение
> в 3D нет вертикальной плоскости, там их как минимум две
В Duke ограниченный наклон с искажением, скошенный фрустум, передняя грань и боковины остаются вертикальными
Aslan
> это твоя реализация писец, вектора сравниваются псевдовекторным произведением
> Чтобы утверждать что чтото в 10 раз медленнее, надо уметь нормально реализовать
Когда твой код будет выполняться за 0.1мс на Селероне, тогда и поговорим :)
Да и не знал, что топографическая сортировка может быть быстрее, чем пара операций cross и dot продуктов)))) Еще раз повторюсь, рейкаст не очень то подходит для определения видимости, есть более быстрые решения...в данном случае даже мое, которое умеет обрабатывать 10000 порталов за намного короткое время. И именно поэтому я использую рейкаст постобработкой, когда порталов становится 50-100, тогда рейкаст уже не несет такой ощутимой нагрузки.
Aslan
>В Duke ограниченный наклон с искажением, скошенный фрустум, передняя грань и боковины остаются вертикальными
Спасибо, я в курсе...но вот проблема - я пишу новый 3D рендер с freelookом, он 3D, у меня 3 плоскости а не 2 (наверно уже в 4й раз пишу) и мне абсолютно не важно, что там было реализовано в 90е....сейчас 2021год.
Но спасибо за методы, оставлю их на потом.
m210
> Когда твой код будет выполняться за 0.1мс на Селероне, тогда и поговорим :)
Рендер или что? 1000 fps крутовато даже для простой заливки экрана
У тебя портал - любая открытая линия между секторами?
Есть демка погонять?
> я пишу новый 3D рендер с freelookом
Честная проекция нарушает вертикальность порталов, но не влияет на их перекрытие, в результате пересечения двух проекций прямогольников - опять проекция прямоугольника, надо только разобраться с геометрией
Тема в архиве.