на главную ] 

Использование языка MC# для реализаций параллельных алгоритмов в 3D моделировании.

Е.С.Борисов

суббота, 27 сентября 2003 г.

1 Введение

Без систем автоматизированного проектирования (САПР) уже трудно представить современное производство, которое можно коротко описать такой схемой :

САПР конструктора → САПР технолога → станок с ЧПУ

Первые 2D САПР представляли собой по сути электронные чертежные доски, упрощавшие процесс изготовления чертежей, но не позволявших выйти за рамки классической проекционной модели - вид сверху, вид сбоку и т.д. С появлением достаточно мощных вычислительных средств, у конструктора появилась возможность, используя методы проективной геометрии, перейти к 3D САПР, т.е. работать не с проекциями детали, а с её виртуальным 3-х мерным образом. Этот подход позволяет, без изготовления реальных деталей ''в железе'', промоделировать процесс сборки узла, выявить все несоответствия деталей относительно друг друга, буквально увидеть как одна деталь входит в другую и входит ли, и оперативно устранить обнаруженные огрехи. Таким образом, 3D моделирование является неотъемлемой частью такой системы.

Спроектированные детали хранятся в иерархической базе данных, называемой деревом проекта. В любой момент из дерева проекта можно загрузить но рабочую станцию конструктора нужные детали, проверить их соответствие друг другу, оценить вес, определить прочностные и прочие характеристики. Размеры такой базы данных, к примеру в авиастроении, могут достигать десятков терабайт (1012 байт).

2 Постановка задачи

Для хранения и обработки в реальном времени таких объемов данных как дерево проекта требуются системы сверхвысокой производительности [1] - многопроцессорные вычислительные системы. Программное обеспечение таких систем существенным образом использует методы и средства параллельного программирования. Задача которую мы будем рассматривать в данной статье это визуализация 3D объектов в реальном времени, как неотъемлемая часть виртуального конструирования. Постановку задачи можно сформулировать так : разработать параллельную программу, визуализации 3D объектов в реальном времени, используя средства параллельного программирования.

3 Пути и средства решения

3.1 Модель

Объект в 3-х мерном пространстве [2] представлен множеством точек, которые задаются постоянными координатами в неподвижной системе координат. Вид объекта, проецируемый на экран, определяется положением наблюдателя относительно неподвижной системы координат. Таким образом, необходимо определить две пространственные и одну плоскую систему координат (рис.1).

Рисунок 1: системы координат
\includegraphics[width=8cm]{pict/image1.ps}

Причем: OэкXэк || OнXн, OэкYэк || OнYн

Для отображения объекта на экране OэкXэкYэк необходимо для каждой точки данного объекта выполнить два преобразования : видовое и перспективное. Возьмем произвольную точку M, принадлежащую объекту и имеющую координаты (x,y,z) в системе OXYZ.

  1. Видовое преобразование - переход от абсолютной системы OXYZ к системе координат наблюдателя OнXнYнZн. Положение системы координат наблюдателя OнXнYнZн относительно неподвижной системы координат объекта OXYZ определяется углами поворота φ , ψ, θ относительно соответствующих осей системы OXYZ и расстоянием ρ между центрами координат O и Oн (рис.1).


    [ xн yн zн 1 ] = [ x y z 1 ] . V (1)

    Матрица перехода V запишется следующим образом :


    cos(θ) . cos(ψ) + sin(θ) . sin(φ) . sin(ψ)     - cos(θ) . sin(ψ) + cos(ψ) . sin(θ) . sin(φ)     cos(φ) . sin(θ)     0   
     
    cos(φ) . sin(ψ)     cos(φ) . cos(ψ)     -sin(φ)     0   
     
    -cos(ψ) . sin(θ) + cos(θ) . sin(φ) . sin(ψ)     sin(θ) . sin(ψ) + cos(θ) . cos(ψ) . sin(φ)     cos(θ) . cos(φ)     0   
     
    0     0     ρ     1    

  2. Перспективное преобразование - проецирование точки М с новыми координатами (xн, yн, zн) в системе OнXнYнZн на экран OэкXэкYэк.
    xэк = ( xн / zн ) . d
    yэк = ( yн / zн ) . d
    (2)

    где d = OнOэк - расстояние от наблюдателя до экрана,

3.2 Язык программирования MC#

Язык программирования MC# [3] предназначен для написания программ, работающих на параллельных архитектурах. MC# является адаптацией языка Polyphonic C# [4] для распределенных вычислений. Ключевая особенность языка Polyphonic C# заключается в добавлении к обычным, синхронным так называемых асинхронных методов, исполняемых параллельно с основной программой. Для синхронизации методов обоих видов в язык C#, были введены новые конструкции, получившие название связок (chords). При этом, исполнение Polyphonic C# - программ, по замыслу авторов этого языка, предполагалось либо на одной машине, либо на нескольких с привлечением средств удаленного вызова методов .NET Remoting.

Специфика языка MC# состоит в перенесении модели асинхронного параллельного программирования языка Polyphonic C# на распределенный случай, когда автономный метод может быть автоматически спланирован для исполнения на наиболее подходящем (обычно, наименее загруженном) узле кластера. При этом методы, служащие для доставки значений, выделяются в специальный синтаксический класс, элементы которого называются Channel ( канал ).

Написание параллельной программы на языке MC# сводится к выделению с помощью специального ключевого слова movable методов, которые могут быть перенесены для исполнения на другие вычислительные узлы, и организации их взаимодействия через каналы с использованием связок.

Ранее, аналогичный подход, в котором программист разбивал все функции в своей программе на ''перемещаемые'' и ''неперемещаемые'', использовался в Т-системе [5], предназначенной для динамического распараллеливания программ на языке С.

Адрес разработчиков языка MC# - yury@serdyuk.botik.ru

4 Решение

4.1 Реализация с распараллеливанием

Соответственно представленной выше модели на языке MC# написана параллельная программа. На этапе инициализации программы генерируются оси координат, куб и множество случайных точек. Изменяя положение наблюдателя (φ,ψ,θ,ρ на рис.1) можно посмотреть на эту сцену с разных сторон.

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

3D пространство реализуется классом Space3D. Объект в этом пространстве описывается множеством точек m_points. Для того чтобы отобразить этот объект на экране необходимо для каждой точки объекта рассчитать ее экранные (плоские) координаты по (1)(2).

Все множество точек m_points, делится на несколько частей методом makePoints и каждая такая часть обрабатывается независимо от других методом makePointsPar. Собственно, механизм распараллеливания заключен в двух методах makePointsPar и Get :

class Space3D { 
. . .
protected Point3D [] m_points;
. . .
public void makePoints() {
. . .
makeMatrix();
for(int i=0;i<PROCESS_COUNT;i++){ ... ; makePointsPar(P,m_chanel); }
for(int i=0;i<PROCESS_COUNT;i++){ Get(); }
}

public movable makePointsPar( Point3D[] P, Channel ( Point3D[] ) c ) {
. . .
for ( int i = 0; i < length; i++ ) {
x_obs = m_V[0,0]*P[i].x()+m_V[1,0]*P[i].y()+m_V[2,0]*P[i].z()+0;
y_obs = m_V[0,1]*P[i].x()+m_V[1,1]*P[i].y()+m_V[2,1]*P[i].z()+0;
z_obs = m_V[0,2]*P[i].x()+m_V[1,2]*P[i].y()+m_V[2,2]*P[i].z()+m_V[2,3];
P[i].x_scr( ix( SCREEN_DIST*(x_obs/z_obs) + CX ) );
P[i].y_scr( iy( SCREEN_DIST*(y_obs/z_obs) + CY ) );
}
c(P);
}

public void Get() & Channel m_chanel( Point3D[] P ) {
int length = P.Length;
for(int i=0;i<length;i++){
m_points[P[i].index()].xy_scr(P[i].x_scr(),P[i].y_scr());
}
}
. . .
}

5 Результат

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

При увеличении количества процессоров, предполагается ускорение близкое к линейному. Ускорение[6] на p процессорах это отношение

s(p)=T(1) / T(p)

где T(1) и T(p)- время выполнения программы на 1 и p процессорах соответственно.

Рисунок 2: screenshot программы
\includegraphics[width=14cm]{pict/cube.ps}

Текст программы на MC# [ здесь ]

Литература


1
Борисов Е.С. Вычислительные системы сверхвысокой производительности. - http://www.mechanoid.kiev.ua/parallel-high-performance-computing.html
2
Аммерал Л. Принципы программирования в машинной графике. - Москва : Сол Систем, 1992. - 220 c.
3
MC# - http://www.mcsharp.net
4
Polyphonic C# - http://research.microsoft.com/~nick/polyphony
5
СКИФ - http://skif.pereslavl.ru
6
Дорошенко А.Е. Математические модели и методы организации высокопроизводительных параллельных вычислений. - Киев : Наукова думка, 2000. - 176 c.


Evgeny S. Borisov
2003-09-27
При использовании материалов этого сайта, пожалуйста вставляйте в свой текст ссылку на мою статью.