Name: 凸多角形の衝突 #1 (Convex Polygon Collisions #1)
Uploaded: 2021-01-14T10:16:30.000Z
Duration: 36 min 40 s
Description: VoiceTubeの動画で発音を聞きながら英語表現を覚えよう！学べる英語：

未来進行形

In this video, I'm going to be introducing several techniques toe handle collisions between convex polygons on.

程度の副詞

I'll even look at handling collisions in a static fashion to, but I've got two things to mention just before we get started.

Firstly, anything you can do to a convex polygon, you can also do tow a quadrilateral.

So those of you with tile based systems using rectangles and scores all of this material should be very relevant to.

Secondly, it may seem like a horribly complicated thing.

I want to focus on the algorithms rather than the code for this video.

And so the coding sections may go a bit quicker than usual.

However, I encourage you to download the source file from the get hub and study it for yourselves.

Let's get some of the very basics out of the way first, as my regular viewers will know by now, I draw everything by hand, so technically nothing you'll see on the screen is a poly go.

A polygon is defined by points connected by straight edges, and as you can see, I'm no good at drawing straight things on my screen.

on what I have here is called a concave polygon and concave polygon presents all sorts of problems I'm not going to discuss in the video simply because they have something like this.

And a concave polygon can be identified because it has at least one internal angle that is greater than 180 degrees.

And so for this video, we're not interested in con que Fala guns were interested in convex polygons, which means all of the internal angles are less than 100 and 80 degrees.

Now I know that a large part of my audience build simple to D games and so we mustn't forget that rectangles and squares are also convex polygons on the algorithms.

I'm going to show today there are some explicit optimization is you could make if your system only contains quadrille actuals such as this, But the code I'm going to show is for arbitrary sided convex polygons.

However, I just want to get out of the way.

One little thing which deals with just rectangles only, and you may have heard of it.

It's called a B B, which stands for axis aligned bounding box on.

This is an incredibly simple collision detection routine just for squares and rectangles on specifically for squares and rectangles that haven't been rotated.

And this means given an axis of the world in our X and Y directions, the sides of the quadrilateral a parallel to those axes, checking to see if two axis aligned Quadra laterals overlap is very trivial if I label this one pee on this one.

We can intuitively see that in the X axis.

If this side of P is less than this side of Q, and this is just for X axis, then there is potential for overlap.

Because if this highlighted side of P was greater than the right hand side of Q, clearly they wouldn't be overlapping.

We can confirm this with another check that if this side off P is greater than this side of Q, then in the X axis, these two Quadra laterals are overlapping.

And so if I label this as X on, this point is X plus wit for that rectangle, and the same applies for Q.

We know that there's overlap in the X axis if P X is less than que x plus w and p x plus W is greater than Q X on because our quadrille actuals axis aligned.

Whatever applies in the X axis also applies in the Y axis.

So we can simply duplicate the formula, replacing Xs on W's for wise on H S.

Of course, I'm not even going to code this up because it's so simple and quite obvious.

But I felt it needed a place somewhere in this presentation, as usual.

Before we get stuck into the algorithms, I'd like to just demonstrate the kind of thing I'm going to be building today.

And this is just a little program that demonstrates to alternative methods for detecting overlap between convex polygon.

We've got a selection of convex polygons on the screen.

I've got a Pentagon, which I can move around The line from the middle of the Pentagon to the outside just helps with the direction, so I know how to steer it with the arrow keys.

I could move the Pentagon around with the W S and D keys.

I can't move the square around in the bottom corner and with the function keys, I can choose between four different options of the algorithms.

The first is called separated Access Theory on As you'll see as I move the Pentagon into the square, it's changed.

Read that indicates that overlap has occurred, in fact, and go over the triangle and the same thing happens.

And it's very, very precise for now, the the alternative algorithm that where I look at diagonals versus edges gives exactly the same result.

I can move the triangle into the quadrilateral as well.

Detecting whether two polygons overlap is very useful.

But if we wanted to actually constrain them from overlapping, we need to apply some sort of static collision resolution.

And so I can press F two to select static for the separated access their version, and we'll see what happens so I can control the Pentagon.

We can see it doesn't go between the shakes, but it Judd is a little bit.

Now the shapes have a degree of priority, so if I push the triangle, I can push the other shape around.

But I can't push the quadrille national around with the triangle.

We can see the collision is quite robust.

There's no dynamic response is implemented here.

So the feel of what's going on may look a little strange because you'd expect it to rotate and bounce accordingly.

It's just a way of stopping the shapes from overlapping the alternative method.

Using the shapes diagonals on, we will go into some detail about these methods during this video, I feel is a little bit more numerically stable.

So if I take the Pentagon this time, what we noticed is, well, I set it up.

There's actually less juddering as part off the resolution.

The diagonal method approach is a little bit more computational intensive, but fractionally so.

But I think the results on the stability are just a little better.

So let's get started with the rather traditional separated access their, um, here I have a polygon, and here I have a number.

Firstly, we can see they're both convicts, and secondly, we can see they're not access aligned in any way.

This approach involves looking at the shadows off the shape along an axis and checking if for that axis, the shadows overlap.

In fact, we're going to check against several different axes And if the shadows overlapped for all of those axes, we know that the two shapes have collided.

Well, I'm going to create an axis relative to each edge of each polygon on.

I'm going to do that by simply taking the normal oven edge.

So taking this edge of this triangle, I'm going to create an axis relative to that.

Now, it doesn't matter where that axes actually exists in space, as long as we have something that is parallel to it.

So I'm going to translate that access down here just makes the drawing a bit clearer.

And now I'm interested in the normal to that axis, which is, of course, the original direction of the edge of the polygon.

To begin with and somewhere in space appear, I'm going to turn a light on.

And this is a special light because it transmits light globally, but in a single direction.

This means that all of our points will cast a shadow onto this axis.

And we look at all points on both shapes.

We then work out the minimum and maximum extent of that shadow.

So for the quadrilateral here we can see the two big red points on the axis.

And for a triangle, we've got the two big blue points.

We've got the two shadows of the two shapes on What do we see?

Well, the shadows overlap and using a method very similar to the Axis aligned bounding box I've just described, we can consider that for this particular access, we've got overlap, and so far our shapes must be overlapping.

This algorithm requires that we repeat this process for every edge of both shapes.

In fact, it will be for every edge of all shapes who want to test collisions between.

So let's consider two shapes that are not overlapping on.

We'll start with this edge, so we'll take the normal of this edge to create our access on.

I don't need to use the lightbulb analogy anymore.

I think you can see how we can crush these points onto this access.

When we project the point onto this access we can see.

In this instance, there's no overlap between the two shapes, and if we find one axis that has no overlap, then the shapes can't be in collision.

They are indeed separated along that access.

Things get a little strange when we try to assign numeric values to what's going on here.

But ultimately, the numeric values of things is quite irrelevant because it's all relative to one particular system.

字幕リスト動画再生

凸多角形の衝突 #1 (Convex Polygon Collisions #1)

approach

access

alternative

scale