Z-Sorting Problems (Fixed!)

[dewgstrom]

Long time lurker, first time poster, hooray!

I'm working on an isometric 3D kind of thing and I'm using L2D because I really want to get into the guts of my rendering, so it seems like a good choice.

Right now I'm having kind of a major problem with z-sorting of triangles. Everything loads in and renders properly, except when multiple triangles share a common average z value, like so:



If no matching z values are found, like if the entire set is rotated from 2-44 degrees or if I offset the whole thing a teensy tiny bit right from the start so that it's .1 degree off the whole axis:



On some small level that kind of works for now, but I'm trying to avoid the whole problem down the line, since I expect I'm going to have a lot more and more complex geometry in the final thing than this test map does. Here's where I'm running into a problem:

Code: Select all

function zSortTriangles(object3D)
	local sortedTable = {}
	local pairsTable = {}
	local zValueTable = {}
	
	for i, tri in ipairs(object3D) do
		local averageZ = 0
		for _,vert in ipairs(tri) do
			averageZ = averageZ + vert[3]	
		end
		averageZ = averageZ / 3
		if not pairsTable[averageZ] == nil then
			table.insert(zValueTable,averageZ)
			table.insert(pairsTable[averageZ],tri)
		else
			pairsTable[averageZ] = {}
			table.insert(zValueTable,averageZ)
			table.insert(pairsTable[averageZ],tri)
		end
	end

	table.sort(zValueTable)

	for i, val in ipairs(zValueTable) do
		for i, tri in ipairs(pairsTable[val]) do
			table.insert(sortedTable,tri)
		end
	end

	return sortedTable
end

(Sorry if my code's kind of kludgy. Self taught!)

An object composed of un-ordered triangles is passed in, an object of the triangles sorted with the furthest back triangles first is passed out, and then each vertice of the set is broken down into something that can be handled by Mesh:setVertices() (A later step in code strips out the Z value from each vertex to fit the proper xy/uv/rgba format for a mesh.)

The problem seems to be with how I'm handling redundant results for the "averageZ" calculation for every triangle. It seems logical to use the result as an index, then sort those indices over a table and iterate it back, but there's something screwy with the results any time that actually happens.

The Mesh mode is set to ''triangles' too, so rendering order shouldn't matter, but my vertices are clearly getting screwed up somehow by this function and I have no idea what's causing them to get so jumbled.

Is there anything obvious in my code that I goofed?

[dewgstrom]

Also: Here's the full .love for context. I put just the function that I think is causing problems in the OP to not weigh things down too much.

[Sulunia]

print.png (6.51 KiB) Viewed 8234 times

You should fix your .love file!

[dewgstrom]

Good catch! However that image is never called right now, which is why I removed it from the .love. Commenting out line 326 "testBG = love.graphics.newImage('assets/testBG.png')" will also fix it.

[dewgstrom]

Here's a fresh copy of the .love, plus an interesting screenshot.



I edited a few lines to set the RGB value to be equal to the "z" component instead of the texture or lighting, meaning they should come out as greyscale, but my glitched tris show up blue here, if not totally blank. This tells me something's going wrong with the vertex order, but in looking at my code I'm still not sure what.

EDIT: To add some more detail, here's a GIF of the problem in action: https://gfycat.com/QualifiedShrillBunny

If you download the .love you can rotate the "map" using the left and right keys, and the "started" variable is a little bit of a hack to show the bugfix I came up with. If started == true at the beginning of the file, the glitch will be present, if started == false then the first love.update() offsets the entire set by .001 degrees, which stops the problem entirely for this smaller map since all other rotations are +/- 1.0 exactly.

[dewgstrom]

Sorry on the double post, but I fixed it! The problem was in how I was doing my organization of redundant Z results.



Here's the new code:

Code: Select all

function zSortTriangles(object3D)
	local sortedTable = {}
	local pairsTable = {}
	local zValueTable = {}
	local redundancyCheck = {}
	
	for i, tri in ipairs(object3D) do
		local averageZ = 0
		for _,vert in ipairs(tri) do
			averageZ = averageZ + vert[3]	
		end
		averageZ = averageZ / 3

		if not redundancyCheck[averageZ] then
			pairsTable[averageZ] = {}
			table.insert(pairsTable[averageZ],tri)
			table.insert(zValueTable,averageZ)
			redundancyCheck[averageZ] = true
		else
			table.insert(pairsTable[averageZ],tri)
		end
	end
	
	table.sort(zValueTable)

	for i, val in ipairs(zValueTable) do
		for i, tri in ipairs(pairsTable[val]) do
			table.insert(sortedTable,tri)
		end
	end

	return sortedTable
end

Having multiple copies of the same "Z" result in the "zValueTable" that I was sorting by looks like it was the problem, so I added a redundancy check to ensure that not only is there only a single results table for each Z value, but also to make sure that once sorted that Z value table is never sorted out more than once.

Might be useful information for someone else sometime down the line, so I figured I'd reply instead of just editing, though this is resolved now I suppose.

Edit: Even better fix thanks to Lowen from the Something Awful forums that skips the need for the redundancy table. I feel like I tried this at one point and broke my code, but it seems to work now, so whatever!

Code: Select all

if pairsTable[averageZ] == nil then
	pairsTable[averageZ] = {}
	table.insert(zValueTable,averageZ)
end
table.insert(pairsTable[averageZ],tri)

[Sulunia]

Nice 3D, it looks pretty smooth. A full game using this would look rad o.o

[therektafire]

got a copy of the fixed love file?

[dewgstrom]

Nice 3D, it looks pretty smooth. A full game using this would look rad o.o

Thanks! The actual game behind it still needs some major design work, but I'm trying to get a feel for the limitations I have right now. Thanks to L2D it turns out those limits are basically ones I'm gonna have to set myself.

got a copy of the fixed love file?

You got it! My working code has changed pretty drastically since I posted this thanks to adding new features (and is nowhere near the point where I'd start distributing it, haha, it's some ugly code) but here's a copy of the one from this thread with the fix applied:

3DMap_3.love

(9.31 KiB) Downloaded 194 times

Here's a couple of screenshots of my current progress, though a lot of the guts to this is really kludgy and poorly documented right now, haha:


(That's a mesh (this mesh in fact) exported from Blender with a custom script, if you want to get a feel for how nuts I'm going with this. )