So now we have a working camera, we can move around and look at objects that are moving independently from us. There are two obvious issues remaining though, firstly, no matter which direction we look at the cubes the same one is always drawn in front. The other is corruption when we walk into them. I’m going to fix the first one now.
This uses something called the Painter’s Algorithm. It’s a very descriptive name, and it is exactly what it sounds like. We draw the furthest away objects first, and then successively “paint” over each with closer and closer objects.
As always, click here to give it a try, and here to download it. Here are the previous posts:
The first thing we need to do is keep hold of the depth of the vertex when projecting it. I have added a z field to the table that is being returned.
function project(v)
return {
x=flr((v.x/v.z+1)/2*128),
y=flr((v.y/v.z+1)/2*128),
z=v.z,
u=v.u,
v=v.v
}
end
This following function is an implementation of insertion sort. In this algorithm we build up the sorted list element by element in place. This is essentially how people often sort a hand of cards.
There is an outer loop which starts from the second element, and goes to the end of the table. The second element, because a list of size 1 is inherently sorted. The first element is already in place at this point. There is then an inner loop walking backwards from the current position looking for the point to insert the element we are comparing with. With each step we look to see if the item we have should be inserted here, if not then we swap the one we are comparing with its neighbour. Once we have found the item’s place, or we have reached the first element then we insert it.
Insertion sort is slower than quick sort when comparing with big O notation. However we are dealing with a very small data set here, and the overhead of the recursion in quick sort I suspect means that it would actually run slower in practice. I have not tested this, but insertion sort is very simple and will do for now.
--insertion sort
function sort(tbl,cmp)
for i=2,#tbl do
local key=tbl[i]
local j=i-1
while j>=1
and cmp(tbl[j],key) do
tbl[j+1]=tbl[j]
j-=1
end
tbl[j+1]=key
end
end
Inside the _draw function we have a new table called lst used to keep track
of all the triangles with their projected vertices.
local lst={}
Previously at the end of the loop through each cube I was then calling
draw_tri for each of the projected triangles in that cube. Now instead I am
adding the triangles to the end of the draw list table.
Along with the triangle’s projected points I am storing the sum of the depth values for each of the points. If I divide this value by three it becomes the average depth of the triangle. I don’t actually need to do this for the sorting however, the total depth of each point works just as well.
I also moved the culling implementation out of the draw_tri function to here.
This is a tiny optimisation, since it means we never need to sort the triangles
that we already know will not be drawn.
--build the list of triangles
--to draw with their projected
--points, and the sum of their
--depth
for t in all(tris) do
local a=proj[t[1]]
local b=proj[t[2]]
local c=proj[t[3]]
local f=front(a,b,c)
local cull=(f and cull.front)
or (not f and cull.back)
if not cull then
local z=a.z+b.z+c.z
add(lst,{a,b,c,z=z})
end
end
Then at the end of _draw I use the previously defined sorting function. I went back and forth on whether the comparison function should be a lambda as I have written it here, or whether the function should just assume that its argument has a z field. I’ve gone with the lambda as it feels more reusable in a software engineering sense, but I think it’s probably silly in a Pico 8 project. Since the code has to stay small, I could have just made that change if I ever needed it.
--sort by the depth of the
--triangles
sort(lst,function (a,b)
return a.z<b.z
end)
I then iterate through the sorted draw list, rendering each triangle from the furthest out to the closest.
for t in all(lst) do
draw_tri(t[1],t[2],t[3])
end
This leaves the corruption when you walk into the cubes for the next post.