CODEWITHSUNDEEP
pythoncollision-detectiongame-physicsvector-graphicsvectormath
Beefcake
Beefcake

Reputation: 334

Deciding which colliding segment to use as impact vector for reflection

Problem

I´m working on a simple OpenGL project. My goal is to correctly reflect an object that has a force on it, off of an impacted object.

To do this, I am using the shape´s line segments (segment is two points that make up a line), for collision detection. The segments of a square would for example be:

self.segments = [
            Segment2D(self.bottom_left, self.bottom_right),  # Bottom side
            Segment2D(self.bottom_right, self.top_right),  # Right side
            Segment2D(self.top_right, self.top_left),  # Top side
            Segment2D(self.top_left, self.bottom_left)  # Left side
        ]

The detection works by checking if any of the object's segments are intersecting with an external object's segments. I am using a method explained in geeksforgeeks: https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/

To calculate the reflection I am using the formula r=d−2(d⋅n)n
enter image description here

However; After finding that an object is colliding with another object, a problem arises with finding this reflection vector.

enter image description here

When two squares collide for example (the only shape I've implemented), the collision detection will sometimes detect collision on two segments. Since I do not know how I should choose which one to use as the impacted segment the reflection will sometimes be in the wrong direction.

Question

How can I decide which segment of the green ones in the image should be used as the impact vector for the reflection?

Edit:
I have now implemented the solution Blindman67 suggested. The collision detection, (deciding which side to collide) seems to work in about 80% of cases. The square sometimes still reflects in the wrong direction when colliding close to a corner. I am not sure whether this is a bug of mine or the given solution.

I have been unable to resolve the issue.

Also the checks no longer hold when the impacted square is swallowed on both sides, making the impacted lines parallel to each other.

This is the logic I've come up with:

def rect_rect_collision(self, other, force: Vector2D, segments: List[Segment2D]) -> Segment2D:
        """
        Returns the segment that is the most correct one for collision
        :param other: Colliding RigidBody
        :param force: The force applied on the object
        :param segments: The segments that were detected as colliding by the general detection
        :return: The correct collision segment
        """
        if segments[0].angle() == segments[1].angle():
            # TODO: decide which to collide of the remaining 2
            raise Exception("Lines are parallel")

        # Shared corner of the impacted segments
        common_corner = RigidRect2D.get_common_corner(segments[0], segments[1])
        E: Point2D = self.add_width_height_relative_to_center(common_corner, other.shape.center)
        # Segment 0 is EF
        seg_0_other = segments[0].p1 if segments[0].p2 == common_corner else segments[0].p2
        F: Point2D = self.add_width_height_relative_to_center(seg_0_other, other.shape.center)
        # Segment 1 is EJ
        seg_1_other = segments[1].p1 if segments[1].p2 == common_corner else segments[1].p2
        J: Point2D = self.add_width_height_relative_to_center(seg_1_other, other.shape.center)

        A: Point2D = self.shape.center
        ABx: float = force.x
        ABy: float = force.y
        uu = ABx * (A.y - E.y) - ABy * (A.x - E.x)

        EFx = F.x - E.x
        EFy = F.y - E.y
        c = ABx * EFy - ABy * EFx
        if c != 0:
            u = uu / c
            print("U - EF: ", u)
            if 0 <= u <= 1:
                # Hits line E-F
                return segments[0]

        EJx = J.x - E.x
        EJy = J.y - E.y
        c = ABx * EJy - ABy * EJx
        if c != 0:
            u = uu / c
            print("U - EJ: ", u)
            if 0 <= u <= 1:
                # Hits line E-J
                return segments[1]

        raise Exception("Returned no segment from the collision detection")

    @staticmethod
    def get_common_corner(segment1: Segment2D, segment2: Segment2D):
        if segment1.has_point(segment2.p1):
            return segment2.p1
        if segment1.has_point(segment2.p2):
            return segment2.p2
        print(segment1)
        print(segment2)
        raise Exception("No common corner")

    def add_width_height_relative_to_center(self, point: Point2D, center: Point2D) -> Point2D:
        newPoint = Point2D(point.x, point.y)
        if newPoint.y >= center.y:
            newPoint.y += self.shape.height / 2
        else:
            newPoint.y -= self.shape.height / 2

        if newPoint.x >= center.x:
            newPoint.x += self.shape.width / 2
        else:
            newPoint.x -= self.shape.width / 2

        return newPoint

Here's an image depicting the incorrect impact vector that the reflection method received from the rect_rect_collision method: incorrect_impact vector

The green outlines are the rigidBodies that are collidable, the red arrow is the force vector's direction BEFORE the reflection. After the reflection is calculated, the reflection will be in the incorrect direction.

Upvotes: 1

Views: 367

Answers (2)

Blindman67
Blindman67

Reputation: 54099

Using the following illustration.

enter image description here

The box moves along the vector A-B. Calculate the intercepts between A-B and E-F and E-J as units along E-F, or E-J The point of intercept C will in the illustration be between lines A-B and E-J

ABx = B.x - A.x
ABy = B.y - A.y
uu = ABx * (A.y - E.y) - ABy * (A.x - E.x)

EFx = F.x - E.x
EFy = F.y - E.y
c = ABx * EFy - ABy * EFx
if (c !== 0) {
    u = uu / c
    if (u >= 0 && u <= 1) {
        // hits line E-F
    }
}

EJx = J.x - E.x
EJy = J.y - E.y
c = ABx * EJy - ABy * EJx
if (c !== 0) {
    u = uu / c
    if (u >= 0 && u <= 1) {
        // hits line E-J
    }
}

If the boxes are axis aligned AABB then you can simplify by canceling out zeros

ABx = B.x - A.x
ABy = B.y - A.y
uu = ABx * (A.y - E.y) - ABy * (A.x - E.x)

c = -ABy * (F.x - E.x)  
if (c !== 0) {
    u = uu / c
    if (u >= 0 && u <= 1) {
        // hits line E-F
    }
}

c = ABx * (J.y - E.y) 
if (c !== 0) {
    u = uu / c
    if (u >= 0 && u <= 1) {
        // hits line E-J
    }
}

Note that point E represent the common corner as the test is only between the two sides you wish to test. You will never need to test more than two sides.

Upvotes: 2

comingstorm
comingstorm

Reputation: 26117

The accurate way to do this is to treat objects in motion as a function of time.

Currently, you do a full update's worth of motion, then check if the objects overlap:

(x, y) := (x+dx, y+dy)

Instead, you can treat the object's position as a function of time (from the previous frame to new one). This makes the output of the collision logic also a function of time: starting at "no" collision (as you have already checked the previous frame), and possibly changing to "yes" before the end of the update period.

pos(t) = (x+t*dx, y+t*dy)  # for t in [0..1]

Solving for earliest collision point should also let you determine which side the collision is on: each side will have a collision condition, and the first one that fails is the one that is hit. In addition, this method avoids the case where your objects are moving so fast that they can pass through each other.

Upvotes: 0

Related Questions