2012년 3월 9일 금요일

VC7에 포함된 STL string의 할당 구조

간만에 Effective STL책을 다시 보면서..... 심심했던걸까나...쩝.

Visual Studio 2003으로 테스트 해본다..

VC6.0이나 다른 상위버전은 테스트 안해봐서 모르겠다..쩝 귀챠나서..



std:: string s1;
int nSize = sizeof(s1);



위와 같이 대충 끄적대고 나서.. 브레이크를 걸어보자..
nSize값은 28을 가지고 있다.



Watch창에서 s1을 살펴보면 다음과 같이 구성되어 있다.


  s1
   +--- std::_String_val<char,std::allocator<char>>
   |    (STL의 기본 Allocator)
   +--- _Bx
   |    (문자열 데이터의 정보)
   +--- _Mysize
   |    (문자열의 길이)
   +--- _Myres
        (컨테이너의 할당된 메모리 크기)

     
여기서 _Bx라는 넘을 살펴보면(xstring파일 참고) 아래과 같은 union으로 되어 있다.



union _Bxty
{ // storage for small buffer or pointer to larger one
     _Elem _Buf[_BUF_SIZE];
     _Elem *_Ptr;
} _Bx;



* _BUF_SIZE는 16으로 설정되어 있다.


대강 봐도 string의 데이터가 _BUF_SIZE보다 작으면 _Buf배열 안에..
크면 _Ptr의 포인터에 설정되게 구성되었으리라 판단된다..


테스트 해보니. 실제로 그렇다.. ^^;



string이 생성되면 문자열 데이터의 개수가 _BUF_SIZE 보다
작으므로(당연히) _Bxty._Buf[0]은 NULL값을 가지며 _Myres는 15라는 값을 가지게 된다.


그럼 15보다 큰 값을 넣어주면 어떻게 될까..
당연히 배열인 _Bxty._Buf는 무시되고 _Bxty._Ptr에 메모리가 할당되어 사용되어 진다.


그런데 _Myres값은 어떻게 변할까?.. 다시 말하면 할당되는 메모리의 최대 크기는
얼마씩 설정될까..?



20개의 문자열을 할당하고 테스트 해보면
_Myres의 값은 31의 값을 보여주게 된다. 즉 32byte가 할당되었다.
처음 16byte에서 단순이 2배로 설정한것일까?



이번엔 35개의 문자열을 할당하고 테스트 해보면
_Myres의 값이 47의 값을 보여주게 된다. @,@   63이 아니다.. ㄷㄷㄷ
배수로 늘어나는 것이 아님을 보여준다...



stirng의 _Copy함수를 열어보면 그속에 답이 있다.


메모리를 재할당하는 과정에서 아래와 같은 size를 계산하는
단순하고도 오묘한? 수식을 볼 수 있다.



size_type _Newres = _Newsize | _ALLOC_MASK;



위에서 _Newsize는 새로 배정한 문자열의 길이이며..즉 35라는 값이 들어온다.
_ALLOC_MASK값은 15로 설정되어 있다.


이 수식에 의해 47이라는 값이 _Newres에 설정되고 이 크기만큼 할당되게 되는것이다.
뭐 나름대로 깊은 뜻이 있으리라.. 생각하자.~



* resize로 다른 값을 설정해서 같은 현상이 나타난다. 쩝.



참고로 다른 라이브러리는 reference count처리를 한다고 하지만 VC7에 포함된 STL string은
그러한 기능은 없는것 같다. ref count가 보이지 않고.. 테스트 해봐도 마찬가지..

VC7에 포함된 STL set의 데이터 할당 구조

std::set<int> setData;

int nSize = sizeof(setData);
int nNodeSize = sizeof(*listData._Myhead);



nSize의값은 12라고 나타난다.
nNodeSize의값은 20이라고 나타난다.

watch창을 살펴보쟈..



setData
  +-- allocator..
  +-- _Myhead
  |      +-- _Left      // left subtree, or smallest element if head
  |      +-- _Parent    // parent, or root of tree if head
  |      +-- _Right     // right subtree, or largest element if head
  |      +-- _Myval     // the stored value, unused if head
  |      +-- _Color     // _Red or _Black, _Black if head
  |      +-- _Isnil     // true only if head (also nil) node
  +-- _Mysize



알다시피 set컨테이너는 balance 2진트리 구조를 가지고 있다.
데이터 노드는 Left,Right 그리고 Parent를 가지고 있게 될 것이다.


xtree라는 파일을 열어 set컨테이너의 초기화 함수를 살펴보자..


void _Init()
{ // create head/nil node and make tree empty
 _Myhead = _Buynode();
 _Isnil(_Myhead) = true;
 _Root() = _Myhead;
 _Lmost() = _Myhead, _Rmost() = _Myhead;
 _Mysize = 0;
}


set 역시 최초에 head-node를 생성시킨다.(생성시 _Color값은 _Black로 _Isnil은 false로 설정된다)

이 노드는 데이터가 없으므로 _Isnil을 true로 설정.
이 노드가 루트노드로 설정한다.(위 코드를 풀어쓰면.. _Myhead->_Parent = _Myhead;  와 같다.)
좌측 서브 노드와 우측 서브노드 역시 자신으로 설정한다.
Size를 0으로 셋팅.


이 node의 left,right,parent모두 head-node의 주소를 가르키고 있다.


데이터를 여러개 넣은 뒤 데이터의 구조를 살펴보면 간단한 특징을 확인할 수 있다.


head-node의 parent는 트리의 루트를 가르킨다.
head-node의 left-node는 최좌측 노드를 가르킨다.(가장 적은 숫자)
head-node의 right-node는 최우측 노드를 가르킨다.(가장 큰 숫자)



* _Color 값은 tree를 구축할때 사용되어지는것 같다...

VC7에 포함된 STL list의 데이터 할당 구조

어디 까지나 VC7의 STL에만 해당되는 얘기지.. 다른 라이브러리는 검토한바 없으므로..

참고용으로만 알고 있자~.. ㅋㅋ



기본생성자에 의해 리스트 컨테이너가 만들어지면
최초 head-node가 1개 자동으로 만들어진다.



물론 노드안에는 짐작하는것과 같이 link 구조를 유지하기 위한
prev, next node를 가르키는 포인터 변수가 존재한다.
물론 데이터를 담기 위한 _Myval이라는 넘도 존재한다.


std::list<int> list1;



list를 하나 만들고 watch창으로 확인해보자..



list1
  |
  +-- allocator..
  |
  +-- _Myhead
  |      |
  |      +-- _Next
  |      |
  |      +-- _Prev
  |      |
  |      +-- _Myval
  |       
  +-- _Mysize



아무런 데이터가 없는 상태에서는 _Myhead의 주소와 _Next, _Prev의 주소가 같은것을 볼 수 있다.
물론 _Mysize는 0이다.



한개의 노드를 추가해보자.


list.push_back(100);


_Next, _Prev의 주소가 새로 추가된 노드의 주소로 변경된것을 확인할 수 있을것이다.
물론 _Mysize는 1로 바뀌었다



몇개의 노드를 더 추가해보고 살펴보면 링크 구조에서
Prev-node가 없거나 Next-node가 없을경우는 모두
처음에 생성한 head-node의 주소를 가르키는것을 확인할 수 있다.



어찌 보면 head-node가 연결되어 node들이 circle구조처럼 보일수도 있지만.
head-node의 기능은 end iterator의 기능일 뿐이니 오해하지 말자~.



다시 말해

list.begin()은 head-node의 next가 되는것이고
list.end()은 head-node 자신이 된다는 얘기이다..

VC7에 포함된 STL deque의 데이터 할당 구조

VC7.0의 STL 기준으로..~ 다른 버전도 크게 다르지 않을꺼라 본다.~


deque는 내부적으로 고정된 크기의(16byte) 맵형식으로 처리한다.(포인터 배열)

*여기서 맵은 의미상 이름이고.. 그냥 하나의 할당된 메모리 블럭이라고 생각해도 무관하리라 본다.


데이터 타입 / 16 == 1개 맵에 담을수 있는 데이터 개수

deque에 push_front()와 push_back()명령이 이루어지면 내부적으로 2개의 맵이 생성되어진다.

push_back은 맵의 앞부분 부터 채워지고

push_front는 맵의 뒷부분 부터 채워진다.

채워지는 방향에 따라 다른 맵을 생성하므로 2개가 만들어진다...

당연한 얘기지만 내부에 적재되는 데이터가 많아지면 여러개의 맵이 생성되고 데이터가 누적되어 진다.
만약 데이터의 타입의 크기가 8보다 크다면 1개의 데이터 당 1개의 맵을 차지하게 된다.~

원도 프로그램에서 Consol Process Output캡춰하기

bool ExecuteNonConsolProcess(std::string sExeName, std::string sArguments) {
std::string sExecute = sExeName;
sExecute += " ";
sExecute += sArguments;

HANDLE hReadPipe, hWritePipe;

SECURITY_ATTRIBUTES securityAttr;
ZeroMemory( & securityAttr, sizeof(securityAttr));
securityAttr.nLength = sizeof(securityAttr);
securityAttr.bInheritHandle = TRUE;

CreatePipe( & hReadPipe, & hWritePipe, & securityAttr, 0);

STARTUPINFO sStartupInfo;
PROCESS_INFORMATION process_Info;
ZeroMemory( & sStartupInfo, sizeof(sStartupInfo));
ZeroMemory( & process_Info, sizeof(process_Info));

sStartupInfo.cb = sizeof(STARTUPINFO);
sStartupInfo.dwFlags = STARTF_USESTDHANDLES;
sStartupInfo.hStdInput = NULL;
sStartupInfo.hStdOutput = hWritePipe;
sStartupInfo.hStdError = hWritePipe;

BOOL bSuccessProcess = CreateProcess(0, (char * ) sExecute.c_str(), 0, 0, TRUE, NORMAL_PRIORITY_CLASS | CREATE_NO_WINDOW,
0, 0, & sStartupInfo, & process_Info);
CloseHandle(hWritePipe);

if (FALSE == bSuccessProcess) {
CloseHandle(hReadPipe);
return false;
}

char szTemp[260];
DWORD dwReadByte;
std::string sOutputString;
sOutputString.clear();

BOOL bResult;
do {
ZeroMemory(szTemp, sizeof(szTemp));
bResult = ::ReadFile(hReadPipe, szTemp, sizeof(szTemp) - 1, & dwReadByte, 0);

if (TRUE == bResult) {
TRACE("%s", szTemp);

sOutputString += szTemp;
}
} while (TRUE == bResult);

CloseHandle(hReadPipe);

return true;
}

유용한 STL알고리즘

fill
주어진 초기값으로 벡터를 채운다.

copy
수열을 복사한다. 

generate
발생기(generator)가 생성한 값을 벡터에 집어넣는다.

find
조건을 만족하는 원소를 찾는다. 

adjacent_find
연속적으로 중복된 원소를 찾는다. 

search
벡터내에서 서브 시퀀스를 찾는다.

max_element, min_element
최대 또는 최소 원소를 찾는다.

reverse
원소의 순서를 뒤집는다.

replace
원소들을 새로운 값들로 대치한다.

rotate
가운데점을 중심으로 원소들을 순환시킨다.

partition
원소들을 두그룹으로 쪼갠다.

next_permutation
순열(permutation)을 생성한다.

random_shuffle
벡터내의 원소들을 임의로 섞는다.

count
조건을 만족하는 원소들의 갯수를 센다. 

accumulate
벡터로부터의 정보를 가지고 하나의 값을 만들어 낸다.

inner_product
두 벡터의 내적을 구한다.

equal
두벡터를 한쌍씩 비교하여 같은지를 검사한다.

lexicographical_compare 
사전식 비교 

transform
벡터에 변환을 적용한다.

partial_sum
값들의 부분합을 구한다.

adjacent_difference
이웃하는 값들의 차를 구한다.

for_each
각 원소들에 대해 함수를 수행한다.

2011년 5월 3일 화요일

OpenGL ES ?

OpenGL ES ?
Opengl ES는 로열티가 없고, 크로스플렛폼을 지원하는 API 이며, 임베디드 시스템에서의 2D, 3D를 위한 모든 기능을 제공한다.
(그래픽 가속기와 소프트웨어 사이에 강력한? Low-level 인터페이스(API)를 지원)


OpenGL ES는 OpenGL에 포함된 함수 중에서 임베디드 기기에서 사용할만한 것만 간추려놓은 서브셋이라 보면 된다.
그리고 OpenGL ES는 1.x와 2.x로 나누어진다.
이들은 다른 API로서 2.x가 1.x의 버전업이 아니다.
둘 다 OpenGL의 서브셋이지만,
1.x는 고정(Fixed) Pipeline구조를 사용하고 2.x은 프로그램가능(Programmable) Pipeline구조를 사용 한다.
(1.x API 로 구현한 프로그램은 2.x과 그 API 명령과 사용방법이 서로 달라 직접적인 호환이 되지 않는다. )


고정 파이프라인 방식(1.x)은 렌더링 파이프 라인 전체에 대해 하드웨어 틀을 만들어 놓고
사용자가 임의의 값(좌표,색상,텍스쳐 정보 등..)을 입력할 수 있게 한 것이며,


프로그램가능 파이프라인은 사용자가 이 틀 중 일부를 구성할 수 있게 만든 것/
이 틀을 구성하기 위해 사용되는 언어가 Shader Language!!
(쉐이더 언어는 GPU에서 인식가능한 언어/형태로 컴파일되어 GPU 안에서 동작한다.)


1.x상에서는 고정된 틀만 제공하기 때문에 조명식이 Flat/ Gouraud/ Phong으로 한정되어
고정된 수식에 대한 값만 변경할 수 있다.
(퐁 쉐이더는 연산이 너무 많아 일반적으로 고로쉐이더를 많이 사용. / 2D만 사용한다면 필요 없음)


그러나 2.x상에서는 파이프라인 틀을 변경할 수 있으므로 조명 수식자체를 변경할 수 있어
카툰렌더링과 같은 조명식을 구성할 수 있다.
(Vertex Shader : 정점 쉐이더,  Pixel Shader : 픽셀 쉐이더)
(프로그래밍 파이프 라인에 적용한 Flat/ Gouraud/ Phong쉐이딩을 구현한 소스코드는 쉽게 찾을 수 있다.)


참고 : 안드로이드는 JNI를 통해 해당 API function을 호출하게 된다. 매  프레임을 찍을 때마다...
JNI의 function call메커니즘으로 인한 overhead로 성능 최적화의 한계가 있다.. (해결책 : NDK?)


OpenGL ES 의 특징?
결코 객체지향적인지 않다.. 완전 절차적...  
(DX 처럼 C++의 인터페이스를 사용하는 방식이 아니라.  순수한Api 함수 형태로만 구성)
Opengl ES은 state machine 구조로 구동된다.
다양한 상태 정보를 설정하게금 되어 있어  설정한 상태가 계속 유지된다.
(예 : glEnable(); glDisable(); glMatrixMode(); glViewport(); glVertexPointer(); ......)


OpenGL ES가 사용되고 있는 Device들
OpenGL ES 1.0
Android와 Symbian에서 사용
QNX지원


OpenGL ES 1.1
Android 1.6 지원
iOS for iPad , iPhone , and iPod Touch 지원
BlackBerry 5.0 지원
Palm webOS지원
Nintendo 3DS 지원


OpenGL ES 2.0
iPad , iPhone 3GS 이상, iPod Touch 3세대 이상 지원
Android platform 2.2 이상 지원
Android platform NDK 2.0 이상 지원
삼성 Wave폰 지원
Palm webOS 지원


CPU와 GPU 간의 데이터 처리


CPU와 GPU 의 차이
근본적인 차이는 병렬화 처리!
GPU는 기본이 스트리밍 데이터의 처리이므로 병렬처리가 용이하다.
멀티 쓰레드로 처리를 진행 시키는것도 CPU에 비해 쉽고 한 클럭에 다수의 정점과 픽셀의 처리를 병행할 수 있다.


비디오메모리
GPU입장에서 접근 가능한 하드웨어 메모리는  AGP와 VRAM으로 구분된다.(적어도 PC구조에서는 그러함)
일반적으로 비디오 메모리란. 이 AGP+VRAM을 뜻하는 의미이다.
AGP 메모리는 System RAM 의 일정부분을 빌려서 GPU 가 접근 가능하도록 특화된 메모리 영역이다.
AGP 메모리의 태생은 역시 오래 전 컴퓨터의 VRAM 의 부족으로 인해 탄생되었다고 함
AGP 영역은 GPU 가 접근이 용이하도록 독립된 데이터 버스를 이용.
일반적인 메모리 데이터 전송보다는 상당히 빠르고 VRAM보다는 성능이 떨어진다고 할 수 있음.


* GPU라는 용어는 nVIDIA가 1999년 지포스 그래픽 카드를 발표하면서 제창한 용어란다.
(이전엔 그래픽 컨트롤러라고 불렀다나..)


렌더링 파이프라인
3D 장면을 2D 화면에 출력하기 위한 일련의 과정을 렌더링 파이프라인이라 한다.


Local Space(로컬 스페이스, Model 좌표계)
오브젝트를 이루는 정점들의 좌표


World Space(월드 스페이스)
렌더링 오브젝트를 월드 좌표계로 옮긴다.
오브젝트의 이동, 회전, 스케일 메트릭스가 적용된다.


View Space(뷰 스페이스)
월드 스페이스 내의 카메라 위치를 원점으로 이동, 모든 오브젝트 이동


Back Sapce Culling(후면 추려내기)
폴리곤의 전면/후면중에 후면을 추려낸다. 보여주지 않는다. 그리기 연산을 하지 않는다.
정점 두르기 순서에 따라 전면, 후면 결정


Lighting(조명)
광원백터, 시선백터, 법선백터 등 조명 계산식을 이용해 정점의 색상 계산


Tesselation(테셀레이션)
GPU에서 정점을 자유자재로 증감 및 감소 처리(폴리곤의 세분화)


Vertex Shader(정점 쉐이더)
폴리곤의 버텍스에 대한 값(좌표, 색 등)을 바꿀 수 있는 처리


Clipping(클리핑)
시야 볼륨(범위, 카메라에서 보이지 않는 방향) 외부의 물체를 추려내다.
반대방향은 어차피 그려도 보이지 않음.


Projection(투영) : 3D장면을 2D 표현 , n차원에서 n-1차원을 얻는 과정,
직교투영(Perspective Projection)
영역 내에 있는 모든 물체들이 거리에 관계없이 모두 같은 크기 비율로 표현


원근투영(Perspective Projection)
물체가 얼마나 가까이 또는 멀리 있는가에 따라 2D 화면에 나타나는 크기가 달라지게 된다


Viewport(뷰포트) 변환, Screen Mapping
화면의 지정된 직사각형 틀에 출력하도록 한다. (화면전체, 원도우 영역, 일부분)


Rasterizing(래스터 라이징), Triangle setup
렌더링 데이터들을 모니터상의 픽셀단위 점으로 표현하기 위해 계산하는 과정
픽셀의 위치 및 정점 컬러에 따른 그라데이션 컬러 적용


Pixel Shader(픽셀 쉐이더), Texture Mapping, 텍스쳐 적용
출력될 픽셀이 결정된 상태에서  빛 계산에 의한(쉐이딩) 정밀한 효과 처리, Pixel Shader(픽셀 쉐이더)
텍스쳐 적용이 여기서 이루어 진다.


Alpha Test / Alpha Blending(알파 테스트/ 알파 블렌딩)
출력 오브젝트의 투명 단계 조절 및 기 그려진 오브젝트와의 블렌딩 처리를 수행


Z-Test(깊이 테스트)
오브젝트의 앞/뒤를 판별


Stencil Test(스텐실 테스트)
오브젝트에 의한 특정 영역 추출. 해당 영역만 그리거나 안그리거나하는 마스킹 처리


Fog(안개)
안개 색상 처리..
Anti-aliasing(안티알리어싱)


칩셋 및 라이브러리 종류, 버전에 따라 렌더링 파이프라인이 차이가 있음.
OpenGL : ?
OpenGL ES : ?
Direct3D : ?


기초 기식


왼손? 오른손 ? 좌표계


정점?
점은 정점(Vertex) 라고 부르는 부동 소수점 수들의 집합으로 표현한다. 모든 점은 3차원으로 저장된다.
2차원으로 지정해도 z=0의 값을 가지게 된다.
(부동 소수점 사용 : float)
- 부동소수점 사용으로 수치적 오차가 발생될 수 있음을 유념해야 한다.
- 부동소수점 연산의 H/W를 통한 가속 지원 GPU


선은 당연히 직선이 아니라 선분이다. 양쪽끝에 정점을 가지고 있다는 뜻이다.


폴리곤
선들을 연결하여 닫힌 도형을 만들면 바로 폴리곤이 된다.(기본 폴리곤은 삼각형)
* 고사양 게임의 경우 비디오 칩셋의 성능에 따라 동시 출력 폴기곤의 개수를 조정하기도 한다.


백터(Vector)
백터는 정점의 좌표 정보를 가지고 있다.
- 백터의 크기 : V = sqrt(V.x * V.x + V.y * V.y)


- 백터의 정규화(일반와, 법선백터, normal vector) : V = 1 / sqrt(V.x * V.x + V.y * V.y) * V
백터의 크기가 1로 계산한 백터


- 백터의 내적(dot product, scalar product, inner product) : n = (A.x * B.x) + (A.y * B.y)
(두백터의 각 성분을 곱한 뒤 모두 더한 값, 결과값이 스칼라..)
다른 식 :  A백터의 길이 * B백터의 길이 * 두백터의 코사인 값   ||A|| ||B|| cos(Θ)
내적은 백터의 방향 및 각도를 얻는데 활용
값이 0이면 두 백터는 수직 관계
값이 0보다 크면 두 백터간 각도는 90보다 작다
값이 0보다 작으면 두 백터간 각도는 90보다 크다
각도 : arcos(백터의 내적 / (A백터의 길이 * B백터의 길이))
내적 용도 : 조명 계산, 좌표계 변환, 컬링


- 백터의 외적(cross product, vector product) : N = A x B = [ (AyBz – AzBy), (AzBx – AxBz), (AxBy – AyBx) ]
외적크기 : ||W|| = ||A|| ||B|| sin(Θ)
외적 = 외적크기 * (A와B에 수직인 단위백터)
A x B = 오른손을 엄지만 편 상태에서 A->B방향으로 엄지를 제외한 손가락을 같은 방향으로 향하게 했을 때 엄지의 방향이 외적 백터가 된다.(결과값은 백터..)
두 백터에 모두 수직한 한 백터를 구해낸다.(B x A 의 외적은 반대 방향이 된다)
법선 백터(수직백터)를 구하는데 주로 사용 : 물체의 면마다 반사되는 빛 계산, 충돌 체크, 컬링 등에 활용
삼각형 면적계산에도 활용 : ( ||A x B|| * A ) / 2


참고(백터의 연산 소스 일부.)

백터 곱
public static GVector3 GVec3Multiply(GVector3 pVtOut, GVector3 vVector1, GVector3 vVector2)
{
pVtOut.x = vVector1.x * vVector2.x;
pVtOut.y = vVector1.y * vVector2.y;
pVtOut.z = vVector1.z * vVector2.z;
return pVtOut;
}

행렬에 의한 백터값 변환처리
static float g_x, g_y, g_z, g_w;
public static GVector3 GVec3TransformCoord(GVector3 pVtOut, GVector3 pVtIn, GMatrix pMatIn)
{
if(null == pVtOut || null == pVtIn || null == pMatIn)
return null;
g_x = pVtIn.x * pMatIn.m[0][0] + pVtIn.y * pMatIn.m[1][0] + pVtIn.z * pMatIn.m[2][0] + pMatIn.m[3][0];
g_y = pVtIn.x * pMatIn.m[0][1] + pVtIn.y * pMatIn.m[1][1] + pVtIn.z * pMatIn.m[2][1] + pMatIn.m[3][1];
g_z = pVtIn.x * pMatIn.m[0][2] + pVtIn.y * pMatIn.m[1][2] + pVtIn.z * pMatIn.m[2][2] + pMatIn.m[3][2];
g_w = pVtIn.x * pMatIn.m[0][3] + pVtIn.y * pMatIn.m[1][3] + pVtIn.z * pMatIn.m[2][3] + pMatIn.m[3][3];

pVtOut.x = g_x / g_w;
pVtOut.y = g_y / g_w;
pVtOut.z = g_z / g_w;

return pVtOut;
}

백터의 길이 계산
public static float GVec3Length(GVector3 vVector)
{
return (float) Math.sqrt((vVector.x * vVector.x) + (vVector.y * vVector.y) + (vVector.z * vVector.z));
}

두 백터의 길이 계산
public static float GVec3Length(GVector3 vVector1, GVector3 vVector2)
{
g_x = vVector2.x - vVector1.x;
g_y = vVector2.y - vVector1.y;
g_z = vVector2.z - vVector1.z;

return (float) Math.sqrt(g_x * g_x + g_y * g_y + g_z * g_z);
}


백터 외적
public static GVector3 GVec3Cross(GVector3 pVtOut, GVector3 vVector1,
GVector3 vVector2)
{
pVtOut.x = vVector1.y * vVector2.z - vVector1.z * vVector2.y;
pVtOut.y = vVector1.z * vVector2.x - vVector1.x * vVector2.z;
pVtOut.z = vVector1.x * vVector2.y - vVector1.y * vVector2.x;

return pVtOut;
}

백터 내적
public static float GVec3Dot(GVector3 vVector1, GVector3 vVector2)
{
return ((vVector1.x * vVector2.x) + (vVector1.y * vVector2.y) + (vVector1.z * vVector2.z));
}

백터 정규화
public static GVector3 GVec3Normalize(GVector3 pVtOut, GVector3 vNormal)
{
float fMagnitude = (float) Math.sqrt((vNormal.x * vNormal.x)
+ (vNormal.y * vNormal.y) + (vNormal.z * vNormal.z));

pVtOut.x = vNormal.x / fMagnitude; // Divide the X value of our normal
pVtOut.y = vNormal.y / fMagnitude; // Divide the Y value of our normal
pVtOut.z = vNormal.z / fMagnitude; // Divide the Z value of our normal

return pVtOut; // Return the new normal of length 1.
}

아래 함수 보조
private static float _inTriangleFunc(GVector3 vt1, GVector3 vt2, GVector3 vt3)
{
return ((vt3.x - vt1.x) * (vt1.y - vt2.y) - (vt3.y - vt1.y) * (vt1.x - vt2.x));
}

3개의 백터로 구성된 Triangle 폴리곤에 지정된 1개의 백터가 교차 되는지 판별(ray point 판별, 마우스클릭)
static float g_fTemp1, g_fTemp2;
public static boolean isInTriangle(GVector3 vt1, GVector3 vt2, GVector3 vt3, GVector3 vtFind)
{
g_fTemp1 = _inTriangleFunc(vt1, vt2, vt3);
g_fTemp2 = _inTriangleFunc(vt1, vt2, vtFind);
if((g_fTemp1 * g_fTemp2) <= 0.0)
return false;
g_fTemp1 = _inTriangleFunc(vt2, vt3, vt1);
g_fTemp2 = _inTriangleFunc(vt2, vt3, vtFind);
if((g_fTemp1 * g_fTemp2) <= 0.0)
return false;
g_fTemp1 = _inTriangleFunc(vt3, vt1, vt2);
g_fTemp2 = _inTriangleFunc(vt3, vt1, vtFind);
if((g_fTemp1 * g_fTemp2) <= 0.0)
return false;

return true;
}

3개의 백터로 구성된 베지어 곡선
// fMu : 0.0f ~ 1.0f
public static GVector3 GVec3Bezier3(GVector3 pVtOut, GVector3 vVector1, GVector3 vVector2, GVector3 vVector3, float fMu)
{
float fMum1, fMum12, fMu2;

fMu2 = fMu * fMu;
fMum1 = 1.0f - fMu;
fMum12 = fMum1 * fMum1;

pVtOut.x = vVector1.x * fMum12 + 2 * vVector2.x * fMum1 * fMu + vVector3.x * fMu2;
pVtOut.y = vVector1.y * fMum12 + 2 * vVector2.y * fMum1 * fMu + vVector3.y * fMu2;
pVtOut.z = vVector1.z * fMum12 + 2 * vVector2.z * fMum1 * fMu + vVector3.z * fMu2;
return pVtOut;
}

4개의 백터로 구성된 베지어 곡선
// fMu : 0.0f ~ 1.0f
public static GVector3 GVec3Bezier4(GVector3 pVtOut, GVector3 vVector1, GVector3 vVector2, GVector3 vVector3, GVector3 vVector4, float fMu)
{
float fMum1, fMum13, fMu3;

fMum1 = 1.0f - fMu;
fMum13 = fMum1 * fMum1 * fMum1;
fMu3 = fMu * fMu * fMu;

pVtOut.x = fMum13 * vVector1.x + 3 * fMu * fMum1 * fMum1 * vVector2.x + 3 * fMu * fMu * fMum1 * vVector3.x + fMu3 * vVector4.x;
pVtOut.y = fMum13 * vVector1.y + 3 * fMu * fMum1 * fMum1 * vVector2.y + 3 * fMu * fMu * fMum1 * vVector3.y + fMu3 * vVector4.y;
pVtOut.y = fMum13 * vVector1.z + 3 * fMu * fMum1 * fMum1 * vVector2.z + 3 * fMu * fMu * fMum1 * vVector3.z + fMu3 * vVector4.z;
return pVtOut;
}


백터1 에서 백터2 방향으로 지정된 거리 지점의 위치 백터를 구해낸다.
public static GVector3 GVec3PointOnHypotenuse(GVector3 pVtOut, GVector3 vVector1, GVector3 vVector2, float fDistance)
{
float fDx = vVector2.x - vVector1.x;
float fDy = vVector2.y - vVector1.y;

float fLineLength = (float) Math.sqrt(fDx * fDx + fDy * fDy);
float fScale = fDistance / fLineLength;
pVtOut.x = vVector1.x + fDx * fScale;
pVtOut.y = vVector1.y + fDy * fScale;
pVtOut.z = 0;
return pVtOut;
}

백터1와 백터2에 직각이고 백터3에서 시작되는 새로운 백터 만들어낸다.(fNorm이 0이면 오른손법칙, 아니면 왼손)
public static GVector3 GVec3RightAnglePt(GVector3 pVtOut, GVector3 vVector1, GVector3 vVector2, GVector3 vVector3,
float fDistance, float fNorm)
//pt1:Object,pt2:Object,pt3:Object,newpt:Object,distance,norm:int=0)
{
GVector3 vtTemp = new GVector3(vVector1.x - vVector2.x, vVector1.y - vVector2.y, 0);

GVec3Normalize(vtTemp, vtTemp);

if (fNorm==0)
{
vtTemp.x=-vtTemp.x;
}
else
{
vtTemp.y=-vtTemp.y;
}
   
GVector3 vtNormalTemp = new GVector3(vtTemp.x, vtTemp.y, 0);
   
pVtOut.x = vVector3.x + vtNormalTemp.x * fDistance;
pVtOut.y = vVector3.y + vtNormalTemp.y * fDistance;
pVtOut.z = 0;

return pVtOut;
}

백터1와 백터2를 잇는 선분에 백터3이 직각으로 교차하게 되는 지점의 백터 반환
public static GVector3 GVec3PointToLine(GVector3 pVtOut, GVector3 vVector1, GVector3 vVector2, GVector3 vVector3)
{
float dx = vVector2.x - vVector1.x;
float dy = vVector2.y - vVector1.y;
if (dx == 0 && dy == 0)
{
pVtOut.x = vVector1.x;
pVtOut.y = vVector1.y;
pVtOut.z = 0;
}
else
{
float t = ((vVector3.x - vVector1.x) * dx + (vVector3.y - vVector1.y) * dy) / (dx * dx + dy * dy);
pVtOut.x = vVector1.x + t * dx;
pVtOut.y = vVector1.y + t * dy;
pVtOut.z = 0;
}
return pVtOut;
}

백터1과 백터2를 잇는 선분과 백터3, 백터4를 잇는 선분이 교차하는 지점의 백터값 반환
public static GVector3 GVec3Intersection(GVector3 pVtOut, GVector3 vVector1, GVector3 vVector2, GVector3 vVector3, GVector3 vVector4)
{
 float a1, a2, b1, b2, c1, c2;

 a1 = vVector2.y - vVector1.y;
 b1 = vVector1.x - vVector2.x;
 c1 = vVector2.x * vVector1.y - vVector1.x * vVector2.y;
 
 a2 = vVector4.y - vVector3.y;
 b2 = vVector3.x - vVector4.x;
 c2 = vVector4.x * vVector3.y - vVector3.x * vVector4.y;

 float fDenominator = a1 * b2 - a2 * b1;
 if(0 == fDenominator)
 {
 pVtOut.x = 0;
 pVtOut.y = 0;
 pVtOut.z = 0;
 return pVtOut;
 }
 
 pVtOut.x = (b1 * c2 - b2 * c1) / fDenominator;
 pVtOut.y = (a2 * c1 - a1 * c2) / fDenominator;
 pVtOut.z = 0;
 return pVtOut;
}


행렬
행렬은 백터의 값을 변환하는 용도로 사용된다.
- 정방행렬 : n x n차 행렬
3차원 좌표계를 사용하는 경우 4*4의 행렬. 16개의 스칼라 원소들로 구성된 행렬을 사용한다.


- 단위 행렬(항등행렬, indentity matrix) : 대각선 값들이 1이고 나머지는 0인 행렬


- 행렬의 곱
예  AB = =


-  OpenGL은 열백터(행렬의 열 구성요소가 백터가 됨)를 사용. DirectX는 행백터를 사용(본문 내용은 모두 열백터..)
- 두 행렬을 곱하면 새로운 행렬이 되며 그 원소들은 한 행렬의 행과 다른 핼렬의 열을 내적하여 구한다.


- 전치행렬(M^T) : 행렬의 각 원소들의 행,열 위치를 서로 맞바꾼 행렬
  • 역행렬 : 행렬 M에 대해 NM=MN=I(단위행렬)을 만족하는 행렬 N (N=M^-1)
- 이동 행렬
glTranslatef(1.0f, 1.0f, 0.0f);


- 스케일 행렬
glScalef(1.0, 2.0f, 1.0f);
스케일 행렬의 S?값이 1이면 기본 크기지만. 음의 크기를 가질경우 반사(Reflection)효과를 표현하는데 사용하기도 함


- 회전 행렬
glRotatef(45.0f, 0.0f, 0.0f, 1.0f) 
Z축 회전
X축 회전
Y축 회전


참고(행렬의 연산 소스 일부.)
단위 행렬 만들기
public static GMatrix GMatrixIdentity(GMatrix pMatrixOut)
{
for(g_i = 0; g_i < 16; g_i++)
{
pMatrixOut.m[g_i / 4][g_i % 4] = ((g_i / 4) != (g_i % 4) ? 0.f : 1.f);
}
return pMatrixOut;
}

행렬의 곱
static GMatrix m_matrixTemp = new GMatrix();
public static GMatrix GMatrixMultiply(GMatrix pMatrixOut, GMatrix pMatrix1, GMatrix pMatrix2)
{
m_matrixTemp.clear();

for (g_i = 0; g_i < 4; ++g_i)
{
for (g_j = 0; g_j < 4; ++g_j)
{
for (g_k = 0; g_k < 4; ++g_k)
{
m_matrixTemp.m[g_i][g_k] += pMatrix1.m[g_i][g_j] * pMatrix2.m[g_j][g_k];
}
}
}

pMatrixOut.set(m_matrixTemp);
return pMatrixOut;
}


행렬에 이동속성 적용
public static GMatrix GMatrixTranslation(GMatrix pOut, float x, float y, float z)
{
pOut.m[3][0] = x;
pOut.m[3][1] = y;
pOut.m[3][2] = z;
return pOut;
}

행렬에 스케일 속성 적용
public static GMatrix GMatrixScaling(GMatrix pOut, float x, float y, float z)
{
pOut.m[0][0] = x;
pOut.m[1][1] = y;
pOut.m[2][2] = z;
return pOut;
}

행렬에 X로테이션 속성적용
public static GMatrix GMatrixRotationX(GMatrix pOut, float fAngle)
{
pOut.m[1][1] = (float) Math.cos(fAngle);
pOut.m[1][2] = (float) Math.sin(fAngle);
pOut.m[2][1] = (float) -Math.sin(fAngle);
pOut.m[2][2] = (float) Math.cos(fAngle);
return pOut;
}

행렬에 Y로테이션 속성적용
public static GMatrix GMatrixRotationY(GMatrix pOut, float fAngle)
{
pOut.m[0][0] = (float) Math.cos(fAngle);
pOut.m[0][2] = (float) -Math.sin(fAngle);
pOut.m[2][0] = (float) Math.sin(fAngle);
pOut.m[2][2] = (float) Math.cos(fAngle);
return pOut;
}

행렬에 Z로테이션 속성적용
public static GMatrix GMatrixRotationZ(GMatrix pOut, float fAngle)
{
pOut.m[0][0] = (float) Math.cos(fAngle);
pOut.m[1][1] = (float) Math.cos(fAngle);
pOut.m[0][1] = (float) Math.sin(fAngle);
pOut.m[1][0] = -(float) Math.sin(fAngle);
return pOut;
}


ETC..
라디안 * 180 / 3.14 = 도
도 / 180 * 3.14 = 라디안
원의 방정식 : (x-h)^2 + (y-k)^2 = r^2
구의 방정식 : (x-h)^2 + (y-k)^2 + (z-l)^2 = r^2
수직축을 가지는 포물선 방정식(x축은 h, y축은 k) : y = a(x-h)^2 + k
수평축을 가지는 포물선 방정식(x축은 h, y축은 k) : x = a(y-k)^2 + h
두점사이의 거리 : distance = sqrt( (x2-x1)^2 + (y2-y1)^2 )
두점사이의 거리(3D) : distance = sqrt( (x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2 )
직각삼각형에서 길이순으로 b, a, c일때   sin alpha = b/c ,  cos alpha = a/c ,  tan alpha = b/a
등속도 운동의 이동거리 속도v가 일정할 때  변위=속도*시간(d=v*t)
가속도 = (이후속도 - 이전속도) / (이후시간 - 이전시간)
운동방정식1 : 최종속도 = 초기속도 + 가속도*시간
운동방정식2 : 평균속도 = (초기속도 + 최종속도) / 2
운동방정식3 : 변위 = (초기속도 + 최종속도) / 2 * 시간
뉴턴 > 무게 = 질량 * 중력가속도


행렬 스택
OpenGL에서는 CTM을 설정한 후 그려지는 모든 물체는 CTM의해 3차원 공간에 그려지게 된다.
때문에 어느 한 곳에서 CTM을 변환 하면 다른 모든 물체도 영향을 받는다.
OpenGL에서는 행렬 스택이라는것을 이용해 기존의 CTM(Current Transformation Matrix) 에 변화를 주지 않으면서 변환을 할수 있게 해준다.

행렬 스택의 실행방식은 이름에도 있듯이 스택을 이용해 CTM을 스택에 저장 하고 꺼내는 방식이다.
먼저 glPushMatrix라는 함수를 사용하면 CTM스택에 저장 한다.
그러면 스택에는 변환하기 전의 CTM이 저장되어있고 CTM의 복사본이 CTM으로 설정 되어있다.
그 후부터 나오는 모든 변환 및 렌더링은 CTM의 복사본에 일어난다.
그리고 glPopMatrix라는 함수를 사용하여 변환하기 전에 저장한 CTM을 불러와 CTM으로 복원한다.
* 스택에 저장할수 있는 행렬의 갯수는 하드웨어 마다 다르지만 모델뷰는 최소 32개, 투상은 최소 2개이다.
스택의 범위를 벗어나게 되면 화면에 아무것도 나오지 않는 현상이 발생될 수 있다.

void glMatrixMode(GLenum mode);
mode에는 GL_MODELVIEW, GL_PROJECTION, GL_TEXTURE 등 을 사용할 수 있다.
이 함수를 사용하면 지정한 행렬을 현재 행렬로 설정 한다.

void glLoadIdentity(void)
CTM을 항등행렬로 초기화 시킨다.

void glLoadMatrixd(const GLdouble *m),void glLoadMatrixf(const GLfloat *m)
CTM의 값들을 m의 값들로 바꾼다.

void glMultMatrixd(const GLdouble *m),void glMultMatrixf(const GLfloat *m)
CTM과 m을 곱한 후 곱한 값을 CTM에 넣는다.

void glPushMatrix(void);
CTM을 스택의 데이터가 없는 곳에서 제일 아래쪽에 저장한다.

void glPopMatrix(void);
스택에 저장되어 있는 제일 위의 CTM 저장본을 꺼내서 CTM으로 설정한다.


변한 행렬
OpenGL에서 모든 변환은 변환행렬로 대신한다. 예를 들어 모델변환은 모델행렬로, 시점변환은 뷰행렬로, 투영변환은 투영행렬등으로 사용한다.

OpenGL에서는 모델변환행렬뷰변환행렬을 합쳐서 모델뷰변환행렬로 사용하게 되어있다.
원래는 뷰행렬과 모델행렬이 곱해져 모델뷰를 이루지만 물체를 보기위해 카메라를 옮기는거나 물체를 옮기는 거나
최종 결과 모습은 동일 하기 때문이다.
(따로 카메라를 위한 분리된 뷰 행렬이 존재하지 않는다는 의미이다.)

변환을 할려면 행렬을 지정해주어야 하는데…
OpenGL에서 glMatrixMode라는 함수를 사용해 지정해 줄 수 있다.
그리고 glLoadIdentity라는 함수를 실행하여 CTM을 항등행렬(단위행렬)로 초기화 해준다.
초기화 해주지 않으면 그 전 행렬을 그대로 가지고 있기 때문에 원하는 결과와 다르게 나올수도 있으므로
상황따라 적절히 사용해 주어야한다.

OpenGL에서는 이라는 것을 이용하여 CTM을 변환 시키는 방법이 크게 3가지로 사용된다.

1. glLoadMatrix 라는 함수를 사용 해서 배열을 넘겨 CTM을 그 배열 값으로 채울 수 있다.
이 함수는 넘겨받을 배열의 데이터 형을 GLfloat과 GLdouble을 지원 하며 위의 함수명마지막에 데이터 형에 따라 f 또는 d를 명시해 주어야 한다.

2. glMultMatrix 라는 함수는 CTM에 파라미터로 넘겨주는 배열 M을 곱하는 함수이다.
이 곱셈은 후위곰셈으로 CTM = CTM * M 이므로 행렬의 곱셈은 교환 법칙이 성립하지 않으므로 주의를 요한다.
이 함수도 1과 같이GLfloat과GLdouble을 사용 가능하므로 함수명 마지막에 f 또는 d를 명시해주어야 한다.

3. 마지막으로 OpenGL에서 제공하는 이동, 회전, 크기조절등의 함수를 이용하는 것이다.
이 방법을 이용할때 주의할 점은 OpenGL 에서는 변환을 Stack을 이용해 전역 좌표를 기준으로 변환을 하기 때문에
물체를 이동후 회전을 하고 싶으면 OpenGL에서는 회전후 이동을 해야 원하는 결과를 얻을 수 있다.

(끝에 d가 붙는건 넘겨받을 파라미터가 GLdouble f는 GLfloat형을 뜻한다.)

회전
glRotated, glRotatef( angle, x축, y축, z축)
이 함수는 모델 좌표계를 젼역 좌표계로 부터 angle만큼 반 시계방향으로 회전 시킨다.
angle의 단위는 도(Degree)이고 그 다음은 전역 좌표계의 어느 축을 기준으로 회전을 할껀지 정하고 회전할 축의 값을 1로 준다.
(주의! 모델좌표계가 기준이 아니다)

이동
glTranslated,glTranslatef( x축, y축, z축)
이 함수는 모델 좌표계를 전역 좌표계로부터 X,Y,Z축 방향으로 x,y,z 만큼 이동 시킨다.

크기 조절
glScaled, glScaledf(x, y, z);
이 함수는 모델 좌표계의 X,Y,Z축의 눈금이 전역 좌표계 눈금의 x,y,z 배만큼 되도록 크기를 조절한다.
이 함수를 사용시 주의 해야할 점은 기본 크기가 1 이기 때문에 하나의 축만 조절할때 나머지는 0이 아닌 1을 줘야 한다.
(만약 위함수를 사용해서 전역 좌표계 한 눈금이 0.1cm이고 x가 2일 때 모델 좌표계의 한 눈금은 0.2cm가 되어 좌표는 똑같이
1이지만 0.1cm가 아닌 0.2cm를 가기 때문에 크기는 2배가 된다.)




텍스쳐 크기 제약 사항 및 권고사항
텍스쳐는 2승수로 제작되어야 한다.
폭과 너비가 같은 2승수 정방형 로만 제작되어야 동작하는 칩셋이 있고..
2승지만 정방형이 아닌 경우도 지원하는 칩셋도 있고
2승수 크기에 대한 제약이 없는 칩셋도 있다..
2승수로 해야 GPU내부 연산시 성능의 이득(shift연산) 을 볼 수 있다는 점이 있어  텍스쳐 크기를 2승수로 제한한 그래픽 칩셋이 많이 있다.
(PC에서는 제약사항이 많이 줄어있음.)
현재 대부분의(어쩌면 모두다..) 휴대 단말기에서는 해당 제약 사항을 가지고 있다.
그래픽카드가 2승수가 아닌경우도 지원할 경우 그래픽카드의 속성으로 확인하여
변환없이 프로그래밍 처리 할 수도 있다.
(단, 2승수 제약이 없는경우 내부적으로 승수 크기로 강제 변환되면서 예상못한 메모리 낭비가 있을 수 있다.)
스마트 휴대단말에서는 2승수 정방형만 지원한다고 생각하자.


최대크기가 정해져 있다.
비디오칩셋에 텍스쳐의 크기 제한은 존재하고 있다. (피시에서는 대개 4096* 4096 또는 8192 * 8192)
스마트 휴대단말에서는 최대크기를 1024, 2048 정도를 사용하고 있는것으로 보임.
제약 크기보다 큰 이미지를 사용하고자 할 경우는 여러개의 타일로 붙여서 제작하여야 한다.


* 위 제약사항을 확인하지 않고 제작할 경우 화면에 아무것도 나오지 않을 수 있다.


성능을 향상을 위한 텍스쳐 제작 팁
1. 텍스쳐 크기는 최대한 작게 사용할 것.(작으면 작을수록 유리)
2. 2승수 정방형을 유지할것.(텍스쳐 어드레스 연산시 쉬프트 연산을 사용으로 처리속도 향상,
아닌경우 성능저하 : 칩셋이 지원하더라고 정방형 유지 권장)
3. 가능하면 여러이미지를 256*256 크기로 합쳐서 사용될 수 있도록 구현할 것(효율이 가장 좋음)
4. 비디오 메모리가 부족한경우 일부 텍스쳐에 할당된 메모리가 자동으로 제거되고 다시 새로운 텍스쳐에 할당되면서 성능의 저하가 생길수 있다.
성능이 우려된다면 필요한 텍스쳐만 사용하고 불필요한 텍스쳐는 반드시 정리할 필요가 있다.


참고(게임엔진)
대부분의 온라인 게임은 Windows PC환경+DirectX 구조로 만들어져 있다.


언리얼 엔진
개발사 : 에픽 게임스 (Epic Games)
테라, A.V.A, 기어스 오브 워, 레인보우 식스 베가스, 아바, 바이오쇼크, 헉슬리, 뮤2, 스페셜 포스2 등 상당히 많음


게임브리오(구버전:넷임머스)
개발사 : 이머젼트 게임 테크놀러지스 (Emergent Game Technologies)
레퀴엠 온라인, 제라, 메이팡 온라인, 스키드러쉬, WOW(넷임머스를 튜닝해서 자체 엔진으로 발전) 등…


쥬피터
개발사 : 터치다운 엔터테인먼트 (Touchdown Entertainment)
히트 프로젝트, 서든 어택, 파병, 크로스 파이어, 테이크다운 온라인


크라이
개발사 : 크라이텍 (CryTek)
아이온, 카일라스, 네드 온라인


  1. 밸브 소스 엔진
    개발사 : 밸브 소프트웨어 (Valve Software)
스팅, 마비노기 영웅전


프라우드넷
개발사 : 넷텐션(국산)

마비노기 영웅전, 라그나로크온라인2, 마계촌 온라인, 다크블러드온라인, 거울전쟁 신성부활 등,.