Archived

This topic is now archived and is closed to further replies.

_DarkWIng_

ever/optimal distribution

Recommended Posts

_DarkWIng_    602
Another problem for you. I have patch of terrain lets say size of 17x17 and I to trace a ray from camera to each of it''s vertices. (5x5 verison) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 patch size is n*n where n = 2^k+1 (k = [1..6]) I have a function that treturns true if vertice is visible and false if it''s not. And if any of those is visible patch is renderd (early out). Now I need to find some order to check vertices so there will be more early outs. Something like ever distribution. in 5x5 case: 12 (center point), 0, 4, 20, 24 (corners), 2, 10, 14, 22 (edge midpints), .... OK, I could hardcode those values for 5x5 array but since array can be much bigger I''m not gonna do it. I need some function that calculates them. Any Idea? You should never let your fears become the boundaries of your dreams.

Share this post


Link to post
Share on other sites
Cedric    158
I am not sure how to deal with terrain patches, or how to solve your problem as a whole, but your specific question is quite simple.

Let N be the number of elements in the array (25 for a 5 x 5 matrix), and n the size of the side of your matrix (5 in this case)

If N is odd, then

center = (N - 1) / 2
corners = {0, n-1, N-1, N-n}
edge midpoints = {(n-1) / 2, (N - 1) / 2 - (n-1) / 2, (N - 1) / 2 + (n-1) / 2, N - (n+1) / 2}

Is this what you were asking for?

Cédric

Share this post


Link to post
Share on other sites
_DarkWIng_    602
cedricl : that''s a start... but I need to order all(25) vertices in this way.. so how to continue?

You should never let your fears become the boundaries of your dreams.

Share this post


Link to post
Share on other sites
Cedric    158
Ok. I think that trying to order all 25 vertices this way is going to be complicated. You could try something like:

{0, 4, 8, 12, 16, 20, 24}
{2, 6, 10, 14, 18, 22}
{1, 5, 9, 13, 17, 21}
{3, 7, 11, 15, 19, 23}

Here, I chose 4 as the base multiple, but you could choose 8, and try successively {8m, 4 + 8m, 2 + 8m, 6 + 8m, 3 + 8m, 7 + 8m, 1 + 8m, 5 + 8m} where m is an integer incremented until 8m > N.

The multiple could be 2^k, so that larger matrices will have a larger multiple.

I think that shell sort uses the same technique to speed up sorting. You could take look at it.

Cédric

[edited by - cedricl on April 30, 2002 10:37:07 AM]

Share this post


Link to post
Share on other sites