Реализация Алгоритма Робертса + задача [Pascal]

[[Lichkin-rus]]

Здравствуйте товарищи программисты. Нужно разработать и отладить Алгоритм Робертсона для октаэдрa (фигура такая), так же эта фигура должна вращаться.

Фигура статичная, объявленная через константу. Есть затруднения в написании процедуры для алгоритма. Я уже написал построение самой фигуры, её вращение тоже реализовал, правда у меня она подтормаживает на моем паскале free..

Итак в чем смысл алгоритма...

Алгоритм Робертса представляет собой первое известное решение задачи об удалении невидимых линий. Это математически элегантный метод, работающий в объектном пространстве. Алгоритм прежде всего удаляет из каждого тела те ребра или грани, которые экранируются самим телом. Затем каждое из видимых ребер каждого тела сравнивается с каждым из оставшихся тел для определения того, какая его часть или части, если таковые есть, экранируются этими телами. Поэтому вычислительная трудоемкость алгоритма Робертса растет теоретически, как квадрат числа объектов. Это в сочетании с ростом интереса к растровым дисплеям, работающим в пространстве изображения, привело к снижению интереса к алгоритму Робертса. Однако математические методы, используемые в этом алгоритме, просты, мощны и точны. Кроме того, этот алгоритм можно использовать для иллюстрации некоторых важных концепций. Наконец, более поздние реализации алгоритма, использующие предварительную приоритетную сортировку вдоль оси z и простые габаритные или минимаксные тесты, демонстрируют почти линейную зависимость от числа объектов.

Работа Алгоритм Робертса проходит в два этапа:

1.     Определение нелицевых граней для каждого тела отдельно.
2.     Определение и удаление невидимых ребер.

Нужно реализовать это через процедуру, чтобы её можно вставить в любую программу.
Мы определяем видимость грани, если она не видна мы ставим флажок на False, изначально стоит True

Я так понимаю нужно попробовать реализовать счетчиком по формуле....

Давайте подумаем вместе!

[SeriousPasha]

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

[[Lichkin-rus]]

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

Спасибо! Будем пробовать!

Пока получается так: (Вот пока наработки, тоесть мы берем из программы грани и проверяем их на видимость), если c<=0, то грань не видна.

Код Выделить Развернуть

function robert(side:side_positia):boolean;
var
a,b,c:real;
i,j:integer;
begin
c:=1;
robert:=true;
for i:=1 to high(side) do
begin
if i=high(side) then j:=1
else j:=i+1;

c:=c+(side[i,1]-side[j,1])*(side[i,2]+side[j,2]);
end;
if c<=0 then robert:=false;

end;

Так? или я вас не так понял?

[SeriousPasha]

Да так, основываясь на то, что вы мне прислали в Личное сообщение - нужна процедура прорисовки и очистки, попробовал написать. получилось, что-то такое:

Код Выделить Развернуть

procedure draw_oct(new: boolean;figure:oct_crd);
var
i,j,k:integer;
area: array [1..3] of PointType;
new_side:side_positia;
begin
setcolor(0);
for i:=1 to high(oct_new) do
begin

for k:=1 to high(new_side) do
begin
modif(figure[i,k,1], figure[i,k,2], figure[i,k,3],
new_side[k,1],new_side[k,2],new_side[k,3]);

end;
if robert(new_side) then
begin
if new then
begin
setFillStyle(solidfill, Color[i]);

end
else begin
setFillStyle(solidfill, 0);
end;
for j:=1 to High(new_side) do
begin
area[j].X :=x0+ round(new_side[j,1]);
area[j].Y := round(new_side[j,2]);
end;
fillpoly(sizeOf(area) div sizeOf(pointtype),area);

end;
end;
end;

[drummer]

Интересная задача... И алгоритм интересный (почитал в интернете про него).

А вы уже с плоскостью разобрались?

[SeriousPasha]

Реализация вращения хромает... но я думаю  так пойдет.

[ioshkarola]

А почему имено октаэдер? Можно же бы сделать кубик.

[diy05]

Интересный алгоритм, нужно будет применять и на практике. Спасибо за идею!

[[Lichkin-rus]]

А почему имено октаэдер? Можно же бы сделать кубик.

Легче описать...

Ладно начнем собирать программу по винтикам. 

[rz00007]

А можно всю программу? интересно посмотреть. Может дам пару советов.