Introduction
What It Is
The Rubik's Cube is a 3-D mechanical puzzle invented in 1974 by Hungarian sculptor and professor of architecture Erno Rubik. Originally called the "Magic Cube", Rubik cube won the German game of year special award for Best Puzzle that year.
In a classic Rubik's Cube, each of the six faces is covered by nine stickers, among six solid colors (traditionally darkblue, red, blue, orange, green, and yellow). A pivot mechanism enables each face to turn independently, thus mixing up the colours. For the puzzle to be solved, each face must be a solid colour.
What It Does
Solve rubic cube puzzle on computer systems.The image below shows the computer version:
Use directions to turn the cube face independently. Play and win.
How to Use It
Enjoy:).
All about Code (I will target this article in the form of Questions/Answers)
Note: The next six questions are very basic, one can skip them.
Q.What is the learning curve for fellow programmers ? What all technologies/algorithms are used?
One can learn how to cast 3D model on 2D surface (computer screen) accurately using only basic mathematics calculations. Code involves using perspective projection, hidden surface removal algorithms, linqs in .NET 3.5 framework, GDI+, lot of matrix computations.
Q.What is coordinate system ?
A method of representing points in a space of given dimensions by coordinates from origin.The image below shows 3 dimensional coordinate system,the axis X, Y, Z are perpendicular to each other. IMP: Z axis is perpendicular to screen.
Q.What is a point ?
A Point is a reference to position in 3D world, point is represented by x,y,z coordinate with respect to coordinate system.
Q. What are cubes ?
A three-dimensional shape with six square or rectangular sides formed by connecting 8 Points(each point connect to 3 other points) as shown below.
Q. What make up a Rubik cube ?
27 carefully placed cubes in 3D world make a larger cube called Rubik cube.
Q. What are the coordinates of a simple cube ?
As shown in the image below, the coordinates of a simple cube are in format POINTNUMBER(X,Y,Z)
1(0,1,1) ,2(1,1,1) ,3(1,0,1) ,4(0,0,1) ,5(0,1,0) ,6(1,1,0) ,7(1,0,0) ,8(0,0,0).
The image below shows the coordinate system where z axis is perpendicular to the computer screen, the next image is of cube formed by connecting 8 points, the next image is placement of 9 cubes forming the bottom layer of Rubik cube.
Image 1
Q. How to rotate a point in 3d coordinate system around X,Y,Z axis ?
Rotation of a point around z axis, there are three basic steps:
- Translate to center point around which to rotate, the code below translates point (x1,y1) to center point point.
double tempy1 = y1 - point.y;
double tempx1 = x1 - point.x;
- Rotate around center point, the code below rotates translated point (tempy1,tempx1) around z-axis using angle which is expressed in radians.
y = tempy1 * Math.Cos(rotationAngle.ZRadianAngle) -
tempx1 *Math.Sin(rotationAngle.ZRadianAngle);
x = tempx1 * Math.Cos(rotationAngle.ZRadianAngle) +
tempy1 * Math.Sin(rotationAngle.ZRadianAngle);
- Translate back to original points, as done below:
y1 = y1 + point.y;
x1 = x1 + point.x;
x1,y1 are final coordinates as a result of rotation around z axis. Slightly modify the above formula to make rotation about x,y axis possible.
Q.How to rotate a cube face around Z axis by 90 degrees ?
A Cube face has 9 cubes, meaning 72 points in space. Calculate the center point of face, apply rotation logic on all 72 points. :)
Q What is Camera, Camera Angles, Camera position, Viewer position ?
A camera is eye watching a Rubik cube in 3d space, Camera position is position of camera with respect to coordinate system, camera angles are angles of camera how it is tilted. Viewer position is position of viewer with respect to computer screen. Actually I did another POC understanding all camera related stuff. Here is the link for more information. Camera position, camera angles, viewer position are set carefully to give best shot. The below code shows the camera parameters, be careful when playing around with camera parameters, it can result in distorted rubikcube.
Point3D cameraPosition = new Point3D(-1, 90, 90, 140);
Angles angles = new Angles(0, 0, 0);
Point3D viewer = new Point3D(-1, 0, 0, 500);
rubikCube.draw(e.Graphics, cameraPosition, angles, viewer);
Q. What is the Role of Point3D Class ?
Point3D class represents points of coordinate system, store coordinates in x,y,z variables, index in Point3D constructor is reference to position in cube (for calculation purpose). See Image 1:
public Point3D(int index, double Xcoor, double Ycoor, double Zcoor);
Note: Variable x,y,z in Point3D class are initialized and are never changed in any operations, only used as reference for calculations.
Q.What operation are performed by Point3d class ?
- Calculate final location of
Point3D in 3d space when viewed from camera position, camera angles, store the final coordinates in Point3D x1,y1,z1. The image below shows matrix computations.
public void FullFinalTransformation(Point3D Camera, Angles Angle);
- Apply sequence of rotation to
POINT3D coordinate as a result of user actions, rotate the point around the center point (passed as parameter this is RUBIK CUBE CENTER POINT).
public void XYXRotation(Angles rotationAngleS, Point3D point, DIRECTION direction,
List<Angles> listRotationangles) ;
- This is the most important part "perspective projection". It's all about how a point in 3D space is projected on 2d screen so that there is no deviation from real look and feel. Viewer is position of viewer with respect to screen, calculate the final x,y and return it.
Note: All graphics functions take only X,Y coor as parameter.
public PointF PerspetiveProjection(Point3D Viewer);
Q What is the Role of Cube Class ?
This is where the complexity starts. We know that cube is formed by connecting (carefully placed) 8 points in space, cube stores collection of eight points and is responsible for its drawing, in order to fill something computer graphics need a enclosed region, in case of cube we have 6 enclosed regions called faces. Cube stores collection of points which form a cube face.
- (1,2,3,4) represents face 1,
- (2,6,7,3) represents face 2,
- (5,6,7,8) represents face 3,
- (1,8,6,5) represents face 4,
- (1,5,8,4) represents face 5,
- (8,7,3,4) represents face 6,
Each face has a color associated with it. Cube remembers the sequence of rotations applied on to it as shown in the code below:
switch (direction)
{
case DIRECTION.XAXIS:
listRotationangles.Add(new Angles(rotationAngles.xAngle, 0, 0));
break;
case DIRECTION.YAXIS:
listRotationangles.Add(new Angles(0, rotationAngles.yAngle, 0));
break;
case DIRECTION.ZAXIS:
listRotationangles.Add(new Angles(0, 0, rotationAngles.zAngle));
break;
}
Q What sequence of operation Cube follow while drawing ?
- Apply
FullFinalTransformation on 8 points. - Apply sequence of rotations(previously stored) and current one(this arises from user action) on 8 points. Add the current rotation in
listRotationangles. - Apply
PerspectiveProjection on 8 points to project on computer screen. - As a result of all previous actions, we have all points in 2d space ready to be drawn on computer screen.
- Choosing which cube face to draw is most tricky. The most important point to be kept in mind is that at any point while viewing a cube only 3 faces are visible.
Here, the hidden surface removal algorithm fits in.
- I have to choose three faces.
- Store 3 top most points whose Z coor in max in world space in collection
lsttop.
var sortedDict = (from entry in POINTS
orderby entry.Final.z descending
select entry);
lsttop = new List<int>();
lstbottom = new List<int>();
int i = 0;
foreach (Point3D key in sortedDict)
{
if (i <= 3)
{
lsttop.Add(key.i);
}
else
{
lstbottom.Add(key.i);
}
i++;
}
- Find the face which consists of all points in
lsttop, draw the face.
var sortedDict1 = (from entry in listpoint
where entry.Value.All(find)
select entry.Key);
foreach (int key in sortedDict1)
{
FinalRegion.Union(new Region(collectionGp[key]));
graphic.FillRegion(new SolidBrush(Colors[key]), FinalRegion);
graphic.DrawPath(new Pen(Colors[key]), collectionGp[key]);
- Find the face adjacent to drawn face, which does not intersect with already drawing face, draw them.
var sortedDict2 = (from entry in listpoint
where entry.Value.Any(findone)
select entry.Key);
Region cloneregion = FinalRegion.Clone();
foreach (int key1 in sortedDict2)
{
FinalRegion = cloneregion.Clone();
Region region = new Region(collectionGp[key1]);
FinalRegion.Intersect(region);
if (FinalRegion.IsEmpty(graphic) == true)
{
graphic.FillRegion(new SolidBrush(Colors[key1]), region);
graphic.DrawPath(new Pen(Colors[key1]), collectionGp[key1]);
}
}
done with drawing a cube.
Q What is the Role of Rubik Cube Class?
Rubik cube is responsible for placing 27 cubes in world coordinate system as shown below:
The code below shows how to place 27 cubes in 3d space.
for (int j = 0; j < 3; j++)
{
for (int k = 0; k < 3; k++)
{
for (int i = 0; i < 3; i++)
{
cubes[i + k * 3 + j * 3 * 3] = new cube(i + k * 3 + j * 3 * 3);
CubesAtposition.Add(i + k * 3 + j * 3 * 3, i + k * 3 + j * 3 * 3);
xplus = 11;
yplus = 11;
zplus = 11;
cubes[i + k * 3 + j * 3 * 3].POINTS[0] = new Point3D(1, offset + i * xplus + i *
xspace, yplus + j * yplus + j * yspace, zplus + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].POINTS[1] = new Point3D(2, xplus + i * xplus + i *
xspace, yplus + j * yplus + j * yspace, zplus + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].POINTS[2] = new Point3D(3, xplus + i * xplus + i *
xspace, offset + j * yplus + j * yspace, zplus + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].POINTS[3] = new Point3D(4, offset + i * xplus + i *
xspace, offset + j * yplus + j * yspace, zplus + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].POINTS[4] = new Point3D(5, offset + i * xplus + i *
xspace, yplus + j * yplus + j * yspace, offset + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].POINTS[5] = new Point3D(6, xplus + i * xplus + i *
xspace, yplus + j * yplus + j * yspace, offset + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].POINTS[6] = new Point3D(7, xplus + i * xplus + i *
xspace, offset + j * yplus + j * yspace, offset + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].POINTS[7] = new Point3D(8, offset + i * xplus + i *
xspace, offset + j * yplus + j * yspace, offset + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].Colors[0] = Color.Red;
cubes[i + k * 3 + j * 3 * 3].Colors[1] = Color.Blue;
cubes[i + k * 3 + j * 3 * 3].Colors[2] = Color.Yellow;
cubes[i + k * 3 + j * 3 * 3].Colors[3] = Color.Green;
cubes[i + k * 3 + j * 3 * 3].Colors[4] = Color.DarkTurquoise;
cubes[i + k * 3 + j * 3 * 3].Colors[5] = Color.DarkOrange;
}
}
}
Rubik cube is responsible for rotating cube faces, every face can be rotated, even whole Rubic cube can be rotated on X,Y,Z axis, Rubik cube maintains a mapping between cubeposition and cubenumber, every cube in rubik cube has a cube number associated with it, when a face is rotated, the cubenumber at cubeposition is changed in mapping.
Dictionary<int, int> CubesAtposition = new Dictionary<int, int>();
The most important challenge Rubik cube face is in what order cubes must be drawn so that a perfect picture is possible (no overlapping no distortion). Cubes which are farthest from the camera position are drawn first.
for (int index = 0; index <= 26; index = index + 1)
{
double distance = 0;
collectionPoint3d[index] = cubes[index].CalculateCentrePointAfterRotate(cameraPosition,
angles, cubes[index].CuberRotationAngles, point3d, cubes[index].dir);
distance = Math.Sqrt((cameraPosition.x - collectionPoint3d[index].x) *
(cameraPosition.x - collectionPoint3d[index].x)
+ (cameraPosition.y - collectionPoint3d[index].y) *
(cameraPosition.y - collectionPoint3d[index].y)
+ (cameraPosition.z - collectionPoint3d[index].z) *
(cameraPosition.z - collectionPoint3d[index].z));
listdistance[index] = distance;
}
var sortedDict2 = (from entry in listdistance
orderby entry.Value descending
select entry.Key);
foreach (int key in sortedDict2)
{
cubes[key].Draw(g, cameraPosition, angles, viewer,
cubes[key].CuberRotationAngles, point3d, cubes[key].dir);
}
The little piece of code check for game completeness.
public bool Check()
{
bool bCheck = true;
for (int iPos = 0; iPos < 27; iPos++)
{
if (CubesAtposition[iPos] != iPos)
{
bCheck = false;
break;
}
}
return bCheck;
}
I am done with the article. Do write to me at Atulloona4@gmail.com for any queries and please do vote.
Thanks!
