Свой 3D движок Python Пересечение отрезка и прямоугольника

Я пишу свой небольшой 3D движок на Python Я использовал технологию когда выпускаешь из камеры много лучей-пикселей и меряешь расстояние до треугольников. Но даже после numpy, оптимизации и распараллеливания с numba и много другого, нормальные объекты на 1000 треугольников даже в разрешении 400+400 пикселей рендерятся 4-7 минут, что очень много.

Появилась идея нового алгоритма - ты смотришь на какой пиксель в камере попадает отрезок от точки съемки до точки треугольника, находишь три пикселя и между ними делаешь треугольник средствами pygame.

Но в интернете я нашел нигде внятного объяснения того как рассчитать хотя бы точку пересечения отрезка и прямоугольника в пространстве. Помогите пожалуйста, так как я даже школу не закончил что бы самому придумать мат. решение.

Желательно решение для CPU и для Windows

Картинка - описание способа которого надо сделать введите сюда описание изображения


Ответы (1 шт):

Автор решения: FotonPC

Не дождался ответа, поэтому несколько часов решал уравнения и все получилось. вот код для этой функции. Возможно можно как-то еще до оптимизировать numpy

import numba as nb
import numpy as np
import time
import math
import random


@nb.njit(cache=True, fastmath=True)
def _3points_to_eq_of_plane(_3v3):
    v3_1 = _3v3[0]
    v3_2 = _3v3[1]
    v3_3 = _3v3[2]
    x1 = v3_1[0]
    y1 = v3_1[1]
    z1 = v3_1[2]
    x2 = v3_2[0]
    y2 = v3_2[1]
    z2 = v3_2[2]
    x3 = v3_3[0]
    y3 = v3_3[1]
    z3 = v3_3[2]
    vector1 = np.array([x2 - x1, y2 - y1, z2 - z1])
    vector2 = np.array([x3 - x1, y3 - y1, z3 - z1])

    cross_product = [vector1[1] * vector2[2] - vector1[2] * vector2[1],
                     -1 * (vector1[0] * vector2[2] - vector1[2] * vector2[0]),
                     vector1[0] * vector2[1] - vector1[1] * vector2[0]]

    a = cross_product[0]
    b = cross_product[1]
    c = cross_product[2]
    d = - (cross_product[0] * x1 + cross_product[1] * y1 + cross_product[2] * z1)
    return np.array([a, b, c, d])


@nb.njit(cache=True, fastmath=True)
def xyz_of_intersection_plane_and_line(a, b, c, d, x1, x2, y1, y2, z1, z2):
    x21 = (x2 - x1)
    y21 = (y2 - y1)
    z21 = (z2 - z1)
    zxy21_c = (z21 + x21) * c / y21
    y = (y1 * zxy21_c - z1 * c - d - x1 * a) / (zxy21_c + b)
    x = (y - y1) * x21 / y21 + x1
    z = (-d - a * x - b * y) / c
    return np.array([x, y, z])

@nb.njit(cache=True, fastmath=True)
def point_to_pix_on_rect(view_rect, v3, size_x, size_y):
    xsx = (view_rect[1][0] - view_rect[0][0]) / (size_x - 1)
    xsy = (view_rect[1][1] - view_rect[0][1]) / (size_x - 1)
    xsz = (view_rect[1][2] - view_rect[0][2]) / (size_x - 1)
    ysx = (view_rect[3][0] - view_rect[0][0]) / (size_y - 1)
    ysy = (view_rect[3][1] - view_rect[0][1]) / (size_y - 1)
    ysz = (view_rect[3][2] - view_rect[0][2]) / (size_y - 1)
    c1x = view_rect[0][0]
    c1y = view_rect[0][1]
    c1z = view_rect[0][2]
    x = v3[0]
    y = v3[1]
    z = v3[2]
    # Здесь система из 3 линейный уравнений с 2 неизвестными
    # Выбираем лучшие - самая большая разница координат для меньшей ошибки
    dx = abs(view_rect[2][0] - view_rect[0][0])
    dy = abs(view_rect[2][1] - view_rect[0][1])
    dz = abs(view_rect[2][2] - view_rect[0][2])
    if ysx == 0 and ysz == 0:
        i = (x - c1x) / xsx
        j = (y - c1y) / ysy
    elif ysy == 0 and ysz == 0:
        i = (x - c1x) / ysx
        j = (y - c1y) / xsx
    elif ysy == 0 and ysx == 0:
        i = (x - c1x) / ysz
        j = (y - c1y) / ysz
    elif min(dx, dy, dz) == dx:
        # i * xsx + j * ysx = x - c1x
        # i * xsy + j * ysy = y - c1y
        print(ysx)
        i = (y - c1y + x * ysy / ysx + c1x * ysy / ysx) / (xsy - xsx * ysy / ysx)
        j = (x - c1x - i * xsx) / ysx

    elif min(dx, dy, dz) == dy:
        # i * xsx + j * ysx = x - c1x
        # i * xsz + j * ysz = z - c1z

        i = (z - c1z + x * ysz / ysx + c1x * ysz / ysx) / (xsz - xsx * ysz / ysx)
        j = (x - c1x - i * xsx) / ysx

    elif min(dx, dy, dz) == dz:
        # i * xsz + j * ysz = z - c1z
        # i * xsy + j * ysy = y - c1y

        i = (y - c1y + z * ysy / ysz + c1z * ysy / ysz) / (xsy - xsz * ysy / ysz)
        j = (y - c1y - i * xsy) / ysy
    return np.array([i, j])

@nb.njit(cache=True, fastmath=True)
def rect_view_triangle_size_to_pix(rect, view, triangle, size_x, size_y):
    points_from_rect = np.zeros((3, 3))
    points_from_rect[0] = rect[0]
    points_from_rect[1] = rect[1]
    points_from_rect[2] = rect[2]
    plane = _3points_to_eq_of_plane(points_from_rect)
    a = plane[0]
    b = plane[1]
    c = plane[2]
    d = plane[3]
    v31 = triangle[0]
    v32 = triangle[1]
    v33 = triangle[2]
    x = view[0]
    y = view[1]
    z = view[2]
    x1 = v31[0]
    y1 = v31[1]
    z1 = v31[2]
    x2 = v32[0]
    y2 = v32[1]
    z2 = v32[2]
    x3 = v33[0]
    y3 = v33[1]
    z3 = v33[2]
    v31 = xyz_of_intersection_plane_and_line(a, b, c, d, x, x1, y, y1, z, z1)
    v32 = xyz_of_intersection_plane_and_line(a, b, c, d, x, x2, y, y2, z, z2)
    v33 = xyz_of_intersection_plane_and_line(a, b, c, d, x, x3, y, y3, z, z3)
    v1 = point_to_pix_on_rect(rect, v31, size_x, size_y)
    v2 = point_to_pix_on_rect(rect, v32, size_x, size_y)
    v3 = point_to_pix_on_rect(rect, v33, size_x, size_y)
    ret = np.zeros((3, 2))
    ret[0] = v1
    ret[1] = v2
    ret[2] = v3
    return ret


@nb.njit(cache=True, fastmath=True, parallel=True)
def get_triangles_on_screen(triangles, rect, size_x, size_y, x, y, z):
    view = np.zeros(3)
    view[0] = x
    view[1] = y
    view[2] = z
    lt = len(triangles)
    result = np.zeros((lt, 3, 2))
    for i in nb.prange(lt):
        result[i] = rect_view_triangle_size_to_pix(rect, view, triangles[i], size_x, size_y)
    return result

Остальное не покажу. картинка рендерится пол секунды 470000 полигонов. triangles - массив треугольников rect - прямоугольник size_x - ширина окна size_y - высота окна x, y, z - положение камеры

введите сюда описание изображения

→ Ссылка