RRT Helicopter Simulation
Simon Carroll
David Pawlowski
EECS 466: Computer Graphics (Spring '05)
RRT Demo.zip (requires Visual Studio.NET dll's)
Compressed .mp4 videos:
XCode Project: .zip folder
Rapidly-Exploring Random Trees
Rapidly-Exploring Random Trees are a sampling based technique used to explore a solution space. The space can be regular two, three, or four (time) dimensional, or it can include hybrid components as well, such as switching rules of movement. RRTs were developed to d eal with the problem of exploring space deterministically, as this is computationally inefficient. Obviously RRTs do not explore every possible path, but they are probabilistically complete in their exploration. RRT's were developed by Steve LeValle at the University of Illinois. RRT Website
Select Picture from LeValle showing RRT showing the growth of a two dimensional RRT:
 |
 |
 |
Methodologies
We used Rapidly-exploring Random Trees to plan the path for the helicopter. In order to ensure that the helicopter pr oceeded in the general direction of the goal, the search was biased toward the goal every fourth iteration. The trees we used for the helicopter explored the space of the problem in four dimensions, including keeping track of a time component used for avoidance of moving obstacles. At a specific point in time a path to the goal is generated avoiding all obstacles. With some specified frequency, obstacles are fired from the goal to the predicted helicopter's position, forcing a path to be re-routed to avoid the obstacle.
Helicopter Image
To create a more realistic helicopter, texture mapping techniques could be used. However, we concentrated more on the algorithm portion and used a more primitive looking representation. We used a triangle mesh representation of a helicopter. To realistically color the helicopter we decomposed the faces into the different parts and then colored them apropriately. For example the missiles are red, the body is green, and the propeller is gray.
 |
 |
Simplified Helicopter Physics
To make the helicopter's motions somewhat realistic we used a simplified model. The helicopter was allowed to move forward, turn left or right, or to climb or dive. At each stage of development of the tree, the helicopter would choose the one of these five options that would get it closest to the randomly chosen point. Additionally, each motion has associated yaw, pitch, and roll values which are interpolated through each motion.
 |
 |
Right Turn |
Climb |
City Scene (Texture Mapping)
We used texture mapping to create the buildings in our city. The city consists of single lane, flanked by buildings on the left and right. Down the middle of the lane are a few smaller buildings. We obtained texture maps that were images of a part of the surface of a building. We then used those maps as the building blocks for our buildings. The size and shape of the buildings are generated randomly, within some predefined specifications, as well as choosing a random building texture map. The result is that the scene is slightly different each time. The ground is simply a repeated concrete texture map, while the sky is a repeated texture map of a sky scene.
 |
 |
 |
Lighting
We used the lighting techniques built in to OpenGL with the smooth Gourard shading model. Our scene takes place during the daytime so we use a very high level of ambient light. Likewise we model the sun as omni-directional light source placed directly above the scene. The normals are calculated for the triangle mesh helicopter as well as the spherical obstacles. Diffuse and specular lighting can then be calculated for those objects.