python - Depth issue with 3D graphics

Question

I copied a code off YouTube recently, about 3d graphics in Python without the use of 3D modules, like OpenGL. The video worked with only cubes, so I tried adding a tetrahedron to the shapes, and things started popping up where they weren't supposed to. The code is as follows:

import pygame, sys, math, random

def rotate2d(pos, rad): x,y=pos; s,c = math.sin(rad),math.cos(rad); return x*c-y*s,y*c+x*s

class Cam:
    def __init__(self, pos=(0,0,0),rot=(0,0)):
        self.pos = list(pos)
        self.rot = list(rot)

    def events(self, event):
        if event.type == pygame.MOUSEMOTION:
            x, y = event.rel; x/=200; y/=200
            self.rot[0]+=y; self.rot[1]+=x

    def update(self, dt, key):
        s = dt*10

        if key[pygame.K_q]: self.pos[1]+=s
        if key[pygame.K_e]: self.pos[1]-=s

        x,y = s*math.sin(self.rot[1]),s*math.cos(self.rot[1])
        if key[pygame.K_w]: self.pos[0]+=x; self.pos[2]+=y
        if key[pygame.K_s]: self.pos[0]-=x; self.pos[2]-=y
        if key[pygame.K_a]: self.pos[0]-=y; self.pos[2]+=x
        if key[pygame.K_d]: self.pos[0]+=y; self.pos[2]-=x
        if key[pygame.K_r]: self.pos[0]=0; self.pos[1]=0;
                                         self.pos[2]=-5; self.rot[0]=0; self.rot[1]=0


class Cube:
    faces = (0,1,2,3),(4,5,6,7),(0,1,5,4),(2,3,7,6),(0,3,7,4),(1,2,6,5)
    colors = (255,0,0),(255,128,0),(255,255,0),(255,255,255),(0,0,255),(0,255,0)
    def __init__(self,pos=(0,0,0),v0=(-1,-1,-1),v1=(1,-1,-1),v2=(1,1,-1),v3=(-1,1,-1),v4=(-1,-1,1),v5=(1,-1,1),v6=(1,1,1),v7=(-1,1,1)):
        self.vertices = (v0,v1,v2,v3,v4,v5,v6,v7)
        x,y,z = pos
        self.verts = [(x+X/2,y+Y/2,z+Z/2) for X,Y,Z in self.vertices]

class Tetrahedron:
    faces = (1,2,3),(0,1,2),(0,1,3),(0,2,3)
    colors = (255,0,0),(255,128,0),(255,255,0),(255,255,255)
    def __init__(self,pos=(0,0,0),v0=(0,0,.866),v1=(-.866,-1,-1),v2=(-.866,1,-1),v3=(.866,0,-1)):
        self.vertices = (v0,v1,v2,v3)
        x,y,z = pos
        self.verts = [(x+X/2,y+Y/2,z+Z/2) for X,Y,Z in self.vertices]

pygame.init()
w,h = 400,400; cx,cy = w//2, h//2
screen = pygame.display.set_mode((w,h))
clock = pygame.time.Clock()
cam = Cam((0,0,-5))
pygame.event.get(); pygame.mouse.get_rel()
pygame.mouse.set_visible(0); pygame.event.set_grab(1)

objects = [Cube((0,0,0)),Cube((0,0,2)),Tetrahedron((0,0,1))]

while True:
    dt = clock.tick()/1000

    for event in pygame.event.get():
        if event.type == pygame.QUIT: pygame.quit(); sys.exit()
        if event.type == pygame.KEYDOWN:
            if event.key == pygame.K_ESCAPE: pygame.quit(); sys.exit()
        cam.events(event)

    screen.fill((0,0,0))

    face_list = []; face_color = []; depth = []

    for obj in objects:

        vert_list = []; screen_coords = []
        for x,y,z in obj.verts:
            x-=cam.pos[0]; y-=cam.pos[1];z-=cam.pos[2]
            x,z=rotate2d((x,z),cam.rot[1])
            y,z = rotate2d((y,z),cam.rot[0])
            vert_list += [(x,y,z)]

            f = 200/z
            x,y = x*f,y*f
            screen_coords+=[(cx+int(x),cy+int(y))]

        for f in range(len(obj.faces)):
            face = obj.faces[f]

            on_screen = False
            for i in face:
                x,y = screen_coords[i]
                if vert_list[i][2]>0 and x>0 and x<w and y>0 and y<h: on_screen = True; break

            if on_screen:
                coords = [screen_coords[i] for i in face]
                face_list += [coords]
                face_color += [obj.colors[f]]
                depth += [sum(sum(vert_list[j][i] for j in face)**2 for i in range(3))]

    order = sorted(range(len(face_list)),key=lambda i:depth[i],reverse=1)

    for i in order:
        try: pygame.draw.polygon(screen,face_color[i],face_list[i])
        except: pass

    key = pygame.key.get_pressed()
    pygame.display.flip()
    cam.update(dt,key)

My problem is that the tetrahedron part is showing up through the cubes on either side, when the cam.pos is at least 7.5 away from the object:

As you can see, the tetrahedron is supposed to be buried under the cube, but it's still showing up. Can someone please suggest an edit to the code which will stop the tetrahedron from showing up through any objects?

Answer 1

What you actually try to do is to sort the faces by the square of the Euclidean distance to the vertices of the face.

But sum(vert_list[j][i] for j in face)**2 does not compute the square of the euclidean distance. It computes the square of the sum of the components of a coordinate. The square of the euclidean distance is

vert_list[j][0]**2 + vert_list[j][1]**2 + vert_list[j][2]**2 

That is not the same as

(vert_list[j][0] + vert_list[j][1] + vert_list[j][2])**2

Furthermore you do not take into account the number of vertices of a face, because the squared distances are summed.
Note, the faces of the cube are quads and have 4 vertices, but the faces of the tetrahedron are triangles and have 3 vertices.

Correct the computation of the squared distance and divide by the number of vertices, to solve the issue:

depth += [sum(sum(vert_list[j][i] for j in face)**2 for i in range(3))]

depth += [sum(sum(vert_list[j][i]**2 for i in range(3)) for j in face) / len(face)]

But note, if faces are close to another there still may occur an issue (e.g. covering faces in the same plane). That is not an exact algorithm. It is not designed for "touching" objects.