Hand Motion Controlled Tetris

Hardware Design    top

As mentioned earlier in the High Level Design section, there were a few main components that needed to be put together to get the final project functioning correctly. This section will explore each of those components in greater depth.

Tetris Game

The Tetris Game FPGA can be broken down into 4 main sections: the physical hardware connections, overall game finite state machine, shape drawer, and the memory/VGA color mapping.

Physical Hardware Connections:

As mentioned earlier, the Tetris Game FPGA does receive information from the hand motion recognition FPGA, and the two FPGAs must be wired together on the GPIO header to communicate the left, right, or rotate command from the hand motion recognition FPGA to the Tetris Game FPGA. In essence, the hand motion FPGA outputs voltages on GPIO ports 1,3,5 as to whether there was a left, right, or up hand motion gesture recognized from the video stream. GPIO[1] corresponds to the right signal, GPIO[3] is the left signal, and GPIO[5] is the rotate signal. The Tetris Game FPGA is using its GPIO ports as an input, so the FPGA must set its GPIO ports 1,3,5 to high impedance, otherwise, it could possibly damage the FPGA.

Overall Game FSM

The overall game FSM takes care of running the entire game whose tasks are broken down into the flow diagram below:

Every time the game is reset, the walls of the game are first drawn, and then a random tetrimino will be drawn onto the playing area. The FSM will check to see if the tetrimino moves down/left/right, that the tetrimino will be stopped by another tetrimino or wall. If there are no obstacles, the tetrimino will move in the direction specified. If the tetrimino is at the top and cannot move down, the game is finished, and LED0 lights up. Then the FSM checks to see if there are any rows filled in the location where the most recent tetrimino was dropped off. If so, that row will be erased, shift everything above down by 1 row, and increment the score. If there are no rows filled, the FSM will produce the next random shape and continue looping through until the game is finished. A general diagram showing which FSM states belong with which task is shown below:

These different tasks will be discussed in detail later.

Overall Game FSM -> Drawing Wall:

Whenever the game starts up, the first thing that the FSM will do is draw out the two vertical lines that indicate the walls of the game. To do this, there were two states in the FSM dedicated for this task: drawBoard0 and drawBoard1. These two states output the correct signals to the VGA such as controlling the mux (so the VGA buffer would get the signals from this FSM instead of the other submodule called newShapeDrawer). First, the FSM would draw the left wall, which is at x=149 and 480 pixels long. Once the first left wall was drawn, the x coordinate was changed to x=491, and then 480 pixels would be drawn down the screen. Once the right wall is drawn, the FSM will go on to start generating the next random shape.

Overall Game FSM -> Random Shape Generation:

Two more states of the FSM fall under this task: drawShape0 and drawShape1. Determining the next shape and orientation are calculated in drawShape0. For random shape generation, the method for determining a shape and its orientation is in 3 and 2 bits, respectively. Then, two 15 bit registers are built, one with a random seed and another (called shape_orient_rand) with certain bits from the random seed in different order. There is a shape and orientation register that feeds into the newShapeDrawer module, and these two registers get bits 7 through 5 and bits 12 to 11 from the 15 bit shape_orient_rand register. Every time when in this state, bits 13 and 6 of shape_orient_rand are XORed together and shifted in from the left into the random seed. The shape_orient_rand register is also shifted to the left by one with the product of the XORed bits 13 and 6 shifted in. DrawShape0 also sets the coordinates of where that block should start (top of the screen) and ensures that the muxes will be muxing signals from the newShapeDrawer module to the VGA buffer, and not the signals from this FSM to the VGA buffer. The parameters for newShapeDrawer are set so that the newShapeDrawer will be in its draw mode.

DrawShape1 state will enable the newShapeDrawer module to start drawing the tetrimino. Since it takes more than one cycle to draw a tetrimino, the FSM will stall in this state until the newShapeDrawer indicates that it is done drawing the tetrimino on the VGA. The drawShape1 state will go to the waitstate. Because the FSM is running at about 75.6 MHz, it would not make sense to immediately erase the shape and redraw it 1 block down. The human eye would not be able to see the tetrimino if there was no delay in between. There were two registers (timeDraw and timeErase) used to control how long the the tetrimino should stay displayed and how long it should stay erased. The value of the registers were determined by switch 16, with the slow mode set to 60000000 and 1000000 for timeDraw(.794 sec) and timeErase (.013 sec), respectively. The fast mode is set to 50000000 and 3000000 for timeDraw(.661 sec) and timeErase (.0397 sec.), respectively. In the wait state, it will stall in the wait state until .794 seconds have passed with the tetrimino block still being displayed on the VGA. Then it will go to the move0 state.

Overall Game FSM -> Checking Boundaries and Moving Shapes:

The move0 state sets up the parameters so that the newShapeDrawer will erase the tetrimino at the same location where it was displayed. There is a flag called erasedshape that is set to 1 to indicate that the shape will have been erased after being displayed once. It will go back to drawShape1 then to waitstate. The erased shape will display on the buffer for .013 sec, and then go to the move1 state.

In the move1 state, it will check a newShapeDrawer signal called bottomwall, which indicates if there is a wall or block beneath the tetrimino before redrawing it 1 block down. If the bottomwall flag is not set, the location of the tetrimino is updated x and y coordinate-wise. The shape is then redrawn with the new coordinates, going through drawShape1 and waitstate. Then this cycle of drawing the tetrimino, waiting for .794 sec, erasing, waiting for .013 sec, and updating coordinates/checking boundaries is repeated until the tetrimino has reached the bottom or hit another block below it.

Overall Game FSM -> Checking for Full Line:

In order to detect when a full line is cleared, we need to have an efficient way to detect full lines. In the most basic solution, you would check every single line whenever you perform any operation such as a draw. However, we can instead check a range of lines once a block is permanently placed down. Since a shape’s position is defined by a point at the top of the shape, and we know each shape is at most 4 blocks high, we can check the y position and the 3 lines below that once we detect that we have hit a bottom boundary. Functionality of boundary checking has already been described, so we will focus on the few states to check full lines. When the outer FSM detects a shape has reached its final destination, it changes the mode for newShapeDrawer to verify full lines to mode 3. Given the y position of the placed block, it simply goes through the 4 lines, reading blocks until it either finds an empty block or the rightmost boundary of the game board.

Overall Game FSM -> Erasing Line:

With the functionality of checking for a full line, we can continue the functionality in the main FSM. So after checking for a full line, the outer FSM reads the result, and for each bit that is set, it invokes the line erase mode, mode 2. So say the result from the verify full line was 0011, it will invoke the erase line function in newShapeDrawer, which will be explained in a later section, on y_position+2, and then on y_position+3. Doing this means that this game is able to both detect and erase multiple lines even when a single block completed both lines. Like with many invocations of newShapeDrawer, the states involve checking the results and setting the appropriate registers to call the erase line functionality, and a wait state for newShapeDrawer to finish.

Shape Drawer:

The newShapeDrawer module is an essential component for the Tetris game to work. It consists of an FSM with many registers, wires, buses, submodule shapeBitLUT, submodule drawSquare_w, and multiple multiplexers. The FSM interacts will all of the other hardware within this module to generate the correct signals to the VGA for drawing/erasing the tetrimino or checking/erasing entire lines in the grid. This module has four modes: drawing tetrimino, erasing tetrimino, erasing line of blocks, and verifying if the next four lines are filled up with blocks. The FSM has states that are dedicated for each of the four modes. The diagram below shows which states are split up for the different modes. Note that there are only 3 different modes shown, because the erase and draw shape mode both utilize the blue branch, only the color being drawn is black instead of from the look up table for erasing as opposed to drawing.

Shape Drawer FSM -> Mode: Erase/Draw Shape

In this mode, it uses 5 states total to check the boundaries of what is about to be drawn and then to actually draw the tetrimino onto the VGA. For the first 2 states, checkDraw1 will start checking if the tetrimino at its current location will hit the wall or bottom before drawing it out. The LUT table has outputs that contain the x and y coordinates that should be checked to see if the tetrimino will run into a wall or another block. If the tetrimino will hit the wall or ground, it sets either the bottomwall, leftwall, or rightwall flag to indicate that the tetrimino will hit something. Walls take priority, so the FSM will not cycle through the rest of the boundary condition and will draw the tetrimino at its new location (since it knows the wall will be next to it and only sets the flag to indicate if we moved it one block more, it should not go in that direction). If there are no walls, the FSM will cycle through the rest of the boundary conditions to read from the VGA screen and see if there is another tetrimino that the current tetrimino might hit. Another important thing to notices is that it takes 3 cycles to get a reading from the VGA buffer, so checkDraw2 has a counter that stalls it for that long in order to get a valid reading from the VGA buffer.

If the tetrimino does not have any boundaries being hit, draw1-3 states handles the signals for drawing the tetrimino at its new location. Due to the way the tetriminos are encoded in the LUT, the drawSquare_w module is used to draw out the 4 blocks of a tetrimino. The LUT provides the relative coordinates of what blocks should be drawn from a top left corner reference. In the diagram below, it shows how the square tetrimino is encoded. The reference point is where the black dot is and the green squares are the boundary condition coordinates that need to be checked each time you want to draw/erase the tetrimino. The square numbers are how it is encoded in the look up table, and the draw1-3 states will cycle through this entire 4x4 grid. The blue square means that the LUT will have those bit numbers encoded with a value of 1 while the others in the 4x4 grid are 0. Whenever one of the squares has a value of 1, that square will be drawn by the drawSquare_w module with either the color that is encoded from the LUT or with black. If erasing, the color is black and if drawing, the color will be the LUT’s color. The draw1-3 state will set the appropriate coordinates for a square to be drawn in the tetrimino and color. Then the drawSquare_w module is enabled, and the FSM will stall in draw3 state until the drawSquare_w module has finished drawing 1 square. Then it repeats this process until all 16 squares in the 4x4 block have been checked and drawn.

Shape Drawer FSM -> Mode: Erase Line

There are several different states associated with erasing a line since it needs to deal with moving all blocks down, and erasing the very top line. Overall, moving blocks down involves reading the line above and writing it in the current line, working from the bottom up to the top. It starts in the eraseline1 state, which checks to see which line it is currently in. For most lines, it moves to the eraselineread1 state, and for the very top line, it moves to the eraseline2 state. The eraselineread1 state sets memory control to newShapeDrawer and waits to read the value of the block that is at the same x-coordinate, but one less than the y-coordinate. This means we read the block above the current block. We move to eraselineread1_5 once we finish reading and set the memory control back to the square drawer, and have it draw the block we just read at the current block position. At this point, it is at eraseline2, which is the same as when we are in the top line case as well. This state enables the square drawer and moves to our eraseline3 state, which checks our termination conditions. So eraseline3 will wait for the drawing to finish, then move to the next block in a the current line, else it will move to the line above. If we are at the top line and all blocks in the line were read, it goes to the done state, else it goes back to eraseline1 where the process is repeated.

Shape Drawer FSM -> Mode: Verify Line

Given a starting y position, this mode will check the line and the next 3 after that to see if the line is completely full of blocks. It starts off at the top line, checking every block in the line iteratively. It starts in verifyFull1, which sets registers to prepare for a memory read. For the current coordinates, it reads the contents. The verifyFull2 simply waits for a memory read to complete and then moves directly to verifyFull3. Finally, verifyFull3 handles the determination of whether to continue or not. If it finds an empty block, the line is not full and it immediately moves to the next line. Else, it will continue checking the line. If it checks all x positions and finds no empty blocks, it sets a bit in a 4-bit wide result that indicates which line is full. So if the second line from the top y position was filled, the result would look like 0100. After setting the new coorrdinates, it moves back to the verifyFull1 state. Once it checks all 4 lines, it moves to the idle state and sets the done flag.

Shape Drawer -> Translate grid to VGA Coordinate

When implementing shape drawer, we mainly worked with what we call “grid coordinates”. Grid coordinates specify blocks within the board. Our board space is 340x480 pixels, and each block is 10x10 pixels, thus, we have a 34x48 grid space. Making this abstraction allows us think more clearly about higher level functionalities such as reading certain blocks, rather than pixels. However, we cannot simply use grid coordinates when we want to access memory, so we use a translation to VGA coordinates. The Y coordinate is easily translated since we can just multiple the grid coordinate by 10. However, to translate the X coordinate, we need to multiply by 10, and also add 150 since the left border of the game starts the game board at the 150th pixel on the VGA. This implementation was simple to implement but provided many benefits through abstraction. Originally, we had thought to create two memory buffers, one that was actually a grid coordinate system that was 34x48, where we can get the overall state of the game, and then we could have a module to write the contents and translate it into the VGA buffer. However, we realized this did not provide any extra benefits over the final solution, and rather might have introduced delays, unnecessary work, and more memory usage.

Shape Drawer -> Draw Square Module

This module was created to handle the basic details of drawing 1 square of a 4 square tetrimino. It takes in inputs of its reference point (top left corner), the width/height, and what color the square should be. The outputs of the module are the data, address, and write enable for the VGA buffer and also a done signal to indicate that the module has finished drawing the square. There is a FSM within this module to handle drawing all of the pixels for the square. There are four states in which the module will output the the correct address, data, and write enable signal for the VGA buffer. The first two states actually are the signals for writing to the VGA buffer and the third state will increment the x coordinate until the row is finished. Then the y coordinate will be incremented by 1. This cycle of drawing row by row is repeated until it reaches the bottom right corner of the square. Then it transitions to the idle state, which outputs the done signal indicating that it has finished drawing the square. The diagram below shows the finite state machine diagram.

Shape Drawer -> LUT

As previously mentioned, the LUT provides encoded information about how the shapes look at different orientations, the color, and boundary conditions. The look up table takes in a shape, encoded as a 3-bit input, an orientation, encoded as a 2-bit input, and the x and y grid coordinates. It outputs a 16-bit shape, a 10-bit color, and 6 boundary conditions for each shape. The 16-bit shape encoding essentially defines the shape relative to the top-left corner of a 4x4 box. So the highest 4 bits encode the top row of the 4x4, and the lowest 4 bits encode the bottom row. When a bit is 1, that means there is a block, when it is 0, it is empty. So take for example a simple square shape, encoded as 0xCC00. On the top row we have two blocks then 2 empty spaces, as well as the second row. For the third and fourth rows, it is empty. Each of the 6 boundary conditions per shape,orientation pair specifies a coordinate and a boundary type. These coordinates are read in the shape drawer to see if there is a block there. We want to differentiate between a bottom boundary, which means the shape should no longer move and has settled, with a left or right boundary, which just means the shape cannot move in a certain direction. So for each boundary, we have 2 bits that specifies the boundary type. A left boundary is 0, a bottom boundary is 1, and a right is 2. When determining these boundaries, points that could be both bottom or a side, are set as bottom since it is priority over side movement. All boundaries were manually set and figured out.

Shape Drawer -> Memory/VGA Color Mapping

As mentioned, the LUT stores colors for each of the shapes. However, we encode 3 10-bit color values with just 10-bits by only specifying some of the bits of each color. Many of the least significant bits on each color do not produce visually different results, so instead, we use either 3 (red, green), or 4 (blue) bits for each color and then set the higher bits in the VGA color according to those bits, with the rest of the color bits as zero. So we use the 3 most significant bits for red, the next 3 for green, and the last 4 for blue. When we go to draw shapes, we are just writing these 10-bit color encodings into our memory buffer. We used a dual-clocked, dual-read/write port RAM with 10-bits for each of the pixels we display. This ends up using about 78% of the FPGAs total memory. One port of the memory is used by the VGA controller, which is in charge of the VGA signals. This port is clocked with the VGA control clock and is only read from. The other port is used by the overall FSM, the shape drawer, and the square drawer for both reading and writing. This port has two levels of muxing for control over the port, and is clocked with the SM control clock, a 75.6 MHz clock. Muxing between the overall FSM and the shape drawer is done by disabling the shape drawer and selecting the correct mux bits to allow the overall FSM to use the memory port. However, most of the time the shape drawer has access to the port. Inside, there is another mux between the shape drawer and the square drawer. Similar to the first scenario, when the shape drawer has memory control, the sqaure drawer is disabled and the mux bits are set. Otherwise, most of the time the square drawer will have control over the memory.

Timer and Scorekeeping

Two important aspects of the Tetris game is counting down until the game ends and keeping track of the score. The 27 MHz clock on the FPGA was used to keep track of the amount of time left in the game. A counter would until 27,000,000 and then subtract a 1 from the seconds timer. The seconds were kept track of using a “ones” and “tens” place. The minutes were kept track of using just one register. The timer starts at 2:00 minutes and counts down from there. The boundaries were taken into account (i.e. there being 60 seconds in a minute). When the ones place hit 0, a 1 was subtracted from the tens places. A similar method was used when the seconds counter reached :00. These numbers were all saved in decimal form. A hex display LUT was then used to convert the decimal numbers into the appropriate values for each hex displayed used.

Scorekeeping worked in a similar fashion. The score starts at 0 and the user gets 10 points for each line that is erased. An eraseline signal is taken in from the main game part. On the rising edge of the signal, 10 points are then added to the user’s score and displayed as the points accumulated. When the user reaches 100 points, the “tens” counter of the score is set to 0 and the “hundreds” counter is incremented by one. This is done in and combinational always block.

Hand Motion Recognition and Control

Video Signal Decoding

The video signal decoding was adapted from example code provided by Bruce Land on the 5760 webpage. Within this code, there are few modules that play an integral part in rendering the signal. It starts with a mini camera that gets plugged into the video input port on the DE2-115 board. Once turned on, this camera sends a video signal to the input port in NTSC format. More specifically, it uses ITU-R 656 protocol to do so. ITU-R 656 protocol is a digital video protocol used for streaming NTSC signals, similar to how wireless communications have protocols to send the information necessary. Once the signal is processed with the built in video decoder on the FPGA, the signal can than be worked with. In order to get the video to fit on the 640x480 screen, the signal is downsampled using a provided module. A separate module then takes the ITU-R 656 signal and converts it into YUV color space. This new signal is then taken and stored in SDRAM using a first in, first out (FIFO) method for the how to send the data out. The YUV data is used primarily for skin tone recognition in the next section. In order to get the the video to now be sent to the VGA screen, it is converted into RGB color space. With the signal now in RGB, a VGA control buffer reads in the value for each pixel of the 640x480 display and sends it out to the monitor. The program has the function to either display the original video or the raw, filtered video that just shows skin as white and everything else as black. This will be talked about in detail in the hand recognition section.

Hand Recognition

For this part of the project, it was necessary to discern what in the frame was actually skin and what was not. At this point, we have decoded NTSC video to work with. We adapted an M. Eng project from Thu-Thao Nguyen which also incorporated some example code from the 5760 website provided by Bruce Land. Both of these references and links to the work can be found in the appendix part of the webpage.

As mentioned before, one of the interesting facts about skin recognition is that independent of the intensity of the skin, the skin tones fall in the same general range on the UV components of the YUV color space. Therefore, we were able to disregard the Y factor of the YUV color space and just focus on the actual colors that were represented. Using the example NTSC code from Bruce, the decoded video signal was converted into the format YUV 422. However, this format shares the U and V information between two pixels, which means these values are only transmitted to the image buffer once every two pixels. In order to get a more exact value for the pixel colors, YUV 422 was converted into YUV 444. With this format, Y,U, and V each get 8 bits of information and is a more straightforward format. Additionally, we can now use these values to find R,G,B values on a range from 0 to 255. Another conversion was needed to change the YUV 444 color space into RGB values from [0:255] for R, B, and G. With these values, we can now relate RGB to YUV using some general equations. That was the next step. The two important ones to focus on for skin recognition are U = R - G and V = B - G. With these equations, we can calculate these differences for each pixel. We can break up the skin pixels into the following 2 categories:

10 < U < 74

-40 < V < 11

Additionally, it turns out that the blue part of RGB is the least important in regards to skin color. For this reason, just the U factor was taken into account. After doing some testing with the VGA output, it was determined that a good range to take into account for skin recognition was U > 60 and U < 256 (or R-G > 60 and R-G < 256). This produced minimal amount of errors, such as accidentally mistaking something else in the room for skin. If the U value was in this range, a 1 was stored in the VGA buffer. If the U value was out of this range, a 0 was put in the buffer. This way, there was now just a simple black and white image that showed where the hand was in the frame.

Hand in gesture control system

The next step was actually determining where the hand was and sending certain signals to the game. The four choices in signals were to move the piece to the right, left, down at 2x speed, or rotate clockwise. To accomplish this, the screen was broken up into four sections as follows:

VGA Regions of the Screen and Their Bounds

The boundaries for making the piece go left or right were at X-pixel 100 and X-pixel 550, respectively. The boundaries for making the piece rotate or go down were at Y-pixel 50 and Y-pixel 400, respectively. These values were tinkered with until that seemed reasonable given an actual user. Additionally, due to the fact that the skin detection algorithm also will detect the user’s face, it was important to make the regions relatively small compared to the space in the middle. One the user moves their hand into one of the regions, a counter counts how many white pixels are in the given region. The limit for the left and right regions were 425 white pixels. This is due to the fact that the user will have their palm facing the screen (meaning a good amount of white pixels) so the game needs to register that their palm is in the region as opposed to another item in the room. The limit for the rotate region was 325 pixels; slightly less than the left and right sections. This is due to the fact that the user’s hand is perpendicular to the region and therefore, inherently, won’t have as much as the palm in the region. Increasing the size of the region was not practical due to the fact that the head is always towards the top of the screen. The down region on requires 225 white pixels to send a “1” to the down movement of the game. This is because it is naturally difficult to keep the palm exactly parallel to the screen when move the arm down. People have a tendency to rotate their palm downward as they move their arm downward. This was accounted for in the smaller number of pixels need for this section. In the end, these hand movements simply send a high signal to the appropriate movement. This signal is taken as an input to the game module and handled from there.

---