В 1000 раз быстрее

Реализация алгоритма трассировки лучей на новом языке программирования «Перфолента»

 

Предлагаю на время отвлечься от задач автоматизации, и погрузиться в загадочный и увлекательный мир 3D моделирования. Дочитавшим до конца — сюрприз)

 

Предыстория

Изначально программа для отрисовки сцен при помощи алгоритма трассировки лучей tinyraytracer была написана на языке C++ (статья на Хабре).
 
Потом на язык OneScript программу перевел Michael Rybakin (проект на GitHub).
 

К сожалению, реализация этого алгоритма на OneScript имеет один критический недостаток — картинка формируется слишком медленно. Программа интенсивно использует структуры данных, что приводит к большим накладным расходам.

Забегая вперёд, скажу, что труды Mr-Rm не пропали даром, и его программа засияла новыми красками. Мной была проделана работа по адаптации этой программы под новый язык "Перфолента" Сергея Рогаткина.

Кто не знает, "Перфолента" — это "повзрослевший" язык 1С, который из прикладного инструмента, превратился в самостоятельный язык программирования. Он получил все необходимые для современного языка технологии, при этом сохранив привычные возможности и совместимый синтаксис. Но, в отличие от 1С и OneScript, "Перфолента" — это компилятор со статической типизацией, поэтому типы для всех объявляемых переменных, функций и их аргументов должны быть заранее определены.
 
Программа
 
Процесс адаптации программ не сложный, но требует внимательности и терпения) Надеюсь, что в будущем эту задачу удастся автоматизировать.

Итак, мы получили работающий код на языке "Перфолента".

 
Текст программы без оптимизации:
 
 
Хм, программа хоть и стала работать быстрее, но не намного — где-то раза в 2,5. Но ещё рано унывать! Вспоминаем про тяжелые структуры данных, и заменим их на более оптимальные классы.
 
Текст программы с классами:

//Код, оптимизированный под возможности Перфоленты

#ИспользоватьСтандартнуюБиблиотеку

//В процессе экспериментов выяснилось,
//что Вектор лучше делать Структурой
//а Материал, Свет и Сферу классами, тогда производительность возрастает
//примерно на 25 процентов по сравнению с вариантом когда только структуры
//и примерно на 8 процентов по сравнению с вариантом, когда только классы


// ------------------
Структура Вектор
&ВидноВсем Поле x тип ДВещ
&ВидноВсем Поле y тип ДВещ
&ВидноВсем Поле z тип ДВещ
//---------------------------
&ВидноВсем
Конструктор(px тип ДВещ, py тип ДВещ, pz тип ДВещ)
x = px
y = py
z = pz
КонецКонструктора

#Область ПереопределениеОператоровВектора

//Переопределим для теста операторы сложения, вычитания, умножения и скалярного произведения векторов
//проверим в функции Отражение()

//---------------------------
&ВидноВсем, ОбщийДляКласса
Оператор +(В1 тип Вектор, В2 тип Вектор) тип Вектор
возврат Новый Вектор( В1.x+В2.x, В1.y+В2.y, в1.z+В2.z );
КонецОператора

//---------------------------
&ВидноВсем, ОбщийДляКласса
Оператор -(В1 тип Вектор, В2 тип Вектор) тип Вектор
возврат Новый Вектор( В1.x-В2.x, В1.y-В2.y, В1.z-В2.z );
КонецОператора

//---------------------------
&ВидноВсем, ОбщийДляКласса
Оператор *(В1 тип Вектор, ч тип ДВещ) тип Вектор
возврат Новый Вектор( В1.x*ч, В1.y*ч, В1.z*ч );
КонецОператора

//---------------------------
&ВидноВсем, ОбщийДляКласса
Оператор *(В1 тип Вектор, В2 тип Вектор) тип ДВещ
возврат В1.x*В2.x + В1.y*В2.y + В1.z*В2.z;
КонецОператора

#КонецОбласти

//---------------------------
&ВидноВсем,ОбщийДляКласса
Процедура Печать( В1 тип Вектор )
ВыводСтроки "("+В1.x+","+В1.y+","+В1.z+")";
КонецПроцедуры

//---------------------------
&ВидноВсем,ОбщийДляКласса
Функция Минус( В1 тип Вектор ) тип Вектор
возврат Новый Вектор( -В1.x, -В1.y, -В1.z );
КонецФункции

//---------------------------
&ВидноВсем,ОбщийДляКласса
Функция Сумма( В1 тип Вектор, В2 тип Вектор ) тип Вектор
возврат Новый Вектор( В1.x+В2.x, В1.y+В2.y, в1.z+В2.z );
КонецФункции

//---------------------------
&ВидноВсем,ОбщийДляКласса
Функция Разность( В1 тип Вектор, В2 тип Вектор ) тип Вектор
возврат Новый Вектор( В1.x-В2.x, В1.y-В2.y, В1.z-В2.z );
КонецФункции

//---------------------------
&ВидноВсем,ОбщийДляКласса
Функция Умножить( В1 тип Вектор, ч тип ДВещ) тип Вектор
возврат Новый Вектор( В1.x*ч, В1.y*ч, В1.z*ч );
КонецФункции

//---------------------------
&ВидноВсем,ОбщийДляКласса
Функция СкалярноеПр( В1 тип Вектор, В2 тип Вектор ) тип ДВещ
возврат В1.x*В2.x + В1.y*В2.y + В1.z*В2.z;
КонецФункции

//---------------------------
&ВидноВсем,ОбщийДляКласса
Функция Норма( В1 тип Вектор ) тип ДВещ
возврат Sqrt( В1.x*В1.x+В1.y*В1.y+В1.z*В1.z );
КонецФункции

//---------------------------
&ВидноВсем,ОбщийДляКласса
Функция КвНормы( В1 тип Вектор ) тип ДВещ
возврат В1.x*В1.x+В1.y*В1.y+В1.z*В1.z;
КонецФункции

//---------------------------
&ВидноВсем,ОбщийДляКласса
Функция Нормализация( В1 тип Вектор ) тип Вектор
норма=Вектор.Норма( В1 );
В1.x = В1.x/норма;
В1.y = В1.y/норма;
В1.z = В1.z/норма;
возврат В1;
КонецФункции
КонецСтруктуры


//***************************
Программа tiny

//---------------------------
Поле МАКС_Число тип ДВещ;
Поле ГЛУБИНА_РЕКУРСИИ тип Целое;

Поле НулевойВектор тип Вектор;
Поле ЕдиничныйВектор тип Вектор;
Поле ЕдиничныйВекторX тип Вектор;
Поле ЕдиничныйВекторY тип Вектор;
Поле ЕдиничныйВекторZ тип Вектор;

Поле ЦветФона тип Вектор;
Поле ЦветБелый тип Вектор;
Поле ЦветЖелтый тип Вектор;

Поле ПлиткаБелая тип Материал;
Поле ПлиткаЖелтая тип Материал;

Поле Сферы тип Сфера[];
Поле Освещение тип Свет[];
Поле Ширина тип Целое;
Поле Высота тип Целое;
Поле УголЗрения тип ДВещ;
Поле Кадр тип Вектор[];


Функция Норм_Цвет(знач цв тип ДВещ) тип ДВещ
возврат Цел(255*Макс(0, Мин(1,цв)));
КонецФункции


// ------------------

Функция Сфера_Пересечение(Сф тип Сфера,Исх тип Вектор, Напр тип Вектор, ссыл Расст тип ДВещ) тип Булево

КЦентру = Вектор.Разность( Сф.Центр, Исх );
перем пр тип ДВещ = Вектор.СкалярноеПр( КЦентру, Напр );
перем д2 тип ДВещ = Вектор.КвНормы( КЦентру ) - пр*пр;
перем р2 тип ДВещ = Сф.Радиус*Сф.Радиус;
если д2 > р2 тогда
возврат Ложь;
КонецЕсли;

р = Sqrt( р2 - д2 );
Расст = пр - р;

если Расст < 0 тогда
Расст = пр + р;
если Расст < 0 тогда
возврат Ложь;
КонецЕсли;
КонецЕсли;

возврат Истина;

КонецФункции

Функция НайтиПересечения( Исх тип Вектор, Напр тип Вектор, ссыл Точка тип Вектор, ссыл Нормаль тип Вектор, ссыл Материал тип Материал ) тип Булево
Перем Расст тип ДВещ = 0;
МинРасст = МАКС_Число;
Для Каждого Сф из Сферы Цикл
если (Сфера_Пересечение( Сф,Исх,Напр, Расст )) и (Расст < МинРасст) тогда
МинРасст = Расст;
Точка = Вектор.Сумма( Исх, Вектор.Умножить( Напр, Расст ) );
Нормаль = Вектор.Нормализация( Вектор.Разность( Точка, Сф.Центр ) );
Материал = Сф.Материал;
конецесли;
КонецЦикла;

// квадрат (-10,-10,-4) - (10,-30,-4)
Если Напр.y < -0.001 Тогда
р = -(Исх.y+4)/Напр.y;
Если 0<р и р<МинРасст Тогда
Т = Вектор.Умножить(Напр,р);
Т = Вектор.Сумма(Т,Исх);
Если Abs(Т.x)<10 и -30<Т.z и Т.z<(-10) Тогда
МинРасст = р;
Точка = Т;
Нормаль = ЕдиничныйВекторY;
Материал = ?( (Цел(0.5*Точка.x+1000)+Цел(0.5*Точка.z))%2=1, ПлиткаБелая, ПлиткаЖелтая );
КонецЕсли;
КонецЕсли;
КонецЕсли;

возврат МинРасст < 1000;
КонецФункции

// return I - N*2.f*(I*N);
Функция Отражение( Луч тип Вектор, Норм тип Вектор ) тип Вектор

//возврат Вектор.Разность( Луч, Вектор.Умножить( Норм, 2*Вектор.СкалярноеПр(Луч, Норм) ) );

//воспользуемся переопределенными операторами для Вектора
возврат Луч - Норм * 2д * (Луч * Норм)

КонецФункции

Функция Преломление( Луч тип Вектор, Норм тип Вектор , КоэфПр тип ДВещ  ) тип Вектор
Если КоэфПр=1 Тогда
Возврат Луч;
КонецЕсли;

CosI = -Макс( -1, Мин( 1, Вектор.СкалярноеПр(Луч, Норм)));
Если CosI>=0 Тогда
_1; = 1/КоэфПр;
Н = Норм;
Иначе
CosI = -CosI;
_1; = КоэфПр;
Н = Вектор.Минус(Норм);
КонецЕсли;
К = 1 - _1;*_1;*(1-CosI*CosI);
Если К<0 Тогда
возврат ЕдиничныйВекторX;
КонецЕсли;

возврат Вектор.Сумма( Вектор.Умножить(Луч,_1;), Вектор.Умножить(Н,_1;*CosI-Sqrt(К)) );
КонецФункции

Функция ТрассироватьЛуч( Исх тип Вектор, Напр тип Вектор, Глубина тип Целое = 0 ) тип Вектор
Перем Точка тип Вектор = Неопределено;
Перем Нормаль тип Вектор = Неопределено;
Перем Материал тип Материал = Неопределено;

Перем ТеньТочка тип Вектор = Неопределено;
Перем ТеньНормаль тип Вектор = Неопределено;
Перем ВремМатериал тип Материал = Неопределено;

если Глубина>ГЛУБИНА_РЕКУРСИИ или НЕ НайтиПересечения( Исх,Напр, Точка,Нормаль,Материал ) тогда
возврат ЦветФона;
конецесли;

СдвигПоНормали = Вектор.Умножить( Нормаль, 0.001 );

ОтражНапр = Отражение(Напр,Нормаль); // нормализовано
ОтражИсх = ?( Вектор.СкалярноеПр(ОтражНапр, Нормаль)<0, Вектор.Разность(Точка,СдвигПоНормали), Вектор.Сумма(Точка,СдвигПоНормали) );
ОтражЦвет = ТрассироватьЛуч( ОтражИсх, ОтражНапр, Глубина+1 );

ПреломНапр = Вектор.Нормализация(Преломление(Напр,Нормаль,Материал.КПрелом));
ПреломИсх = ?( Вектор.СкалярноеПр(ПреломНапр, Нормаль)<0, Вектор.Разность(Точка,СдвигПоНормали), Вектор.Сумма(Точка,СдвигПоНормали) );
ПреломЦвет = ТрассироватьЛуч( ПреломИсх, ПреломНапр, Глубина+1 );

перем Яркость тип ДВещ = 0;
перем Блик тип ДВещ = 0;
Для Каждого Свет из Освещение цикл
НапрКСвету = Вектор.Нормализация(Вектор.Разность(Свет.Поз, Точка));

РасстДоСвета = Вектор.КвНормы(Вектор.Разность(Свет.Поз, Точка));
ТеньИсх = ?( Вектор.СкалярноеПр(НапрКСвету, Нормаль)<0, Вектор.Разность(Точка,СдвигПоНормали), Вектор.Сумма(Точка,СдвигПоНормали) );

если НайтиПересечения( ТеньИсх,НапрКСвету, ТеньТочка,ТеньНормаль,ВремМатериал )
и Вектор.КвНормы(Вектор.Разность(ТеньТочка, ТеньИсх))<РасстДоСвета  тогда
Продолжить;
конецесли;

Яркость = Яркость + Свет.Ярк * Макс( 0, Вектор.СкалярноеПр( НапрКСвету, Нормаль ));

//powf(std::max(0.f, -reflect(-light_dir, N)*dir), material.specular_exponent)*lights[i].intensity;
Блик = Блик + Свет.Ярк * Pow(Макс(0, Вектор.СкалярноеПр(Отражение(НапрКСвету, Нормаль),Напр) ), Материал.ЭкспОтраж);
КонецЦикла;

возврат Вектор.Сумма(Вектор.Сумма(Вектор.Сумма( Вектор.Умножить( Материал.Цвет, Яркость*Материал.Альб0 ), Вектор.Умножить( ЕдиничныйВектор, Блик*Материал.Альб1 )),Вектор.Умножить( ОтражЦвет, Материал.Альб2 )),Вектор.Умножить( ПреломЦвет, Материал.Альб3 ));
КонецФункции

Процедура Рендер()

Камера = Новый Вектор(0,0,0);
Напр_Z =-Высота/(2*Tan(УголЗрения/2));
Для верт=0 по Высота-1 Цикл
линия = верт*Ширина;
Напр_Y = -(верт+0.5д)+Высота/2д;
Для гор=0 по Ширина-1 Цикл
Напр_X = (гор+0.5д)-Ширина/2д;
Направление = Вектор.Нормализация( Новый Вектор(Напр_X,Напр_Y,Напр_Z) );
Кадр[линия+гор] = ТрассироватьЛуч( Камера, Направление );
КонецЦикла;
КонецЦикла;

КонецПроцедуры

Процедура СохранитьКадр( ИмяФайла тип Строка)
файл=Новый ТекстовыйДокумент;

файл.ДобавитьСтроку("P3");
файл.ДобавитьСтроку(""+Ширина+" "+Высота);
файл.ДобавитьСтроку("255");

//Для п=0 по Высота*Ширина-1 Цикл
Для Инд тип Целое = 0 по Высота*Ширина-1 Цикл //делаем переменную цикла целой!
Пиксел = Кадр[Инд];
перем м1 тип ДВещ = Пиксел.x;
перем м2 тип ДВещ = Пиксел.y;
перем м3 тип ДВещ = Пиксел.z;
МаксИнт = Макс( м1, Макс(м2,м3) );
Если МаксИнт>1 Тогда
МаксИнт = 1/МаксИнт;
Пиксел.x = Пиксел.x * МаксИнт;
Пиксел.y = Пиксел.y * МаксИнт;
Пиксел.z = Пиксел.z * МаксИнт;
КонецЕсли;
файл.ДобавитьСтроку( ""+Норм_Цвет(Пиксел.x)+" "+Норм_Цвет(Пиксел.y)+" "+Норм_Цвет(Пиксел.z) );
КонецЦикла;

ВыводСтроки ИмяФайла

файл.Записать(ИмяФайла,КодировкаТекста.ANSI);


КонецПроцедуры


Процедура Старт

Пи = 3.14159265359;
МАКС_Число = 999999999999999;
ГЛУБИНА_РЕКУРСИИ = 4;

НулевойВектор=Новый Вектор(0, 0, 0);
ЕдиничныйВектор=Новый Вектор(1, 1, 1);
ЕдиничныйВекторX=Новый Вектор(1, 0, 0);
ЕдиничныйВекторY=Новый Вектор(0, 1, 0);
ЕдиничныйВекторZ=Новый Вектор(0, 0, 1);

ЦветБелый=ЕдиничныйВектор;
ЦветЖелтый=Новый Вектор(1, 0.7, 0.3);

Ширина=1024;
Высота=768;
УголЗрения = Пи/3;
Кадр = Новый Вектор[Ширина*Высота]

ЦветФона=Новый Вектор(0.2, 0.7, 0.8);

Серый =   Новый Материал( Новый Вектор( 0.4, 0.4, 0.3 ), 0.6, 0.3,0.1,0,    50,1 );
Стекло =  Новый Материал( Новый Вектор( 0.6, 0.7, 0.8 ), 0,   0.5,0.1,0.8, 125,1.5 );
Красный = Новый Материал( Новый Вектор( 0.3, 0.1, 0.1 ), 0.9, 0.1,0.0,0,    10,1 );
Зеркало = Новый Материал( Новый Вектор( 1.0, 1.0, 1.0 ), 0,  10.0,0.8,0,  1425,1 );

ПлиткаБелая =  Новый Материал( Вектор.Умножить(ЦветБелый,0.3),  1,0,0,0, 0,1 );
ПлиткаЖелтая = Новый Материал( Вектор.Умножить(ЦветЖелтый,0.3), 1,0,0,0, 0,1 );

Сферы = Новый Сфера[3]
Сферы[0]=Новый Сфера(Новый Вектор(-3,   0,  -16), 2, Серый )
Сферы[1]=Новый Сфера(Новый Вектор(-1.0,-1.5,-12), 2, Стекло )
Сферы[2]=Новый Сфера(Новый Вектор( 1.5,-0.5,-18), 3, Красный )
Сферы[3]=Новый Сфера(Новый Вектор( 7,   5,  -18), 4, Зеркало )

Освещение = Новый Свет[2]
Освещение[0]=Новый Свет(Новый Вектор(-20, 20,  20), 1.5)
Освещение[1]=Новый Свет(Новый Вектор( 30, 50, -25), 1.8)
Освещение[2]=Новый Свет(Новый Вектор( 30, 20,  30), 1.7)

т0=ТекущаяУниверсальнаяДатаВМиллисекундах();
Рендер();
т1=ТекущаяУниверсальнаяДатаВМиллисекундах();
ВыводСтроки("~"+ Цел(т1-т0) );

СохранитьКадр(ЭтаПрограмма.Каталог+"out.ppm");

Консоль.Пауза

КонецПроцедуры

КонецПрограммы


// ------------------
Класс Материал
&ВидноВсем Поле Цвет тип Вектор
&ВидноВсем Поле Альб0 тип ДВещ
&ВидноВсем Поле Альб1 тип ДВещ
&ВидноВсем Поле Альб2 тип ДВещ
&ВидноВсем Поле Альб3 тип ДВещ
&ВидноВсем Поле ЭкспОтраж тип ДВещ
&ВидноВсем Поле КПрелом тип ДВещ
//---------------------------
&ВидноВсем
Конструктор(пЦвет тип Вектор, пАльб0 тип ДВещ, пАльб1 тип ДВещ, пАльб2 тип ДВещ, пАльб3 тип ДВещ, пЭкспОтраж тип ДВещ, пКПрелом тип ДВещ)
Цвет = пЦвет
Альб0 = пАльб0
Альб1 = пАльб1
Альб2 = пАльб2
Альб3 = пАльб3
ЭкспОтраж = пЭкспОтраж
КПрелом = пКПрелом
КонецКонструктора
КонецКласса


// ------------------
Класс Свет
&ВидноВсем Поле Поз тип Вектор
&ВидноВсем Поле Ярк тип ДВещ
//---------------------------
&ВидноВсем
Конструктор(пПоз тип Вектор, пЯрк тип ДВещ)
Поз=пПоз
Ярк=пЯрк
КонецКонструктора
КонецКласса

// ------------------
Класс Сфера
&ВидноВсем Поле Центр тип Вектор
&ВидноВсем Поле Радиус тип ДВещ
&ВидноВсем Поле Материал тип Материал
//---------------------------
&ВидноВсем
Конструктор( пЦентр тип Вектор, пРадиус тип ДВещ, пМатериал тип Материал )
Центр=пЦентр
Радиус=пРадиус
Материал=пМатериал
КонецКонструктора
КонецКласса


 

Как видите, классы очень органично легли в программу, и это не удивительно, потому что они были в исходной версии на С++.

Что же теперь со скоростью? Это невероятно! Программа стала выполняться быстрее в 500 раз! Это конечно не так быстро как в C++, но учитывая гораздо более простой процесс разработки, результат более чем достойный.

 
Что еще можно предпринять для ускорения программы? Добавим в программу параллельности.
 
Текст изменений:

//1) добавляем поля

//переменные для параллельного цикла
Поле Камера тип Вектор;
Поле линия тип ДВещ;
Поле Напр_Y тип ДВещ;
Поле Напр_Z тип ДВещ;

//2) изменяем процедуру Рендер

Процедура Рендер()

Камера = Новый Вектор(0,0,0);
Напр_Z =-Высота/(2*Tan(УголЗрения/2));
Для верт=0 по Высота-1 Цикл
линия = верт*Ширина;
Напр_Y = -(верт+0.5д)+Высота/2д;

//распараллелим
ПараллельныеДействия.Для(0, Ширина-1, ПолучитьДелегат(,ТелоЦикла,"ДействиеПроц<Целое>"))

КонецЦикла;

КонецПроцедуры


//3) добавляем тело параллельного цикла


//---------------------------
//тело параллельного цикла
Процедура ТелоЦикла(гор тип Целое)
Напр_X = (гор+0.5д)-Ширина/2д;
Направление = Вектор.Нормализация( Новый Вектор(Напр_X,Напр_Y,Напр_Z) );
Кадр[линия+гор] = ТрассироватьЛуч( Камера, Направление );
КонецПроцедуры    

 

Производительность возрастает кратно количеству имеющихся физических ядер процессора.
Все современные компьютеры оснащены минимум двух-ядерными процессорами, поэтому заявленный в заголовке прирост производительности в 1000 раз вам обеспечен. А если у вас есть еще и мощный сервер, то грех ему простаивать)
 
randraytracer
 
Теперь уже можно полноценно пользоваться программой. Давайте её немного усовершенствуем. Сделаем так, чтобы программа случайным образом размещала свет и объекты, а мы будем выбирать самые удачные кадры.
 

Вот что у меня получилось:

 
 
Ещё немного:
 

 

И ещё

 

 

И всё

 

 

Слабые варианты (определяются по малому времени рендеринга) программа пропускает сама. Еще программа берет параметры (из имени файла) уже существующих в папке изображений, для построения на их основе новых. Так что можно сказать, что программа учитывает ваши предпочтения. Богатый материал для психодиагностики)
 
Для скачивания доступны две программы:
randraytracer1 генерирует случайные изображения небольшого разрешения для отбора удачных вариантов.
randraytracer2 увеличивает разрешение и глубину рекурсии выбранных изображений.
Для их запуска потребуется установить дистрибутив языка "Перфолента"

 

6 Comments

  1. SerVer1C

    Сравнивать IL под .Net платформу с псевдобайткодом стековой машины 1с, думаю, не уместно, т. к. последний в алгоритмических задачах, мягко сказать, просаживается по производительности в сотни раз.

    Reply
  2. vasvl123

    Цель статьи наглядно продемонстрировать возможности нового языка. Ранее недоступные.

    Reply
  3. Perfolenta

    (1) зато хороший пример того, что иногда производительность имеет значение…

    пользоваться программой до переделки совершенно не возможно…

    а еще, показывает, что при необходимости критичный код перевести на Перфоленту не трудно…

    и картинки красивые получились, хоть на рабочий стол ставь 🙂

    Reply
  4. Perfolenta

    (2) кстати, да, интересный ход, пропускать слабые кадры по времени рендеринга… если шары расположились кучкой друг за другом, то картинка вряд-ли будет интересной!

    Reply
  5. shard

    генератор картинок на рабочий стол, стандартные обои кубунты некоторых релизов напомнило)

    Reply
  6. Perfolenta

    Отрендерил в 4К и посмотрел на большом телевизоре.. гораздо интереснее выглядит, чем сжатые кадры маленького разрешения, которые тут в скриншотах показаны…

    Reply

Leave a Comment

Ваш адрес email не будет опубликован. Обязательные поля помечены *