LSP FAQ 96/12/10 김성익 ( NOERROR ) 1. lsp란 무엇인가 ? 2. 데이타는 어떤 방식으로 처리하는 가 ? 3. 화면 출력은 ? 4. 노드 삽입은 ? 5. 클리핑은 ? 6. 타일 스크롤은 ? *7. 다중스크롤은 ? *8. 0번 압축 스프라잇은 ? *9. 확대 축소 출력은 가능한가 ? 10. 베사 모드에선 어떻게 적용시킬 수 있는 가 ? 11. 3차원에 어떻게 적용될 수 있는 가 ? *12. 윈도우 다이렉트 X에 적용 13. 노드 생성에 관해 14.기타 15. 참고자료 0. vesa faq 노트 두번째글입니다. 모든 질문에 답변을 단 최초의 버젼이군요. 이젠 보충과 수정 위주로 업그레이드가 되겠군요. 분량이 많아져설람 내용을 줄이는 일을 하다가 (하이텔 500라인제한) 그냥 문서두개로 나누어 버렸습니다. 답변 내용이 부실한 면이 있어 조만간 버젼업이 필요할거 같습니다. 1. lsp란 무엇인가 ? LSP(Linear Space Partitioning algorithm)는 출력 공간을 나누는 한 기법입니다. 그러니까 쉽게 말해 한 라인 중간에 짧은 라인을 하나 두었을 때 3개의 라인을 구하는 그런 기법이라고 할 수 있습니다. 이 기법을 게임에 응용할 경우 중복되는 출력을 줄일 수 있습니다. 배경을 찍고 캐릭터를 찍을 경우를 생각해 봅시다. 이 경우 분명히 캐릭터에 의해 가려지는 배경부분이 있습니다. 이부분은 찍을 필요가 없는 것입니다. LSP기법을 응용하면 이런 무의미한 출력을 완전히 없앨 수 있습니다. 그리고 버퍼에 배경을 찍고 캐릭터를 찍은 후에 화면으로 출력하는 방식에서 중간 버퍼에 그리는 과정을 없애고 바로 화면에 뿌릴 수가 있습니다. 다음 두개를 비교해 봅시다. (아래의 두 결과는 같다는 점에 주목해주세요. ) [A] memcpy(buffer, background, 100); // 버퍼에 배경 찍기 memcpy(buffer+10, object, 20); // 버퍼에 오브젝트 찍기 memcpy(vram, buffer, 100); // 버퍼를 비디오로 [B] memcpy(vram, background, 10); // 비디오에 배경 10만큼 찍기 memcpy(vram+10, object, 20); // 다음부분에 오브젝트 찍기 memcpy(vram+30, background+30, 70); // 다음부분에 배경 찍기 바로 A의 방법을 B로 바꾸는 것이 LSP의 핵심인 것입니다. ( 위의 것이 같다는 것을 이해 하셔야 LSP를 이해 하실 수 있습니다. ) 단 픽셀 100개를 화면에 찍는 데에도 엄청난 이득이 있음을 알 수 있습니다. A의 방법을 보면 버퍼에 120바이트를 전송한 후에 다시 비디오메모리에 100 바이트를 전송합니다. 그러나 B의 방법은 비디오에 단 100 바이트만을 전송합니다. 먼저 중간 버퍼링 과정과 오브젝트에 가려질 배경출력 20바이트도 생략되었으니 가능하다면 B의 방법 사용이 유리하겠죠 ? 2. 데이타는 어떤 방식으로 처리하는 가 ? 노드 단위로 구성됨으로 노드 구성을 알 필요가 있습니다. 한 노드에 필요한 정보라면길이와 출력 포인터일 것입니다. 그리고 다음 노드의 어드레스도 필요하군요. ( 노드간에 연결을 처리는 사용이 편리한 싱글 링크드 리스트를 이용합니다. ) struct LSP { short length; char *address; LSP *next; }; 이렇게 구성됩니다. 싱글 링크드 리스트는 각 라인별로 쭉 연결이 되겠지요. 한 라인의 출력 하는 소스를 살펴 봅시다. int i; LSP *node = 라인의첫 노드 ; for(i=0; i < SCREEN_XSIZE; ) { memcpy(vram + i, node->address, node->length); // 비디오에 그리기 i += node->length; // 그린만큼 증가 node = node->next; // node = 다음 노드 } 무지 간단하죠 ? 만약 노드가 다음같이 구성되어 있다고 합시다. A1 A2 A3 길이 10 20 70 어드레스 background object (background+30) 다음노드 A2 A3 -- 위와 같이 노드가 구성되어 있다면 아마 1번질문에서 예를 든 B가연출 될것입니다 아예 루프를 쭉 나열해보죠. #define SCREEN_XSIZE 100 int i; LSP *node = A1; memcpy(vram , background, 10); // i=0 // node = A1 이므로 node->address는 background // node->length 는 10이겠죠 ? // 그러니까 memcpy(vram + i, node->address, node->length) // 는 위가 됨 i += 10; // i = 10이 됨 node = A2; // node = A1 이었으니 node->next 는 A1->next 이니 A2 겠죠? // i가 10이니 SCREEN_XSIZE보다 작죠 ? 다시 루프 memcpy(vram + 10, object, 20); // i=10 , node->address = object , node->length = 20 i += 20; // i = 30이 됨 node = A3; // i가 30이니 100보다 작죠 ? 다시 루프 memcpy(vram + 30, background+30, 70); // i=30 , node->address = background+30, node->length = 70 i += 70; // i = 100이 됨 node = --; // 사실 루프에서 벗어날 것은 기정사실이기 때문에 어떤 값이던지 // 상관없음 // i가 100이니 100보다 작지가 않죠 ? // 끝 천천히 읽어 보세요. 이제 감이 잡히시죠 ? 이젠 왜 노드가 위와 같이 구성되는 지 어떻게 출력되는 지는 아실 겁니다. 이제 남은 문제라면 단지 위의 노드를 어떻게 만드냐는 거 겠죠. 3. 화면 출력은 ? ( 2번 질문 참고) 아마 게임화면이 세로 한줄로 구성될리는 없을 것입니다. 그러므로 각 노드는 라인별로 구성되어야 합니다. LSP *lspnode[SCREEN_YSIZE] 이렇게 이중 포인터로 각 라인의 첫 노드들을 저장해 주어야 합니다. 그렇게 노드를 구성해 놓으면 나머지는 만사해결되지요. 일단 13h라고 가정합니다. ( 각 라인은 320바이트겠죠 ?) void PutScreen() { char *video = (char*)0xa0000; // 보호모드가 아니면 0xa0000000l LSP *node; int i,j; for(j=0; jaddress, node->length); i += node->length; node = node->next; } } } 위의 단순 루틴이 출력 루틴의 전부입니다. 4. 노드 삽입은 ? 노드 삽입은 몇가지로 구분할 수 있습니다. 하나씩 살펴보죠. 기존 aaaabbbb : (a', 4), (b', 4) 삽입 CCCC 결과 aaCCCCbb : (a', 2), (C', 4), (b'+2, 2) ( aaaa영역의 가장 처음 어드레스를 a'라 표시. 각 노드는 (주소, 길이)로 표시했음. ) 위의 것은 가장 기본적인 루틴이지요. 중간에 삽입해주면 됩니다. 앞의 노드는 길이가 줄어들겠고 뒤의 노드는 길이는 줄어들고 시작포인터는 증가하지요. 새로운 노드 C를 삽입해도 길이는 8임에도 주목하시길... 기존 aaaabbbbccccdddd : (a', 4), (b', 4), (c', 4), (d', 4) 삽입 CCCCCCCCCCCC 결과 aaCCCCCCCCCCCCdd : (a', 2), (C', 12), (d'+2, 2) 이번 경우는 사실상 처음의 경우와 같은 경우입니다. 단지 처음 노드 삽입 예는 중간에 지나보낸 노드들이 없는 거지요. 이번 경우는 b,c노드는 필요가 없기 때문에 이탈되게 되는 거지요. ( 더이상 쓸모없는 노드라는 소리죠. ) 기존 aaaaaaaa : (a', 8) 삽입 CCCC 결과 aaCCCCaa : (a', 2), (C', 4), (a'+6, 2) 이번 경우는 삽입할 노드외에도 새로운 노드를 하나 만들어서 뒤에 갖다 붙여야 합니다. 세밀히 분석해보면 결국 두경우(앞의 두개는 같은 경우로 봄)가 노드삽입의 핵심이 됨니다. 더 이상의 경우는 생각 안해도 된다는 거지요. 그냥 노드의 시작이 일치하거나 같이 끝나는 경우같은 자잘한 처리까지 고려는 해야겠지요. 기존 aabbbb : (a', 2) (b', 4) 삽입 CCCC 결과 CCCCbb : (C', 4), (a'+6, 2) 이런 경우가 그런 경우중 하나 인데... 어떻게 보면 새로운 형태 같지만 결국은 (a', 0)이 있다고 생각해보면 젤 첨의 경우과 같지요. (물론 길이가 0인 노드는 버려야 겠지요. ) 기존 aaaaabbbbddddeeeeffffgggg 삽입 CC 결과 aaaaabbbbddddeeeeffffggCC 이와 같은 경우는 사실상 앞부분은 생각할 필요가 없고 뒤에 기존 gggg 삽입 CC 결과 ggCC 이 부분만 주목하면 됩니다. 마찬가지로 뒷부분은 생각안해도 되겠죠 ? 소스화 하면 다음과 같습니다. ( 몇번 다듬은 소스이니 덩어리로 이해해주세요. ) void AddLsp(int x, int y,short length, char *address) { if (y < 0 || y >= SCREEN_YSIZE) // 클리핑 (5번 질문 참고) return; // // int x2 = min(SCREEN_XSIZE, x +length); // int x1 = max(x, 0); // // if (x1 != x) // address += x1 - x;// LSP *node = lspnode[y]; // 현라인의 새노드 for(x=node->length; xnext; x += node->length; } node->length -= x - x1; // 앞노드 길이 줄이기 LSP *next = AllocNode(); // 삽입할 노드만들기 next->length = x2 - x1; // next->address = address; // next->next = node->next; // 뒷노드와 연결 node->next = next; // 앞노드와 연결 if(x > x2) { // 자투리노드 생성여부검사 LSP *dumy = AllocNode(); // 자투리노드 만들기 dumy->address = node->address + node->length + (x2 - x1); dumy->length = x - x2; // dumy->next = next->next; // 자투리와 뒷노드 연결 next->next = dumy; // 삽입노드와 자투리 연결 } else { if(x == SCREEN_XSIZE) // 마지막 노드이면 끝냄 return; LSP *dumy = next->next; for(x += dumy->length; x<=x2;) { // 이탈할 노드 skip dumy = dumy->next; x += dumy->length; } int gap = x2 - (x - dumy->length); // 뒷노드 줄이기 dumy->address += gap; // 어드레스 증가 dumy->length -= gap; // 길이감소 next->next = dumy; // 삽입노드와 뒷노드 연결 } // 이탈노드가 있으면유효 if(node->length == 0) memcpy(node, next, sizeof(LSP)); // 길이 0노드 삭제 } 먼저 화면을 SCREEN_XSIZE인 노드로 꽉 채운후에 스프라잇을 쭉쭉 삽입하면 되지요 이미지를 뿌리는 루틴도 아래와 같아 지겠죠 ? void PutImage(int x, int y, char *address, int xs, int ys) { int y2 = y+ys; for (; ylength=SCREEN_XSIZE; empty->address=(char*)0xa0000; // 어떤값이든 상관은 없음 lspnode[i]=empty; // 각라인에 초기값 } 5. 클리핑은 ? 위의 소스에 나타난 것을 먼저 보죠. if (y < 0 || y >= SCREEN_YSIZE) return; int x2 = min(SCREEN_XSIZE, x + length); int x1 = max(x, 0); if (x1 != x) address += x1 - x; 먼저 y가 화면의 위나 아래 라인이라면 만들 필요가 없을 것입니다. ------+ CCCCC CCC 위와 같이 화면을 넘어가는 부분은 잘라주면 될 것입니다. 뭐 단순히 가로 길이만 줄여 주면 되겠죠 ? +------ CCCC CC 이와 같이 좌측으로 넘어간 경우에는 길이도 줄여주고 어드레스도 증가 시켜 주어야 합니다.이런 것들을 다듬으면(?) 위의 클리핑 루틴이 되는 거죠. 이렇게 화면 넘어가는 부분을 잘라버리고 그 노드를 삽입하면 됩니다. LSP의 장점중의 하나가 클리핑이 자동으로 된다는 건데... 위와 같이 약간만 계산해주면 어떤 경우건간에 클리핑을 생각할 필요가 없습니다. 캐릭터가 넘어가건 화면에 걸치건 간에 말이죠. ( 사실 클리핑이란게 그런거지만... ^^; )