Иррегулярлы Z-буфер алгоритмі және CUDA платформасындағы қолданылуы
Irregular Z-buffer
Иррегулярлық Z-буфері: 3D графикада көріну мәселесін шешетін алгоритм. Бұл бейімделмелі үлгі орналасуы арқылы сурет сапасын жақсартады. Z-буфер туралы толық ақпарат!
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Қалыпсыз Z буфері — нақты уақыт 3D компьютерлік графикада көріну мәселесін шешуге арналған алгоритм. Ол классикалық Z буферімен байланысты, себебі ол әрбір бейне үлгісі үшін тереңдік мәнін сақтайды және оларды көріністегі қай геометриялық элементтердің көрінетінін анықтау үшін пайдаланады. Дегенмен, классикалық Z буфері мен қалыпсыз Z буферінің басты айырмашылығы — соңғысы бейне үлгілерін бейне жазықтығында кез келген орналасқан жерге қоюға мүмкіндік береді, ал алғашқысы үлгілерді реттелген торға орналастыруды қажет етеді. Бұл тереңдік үлгілері екі өлшемді кеңістіктік дерек құрылымында нақты сақталады. Растрлеу кезінде үшбұрыштар әдеттегідей бейне жазықтығына проекцияланады, ал дерек құрылымы әрбір проекцияланған үшбұрыштың қай үлгілермен қиылысатынын анықтау үшін сұралады. Ақырында, әрбір қиылысқан үлгі үшін стандартты Z салыстыру және (шартты) кадр буферін жаңарту орындалады.
The irregular Z buffer is an algorithm designed to solve the visibility problem in real time 3 d computer graphics. It is related to the classical Z buffer in that it maintains a depth value for each image sample and uses these to determine which geometric elements of a scene are visible. The key difference, however, between the classical Z buffer and the irregular Z buffer is that the latter allows arbitrary placement of image samples in the image plane, whereas the former requires samples to be arranged in a regular grid. These depth samples are explicitly stored in a two dimensional spatial data structure. During rasterization, triangles are projected onto the image plane as usual, and the data structure is queried to determine which samples overlap each projected triangle. Finally, for each overlapping sample, the standard Z compare and (conditional) frame buffer update are performed.
Іске асыру
Классикалық растерлеу алгоритмі әрбір көпбұрышты бейне жазықтығына проекциялайды және проекцияланған көпбұрыш ішінде тұрақты аралықтағы жиыннан қандай үлгі нүктелері бар екенін анықтайды. Бұл үлгілердің орналасуы (яғни пиксельдер) ашық болғандықтан, бұл анықтауды жиектерді үлгі нүктелерінің ашық торымен салыстыру арқылы жасауға болады. Егер үлгі нүктелерінің орналасуы тұрақты аралықта болмаса және формуладан есептеуге болмаса, онда бұл тәсіл жұмыс істемейді. Қалыпсыз Z буфері бұл мәселені екі өлшемді кеңістіктік деректер құрылымында үлгілердің орналасуын нақты сақтау арқылы шешеді, содан кейін осы құрылымды сұрау арқылы проекцияланған үшбұрыш ішінде қандай үлгілер бар екенін анықтайды. Бұл соңғы қадам "қалыпсыз растерлеу" деп аталады. Қолданылатын нақты деректер құрылымы іске асырудан іске асыруға өзгеруі мүмкін, бірақ зерттелген екі тәсіл – kd ағашы және байланысты тізімдер желісі. Теңгерілген kd ағашын іске асыру O(log(N)) қол жеткізуді кепілдейді. Оның басты кемшілігі – kd ағашын параллель құру қиын болуы мүмкін, ал оны бағдарлауда қымбат тармақталу нұсқаулары қажет. Тізімдер желісінің артықшылығы – оны классикалық Z буфері үшін арналған GPU аппараттық құралдарында тиімдірек іске асыруға болады. CUDA пайда болуымен қазіргі графикалық аппараттардың бағдарламалану мүмкіндігі күрт жақсарды. "CUDA-да қалыпсыз Z буферін пайдалана отырып, жылдам үшбұрышты растерлеу" (сыртқы сілтемелерді қараңыз) магистрлік диссертациясы CUDA-да қалыпсыз Z буферге негізделген көлеңке карталау бағдарламалық жасақтамасын толық сипаттайды. Рендеринг жүйесі толығымен GPU-да жұмыс істейді. Ол секундына он миллион үшбұрыштан астам жылдамдықпен антиалиасингті көлеңкелерді жасауға қабілетті.
The classical rasterization algorithm projects each polygon onto the image plane, and determines which sample points from a regularly spaced set lie inside the projected polygon. Since the locations of these samples (i. e. pixels) are implicit, this determination can be made by testing the edges against the implicit grid of sample points. If, however the locations of the sample points are irregularly spaced and cannot be computed from a formula, then this approach does not work. The irregular Z buffer solves this problem by storing sample locations explicitly in a two dimensional spatial data structure, and later querying this structure to determine which samples lie within a projected triangle. This latter step is referred to as "irregular rasterization". Although the particular data structure used may vary from implementation to implementation, the two studied approaches are the kd tree, and a grid of linked lists. A balanced kd tree implementation has the advantage that it guarantees O(log(N)) access. Its chief disadvantage is that parallel construction of the kd tree may be difficult, and traversal requires expensive branch instructions. The grid of lists has the advantage that it can be implemented more effectively on GPU hardware, which is designed primarily for the classical Z buffer. With the appearance of CUDA, the programmability of current graphics hardware has been drastically improved. The Master Thesis, "Fast Triangle Rasterization using irregular Z buffer on CUDA" (see External Links), provide a complete description to an irregular Z Buffer based shadow mapping software implementation on CUDA. The rendering system is running completely on GPUs. It is capable of generating aliasing free shadows at a throughput of dozens of million triangles per second.
Қолданбалар
Қалыпсыз Z буфері бейне жазықтығының кез келген нүктесінде көрінуді есептеуді қажет ететін кез келген қолданба үшін қолданылуы мүмкін. Ол әсіресе көлеңке картасын жасауда тиімді, бұл қатты көлеңкелерді көрсетуге арналған бейне кеңістігіндегі алгоритм. Көлеңкелерді көрсетуден басқа, потенциалды қолданыстарға адаптивті антиалиазинг, қимылды үлгі алу және қоршаған ортаны бейнелеу кіреді.
The irregular Z buffer can be used for any application which requires visibility calculations at arbitrary locations in the image plane. It has been shown to be particularly adept at shadow mapping, an image space algorithm for rendering hard shadows. In addition to shadow rendering, potential applications include adaptive anti aliasing, jittered sampling, and environment mapping.