Геометрические фигуры

Товарищщи программисты, прошу о помощи. Нужно написать программку, рисующие сабж (только контур, без текстурирования). Запоролся на такой вещи: не знаю, как нарисовать невидимые рёбра пунктиром. Скажем, опорные точки найти, соединить их, потом вращать всю эту конструкцию несложно, но с невидимыми рёбрами - беда. Есть ли какой-нибудь уникальный алгоритм?

Товарищь Progger, видимо речь идет о трехмерных фигурах и тебе нужно найти невидимые ребра. Это можно сделать достаточно простым способом для выпуклых тел.

• Для каждой грани находим нормальный вектор, у всех граней тела нормали разворачиваем во внутрь.
  
• У камеры, которой ты проецируешь на экран фигуру, задаешь направляющий вектор
  
• Если угол между направляющим вектором и нормалью тупой (>90°), то данная грань невидима
  
• Если ребро принадлежит двум невидимым граням, то ребро не видимо, рисуй его пунктиром.

Сообщение отредактировано: m - 19.02.03, 09:40

Meg, спасибо за ответ. Идею я понял, но с реализацией туго. Нормальный вектор, как я понимаю, тот, направление которого перпендикулярно грани, так? Если да, то как его найти и почему он будет тем самым, который направлен именно внутрь?

Нормаль плоскости --- это вектор направленный перпендикулярно плоскости и его длина равна единице.
Берем два вектора лежащих в плоскости и производим векторное умножение. Результат --- вектор перпендикулярный плоскости, приводим его к единице ---  получаем нормаль. Так как тебе важно  направление, то к единичной длине можно не приводить.

Вообще-то он не обязательно будет направлен внутрь. Это зависит от того что ты умножаешь, вернее в каком порядке. [a,b] = -[b,a]. Здесь a и b - вектора, [] - операция векторного произведения. Т.е. если поменять порядок множителей, то получим вектор, той же длины, но направленный в обратную строну.

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

2deesan Это верно про нормали
Но фокус в том, что если мы выбираем вектора на всех гранях однообразно, то все нормали получаются направленными во внутрь или наружу. Поскольку расчет нормалей делается, обычно, одной функцией, то направление нормалей получается автоматически.

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

Выбора векторов будет зависеть от организации массива (списка) вершин грани.

Часто нормали используются еще в других алгоритмах, по этому нормали выгодно рассчитать при создании тела и хранить вместе с телом.

Могу сбросить свой старый исходничек на С++. Там параллелепипед с невидимыми ребрами и отсечение отрезка алгоритмом Кируса-Бека.

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

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

Согласен, но тогда и поиск невидимых ребер будет сложнее, потому как часть грани  и ребра может быть видимой, а часть не видимой

Народ, спаибо за помощь, но мне не хватает чисто геометрических знаний. Вот возьмём уравнение плоскости: Ax + By + Cz + D = 0 Имея 3 точки (x1,y1,z1), (x2,y2,z2), (x3,y3,z3)
построим уравнение:
A = y1 (z2 - z3) + y2 (z3 - z1) + y3 (z1 - z2)
B = z1 (x2 - x3) + z2 (x3 - x1) + z3 (x1 - x2)
C = x1 (y2 - y3) + x2 (y3 - y1) + x3 (y1 - y2)
- D = x1 (y2 z3 - y3 z2) + x2 (y3 z1 - y1 z3) + x3 (y1 z2 - y2 z1)
Так? Дальше, у нас есть точка, задающая центр фигуры, с координатами x4,y4,z4. Так вот, имея всё это, нужно построить "правильную нормаль", ну, или вектор, направленный внутрь. Как это сделать? Покажите наглядно.

Следующее. Напрвляющий вектор, если плоскость монитора - плоскость xy, будет {0,0,10} или {0,0,100} - это уже не так важно, верно? И последнее: угол между векторами по формуле cos(angle)=(x1*x2+y1*y2+z1*z2)/(sqrt(x1*x1+y1*y1+z1*z1)*sqrt(x2*x2+y2*y2+z2*z2))

Если что не так, поправьте.

Я считал нормаль так:

 
type tPoint3d=record x,y,z:single end;
procedure Normalize(var a1,a2,a3:single);
 var l:single;
 begin
 l:=sqrt(sqr(a1)+sqr(a2)+sqr(a3));
 a1:=a1/l;
 a2:=a2/l;
 a3:=a3/l;
 end;
procedure diff3(const a,b:tPoint3d;out c:tPoint3d);
 begin
 c.x:=a.x-b.x;
 c.y:=a.y-b.y;
 c.z:=a.z-b.z;
 end;
procedure crossprod(const v1,v2:tPoint3d;out prod:tPoint3d);
 begin
 prod.x:=v1.y*v2.z-v2.y*v1.z;
 prod.y:=v1.z*v2.x-v2.z*v1.x;
 prod.z:=v1.x*v2.y-v2.x*v1.y;
 end;
 
procedure CalculateNormal(const p1,p2,p3:tPoint3d;out n:tPoint3d);
 var d1,d2:tPoint3d;
 begin
 diff3(p2,p1,d1);
 diff3(p2,p3,d2);
 crossprod(d1,d2,n);
 normalize(n.x,n.y,n.z);
 end;

Но тут направление зависит от порядка умножения векторов.

Если Ax+By+Cz+D=0 - уравнение плоскости, то вектор (A, B, C) - есть вектор нормали к этой плоскости.

Формула для косинуса верна, но поскольку нас в данный момент интересует только то, больше угол 90 или меньше, то достаточно рассчитать скалярное произведение векторов
по формуле x1*x2+y1*y2+z1*z2 и посмотреть знак, если больше нуля, то угол между векторами острый, если меньше - тупой. Это становится очевидно если взглянуть на другую формулу для скалярного произведения: (v1, v2) = |a|*|b|*cos(alpha) здесь |a| и |b| - всегда неотрицательны, следовательно знак будет определяться величиной косинуса, который меньше нуля только в случае тупых углов.

Сообщение отредактировано: deesan - 25.02.03, 04:35