Алгоритм Робертса

← →
set © (2010-09-24 22:04) [0]

Здравствуйте. Я нарисовал куб в 3D с использованием GDI. Мне хотелось бы удалить невидимые грани, я нашел алгоритм Робертса и прочитал что он как раз подходит для куба и я решил его реализовать но к сожалению я немогу понять никак по найденным материалам в поисковиках как это можно сделать. Немогли бы вы мне пошагово написать как должен работать такой алгоритм чтобы я мог понять его работу и если можно с картинками. Зараннее спасибо откликнувшимся.

← →
@!!ex © (2010-09-24 22:51) [1]

И что там не понятно

← →
@!!ex © (2010-09-24 22:52) [2]

← →
@!!ex © (2010-09-24 22:52) [3]

Давай ты приведешь лучший материал который найдешь и спросишь что непонятно.
Никто для тебя рисовать картинки не будет.

← →
set © (2010-09-25 18:31) [4]

Вот к примеру возьмем эту ссылку на алгоритм: http://compgraph.ad.cctpu.edu.ru/roberts.htm

Вот список вопросов которые мне были непонятны для реализации алгоритм:

1. "Уравнение произвольной плоскости в трехмерном пространстве имеет вид aх + by + cz + d = 0". Непонятно как формула эта получилась? Я читал про уравнение поскости но непонял как оно работает.

2. "В матричной форме этот результат выглядит так: [x y z 1][P]T = 0 где [P]T = [a b c d] представляет собой плоскость."
2.1 Координаты [x y z 1] координаты чего и откуда 1 появилась и еденица постоянная ли величина?
2.2 А это что такое [P]T = [a b c d]? В этой матрице тоже координаты вписывать тока плоскости? И как их вписать если это координаты плоскости и если у каждой вершины координаты то 3?

3. "Если точка [S] лежит на плоскости, то [S]·[P]T = 0. Если же [S] не лежит на плоскости, то знак этого скалярного произведения показывает, по какую сторону от плоскости расположена точка. В алгоритме Робертса предполагается, что точки, лежащие внутри тела, дают отрицательное скалярное произведение, т. е. нормали направлены наружу."
Непонятно где же точка все таки должна предположительно находится чтобы показывать вне плоскости она или за плоскостью? И как у плоскости определить где передняя часть а где задняя чисто наглядно на осях координат?

← →
TUser © (2010-09-25 20:11) [5]

> 1. "Уравнение произвольной плоскости в трехмерном пространстве
> имеет вид aх + by + cz + d = 0". Непонятно как формула эта
> получилась? Я читал про уравнение поскости но непонял как
> оно работает.
>

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

Далее. Если ты понял, что я тут написал (что такое скалярное произведение, нормаль к плоскости, как его расписывают через коэффициенты и почему оно будет равно 0), то читай объяснения дальше. Если не понял, то тыпытаешься разобраться в алгоритме, который пока недоступен. Страшного ничего нет, не такие и сложные вещи надо познать, просто перепрыгивать через этот этап совсем не рекомедуется (все равно толку не будет). Это примерно как бином Ньютона учить, не научившись раскрывать скобки. Просто отложи на недельку этот алгоритм и иди читать про аналитическую геометрию и векторную алгебру. Мне нравится, например, учебник Шипачева "Высшая математика", коротко, понятно, типовые задачи решены и для большинства случаев моей жизни более чем достаточно.

> 2. "В матричной форме этот результат выглядит так: [x y
> z 1][P]T = 0 где [P]T = [a b c d] представляет собой плоскость.
> "
> 2.1 Координаты [x y z 1] координаты чего и откуда 1 появилась
> и еденица постоянная ли величина?
> 2.2 А это что такое [P]T = [a b c d]? В этой матрице тоже
> координаты вписывать тока плоскости? И как их вписать если
> это координаты плоскости и если у каждой вершины координаты
> то 3?

Так умножаются матрицы. Если распишешь результат в числах, то увидишь, что он идентичен записанному уравнению плоскости. Прочитать об этом можно в разделе "Линейная алгебра".

> 3. "Если точка [S] лежит на плоскости, то [S]·[P]T = 0.
> Если же [S] не лежит на плоскости, то знак этого скалярного
> произведения показывает, по какую сторону от плоскости расположена
> точка. В алгоритме Робертса предполагается, что точки, лежащие
> внутри тела, дают отрицательное скалярное произведение,
> т. е. нормали направлены наружу."
> Непонятно где же точка все таки должна предположительно
> находится чтобы показывать вне плоскости она или за плоскостью?
> И как у плоскости определить где передняя часть а где задняя
> чисто наглядно на осях координат?

Задняя (отрицательная) часть - та, по которую от плоскости находятся остальные вершины вногогранника. Надо выправить знак нормали соотвествующим образом.

← →
TUser © (2010-09-25 22:15) [6]

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

допустим, у нас есть таблицы
b11 b12
b21 b22
b31 b32
и
a11 a12 a21 a22
Записываем их так:
b11 b12 a11 a12 a21 a22 b11 b12 x y b21 b22 z w b31 b32 u t
xyzw - это элементы матрицы-результата. Вычисляются они так: надо взять соотвествующую строку первой матрицы и столбец второй, последовательно перемножить все их элементыи сложить. Например, x=a11*b11+a21*b21.

Да, еще значком Т в тех формулах обозначено переворачивание (транспонирование) матрицы. Соотвественно,
a [x y z 1][a b c d]T = [x y z 1] b = ax + by + cz + d c

← →
TUser © (2010-09-25 22:17) [7]

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

← →
@!!ex © (2010-09-25 23:29) [8]

> [4] set © (25.09.10 18:31)

Ясно.
Учебник по выш мату тебе в руки.

> [7] TUser © (25.09.10 22:17)

"Высшая математика за 21 день". :))

← →
TUser © (2010-09-25 23:31) [9]

> > И как у плоскости определить где передняя часть а где
> задняя
> > чисто наглядно на осях координат?
>
> Задняя (отрицательная) часть - та, по которую от плоскости
> находятся остальные вершины вногогранника. Надо выправить
> знак нормали соотвествующим образом.

Пардон, чушь сказал. Задняя (с точки зрениянаблюдателя) часть - это та, не в которую смотрит соотвествующая нормаль. То есть скалярное произведение этой нормали на вектор "к наблюдателю" - положительное.

← →
set © (2010-09-26 10:53) [10]

Спасибо огромное, буду читать геометрию кароче, тока нет у меня уверенности что я реализую этот алгоритм, за 2 года первый раз так встал на месте с программой, и тока работая с графикой я наконец за 7 лет после окончания школы понял что математика великая и красивая наука, жаль что так долго пришлось понять это.

← →
set © (2010-09-26 10:59) [11]

К стате вопрос остался еще один. Матрицей перемножаем плоскость и точку а относительно какой точки должно производится вычисление каковы ее координаты относительно граней куба?

← →
set © (2010-10-02 15:14) [12]

Вот мой код с алгоритмом робертса только вот что то неверно я немогу понять что. В массиве MIntScalProizVekNaMat[i] должны получится тока 3 отрицательные числа (три грани куба), а там совсем не то. Помогите разобратся :(

unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, ExtCtrls, Math; type TForm1 = class(TForm) Timer1: TTimer; procedure FormPaint(Sender: TObject); procedure FormCreate(Sender: TObject); procedure Timer1Timer(Sender: TObject); private { Private declarations } public { Public declarations } end; var Form1: TForm1; MIntVerKyb: array[1..8, 1..3] of integer; //Массив истинных координат вершин куба MIntVerKyb2: array[1..8, 1..3] of integer;//Массив временных координат куба MBytPloskKyb: array[1..6, 1..3] of byte;//Массив плоскостей с вершинами ReaYgolKyb: real; //Счетчик угла implementation {$R *.dfm} /////////////////////////////До загрузки формы////////////////////////////////// procedure TForm1.FormCreate(Sender: TObject); var i, j: integer; begin DoubleBuffered:= true;//Избавляемся от мерцания //Первоначальные координаты вершин куба MIntVerKyb[1, 1]:= 100; MIntVerKyb[1, 2]:= 100; MIntVerKyb[1, 3]:= 200; MIntVerKyb[2, 1]:= 200; MIntVerKyb[2, 2]:= 100; MIntVerKyb[2, 3]:= 200; MIntVerKyb[3, 1]:= 200; MIntVerKyb[3, 2]:= 200; MIntVerKyb[3, 3]:= 200; MIntVerKyb[4, 1]:= 100; MIntVerKyb[4, 2]:= 200; MIntVerKyb[4, 3]:= 200; MIntVerKyb[5, 1]:= 100; MIntVerKyb[5, 2]:= 100; MIntVerKyb[5, 3]:= 100; MIntVerKyb[6, 1]:= 200; MIntVerKyb[6, 2]:= 100; MIntVerKyb[6, 3]:= 100; MIntVerKyb[7, 1]:= 200; MIntVerKyb[7, 2]:= 200; MIntVerKyb[7, 3]:= 100; MIntVerKyb[8, 1]:= 100; MIntVerKyb[8, 2]:= 200; MIntVerKyb[8, 3]:= 100; //Копирование истинных вершин куба во временные For i:= 1 to 8 do begin for j:= 1 to 3 do begin MIntVerKyb2[i, j]:= MIntVerKyb[i, j]; end; end; //Создание массива вершин плоскости MBytPloskKyb[1,1]:= 1; MBytPloskKyb[1,2]:= 2; MBytPloskKyb[1,3]:= 3; MBytPloskKyb[2,1]:= 5; MBytPloskKyb[2,2]:= 6; MBytPloskKyb[2,3]:= 7; MBytPloskKyb[3,1]:= 4; MBytPloskKyb[3,2]:= 3; MBytPloskKyb[3,3]:= 7; MBytPloskKyb[4,1]:= 1; MBytPloskKyb[4,2]:= 2; MBytPloskKyb[4,3]:= 5; MBytPloskKyb[5,1]:= 1; MBytPloskKyb[5,2]:= 4; MBytPloskKyb[5,3]:= 8; MBytPloskKyb[6,1]:= 2; MBytPloskKyb[6,2]:= 3; MBytPloskKyb[6,3]:= 6; end;

//////////////////////Рисование и вычисление координат куба///////////////////// procedure TForm1.FormPaint(Sender: TObject); var i, j: integer;//Счетчик цикла X, Y: integer;//Координаты линий BlnF: boolean;//Завершает цикл MIntPloskostei:array [1..6, 1..4] of integer;//Массив представляет собой матрицу из уравнений плоскости MIntScalProizVekNaMat: array [1..6] of integer;//Массив результата скалярного произведения точки на матрицу тела IntTcX, IntTcY, IntTcZ: integer;//Хранение координат точки внутри плоскости begin With Form1.Canvas do begin Pen.Color:= clRed;//Цвет карандаша Brush.Color:= clBlack;//Цвет кисти BlnF:= false; //Находим уравнение плоскости и записываем его в массив For i:= 1 to 6 do begin MIntPloskostei[i, 1]:= MIntVerKyb2[MBytPloskKyb[i, 2], 2] * MIntVerKyb2[MBytPloskKyb[i, 3], 3] + MIntVerKyb2[MBytPloskKyb[i, 1], 2] * MIntVerKyb2[MBytPloskKyb[i, 2], 3] + MIntVerKyb2[MBytPloskKyb[i, 1], 3] * MIntVerKyb2[MBytPloskKyb[i, 3], 2] - MIntVerKyb2[MBytPloskKyb[i, 1], 3] * MIntVerKyb2[MBytPloskKyb[i, 2], 2] - MIntVerKyb2[MBytPloskKyb[i, 1], 2] * MIntVerKyb2[MBytPloskKyb[i, 3], 3] - MIntVerKyb2[MBytPloskKyb[i, 2], 3] * MIntVerKyb2[MBytPloskKyb[i, 3], 2]; MIntPloskostei[i, 2]:= MIntVerKyb2[MBytPloskKyb[i, 1], 1] * MIntVerKyb2[MBytPloskKyb[i, 3], 3] + MIntVerKyb2[MBytPloskKyb[i, 2], 3] * MIntVerKyb2[MBytPloskKyb[i, 3], 1] + MIntVerKyb2[MBytPloskKyb[i, 1], 3] * MIntVerKyb2[MBytPloskKyb[i, 2], 1] - MIntVerKyb2[MBytPloskKyb[i, 1], 3] * MIntVerKyb2[MBytPloskKyb[i, 3], 1] - MIntVerKyb2[MBytPloskKyb[i, 2], 1] * MIntVerKyb2[MBytPloskKyb[i, 3], 3] - MIntVerKyb2[MBytPloskKyb[i, 1], 1] * MIntVerKyb2[MBytPloskKyb[i, 2], 3]; MIntPloskostei[i, 3]:= MIntVerKyb2[MBytPloskKyb[i, 1], 1] * MIntVerKyb2[MBytPloskKyb[i, 2], 2] + MIntVerKyb2[MBytPloskKyb[i, 1], 2] * MIntVerKyb2[MBytPloskKyb[i, 3], 1] + MIntVerKyb2[MBytPloskKyb[i, 2], 1] * MIntVerKyb2[MBytPloskKyb[i, 3], 2] - MIntVerKyb2[MBytPloskKyb[i, 2], 2] * MIntVerKyb2[MBytPloskKyb[i, 3], 1] - MIntVerKyb2[MBytPloskKyb[i, 1], 2] * MIntVerKyb2[MBytPloskKyb[i, 2], 1] - MIntVerKyb2[MBytPloskKyb[i, 1], 1] * MIntVerKyb2[MBytPloskKyb[i, 3], 2]; MIntPloskostei[i, 4]:= -(MIntVerKyb2[MBytPloskKyb[i, 1], 1] * MIntVerKyb2[MBytPloskKyb[i, 2], 2] * MIntVerKyb2[MBytPloskKyb[i, 3], 3] + MIntVerKyb2[MBytPloskKyb[i, 1], 2] * MIntVerKyb2[MBytPloskKyb[i, 2], 3] * MIntVerKyb2[MBytPloskKyb[i, 3], 1] + MIntVerKyb2[MBytPloskKyb[i, 1], 3] * MIntVerKyb2[MBytPloskKyb[i, 2], 1] * MIntVerKyb2[MBytPloskKyb[i, 3], 2] - MIntVerKyb2[MBytPloskKyb[i, 1], 3] * MIntVerKyb2[MBytPloskKyb[i, 2], 2] * MIntVerKyb2[MBytPloskKyb[i, 3], 1] - MIntVerKyb2[MBytPloskKyb[i, 1], 2] * MIntVerKyb2[MBytPloskKyb[i, 2], 1] * MIntVerKyb2[MBytPloskKyb[i, 3], 3] - MIntVerKyb2[MBytPloskKyb[i, 1], 1] * MIntVerKyb2[MBytPloskKyb[i, 2], 3] * MIntVerKyb2[MBytPloskKyb[i, 3], 2]); end; //Проверяем знак уравнений плоскости беря произволную точку внутри куба //Вычисляем центр куба IntTcX:= MIntVerKyb2[1, 1]; IntTcY:= MIntVerKyb2[1, 2]; IntTcZ:= MIntVerKyb2[1, 3]; For i:= 2 to 8 do begin If IntTcX < MIntVerKyb2[i, 1] then IntTcX:= MIntVerKyb2[i, 1]; If IntTcY < MIntVerKyb2[i, 2] then IntTcY:= MIntVerKyb2[i, 2]; If IntTcZ < MIntVerKyb2[i, 3] then IntTcZ:= MIntVerKyb2[i, 3]; end; IntTcY:= IntTcY shr 1; //Находим скалярное произведение вектора на матрицу тела For i:= 1 to 6 do MIntScalProizVekNaMat[i]:= IntTcX * MIntPloskostei[i, 1] + IntTcY * MIntPloskostei[i, 2] + IntTcZ * MIntPloskostei[i, 3] + MIntPloskostei[i, 4]; //Определяем больше ли нуля полученный результат скалярного произведения и если больше то умножаем // уравнение матрицы на -1 For i:= 1 to 6 do begin If MIntScalProizVekNaMat[i] > 0 then For j:= 1 to 4 do MIntPloskostei[i, j]:= MIntPloskostei[i, j] * (-1); end; //Определяем точку с которой смотрим на куб IntTcX:= IntTcX * 2; IntTcY:= IntTcY * 4; IntTcZ:= IntTcZ * 2; //Перемножаем корректную матрицу тела с точкой наблюдения For i:= 1 to 6 do MIntScalProizVekNaMat[i]:= IntTcX * MIntPloskostei[i, 1] + IntTcY * MIntPloskostei[i, 2] + IntTcZ * MIntPloskostei[i, 3] + MIntPloskostei[i, 4]; //И сейчас в массиве MIntScalProizVekNaMat[i] должно быть 3 отрицательных числа, но их не 3...

и вот окончание всего кода

i:= 0; While i <= 4 do begin //Рисуем нижний квадрат куба i:= i + 1; //Ниже производится вычисление и перевод координат из трехмерного пространства в двумерное //Куб рисуется во фронтально диметрической проекуции // z // z // z // z // z // z // z // 0 x x x x x x x x x x x x x // y // y // y // y // y // y // y X:= Trunc(MIntVerKyb2[i, 1] + ((MIntVerKyb2[i, 2] / 2) * sin(0.785))); Y:= Trunc(((MIntVerKyb2[i, 2] / 2) * sin(0.785)) + MIntVerKyb2[i, 3]); MoveTo(X,Y); If i = 4 then begin i:= 0; BlnF:= true; end; i:= i + 1; X:= Trunc(MIntVerKyb2[i, 1] + ((MIntVerKyb2[i, 2] / 2) * sin(0.785))); Y:= Trunc(((MIntVerKyb2[i, 2] / 2) * sin(0.785)) + MIntVerKyb2[i, 3]); LineTo(X,Y); i:= i - 1; If BlnF = true then break; end; //Рисуем верхний квадрат куба BlnF:= false; i:= 4; While i <= 8 do begin i:= i + 1; X:= Trunc(MIntVerKyb2[i, 1] + ((MIntVerKyb2[i, 2] / 2) * sin(0.785))); Y:= Trunc(((MIntVerKyb2[i, 2] / 2) * sin(0.785)) + MIntVerKyb2[i, 3]); MoveTo(X,Y); If i = 8 then begin i:= 4; BlnF:= true; end; i:= i + 1; X:= Trunc(MIntVerKyb2[i, 1] + ((MIntVerKyb2[i, 2] / 2) * sin(0.785))); Y:= Trunc(((MIntVerKyb2[i, 2] / 2) * sin(0.785)) + MIntVerKyb2[i, 3]); LineTo(X,Y); i:= i - 1; If BlnF = true then break; end; //Рисуем Вертикальные линии соединяющие верхний и нижний квадрат i:= 0; While i <= 8 do begin i:= i + 1; X:= Trunc(MIntVerKyb2[i, 1] + ((MIntVerKyb2[i, 2] / 2) * sin(0.785))); Y:= Trunc(((MIntVerKyb2[i, 2] / 2) * sin(0.785)) + MIntVerKyb2[i, 3]); MoveTo(X,Y); i:= i + 4; X:= Trunc(MIntVerKyb2[i, 1] + ((MIntVerKyb2[i, 2] / 2) * sin(0.785))); Y:= Trunc(((MIntVerKyb2[i, 2] / 2) * sin(0.785)) + MIntVerKyb2[i, 3]); LineTo(X,Y); If i = 8 then break; i:= i - 4; end; end; ReaYgolKyb:= ReaYgolKyb + 0.07;//Счетчик угла поворота //С помощью мировой матрицы начинаем вращать куб вокруг оси х For i:= 1 to 8 do begin MIntVerKyb2[i, 2]:=300 + Trunc(((MIntVerKyb[i, 2] - 150) * cos(ReaYgolKyb)) - ((MIntVerKyb[i, 3] - 150) * sin(ReaYgolKyb))); MIntVerKyb2[i, 3]:=Trunc(((MIntVerKyb[i, 2] - 150) * sin(ReaYgolKyb)) + ((MIntVerKyb[i, 3] - 150) * cos(ReaYgolKyb))); end; end; ///////////////////////////Перерисовка каждые 35 милесекунд///////////////////// procedure TForm1.Timer1Timer(Sender: TObject); begin Repaint;//Перерисовываем форму end; end.

Есть отличный метод: отложить компьютер, взять ручку и бумажку и самому просчитать по своему алгоритму (только точно по нему!) все значения.
Сразу станет понятно, что не так.
Гарантирую. Проверено.

Я так понимаю просто никому неохото ковырятся в моем корявом коде вот и все. :(

> set © (02.10.10 19:55) [16]

дело не в корявости кода, а в его количестве. да и ошибка ищется отладчиком, а лучше, как в [15].
если обнаружится какая-нить, с твоей точки зрения, фантастика в куске строчек 15, кто-нить да поможет, при необходимости недостающие куски "клещами вытянут", хоть и поругавшись.

Алгоритм Робертса Найти похожие ветки