Tuesday Afternoon Club/Session 2: Oснови на геометричната алгоритмика

Презентатори: доц. Бойко Банчев и Aндрей Дренски, GPU developer в Chaos Group

Модератор: доц. Петър Армянов

Резюме:

I част/ доц. Бойко Банчев /От над 40 години активно се развива област на алгоритмиката, известна като „изчислителна геометрия“ (от англ. computational geometry), в която обектите на разглеждане са именно геометрични: точки, отсечки, прави, окръжности и множества от такива, а също например многоъгълници и др. по-сложни фигури и структури.

В основата на проектирането и реализирането на алгоритми над геометрични обекти стои един или друг формализъм, език за ефикасно изразяване на свойства, отношения и действия с основните споменати обекти – език за извършване на геометрични пресмятания. Ролята на такъв език може да играе традиционната аналитична геометрия, но в изложението ще покажа, че много по-сполучливо изразно средство е векторната алгебра.

Тъй като в курсовете по аналитична геометрия смятането с вектори е представено крайно непълноценно, а в учебниците по изчислителна геометрия дори не става дума за това, какъв формализъм за пресмятане да се използва, в беседата ще бъде показано решаването на основни, най-прости задачи на изчислителната геометрия на езика на векторната алгебра. Чрез няколко примера ще покажем и как на тази основа се решават по-сложни, съществено алгоритмични задачи.

II част / Андрей Дренски/ През 2005-та година за пръв път се използват графични процесори (GPU-та) за нещо, различно от графично програмиране - т.нар. общо програмиране (generic programming, оттам GPGPU програмиране) и това задава хода на развитието им в следващите 15 години. Тяхната паралелизирана, относително проста архитектура, се оказва приложима към много други изчислителни задачи в сферите на обработка на данни, биоинформатика, изкуствен интелект, и отново компютърна графика, вече с различен подход.

Една такава задача, развита до огромна сложност съвместно с развитието на хардуера, представлява симулирането на пътя на светлината в околния свят - начините, по които свeтлината се пречупва, отразява, поглъща и излъчва обратно. Тази задача е разковничето за постигане на истински, реалистични компютърно-генерирани изображения, с потенциал за използване във всички сфери на създаване на дигитално съдържание (digital content creation).

Ще представим простото геометрично ядро на тази задача - как ефективно да се изчисли даден светлинен лъч къде би се ударил в дадена околна среда, т.нар. трасиране на лъч. Ще се фокусираме предимно върху ефективните начини, по които средата бива представяна, за да ускорим трасирането и ще отворим вратата към паралелното ѝ изпълнение и понататъшно усложняване.