Handling collisions with an algorithm and implementation
Hi, Habr!
Recently saw an article about handling collisions. And there was not the most important thing - the algorithm and implementation. Let's fill this gap and look at how to find and handle collisions. The implementation will be in Java.
I warn you that the article has a lot of code.
')
The algorithm is based on the separating axis theorem. For a 3D case, this is the dividing plane.
The definition will be this: if there is a plane (for a 2D straight line) between two convex figures, in relation to which the figures lie on opposite sides, then such figures do not overlap.
The consequence, with the help of which it is possible to check the dividing plane or not: if we take our dividing plane and build a perpendicular to it, then the projections of the figures on the resulting plane will also not be stopped.
In order to find (or not find if the figures intersect) the dividing plane, it is necessary to assemble the normals of the sides and build perpendiculars to them. These perpendiculars will be normals of the planes on which it will be necessary to build projections of models. In this case, we do not need to know the coordinates of the plane; we will assume that they all pass through the center. The figure below shows the verification of one of the parties.
Green indicates the normal of the side of the figure that is checked. Red is the dividing plane. The blue plane on which we must build projections. As you can see, if we take the normal of the blue plane, then it will be perpendicular to the normal of the side we are testing.
Now we have two projections of models on each plane. It is necessary to find at least one plane where the projections do not intersect. To do this, you can apply the same theorem, only for the 2D case (more details in the implementation). If we find one, then the models do not overlap. Accordingly, if we do not find - overlap.
Based on the theory, you can make the following algorithm works:
Then we work separately with each plane.
Algorithm for checking the intersection of projections:
We collect all sides of the projections and then work with them.
Next we analyze the full implementation of finding and processing intersections.
A small digression:
I will not shorten the laid out code (the devil is in the details), just add comments, maybe I will not post any methods that interest you, but they can be easily found in the repository on GitHub , I will also leave links to classes.
Following the algorithm, let's start with the search for all planes. It is assumed that we know the normals (loaded them from the model file).
It is very important to weed out the same planes, the algorithm is very difficult in terms of costs, and any optimization will be appropriate. In this case, it is not any, and a decrease in the number of checked planes greatly affects its speed.
For the physical models in the game, I use only parallelepipeds, no complex shapes. As a result, in the worst case, we will check 6 planes.
Before you begin, consider the interface that I will use below.
Class source code Plane , Vector3
So, we have planes that need to be checked. To do this, we construct projections of models on each plane. If we do not find the planes on which the projections do not intersect, then we need to find the plane on which the models intersect the least of all, we need to extract a vector from this intersection. This will be the vector on which it is necessary to move one of the models so that they no longer intersect.
Vector we initially get on the plane. Therefore, although the direction of the axes of the X and Y planes is not important to us, however, we must save them, since the vector will need to be returned to 3D and they will be useful to us.
Class implementing the search for the intersection of models: Collision3D
Code executing the algorithm above:
Let us consider in more detail how we get the projections. Here is the full implementation.
Actually finding the projection itself is not difficult, but there will be no sense from the projection itself. For further processing it is necessary to correctly find the sides of the figure. It should also be convex, the picture below explains why.
As can be seen in the first figure (with a concave figure), the algorithm considers that the figures intersect, although we can construct a separating axis. Since the axis is searched from the sides of the figure, there is no parallel side to the axis in this case. In the second figure, an MBO is drawn up along the concave figure. Here the algorithm will find the axis. To find the shell, I implemented the Graham algorithm.
Below is the function of finding a simple projection — a set of points projected onto a plane.
Now it's time to look at the implementation of building an MBO .
Action can be painted on four steps.
The first point that should be included in the MBO, I choose the rightmost. If there are more than one, then choose the top one.
The most buggy place I had was sorting the points counterclockwise. In the beginning there were just incorrect implementations, and then it took a lot of time to understand what exceptional situations there are. For myself, even the comments written, so as not to forget what's what.
Sort the points relative to the first in the corners. If the points are equal angles, then I compare them in distance from the first one and in different ways depending on how the points lie - above or below the reference. If lower, then the first must go to the one to which the distance is less. If higher - the opposite.
The blue dot is the reference. Green - the usual points. Red - with the same angles. The traversal scheme demonstrates the sorting algorithm described above.
You also need to remember to normalize the corners for normal sorting, there will be an example in the code.
With the search for the projection figured out, it is now necessary to understand how to find the intersection of two projections. The logic remains the same as with 3D.
Further I will call these projections figures, because how to build further we will be projections of projections, I apologize for the tautology.
Looking through all sides of the obtained figures, we look for normals. Next, we build the projection of the figure onto the found normal, if at least one straight line is found on which the projections do not intersect, so what? Suddenly, but the figures (like 3D models) are not suppressed in this case. :)
Full implementation of the class here: Collision2D
Immediately in the method above we are looking for the minimum intersection vector, if the figures do not intersect it, of course, we will not need it. And if crossed, it must be converted to 3D, so that the models can be moved away from each other. You can do this using the method below.
On this, in principle, everything, everything described above is sufficient to determine the intersection of 3D models.
Instead of writing, I'll write that checking for the intersection of two objects takes a lot of time. As I said before, I do not use complex collision models. I also apply a number of optimizations such as calculating the radius of the sphere described around the model, the intersection of the spheres is much easier to compare. For the same objects of the sphere that intersect, a detailed search for intersections is performed in parallel .
The sources of the game are here: github.com/Nirklav/Tanks
UPD : Updated the implementation of the algorithm, removing the extra step in the form of a projection on the plane, now the projections are searched immediately to the normal.
Recently saw an article about handling collisions. And there was not the most important thing - the algorithm and implementation. Let's fill this gap and look at how to find and handle collisions. The implementation will be in Java.
I warn you that the article has a lot of code.
')
A bit of theory
The algorithm is based on the separating axis theorem. For a 3D case, this is the dividing plane.
The definition will be this: if there is a plane (for a 2D straight line) between two convex figures, in relation to which the figures lie on opposite sides, then such figures do not overlap.
The consequence, with the help of which it is possible to check the dividing plane or not: if we take our dividing plane and build a perpendicular to it, then the projections of the figures on the resulting plane will also not be stopped.
In order to find (or not find if the figures intersect) the dividing plane, it is necessary to assemble the normals of the sides and build perpendiculars to them. These perpendiculars will be normals of the planes on which it will be necessary to build projections of models. In this case, we do not need to know the coordinates of the plane; we will assume that they all pass through the center. The figure below shows the verification of one of the parties.
Green indicates the normal of the side of the figure that is checked. Red is the dividing plane. The blue plane on which we must build projections. As you can see, if we take the normal of the blue plane, then it will be perpendicular to the normal of the side we are testing.
Now we have two projections of models on each plane. It is necessary to find at least one plane where the projections do not intersect. To do this, you can apply the same theorem, only for the 2D case (more details in the implementation). If we find one, then the models do not overlap. Accordingly, if we do not find - overlap.
Algorithm
Based on the theory, you can make the following algorithm works:
- Find all the normals of the objects. (we collect normals from both objects)
- Normally we find planes on which we will build projections.
Then we work separately with each plane.
- We are looking for projection models on the plane.
- Check whether the projections intersect. If not, then our objects also do not overlap.
Algorithm for checking the intersection of projections:
We collect all sides of the projections and then work with them.
- We are looking for perpendicular to the side.
- We build on this perpendicular projection of figures. If the projections do not intersect, then our figures also.
Implementation
Next we analyze the full implementation of finding and processing intersections.
A small digression:
I will not shorten the laid out code (the devil is in the details), just add comments, maybe I will not post any methods that interest you, but they can be easily found in the repository on GitHub , I will also leave links to classes.
Following the algorithm, let's start with the search for all planes. It is assumed that we know the normals (loaded them from the model file).
It is very important to weed out the same planes, the algorithm is very difficult in terms of costs, and any optimization will be appropriate. In this case, it is not any, and a decrease in the number of checked planes greatly affects its speed.
For the physical models in the game, I use only parallelepipeds, no complex shapes. As a result, in the worst case, we will check 6 planes.
Before you begin, consider the interface that I will use below.
public interface ICollidable { // . // , . float getRadius(); Vector3 getPosition(); ArrayList<Vector2> getConvexHull(Plane plane); // ( ) ArrayList<Vector3> getNormals(); void normalizeLocation(); } private static ArrayList<Plane> getPlanes(ICollidable firstPh, ICollidable secondPh) { ArrayList<Plane> planes = new ArrayList<>(); ArrayList<Vector3> firstNormals = firstPh.getNormals(); ArrayList<Vector3> secondNormals = secondPh.getNormals(); Plane plane = new Plane(); int size = firstNormals.size() + secondNormals.size(); for(int i = 0; i < size; i++) { setPlane(plane, firstNormals, secondNormals, i); if (!planes.contains(plane)) planes.add(new Plane(plane)); } return planes; } private static void setPlane(Plane plane, ArrayList<Vector3> firstNormals, ArrayList<Vector3> secondNormals, int num) { // ( x, y ) if (num < firstNormals.size()) plane.setFrom(firstNormals.get(num)); else { num -= firstNormals.size(); plane.setFrom(secondNormals.get(num)); } // . plane.swapZY(); } Class source code Plane , Vector3
So, we have planes that need to be checked. To do this, we construct projections of models on each plane. If we do not find the planes on which the projections do not intersect, then we need to find the plane on which the models intersect the least of all, we need to extract a vector from this intersection. This will be the vector on which it is necessary to move one of the models so that they no longer intersect.
Vector we initially get on the plane. Therefore, although the direction of the axes of the X and Y planes is not important to us, however, we must save them, since the vector will need to be returned to 3D and they will be useful to us.
Class implementing the search for the intersection of models: Collision3D
Code executing the algorithm above:
private static CheckResult check(ICollidable firstPh, ICollidable secondPh) { // ArrayList<Plane> planes = getPlanes(firstPh, secondPh); Collision2D min = null; Plane minPlane = new Plane(); for (Plane plane : planes) { // . ArrayList<Vector2> resultOne = firstPh.getConvexHull(plane); ArrayList<Vector2> resultTwo = secondPh.getConvexHull(plane); // . ( "check") Collision2D collision = new Collision2D(resultOne, resultTwo); Vector.release(resultOne); Vector.release(resultTwo); if (!collision.isCollide()) return null; // if (min == null || collision.getMTVLength() < min.getMTVLength()) { min = collision; minPlane.setFrom(plane); } plane.release(); } return new CheckResult(min, minPlane); } Let us consider in more detail how we get the projections. Here is the full implementation.
Actually finding the projection itself is not difficult, but there will be no sense from the projection itself. For further processing it is necessary to correctly find the sides of the figure. It should also be convex, the picture below explains why.
Voguntaya | Convex |
As can be seen in the first figure (with a concave figure), the algorithm considers that the figures intersect, although we can construct a separating axis. Since the axis is searched from the sides of the figure, there is no parallel side to the axis in this case. In the second figure, an MBO is drawn up along the concave figure. Here the algorithm will find the axis. To find the shell, I implemented the Graham algorithm.
Below is the function of finding a simple projection — a set of points projected onto a plane.
private ArrayList<Vector2> getDistinctProjection(Plane plane) { Vector2 vector = Vector.getInstance(2); // HashSet ( ) ArrayList<Vector2> result = new ArrayList<>(); for (Vector3 current : vertices) { plane.getProjection(vector, current); if (!result.contains(vector)) // { Vector2 copy = Vector.getInstance(2, vector); result.add(copy); } } Vector.release(vector); return result; } // Plane: public void getProjection(Vector2 result, Vector3 vector) { throwIfReleased(); float x = vector.getX() * xAxis.getX() + vector.getY() * xAxis.getY() + vector.getZ() * xAxis.getZ(); float y = vector.getX() * yAxis.getX() + vector.getY() * yAxis.getY() + vector.getZ() * yAxis.getZ(); result.setFrom(x, y); } Now it's time to look at the implementation of building an MBO .
Action can be painted on four steps.
- Search projection.
- Selection of the reference point.
- Sort the remaining points relative to the reference.
- Remove extra points.
Little about mvo
Wikipedia says that:
Also there is an example:
Good article on building a minimal convex hull .
The convex hull of a set X is the smallest convex set containing X. “Least set” here means the smallest element with respect to the embedding of sets, that is, such a convex set containing this shape that it is contained in any other convex set containing this shape.
Also there is an example:
Imagine a board into which you have driven - but not to the bit of a hat - many nails. Take a rope, tie a sliding loop (lasso) on it and throw it on the board, and then tighten it. The rope surrounds all the nails, but it concerns only some of the most external. Those nails, which it concerns, constitute a convex shell for the entire group of nails [1].
Good article on building a minimal convex hull .
@Override public ArrayList<Vector2> getConvexHull(Plane plane) { // ArrayList<Vector2> projection = getDistinctProjection(plane); ArrayList<Vector2> convexHull = new ArrayList<>(projection.size()); if (projection.size() < 2) throw new IllegalStateException("projection size less than 2"); // , 100% // // , . int firstIndex = getFirstPointIndex(projection); Vector2 first = projection.remove(firstIndex); convexHull.add(first); // Collections.sort(projection, new AngleComparator(first)); // , .. . Vector2 second = projection.remove(0); convexHull.add(second); Vector2 prevVector = Vector.getInstance(2); Vector2 currentVector = Vector.getInstance(2); for(Vector2 current : projection) { Vector2 firstPrevPoint = convexHull.get(convexHull.size() - 1); Vector2 secondPrevPoint = convexHull.get(convexHull.size() - 2); // prevVector.setFrom(firstPrevPoint); prevVector.subtract(secondPrevPoint); // currentVector.setFrom(current); currentVector.subtract(firstPrevPoint); // , float angle = prevVector.getAngle(currentVector); if (angle >= 180 && angle < 360) convexHull.remove(convexHull.size() - 1); // convexHull.add(current); } Vector.release(prevVector); Vector.release(currentVector); return convexHull; } getAngle
// Vector2 public float getAngle(Vector2 other) { throwIfReleased(); float scalar = getScalar(other); float lengthOne = this.getLength(); float lengthTwo = other.getLength(); float angle = (float)Math.toDegrees(Math.acos(scalar / (lengthOne * lengthTwo))); return Angle.correct(getCross(other) > 0 ? angle : 360 - angle); } The first point that should be included in the MBO, I choose the rightmost. If there are more than one, then choose the top one.
Select the first point
private static int getFirstPointIndex(ArrayList<Vector2> projection) { Vector2 minVector = null; int minVectorIndex = 0; int size = projection.size(); for (int i = 0; i < size; i++) { Vector2 current = projection.get(i); if (minVector == null) { minVector = current; continue; } int compareX = Float.compare(current.getX(), minVector.getX()); if (compareX < 0) { minVector = current; minVectorIndex = i; } if (compareX == 0) { int compareY = Float.compare(current.getY(), minVector.getY()); if (compareY == 0) throw new IllegalArgumentException("projection has the same points"); if (compareY > 0) { minVector = current; minVectorIndex = i; } } } return minVectorIndex; } The most buggy place I had was sorting the points counterclockwise. In the beginning there were just incorrect implementations, and then it took a lot of time to understand what exceptional situations there are. For myself, even the comments written, so as not to forget what's what.
Sort the points relative to the first in the corners. If the points are equal angles, then I compare them in distance from the first one and in different ways depending on how the points lie - above or below the reference. If lower, then the first must go to the one to which the distance is less. If higher - the opposite.
The blue dot is the reference. Green - the usual points. Red - with the same angles. The traversal scheme demonstrates the sorting algorithm described above.
You also need to remember to normalize the corners for normal sorting, there will be an example in the code.
private static class AngleComparator implements Comparator<Vector2> { private Vector2 first; private Vector2 left; private Vector2 right; public AngleComparator(Vector2 first) { this.first = first; left = Vector.getInstance(2); right = Vector.getInstance(2); } @Override public int compare(Vector2 lhs, Vector2 rhs) { // // left.setFrom(lhs); left.subtract(first); right.setFrom(rhs); right.subtract(first); // float firstAngle = Vector2.xAxis.getAngle(left); float secondAngle = Vector2.xAxis.getAngle(right); // // : 15, 45, 315, 345 () => -45, -15, 15, 45 () if (firstAngle > 90) firstAngle -= 360; if (secondAngle > 90) secondAngle -= 360; // // // . // , // if (Math.abs(firstAngle - secondAngle) <= Vector.epsilon) { float leftLength = left.getLength(); float rightLength = right.getLength(); // 0, if (firstAngle >= 0) return Float.compare(rightLength, leftLength); return Float.compare(leftLength, rightLength); } // return Float.compare(firstAngle, secondAngle); } } With the search for the projection figured out, it is now necessary to understand how to find the intersection of two projections. The logic remains the same as with 3D.
Further I will call these projections figures, because how to build further we will be projections of projections, I apologize for the tautology.
Looking through all sides of the obtained figures, we look for normals. Next, we build the projection of the figure onto the found normal, if at least one straight line is found on which the projections do not intersect, so what? Suddenly, but the figures (like 3D models) are not suppressed in this case. :)
Full implementation of the class here: Collision2D
private static CheckResult check(ArrayList<Vector2> firstVertices, ArrayList<Vector2> secondVertices) { Vector2 mtv = null; Vector2 normal = Vector.getInstance(2); float minMTVLength = 0.0f; int count = firstVertices.size() + secondVertices.size(); for (int i = 0; i < count; i ++) { setNormal(normal, firstVertices, secondVertices, i); // . X - Y - . Vector2 firstProjection = normal.getProjection(firstVertices); Vector2 secondProjection = normal.getProjection(secondVertices); // , , . if (firstProjection.getX() < secondProjection.getY() || secondProjection.getX() < firstProjection.getY()) return null; // . , . if (mtv == null) { mtv = Vector.getInstance(2, normal); minMTVLength = getIntersectionLength(firstProjection, secondProjection); } else { float mtvLength = getIntersectionLength(firstProjection, secondProjection); if (Math.abs(mtvLength) < Math.abs(minMTVLength)) { mtv = Vector.getInstance(2, normal); minMTVLength = mtvLength; } } } return new CheckResult(mtv, minMTVLength); } // Vector2 public Vector2 getProjection(ArrayList<Vector2> vertices) { Vector2 result = null; for (Vector2 current : vertices) { float projection = getScalar(current); if (result == null) result = new Vector2(projection, projection); // x - max if (projection > result.getX()) result.setX(projection); // y - min if (projection < result.getY()) result.setY(projection); } return result; } getIntersectionLength, setNormal
private static float getIntersectionLength(Vector2 firstProjection, Vector2 secondProjection) { return (secondProjection.getY() - firstProjection.getX() > 0) ? secondProjection.getY() - firstProjection.getX() : firstProjection.getY() - secondProjection.getX(); } private static void setNormal(Vector2 normal, ArrayList<Vector2> vertices, int num) { Vector2 firstPoint = vertices.get(num); Vector2 secondPoint = vertices.get(num + 1 == vertices.size() ? 0 : num + 1); Vector2 edge = secondPoint.getSubtract(firstPoint); normal.setX(-edge.getY()); normal.setY(edge.getX()); normal.normalize(); } Immediately in the method above we are looking for the minimum intersection vector, if the figures do not intersect it, of course, we will not need it. And if crossed, it must be converted to 3D, so that the models can be moved away from each other. You can do this using the method below.
private static Vector3 getMTV(CheckResult result) { Vector2 mtv2 = result.collision.getMTV(); Vector3 mtv3 = new Vector3(mtv2.getX(), mtv2.getY(), 0); Vector3 planeX = result.plane.xAxis(); Vector3 planeY = result.plane.yAxis(); Vector3 planeZ = result.plane.zAxis(); float[] matrix = new float[16]; matrix[0] = planeX.getX(); matrix[1] = planeX.getY(); matrix[2] = planeX.getZ(); matrix[4] = planeY.getX(); matrix[5] = planeY.getY(); matrix[6] = planeY.getZ(); matrix[8] = planeZ.getX(); matrix[9] = planeZ.getY(); matrix[10] = planeZ.getZ(); matrix[15] = 1.0f; Matrix.multiplyMV(mtv3.getRaw(), 0, matrix, 0, mtv3.getRaw(), 0); mtv3.normalize(); return mtv3; } On this, in principle, everything, everything described above is sufficient to determine the intersection of 3D models.
Algorithm application
Instead of writing, I'll write that checking for the intersection of two objects takes a lot of time. As I said before, I do not use complex collision models. I also apply a number of optimizations such as calculating the radius of the sphere described around the model, the intersection of the spheres is much easier to compare. For the same objects of the sphere that intersect, a detailed search for intersections is performed in parallel .
The sources of the game are here: github.com/Nirklav/Tanks
UPD : Updated the implementation of the algorithm, removing the extra step in the form of a projection on the plane, now the projections are searched immediately to the normal.
Source: https://habr.com/ru/post/257655/
All Articles