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

24.07.2019 6 Comments

Практика программирования, Разработка

, , ,

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

 

Предлагаю на время отвлечься от задач автоматизации, и погрузиться в загадочный и увлекательный мир 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 увеличивает разрешение и глубину рекурсии выбранных изображений.
Для их запуска потребуется установить дистрибутив языка "Перфолента"

 

Related Posts

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 не будет опубликован. Обязательные поля помечены *