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

Вопрос: 1) Где найти архивы конференции comp.graphics.algorithms ? | Официально : | | http://www.cis.ohio-state/hypertext/faq/usenet/graphics/algorithms-faq/faq.html | ftp://rtfm.mit.edu/pub/usenet-by-group/news.answers/graphics/algorithms-faq | | Также : | | ftp://wuarchive.wustl.edu/graphics/graphics/mail-lists/comp.graphics.algorithms | http://www.cis.ohio-state/hypertext/faq/usenet/top.html ---------------------------------------------------------------------- Вопрос : 2) Какие книги можно почитать по графическим алгоритмам ? Основы компьютерной графики ---------------------------------------------- [Foley] Computer Graphics: Principles and Practice (2nd Ed.), J.D. Foley, A. van Dam, S.K. Feiner, J.F. Hughes, Addison-Wesley 1990, ISBN 0-201-12110-7 [Rogers:Procedural] Procedural Elements for Computer Graphics, David F. Rogers, McGraw Hill 1985, ISBN 0-07-053534-5 [Rogers:Mathematical] Mathematical Elements for Computer Graphics 2nd Ed., David F. Rogers and J. Alan Adams, McGraw Hill 1990, ISBN 0-07-053530-2 [Watt:3D] _3D Computer Graphics, 2nd Edition_, Alan Watt, Addison-Wesley 1993, ISBN 0-201-63186-5 [Glassner:RayTracing] An Introduction to Ray Tracing, Andrew Glassner (ed.), Academic Press 1989, ISBN 0-12-286160-4 [Gems I] Graphics Gems, Andrew Glassner (ed.), Academic Press 1990, ISBN 0-12-286165-5 [Watt:Animation] Advanced Animation and Rendering Techniques, Alan Watt, Mark Watt, Addison-Wesley 1992, ISBN 0-201-54412-1 [Bartels] An Introduction to Splines for Use in Computer Graphics and Geometric Modeling, Richard H. Bartels, John C. Beatty, Brian A. Barsky, 1987, ISBN 0-934613-27-3 [Farin] Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide, 3rd Edition, Gerald E. Farin, Academic Press 1993. ISBN 0-12-249052-5 [Prusinkiewicz] The Algorithmic Beauty of Plants, Przemyslaw W. Prusinkiewicz, Aristid Lindenmayer, Springer-Verlag, 1990, ISBN 0-387-97297-8, ISBN 3-540-97297-8 [Oliver] Tricks of the Graphics Gurus, Dick Oliver, et al. (2) 3.5 PC disks included, $39.95 SAMS Publishing [Hearn] Introduction to computer graphics, Hearn & Baker Геометрия ---------------------- [Bowyer] A Programmer's Geometry, Adrian Bowyer, John Woodwark, Butterworths 1983, ISBN 0-408-01242-0 Pbk [O' Rourke] Computational Geometry in C, Joseph O'Rourke, Cambridge University Press 1994, ISBN 0-521-44592-2 Pbk, ISBN 0-521-44034-3 Hdbk [Mortenson] Geometric Modeling, Michael E. Mortenson, Wiley 1985, ISBN 0-471-88279-8 [Preparata] Computational Geometry: An Introduction, Franco P. Preparata, Michael Ian Shamos, Springer-Verlag 1985, ISBN 0-387-96131-3 ---------------------------------------------------------------------- Вопрос: 3) Что еще можно найти ? ftp://siggraph.org/publications/bibliography directory. Смотрите файл READ_ME . Исходники на C : ftp://usc.edu/pub/C-numanal. В частности , numcomp-free-c.gz . ---------------------------------------------------------------------- Subject: 4) Еще бы исходников ? Graphics Gems source code. ftp://princeton.edu:pub/Graphics/GraphicsGems General 'stuff' ftp://wuarchive.wustl.edu/graphics/graphics ---------------------------------------------------------------------- Subject: 5) Как вращать 2D point? В 2-D, матрица 2x2 проста . M = {cos t, -sin t} {sin t, cos t } Если мы хотим вращать вектор ( то бишь точку ) и если вектор представлен в виде матрицы из одного столбика , то смело перемножайте вектор на матрицу . ---------------------------------------------------------------------- Вопрос : 7) Как найти расстояние от точки до линии ? Пусть точка C имеет координаты (XC,YC) и отрезок от AB (XA,YA) до (XB,YB). Длина отрезка AB : L=((XB-XA)**2+(YB-YA)**2)**0.5 и (YA-YC)(YA-YB)-(XA-XC)(XB-XA) r = ----------------------------- L**2 (YA-YC)(XB-XA)-(XA-XC)(YB-YA) s = ----------------------------- L**2 Пусть точка I - точка перпендикулярной проекции C на AB . XI=XA+r(XB-XA) YI=YA+r(YB-YA) Расстояние от A до I = r*L Расстояние от C до I = s*L Если r<0 I сзади AB If r>1 I спереди AB If 0<=r<=1 I лежит на AB Если s<0 C слева от AB Если s>0 C справа от AB Если s=0 C на AB ---------------------------------------------------------------------- Subject: 8) Как найти пересечение 2-х 2D линейных сегментов ? Пусть A,B,C,D - 2 вектора . Тогда : AB=A+r(B-A), r : [0,1] CD=C+s(D-C), s : [0,1] Если AB & CD пересекаются , то A+r(B-A)=C+s(D-C), или XA+r(XB-XA)=XC+s(XD-XC) YA+r(YB-YA)=YC+s(YD-YC) r,s : [0,1] Формулы для r и s : (YA-YC)(XD-XC)-(XA-XC)(YD-YC) r = ----------------------------- (eqn 1) (XB-XA)(YD-YC)-(YB-YA)(XD-XC) (YA-YC)(XB-XA)-(XA-XC)(YB-YA) s = ----------------------------- (eqn 2) (XB-XA)(YD-YC)-(YB-YA)(XD-XC) Пусть I - точка пересечения , тогда I=A+r(B-A) или XI=XA+r(XB-XA) YI=YA+r(YB-YA) Некоторые ограничения : Если 0<=r<=1 & 0<=s<=1, пересечение имеет место быть r<0 или r>1 или s<0 или s>1 , то увы , не пересекаются . Если знаменатель в (eqn 1) = 0 , AB & CD параллельны . Если числитель в (eqn 1) = 0 , AB & CD просто совпадают . ---------------------------------------------------------------------- Вопрос : 9) Как найти пересечение линии и плоскости ? Если плоскость определена как : a*x + b*y + c*z + d = 0 и линия определена как : x = x1 + (x2 - x1)*t = x1 + i*t y = y1 + (y2 - y1)*t = y1 + j*t z = z1 + (z2 - z1)*t = z1 + k*t Подставляем их в уравнение плоскости : t = - (a*x1 + b*y1 + c*z1 + d)/(a*i + b*j + c*k) Если знаменатель = 0 , то вектор (a,b,c) и вектор (i,j,k) перпендикулярны . Вектор (a,b,c) - нормаль к плоскости и (i,j,k) - направление . Это означает , что линия либо параллельна плоскости , либо принадлежит ей . ---------------------------------------------------------------------- Вопрос: 10) Как вращать bitmap? Рассмотрим матрицу вращения : R(T) = { cos(T), -sin(T) } { sin(T), cos(T) } Она может быть сформирована так : R(T) = M1(T) * M2(T) * M3(T) где : M1(T) = { { 1, -tan(T/2) }, { 0, 1 } } M2(T) = { { 1, 0 }, { sin(T), 1 } } M3(T) = { { 1, -tan(T/2) }, { 0, 1 } } Каждое из этих преобразований может быть выполнено последовательно - отдельно . ---------------------------------------------------------------------- Вопрос : 17) Как определить , находится ли точка внутри полигона ? Ответ может быть таков : int pnpoly(int npol, float *xp, float *yp, float x, float y) { int i, j, c = 0; for (i = 0, j = npol-1; i < npol; j = i++) { if ((((yp[i]<=y) && (y<yp[j])) || ((yp[j]<=y) && (y<yp[i]))) && (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i])) c = !c; } return c; } ---------------------------------------------------------------------- Вопрос : 20) Как сгенерировать круг по 3 точкам ? Пусть даны 3 точки a, b, c. Используем _0 и _1 для x и y координат . Координаты центра p=(p_0,p_1) определяются так : p_0 = ( b_1 a_0^2 - c_1 a_0^2 - b_1^2 a_1 + c_1^2 a_1 + b_0^2 c_1 + a_1^2 b_1 + c_0^2 a_1 - c_1^2 b_1 - c_0^2 b_1 - b_0^2 a_1 + b_1^2 c_1 - a_1^2 c_1 ) / D p_1 = ( a_0^2 c_0 + a_1^2 c_0 + b_0^2 a_0 - b_0^2 c_0 + b_1^2 a_0 - b_1^2 c_0 - a_0^2 b_0 - a_1^2 b_0 - c_0^2 a_0 + c_0^2 b_0 - c_1^2 a_0 + c_1^2 b_0) / D где D = 2( a_1 c_0 + b_1 a_0 - b_1 c_0 -a_1 b_0 -c_1 a_0 + c_1 b_0 ) Радиус : r^2 = (a_0 - p_0)^2 + (a_1 - p_1)^2 ---------------------------------------------------------------------- Вопрос : 35) Как найти пересечение луча и сферы ? Луч определен как : x = x1 + (x2 - x1)*t = x1 + i*t y = y1 + (y2 - y1)*t = y1 + j*t z = z1 + (z2 - z1)*t = z1 + k*t Сфера определена как : (x - l)**2 + (y - m)**2 + (z - n)**2 = r**2 Подставляя первое во второе , получим : a*t**2 + b*t + c = 0 где : a = i**2 + j**2 + k**2 b = 2*i*(x1 - l) + 2*j*(y1 - m) + 2*k*(x1 - n) c = l**2 + m**2 + n**2 + x1**2 + y1**2 + z1**2 - 2*(l*x1 + m*y1 + n*z1) - r**2 Если детерминант от квадратичного уравнения (t) меньше нуля , пересечения нет . Если равен нулю , то линия касается сферы в одной точке . Если больше нуля , то пересекает в 2-х точках . ---------------------------------------------------------------------- Вопрос : 43) Как определить видимость полигона в 3d ? Нужно перебрать вершины полигона по часовой стрелке : c = (x3*((z1*y2)-(y1*z2))+ (y3*((x1*z2)-(z1*x2))+ (z3*((y1*x2)-(x1*y2))+ x1,y1,z1, x2,y2,z2, x3,y3,z3 = первые три вершины полигона . Если c > 0 , то полигон видим . Если c < 0 , полигон невидим . ---------------------------------------------------------------------- Вопрос : 44) То же самое , но в 2d ? c = (x1-x2)*(y3-y2)-(y1-y2)*(x3-x2)

Смотрите также: