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, building a sorted section on the left hand side by moving a card from the right into its correct position.
There is an outer loop which starts from the second element, and walks right until it reaches the end of the list. We start at the second element because a list of size 1 is inherently sorted. There is then an inner loop that slides the item we are currently sorting left step by step until it is in its correct position.
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. Out of habit I’ve used a lambda here, rather than just having the function assume that its argument has a z field. The lambda means that the function is more reusable for other data types down the line, which is normally a perfectly sensible programming approach. It just seems silly here in a Pico 8 project though, as the project will always be small enough that I can just make that change if I ever found it to be useful.
--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 fixes the more distant cube being drawn over the nearer one, but leaves the corruption when you walk into the cubes for the next post.