Pull to refresh

Comments 50

если мы смотрим на плоскость и она от нас как бы легла в глубину по оси z и при этом угол между x и y 90 градусов.
Так положить можно просто умножив вектор координат точек плоскости на матрицу вращения вокруг X на угол 90 градусов.
UFO just landed and posted this here
Нет, через Direct Draw. В cvideo задаётся адрес видеопамяти и размер строки, которые получены от Direct Draw при захвате вторичной плоскости.
UFO just landed and posted this here
Аккуратно-то аккуратно, но в устаревшей манере — я в современном Си++ плаваю, как топор (всякие лямбды и прочее для меня тёмный лес).
Там в Direct Draw просто получается адрес видеопамяти, который передаётся в класс видео CVideo. Дальше интерфейсный класс CIEngine определяет все функции вывода графики и загрузки данных. От этого класса унаследован класс CEngine_Base, в котором определены многие функции и добавлены защищённые функции, общие для все трёх вариантов движков (текстурирование линий, например). А уже от этого класса унаследованы сами движки. Все эти классы первым делом у CVideo запрашивают параметры видеоэкрана, а рисуют уже как в MS-DOS — записью в видеопамять.
Кстати, чтобы совсем отвязаться от DirectDraw в пользу GDI можно попробовать SetDIBitsToDevice, также выделяешь кусок памяти, растеризуешь и в нужный момент блитишь на поверхность окна.
Э… А зачем нужно от Direct Draw отвязываться? К нему наоборот привязываться надо исходя из соображений быстродействия.
Э… портировать на Linux например, да и нет у него нынче никакого быстродействия.
Ну, портировать-то как раз просто. Нужно просто в cVideo задать адрес буфера, выделенного с помощью malloc или new. А после рисования вывести этот буфер чем угодно. А клавиатура в движке привязана классом CKeyboard. То есть, клавиатура там виртуальная.
Кстати, я под QNX предыдущую версию портировал.

#include "cmain.h"

CMain cMain;
extern CVideo cVideo;

//-Конструктор класса--------------------------------------------------------
CMain::CMain()
{
 VideoBufferPtr=new unsigned long[WINDOW_WIDTH*WINDOW_HEIGHT];
 cVideo.SetVideoPointer(VideoBufferPtr,WINDOW_WIDTH); 
}
//-Деструктор класса---------------------------------------------------------
CMain::~CMain()
{ 
 delete[](VideoBufferPtr);
}
//-Замещённые функции предка-----------------------------------------------
//-Новые функции класса------------------------------------------------------

//----------------------------------------------------------------------------------------------------
//открытие окна
//----------------------------------------------------------------------------------------------------
bool CMain::OpenWindow(void)
{
 PgSetDrawBufferSize(65535);
 cControl.Init(); 
 return(true);
}
//----------------------------------------------------------------------------------------------------
//закрытие окна
//----------------------------------------------------------------------------------------------------
bool CMain::CloseWindow(void)
{
 cControl.Close();	
 return(true);	
}
//-Функции обработки сообщений класса----------------------------------------
//----------------------------------------------------------------------------------------------------
//нажали или отпустили кнопку мыши
//----------------------------------------------------------------------------------------------------
void CMain::OnActivate_MouseButton(long x,long y,bool left,bool right,bool center)
{
 OnPaint();
}
//----------------------------------------------------------------------------------------------------
//перерисовать картинку
//----------------------------------------------------------------------------------------------------
void CMain::OnPaint(void)
{
 PhDim_t ImageSize;
 int ImageBPL=WINDOW_WIDTH*sizeof(unsigned long);
 ImageSize.w=WINDOW_WIDTH;
 ImageSize.h=WINDOW_HEIGHT;
 PhPoint_t pos;
 pos.x=0;
 pos.y=0;
 PgDrawImagev(VideoBufferPtr,Pg_IMAGE_DIRECT_8888,&pos,&ImageSize,ImageBPL,0);  
}

//----------------------------------------------------------------------------------------------------
//обработка таймера
//----------------------------------------------------------------------------------------------------
void CMain::OnActivate_Timer(void)
{ 
 cVideo.SetVideoPointer(VideoBufferPtr,WINDOW_WIDTH);
 cControl.Processing();	
 OnPaint();
}

//-Новые функции класса------------------------------------------------------

//-Прочее--------------------------------------------------------------------



/* Y o u r   D e s c r i p t i o n                       */
/*                            AppBuilder Photon Code Lib */
/*                                         Version 2.03  */

/* Standard headers */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <photon/PkKeyDef.h>
#include <Ph.h>
#include <Pt.h>
#include <Ap.h>

/* Local headers */
#include "ablibs.h"
#include "abimport.h"
#include "proto.h"
#include "ckbrd.h"

extern CKeyboard cKeyboard;

int OnActivate_Raw(PtWidget_t *widget, ApInfo_t *apinfo, PtCallbackInfo_t *cbinfo )
{
 if (cbinfo->event->type==Ph_EV_KEY)
 {
  PhKeyEvent_t *kev=(PhKeyEvent_t *)PhGetData(cbinfo->event);
  long scan=kev->key_scan;
  if (kev->key_flags&Pk_KF_Scan_Valid) 
  {
   if (kev->key_flags&Pk_KF_Key_Down) cKeyboard.SetKeyState(scan,true);
                                else  cKeyboard.SetKeyState(scan&0x7f,false);
   //printf("Scan:%i\r\n",scan);                                
  }
 }
 return(Pt_CONTINUE);
}
Ещё вариант портального софт-рендера на C
Прикольно. :) Правда, а это точно софтверный рендер — вот то, что с освещением? Вроде как карта освещенённости используется, но её в софверном варианте довольно дорого выводить.

Пожалуйста, укажите лицензию на код и, если совсем не затруднит, создайте репозиторий, например на GitHub или Bitbucket. Спасибо!

Лицензию на код? Я в них не разбираюсь. Как называется лицензия, если вы можете делать с кодом абсолютно всё, что захотите? Free?
А на Github я не могу выложить — я никогда не работал с такими системами разработки и понятия не имею, как там вообще осуществляется работа. Я попытался понять, нифига не понял, что там вообще нужно делать. Дело в том, что я в команде никогда не работал (хоть я и пишу ПО по работе в НИИ, но я самоучка); у нас таких систем не применяется и опыта работы с ними у меня полный ноль.
Спасибо. :) Ну, значит, MIT. :)

Правда, не знаю, кому эти исходники пригодиться вообще могут. Мне тут на одном форуме сказали, фигурально, что я фигнёй страдаю с софтверными движками и обычным OpenGL. И что давно вместо «forward rendering» используют Deferred Rendering и надо брать готовый движок типа Ogre3d и не изобретать велосипед. :) И я в общем, почти согласен с первым, но вот со вторым не соглашусь — зачем мне Ogre3D, если я игру делать всё равно не буду. :)
Правда, не знаю, кому эти исходники пригодиться вообще могут

По этой теме точно не следует волноваться! Сообществу, имхо, чем больше кодов выложено, тем лучше ;)

Кстати, я совсем забыл — в этом движке используется пирамида фильтрации текстур. Ну тут совсем просто — определяется, во сколько раз текстура сжата и выбирается нужная текстура и всё. Функция FindTexture как раз этим и занимается. Также в движке есть вывод спрайта — он просто закомментирован (функция PutSprite). В качестве спрайта используется текстура стены (он тестовый). Но для его вывода нужно раскомментировать в функциях текстурирования в cEngine_Base.cpp заполнение Z-буфера. Раньше я как раз я Z-буфером спрайты и выводил. Но это медленно, поэтому я отключил спрайты и как будет желание и время, подумаю, как обойтись без него.

da-nie нельзя ли, пожалуйста, продублировать скачивание файлов, чтобы качать их НЕ с яндекса?
(до сих пор пытаюсь скачать пример и постоянно обламываюсь)

Странно, я думал, с яндекс-диска никаких проблем со скачиванием не бывает. Вот ссылка на другом ресурсе.

Спасибо! Качается!

Кое-что расскажу о том, как это работает. В файлах исходников геометрический портал в cengine_gportal.cpp. Там вот что делается.
1) Задаём исходный портал, совпадающий с областью поля зрения игрока.
2) Задаём прямую отсечения — это не более, чем прямая, перпендикулярная вектору зрения игрока. Она нужна, чтобы выбросить из рассмотрения всё, что за спиной игрока. Дело в том, что использованная математика требует, чтобы всё происходило перед игроком.
3) Назначаем текущим сектором, сектор, где находится игрок.
4) Выводим стены текущего сектора
5) Рекурсивно бегаем через все порталы сектора, модифицируя портал на ходу и меняя текущий сектор (как зашли в сектор -выводим все его стены). При этом блокируем портал при заходе в него и разблокирует после выхода (через один портал можно смотреть по-разному, в зависимости от того, как мы в него пришли).

Вот и всё.А вот картинка, как обрезаются порталы и стены.



В OpenGL обрезать нужно только порталы — стены сами обрежутся OpenGL с помощью Z-буфера.

Вроде всё. :)
Совсем забыл случай, когда стена пересекает прямую области видимости. В этом случае я просто обрезаю стену областью видимости так, чтобы она была со стороны игрока.
Попробовал конвертировать карту типа Wolf-3D. Получилось плохо и вот почему: если каждую клетку назначить сектором с порталами в 4 стороны (или меньше — со стороны блоков-стен нужно поставить стену, а не портал), то при рекурсивном обходе порталов в некоторых зонах начинаются тормоза (вплоть до FPS=0). Фишка в том, что раз сектора мелкие, обход через все порталы всех остальных порталов и секторов вырождается в здоровенную рекурсию. То есть, вот так втупую лабиринт из Wolf-3D с порталами не подружить. Нужно как-то объединять сектора в один большой сектор, не создавая порталов.
Всё, понял в чём дело. В функции конвертации карты из Wold-3D создавался двойной набор порталов. Вот оно и дико тормозило. Исправил — и всё заработало на ура. :) Не такая уж там и большая рекурсия, даже без объединения квадратов.

Конвертировал вот такой вот функцией в редакторе 3DEngineEditor. Карта задаётся в текстовом файле:'#'-стена.

//---------------------------------------------------------------------------
//импорт карты из текстового файла
//---------------------------------------------------------------------------
void CDocument_Map::ImportMapFromTXT(FILE *file,CDialog_SettingsWall *cDialog_SettingsWall_Ptr,CDialog_SettingsSector *cDialog_SettingsSector_Ptr)
{
 long n;
 DeleteAll();
 //считываем текстовый файл в плоский массив (0-следующая строка)
 vector<unsigned char> vector_data;
 bool element=false;
 long x=0;
 long y=0;
 long max_x=0;
 while(1)
 {
  unsigned char b;
  if (fread(&b,sizeof(char),1,file)<=0) break;//файл закончился
  if (b<static_cast<unsigned char>(' '))
  {
   if (element==true)//если в строке что-то было считано, делаем перевод строки 
   {
    y++;
    vector_data.push_back(0);
   }
   element=false;
   if (x>max_x) max_x=x;
   x=0;//строка начинается заново
   continue;
  }
  element=true;
  x++;
  vector_data.push_back(b);
 }
 long max_y=y;
 //разворачиваем считанную карту в двумерный массив [max_y][max_x] и заполняем его точками
 vector< vector<unsigned char> > vector_map(max_y,vector<unsigned char>(max_x,'.'));
 x=0;
 y=0;
 long size=vector_data.size();
 for(n=0;n<size;n++)
 {
  if (vector_data[n]==0 || n==size-1)
  {
   y++;
   x=0;
   continue;
  }
  if (vector_data[n]==static_cast<unsigned char>('#')) vector_map[max_y-y-1][x]=static_cast<unsigned char>('#');//непустое поле
  x++;
 }
 vector_data.clear();
 //создаём сектора и сегменты по считанной карте
 CSector cSector_Create;//создаваемый сектор
 cSector_Create.vector_SSectorPoint.clear();
 cSector_Create.Select=false;
 cSector_Create.sSector_State=cDialog_SettingsSector_Ptr->GetState();
 CWall cWall_Create;//создаваемая стена
 cWall_Create.Frontier=false;
 cWall_Create.Select=false;
 cWall_Create.sWall_State=cDialog_SettingsWall_Ptr->GetState();
 for(y=0;y<max_y;y++)
 {
  for(x=0;x<max_x;x++)
  {
   unsigned char b=vector_map[y][x];
   if (b==static_cast<unsigned char>('.'))//сектор пустой
   {
    //создаём пустой сектор
    cSector_Create.vector_SSectorPoint.clear();
    //добавляем точки четырёхугольника, описывающего сектор
    SSectorPoint sSectorPoint[4];
    sSectorPoint[0].X=(x+1)*100;
    sSectorPoint[0].Y=(y+1)*100;
    sSectorPoint[1].X=(x+1)*100;
    sSectorPoint[1].Y=(y+0)*100;
    sSectorPoint[2].X=(x+0)*100;
    sSectorPoint[2].Y=(y+0)*100;
    sSectorPoint[3].X=(x+0)*100;
    sSectorPoint[3].Y=(y+1)*100;

    cSector_Create.vector_SSectorPoint.push_back(sSectorPoint[0]);
    cSector_Create.vector_SSectorPoint.push_back(sSectorPoint[1]);
    cSector_Create.vector_SSectorPoint.push_back(sSectorPoint[2]);
    cSector_Create.vector_SSectorPoint.push_back(sSectorPoint[3]);
    //добавляем сектор в список секторов
    vector_CSector.push_back(cSector_Create);
	//если вокруг сектора есть стектора-стены, то добавляем стену, иначе добавляем линию раздела
	for(n=0;n<4;n++)
	{
     long next_n=(n+1)%4;
     cWall_Create.X1=sSectorPoint[n].X;
     cWall_Create.Y1=sSectorPoint[n].Y;
     cWall_Create.X2=sSectorPoint[next_n].X;
     cWall_Create.Y2=sSectorPoint[next_n].Y;
     cWall_Create.Frontier=true;//стена - линия раздела
	 if (n==0)//правая стена
	 {
      if (x<max_x-1)
	  {
       if (vector_map[y][x+1]!=static_cast<unsigned char>('.')) cWall_Create.Frontier=false;//сектор справа - стена
	  }
	  else cWall_Create.Frontier=false;
	 }

	 if (n==1)//нижняя стена
	 {
      if (y>0)
	  {
       if (vector_map[y-1][x]!=static_cast<unsigned char>('.')) cWall_Create.Frontier=false;//сектор снизу - стена
                                                           else continue;//не ставим портал, так как он уже есть с этой стороны
	  }
	  else cWall_Create.Frontier=false;
	 }

	 if (n==2)//левая стена
	 {
      if (x>0)
	  {
       if (vector_map[y][x-1]!=static_cast<unsigned char>('.')) cWall_Create.Frontier=false;//сектор слева - стена
	                                                       else continue;//не ставим портал, так как он уже есть с этой стороны
	  }
	  else cWall_Create.Frontier=false;
	 }

	 if (n==3)//верхняя стена
	 {
      if (y<max_y-1)
	  {
       if (vector_map[y+1][x]!=static_cast<unsigned char>('.')) cWall_Create.Frontier=false;//сектор сверху - стена
	  }
	  else cWall_Create.Frontier=false;
	 }
	 //добавляем сегмент
     vector_CWall.push_back(cWall_Create);
	}
   }
  }
 }
}

Круто! Впечатляет!

Так это ж самая очевидная схема работы с порталами. :) Я сперва именно геометрический портал и сделал. А потом, много позже, сообразил, что можно по экрану отсекать в случае, когда стены не могут наклоняться влево-вправо. В общем, для Wolf-3D под OpenGL геометрический портал просто идеален. Только надо при выводе стен не выводить одну и ту же стенку дважды (делать отметку о том, что стена уже выведена) и выводить не фрагмент, видимый через портал, а всю стену сразу. Так же и с персонажами и прочими объектами — выводить только из тех секторов-квадратов, которые были выведены через портал и заодно можно проверить, что объекты вообще видны в портал (описать прямоугольник вида сверху вокруг объектов и сравнивать его попадание в портал).
Движок легендарный, спору нет. Я даже не во все игры успел на нем погонять.
Это который от Сильвермана — Build. Это легендарный 100%. Shadow Warrion, Blood, Duke Nukem 3D.

Но к этой статье приложен не он, а самодельный, гораздо менее мощный.
И вот что меня удивляет. 20 лет, как вышел Duke 3D. Армия программистов. А движков самодельных (хоть с OpenGL, Direct 3D, хоть сотфверных) сделано очень мало. Как так-то? Вообще странно, столько программистов, а весь инет не завален их интересными программами (например, графическими). То ли они пишут только на работе, а дома нет, то ли ещё есть какая причина, но при таком количестве программистов их программ должно быть сильно дофига.
Можно также спросить, где Бахи, Бетховены, Пушкины, Толстые и всякие другие Моцарты…
А на этот вопрос какой ответ? :)

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

Всё очень просто. Итак, у вас есть карта как набор соединённых друг с другом точек. Между точками отрезки — это стены. Значит, у стены есть кординаты (x1,y1)-(x2,y2). Таких стен на уровне много. В начале разбиения у вас в наборе все стены карты. Теперь геометрически поделим этот набор некоторой линией (можно её провести через геометрический центр этого набора — просто окружить набор прямоугольником и провести линию через центр). Это даст нам относительно этой линии ДВА набора — слева от линии и справа от неё (все стены, которые линия пересекла надо ей «разрезать» на два новых кусочка; если стена совпадает с линией, то добавляем её в любой один набор, правый или левый). Каждый из этих наборов обработаем так же, как и исходный. Так будем разбивать до тех пор, пока разбивать станет нечего (DooM бьёт до выпуклых прямоугольников из сегментов, я бью до отдельной линии). Получится дерево двоичного (так как пространство делится каждый раз на две половинки) разбиения пространства — BSP-дерево. Как им пользоваться? Очень просто. Начинаете обход дерева: последовательно от вершины (это первое разбиение карты на пополам) на каждом уровне дерева (место очередного разбиения на два) сравниваете игрока с линиями, которыми разбивали и идёте в ту часть дерева, в которой игрок (если игрок стоит на линии, можно в любую сторону переходить). И так до конца, содержащего игрока. Если теперь обойти дерево от игрока к вершине (поднимаясь в верх дерева заходя на каждой развилке-разбиении в сторону, в которую ещё не заходили), то вы получите набор стен, упорядоченный от игрока в глубь. При этом можно если каждый раз при исходном разбиении описывать набор прямоугольником, в котором этот набор содержится, то при обходе дерева от игрока можно сразу сравнивать эти прямоугольники с областью видимости игрока и не переходить в них.
Итак, мы получили обход стен от игрока в бесконечность. Теперь в дело вступают линии горизонта. Как они работают, я написал в этой статье.

Метод порталов тоже позволяет упорядочить стены от игрока в бесконечность. Но заключается в рекурсивном (последовательном) обходе выпуклых секторов (! не стен !), у которых определены отрезки, через которые виден другой сектор. Если начать обход через эти отрезки из сектора в сектор от игрока (мы же можем найти в каком он секторе?), то мы получим метод порталов.

спасибо, но то что вы написали я читал много-много раз и это совсем не приближает меня к практическому пониманию.

основные вопросы возникающие по ходу прочтения:

1) какая зависимость от выбора стратегии разрезания? резать можно в двух направлениях

2) не проще ли считать хеш от координат - это будет O(1) переходов, а не O(Log2(N))?

3) где у вас вектор взгляда и как он фигурирует в дереве?

4) и не просто вектор взгляда, а отсекающий треугольник камеры, как порталы работают если попадают в камеру частично?

последний абзац совсем не понимаю, откуда в вашем двоичном дереве отрезков появляются выпуклые секторы?

1) какая зависимость от выбора стратегии разрезания? резать можно в двух направлениях


Резать можно в любых направлениях. От разрезающей линии зависит сбалансированность дерева. Можно вообще выбирать любой отрезок за линию разрезания. Лишь бы не получалось всё время с одной стороны пусто, а с другой вся карта — это, понятно, процесс бесконечный.

2) не проще ли считать хеш от координат — это будет O(1) переходов, а не O(Log2(N))?


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

3) где у вас вектор взгляда и как он фигурирует в дереве?


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

image

4) и не просто вектор взгляда, а отсекающий треугольник камеры, как порталы работают если попадают в камеру частично?


Геометрический портал просто отсекается по границам области видимости. Экранный отсекается автоматически экраном.

последний абзац совсем не понимаю, откуда в вашем двоичном дереве отрезков появляются выпуклые секторы?


Порталы не используют BSP. Они требуют изначально выпуклых секторов и отсутствие стен внутри них (только по границам).
BSP-дерево не требует выпуклых секторов, но, обычно, сектора всё равно делают выпуклыми (так легко определять наличие объектов в них). Внутри секторов могут быть стены (а не только по контуру). Поэтому при разбиении можно дойти до ситуации, когда остались только стены, формирующие выпуклую фигуру. Вот её уже можно выводить целиком — в ней стены друг друга не перекрывают. Это и использует DooM.

Сразу скажу, что метод порталов быстрее, чем BSP. Именно это позволяло Duke Nukem работать быстрее DooM.

Дерево формирует упорядоченный вывод стен от наблюдателя в даль

пока я не увидел объяснения этого. для меня деление на две части - суть сортировка, а так же это битовое кодирование пути. в какой момент там появляется вектор взгляда и почему деление на две части вдруг одинаково работает для любой позиции наблюдателя (без информации о камере) да еще и откуда-то берется информация о взаимном перекрытии. Вот это и не ясно.

Я не понял, что такое хэш координат и зачем он вам

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

Нарисованное на картинке совсем не понял, если у вас есть треугольник зоны видимости зачем вам еще прямая зоны видимости?

Геометрический портал просто отсекается по границам области видимости. Экранный отсекается автоматически экраном.

не понимаю контекста

Порталы не используют BSP

я не знаю что такое BSP и как оно работает, поэтому объяснять порталы через BSP плохая идея.

В общем мне кажется это бесполезной тратой времени.

PS: еще из ваших объяснений у меня сложилось впечатление что слово "портал" тут применяется в какой-то абстрактном значении, как если бы кто-то голубя назвал квадратом просто потому что ому-то это пришло в голову.

пока я не увидел объяснения этого. для меня деление на две части — суть сортировка, а так же это битовое кодирование пути. в какой момент там появляется вектор взгляда и почему деление на две части вдруг одинаково работает для любой позиции наблюдателя (без информации о камере) да еще и откуда-то берется информация о взаимном перекрытии. Вот это и не ясно.


А это и есть сортировка по отношению к выбранной линии разделения. Вектор взгляда там для возможности отбрасывать поддеревья, про которые точно известно, что они не видны из позиции наблюдателя для ускорения вывода. Можно его не использовать и выводить весь обход дерева целиком. А работает этот потому, что когда вы строите дерево, вы делаете декомпозицию сцены на всё более мелкие элементы, расположенные определённым образом относительно выбранных линий наблюдения. То есть, движетесь от большой сцены к её отдельному элементу. При обратном проходе от наблюдателя вы просто идёте от меньших элементов к большим. Вы как бы с каждой итерацией отдаляетесь от наблюдателя. Проверьте, это точно работает. :)

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


Это потребует приличных вычислительных затрат на этапе построения карты. И это не так делается. Такая техника сделана для Quake для ускорения — там BSP-дерево трёхмерное. Quake бьёт до объёмных секторов, а потом цепляет к ним список видимых из данного сектора других секторов (они в поддеревьях). При раскручивании дерева, он выбрасывает всё, что не видимо. В DooM такая техника избыточна и не применяется.

Нарисованное на картинке совсем не понял, если у вас есть треугольник зоны видимости зачем вам еще прямая зоны видимости?


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

я не знаю что такое BSP и как оно работает, поэтому объяснять порталы через BSP плохая идея.


Я не объяснял порталы через BSP. Я объяснял и то и другое. :)

В общем мне кажется это бесполезной тратой времени.


Почему? Возьмите книжку «Шикин, Боресков. Компьютерная графика, полигональные модели». Я по ней в 2001 году делал свой DooM. Он под MS-Dos. А выглядит он так (в этом видео он на 3:19).

PS: еще из ваших объяснений у меня сложилось впечатление что слово «портал» тут применяется в какой-то абстрактном значении, как если бы кто-то голубя назвал квадратом просто потому что ому-то это пришло в голову.


Да нет…
Портал (англ. portal от лат. porta «ворота»): Портал — главный вход большого архитектурного сооружения. Портал (сцены) — архитектурный элемент, окаймляющий сцену и отделяющий её от зрительного зала.


Вот и вся идея в том, что из одного сектора другой можно видеть только через портал, их соединяющий.

не понимаю контекста


А вы нарисуйте карту и посмотрите, как меняется конус видимости, отсекаясь по порталам при переходе из сектора где находится игрок и в даль. Это и есть геометрический портал — вы все выводимые линии каждый раз этим конусом обрезаете ДО вывода). А экранный, это когда этот конус автоматически просто уменьшается прямо по экрану (это координаты на экране X слева и справа (зона вывода находится между ними) при выводе) при отрисовке порталов между секторами.

Возьмите книжку «Шикин, Боресков. Компьютерная графика, полигональные модели»

не вижу смысла мусолить детали без понимания основы, поэтому книгу скачал и посмотрел. И это ничего не дало. Метод порталов в книге работает совсем иначе, совсем другое его объяснение, в целом то что написано в книге понятно в общих чертах (описание скудное и говорит исключительно о способе определения видимости комнат, но совсем ничего не написано про разрезание карты или двоичный поиск, о которых пишете вы и из ваших слов я не вижу объяснения того почему движение по дереву даёт что-то упорядоченное если в дереве отсутствует информация о камере и векторе взгляда).

поэтому остался открытым вопрос с тем что написали вы.

Невозможно помочь тому, кто не хочет сам понимать, что ему рассказывают, а ждёт, что понимание наступит само по себе. ;)
Потому что я с этим разобрался в 18 лет ровно по этой же книжке. Никаких чудес там нет. Всё очень просто и понятно.

Вы как себе это представляете? Я сажусь на стул и с надутыми губами дёргая ножками начинаю канючить и кричать "я не хочу понимать суть порталов"? Мило конечно, но это не так.

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

То что вы что-то для себя вынесли из этой книги в 18 лет лишь подчеркивает вашу исключительность в этом вопросе и с бОльшей долей вероятностью что ваши способности заметно выше моих. Но учитывая что raycasting я изучил быстро по английскому источнику у меня не поднимется рука сказать о себе, как о безнадежном и тупом. Именно поэтому я в самом первом комментарии указал (специально), что мне пока не удалось найти внятного и понятного объяснения, в массе прочитанного даются абстрактные данные, словно я уже должен всё знать о чем-то. Ваша подача как в статье, так и в комментариях в данном аспекте ничем не отличается. Вы даже первый ответ начали с фразы "всё просто". В книге, которую вы дали - действительно всё просто - идём по соседним комнатам и всё. Но там это описано как способ оптимизации, то есть это не алгоритм упорядоченного выбора, это минимизация выборок для проверки.

Вы как себе это представляете?


На практике это просто лень затратить усилия и пытаться понять до просветления. Никогда не готовились к экзаменам? Сидишь над конспектом (бывает, совсем не очевиден кусочек перехода от одного к другому) и пытаешься понять, «ПОЧЕМУ ТАК?!».

и оно никак не совпадает с вашим вариантом даже в ближайшем приближении.


Потому что вы не попытались затратить усилия понять, как оно так работает и почему.

В книге, которую вы дали — действительно всё просто — идём по соседним комнатам и всё. Но там это описано как способ оптимизации, то есть это не алгоритм упорядоченного выбора, это минимизация выборок для проверки.


Вам не очевидно, что если начать ходить из комнаты, где игрок, всё дальше и дальше через первый портал, то вы получите упорядочение ОТ ИГРОКА через этот портал? Так же для следующего. Там обычный рекурсивный обход.

На практике это просто лень затратить усилия и пытаться понять до просветления

я правильно понимаю что вам в школе просто давали учебник и ждали когда наступит просветление?

и пытаешься понять, «ПОЧЕМУ ТАК?!»

Так можно просидеть всю жизнь, не?

Потому что вы не попытались затратить усилия понять, как оно так работает и почему

Вы слишком много на себя берёте давая оценку другому человеку в таком виде.

Вам не очевидно, что если начать ходить из комнаты, где игрок, всё дальше и дальше через первый портал, то вы получите упорядочение ОТ ИГРОКА через этот портал?

Как я уже написал, ваши объяснения и то что написано в книге - разные вещи. Как это работает в книге я понимаю, хотя там нет описанных механизмов для представления информации и способов обхода, но в теории там всё ясно. Ваш же вариант с распилами мне некуда приложить.

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

В частности:

1) Как хранится информация о векторе взгляда? От этого напрямую зависит направление обхода, ведь место где находится игрок может граничить с бесконечным числом порталов в соседние комнаты.

2) Как отсекать порталы следующие и следующие, такие, которые заведомо не видны с позиции игрока? Например в вашем объяснении не ясно зачем нам всё дерево распилов всей карты, если игрок бегает по одной комнате в самом дальнем углу карты со всего одним порталом, который при правильной реализации п.3 будет за О(1) операций всегда выбираться из массива.

3) Без использования хеширования вы будете перебирать постоянно N комнат и если N сильно большое, близкое к общему числу комнат, то вы фактически будете бегать постоянно по всем комнатам карты, хотя на экране вообще смотрите в стену.

Я всё же склонен считать, что вы в силу лёгкости и простоты темы ЛИЧНО ДЛЯ ВАС ушли в её понимании так далеко, что не в состоянии опуститься до уровня первого вхождения в тему и объяснить материал доходчиво. Отсюда и ваше упование на весьма странный способ образования через созерцание книжки. (на всякий случай расскажу, на нашей планете очень много людей не понимаю время в 24-часовом формате и не в силу культурных аспектов, как в США например, а в силу просто особенностей мышления. я, так уж повелось, совсем не умею мыслить категориями ООП, хотя хорошо понимаю структурное программирование, поэтому понимание работы с BSP и порталами скорее всего находится где-то там же, отчего я это могу не понимать вовсе. Но, если взять например мою историю знакомства с методом Хаффмана, то для понимания его работы мне потребовалось больше 20 лет, и оно пришло всего-то из-за прочтения небольшого текстовика на английском из 90-х, хотя до этого я прочёл огромное количество литературы. Сейчас у меня такие же точно проблемы с ANS/rANS)

Поэтому будьте попроще, я не навязываюсь и если вам неинтересно что-то рассказать и объяснить - это ваше право, но не нужно всё сводить к моей лени, вы меня не знаете.

PS: кстати было бы интересно, с практической точки зрения, для всех преподавателей в стране услышать подробное описание метода образования через "усилие", формы затраты оного и сам процесс понимания через такое "усилие". Возможно вы бы произвели революцию в образовательной сфере. Особенно это было бы полезно в изучении иностранного языка, когда вы смотрите 4-7-10 часов на английское слово и вуаля - вы уже умете пользоваться всеми формами инфинитивов.

я правильно понимаю что вам в школе просто давали учебник и ждали когда наступит просветление?


Далеко не всё из учебника я понимал с первого раза. И даже с сотого не всегда получалось.

Так можно просидеть всю жизнь, не?


Интересно, интересно, как вы собираетесь постигать сложные концепции (которые и самим ими оперирующими часто не очень-то ясны — квантмех там всякий, теорию поля)?

Вы слишком много на себя берёте давая оценку другому человеку в таком виде.


Это не коррелирует с «Так можно просидеть всю жизнь, не?»? Перевожу с вашего: «мне лень тратить время на понимание. Обучите меня с минимальными затратами с моей стороны!»

1) Как хранится информация о векторе взгляда? От этого напрямую зависит направление обхода, ведь место где находится игрок может граничить с бесконечным числом порталов в соседние комнаты.


Никак не хранится. У вас в текущий момент времени есть (x,y) и угол обзора (alpha). Ищете в каком секторе игрок. Рисуете его. Дальше рекурсия: для каждого видимого (того, который попадает в сектор обзора игрока) портала сектора, где находится игрок, выводите видимую через портал часть сектора смежного с порталом. Теперь берёте этот смежный сектор за исходный и перебираете его порталы, видимые через портал с которого попали. И снова и снова всё это повторяете, обходя сектора друг за другом. Замечу, что каждый портал обрезает собой косус взгляда. По мере удаления, этот конус уменьшается (или вообще пропадает). Поймите, портал — это ограничение взгляда игрока! С каждым порталом происходит коррекция конуса видимости (он отсекается по порталу).

Например в вашем объяснении не ясно зачем нам всё дерево распилов всей карты, если игрок бегает по одной комнате в самом дальнем углу карты со всего одним порталом, который при правильной реализации п.3 будет за О(1) операций всегда выбираться из массива.


Это ДВА РАЗНЫХ метода, между собой не связанных. Двоичное разбиение пространства позволяет выполнить ту же задачу вывода от игрока вдаль, что и метод порталов, но другим способом.

3) Без использования хеширования вы будете перебирать постоянно N комнат и если N сильно большое, близкое к общему числу комнат, то вы фактически будете бегать постоянно по всем комнатам карты, хотя на экране вообще смотрите в стену.


Так не буду же. Вот я нашёл, что я в секторе 6. У меня есть список его порталов и стен. Порталы связывают его с секторами 3 и 10. Их порталы мне тоже известны. Ну и зачем мне хэширование? Я сразу на обычном массиве секторов бегаю из сектора в сектор и получаю сразу его стены и порталы.

Я всё же склонен считать, что вы в силу лёгкости и простоты темы ЛИЧНО ДЛЯ ВАС ушли в её понимании так далеко, что не в состоянии опуститься до уровня первого вхождения в тему и объяснить материал доходчиво.


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

Поэтому будьте попроще, я не навязываюсь и если вам неинтересно что-то рассказать и объяснить — это ваше право, но не нужно всё сводить к моей лени, вы меня не знаете.


Лень легко проверяется. Кто не ленится, тот пытается составить картинку понимания, пересказать её, и задать уточняющие вопросы, правильно ли он понял, что происходит. А вот кто ленится, тот просто сообщает, что ничего не понял и точка. Иными словами, ленящийся сопротивляется осмыслению сказанного, а пытающийся понять наоборот.

Возможно вы бы произвели революцию в образовательной сфере.


Во многих случаях просто заучить (как с английским) бывает мало.

Далеко не всё из учебника я понимал с первого раза. И даже с сотого не всегда получалось.

Так почему вы считаете что я просто обязан понимать вас или то что написано в указанной книге?

Интересно, интересно, как вы собираетесь постигать сложные концепции (которые и самим ими оперирующими часто не очень-то ясны — квантмех там всякий, теорию поля)?

А я должен? Мне это неинтересно ни в каком приближении.

Это не коррелирует с «Так можно просидеть всю жизнь, не?»? Перевожу с вашего: «мне лень тратить время на понимание. Обучите меня с минимальными затратами с моей стороны!»

Это так не работает. Не ленью определяется образование или его отсутствие. Понятие наставничества существует ровно столько, сколько существует человек и способность наставника показать, рассказать, навести на мысль - это важный аспект образования человека. При кажущейся одинаковости людей - мы все разные, и очень сильно, как в возможностях осмысливать вещи, так и в возможностях их постигать. А самое удивительное, что прочтение одной и той же информации может приводить к разным выводам - трактовкам. Если что, концепция логики, как науки, сформирована совсем недавно, по меркам жизни человечества - вчера. Поэтому когда вы думаете что все вокруг такие как вы и понимают всё точно так же как вы, это лишь говорит о недостаточности вашего образования, как бы странно это не звучало. Думая что постигнув порталы и квантмех вы думаете что вы познали всё и что вы в состоянии смотреть на вещи с единственно правильной точки зрения, но это и есть недостаток образования.

Никак не хранится. У вас в текущий момент времени есть (x,y) и угол обзора (alpha)

Советую очень внимательно вам самому перечитать вашу же статью. Вы нигде не оперируете этими значениями.

Ищете в каком секторе игрок. Рисуете его. Дальше рекурсия

Это понятно сразу, вопрос в том причем тут разрезание на половинки.

Это ДВА РАЗНЫХ метода, между собой не связанных. Двоичное разбиение пространства позволяет выполнить ту же задачу вывода от игрока вдаль, что и метод порталов, но другим способом.

А зачем вы упоминаете двоичное разбиение еще и в контексте статьи про порталы.

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

  1. представленный движок будет использовать не BSP (как DOOM), а метод порталов

  2. метод порталов работает быстрее

  3. Как же работает BSP-движок? Да очень просто (на основании п.1 не ясно причем тут BSP)

  4. Тем самым вы автоматически получите упорядочение сегментов и линий раздела от игрока в бесконечность (на основании чего это стало ясным?)

  5. Портальный движок работает несколько иначе (ах, оказывается до этого описывая "не BSP" вы описали BSP?)

  6. Мы просто должны узнать, в каком из секторов находится игрок (а мы забыли где он находится?)

  7. Алгоритм такого хождения тоже рекурсивный и тоже в результате мы получаем упорядочивание секторов и сегментов от игрока в бесконечность (На основании чего мы получаем упорядоченность?)

  8. Ну вот, вроде как и всё (действительно XD)

Теперь вы видите как ваша статья выглядит со стороны читателя. Неясным остаётся аспект описания BSP - зачем вы о нём пишете вообще? А так же отсутствие описания метода порталов (в указанной вами книге написало просто и понятно, как раз для непосвященного читателя, надеюсь вы затевали свой материал тоже как что-то, что будет интересно не только тем кто уже всё знает?)

Так не буду же. Вот я нашёл, что я в секторе 6. У меня есть список его порталов и стен. Порталы связывают его с секторами 3 и 10. Их порталы мне тоже известны. Ну и зачем мне хэширование? Я сразу на обычном массиве секторов бегаю из сектора в сектор и получаю сразу его стены и порталы.

Во-первых "не будете" вовсе не потому что вы написали, а потому что у вас есть конус отсечения и вектор взгляда (не в статье, в статье о них ничего не написано). Во-вторых, если у вас есть центральная комната вокруг которой еще 50 млн комнат, то если судить по вашему тексту - вы будете каждый раз пробегать по всем 50 млн порталов, что конечно же глупо. А чтобы этого не делать, вы должны очень быстро по информации о векторе взгляда получать дерево порталов ограниченные конусом взгляда. Лучше, если сразу будут отсекаться те порталы, которые хоть и попадают в конус, но находятся вне поля зрения. В случае реального игрового проекта на ограниченном по производительности железе избегать таких комнат лучше всего на этапе проектирования уровня, тогда заморочки с хешированием можно опустить, но тогда число порталов на уровне должно быть малым, достаточным для обработки с приемлемым фреймрейтом, например в 30 fps (Кармак обошел это ограничение используя эффект замедления времени без потери кадров).

У меня очень средние способности, не преувеличивайте

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

Лень легко проверяется

Нет. Вы никогда не отличите лень и отсутствие способностей к пониманию.

Кто не ленится, тот пытается составить картинку понимания, пересказать её, и задать уточняющие вопросы, правильно ли он понял, что происходит

Ну вот я и составил картину, задаю уточняющие вопросы, а вы меня называете ленивым XD как-то не работает ваш метод

А вот кто ленится, тот просто сообщает, что ничего не понял и точка

И где я такое написал? Как вывод по результатам общения с вами - да, я резюмировал это как мою неспособность ПОКА понять материл в текущем изложении. Заметьте, описание метода порталов из вашей статьи я не понял, из книги - понял сразу. Вопросы у меня по вашей статье, выше 8 основных позиций. Вы считаете что в статье есть всё, а я вам показываю что это не так. То есть меня ленивым называть это прям фуфуфу. Я работаю с материалом, но не понимаю вас. Причем тут лень?

Иными словами, ленящийся сопротивляется осмыслению сказанного, а пытающийся понять наоборот

Я любую информацию воспринимаю как черный ящик из которого достают детали. Каждая деталь, это часть механизма внутри. Детали лежат порознь. Моя задача по этим деталям создать машину, которая будет выполнять описываемую функцию. Задача учителя - показать, как детали можно соединить, как можно, не имея всех деталей - додумать, закончить механизм и получить полную картину. И тут главное, что многие люди даже если им просто вытащить механизм из ящика и рассказать его работу - всё равно ничего не поймут.

У вас просто нет опыта преподавания, у меня - есть. У вас выше скилл, знания, компетенции, но вы не умеете объяснять.

Во многих случаях просто заучить (как с английским) бывает мало

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

Мой комментарий в основном был о том, что вы не имея педагогического образования и понимания основ образовательного процесса, придумали себе некий стандарт, который единственно верный. Проблема в том, что вы действуете по принципу "ошибки выжившего", то есть вы думаете - если вам это помогает получать знания (причем я думаю довольно легко), то этот способ работает со всеми, но это не так. Для большинства это долгий, суровый, тяжёлый процесс.

Например в школе мне было скучно, потому что всё давалось легко, домашку делал влёт. И так, на саночках, я прилетел в ВУЗ и быстро стал аутсайдером, всё было тяжело, сложно, непонятно и главное - никто не стремился что-то объяснять - давали книги и нужно было их читать. Я сначала думал что можно бросать ВУЗ, но переезд решил этот вопрос и я оказался в другом ВУЗе и понял, что в первом просто не умели преподавать. Три последних года после перевода я окончил с отличием. И нет, второй ВУЗ не был ниже уровнем. А позже, я попал в академическую среду и на практике увидел разницу между преподавателями и тем, может кто-то обучать или нет.

Извините, вам помочь не смогу. Кто хочет учиться, тот учится и разбирается, кто не хочет, изыскивает причины. Тут какое-то заболевание с отсуствием способностей к пониманию. В этом случае, я бессилен.

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

Видите ли, но это ваши недостатки. В вашем посте прямо кричит «я ничего не понял, я читал бездумно и очень невнимательно, я разбираться не пытался, воображения у меня нет, желания понять тоже». Зато «обоснования», что вам объясняют неправильно прямо вагон. Такие дети тоже бывают — учатся в спецшколах, там к ним особый подход. Но я особый подход не практикую, уж извините. Наличие особого подхода сразу сигнализирует, что это не ваша стезя. А зачем тогда пытаться объяснить? Чтобы вы потом застряли на другом простейшем элементе?
Only those users with full accounts are able to leave comments. Log in, please.