http___fmi.wikidot.com_okg6_1.xml
http___jccc-mpg.wikidot.com_basic-coordinate-geometry.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 1.2 1.3 2.1 3.1 3.2 3.3 3.4 4.1 4.2 4.3 4.4 5.1 5.2 6.1 7.1 8.1 9.1 10.1 11.1 12.1 13.1 14.1 15.1 16.1 17.1 18.1 18.2 18.3 19.1 20.1 21.1 21.2 21.3 21.4 21.5 21.6 22.1 23.1 23.2 23.3 24.1 25.1 25.2 25.3 25.4 26.1 27.1 27.2 28.1 29.1 30.1 31.1 32.1 33.1 34.1 35.1 35.2 35.3 35.4 36.1 36.2 37.1 38.1 38.2 38.3 39.1 40.1 41.1 42.1 43.1 44.1 45.1 46.1 47.1 48.1 49.1 49.2 50.1 51.1 52.1 53.1 54.1 54.2 54.3 55.1 55.2 55.3 56.1 57.1 58.1 59.1 60.1 60.2 61.1 62.1 63.1 64.1 65.1 66.1 67.1 68.1 69.1 70.1 71.1 71.2 71.3 71.4 71.5 71.6 72.1 73.1 74.1 75.1 75.2 76.1 77.1 78.1 79.1 80.1 81.1 82.1 83.1 84.1 85.1 86.1 87.1 88.1 89.1 90.1 90.2
Our goal in this course is to understand the physics and therefore the mathematics that is involved in describing the motion of objects so that we can use them to model the motion of objects in the game world. Motion is a result of changing the position of an object over time, so let us first start with how we will describe the position of objects. First in 2-Dimensions and then in 3-Dimensions. Points and Coordinate Systems in 2D In mathematics, there are several coordinate systems available to describe the location of a point in 2 or 3 dimensions. For our purposes, the rectangular or Cartesian coordinate system will be the most appropriate. In 2 dimensions, we most often use the x coordinate for the horizontal component of the location and y for the vertical component of the location. The image below shows a standard 2-dimensional Cartesian coordinate system. In the plane, the x-axis runs left to right with larger values to the right while the y-axis runs up and down with larger values above. Each point in the plane can be referred to by its x and y coordinate pair $(x,y)$. This is called the ordered pair. The point with ordered pair $(0,0)$ is called the origin. It is worth mentioning that the coordinates on the computer screen have the positive y-direction pointing down and the origin in the upper left-hand corner. One can work in the standard coordinate system and simplify convert to screen coordinates before outputting. Distance in 2 Dimensions Given two points in 2 dimensions, the distance between them is defined as follows(1) This formula can be easily derived from the theorem of Pythagoras. First, notice that the distance between the two points is just the length of the hypotenuse of a right triangle. Side a has a length of $x_2-x_1$ Side b has a length of $y_2-y_1$ So from Pythagoras we have that $d=\sqrt{a^2+b^2}=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$ Midpoint in 2 Dimensions Given two points in 2 dimensions, the midpoint is defined as follows(2) Notice that the x coordinate of the midpoint is the average of the two x coordinates and likewise with the y coordinate Lines in 2 Dimensions Slope One key feature of a line is the degree to which it inclines or declines. This feature is called it's slope. We define the slope of a line that passes through the points $(x_1,y_1)$ and $(x_2,y_2)$ as(3) Exercise Find the slope of the line that passes through the points (2,4) and (6,-1). The slope of a line is an indicator of how quickly the line rises or falls. For a line that rises from left to right the slope is positive. For a line that falls the slope is negative. For a vertical line the slope is undefined. For a horizontal line the slope is zero. The image below illustrates this fact. Parallel Lines Two lines that are parallel rise or fall at the same rate therefore their slopes are equal, assuming they exist. In other words, if $m_1=m_2$, then the two lines are parallel. If both slopes are undefined, then both lines are vertical and are therefore parallel. Perpendicular Lines In the case of perpendicular lines, as one line rises the other falls and the faster one rises the slower the other falls. Specifically, the slopes are related as opposite reciprocals, assuming they exist. That is to say, $m_1=-\frac{1}{m_2}$. For the case of a vertical and a horizontal line, one line has a slope of 0, while the other line has undefined slope. Point Slope Form We can now use our definition of slope to create an equation of a line. Given a line with slope m that passes through the point $(x_1,y_1)$, every point $(x,y)$ on that line satisfies the equation(4) Multiplying this equation on both sides by $x-x_1$ yeilds the following(5) This is the so called point slope form of the equation of a line. Exercise Find the point slope equation of the line that has slope $m=\frac{1}{2}$ and passes through the point $(2,-3)$. Example Find the point slope equation on the line that passes through the points $(-1,3)$ and $(2,-6)$. Slope Intercept Form Now say we have a line with slope m and passing through the point $(0,b)$. This point lies on the y-axis since its x coordinate is zero. We call this point the y-intercept of the line. If we plug this information into the point-slope equation we get(6) This equation is the so called slope intercept form of the equation of a line. It is a specific case of the point slope form. Standard Form The one limitation of both of these forms is that they require the slope, but as we saw previously vertical lines have an undefined slope. In fact, vertical lines consist of all points with a common x value therefore they have an equation of the form $x=a$. This is a special case of the more general standard form of the equation of a line which is given by(7) The equation of any line can be expressed in this form. Example Find the equation in standard form for the line with slope-interpect form of $y=3x+4$ Example Find the equation in standard form for the line with point-slope form of $y-2=4(x+5)$ Example Find the equation in standard form for the vertical line $x-4=8$ Circles Standard Form A circle can be defined as the set of points that are all a fixed distance r, radius, from a common center, $(x_0,y_0)$. We already know that in 2D distance is defined as $d=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$. Since a cirlce is the set of points whose distance is r from the point $(x_0,y_0)$, the distance formula yields the formula(8) This is the so called standard form of the equation of a circle in 2D. Exercise Find the center and radius of the circle $x^2-4x+y^2+10y=7$ Points and Coordinate Systems in 3D In 3 dimensions, the Cartesian coordinate system has three perpendicular axes. The original x and y axes from the xy-plane plus the z-axis that runs perpendicular to the xy-plane. In the right-handed coordinate system the positive z-axis is pointing out of the screen and in the left-handed coordinate system the positive z-axis is pointing into the screen. To determine handedness you lay your hand flat on the x-axis with your fingers pointing in the positive x direction. Now curve your fingers in the direction of the positive y-axis. The direction your thumb is pointing will be the positive z direction. In mathematics, it is somewhat standard to use a right-handed system with the positive z direction being up and the positive x direction being out. Every point in 3 dimensional space can be uniquely defined by its ordered triple $(x,y,z)$. Distance in 3 Dimensions Our formula from 2 Dimensions can be extended the 3 dimensions by twice applying the theorem of Pythagoras.(9) Notice that the z component is the same for the endpoints of side a. Therefore our 2-dimensional distance formula applies and(10) Since only the z coordinate is different on the endpoints of side b, we know that(11) Now applying the theorem of Pythagoras we get(12) Exercise Find the distance between (1,3,-1) to (4,5,6) Midpoint in 3 Dimensions Given two points in 3 dimensions the midpoint is defined as follows(13) Again each coordinate is the average of the corresponding original two coordinates. Exercise Find the midpoint of the points (8,20,6) and (9,10,1) Planes in 3 Dimensions The analog to a line in 3D is a plane. So, whereas the line has the general form, $Ax+By=C$, the plane has the general form, $Ax+By+Cz=D$. So for example, the equation $x+2y+3z=6$ will be represented graphically as a plane. Sketching curves and surfaces in 3D by hand requires some practice and a little artistic effort. For general surfaces, there are various slicing techniques that can help you build up the 3D picture. Due to the simple geometry of planes, the easiest approach is to compute the intercepts with the three major axes and then sketch the portion of the plane that lies in-between. Example Sketch $x+2y+3z=6$ Spheres The 3D analog of a circle is a sphere. By definition it is the set of all points $(x,y)$ a fixed distance $r$, called the radius, from a center $(x_0,y_0,z_0$ Using the definition of distance in 3D we get the standard form of the equation of a sphere;(14) Example Give the equation of the sphere with center $(2,0,-5)$ and radius 3. Example Find the center and radius of $x^2+y^2+z^2+4x-8y+12z=0$ Exercises - Draw a left-handed 3D coordinate system with the positive x-axis pointing to the left. - Draw a right-handed 3D coordinate system with the positive x-axis pointing out. - Find the distance and midpoint between the points (4, 11, –5) and (–3, 7, 2). - Find the distance and midpoint between the points (-2, 1) and (6, -20). - Write the equation of a line passing through the points (6, 3) and (2, –5). - Write the equation of a line passing through the point (4, –7) that is perpendicular to the line with equation $5x-3y=9$. - On a right-handed coordinate system with the z-axis pointing down, sketch a graph of the plane with equation $2x+3y-z=4$. - Write the equation of a circle with center (3, 8) and radius 7. - Write the equation of a sphere where (5, 7, 3) and (–1, 5, 4) are endpoints of a diameter. - A sphere has the equation $x^2+y^2+z^2-6y+5z=14$ . Find its center and radius.