Bitc

def ray_plane_intersection(ray_origin, ray_dir, tri_vertices, tri_normal):
    denom = dot(tri_normal, ray_dir)
    if abs(denom) < 1e-6:  # Ray parallel to plane
        return None
    t = dot(tri_normal, tri_vertices[0] - ray_origin) / denom
    if t < 0:
        return None  # Intersection behind ray origin
    intersection = ray_origin + t * ray_dir
    return intersection

def point_in_triangle(p, A, B, C):
    # Use barycentric coordinates to check if p is inside triangle ABC
    v0 = C - A
    v1 = B - A
    v2 = p - A

    dot00 = dot(v0, v0)
    dot01 = dot(v0, v1)
    dot02 = dot(v0, v2)
    dot11 = dot(v1, v1)
    dot12 = dot(v1, v2)

    invDenom = 1 / (dot00 * dot11 - dot01 * dot01)
    u = (dot11 * dot02 - dot01 * dot12) * invDenom
    v = (dot00 * dot12 - dot01 * dot02) * invDenom

    return (u >= 0) and (v >= 0) and (u + v <= 1)

def find_floor_clip(pos, vel, dt, floor_triangles):
    # Step 2 & 3
    x_new = pos.x + vel.x * dt
    z_new = pos.z + vel.z * dt

    # Step 4
    ray_origin = Vector3(x_new, pos.y + 0.1, z_new)
    ray_dir = Vector3(0, -1, 0)

    for tri in floor_triangles:
        intersection = ray_plane_intersection(ray_origin, ray_dir, tri.vertices, tri.normal)
        if intersection is not None:
            if point_in_triangle(intersection, *tri.vertices):
                # Check if intersection is on seam/gap edge (optional debug)
                if is_on_gap_edge(intersection, tri):
                    return intersection

    return None