Передняя плоскость отсечения / Графика / Форум / Программирование игр / GameDev.ru

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

for ( int j =0; j < tree->polygons.PolygonCount; j++)
{

  vector3 v0, v1, v2;
  v0 = tree->polygons.PolyList[j].Vertex[0];
  v1 = tree->polygons.PolyList[j].Vertex[1];
  v2 = tree->polygons.PolyList[j].Vertex[2];

  float dist;

  dist = m_Frustum_Near.a * v0.x + m_Frustum_Near.b * v0.y + m_Frustum_Near.c * v0.z + m_Frustum_Near.d;
  if(dist < 0)  {    continue;  }

  dist = m_Frustum_Near.a * v1.x + m_Frustum_Near.b * v1.y + m_Frustum_Near.c * v1.z + m_Frustum_Near.d;
  if(dist < 0)  {    continue;  }

  dist = m_Frustum_Near.a * v2.x + m_Frustum_Near.b * v2.y + m_Frustum_Near.c * v2.z + m_Frustum_Near.d;
  if(dist < 0)  {    continue;  }

foxes
Постоялец

#1
(Правка: 22:45) 21:50, 20 фев. 2021

Нужно отсекать только если все вершины за плоскостью. Когда ты проецируешь вершины, то есть умножаешь на матрицу поворота и матрицу проекции, у тебя должна получиться вершина в пространстве пирамиды отсечения, где 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, чтобы отсечь уже боковые, иначе будут искажения.

SmoothBoy
Постоялец

#2
(Правка: 10:28) 10:27, 21 фев. 2021

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

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

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

Apfel1994
Постоялец

#3
(Правка: 17:11) 16:59, 21 фев. 2021

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

+ Показать

− Скрыть

#define PLANE_DOT(x, y) \
    ((x)[0] * (y)[0] + (x)[1] * (y)[1] + (x)[2] * (y)[2] + (x)[3] * (y)[3])

#define DIFFERENT_SIGNS(x, y) \
    (((x) <= 0 && (y) > 0) || ((x) > 0 && (y) <= 0))

#define LERP(x, y, t) \
    ((y) + ((x) - (y)) * (t))

sw_inline SWint _swClipAndTransformToNDC_Tri(SWfloat vs_in[][SW_MAX_VTX_ATTRIBS], SWfloat vs_out[16][SW_MAX_VTX_ATTRIBS], SWint _0, SWint _1, SWint _2, SWint out_verts[16], SWint num_attrs, SWint num_corr_attrs) {
    const SWfloat clip_planes[6][4] = {
        { -1, 0, 0, 1 },
        { 1, 0, 0, 1 },
        { 0, -1, 0, 1 },
        { 0, 1, 0, 1 },
        { 0, 0, -1, 1 },
        { 0, 0, 0, 1 }
    };
    const SWint clip_plane_bits[6] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20 };
    SWint clip_mask = 0, num_verts = 3;
    SWint i, j;

    for (i = 0; i < 3; i++) {
        for (j = 0; j < 6; j++) {
            if (PLANE_DOT(vs_in[i], clip_planes[j]) < -0.01f) clip_mask |= clip_plane_bits[j];
        }
    }

    if (vs_in != vs_out) {
        for (i = 0; i < 3; i++) {
            for (j = 0; j < num_attrs; j++) {
                vs_out[i][j] = vs_in[i][j];
            }
        }
    }

    SWint list1[16] = { _0, _1, _2 };
    SWint *in_list = list1, *out_list = out_verts;
    SWint n = num_verts;

#define EMIT_VERTEX(ndx1, ndx2, t)  \
    {                               \
        SWint ii;                   \
        for (ii = 0; ii < num_attrs; ii++) {                    \
            vs_out[num_verts][ii] =                             \
                LERP(vs_out[ndx1][ii], vs_out[ndx2][ii], t);    \
        }                                                       \
        num_verts++;                                            \
    }


    for (i = 0; i < 6; i++) {
        if (clip_mask & clip_plane_bits[i]) {
            SWint out_count = 0;
            SWint ndx_prev = in_list[0];
            SWfloat dp_prev = PLANE_DOT(vs_out[ndx_prev], clip_planes[i]);

            in_list[n] = in_list[0];
            for (j = 1; j <= n; j++) {
                SWint ndx = in_list[j];
                SWfloat dp = PLANE_DOT(vs_out[ndx], clip_planes[i]);
                if (dp_prev >= 0) {
                    out_list[out_count++] = ndx_prev;
                }

                if (DIFFERENT_SIGNS(dp, dp_prev)) {
                    if (dp < 0) {
                        SWfloat t = dp / (dp - dp_prev);
                        EMIT_VERTEX(ndx_prev, ndx, t);
                    } else {
                        SWfloat t = dp_prev / (dp_prev - dp);
                        EMIT_VERTEX(ndx, ndx_prev, t);
                    }
                    out_list[out_count++] = num_verts - 1;
                }

                ndx_prev = ndx;
                dp_prev = dp;
            }

            if (out_count < 3) {
                return 0;
            }

            sw_swap(in_list, out_list, SWint *);
            n = out_count;
        }
    }

    if (in_list != out_verts) {
        for (i = 0; i < n; i++) {
            out_verts[i] = in_list[i];
        }
    }

    for (i = 0; i < n; i++) {
        SWint ii, ndx = in_list[i];
        SWfloat inv_posw = 1 / vs_out[ndx][3];
        for (ii = 0; ii < num_corr_attrs; ii++) {
            vs_out[ndx][ii] *= inv_posw;
        }
        vs_out[ndx][3] = inv_posw;
    }

    return n;

#undef EMIT_VERTEX
}

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

SmoothBoy
Постоялец

#4
19:07, 21 фев. 2021

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

foxes
Постоялец

#5
(Правка: 13:02) 12:16, 22 фев. 2021

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));

x1, y1, z1 - вершина перед плоскостью Z
x2, y2, z2 - вершина за плоскостью Z

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

SmoothBoy
Постоялец

#6
(Правка: 15:16) 15:14, 22 фев. 2021

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

Рендерферма кроликов
Пользователь

#7
(Правка: 17:09) 16:48, 22 фев. 2021

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

foxes
Постоялец

#8
(Правка: 22:23) 22:10, 22 фев. 2021

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

SmoothBoy
Постоялец

#9
11:05, 23 фев. 2021

SmoothBoy
Постоялец

#10
19:38, 24 фев. 2021

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 это есть экранные координаты- это пространство вида.

foxes
Постоялец

#11
(Правка: 21:54) 20:11, 24 фев. 2021

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
По феншую делается так

v.w = 1 / v.w;
v.x = v.x * v.w; // проекция X
v.y = v.y * v.w; // проекция Y
v.z = v.z * v.w; // глубина

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

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

SmoothBoy
Постоялец

#12
16:50, 3 мар. 2021

SmoothBoy
Постоялец

#13
16:54, 12 мар. 2021

Я использую BSP tree и добавил функцию Transform_BSP_Tree которая выполняет умножение на матрицы мира, вида, проекции и делает отсечение по передней плоскости. Но что то отсечение не работает. Причем я выполнял этот код по отсечению в другом проекте для проверки (проект без BSP tree) все работает, а у меня не работает. Вот мой код:

void CMeshManager::Transform_BSP_Tree (BSP_tree *tree)
{
  if(!tree)
    return;

  ExtractFrustum();

  for ( int j = 0; j < tree->polygons.PolygonCount; j++)
   {
     
    if (!PolygonInFrustum(3, tree->polygons.PolyList[j].Vertex))
      continue;

    vertex v0, v1, v2;
    v0 = tree->polygons.PolyList[j].Vertex[0];
    v1 = tree->polygons.PolyList[j].Vertex[1];
    v2 = tree->polygons.PolyList[j].Vertex[2];
    
    v0 = mWorld * v0;
    v1 = mWorld * v1;
    v2 = mWorld * v2;

    v0 = mView * v0;
    v1 = mView * v1;
    v2 = mView * v2;

    polygon poly;

    poly.Vertex[0] = v0;
    poly.Vertex[1] = v1;
    poly.Vertex[2] = v2;
    poly.Texture.TexID = tree->polygons.PolyList[j].Texture.TexID; 
    
    list front_list;
  
    vertex *InTemp[3];

    float fZNear = 0.01f;
    float fZNearTemp = fZNear + 1.0f;
      

    int iNumVertsIn=0;
    bool bV1=false;   bool bV2=false;   bool bV3=false;

    if( poly.Vertex[0].z > fZNear )
    {
      iNumVertsIn++;
      bV1=true;
    }

    if( poly.Vertex[1].z > fZNear )
    {
      iNumVertsIn++;
      bV2=true;
    }

    if( poly.Vertex[2].z > fZNear )
    {
      iNumVertsIn++;
      bV3=true;
    }

      if( iNumVertsIn == 1 )
      {

        if( bV1 )
        {
          InTemp[0]= &(poly.Vertex[0]);
          InTemp[1]= &(poly.Vertex[1]);
          InTemp[2]= &(poly.Vertex[2]);
        }

        if( bV2 )
        {
          InTemp[0]= &(poly.Vertex[1]);
          InTemp[1]= &(poly.Vertex[0]);
          InTemp[2]= &(poly.Vertex[2]);
        }
        
        if( bV3 )
        {
          InTemp[0]= &(poly.Vertex[2]);
          InTemp[1]= &(poly.Vertex[1]);
          InTemp[2]= &(poly.Vertex[0]);
        }

        //Parametric line stuff
        // p = v0 + v01*t
        vertex v01 = *InTemp[1] - *InTemp[0];

        float t1 = ( (fZNearTemp - (*InTemp[0]).z)/v01.z ) ;

        float newz1 = fZNearTemp;
        float newx1 = (*InTemp[0]).x + v01.x * t1;
        float newy1 = (*InTemp[0]).y + v01.y * t1;

        // Second vert point
        vertex v02 = *InTemp[2] - *InTemp[0];
        
        float t2 = ( (fZNearTemp - (*InTemp[0]).z)/v02.z ) ;

        float newz2 = fZNearTemp;
        float newx2 = (*InTemp[0]).x + v02.x * t2;
        float newy2 = (*InTemp[0]).y + v02.y * t2;

        InTemp[2]->x = newx2;
        InTemp[2]->y = newy2;
        InTemp[2]->z = newz2;

        InTemp[1]->x = newx1;
        InTemp[1]->y = newy1;
        InTemp[1]->z = newz1;

        
        float newtx1 = (*InTemp[0]).tu + v01.tu * t1;
        float newty1 = (*InTemp[0]).tv + v01.tv * t1;

        float newtx2 = (*InTemp[0]).tu + v02.tu * t2;
        float newty2 = (*InTemp[0]).tv + v02.tv * t2;


        InTemp[2]->tu = newtx2;
        InTemp[2]->tv = newty2;
      
        InTemp[1]->tu = newtx1;
        InTemp[1]->tv = newty1;

        front_list.Add_To_List(&poly);
      }

      else if( iNumVertsIn == 2 )
      {

        if( bV1 )
        {
          InTemp[0]= &(poly.Vertex[1]);
          InTemp[1]= &(poly.Vertex[2]);
          InTemp[2]= &(poly.Vertex[0]);
        }
        
        if( bV2 )
        {
          InTemp[0]= &(poly.Vertex[0]);
          InTemp[1]= &(poly.Vertex[2]);
          InTemp[2]= &(poly.Vertex[1]);
        }
        
        if( bV3 )
        {
          InTemp[0]= &(poly.Vertex[0]);
          InTemp[1]= &(poly.Vertex[1]);
          InTemp[2]= &(poly.Vertex[2]);
        }

        //Parametric line stuff
        // p = v0 + v01*t
        vertex v01 = *InTemp[2] - *InTemp[0];

        float t1 = ((fZNearTemp - (*InTemp[0]).z)/v01.z ) ;

        float newz1 = fZNearTemp;
        float newx1 = (*InTemp[0]).x + v01.x * t1;
        float newy1 = (*InTemp[0]).y + v01.y * t1;

        // Second point
        vertex v02 = *InTemp[2] - *InTemp[1];
        
        float t2 = (fZNearTemp - (*InTemp[1]).z)/v02.z ;

        float newz2 = fZNearTemp;
        float newx2 = (*InTemp[1]).x + v02.x * t2;
        float newy2 = (*InTemp[1]).y + v02.y * t2;

        InTemp[2]->x = newx1;
        InTemp[2]->y = newy1;
        InTemp[2]->z = newz1;

        //------------
        
        float newtx1 = (*InTemp[0]).tu + v01.tu * t1;
        float newty1 = (*InTemp[0]).tv + v01.tv * t1;

        float newtx2 = (*InTemp[1]).tu + v02.tu * t2;
        float newty2 = (*InTemp[1]).tv + v02.tv * t2;

        InTemp[2]->tu = newtx1;
        InTemp[2]->tv = newty1;
        
        front_list.Add_To_List(&poly);

        //////////////////

        polygon temp;
        temp.Vertex[0] = vertex(newx1, newy1, newz1);
        temp.Vertex[1] = vertex(newx2, newy2, newz2);
        temp.Vertex[2] = (*InTemp[1]);

        temp.Vertex[0].tu = newtx1;
        temp.Vertex[0].tv = newty1;

        temp.Vertex[1].tu = newtx2;
        temp.Vertex[1].tv = newty2;

        temp.Vertex[2].tu = (*InTemp[1]).tu;
        temp.Vertex[2].tv = (*InTemp[1]).tv;

        temp.Texture.TexID = poly.Texture.TexID;

        front_list.Add_To_List(&temp);

      }
      else if (iNumVertsIn == 3 )
      {
        front_list.Add_To_List(&poly);
      }

    for ( int i = 0; i < front_list.PolygonCount; i++)
    {

    vertex v0, v1, v2;

    v0 = front_list.PolyList[i].Vertex[0];
    v1 = front_list.PolyList[i].Vertex[1];
    v2 = front_list.PolyList[i].Vertex[2];
    
    v0 = mProj * v0;
    v0.x = v0.x / v0.z;
    v0.y = v0.y / v0.z;

    v1 = mProj * v1;
    v1.x = v1.x / v1.z;
    v1.y = v1.y / v1.z;

    v2 = mProj * v2;
    v2.x = v2.x / v2.z;
    v2.y = v2.y / v2.z;

    //-------------------------------------

    vector3 edge1,edge2,vcross,vLook;

    edge1 = v1 - v0;
    edge2 = v2 - v0;

    edge1 = Vec3Normalize(edge1);
    edge2 = Vec3Normalize(edge2);

    vcross = Vec3Cross(edge1, edge2);

    vcross = Vec3Normalize(vcross);

    vLook.x = 0.0f;
    vLook.y = 0.0f;
    vLook.z = -1.0f;

    float angle_cos = Vec3Dot(vcross, vLook);
    
    if(angle_cos <= 0.0) //backface culling
      continue;

    //-------------------------------------

    float alpha = (0.5f*nViewWidth-0.5f);
    float beta  = (0.5f*nViewHeight-0.5f);
  
    matrix4x4 mScreen(alpha,  0,      0,    0, 
            0,      -beta,  0,    0, 
            0,    0,    1,    0,
            alpha,  beta,  0,    1);

    v0 = mScreen * v0;
    v1 = mScreen * v1;
    v2 = mScreen * v2;

    polygon pt;

    pt.Texture.TexID = front_list.PolyList[i].Texture.TexID;

    pt.Vertex[0] = v0;
    pt.Vertex[1] = v1;
    pt.Vertex[2] = v2;
        tree->transformed_polygons.Add_To_List(&pt);

    }

  }

  Transform_BSP_Tree (tree->front);
  Transform_BSP_Tree (tree->back);

}