Folding a selection of points on a 3D cube

Question

I am trying to find an effective algorithm for the following 3D Cube Selection problem:

Imagine a 2D array of Points (lets make it square of size x size) and call it a side.

For ease of calculations lets declare max as size-1 Create a Cube of six sides, keeping 0,0 at the lower left hand side and max,max at top right. Using z to track the side a single cube is located, y as up and x as right

public class Point3D {
    public int x,y,z;

    public Point3D(){}
    public Point3D(int X, int Y, int Z) {
        x = X;
        y = Y;
        z = Z;
    }
}

Point3D[,,] CreateCube(int size)
{
    Point3D[,,] Cube = new Point3D[6, size, size];
    for(int z=0;z<6;z++)
    {           
        for(int y=0;y<size;y++)
        {
            for(int x=0;x<size;x++)
            {
                Cube[z,y,x] = new Point3D(x,y,z);
            }
        }
    }
    return Cube;
}

Now to select a random single point, we can just use three random numbers such that:

Point3D point = new Point(
Random(0,size), // 0 and max
Random(0,size), // 0 and max
Random(0,6));   // 0 and 5

To select a plus we could detect if a given direction would fit inside the current side. Otherwise we find the cube located on the side touching the center point.

Using 4 functions with something like:

private T GetUpFrom<T>(T[,,] dataSet, Point3D point) where T : class {
    if(point.y < max)
        return dataSet[point.z, point.y + 1, point.x];
    else {
        switch(point.z) {
            case 0: return dataSet[1, point.x, max];      // x+
            case 1: return dataSet[5, max, max - point.x];// y+
            case 2: return dataSet[1, 0, point.x];        // z+
            case 3: return dataSet[1, max - point.x, 0];  // x-
            case 4: return dataSet[2, max, point.x];      // y-
            case 5: return dataSet[1, max, max - point.x];// z-
        }
    }
    return null;
}

Now I would like to find a way to select arbitrary shapes (like predefined random blobs) at a random point. But would settle for adjusting it to either a Square or jagged Circle.

The actual surface area would be warped and folded onto itself on corners, which is fine and does not need compensating ( imagine putting a sticker on the corner on a cube, if the corner matches the center of the sticker one fourth of the sticker would need to be removed for it to stick and fold on the corner). Again this is the desired effect.

No duplicate selections are allowed, thus cubes that would be selected twice would need to be filtered somehow (or calculated in such a way that duplicates do not occur). Which could be a simple as using a HashSet or a List and using a helper function to check if the entry is unique (which is fine as selections will always be far below 1000 cubes max).

The delegate for this function in the class containing the Sides of the Cube looks like: delegate T[] SelectShape(Point3D point, int size);

Currently I'm thinking of checking each side of the Cube to see which part of the selection is located on that side.

Calculating which part of the selection is on the same side of the selected Point3D, would be trivial as we don't need to translate the positions, just the boundary. Next would be 5 translations, followed by checking the other 5 sides to see if part of the selected area is on that side.

I'm getting rusty in solving problems like this, so was wondering if anyone has a better solution for this problem.

@arghbleargh Requested a further explanation:

We will use a Cube of 6 sides and use a size of 16. Each side is 16x16 points. Stored as a three dimensional array I used z for side, y, x such that the array would be initiated with: new Point3D[z, y, x], it would work almost identical for jagged arrays, which are serializable by default (so that would be nice too) [z][y][x] but would require seperate initialization of each subarray.

Let's select a square with the size of 5x5, centered around a selected point. To find such a 5x5 square substract and add 2 to the axis in question: x-2 to x+2 and y-2 to y+2.

Randomly selectubg a side, the point we select is z = 0 (the x+ side of the Cube), y = 6, x = 6.

Both 6-2 and 6+2 are well within the limits of 16 x 16 array of the side and easy to select.

Shifting the selection point to x=0 and y=6 however would prove a little more challenging. As x - 2 would require a look up of the side to the left of the side we selected. Luckily we selected side 0 or x+, because as long as we are not on the top or bottom side and not going to the top or bottom side of the cube, all axis are x+ = right, y+ = up. So to get the coordinates on the side to the left would only require a subtraction of max (size - 1) - x. Remember size = 16, max = 15, x = 0-2 = -2, max - x = 13. The subsection on this side would thus be x = 13 to 15, y = 4 to 8. Adding this to the part we could select on the original side would give the entire selection.

Shifting the selection to 0,6 would prove more complicated, as now we cannot hide behind the safety of knowing all axis align easily. Some rotation might be required. There are only 4 possible translations, so it is still manageable.

Shifting to 0,0 is where the problems really start to appear. As now both left and down require to wrap around to other sides. Further more, as even the subdivided part would have an area fall outside. The only salve on this wound is that we do not care about the overlapping parts of the selection. So we can either skip them when possible or filter them from the results later.

Now that we move from a 'normal axis' side to the bottom one, we would need to rotate and match the correct coordinates so that the points wrap around the edge correctly.

As the axis of each side are folded in a cube, some axis might need to flip or rotate to select the right points.

The question remains if there are better solutions available of selecting all points on a cube which are inside an area. Perhaps I could give each side a translation matrix and test coordinates in world space?

Answer 1

Found a pretty good solution that requires little effort to implement.

Create a storage for a Hollow Cube with a size of n + 2, where n is the size of the cube contained in the data. This satisfies the : sides are touching but do not overlap or share certain points.

This will simplify calculations and translations by creating a lookup array that uses Cartesian coordinates. With a single translation function to take the coordinates of a selected point, get the 'world position'.

Using that function we can store each point into the cartesian lookup array.

When selecting a point, we can again use the same function (or use stored data) and subtract (to get AA or min position) and add (to get BB or max position).

Then we can just lookup each entry between the AA.xyz and BB.xyz coordinates. Each null entry should be skipped.

Optimize if required by using a type of array that return null if z is not 0 or size-1 and thus does not need to store null references of the 'hollow cube' in the middle.

Now that the cube can select 3D cubes, the other shapes are trivial, given a 3D point, define a 3D shape and test each part in the shape with the lookup array, if not null add it to selection. Each point is only selected once as we only check each position once.

A little calculation overhead due to testing against the empty inside and outside of the cube, but array access is so fast that this solution is fine for my current project.