i''m currently working on an algorithm that will split a large 2D grid of points into smaller 2d grids. the main grid will always have an odd number of points along the x and y axis, with 3 being the minimum number on both sides. the grids it is split into are always 3x3, and will share the edges of the surrounding grids, i.e. 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 will be split into 0---1---2 2---3---4 | | | | | | 5---6---7 7---8---9 | | | | | | 10--11--12 12--13--14 10--11--12 12--13--14 | | | | | | 15--16--17 17--18--19 | | | | | | 20--21--22 22--23--24 the number of 3x3 grids required can be calculated using the formulas: GridNumX = (Width - 1) / 2 GridNumY = (Height - 1) / 2 and from that the total number of grids is GridNumX * GridNumY (obviously). the problem that i''m having is converting BigGrid[x][y] into SmallGrid[x1][y1].Points[x2][y2]. all i''ve managed to work out is that any point where the X or Y value is even (counting from zero btw) will end up being shared with another grid, and those 2 grids can be calcuated by X/2 and (X/2)-1 (and the same for the Y axis). Now, does anyone know of a quick way of putting this into c? i''ve tried for hours but it refuses to work. thanks in advance

They key to doing this is understanding the relationship between absolute X coordinates and our value equivalents.

Let's graph our "X-coordinate line":
0 1 2 3 4 5 6 7 8

Basically, just the set of all integers from 0 to 8. Now, let's graph our actually grid values on a line:
0 1 2 2 3 4 4 5 6

That represents our values for the given X coordinates (assuming top row).

Together now:
0 1 2 3 4 5 6 7 8
0 1 2 2 3 4 4 5 6

Increase our number line a little bit:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
0 1 2 2 3 4 4 5 6 6 7 8 8 9 10 10 11

A little more:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
0 1 2 2 3 4 4 5 6 6 7 8 8 9 10 10 11 12 12 13 14 14 15

A pattern begins to form. As our number lines grow, we gradudually build up a "deficiency" with the bottom line in relation to the top one, as we are duplicating every other value. This dificiency can be described as a function of X, or any value in the top number line:

int((X - 1) / 3) + 0

+ 0 means we are adding the starting value of our bottom value line.

This deficit function only holds true for all values of X that don't correspond to the second value in a pair. For example, the X value of 6 corresponds to 4 on the value line, but via our equation, the calculated deficit is 1, when it should be 2. This is actually a useful side effect, because in essense, any given row won't end in double values, so we can use this for finding suitable starting values.

Thus, for any value of X, we can find it's true correspondant value by subtracting the deficiency from the X:

True Value Function
X - int((X - 1) / 3) + 0

(Once again, + 0 means adding the start value)

So, for any value of X, we subtract int((X - 1) / 3) to find the corresponding value.

Now, this was only for the top row. As we move on to other rows, the numbers don't start at 0 anymore - our X coordinates do, but not the real values. We have do use the Y coordinate to find an appropiate starting value for our value line. Now, our starting values also suffer from "deficiency" as well. Thus we must also use the same logic we used for X values with our Y values. Our scale is different however, because our starting values increase by a number besides 1. We plug in the Width of each row into our "true value function" to find the number by which they increase.

Take a look:

0 0
1 5
2 10
3 10
4 15
5 20
6 20
7 25
8 30
9 30
10 35
11 40
12 40
13 45


Now, imagine factoring out a 5 for each value. Then, our number lines would look identical to those used in the initial observations. The same equation can be used to find the base deficiency:

int((Y - 1) / 3)


However, when we finally do find our value, we have to remember that we factored out a 5, and it needs to be remultiplied into the equation. In the end, we have this:

5Y - 5*int((Y - 1) / 3)

(Starting value is assumed to be 0).

To recap. We use the Y value to find a suitable starting value for our value line. We use the X value in our final equation to find the appropiate value. In the end, these are our final equations:

X - int((X - 1) / 3) + (Width - int((Width - 1) / 3))*Y - (Width - int((Width - 1) / 3))*int((Y - 1) / 3)

Yes, you can crucify me now But let me plug in an example, just so you don't think I'm crazy!

Let's use your graph:

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

The width of this big grid is 6. Let's take coordinate (4,2) -> 13. Plug it into our huge bitch-o-quation ->

4 - int(3 / 3) + (6 - int(5 / 3))*2 - (6 - int(5 / 3))*int(1 / 3)
4 - 1 + 10 - 0
13


So, it works You can optimize that for computer code by factoring out (Width - int((Width - 1) / 3)) and simplifying as much as possible.

[edited by - Zipster on October 11, 2002 2:43:39 AM]

zipster: thanks for the reply, but i managed to work it out another way this morning (i posted that at about 3 in the morning my time!). My method is this:




now all i gotta do is try and simplify it a bit. Also, there's not a divide in sight .

Thankfully the smaller grids will always be 3x3 and the larger grid will always have an odd number of rows and columns, otherwise it would make life MUCH harder (read: impossible).

Of course, if you can see anything that can be factored out it would be nice...

hmmm... i see the forum screwed up my original diagrams nicely!

[edited by - MENTAL on October 11, 2002 10:30:30 AM]

Your method retrives the linear offset into the bigger grid based on the smaller grid coordinates and local coordinates. Mine is a bit different. It actually assumes that the first number in the upper left is 0 (or any other starting number), and that every other value is duplicated. You then enter the global X and Y coordinates and the equation returns the actual value at the coordinate.

But I suppose if what you have is what you needed, then great!

yeah, it made sense to do it that way as i''m filling the smaller grids with the values as they''re being processed and tesselated (yes, it''s for curved surfaces).

again, thanks for the response though. i''m gonna bookmark it for future use!