среда, 20 мая 2009 г.

Сага о болте и тени

Преамбула
Году в 2002-м, а может в 2003-м, когда я еще работал в одном небезызвестном НИИ произошла эта история, которая окончилась ничем.

Сидел я на одной из местного пошиба весенних конференций, слушал про достижения "передовой" науки. Скучно было хоть режь… Как правило там докладывают про то, в чем мало кто понимает, причем из года в год одно и то же, но обязательно все хлопают в ладоши. Одним из докладов был доклад одной моей сотрудницы Лены (тогда она еще работала там, сейчас уже нет). Доклад Лены заставил меня проснуться.

Проблематика заключалась в следующем: перед нашими математиками (а я принадлежал касте простых программистов) стояли задачи счета на геометрии, описываемой в виде аналитически заданных поверхностей и их комбинаций. Для чего говорить не буду, кто знает – поймет, а кто не знает – не важно это... Задачи они решали, и по всей видимости, не один десяток лет. Проблема была в том, чтобы быстро и качественно описывать эту геометрию для непростых случаев.

Задание уравнений поверхностей происходило в текстовом виде в DSL, который напоминал мне многострочный лес регулярных выражений. Беда была в том, что язык этот был абсолютно чужд всему человеческому, понять его мне не посчастливилось. Геометрии, которые нужно было задавать были довольно большими, задавать их в текстовом виде было безобразно сложно. Посмотреть на эту геометрию глазами можно было, но не сразу. Для того чтобы посмотреть на картинку, нужно было скормить описание специально разработанной библиотеке (я ее буду называть движок ), которая могла отвечать на пространственные запросы типа лежит ли точка P в теле с именем X.

Тела представляли собой множества точек, ограниченных поверхностями, описываемых в этом DSL. Собственно сам DSL позволял записывать уравнения поверхностей (класс поверхностей был ограничен квадриками), позволял задавать операции над этими поверхностями, тем самым подразумевая теоретико-множественные операции над множествами точек пространства.
Так вот, для того, чтобы построить 3D сцену более-менее сложной геометрии, требовалось часто-часто прострелить пространство, и узнать, какого цвета (какому телу принадлежат) точки, потом сгруппировать эти точки по цвету, потом отрендерить в 3D, например OpenGL-ем. Еще этот движок мог (кажется) узнать расстояние от заданной точки до некоторого тела. Тоже на основе прострелов и некоторой логики оптимизации выбора следующей точки для прострела. В итоге построение сцены занимало часы (могу ошибаться, прошло много времени). Построение плоского среза, соразмерного с экраном монитора занимало что-то около нескольких минут.

Несложно представить, что процесс описания геометрии занимал очень много времени.
Работа сотрудницы Лены заключалась в том, чтобы предоставить интерактивный 3D редактор, позволяющий оперировать примитивными телами и транслирующий набор примитивных тел в DSL для последующего счета. Набор примитивов (сфера, плоскость, труба и т.п.) обладает известным при рендеригне набором точек, потому рендерить такие тела гораздо проще, чем извлекать информацию о точках из пространства с набором аналитических формул. Вроде бы были проблемы при построении набора примитивов по готовому текстовому описанию геометрии.

А болт тут вот причем: т.к. показывать реальные картинки актуальных для обсчетов геометрий на конференции было нельзя, а даже и видеть их могло только очень ограниченное кол-во сотрудников, то все работы с написанием и отладкой интерактивного редактора происходили на простенькой сцене с болтом (в хорошем смысле слова).

Представим ее:
  • Плоскость обозначающая стену. Т.е. по одну сторону от плоскости стена, по другую - не стена. Может я стену сам придумал, не помню;
  • На некотором расстоянии от стены находится полусфера, обозначающая шляпку болта. Полусфера - это комбинация сферы и плоскости;
  • В полусфере вырезан шлиц, как нехитрая комбинация трех плоскостей, выкусывающих кусок шляпки болта;
  • Цилиндр, соединяющий шляпку со стеной и уходящий в стену на некоторое расстояние.
Резьбы у болта не было. Ограничены квадриками ведь.
Лене удалось построить действительно интерактивный редактор сцен. Вживую я его не видел, видел только слайды презентации. Но не о работе Лены речь.
Сама история
До конца конференции я тогда не досидел. Пришла в голову мысль собрать движок на кодогенерации, которая тогда стала доступна прямо из .NET-а.

Сварганил свой DSL. Нет, назвать это DSL, либо своим язык не поворачивается. Что-то вроде языка было сделано с тем расчетом, чтобы записывать уравнения поверхностей и операции над поверхностями в привычной для программиста форме, так чтобы нехитрыми манипуляциями над текстом можно было привести описание геометрии в исходные коды на C#, скомпилировать и выполнить в рантайме. Т.е. никаких парсеров, лексеров и т.п. не было. Это был полу-C#. Мне нужно было только доказательство состоятельности концепта, потому над деталями я не парился.

За два рабочих дня я слабал что-то (назовем это прототипом):
Bolt
Это что-то (тогда) поразило воображение своей скорострельностью. Плоский срез усложненной сцены с болтом прототип строил пол секунды. Прототип не имел ограничений на класс поверхностей, как видите, я добавил в стену штрихи, а к болту присобачил резьбу Архимеда!

Я не пытался заменить редактор сцены Лены, я имел надежду написать транслятор из родного DSL в мой с тем чтобы обеспечить более быстрый прострел пространства и решения сопряженных задач (таких как расстояние от точки до тела), которые использовались дальше в части долгих многонедельных числодробилках. Ожидал 100 кратное увеличение производительности движка (и это без возможностей инлайнинга, тогда JIT еще не умел инлайнить даже методы структур). Что так много, спросите вы? Просто реализация старого движка не была предельно эффективна, и было ей много лет. Тогда я помнил конкретные цифры из доклада на конференции, сейчас помню только порядок ускорения, который тогда прикинул на пальцах.

Показал тогда прототип сотрудникам, начальнику своего отдела, начальнику соседней лаборатории, где работала Лена, все были поражены. Подумал, что до математиков дойдет слушок и занялся своей непосредственной работой. По началу переживал, что что-то не идут математики.

Прошло года 2-3, Лена уже не работала в институте, я уже тоже паковал чемоданы. Перебирая барахло на винте наткнулся на прототип, рисующий болт, подумал чего добру пропадать? Надо сказать, что я не строил планов на научную степень, просто было обидно за идею.

Поймал начальника отдела математиков, а тот был как раз заказчиком того интерактивного редактора, что написала Лена. Разговор получился ни о чём. Да, как бы проблема производительности старого движка есть, но есть и другие проблемы. Старый движок сейчас переписывает одна девочка с фортрана на Watcom C++, ожидается некоторое улучшение производительности. Более кардинальные меры им не требуются.

Ходил пару дней в недоумении: потом меня образумил батя (он как раз из касты математиков в том НИИ). Батя мне сказал, что я со своим болтом отбросил тень на членов высшей касты.
Disclaimer (особый вид интеллектуальной индульгенции)
Вообще-то у меня плохая память, богатая фантазия, и это все неправда.
ЗЫ. А прототип - настоящий.