Archived

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

_DarkWIng_

ever/optimal distribution

Recommended Posts

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
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
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