Planner.cpp

00001 /*  
00002       This file is part of Smoothie (http://smoothieware.org/). The motion control part is heavily based on Grbl (https://github.com/simen/grbl) with additions from Sungeun K. Jeon (https://github.com/chamnit/grbl)
00003       Smoothie is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
00004       Smoothie is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
00005       You should have received a copy of the GNU General Public License along with Smoothie. If not, see <http://www.gnu.org/licenses/>. 
00006 */
00007 
00008 using namespace std;
00009 #include <vector>
00010 #include "libs/nuts_bolts.h"
00011 #include "libs/RingBuffer.h"
00012 #include "../communication/utils/Gcode.h"
00013 #include "libs/Module.h"
00014 #include "libs/Kernel.h"
00015 #include "Block.h"
00016 #include "Planner.h"
00017 #include "Player.h" 
00018 
00019 
00020 Planner::Planner(){
00021     clear_vector(this->position);
00022     clear_vector_double(this->previous_unit_vec);
00023     this->previous_nominal_speed = 0.0;
00024     this->has_deleted_block = false;
00025 }
00026 
00027 void Planner::on_module_loaded(){
00028     this->on_config_reload(this);
00029 }
00030 
00031 void Planner::on_config_reload(void* argument){
00032     this->acceleration =       this->kernel->config->value(acceleration_checksum       )->by_default(100 )->as_number();
00033     this->max_jerk =           this->kernel->config->value(max_jerk_checksum           )->by_default(100 )->as_number();
00034     this->junction_deviation = this->kernel->config->value(junction_deviation_checksum )->by_default(0.05)->as_number(); 
00035 }
00036 
00037 
00038 // Append a block to the queue, compute it's speed factors
00039 void Planner::append_block( int target[], double feed_rate, double distance, double deltas[] ){
00040    
00041     // Stall here if the queue is ful
00042     this->kernel->player->wait_for_queue(2);
00043 
00044     Block* block = this->kernel->player->new_block();
00045     block->planner = this;   
00046 
00047     // Direction bits
00048     block->direction_bits = 0; 
00049     for( int stepper=ALPHA_STEPPER; stepper<=GAMMA_STEPPER; stepper++){ 
00050         if( target[stepper] < position[stepper] ){ block->direction_bits |= (1<<stepper); } 
00051     }
00052     
00053     // Number of steps for each stepper
00054     for( int stepper=ALPHA_STEPPER; stepper<=GAMMA_STEPPER; stepper++){ block->steps[stepper] = labs(target[stepper] - this->position[stepper]); } 
00055     
00056     // Max number of steps, for all axes
00057     block->steps_event_count = max( block->steps[ALPHA_STEPPER], max( block->steps[BETA_STEPPER], block->steps[GAMMA_STEPPER] ) );
00058     //if( block->steps_event_count == 0 ){ this->computing = false; return; }
00059 
00060     block->millimeters = distance;
00061     double inverse_millimeters = 0; 
00062     if( distance > 0 ){ inverse_millimeters = 1.0/distance; }
00063 
00064     // Calculate speed in mm/minute for each axis. No divide by zero due to previous checks.
00065     // NOTE: Minimum stepper speed is limited by MINIMUM_STEPS_PER_MINUTE in stepper.c
00066     double inverse_minute = feed_rate * inverse_millimeters;
00067     if( distance > 0 ){ 
00068         block->nominal_speed = block->millimeters * inverse_minute;           // (mm/min) Always > 0
00069         block->nominal_rate = ceil(block->steps_event_count * inverse_minute); // (step/min) Always > 0
00070     }else{
00071         block->nominal_speed = 0;
00072         block->nominal_rate = 0;
00073     }
00074 
00075     //this->kernel->serial->printf("nom_speed: %f nom_rate: %u step_event_count: %u block->steps_z: %u \r\n", block->nominal_speed, block->nominal_rate, block->steps_event_count, block->steps[2]  );
00076     
00077     // Compute the acceleration rate for the trapezoid generator. Depending on the slope of the line
00078     // average travel per step event changes. For a line along one axis the travel per step event
00079     // is equal to the travel/step in the particular axis. For a 45 degree line the steppers of both
00080     // axes might step for every step event. Travel per step event is then sqrt(travel_x^2+travel_y^2).
00081     // To generate trapezoids with contant acceleration between blocks the rate_delta must be computed
00082     // specifically for each line to compensate for this phenomenon:
00083     // Convert universal acceleration for direction-dependent stepper rate change parameter
00084     block->rate_delta = ceil( block->steps_event_count*inverse_millimeters * this->acceleration*60.0 / this->kernel->stepper->acceleration_ticks_per_second ); // (step/min/acceleration_tick)
00085 
00086     // Compute path unit vector
00087     double unit_vec[3];
00088     unit_vec[X_AXIS] = deltas[X_AXIS]*inverse_millimeters;
00089     unit_vec[Y_AXIS] = deltas[Y_AXIS]*inverse_millimeters;
00090     unit_vec[Z_AXIS] = deltas[Z_AXIS]*inverse_millimeters;
00091   
00092     // Compute maximum allowable entry speed at junction by centripetal acceleration approximation.
00093     // Let a circle be tangent to both previous and current path line segments, where the junction
00094     // deviation is defined as the distance from the junction to the closest edge of the circle,
00095     // colinear with the circle center. The circular segment joining the two paths represents the
00096     // path of centripetal acceleration. Solve for max velocity based on max acceleration about the
00097     // radius of the circle, defined indirectly by junction deviation. This may be also viewed as
00098     // path width or max_jerk in the previous grbl version. This approach does not actually deviate
00099     // from path, but used as a robust way to compute cornering speeds, as it takes into account the
00100     // nonlinearities of both the junction angle and junction velocity.
00101     double vmax_junction = MINIMUM_PLANNER_SPEED; // Set default max junction speed
00102 
00103     if (this->kernel->player->queue.size() > 1 && (this->previous_nominal_speed > 0.0)) {
00104       // Compute cosine of angle between previous and current path. (prev_unit_vec is negative)
00105       // NOTE: Max junction velocity is computed without sin() or acos() by trig half angle identity.
00106       double cos_theta = - this->previous_unit_vec[X_AXIS] * unit_vec[X_AXIS]
00107                          - this->previous_unit_vec[Y_AXIS] * unit_vec[Y_AXIS]
00108                          - this->previous_unit_vec[Z_AXIS] * unit_vec[Z_AXIS] ;
00109                            
00110       // Skip and use default max junction speed for 0 degree acute junction.
00111       if (cos_theta < 0.95) {
00112         vmax_junction = min(this->previous_nominal_speed,block->nominal_speed);
00113         // Skip and avoid divide by zero for straight junctions at 180 degrees. Limit to min() of nominal speeds.
00114         if (cos_theta > -0.95) {
00115           // Compute maximum junction velocity based on maximum acceleration and junction deviation
00116           double sin_theta_d2 = sqrt(0.5*(1.0-cos_theta)); // Trig half angle identity. Always positive.
00117           vmax_junction = min(vmax_junction,
00118             sqrt(this->acceleration*60*60 * this->junction_deviation * sin_theta_d2/(1.0-sin_theta_d2)) ); 
00119         }
00120       }
00121     }
00122     block->max_entry_speed = vmax_junction;
00123    
00124     // Initialize block entry speed. Compute based on deceleration to user-defined MINIMUM_PLANNER_SPEED.
00125     double v_allowable = this->max_allowable_speed(-this->acceleration,0.0,block->millimeters); //TODO: Get from config
00126     block->entry_speed = min(vmax_junction, v_allowable);
00127 
00128     // Initialize planner efficiency flags
00129     // Set flag if block will always reach maximum junction speed regardless of entry/exit speeds.
00130     // If a block can de/ac-celerate from nominal speed to zero within the length of the block, then
00131     // the current block and next block junction speeds are guaranteed to always be at their maximum
00132     // junction speeds in deceleration and acceleration, respectively. This is due to how the current
00133     // block nominal speed limits both the current and next maximum junction speeds. Hence, in both
00134     // the reverse and forward planners, the corresponding block junction speed will always be at the
00135     // the maximum junction speed and may always be ignored for any speed reduction checks.
00136     if (block->nominal_speed <= v_allowable) { block->nominal_length_flag = true; }
00137     else { block->nominal_length_flag = false; }
00138     block->recalculate_flag = true; // Always calculate trapezoid for new block
00139  
00140     // Update previous path unit_vector and nominal speed
00141     memcpy(this->previous_unit_vec, unit_vec, sizeof(unit_vec)); // previous_unit_vec[] = unit_vec[]
00142     this->previous_nominal_speed = block->nominal_speed;
00143     
00144     // Update current position
00145     memcpy(this->position, target, sizeof(int)*3);
00146 
00147     // Math-heavy re-computing of the whole queue to take the new 
00148     this->recalculate();
00149     
00150     // The block can now be used 
00151     block->ready();
00152 
00153 }
00154 
00155 
00156 // Recalculates the motion plan according to the following algorithm:
00157 //
00158 // 1. Go over every block in reverse order and calculate a junction speed reduction (i.e. block_t.entry_factor)
00159 // so that:
00160 //   a. The junction jerk is within the set limit
00161 //   b. No speed reduction within one block requires faster deceleration than the one, true constant
00162 //      acceleration.
00163 // 2. Go over every block in chronological order and dial down junction speed reduction values if
00164 //   a. The speed increase within one block would require faster accelleration than the one, true
00165 //      constant acceleration.
00166 //
00167 // When these stages are complete all blocks have an entry_factor that will allow all speed changes to
00168 // be performed using only the one, true constant acceleration, and where no junction jerk is jerkier than
00169 // the set limit. Finally it will:
00170 //
00171 // 3. Recalculate trapezoids for all blocks.
00172 //
00173 void Planner::recalculate() {
00174    //this->kernel->serial->printf("recalculate last: %p, queue size: %d \r\n", this->kernel->player->queue.get_ref( this->kernel->player->queue.size()-1  ), this->kernel->player->queue.size() );
00175    this->reverse_pass();
00176    this->forward_pass();
00177    this->recalculate_trapezoids();
00178 }
00179 
00180 // Planner::recalculate() needs to go over the current plan twice. Once in reverse and once forward. This
00181 // implements the reverse pass.
00182 void Planner::reverse_pass(){
00183     // For each block
00184     int block_index = this->kernel->player->queue.tail;
00185     Block* blocks[3] = {NULL,NULL,NULL};
00186 
00187     while(block_index!=this->kernel->player->queue.head){
00188         block_index = this->kernel->player->queue.prev_block_index( block_index );
00189         blocks[2] = blocks[1];
00190         blocks[1] = blocks[0];
00191         blocks[0] = &this->kernel->player->queue.buffer[block_index];
00192         if( blocks[1] == NULL ){ continue; }
00193         blocks[1]->reverse_pass(blocks[2], blocks[0]);
00194     }
00195     
00196 }
00197 
00198 // Planner::recalculate() needs to go over the current plan twice. Once in reverse and once forward. This
00199 // implements the forward pass.
00200 void Planner::forward_pass() {
00201     // For each block
00202     int block_index = this->kernel->player->queue.head; 
00203     Block* blocks[3] = {NULL,NULL,NULL};
00204 
00205     while(block_index!=this->kernel->player->queue.tail){
00206         blocks[0] = blocks[1];
00207         blocks[1] = blocks[2];
00208         blocks[2] = &this->kernel->player->queue.buffer[block_index];
00209         if( blocks[0] == NULL ){ continue; }
00210         blocks[1]->forward_pass(blocks[0],blocks[2]);
00211         block_index = this->kernel->player->queue.next_block_index( block_index );
00212     } 
00213     blocks[2]->forward_pass(blocks[1],NULL);   
00214 
00215 }
00216 
00217 // Recalculates the trapezoid speed profiles for flagged blocks in the plan according to the
00218 // entry_speed for each junction and the entry_speed of the next junction. Must be called by
00219 // planner_recalculate() after updating the blocks. Any recalulate flagged junction will
00220 // compute the two adjacent trapezoids to the junction, since the junction speed corresponds
00221 // to exit speed and entry speed of one another.
00222 void Planner::recalculate_trapezoids() {
00223     int block_index = this->kernel->player->queue.head;
00224     Block* current;
00225     Block* next = NULL;
00226 
00227     while(block_index != this->kernel->player->queue.tail){
00228         current = next;
00229         next = &this->kernel->player->queue.buffer[block_index];
00230         //this->kernel->serial->printf("index:%d current:%p next:%p \r\n", block_index, current, next );
00231         if( current ){
00232             // Recalculate if current block entry or exit junction speed has changed.
00233             if( current->recalculate_flag || next->recalculate_flag ){
00234                 current->calculate_trapezoid( current->entry_speed/current->nominal_speed, next->entry_speed/current->nominal_speed );
00235                 current->recalculate_flag = false;
00236             }
00237         }
00238         block_index = this->kernel->player->queue.next_block_index( block_index ); 
00239     }
00240 
00241     // Last/newest block in buffer. Exit speed is set with MINIMUM_PLANNER_SPEED. Always recalculated.
00242     next->calculate_trapezoid( next->entry_speed/next->nominal_speed, MINIMUM_PLANNER_SPEED/next->nominal_speed); //TODO: Make configuration option
00243     next->recalculate_flag = false;
00244 
00245 }
00246 
00247 // Debug function
00248 void Planner::dump_queue(){
00249     for( int index = 0; index <= this->kernel->player->queue.size()-1; index++ ){
00250        if( index > 10 && index < this->kernel->player->queue.size()-10 ){ continue; }
00251        this->kernel->serial->printf("block %03d > ", index);
00252        this->kernel->player->queue.get_ref(index)->debug(this->kernel); 
00253     }
00254 }
00255 
00256 // Calculates the maximum allowable speed at this point when you must be able to reach target_velocity using the
00257 // acceleration within the allotted distance.
00258 double Planner::max_allowable_speed(double acceleration, double target_velocity, double distance) {
00259   return(
00260     sqrt(target_velocity*target_velocity-2L*acceleration*60*60*distance)  //Was acceleration*60*60*distance, in case this breaks, but here we prefer to use seconds instead of minutes
00261   );
00262 }
00263 
00264