3D 길찾기 구현중 #4 – voxel지형으로부터의 네비게이션 매시 생성

3D길찾기를 시도하면서 큰 목표중 하나가 복셀맵에서 길찾기를 하는것이었다. marching cube알고리즘으로 일단 voxel지형에서 삼각형을 생성할 수 있다. 이걸 네비게이션 매시로 사용해서 길찾기를 하면 되기는 하는데…..문제가 있다. 복셀 매시로부터 삼각형 매시를 생성. 삼각형이 미친듯이 많이 나온다. 복셀 매시로부터 생성한 삼각형을 최적화. 인접한 삼각형간에 엣지를 공유할 수 없게 된다. 엣지를 공유하지 않으므로 네비게이션 매시로 사용할 수 없게 된다. … More 3D 길찾기 구현중 #4 – voxel지형으로부터의 네비게이션 매시 생성

3D 길찾기 구현중 #3 – visibility 테스트와 유사한 Stupid Funnel 알고리즘 적용

Stupid Funnel 알고리즘을 적용했다. 알고리즘 내용은 아래 링크에서 참고. http://jceipek.com/Olin-Coding-Tutorials/pathing.html#funnel-algorithm 처음엔 명확하게 이해가 안됐다. 어떤 문서에선 실로 감싼다는 개념으로 설명하는데 이해가 되지 않았다. 일단 꺽이는 위치의 좌표를 구하는건 스킵하고 직선이동이 가능한 경로를 찾는데 촛점을 맞춰서 구현을 시작했다. 몇 일 작업을 하다보니 이 알고리즘의 기본 원리가 보였다. 이거 3D에서 가시성 검사할때 사용하는 Portal-Culling이랑 개념이 같다. Room/Portal방식에서 … More 3D 길찾기 구현중 #3 – visibility 테스트와 유사한 Stupid Funnel 알고리즘 적용

3D 길찾기 구현중 #2

‘복셀 데이터 -> 마칭큐브로 삼각형 변환 -> 네비게이션 매시 변환’ 을 해보고 나서서 인접한 엣지를 타고 삼각형들간의 그래프 자료구조를 만드는게 더럽게 느리다는 사실을 깨달았다. 코드를 왕창 뜯어고쳐서 50배쯤 빠르게 만들고나서 다시 테스트를 했다. 복셀맵으로부터 생성한 네비게이션 매시는 삼각형 분포가 너무 조밀하거나(최적화 안했을때), 혹은 엣지가 자료구조상 연결이 될 수 없거나(최적화 했을때) 복셀쪽은 생각을 좀더 해보기로 하고 … More 3D 길찾기 구현중 #2

3D 길찾기 구현중 #1

퀘이크3처럼 bot과의 전투를 넣으려고 한다. 그러기 위해선 bot이 알아서 길을 찾아야한다. 당초 기술기반을 구축할때 3D길찾기는 고려하지 않았다. 몬스터는 충분히 바보같아야하고 따라서 각자의 스폰 영역을 벗어날 필요가 없었다. 그런데 bot과의 1:1 전투를 하려면 bot이 똑똑할 필요가 있다. 물론 bot을 똑똑하게 만들 자신은 없다. 그래도 bot이 플레이어를 잡으러 돌아는 다녀야 한다. 그러려면 길찾기가 필요하다. 그래서 일단 길찾기는 … More 3D 길찾기 구현중 #1

SW Rasterize 기법에 따른 효용성 요약

SW Occlusion Culling만들면서 CPU로 삼각형 찍는 방법으로 별 짓을 다 써봤다. SW Occlusion Culling을 수행하기 위해선 프레임버퍼에 삼각형의 depth를 출력해야한다. depth값이 아닌 color값이나 texture를 출력하는 경우도 기본 원리는 똑같다. 성분의 종류만 다르고 1/w로 보간하는것까지 똑같다. 즉 CPU로 삼각형 찍는 SW Rasterizer를 만드는 작업이다. 여러가지 기법들을 사용해봤는데 결론을 요약해본다. 1. Multi-Thread 사용 화면 구역을 나눠서 여러스레드가 … More SW Rasterize 기법에 따른 효용성 요약

Async S/W Hierarchical Occlusion Culling

S/W Occlusion Culling에 대한 미련을 못버리고 계속 튜닝하면서 사용해왔다. 다음번 프레임의 카메라 위치 예측 + 비동기 S/W Occlusion Culling으로 완료를 짓는가 싶었다. 성능도 만족스러웠다. 근데 생각해보니 어차피 비동기로 처리할거면 Hierarchical Z방식으로 처리하는게 더 낫지 않나? 그런 생각이 들었다. 512×512 -> 1×1까지 Down-sampling 비용이 항시 포함되어서 메인스레드에서 처리하긴 부담스러웠던것인데 어차피 비동기적으로 Raster스레드가 처리한다. 게다가 이 비용은 … More Async S/W Hierarchical Occlusion Culling

Real-time Volumetric Cloudscapes

Real-time Volumetric Cloudscpes를 Voxel Horizon에 적용했다. 내 엔진에는 하늘과 구름을 자동으로 생성해주는 기능이 없다. 고전적인 디자이너가 모델링 하는 스카이박스를 사용해왔다. 최근 몇년간 도움을 받을 아트 디자이너도 구할 수 없었고, 앞으로도 없을것이기에 하늘과 구름을 코드로 생성해줘야겠다고 생각했다. 2005년 즈음에 Game Programming Gem에 수록된 ‘펄린 노이즈를 이용한 절차적 구름 생성기법’이란 챕터 제목을 기억하고 있었다. 이걸 사용해서 구름을 … More Real-time Volumetric Cloudscapes

삼각형 베이스 맵에서의 SW Occlusion Culling #3

앞서 Rasterize코드의 버그를 수정했고 거의 완벽하게 CPU로 Raster/Test작업을 수행한다. 시간이 걸린다는 문제만 빼면 culling결과는 매우 훌륭하다. 다만 시간이 걸린다는 문제는 결코 무시할 수 없다. CPU로 삼각형을 픽셀 단위로 찍는 작업은 간단한 작업이 아니다. 아무래도 매 프레임마다 SW Occlusion Culling을 수행하면 Raster/Test비용이 렌더링 비용보다 더 커진다. 그래서 카메라 위치와 방향의 변화가 일정 수치 미만인 경우 앞 … More 삼각형 베이스 맵에서의 SW Occlusion Culling #3

삼각형 베이스 맵에서의 SW Occlusion Culling #2

일반적인 삼각형 베이스 맵에서의 SW Occlusion Culling을 적용하고 있다. 현재는 Occluder로 사용할 삼각형을 따로 골라내지 않고 삼각형 그대로 SW Z-Buffer에 Rasterize한다. 오브젝트 단위로 culling하지 않고 다수의 오브젝트가 묶여있는 leaf의 AABB를 Z-Test하고 있다. 처음엔 Occluder로 사용할 삼각형을 미리 골라둘 생각이었으나 굳이 그럴 필요는 없을것 같다. SW Occlusion Culling단계에서는 leaf단위로 culling한다. HW Occlusion Culling단계에서 오브젝트 단위로 culling한다. … More 삼각형 베이스 맵에서의 SW Occlusion Culling #2