빠른 2D 조명 알고리즘?

Question

우리는 반투명의 벽과 광원이있는 직사각형 영역을 가지고 있습니다. 우리는 단지 평면 뷰만을 고려하고 있으므로 2D 문제입니다. 지역의 각 지점에서 대략적인 조명 (신호 강도)을 찾아야합니다.

알고리즘을 매우 빠르게 만들어야합니다. 무차별 방식은 우리의 목적에 너무 느렸다. 모든 벽이 같은 양만큼 감쇠한다고 가정 할 수 있습니다. 일정한 감쇄량도 허용됩니다.

이 지역은 가장 1000x1000에있을 것이며, 100 개 이상의 광원이 없을 것입니다. 광원의 범위는 약 1 ~ 4입니다. 50-100 개 유닛 (무한하지 않음). 보다 빠르고 대략적인 알고리즘을 환영합니다.

미리 감사드립니다. 의 밝기를 결정하는 각 벽과 광원 각 샘플 포인트를 비교 : I 시도 무엇

은 기본적으로 무력 방법이었다. 분명히 그것은 O (n^3)이며 용납 될 정도로 느립니다.

시간까지 나는 어떤 특정 제한을 의미하지 않았다 :하지만이 100ms 이상 속도에서 전체 이미지를 할 좋은 것입니다. 속도와 같은 정확성을 요구하지 않는다는 것을 기억하십시오.

Answer 1

어둠 속에서 단지 찌르기 : (GPU 가속화 된) 광자 매핑을 살펴 보았습니까?

Answer 2

당신은 (예. 모든 2 x와 y를 건너) 차적으로 유사한 알고리즘의 실행 시간을 단축 선형 품질을 잃고 있습니다 (이미지가 반 직경을 얻고 다시 같은 크기로 재 샘플링).

비트 맵을 사용하여 광도를 저장하고 모든 점 라인 atc (더 근접한 요소로 모든 점을 나눕니다)의 하위 크기 비트 맵 (근접 요인으로 나누기)에서 렌더링 한 다음 가우시안 블러를 사용하여 원하는 크기로 다시 리샘플링합니다. . 그런 다음 픽셀에서 광도를 추출합니다.

나는 그 일을 할 수 있다면하려고 내가 코드 한 테스트의 실행을 보여주는 유튜브에 동영상을 업로드했습니다. 물론

Link to Video

여기 벽이 투명 속성 라인, 그리고 당신이처럼 빛이 확산되지 않습니다 : 그것은 당신이 (단일 스레드에 '거의 실시간'으로 그 일을) 필요 것과 유사한 omething 보인다 그러나 선형 적으로 기대할 수 있지만 "approximation"은 알고리즘에 의해 사용 가능해야하며, 속도가 충분하다면이 알고리즘을 적용 할 수 있습니다. 그리고 단지 실험을했기 때문에 조심성있게 코드를 작성합니다. 여기

광도가 정규화, 당신은 아마 픽셀로 로그 스케일의 광도를 내장으로 갈 것이다, 그래서 당신은 원래 값을 유지하기 위해, 더 큰 범위에 맞게 할 수 있습니다. 최적화하고 그것을 스레드, 아마 100ms의 직경 (300)과 (100 개) 조명과 1000x1000의 이미지와 경우 추천 벽

Link to project

: 여기 프로젝트입니다 :

당신이 뭔가를 사용할 수 있나요 200의 길이를 가지며, 5의 근사치를 얻을 수 있습니다.