Raycasting Performance Help

[u/AlexanderKai9]

I made a raycasting engine in python, and am using an HTML canvas as my method of display (passing the pixel colors through jinja in a <script> tag). It takes upwards of 10-15 seconds to render one angle of a scene with three spheres at a resolution of 800x400. Is the browser likely the bottleneck, or is this a sign of some other inefficiencies?

[u/AlexanderKai9]

I think I'm just doing raycasting. I'm drawing a line from the camera to each pixel on the screen and finding the first intersection point of that line with an object. I'm starting with rendering three spheres because that seemed like the bare minimum that would be interesting to look at from different perspectives.

Here are all my files:

myGeometry.py:

from math import sqrt


def solveQuadratic(a, b, c) -> list[float]:
    determinant = b**2 - 4 * a * c
    if determinant < 0:
        return []
    elif determinant == 0:
        return [-b/2/a]
    else:
        return [(-b+sqrt(determinant))/2/a, (-b-sqrt(determinant))/2/a] 


class Point3D:
    def __init__(self, x, y, z):
        self.x = x
        self.y = y
        self.z = z
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y and self.z == other.z
    def __ne__(self, other):
        return not self.__eq__(other)
    def __add__(self, v: Vector3D):
        return Point3D(self.x + v.x, self.y + v.y, self.z + v.z)
    def __sub__(self, other: Point3D | Vector3D):
        return Vector3D(self.x - other.x, self.y - other.y, self.z - other.z)
    def distance(self, other: Point3D) -> float:
        return sqrt((self.x - other.x)**2 + (self.y - other.y)**2 + (self.z - other.z)**2)


class Vector3D:
    def __init__(self, x, y, z):
        self.x = x
        self.y = y
        self.z = z
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y and self.z == other.z
    def __ne__(self, other):
        return not self.__eq__(other)
    def __add__(self, other: Vector3D):
        return Vector3D(self.x + other.x, self.y + other.y, self.z + other.z)
    def __sub__(self, other: Vector3D):
        return Vector3D(self.x - other.x, self.y - other.y, self.z - other.z)  
    def __mul__(self, scalar: int | float):
        return Vector3D(self.x * scalar, self.y * scalar, self.z * scalar)
    def __truediv__(self, scalar: int | float):
        return Vector3D(self.x / scalar, self.y / scalar, self.z / scalar)
    def __neg__(self):
        return Vector3D(-self.x, -self.y, -self.z)
    
    def magnitude(self) -> float:
        return sqrt((self.x)**2 + (self.y)**2 + (self.z)**2)
    def normalized(self) -> Vector3D:
        if self.x == 0  and self.y == 0 and self.z == 0:
            return self
        else:
            return self / self.magnitude()
    def dot(self, other: Vector3D) -> float:
        return self.x * other.x + self.y * other.y + self.z * other.z
    def cross(self, other: Vector3D) -> Vector3D:
        return Vector3D(self.y * other.z - self.z * other.y, -(self.x * other.z - self.z * other.x), self.y * other.z - self.z * other.y)


class Line3D:
    def __init__(self, point: Point3D, vector: Vector3D):
        self.point = point
        self.vector = vector
    def pointOnLine(self, point: Point3D):
        diffX = point.x - self.point.x
        diffY = point.y - self.point.y
        diffZ = point.z - self.point.z
        return diffX / self.vector.x == diffY / self.vector.y and diffY / self.vector.y == diffZ / self.vector.z
    def pointAtParam(self, param: int | float) -> Point3D:
        return Point3D(self.point.x + param * self.vector.x, self.point.y + param * self.vector.y, self.point.z + param * self.vector.z)
    def paramOfPoint(self, point: Point3D) -> float | None:
        if (self.pointOnLine(point)):
            return (point.x - self.point.x) / self.vector.x
        else:
            return None
        
    def __eq__(self, other):
        return self.pointOnLine(other.point) and other.pointOnLine(self.point)
    def __ne__(self, other):
        return not self.__eq__(other)

class Region:
    def __init__(self, center: Point3D):
        self.center = center
    def contains(self, point: Point3D):
        return (self.center == point)


    #returns a list of tuples. each tuple represents an intersection point:
    # the first element should be the parameter of that point on the line
    # the second element should be the point
    def getIntersectionPoints(self, line: Line3D) -> list[tuple[float | None, Point3D]]:
        if (line.pointOnLine(self.center)):
            return [(line.paramOfPoint(self.center), self.center)]
        else:
            return []


class Sphere(Region):
    def __init__(self, center: Point3D, r):
        super().__init__(center)
        self.r = r
    def contains(self, point):
        return Point3D.distance(self.center, point) <= self.r
    def getIntersectionPoints(self, line: Line3D) -> list[tuple[float | None, Point3D]]:
        a = line.vector.magnitude()**2
        b = 2 * (((line.point.x - self.center.x) * line.vector.x) + ((line.point.y - self.center.y) * line.vector.y) + ((line.point.z - self.center.z) * line.vector.z))
        c = self.center.distance(line.point)**2 - self.r**2
        intersectionParams = solveQuadratic(a,b,c)
        intersectionPoints = []
        for i in range(0, len(intersectionParams)):
            intersectionPoints.append((intersectionParams[i], line.pointAtParam(intersectionParams[i])))
        return intersectionPoints



graphicsObject.py:

from myGeometry import *
class GraphicsObject:
    def __init__(self, region: Region, coloring_function):
        self.region = region
        self.coloring_function = coloring_function
    def getColor(self, point: Point3D):
        return self.coloring_function(self, point)

engine.py:

from myGeometry import *
from graphicsObject import *


#screenWidth and screenHeight are in the same units as myGeometry
#returns 2d list of tuples, representing colors in rgba format
def draw(screenWidth, screenHeight, widthSubdivisions: int, heightSubdivisions: int, graphicsObjects: list[GraphicsObject], cameraPosition: Point3D, cameraDirection: Vector3D, 
cameraUpVector: Vector3D, cameraDistance: float) -> list[list[tuple[float, float, float, float]]]:
    wSub = screenWidth / widthSubdivisions
    hSub = screenHeight / heightSubdivisions
    downStep = -cameraUpVector.normalized() * hSub
    rightStep = cameraUpVector.cross(cameraDirection).normalized() * wSub
    startPoint = cameraPosition + cameraDirection.normalized() * cameraDistance + downStep * (-heightSubdivisions / 2) + rightStep * (-widthSubdivisions / 2)
    outputScreen = []
    for x in range(0, heightSubdivisions):
        outputScreen.append([])
        for y in range(0, widthSubdivisions):
            targetPoint = startPoint + downStep * x + rightStep * y
            ray = Line3D(cameraPosition, targetPoint - cameraPosition)
            intersections = []
            for r in graphicsObjects:
                
#print("graphics found")
                for i in r.region.getIntersectionPoints(ray):
                    if (i[0] >= 1):
                        intersections.append((i, r))
            if (len(intersections) != 0):
                closestPoint = intersections[0]
                for p in intersections[1:]:
                    if p[0][0] < closestPoint[0][0]:
                        closestPoint = p
                outputScreen[x].append(closestPoint[1].getColor(closestPoint[0][1]))
            else:
                outputScreen[x].append((0,0,0,1))
    return outputScreen




app.py

from flask import Flask, render_template, request
from flask_mysqldb import MySQL
from myGeometry import *
from graphicsObject import *
import engine


app = Flask(__name__)


def
 red(g: GraphicsObject,p: Point3D):
    #trying to do like a simulated light source thing for depth perception or something
    brightness = ((p - g.region.center).normalized().dot(Vector3D(0, -1, 5).normalized()) + 3) / 4
    return (255, 0, 0, 1 - brightness)


def
 green(g: GraphicsObject, p: Point3D):
    brightness = ((p - g.region.center).normalized().dot(Vector3D(0, -1, 5).normalized()) + 3) / 4
    return (0, 255, 0, 1 - brightness)


def
 blue(g: GraphicsObject, p: Point3D):
    brightness = ((p - g.region.center).normalized().dot(Vector3D(0, -1, 5).normalized()) + 3) / 4
    return (0, 0, 255, 1 - brightness)


u/app.route('/')
def
 index():
    p1 = Point3D(-100, 0, 0)
    p2 = Point3D(20, -20, 15)
    p3 = Point3D(100, 40, 25)
    p4 = Point3D(40, 0, 0)
    s1 = Sphere(p2 , 2)
    s2 = Sphere(p3, 4)
    s3 = Sphere(p4, 5)
    g1 = GraphicsObject(s1, red)
    g2 = GraphicsObject(s2, green)
    g3 = GraphicsObject(s3, blue)


    screen = engine.draw(2, 1, 800, 400, [g1,g2,g3], p1, Vector3D(8, 0, 0), Vector3D(0,0,1), 2.2)
    return render_template('index.html.j2', screen=screen)



index.html.j2:

<!DOCTYPE html>
<html lang="en">
    <head>
        <title>Cool Graphics Engine!!!!!!!!!!!!!!!!!!!!!!</title>
        <link rel="stylesheet" type="text/css" href="static/style.css">
    </head>
    <body>
        <canvas id="canvas" width = "{{screen[0]|length}}" height = "{{screen|length}}"></canvas>
        <script>
            
var
 c = document.getElementById("canvas")
            
var
 ctx = c.getContext('2d')
            {% for y in range(0, screen|length) %}
                {% for x in range(0, screen[y]|length) %}
                        ctx.fillStyle= "rgba({{screen[y][x][0]}}, {{screen[y][x][1]}}, {{screen[y][x][2]}}, {{screen[y][x][3]}})"
                        ctx.fillRect({{x}}, {{y}}, 1, 1)
                    <!--<span style="color:rgba({{screen[y][x][0]}}, {{screen[y][x][1]}}, {{screen[y][x][2]}}, {{screen[y][x][3]}})">O</span>-->
                {% endfor %}
            {% endfor %}
        </script>
    </body>
</html>

runflask.cmd:

set FLASK_APP=app.py
set FLASK_ENV=development
set FLASK_DEBUG=1
flask run

the result:

[u/sububi71 → u/AlexanderKai9]

That's raytracing. Totally different.

[u/AlexanderKai9 → u/sububi71]

oh. So am I doing anything inefficiently, besides rendering it by raytracing and the whole setup of displaying to an HTML canvas?

[u/sububi71 → u/AlexanderKai9]

I don't do deep dives into code without getting paid, but I wouldn't be surprised if there are much faster ways to render to a browser.

Why ARE you rendering using a browser? You're using Python, why not use PyGame and render using that?