http___fmi.wikidot.com_okg6_1.xml
http___jccc-mpg.wikidot.com_parametric-equations_2.xml
1.1 2.1 3.1 3.2 3.3 3.4 3.5 3.6 4.1 5.1 5.2 5.3 6.1 6.2 6.3 7.1 8.1 8.2 8.3 8.4 8.5 9.1 10.1 10.2 10.3 10.4 10.5 11.1 12.1 12.2 13.1 13.2 13.3 13.4 13.5 14.1 15.1 15.2 16.1 17.1 18.1 19.1 19.2 19.3 20.1 20.2 20.3 20.4 21.1 21.2 21.3 22.1 23.1 23.2 23.3 24.1 24.2 25.1 26.1 27.1 28.1 28.2 28.3 29.1 30.1 30.2 30.3 31.1 31.2 32.1 32.2 33.1 34.1 34.2 35.1 36.1 37.1 38.1 39.1 39.2 39.3 39.4 39.5 40.1 40.2 40.3 41.1 42.1 42.2 43.1 43.2 44.1 44.2 44.3 44.4
Дискретно изчертаване на основни примитиви – отсечка, окръжност, елипса Растеризация Често се налага да се изчертават на екрана основни геометрични обекти като отсечки, части от окръжност/елипса. Както знаете обаче мониторът е правоъгълна таблица от пиксели, като всеки пиксел свети в определен цвят. Естествено възниква проблемът за изчертаване на отсечка/окръжност със зададени координати1 върху тази правоъгълна таблица. Т.е трябва да определим кои точно пиксели трябва да светят и евентуално колко силно. Проблемът не е сложен за решаване, но бързодействието е от изключително голяма важност. В тази глава ще разгледаме основните алгоритми за растеризация на отсечка, окръжност и елипса. Отсечка Най-често се налага изобразяването на отсечки върху растера2. Ще разгледаме алгоритъма на Брезенхам (на английски Bresenham). Като за начало да видим какво точно ще правим: Ако си представим отсечката като безкрайно тънка линия, която минава през 2 точки от екрана, то трябва да 'светнем' квадратчетата (пикселите), през които тази отсечка минава. За удобство ще приемем, че отсечката върви от югозапад (долу-ляво) до североизток (горе-дясно) и ъгълът, който тя сключва със $\overrightarrow{Ox}$, e по-малък от 45 градуса (т.е отсечката е по-"легнала"). Всички останали случаи са еквивалентни на този с подходяща ротация на координатната система. С тези ограничения задачата ни става наистина много лесна - ако си представим, че в момента сме в даден пиксел и се чудим в кой следващ пиксел да отидем имаме само 2 възможности - надясно или по диагонал нагоре и надясно: На всяка стъпка от алгоритъма, трябва да знаем текущото квадратче, което сме светнали както и грешката, която показва колко далеч е минала линията от квадратчето. За център на квадратчето ще приемем долния му ляв ъгъл. Ще разглеждаме също пресечните точки на линията (отсечката) с вертикалните линии на решетката. Спрямо тези точно пресечни точки (отбелязани с червено на фигурата) избираме най-близката точка от решетката по тази вертикална линия (т.е най близкия долен ляв ъгъл на квадрат със същия $x$) - на фигурата е отбелязано с лилаво мерниче. След като изберем долните леви ъгли просто светваме съответните им квадратчета (т.е квадратчето, което стои горе вдясно спрямо точката). бре Имаме дадени 2та края на отсечката - нека това са $(x_1, y_1), (x_2, y_2)$. Тогава $\Delta x = x2 - x1, \Delta y = y2 - y1$. Нека за улеснение приемем, че $\Delta x \ge \Delta y$, т.е линията има по-малък наклон от $\frac{\pi}{4}$. Ако си отбележим наклона с $\alpha$, то $\tg \alpha = \frac{\Delta y}{\Delta x} = m$. Това е първата много важна характеристика на линията (за единица дължина по $x$, колко пиксела нагоре (по $y$) се изкачва линията). Алгоритъм на Брезенхам: - Във всеки момент се знае кой е текущият пиксел, в който се намираме - $x_c, y_c$ както и стойността на текущата грешка - $e$, т.е колко далече минава истинската линия от квадратчето. Ще приемем, че координатите на квадратчето са координатите на долния му десен ъгъл и ще се интересуваме повече от самото ъгълче, отколкото от целия квадрат. - От всеки пиксел можем да се движим или надясно (т.е увеличаваме $x$) или по диагонал (т.е увеличаваме $x$ и $y$). Това зависи от грешката - тя се изчислява като към старата грешка прибавим $m$. Т.е $e_{new} = e_{old} + m$. Тъй като грешката е разстоянието от долния десен ъгъл на пиксела до пресечната точка на истинската отсечка с вертикалната права, минаваща над този долен десен ъгъл (на картинката отбелязано със синьо), то за да получим следващата грешка прибавяме точно разстоянието, което отсечката ще "изкачи" за един пиксел. Тъй като искаме точката (долния десен ъгъл) да бъде най-близо до пресечната точка на отсечката с вертикалната права, то ако грешката е повече от $\frac{1}{2}$, избираме горната точка, иначе - долната. Окръжност Сега ще разгледаме подробно алгоритъма за растеризиране на окръжност. За удобство ще приемем за изчертаваната окръжност: - центъра и е в $(0, 0)$ (в общия случай трябва да транслираме) - има целочислен радиус - изчертаваме само частта, която е разположена в първи квадрант (останалите са симетрични) Както при алгоритъма за отсечка, ще приемем, че пиксела се отъждествява с долния си ляв ъгъл. Също така по текущ пиксел в който се намираме $(x, y)$, ще видим как да стигнем до следващия. В случая на окръжност, ако изчертаваме само първи квадрант имаме следните 3 случая: надясно (по хоризонтала), надолу и надясно (по диагонал), на долу (по вертикала): Ще разгледаме случай 1 и 2, останалите два са им симетрични. Основното, което ще използваме, е разстояние от точка до окръжност, което се свежда до разстояние между 2 точки (самата точка и центъра на окръжността). Нека с функцията $k(x, y)$ означим това разстояние. Тогава:(1) Първо трябва да разберем дали сме в първите два случая (1 и 2) или във вторите два случая (3 и 4). За тази цел просто ще определим разположението на точката по диагонала (с координати $(x+1, y-1)$) спрямо окръжността - т.е дали тя е външна или вътрешна. Да положим на $\Delta$ разстоянието от диагоналната точка до центъра на окръжността:(2) Очевидно: Да разгледаме подробно случай 1 (окръжността минава между точките с координати $(x+1, y)$ и $(x+1, y-1)$ (т.е между дясната и диагоналната спрямо текущата). За да разберем коя от 2те точки трябва да светнем, трябва да проверим до коя точка модула от разстоянието до окръжността е минимално - т.е да изберем по-близката до окръжността точка. С други думи трябва да сравним:(3) Понеже сме в първи случай, знаем че точката $(x+1, y)$ е извън окръжността, а точката $(x+1, y-1)$ е в окръжността, следователно знаем знаците на изразите в модулите. Да махнем модула и да разпишем:(4) Сега да видим какво става според знака на $\delta$: С това случай 1 е завършен. Да разгледаме случай 2: По принцип може да направим абсолютно същите разсъждения като в предния случай - това обаче не е необходимо. В случай 2 и диагоналната и дясната точка са в окръжността и очевидно дясната е по-близо, т.е в този случай избираме дясната. Сега ще проверим следното: когато сме в случай 2, $\delta \le 0$, т.е стойността, която сметнахме за случай 1 ще важи и тук (т.е няма нужда даже да проверяваме дали сме в този случай - просто разписваме $\delta$ все едно сме в случай 1 и използваме резултата). Във втори случай сме когато дясната точка е в окръжността: Т.е получихме, че когато сме във 2ри случай, то сметнатото $\delta$ от първи случай е винаги отрицателно. Но това означава че ако просто бяхме забравили за 2ри случай и приемем че има само първи, ако получим $\delta < 0$ пак ще вземем хоризонталната дясна точка - т.е ще направим правилен избор. Ето защо 1ви и 2ри случай се изчерпват с разглеждането на таблицата, показана в 1ви случай. Както казахме 3ти и 4ти случай са напълно аналогични на разгледаните до сега. Ще запишем в таблица всички случай за улеснение: $\Delta'$ е просто новата стойност на $\Delta$. Така си спестявате малко умножения :) Елипса Остана да разлгедаме и алгоритъма на Бреззенхам за растеризация на елипса. Ще приемем че: - елипсата има център $(0, 0)$ и осите и са успоредни на координатните (т.е така би изглеждала след канонизация) - дължините на диаметрите й са реални числа - ще начертаем само частта и в първи квадрант Сега да погледнем какво трябва да се получи: Ще чертаем само в първи квадрант отдолу нагоре. При тези условия ако в даден момент се намираме в клетка $(x, y)$ имаме 3 възможни случая - нагоре, наляво и по диагонал (горе-ляво). В началото елипсата ще се движи по-скоро нагоре (т.е следващият пиксел ще е или над текущия или по диагонал), а след един точно определен момент (този, в който допирателната към елипсата сключва ъгъл 135 (= 180 - 45) градуса с $Ox$) - наляво. Преди и след този специален момент, алгоритъмът върви по подобен начин. Първо ще разгледаме ъгъл на допирателната по-малък от 135 градуса: Ако в момента се намираме в $(x, y)$, то следващата точка е или $(x, y+1)$ (нагоре) или $(x-1, y+1)$ (по диагонал). За да решим коя от 2те ще изберем, ще проверим положението на средната точка $(x - \frac{1}{2}, y+1)$ спрямо елипсата. Просто ще заместим в уравнението на елипсата:(7) След като тангенсът на допирателната стане по-малък от -1 (в началото е $-\infty$ при ъгъл $\frac{\pi}{2}$ (защото е вертикална), накрая е $0$ при ъгъл $\pi$ (защото е хоризонтална)), трябва да разгледаме новата средна точка $(x-1, y+\frac{1}{2})$: Единствено остава да изясним преминаването от случай 1 към случай 2. Производната спрямо $x$ на функцията $f(x, y)$ е точно:(9) Заместваме със $x, y$ и получаваме производната. После естествено я сравняваме с $-1$ Забележка: Как да получите формулата за производната? П просто разписвате спрямо $y$ или пък правите пълен диференциал на функцията. Как точно? Има статии по анализ :)
1.1 2.1 3.1 4.1 5.1 5.2 5.3 5.4 6.1 6.2 6.3 6.4 6.5 7.1 7.2 7.3 7.4 7.5 7.6 8.1 8.2 8.3 8.4 8.5 9.1 10.1 11.1 12.1 13.1 14.1 15.1 16.1 17.1 18.1 19.1 20.1 20.2 21.1 22.1 23.1 24.1 25.1 26.1 27.1 28.1 29.1 30.1 31.1 32.1 33.1 34.1 35.1 36.1 37.1 38.1 39.1 39.2 39.3 40.1 41.1 42.1 43.1 44.1 45.1 45.2 45.3 46.1 47.1 47.2 47.3 48.1 49.1 50.1 51.1 52.1 53.1 55.1 55.2 55.3 56.1 57.1 57.2 58.1 59.1 60.1 61.1 62.1 63.1 64.1 65.1 66.1 67.1 68.1 69.1 70.1 71.1 72.1 73.1
Definition of a Parametric Equation In the past, we have seen curves in two dimensions described as a statement of equality involving x and y.(1) These are sometimes referred to as rectangular equations or Cartesian equations. An alternative approach is two describe x and y separately in terms of a third parameter, usually t. These types of equations are called parametric equations. There are several advantages that parametric equations have over Cartesian equations. We can illustrate these advantages through the following example. Here is an example of a cartesian equation and a similar parametric equation,(3) First, let us look at the graphs of these two equations. Notice that in the parametric equation $x=t$. So if we substitute $x$ in for $t$ into the parametric equation for $y$, we get $y=x^2$. So it would seem logical that their graphs would have the same shape since the relationship between $x$ and $y$ is the same in both equations. Below we have graphs of the two equations. They both have the same shape, but they have different arrow indicators. On the Cartesian equation's graph, the arrows indicate that the graph is continuing on in the established fashion. On the parametric equation, the arrows indicate the direction an object would move along the path as the parameter increases. This leads to our first advantage of parametric equations and that is they not only can show the path of an object they can indicate where the object will be at any given time. This leads to the ability to calculate velocity and acceleration as well. The Cartesian equation's graph cannot do that. The second advantage to parametric equations comes from their utility in three dimensions. If we want to write the equation of a curve in three dimensions, the Cartesian approach fails completely. That is to say, you cannot write the equation of a curve in 3D using an equation of the form $f(x,y,z)=0$. In order to write the equation, we need to use a parametrization. This parametrization would be the same as in 2D, but with a parametric equation for $z$ added as follows. An example of such a curve would be the helix below, The equation for this helix looks like(5) Converting Between Cartesian and Parametric Converting from Cartesian to Parametric To convert a Cartesian equation to a parametric equation simply do the following. - Solve the equation for one variable, if possible - Let $t$ equal the other variable - Substitute t into your solved equation Example Convert 2x+3y=10 to a parametric form Converting from Parametric to Cartesian To convert a parametric equation to a Cartesian equation, there is no one procedure that will always work. If you can solve for $t$ in one of the equations, you can do the following, - Solve for t in one of the parametric equations, if possible. - Substitute the result into the other parametric equation. Example Convert $x=t^2+5t-1$ , $y=t+1$ to Cartesian form Parametric Equation of a Line, Ray and Segment Equation of a Line A parametric equation of the line passing through the point $(x_0,y_0,z_0)$ and parallel to the vector $\vec{v}= $ is given by(6) Example Find a parametrization for the line passing through the points $P(1,2,3)$ and $Q(0,5,3)$. Equation of a Ray A parametric equation of the ray starting at the point $(x_0,y_0,z_0)$ and in the direction of the vector $\vec{v}= $ is given by(7) Example Find a parametrization for the ray starting at the point $P(10,12,13)$ and headed in the direction of $\vec{v}= $. Equation of a Segment A parametric equation of the line segment from the point $(x_0,y_0,z_0)$ to the point $(x_1,y_1,z_1)$ is given by(8) Example Find a parametrization for the line segment from the point $P(-4,0,1)$ to the point $Q(3,-2,5)$ LERP In parametrizing a line segment you are creating a path between two points of constant velocity. This is referred to as a Linear Interpolation or LERP for short. If we conceptualize this as a path from one vector $\vec{p}_0= $ to another vector $\vec{p_1}= $, then we can rewrite our parametrization,(9) as a vector equation,(10) Which we can simplify to,(11) Parametric Equation of a Circle and an Ellipse Circle To create a parametrization of a circle centered at the origin with radius a, we will use the pathagorean identity that $\sin^2t+\cos^2t=1$. We know that in rectangular form the equation of a circle of radius a centered at the origin is $x^2+y^2=a^2$ or for our purposes $(\frac{x}{a})^2+(\frac{y}{a})^2=1$. So by equating these two equations we see that we can use,(12) or simplified(13) This particular parametrization will start at time $t=0$ and the point $(0,a)$. As $t$ starts to increase past zero, the values of both $x$ and $y$ will be positive, so we will be moving into the first quadrant. So our overall motion will be clockwise. We could similarly use the parametrization.(14) Now we will be at the point $(a,0)$ at time $t=0$, but we will still move into the first quadrant afterwards, so we will be moving counter-clockwise. Example Give a parametrization for the circle $x^2+y^2=9$ Ellipse Similarly, to create a parametrization of an ellipse centered at the origin with semi-major axis $a$ and semi-minor axis $b$, we will use the pathagorean identity that $\sin^2t+\cos^2t=1$. We know that in rectangular form the equation of an ellipse centered at the origin with semi-major axis $a$ and semi-minor axis $b$ has equation $(\frac{x}{a})^2+(\frac{y}{b})^2=1$. So by equating these two equations we see that we can use, or simplified(16) With this parametrization, we start at the point $(0,b)$ at time $t=0$ and as $t$ increases from zero, both $x$ and $y$ become positive moving us into the first quadrant. So our motion is clockwise. Example Give a parametrization for the ellipse $\frac{x^2}{49}+y^2=1$, with counter-clockwise motion that completes two revolutions Exercises - From an initial point $(6, 7, –9)$ and direction $ $ of a line, determine three other points on the line. - Write a parametric representation of the line determined by the points $(2, 5, 1)$ and $(7, 6, –3)$. - Write a parametrization for a line segment from $(1,6,2)$ to $(0,1,5)$ - Now parametrize the same path but with twice the speed. - Write a parametric representation of the ray originating at the point $(4, 6, –9)$ that has a compass heading 244º and pitch 35º. - Find the heading and elevation of the ray $[5+7t,2-6t,4t]$ , when $t>0$ . - Give a parametrization for a circle of radius $4$, with a counter-clockwise motion - Give a parametrization for the circle $x^2+y^2=16$ with a clockwise motion. - Give a parametrization for the ellipse $\frac{x^2}{4}+\frac{y^2}{25}=1$, with a counter-clockwise motion. - Convert the Cartesian equation $x-y^2=3$ to a parametric equation. - Convert the parametric equation $x=t+4$ , $y=t^3-t$ to a Cartesian equation. - Can there be more than one parametrization for a curve?, Explain why or why not. - What are the advantages of parametric equations over Cartesian equations?