This is a stepping stone to an overly-ambitious project.
I'm looking for a better way to sort a table of triangles--currently sorting speed for around 150 triangles is preventing me from having solid filled triangles.
Does anyone have a good quicksort implementation that could sort a list of triangles, where each triangle contains 3 points and a centroid "z" value?
triangle_list={}
function new_triangle(p1,p2,p3,z,color)
t={}
t.p1=p1
t.p2=p2
t.p3=p3
t.z=z
t.color=color
add(triangle_list,t)
end
function sort_by_z()
...
end
|
That said, I actually like the way that the wire-frame looks, and backface culling almost makes hills appear opaque.
this is really impressive!
i might be able to help w/ the quicksort but i'm not sure i understand how exactly the list needs to be sorted.
should the triangles be sorted by distance from a certain point?
You can do a little faster sorting if you are able to cache the triangles from one frame to the next. The sort order changes very little, then you can use insertion sort to get nearly O(n) sorting. Reusing the results from the last frame is the hard part though. :-\
If I am careful about the way I load the triangles from the map height field, I can get away with not sorting at all. Right now this means that I clamp the camera angle to be +/-45 degrees, which is definitely not the best way to approach this. As the camera angle changes, I could load the triangles in a different order, ie +z to -z vs. -z to +z...
I agree that the best way to do this would be to keep the triangles around from frame to frame. This would save me from doing ugly things like recalculating their colors every single time the camera moves more than 1 unit up or over.
Then the trouble is figuring out which new triangles to add and which ones to get rid of as you go forward or turn.
Alternatively, maybe I can use a ray-casting algorithm to find map squares from back to front for a given map location and angle. That doesn't seem especially straightforward either. Something to mull over.
I did get a pretty nifty shading effect going with alternating color strips for the surfaces. This provides a lo-fi dithered palate to use for flat shading.
It looks almost like Betrayal at Krondor. Your coding prowess is superb and I applaud you for your efforts.
I use a partial swap sort, where I can set the number of loop of sort per frame. But you obviously have to keep triangle around.
function sorttrisloop(t,n) local tv = #t-1 for j=1,n do for i=1,tv do if(t[i].z < t[i+1].z) then t[i],t[i+1] = t[i+1],t[i] end end end end |
The first frame, or when the camera switch, I do a full sort.
[Please log in to post a comment]
