I know there is already a lot of topics about collision detection but I didn’t find a simple answer to my issue yet.
Indeed I want to solve a pretty simple collision detection issue between a square and a triangle:
If I move any of the above shapes using DragControls, when drag ends, how can I know if the shapes are colliding? https://codepen.io/renodor/pen/dyewWJO
(This is part of a bigger project but I tried to simplify the pb at maximum, and it got down to that. I found a lot of collision topics using BoundingBox or BoundingSphere, but I’m working with polygones (triangles, and trapezoid))
You can check if lines are parallel, if you care about them intersecting, no need to actually find the intersection point.
To not hijack this thread I put some of the relevant code that I use here (disclaimer: I only test this code when I use it, so not a 100% guarantee on anything):
polygonOffset - creates “thick” version of a polygonal line as a shape, useful since WebGL doesn’t have line thickness.
Hey @tfoller I don’t have concave polygons so we should be good.
I see the pointInPolygon method you are refering to here, but the next question is how do you get the points of a polygon? Or more precisely how do you get those points to update when your polygon moves?
Because I can retrieve the points from polygon.geometry.attributes.position.array but when I drag/drop this polygon those attributes are not updated… So I gues we need to manually update it but how?
All mesh transformations (translation, rotation, scale) are stored separately on the mesh object in various matrices, so you’ll probably need to multiply all the geometry vertices by the combined matrix (gets more complicated if your meshes have parents).
mesh.matrixWorld is most likely the one you need but it’s calculated by the library during rendering, so it’s available only after the frame render (before the render it’s going to be identity matrix). If you need it before the render, I guess you need to make it by yourself.
There are some getWorld… functions here three.js docs but again I’m not sure if you can get them before rendering.
The easiest way to make a matrix from translation, rotation, scale is probably .compose: three.js docs
Okay I see your point (about multiplying geometry vertices by the current position and rotation of the obejct in order to have to correct object points).
And just to be sure that I understand correctly your pointInPolygon method:
It has 3 arguments:
pts : that’s the points of the polygon to check against
x : the x coordinate of the point we want to check
y : the y coordinate of the point we want to check
So it means if my red triangle have the points A, B, C, and my green square have the points D, E, F, G, in order to check if the green square colides with the red triangle ll have to do something like:
(pseudo code):
[D, E, F, G].forEach(point) => {
if (pointInPolygon([A, B, C], point[x], point[y])) {
# collision
}
}
→ If any of D, E, F, G point is in [A, B, C] polygon, then green square colides with red triangle.
→ On the contrary, if none of D, E, F, G point is in [A, B, C] polygon, then green square does not colides with red triangle.
I colorized the triangle vertices that are inside the cube, so you can drag them around and see which ones are which:
Important notice: you can’t get vertices from the geometry attribute array - that array forms triangles for the mesh, you meed to mention points in the order they make border lines of the shape.
Hum actually I think it’s not enough… Check the following situation:
The triangle is clearly coliding with the square, but none of the triangle point is actually “within” the square. So pointInPolygon will return false for every points of the triangle against the square…
That said one of the square point is within the triangle… So I guess to have a complete collision detection, I will always need to check triangle points against square AND square points against triangle.
Well, you are asking about collision, it normally happens when you drive one object into another (partially) and it protrudes in, not jumps inside/across it completely in one fell swoop (like a smaller sphere sitting inside a bigger sphere), so what you have on the picture is more like overlapping shapes, not collision.
That being said, you could add more points to the sides of the triangle ( or box ), so there is no way for a side to cross the whole shape like that.
Another, much slower method is to render, say, red triangle, half transparent on top of the green box, and then search for purple-ish pixels on the image (that have red and green channels) on the CPU side using WebGLRenderingContext.readPixels() or renderTarget.readRenderTargetPixels if you render on the target for that purpose (in case your actual objects have to be colorized differently).
I agree that this would only happen when driving the triangle into the square. But for example if I want to use your method to prevent colliding (or overlaping) objects while draging and droping it won’t work. (I would drag the triangle within the square, it would prevent me to drop it as long as no points of both shapes are within the other shape, but as soon as I reach the situation of my last screenshot, it would allow me to drop it…)
So I think adding more points to the sides of the triangle will work for me here.
Finding if there is a point that belongs to two arbitrary shapes is at least a complex task, so yeah, some quick hack that depends on the situation is probably the best option. You can also add points in the middle of the shapes to the check list, not only on the boundary.
