Project 1b - Show acceleration static and during animation, Optimize
Goal: The goal of this phase of the project is compute the tangential and normal
acceleration along the track and design a car that never exceeds a specified maximum
acceleration.
System: My project was written on Windows XP using Processing (http://processing.org). The Java wrapper used by Processing should make it cross-platform compatible.
Racing Strategies: There are several possible to make a car speed up and slow down so that it does not "skid" when going around turns. The first is to simply make a constant speed car go as fast as possible so that none if its normal acceleration vectors exceed the threshold. This is not very feasibly since the car would be very slow on straight-aways. Professor Rossignac proposed a solution in which the car proceeds along a tangent and then picks the largest indexed point within a pre-determined size circle that would still allow the car to stop if it needed to. This sounds like a good method but has some problems, for example when the track crosses itself the car could erroneously switch to the other part of the track. Another solution is to compute individual step sizes of increasing length yet remain below the acceleration threshold.
Acceleration Threshold: I computed the acceleration threshold by using a metric taken from the constant speed car. Since the constant speed car never changes its tangential velocity, the normal acceleration is very high going around curves (especially when other subdivision techniques are used, see the demo video at the bottom). I simply took the average normal acceleration of the constant speed car and used that as the threshold for the optimized car, so around 50% of the time the constant speed car will exceed the threshold (and turn yellow) and the optimized car will not.
Implementation: For my implementation I choose to make a path around the track and increase the next step size so the normal acceleration vector wouldn't exceed the threshold computed earlier. The normal acceleration vector is calculated using:
c1ax[i] = c1x[i] + (2*c1x[i] - c1x[prev(i, car1_totalsteps)] - c1x[next(i, car1_totalsteps)])
c1ay[i] = c1y[i] + (2*c1y[i] - c1y[prev(i, car1_totalsteps)] - c1y[next(i, car1_totalsteps)])
where i is the current step. Then, a step large step distance is chosen and continually decreased until the acceleration magnitude is within the threshold. The acceleration magnitude is simply the length from the vertex to the end of the acceleration vector multiplied by a constant. This constant is also used for drawing the force lines to an appropriate size on the screen. I found that force_length = 0.2*pow(4,curve_iterations) worked well for the magnitude. In the end the blue car goes at a constant speed and often exceeds the threshold while the optimized car slows down for turns and speeds up on the straight-aways.
Evaluation Techniques: Evaluating my implementation with other students would be relatively easy. First, the two programs would have to share the same track. This could be done by supplying the same control polygon coordinates and using a cubic b-spline subdivision scheme. Also the programs would have to compute acceleration uniformly and be pre-programmed with the same threshold. Then the cars could be instructed to make a single loop around the track. My timing and comparing all student solutions it will be possible to see which is the fastest and therefore most optimized.
Applet Instructions:
Drag the vertices to edit the track.
Drag midpoints (small dots) to create a new vertex.
Press [1-9] in edit mode to create less-more interpolated curves.
Press 0 to make a cubic B-spline curve.
Press R to enable/disable racing mode.
Applet:
Source Code: p1b.pde
Demo Video: p1b-demo-divx.avi (2 MB, DivX Required)
System: My project was written on Windows XP using Processing (http://processing.org). The Java wrapper used by Processing should make it cross-platform compatible.
Racing Strategies: There are several possible to make a car speed up and slow down so that it does not "skid" when going around turns. The first is to simply make a constant speed car go as fast as possible so that none if its normal acceleration vectors exceed the threshold. This is not very feasibly since the car would be very slow on straight-aways. Professor Rossignac proposed a solution in which the car proceeds along a tangent and then picks the largest indexed point within a pre-determined size circle that would still allow the car to stop if it needed to. This sounds like a good method but has some problems, for example when the track crosses itself the car could erroneously switch to the other part of the track. Another solution is to compute individual step sizes of increasing length yet remain below the acceleration threshold.
Acceleration Threshold: I computed the acceleration threshold by using a metric taken from the constant speed car. Since the constant speed car never changes its tangential velocity, the normal acceleration is very high going around curves (especially when other subdivision techniques are used, see the demo video at the bottom). I simply took the average normal acceleration of the constant speed car and used that as the threshold for the optimized car, so around 50% of the time the constant speed car will exceed the threshold (and turn yellow) and the optimized car will not.
Implementation: For my implementation I choose to make a path around the track and increase the next step size so the normal acceleration vector wouldn't exceed the threshold computed earlier. The normal acceleration vector is calculated using:
c1ax[i] = c1x[i] + (2*c1x[i] - c1x[prev(i, car1_totalsteps)] - c1x[next(i, car1_totalsteps)])
c1ay[i] = c1y[i] + (2*c1y[i] - c1y[prev(i, car1_totalsteps)] - c1y[next(i, car1_totalsteps)])
where i is the current step. Then, a step large step distance is chosen and continually decreased until the acceleration magnitude is within the threshold. The acceleration magnitude is simply the length from the vertex to the end of the acceleration vector multiplied by a constant. This constant is also used for drawing the force lines to an appropriate size on the screen. I found that force_length = 0.2*pow(4,curve_iterations) worked well for the magnitude. In the end the blue car goes at a constant speed and often exceeds the threshold while the optimized car slows down for turns and speeds up on the straight-aways.
Evaluation Techniques: Evaluating my implementation with other students would be relatively easy. First, the two programs would have to share the same track. This could be done by supplying the same control polygon coordinates and using a cubic b-spline subdivision scheme. Also the programs would have to compute acceleration uniformly and be pre-programmed with the same threshold. Then the cars could be instructed to make a single loop around the track. My timing and comparing all student solutions it will be possible to see which is the fastest and therefore most optimized.
Applet Instructions:
Drag the vertices to edit the track.
Drag midpoints (small dots) to create a new vertex.
Press [1-9] in edit mode to create less-more interpolated curves.
Press 0 to make a cubic B-spline curve.
Press R to enable/disable racing mode.
Applet:
Source Code: p1b.pde
Demo Video: p1b-demo-divx.avi (2 MB, DivX Required)