Олимпийские будни

Как я уже упоминал на страницах блога есть несколько ВУЗов, чьи успехи по внедрению САПР в учебный процесс вызывают в моей душе если не восхищение, то уважение. Одним из этих ВУЗов является БГТУ им. Шухова. О нем я писал совсем недавно по этому и упоминаю первым в списке. Вторым назову “Хмельницкий Национальный Университет”. Вторым он идет потому как дальнейшая информация связана с ним.

Из года в год, на протяжении вот уже тринадцати лет данный ВУЗ проводит олимпиаду под названием: “САПР и компьютерное моделирование в машиностроении”. Причем олимпиаду проводит в двух вариантах – очная, которая проходит в середине апреля в г. Хмельницке, и заочная – в начале декабря. Задания данных олипиад проще всего охарактеризовать как “разработка систем автоматизации проектирования”. Что под этим понимается? А понимается целый класс задач – распознавание, CAD дополнения автоматизирующие те или иные задачи проектирования,  векторизация и много чего другого. Обычно на очной олимпиаде дается 4-6 заданий разной направленности и сложности и дается на выполнение около четырех часов. На следующей за очным весенним туром зимней заочной олимпиадой, даются +/- те же задания, по крайней мере наиболее популярные в очном туре там встречаются, ну и иногда проскакивает нечто новое. На выполнение заочного задания отводится аж неделя. При этом следует отметить, что студентам участвующим в олимпиаде никто не отменяет основные занятия, итого времени остается не многим больше.

Естественно заочность олимпиады создает ряд проблем, но все они ложатся на совесть участников. Мы не первый год участвуем в обоих олимпиадах, но обычно особо похвастаться нечем. Заочный тур чаще всего проваливается по разным причинам. То народ заболеет, то интернет отключится в неподходящий момент… в общем отмазки получаются разные абы не позориться ;)

В очном туре от нас (от политеха) обычно участвуют два “заклятых” друга – кафедра ДПМ и моя родная кафедра. Заклятость проявляется в том, что мы давно друг друга знаем и во многом сотрудничаем, но во многом и соперничаем к всеобщему удовольствию. Есть вещи в которых мы сильнее, есть вещи до которых нам далеко. Одним из таких моментов, в котором ДПМ традиционно сильнее и является данная олимпиада, вернее круг задач близкий к ней. Мы то пытаемся подтянуться, но пока успехи маловаты :(. А уж за лидером – Хмельницким угнаться вообще не легко.

Так вот за 12 лет организаторы выдали на гора уже около 50 различных задач. В связи с тем, что даже очень богатое воображение тоже может выдохнуться, организаторы постоянно просят другие ВУЗы помочь с созданием задач. Обычно все обещают, но редко кто присылает. В прошлый мой приезд, я пообещал с этим делом немного помочь, и в результате обсуждения многие задачи были отбракованы, но родились две, которые я и хотел бы предъявить на суд общественности. В связи с тем, что обе задачи уже участвовали и в очном и в заочном туре, думаю проблем с публикацией быть не должно. Итак задача №1.

Задача: “Shape from Shading” получить геометрию объекта из «закраски». Он же «генератор ландшафта»

В качестве исходных данных для программы выступает следующая информация:

1. графический файл произвольного разрешения в градациях серого
2. длина искомого трехмерного объекта (масштаб по Х)
3. ширина искомого трехмерного объекта (масштаб по Y)
4. разница высот между самой нижней и самой верхней точками искомого объекта
5. положение  центра координат
6. метод воостановления геометрии:

·         - равномерный шаг по длине и ширине (количество линий уровня)

·         - определение густоты сетки из разницы градиента цвета

 

По умолчанию считается что:

1. координаты  Х, Y, Z искомого объекта меняются в пределах 0 - 1
2. центр координат лежит в нижнем левом углу графического файла
3. количество линий уровня = 10

Рис.1	Рис.2

 

 

Построенную геометрию необходимо:

1. визуализировать внутри собственной программы

◦       в изометрическом виде

◦       в трехмерном виде (с возможностью вращения, масштабирования и пр. к примеру с использованием OpenGL или Direct3D)

2. передать/построить в произвольную CAD систему  (на выбор разработчика)

◦       в сеточном формате

◦       в формате аналитически заданной поверхности (NURBS, B-Spline и пр.)

 

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

1.      Обработка исходного изображения:

1.      изменение цветности изображения

2.      поворот, зеркалирование изображения

3.      обрезка изображения

4.      сглаживание/резкость, контраст/яркость

5.      попиксельное редактирование: «резинка», «карандаш», «кисти» с различными эффектами (к примеру сглаживание), заливка области и пр..

2.      Обработка полученной геометрии:

1.      поворот полученной геометрии в трехмерном пространстве

2.      «обрезка» полученной геометрии до нужной формы границы

3.      «склейка» нескольких трехмерных кусков

4.      алгебраические операции (сложение, вычитание, усреднение) нескольких трехмерных кусков в единое целое

5.      наложение текстуры

6.      анализ полученной геометрии (возможностями собственной программы):

1.      кривзна/радиус

2.      «зебра»

3.      линии равного уровня (по всем координатам)

4.      прочее

2.      Экспорт :

◦       сеточной геометрии в STL формат

◦        поверхности в IGES/STEP

◦       кривых уровня в IGES/STEP/DXF

 

 

Приложение1. Структура файла в формате STL

solid Object01

  facet normal 7.160495e-002 -2.368895e-001 9.688942e-001

    outer loop

      vertex 8.335612e+000 -1.087681e+002 2.561384e+001

      vertex 1.934397e+001 -1.055182e+002 2.559488e+001

      vertex 1.927599e+001 -9.714783e+001 2.764641e+001

    endloop

  endfacet

  facet normal 8.911768e-002 -2.524342e-001 9.635015e-001

    outer loop

      vertex 1.927599e+001 -9.714783e+001 2.764641e+001

      vertex 7.897567e+000 -1.003823e+002 2.785143e+001

      vertex 8.335612e+000 -1.087681e+002 2.561384e+001

    endloop

  endfacet

…

endsolid Object01

solid Object02

…

endsolid Object02

…

 

 

solid – начало тела, поверхности, объекта

endsolid – конец информации по телу/поверхности

В цикле solid - endsolid – содержится информация о всех полигонах описывающих геометрию объекта

Object01, Object02 – название тел, поверхностей, объектов

 

facet normal – начало данных по полигону.

endfacet – конец данных по полигону

В цикле facet normal - endfacet – содержится следующая информация: нормаль к полигону и список вершин.

 

outer loop, end loop – обозначение начала и конца списка вершин полигона соответственно

vertex – координаты вершин треугольника

 

            Жирным шрифтом выделены стандартные обозначения формата. Курсивом выделены куски кода, которые могут содержать произвольную информацию. Все цифры описывающие особенности геометрии подчеркнуты. Формат STL не содержит информацию о единицах измерений. Формат STL работает исключительно с прямоугольной декартовой системой координат для описания трехмерных объектов. Все команды и цифры разделены между собой пробелами.

Для уменьшения количества ошибок чтения *.stl файлов, не следует делать:

• пустых строк,
• полигонов содержащих количество вершин отличное от трех;

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

Приложение2. Методы оценки

 

Основная таблица оценки

	Вес (%)	Макс.баллы	Итог
1. Вычитка данных	10	10	1
2. Получение координат точек результирующей поверхности	30*
2.1. Равномерная сетка	10	10	1
2.2. Сетка от градиента	20	10	2
3.визуализировать внутри собственной программы	30*
3.1. в изометрическом виде	15	10	1,5
3.2. в трехмерном виде	15	10	1,5
4. Экспорт в CAD	30*
4.1. сеточный формат (открытие/создание)**	2/3	10/10	0,2/0,3
4.2. аналитический вид (открытие, создание)**	15/10	10/10	1,5/1
итого	100%	10	10

 

Таблица оценки дополнительных возможностей***

	Вес (%)	Макс.баллы	итог
1.      Обработка исходного изображения:	100****	0,5	0,5
1.1.   цветность	40*
1.1.1.      градации серого	10	10	1
1.1.2.      цветная палитра	30	10	3
1.2.   поворот, зеркалирование	5	10	0,5
1.3.   обрезка	5	10	0,5
1.4.   сглаживание, контраст	5	10	0,5
1.5.   попиксельное редактирование:	10	10	1
2.      Обработка полученной геометрии:	100****	0,5	0,5
2.1.   поворот	10	10	1
2.2.   «обрезка»	10	10	1
2.3.   «алгебра»	30	10	3
2.4.   текстуры	10	10	1
2.5.   анализ:	100****	0,5	0,5
1.5.1.            кривизна/радиус	20	10	2
1.5.2.            «зебра»	30	10	3
1.5.3.            линии равного уровня	10	10	1
1.5.4.            прочее (за каждую доп. возможность)	10	10	1

 

* Общий вес пункта оценки. Оценка по данному пункту состоит исключительно из суммы оценок подпунктов

** Открытие – открытие стандартной CAD уже готового файла в нейтральном формате. Создание – создание геометрии определенного типа внутри CAD системы.

*** Дополнительные возможности оцениваются в случае, если созданная программа набрала по основной таблице не менее чем 6 (шесть) итоговых баллов.

**** За наличие любой из возможностей пункта участник получает 0,5б + количество балов заработанных на подпунктах.

 

скачать вариант задания оформленный под распечатку можно тут:

Terrain Generator 2

Ну а вторая задача будет чуть позжее.

Комментарии. и дополнения.
Тестовые задачи:

С подобной задачей справляется большое количество программ ориентированных на игры и создание ландшафта. Из САПР с этой задачей справляются Rhinoceros, ArtCAM, MasterCAM и ряд других ****CAM систем. С точки зрения программирования задача тоже не сильно сложная, хотя есть и проблемные места. Например если шаг по картинке будет отличным от количества пикселов, то возникает вопрос, как интерпретировать данные внутри квадрата – то ли по минимуму, то ли по максимуму, то ли по среднему. Также очень проблемным получается резкий переход, такой как на второй картинке. Проблемным он получается, так как тоже нет однозначности в его интерпретации – то ли его сделать вертикальным, то ли его сделать с уклоном на величину шага между пикселями. Но это логические вещи, которые нужно решить для себя на начальном этапе. Остальное же – простейший код, который можно сделать за час – два из четырех (если не спешить), а остальное потратить на красивое оформление или ловлю блох.

Если считаете себя неплохим спецом в решении подобных вопросов, попробуйте создать программу в отведенные сроки и сравнить себя со студентами олимпийцами. ;) Успехов, всем кто будет пробовать.