Здравствуйте товарищи программисты. Нужно разработать и отладить Алгоритм Робертсона для октаэдрa (фигура такая), так же эта фигура должна вращаться.
Фигура статичная, объявленная через константу. Есть затруднения в написании процедуры для алгоритма. Я уже написал построение самой фигуры, её вращение тоже реализовал, правда у меня она подтормаживает на моем паскале free..
Итак в чем смысл алгоритма...
Алгоритм Робертса представляет собой первое известное решение задачи об удалении невидимых линий. Это математически элегантный метод, работающий в объектном пространстве. Алгоритм прежде всего удаляет из каждого тела те ребра или грани, которые экранируются самим телом. Затем каждое из видимых ребер каждого тела сравнивается с каждым из оставшихся тел для определения того, какая его часть или части, если таковые есть, экранируются этими телами. Поэтому вычислительная трудоемкость алгоритма Робертса растет теоретически, как квадрат числа объектов. Это в сочетании с ростом интереса к растровым дисплеям, работающим в пространстве изображения, привело к снижению интереса к алгоритму Робертса. Однако математические методы, используемые в этом алгоритме, просты, мощны и точны. Кроме того, этот алгоритм можно использовать для иллюстрации некоторых важных концепций. Наконец, более поздние реализации алгоритма, использующие предварительную приоритетную сортировку вдоль оси z и простые габаритные или минимаксные тесты, демонстрируют почти линейную зависимость от числа объектов.
Работа Алгоритм Робертса проходит в два этапа:
1. Определение нелицевых граней для каждого тела отдельно.
2. Определение и удаление невидимых ребер.
Нужно реализовать это через процедуру, чтобы её можно вставить в любую программу.
Мы определяем видимость грани, если она не видна мы ставим флажок на False, изначально стоит True
Я так понимаю нужно попробовать реализовать счетчиком по формуле....
Давайте подумаем вместе!
Мне кажется, что тут одной процедуры не хватит, сначала сделайте проверку на флаг. А потом отдельно делайте очистку и дополнительную прорисовку! допустим возьмем счетчик j, дальше в фикле от 1 до последнего. Ставите на счетчик ноль и верный, затем проверяете условия алгоритма, сбрасывайте флаг, если область невидима.
Цитата: SeriousPasha от 04-12-2012, 23:06:53
Мне кажется, что тут одной процедуры не хватит, сначала сделайте проверку на флаг. А потом отдельно делайте очистку и дополнительную прорисовку! допустим возьмем счетчик 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;Так? или я вас не так понял?
Да так, основываясь на то, что вы мне прислали в Личное сообщение - нужна процедура прорисовки и очистки, попробовал написать. получилось, что-то такое:
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;
Интересная задача... И алгоритм интересный (почитал в интернете про него).
А вы уже с плоскостью разобрались?
Реализация вращения хромает... но я думаю так пойдет.
А почему имено октаэдер? Можно же бы сделать кубик.
Интересный алгоритм, нужно будет применять и на практике. Спасибо за идею!
ЦитироватьА почему имено октаэдер? Можно же бы сделать кубик.
Легче описать...
Ладно начнем собирать программу по винтикам. :D
А можно всю программу? интересно посмотреть. Может дам пару советов.
Вот всё что у меня вышло...
program octahedr25;
uses crt,graph;
type point_positia = array [1..3] of real;
type side_positia = array [1..3] of point_positia;
type oct_crd = array [1..8] of side_positia;
const Color: array[1..8] of Integer = (1,2,3,4,5,6,9,10);
{фигура Октаэдрa описание}
const oct: oct_crd= (((100,100,60),(50,100,-40),(100,50,-40)),
((100,100,60),(50,100,-40),(100,150,-40)),
((100,100,-140),(100,50,-40),(50,100,-40)),
((100,100,-140),(100,150,-40),(50,100,-40)),
((100,100,-140),(150,100,-40),(100,50,-40)),
((100,100,-140),(100,150,-40),(150,100,-40)),
((100,100,60),(100,50,-40),(150,100,-40)),
((100,100,60),(150,100,-40),(100,150,-40)));
const p=-0.002;
var
pcos,psin:real;
oct_new,oct_old:oct_crd;
dv,mv,x0, y0: integer;
procedure init;
var i,j,k:integer;
begin
x0 := getMaxX div 2;
y0 := getMaxY div 2;
for i:=1 to High(oct) do
for j:=1 to High(oct[i]) do
for k:=1 to High(oct[i,j]) do
begin
oct_new[i,j,k] := oct[i,j,k];
oct_old[i,j,k] := oct[i,j,k];
end;
end;
{алгоритм робертса реализация паскаль}
function robert(side:side_positia):boolean;
var
a,b,c:real;
i,j:integer;
begin
c:=0;
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;
{процедура получения перспектив в одной точке схода}
procedure modif(x,y,z:real;var x1,y1,z1:real);
begin
x1:=x/(p*y+1);
y1:=y/(p*y+1);
z1:=z/(p*y+1);
end;
{прорисовка и очистка октаэдра в зависимости от флага new}
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;
{поворот октаэдра}
procedure rotate;
var
i, j: integer;
x_new, z_new: real;
begin
for i:=1 to High(oct_new) do
for j:=1 to High(oct_new[1]) do
begin
oct_old[i,j,1] := oct_new[i,j,1];
oct_old[i,j,3] := oct_new[i,j,3];
x_new:=oct_new[i,j,1]*pcos-oct_new[i,j,3]*psin;
z_new:=oct_new[i,j,1]*psin+oct_new[i,j,3]*pcos;
oct_new[i,j,1]:=x_new;
oct_new[i,j,3]:=z_new;
end;
end;
{основная часть программы}
begin
pcos:=cos(0.05);
psin:=sin(0.05);
dv := detect;
initGraph(dv,mv,'');
init;
repeat
rotate;
draw_oct(false,oct_old);
draw_oct(true,oct_new);
delay(10000);
until keypressed;
closegraph;
end.
Вроде работает! буду сдавать. Всем спасибо!
А помогите для куба с реализацией этого алгоритма (делфи)