diff options
| -rw-r--r-- | 2d/_collisions/polygon_polygon.html | 62 | ||||
| -rw-r--r-- | 2d/_collisions/polygon_polygon.html.content | 62 | ||||
| -rw-r--r-- | 2d/_collisions/polygon_polygon/images/1.png | bin | 0 -> 8299 bytes | |||
| -rw-r--r-- | 2d/_collisions/polygon_polygon/images/2.png | bin | 0 -> 7962 bytes | |||
| -rw-r--r-- | 2d/_collisions/polygon_polygon/images/2a.png | bin | 0 -> 8434 bytes | |||
| -rw-r--r-- | 2d/_collisions/polygon_polygon/images/2b.png | bin | 0 -> 8006 bytes | |||
| -rw-r--r-- | 2d/_collisions/polygon_polygon/images/2c.png | bin | 0 -> 8022 bytes | |||
| -rw-r--r-- | 2d/_collisions/polygon_polygon/images/2d.png | bin | 0 -> 10826 bytes | |||
| -rw-r--r-- | 2d/_collisions/polygon_polygon/images/2e.png | bin | 0 -> 11330 bytes | |||
| -rw-r--r-- | 2d/_collisions/polygon_polygon/images/2f.png | bin | 0 -> 9354 bytes | |||
| -rw-r--r-- | 2d/_collisions/polygon_polygon/images/3.png | bin | 0 -> 8105 bytes | |||
| -rw-r--r-- | 2d/rigidbody/rigidbody_3.html | 12 | ||||
| -rw-r--r-- | 2d/rigidbody/rigidbody_3.html.content | 12 | ||||
| -rw-r--r-- | index.css | 9 | ||||
| -rw-r--r-- | roadmap.html | 8 | ||||
| -rw-r--r-- | roadmap.html.content | 8 |
16 files changed, 161 insertions, 12 deletions
diff --git a/2d/_collisions/polygon_polygon.html b/2d/_collisions/polygon_polygon.html index e8fe7ea..c1c3a2e 100644 --- a/2d/_collisions/polygon_polygon.html +++ b/2d/_collisions/polygon_polygon.html @@ -76,25 +76,79 @@ <section> <h2>Explanation of Separating Axis Theorem</h2> <p> - SAT makes use of vector projection to figure out whether or not two concave polygons are intersecting. The way to think about it is this: + SAT makes use of vector projection to figure out whether or not two concave polygons are intersecting. I believe the best way to describe it is to show you the instance where two polygons do <b>not</b> intersect. <br/> <br/> - Given two shapes <b>A</b> and <b>B</b>. + Images two shapes <b>A</b> and <b>B</b> as shown below (they are triangles here, but they can be anything really). + <br/> + + <div class='image'> + <img src="polygon_polygon/images/1.png" /> + </div> + + <br/> + We know inutitively that if we were able to draw a line between the two objects, that means that they're not intersecting. In this case, that line is a vertical-ish line: + <br/> + + <div class='image'> + <img src='polygon_polygon/images/2.png' /> + </div> - Imagine we could isolate a single edge of A and shine a light on it. + <br/> + That line could be any of the infinite number of lines between the objects, so we can't really select that <i>exact</i> line. So the problem becomes: how do we <i>infer</i> that the vertical line shown in the previous diagram is a line that splits the objects? That is where the Separating Axis Theorem comes in. + + <br /> + <br/> + To do separating axis theorem, we iterate all of the edges of <b>both</b> shapes. For each edge, we get the normal at that edge (In two-dimensions, this amounts to getting the perpendicular of the line segment defined by the two points of the edge). + <br /> + + <div class='image'> + <img src='polygon_polygon/images/2a.png' /> + </div> + + <br /> + + We then, in our heads, extend this normal to create an axis across our scene (keep in mind that you won't have to do any "extending" of this axis in code; the normal will do just fine). + + <div class='image'> + <img src='polygon_polygon/images/2d.png' /> + </div> + + <br /> + + At this point, you will see that I named the three vertices on each of the triangles. Triangle <b>A</b> is made of vertices <i>a1, a2, a3</i> and triangle <b>B</b> is made of vertices <i>b1, b2, b3</i>. At this point, we project the shape onto the axis. To do this, we project the vertices of each shape onto the axis to figure out which one <i>maximizes</i> the dot product and which one <i>minimizes</i> the dot product. The projection of the shape is then the range defined by this min and max value. + + <br /> + + <div class='image'> + <img src='polygon_polygon/images/2e.png' /> + </div> + + <br /> + + Finally, we check if the two ranges overlap. If they don't overlap, then the shapes do <b>not</b> intersect. If they do overlap, we repeat the process for all of the other edges. If all of these ranges overlap, then the shape overlaps, and there is no separating line between them. + + <br /> + + <div class='image'> + <img src='polygon_polygon/images/2f.png' /> + </div> + + <br /> </p> </section> <section> <h2>Algorithm for Finding the Intersection</h2> <p> + Given two polygons <b>A</b> and <b>B</b>: <ol> <li>For each edge on <b>A</b>, get the normal <i>n</i> of that edge.</li> - <li>Project each vertex <i>v</i> of <b>A</b> onto <i>n</i>. Return the minimum and maximum projection of all vertices.</li> + <li>Project each vertex <i>v</i> of <b>A</b> onto <i>n</i>. Return the minimum and maximum projection of all vertices as the projection of the shape.</li> <li>Repeat Step 2 for polygon <b>B</b>.</li> <li>If the min and max projections found in Steps 2 and 3 do <b>NOT</b> overlap, the polygons are not intersecting. Return false.</li> <li>If the projections overlap for each edge of both shapes, the shapes are intersecting. Return true.</li> diff --git a/2d/_collisions/polygon_polygon.html.content b/2d/_collisions/polygon_polygon.html.content index ffa9b15..a0da872 100644 --- a/2d/_collisions/polygon_polygon.html.content +++ b/2d/_collisions/polygon_polygon.html.content @@ -24,25 +24,79 @@ <section> <h2>Explanation of Separating Axis Theorem</h2> <p> - SAT makes use of vector projection to figure out whether or not two concave polygons are intersecting. The way to think about it is this: + SAT makes use of vector projection to figure out whether or not two concave polygons are intersecting. I believe the best way to describe it is to show you the instance where two polygons do <b>not</b> intersect. <br/> <br/> - Given two shapes <b>A</b> and <b>B</b>. + Images two shapes <b>A</b> and <b>B</b> as shown below (they are triangles here, but they can be anything really). + <br/> + + <div class='image'> + <img src="polygon_polygon/images/1.png" /> + </div> + + <br/> + We know inutitively that if we were able to draw a line between the two objects, that means that they're not intersecting. In this case, that line is a vertical-ish line: + <br/> + + <div class='image'> + <img src='polygon_polygon/images/2.png' /> + </div> - Imagine we could isolate a single edge of A and shine a light on it. + <br/> + That line could be any of the infinite number of lines between the objects, so we can't really select that <i>exact</i> line. So the problem becomes: how do we <i>infer</i> that the vertical line shown in the previous diagram is a line that splits the objects? That is where the Separating Axis Theorem comes in. + + <br /> + <br/> + To do separating axis theorem, we iterate all of the edges of <b>both</b> shapes. For each edge, we get the normal at that edge (In two-dimensions, this amounts to getting the perpendicular of the line segment defined by the two points of the edge). + <br /> + + <div class='image'> + <img src='polygon_polygon/images/2a.png' /> + </div> + + <br /> + + We then, in our heads, extend this normal to create an axis across our scene (keep in mind that you won't have to do any "extending" of this axis in code; the normal will do just fine). + + <div class='image'> + <img src='polygon_polygon/images/2d.png' /> + </div> + + <br /> + + At this point, you will see that I named the three vertices on each of the triangles. Triangle <b>A</b> is made of vertices <i>a1, a2, a3</i> and triangle <b>B</b> is made of vertices <i>b1, b2, b3</i>. At this point, we project the shape onto the axis. To do this, we project the vertices of each shape onto the axis to figure out which one <i>maximizes</i> the dot product and which one <i>minimizes</i> the dot product. The projection of the shape is then the range defined by this min and max value. + + <br /> + + <div class='image'> + <img src='polygon_polygon/images/2e.png' /> + </div> + + <br /> + + Finally, we check if the two ranges overlap. If they don't overlap, then the shapes do <b>not</b> intersect. If they do overlap, we repeat the process for all of the other edges. If all of these ranges overlap, then the shape overlaps, and there is no separating line between them. + + <br /> + + <div class='image'> + <img src='polygon_polygon/images/2f.png' /> + </div> + + <br /> </p> </section> <section> <h2>Algorithm for Finding the Intersection</h2> <p> + Given two polygons <b>A</b> and <b>B</b>: <ol> <li>For each edge on <b>A</b>, get the normal <i>n</i> of that edge.</li> - <li>Project each vertex <i>v</i> of <b>A</b> onto <i>n</i>. Return the minimum and maximum projection of all vertices.</li> + <li>Project each vertex <i>v</i> of <b>A</b> onto <i>n</i>. Return the minimum and maximum projection of all vertices as the projection of the shape.</li> <li>Repeat Step 2 for polygon <b>B</b>.</li> <li>If the min and max projections found in Steps 2 and 3 do <b>NOT</b> overlap, the polygons are not intersecting. Return false.</li> <li>If the projections overlap for each edge of both shapes, the shapes are intersecting. Return true.</li> diff --git a/2d/_collisions/polygon_polygon/images/1.png b/2d/_collisions/polygon_polygon/images/1.png Binary files differnew file mode 100644 index 0000000..0e4268a --- /dev/null +++ b/2d/_collisions/polygon_polygon/images/1.png diff --git a/2d/_collisions/polygon_polygon/images/2.png b/2d/_collisions/polygon_polygon/images/2.png Binary files differnew file mode 100644 index 0000000..3dd2020 --- /dev/null +++ b/2d/_collisions/polygon_polygon/images/2.png diff --git a/2d/_collisions/polygon_polygon/images/2a.png b/2d/_collisions/polygon_polygon/images/2a.png Binary files differnew file mode 100644 index 0000000..02bfa02 --- /dev/null +++ b/2d/_collisions/polygon_polygon/images/2a.png diff --git a/2d/_collisions/polygon_polygon/images/2b.png b/2d/_collisions/polygon_polygon/images/2b.png Binary files differnew file mode 100644 index 0000000..1cfc780 --- /dev/null +++ b/2d/_collisions/polygon_polygon/images/2b.png diff --git a/2d/_collisions/polygon_polygon/images/2c.png b/2d/_collisions/polygon_polygon/images/2c.png Binary files differnew file mode 100644 index 0000000..d9ca28b --- /dev/null +++ b/2d/_collisions/polygon_polygon/images/2c.png diff --git a/2d/_collisions/polygon_polygon/images/2d.png b/2d/_collisions/polygon_polygon/images/2d.png Binary files differnew file mode 100644 index 0000000..8e6f6cc --- /dev/null +++ b/2d/_collisions/polygon_polygon/images/2d.png diff --git a/2d/_collisions/polygon_polygon/images/2e.png b/2d/_collisions/polygon_polygon/images/2e.png Binary files differnew file mode 100644 index 0000000..fdaeae3 --- /dev/null +++ b/2d/_collisions/polygon_polygon/images/2e.png diff --git a/2d/_collisions/polygon_polygon/images/2f.png b/2d/_collisions/polygon_polygon/images/2f.png Binary files differnew file mode 100644 index 0000000..9a862b5 --- /dev/null +++ b/2d/_collisions/polygon_polygon/images/2f.png diff --git a/2d/_collisions/polygon_polygon/images/3.png b/2d/_collisions/polygon_polygon/images/3.png Binary files differnew file mode 100644 index 0000000..0e6d218 --- /dev/null +++ b/2d/_collisions/polygon_polygon/images/3.png diff --git a/2d/rigidbody/rigidbody_3.html b/2d/rigidbody/rigidbody_3.html index 60ff03f..eab6527 100644 --- a/2d/rigidbody/rigidbody_3.html +++ b/2d/rigidbody/rigidbody_3.html @@ -67,14 +67,22 @@ </script> <article> - <h1>Rigidbody #2: Rotational Forces</h1> + <h1>Rigidbody #3: Collision Response</h1> + <p> + Now that we have our objects flying and spinning around the scene according to the laws of physics, let's see what happens when two of these objects collide with one another. Please note that this section is <b>not</b> about how we <i>find</i> those collisions, but rather how we <i>resolve</i> those collisions. The links under the "Collision" section on the left pane contain different algorithms on how you can find these collisions. + <br/><br/> + As always, I recommend reading <a href='http://www.chrishecker.com/images/e/e7/Gdmphys3.pdf'>Chris Hecker's explanation</a> of this particular topic if you want more in-depth information. + </p> <section> - <h2>Explanation</h2> + <h2></h2> </section> <section> <h2> Live Example </h2> + <p> + I didn't put any user interaction into this demo yet. This is live however. You can watch as two circles collide with one another. + </p> <div class="opengl_canvas_container"> <canvas id="gl_canvas" width="800" height="600"></canvas> <button id="gl_canvas_play" class="play_button"> diff --git a/2d/rigidbody/rigidbody_3.html.content b/2d/rigidbody/rigidbody_3.html.content index f79db4f..a9c9c5b 100644 --- a/2d/rigidbody/rigidbody_3.html.content +++ b/2d/rigidbody/rigidbody_3.html.content @@ -15,14 +15,22 @@ </script> <article> - <h1>Rigidbody #2: Rotational Forces</h1> + <h1>Rigidbody #3: Collision Response</h1> + <p> + Now that we have our objects flying and spinning around the scene according to the laws of physics, let's see what happens when two of these objects collide with one another. Please note that this section is <b>not</b> about how we <i>find</i> those collisions, but rather how we <i>resolve</i> those collisions. The links under the "Collision" section on the left pane contain different algorithms on how you can find these collisions. + <br/><br/> + As always, I recommend reading <a href='http://www.chrishecker.com/images/e/e7/Gdmphys3.pdf'>Chris Hecker's explanation</a> of this particular topic if you want more in-depth information. + </p> <section> - <h2>Explanation</h2> + <h2></h2> </section> <section> <h2> Live Example </h2> + <p> + I didn't put any user interaction into this demo yet. This is live however. You can watch as two circles collide with one another. + </p> <div class="opengl_canvas_container"> <canvas id="gl_canvas" width="800" height="600"></canvas> <button id="gl_canvas_play" class="play_button"> @@ -133,6 +133,11 @@ nav a:hover { font-style: italic; } +.image { + width: 100%; + text-align: center; +} + /*********************************** Content styling ************************************/ @@ -181,6 +186,10 @@ pre { line-height: 1.0rem; } +code { + font-family: Consolas,monaco,monospace; +} + .code_keyword { color: blue; font-weight: bold; diff --git a/roadmap.html b/roadmap.html index 8d7f3e3..116a57f 100644 --- a/roadmap.html +++ b/roadmap.html @@ -105,6 +105,14 @@ </style> <article> <section> + <h1>July 2021: 3D headway (Planning)</h1> + <ul> + <li>Explanation of Quaternions</li> + <li>3D Rigid Body Collisions</li> + <li>ZIP file creator for downloads</li> + </ul> + </section> + <section> <h1>May/June 2021: More Collisions</h1> <ul> <li class="halfway">SAT Collisions for Convex Polygons with Explanation</li> diff --git a/roadmap.html.content b/roadmap.html.content index ee60886..5e662cc 100644 --- a/roadmap.html.content +++ b/roadmap.html.content @@ -53,6 +53,14 @@ </style> <article> <section> + <h1>July 2021: 3D headway (Planning)</h1> + <ul> + <li>Explanation of Quaternions</li> + <li>3D Rigid Body Collisions</li> + <li>ZIP file creator for downloads</li> + </ul> + </section> + <section> <h1>May/June 2021: More Collisions</h1> <ul> <li class="halfway">SAT Collisions for Convex Polygons with Explanation</li> |
