Передняя плоскость отсечения

Добрый день. Я занимаюсь софтваре рендерингом- то есть без OpenGL/DirectX растеризую треугольники софтваре. Я использую следующий алгоритм отсечения по передней плоскости. Но в этом случае есть недочет- треугольники пропадают по сторонам и вверху- внизу, то есть способ грубый, просто если одна из вершин треугольника за передней плоскостью, а не перед, значит дистанция до плоскости от вершины отрицательная, если отрицательная дистанция хотя бы у одной вершины- пропустить не рисовать весь треугольник. А как на самом деле более элегантно это решить? Как например в Quake 1 source code кто смотрел? Так что бы без математических наворотов просто и элегантно было. Как правильно реализовать отсечение по передней плоскости?
Заранее спасибо.

Нужно отсекать только если все вершины за плоскостью. Когда ты проецируешь вершины, то есть умножаешь на матрицу поворота и матрицу проекции, у тебя должна получиться вершина в пространстве пирамиды отсечения, где x,y,z - в пределах [-1..1], для z [0..1]
В этом случае для каждой вершины ставишь флаги по какой оси они не попадают в диапазон ( 1+2 - x;  4+8 - y; 16+32 - z). Когда вопрос доходит до растеризации треугольников - сверяешь эти флаги. Если треугольник частично заходит за переднюю или какую либо другую грань отсечения, решаешь это на пиксельном уровне во время отрисовки.

Базовое условие "flag1 & flag2 & flag3 == 0" скажет что треугольник не отсекается одной плоскость.

SmoothBoy
> Как например в Quake 1 source code кто смотрел?
Смотрел очень давно, могу ошибиться, насколько помню там сам треугольник режется так - чтобы попадать полностью на экран. Если не путаю с порталами. От треугольника может остаться полигон, который дальше делиться на треугольники в одной плоскости, по мере нахождения отсечений.

Каждый раз когда ты режешь одной из 6 плоскостей треугольник, у тебя на выходе получиться 1-2 новых треугольника, с которыми ты продолжаешь тоже действие с оставшимися плоскостями. В пространстве "пирамиды отсечения" математика отсечения будет выглядеть упрощенной (по крайней мере при выводе формул можно многое сократить), поскольку каждая из плоскостей параллельна осям.

И да, с начало отсекаешь переднюю и дальнюю плоскости, а потом делишь на Z, чтобы отсечь уже боковые, иначе будут искажения.

Я смотрел доку по BSP OpenGL Doc , но нас сейчас BSP не интересует а интересует одна функция из этого мануала, функция

void Split_Polygon (polygon *poly, plane *part, polygon *&front, polygon *&back);

Подойдет она для этой цели? Делить полигоны на части передней плоскостью отсечения подойдет?

SmoothBoy
> Как правильно реализовать отсечение по передней плоскости?
Я когда-то делал так:

Треугольников на выходе может получиться больше одного (очевидно).
Вершины на входе должны быть после трансформации, но до деления на w (деление произойдет в конце функции).
По сути это https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm

Спасибо огромное.

SmoothBoy
> Я смотрел доку по BSP
Причем тут BSP мне не понять. Все гораздо проще.

SmoothBoy
> Делить полигоны на части передней плоскостью отсечения подойдет?
В данном случае деление треугольника плоскостью, которое тривиально до нельзя. Где по условию если отсекается две вершины - на выходе 1 треугольник, если 1 вершина - тогда добавляется еще одна вершина и в результате имеем 2 треугольника. В обоих случаях нужно посчитать 2 раза пересечение плоскости с прямой, которая по факту является началом координат по Z.

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

d = z1/(z1-z2);
x2 = lerp(x1,x2,d); // x2 = (x2-x1)*d + x1;
y2 = lerp(y1,y2,d); // y2 = (y2-y1)*d + y1;
z2 = 0;

аналогично

vec2 = lerp(vec1, vec2, vec1.z/(vec1.z-vec2.z));

Конечно ты можешь делать все так как тебе лично удобнее и понятнее.

Спасибо foxes, я нашел функцию деления треугольника плоскостью в доке по BSP поэтому и вспомнил, а так BSP тут ясно ни причем. :-) А вот эти формулы что вы описали на какой стадии их использовать? В том смысле что в экранных координатах, или после умножения на mxView * mxProj?

SmoothBoy
Для отсечения по прямоугольнику экрана: Weiler–Atherton polygon clipping algorithm не создает промежуточных вершин, которые могут быть затем отсечены
Каждая из 6 плоскостей отсечения (near, far и по 4м сторонам экрана) может добавить максимум 1 вершину, т.е. из 3угольника получится максимум выпуклый 9угольник (даже меньше, но лень разбираться), который легко триангулировать как фан (012,023,034 итд)

SmoothBoy
> В том смысле что в экранных координатах, или после умножения на mxView *
> mxProj?
Разницы нет (хотя экранные координаты это mxModel * mxView). Полноценно и проще делать после умножения на mxModel * mxView * mxProj, до деления на Z или W. Но это только для дальней и ближней плоскости, чтобы отсечь остальные плоскости так же останется поделить на Z или W чтобы получить "двухмерные", точнее координаты в пространстве пирамиды отсечения. Останется только отрисовать усеченные треугольники без лишних расчетов. Также есть альтернативные варианты отсечения по оставшимся 4 плоскостям - как проверка выхода пикселей за экран/буфер во время отрисовки. То есть, по факту требуется посчитать отсечение только ближней и дальней плоскостей. В остальном ты просто делаешь горизонтальную заливку обходя только пиксели в диапазонах [0..width] [0..height], это просто поскольку эта проверка легко выноситься за циклы отрисовки - буквально четыре условия на тех значениях которые у тебя уже будут посчитаны.

Спасибо.

foxes а можно уточнить про экранные координаты?

Например я знаю экранные координаты что это:

//перед этим код обработка одной вершины, программный рендеринг
v.x = v.x / v.z;
v.y = v.y / v.z
//дальше преобразование в экранные координаты ширина экрана 640 высота 480
vx = v.x * 640.0 / 2.0 + 640.0 / 2.0;
vy =-v.y * 480.0 / 2.0 + 480.0 / 2.0;
//дальше проводим линии, интерполируем цвета, текстурные координаты т.п.

Вот насколько я знаю это экранные координаты. А почему вы говорите что mxWorld * mxView это есть экранные координаты- это пространство вида.

SmoothBoy
> foxes а можно уточнить про экранные координаты?
Возможно я не совсем правильную терминологию использовал. Screen space -> "экранное пространство" отсюда экранные координаты. То есть экранные 3D и 2D, но из описания остального я надеялся что будет понятно о чем идет речь.

SmoothBoy
> А почему вы говорите что mxWorld * mxView это есть экранные координаты- это
> пространство вида.
Фактически для рендеринга достаточно общей матрицы "mxModel * mxView * mxProj", Отдельные вариации используются для спецэффектов.
Сама матрица mxProj не производит ни каких изменений влияющих на результат отсечения по плоскости. Только нужно не забыть про W.
w2 = (w2 - w1)*d + w1; - это на самом деле константа для конкретной плоскости отсечения. Проще это все интерполяцией вектора обернуть.
SmoothBoy
> Например я знаю экранные координаты что это:
Эти координаты можно так же назвать проекционными, точнее те что получаются после деления на Z.
SmoothBoy
> //дальше преобразование в экранные координаты ширина экрана 640 высота 480
А далее получаются координаты пикселя - пиксельные координаты. Эти координаты называются экранными чаще для 2D приложений и GUI. А в конкретной реализации софт рендера я бы их назвал буферными.
То есть вариаций и обобщений в разных "культурах" много. И в тех и в других плоскость проекции или ближайшая плоскость отсечения перпендикулярна оси Z.

SmoothBoy
> v.x = v.x / v.z;
> v.y = v.y / v.z
По феншую делается так

Если ты конечно правильно умножение матрицы на вектор делаешь.

https://gamedev.ru/code/forum/?id=16748&page=2&m=3636338#m18
Но этот пример скорее для точки чем для треугольника.