Log In  

Cart #18677 | 2016-02-07 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA
9

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.

P#18678 2016-02-06 21:34 ( Edited 2016-02-23 18:37)

:: cap

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?

P#18692 2016-02-07 07:32 ( Edited 2016-02-07 12:32)

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. :-\

P#18699 2016-02-07 13:10 ( Edited 2016-02-07 18:10)
4

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.

Cart #18706 | 2016-02-07 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA
4

P#18707 2016-02-07 17:01 ( Edited 2016-02-07 22:01)
:: Pizza

It looks almost like Betrayal at Krondor. Your coding prowess is superb and I applaud you for your efforts.

P#18710 2016-02-07 17:54 ( Edited 2016-02-07 22:54)
:: solar

Reminding me a lot of Test Drive III for DOS

P#18726 2016-02-08 05:37 ( Edited 2016-02-08 10:37)
:: matt

reminds me of Virus! Great work

P#18787 2016-02-12 18:25 ( Edited 2016-02-12 23:25)
:: NuSan

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.

P#18941 2016-02-23 13:37 ( Edited 2016-02-23 18:37)

[Please log in to post a comment]

Follow Lexaloffle:        
Generated 2021-04-16 09:07 | 0.031s | 2097k | Q:43