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 
00011 #include "mri.h"
00012 #include "nuts_bolts.h"
00013 #include "RingBuffer.h"
00014 #include "Gcode.h"
00015 #include "Module.h"
00016 #include "Kernel.h"
00017 #include "Block.h"
00018 #include "Planner.h"
00019 #include "Conveyor.h"
00020 #include "StepperMotor.h"
00021 
00022 #define acceleration_checksum          CHECKSUM("acceleration")
00023 #define max_jerk_checksum              CHECKSUM("max_jerk")
00024 #define junction_deviation_checksum    CHECKSUM("junction_deviation")
00025 #define minimum_planner_speed_checksum CHECKSUM("minimum_planner_speed")
00026 
00027 // The Planner does the acceleration math for the queue of Blocks ( movements ).
00028 // It makes sure the speed stays within the configured constraints ( acceleration, junction_deviation, etc )
00029 // It goes over the list in both direction, every time a block is added, re-doing the math to make sure everything is optimal
00030 
00031 Planner::Planner(){
00032     clear_vector_float(this->previous_unit_vec);
00033     this->has_deleted_block = false;
00034 }
00035 
00036 void Planner::on_module_loaded(){
00037     register_for_event(ON_CONFIG_RELOAD);
00038     this->on_config_reload(this);
00039 }
00040 
00041 // Configure acceleration
00042 void Planner::on_config_reload(void* argument){
00043     this->acceleration =       THEKERNEL->config->value(acceleration_checksum       )->by_default(100.0F )->as_number(); // Acceleration is in mm/s^2, see https://github.com/grbl/grbl/commit/9141ad282540eaa50a41283685f901f29c24ddbd#planner.c
00044     this->junction_deviation = THEKERNEL->config->value(junction_deviation_checksum )->by_default(  0.05F)->as_number();
00045     this->minimum_planner_speed = THEKERNEL->config->value(minimum_planner_speed_checksum )->by_default(0.0f)->as_number();
00046 }
00047 
00048 
00049 // Append a block to the queue, compute it's speed factors
00050 void Planner::append_block( float actuator_pos[], float rate_mm_s, float distance, float unit_vec[] )
00051 {
00052     // Create ( recycle ) a new block
00053     Block* block = THEKERNEL->conveyor->queue.head_ref();
00054 
00055     // Direction bits
00056     block->direction_bits = 0;
00057     for (int i = 0; i < 3; i++)
00058     {
00059         int steps = THEKERNEL->robot->actuators[i]->steps_to_target(actuator_pos[i]);
00060 
00061         if (steps < 0)
00062             block->direction_bits |= (1<<i);
00063 
00064         // Update current position
00065         THEKERNEL->robot->actuators[i]->last_milestone_steps += steps;
00066         THEKERNEL->robot->actuators[i]->last_milestone_mm = actuator_pos[i];
00067 
00068         block->steps[i] = labs(steps);
00069     }
00070 
00071     // Max number of steps, for all axes
00072     block->steps_event_count = max( block->steps[ALPHA_STEPPER], max( block->steps[BETA_STEPPER], block->steps[GAMMA_STEPPER] ) );
00073 
00074     block->millimeters = distance;
00075 
00076     // Calculate speed in mm/sec for each axis. No divide by zero due to previous checks.
00077     // NOTE: Minimum stepper speed is limited by MINIMUM_STEPS_PER_MINUTE in stepper.c
00078     if( distance > 0.0F ){
00079         block->nominal_speed = rate_mm_s;           // (mm/s) Always > 0
00080         block->nominal_rate = ceil(block->steps_event_count * rate_mm_s / distance); // (step/s) Always > 0
00081     }else{
00082         block->nominal_speed = 0.0F;
00083         block->nominal_rate  = 0;
00084     }
00085 
00086     // Compute the acceleration rate for the trapezoid generator. Depending on the slope of the line
00087     // average travel per step event changes. For a line along one axis the travel per step event
00088     // is equal to the travel/step in the particular axis. For a 45 degree line the steppers of both
00089     // axes might step for every step event. Travel per step event is then sqrt(travel_x^2+travel_y^2).
00090     // To generate trapezoids with contant acceleration between blocks the rate_delta must be computed
00091     // specifically for each line to compensate for this phenomenon:
00092     // Convert universal acceleration for direction-dependent stepper rate change parameter
00093     block->rate_delta = (block->steps_event_count * acceleration) / (distance * THEKERNEL->stepper->acceleration_ticks_per_second); // (step/min/acceleration_tick)
00094 
00095     // Compute maximum allowable entry speed at junction by centripetal acceleration approximation.
00096     // Let a circle be tangent to both previous and current path line segments, where the junction
00097     // deviation is defined as the distance from the junction to the closest edge of the circle,
00098     // colinear with the circle center. The circular segment joining the two paths represents the
00099     // path of centripetal acceleration. Solve for max velocity based on max acceleration about the
00100     // radius of the circle, defined indirectly by junction deviation. This may be also viewed as
00101     // path width or max_jerk in the previous grbl version. This approach does not actually deviate
00102     // from path, but used as a robust way to compute cornering speeds, as it takes into account the
00103     // nonlinearities of both the junction angle and junction velocity.
00104     float vmax_junction = minimum_planner_speed; // Set default max junction speed
00105 
00106     if (!THEKERNEL->conveyor->queue.is_empty())
00107     {
00108         float previous_nominal_speed = THEKERNEL->conveyor->queue.item_ref(THEKERNEL->conveyor->queue.prev(THEKERNEL->conveyor->queue.head_i))->nominal_speed;
00109 
00110         if (previous_nominal_speed > 0.0F) {
00111             // Compute cosine of angle between previous and current path. (prev_unit_vec is negative)
00112             // NOTE: Max junction velocity is computed without sin() or acos() by trig half angle identity.
00113             float cos_theta = - this->previous_unit_vec[X_AXIS] * unit_vec[X_AXIS]
00114                                 - this->previous_unit_vec[Y_AXIS] * unit_vec[Y_AXIS]
00115                                 - this->previous_unit_vec[Z_AXIS] * unit_vec[Z_AXIS] ;
00116 
00117             // Skip and use default max junction speed for 0 degree acute junction.
00118             if (cos_theta < 0.95F) {
00119                 vmax_junction = min(previous_nominal_speed, block->nominal_speed);
00120                 // Skip and avoid divide by zero for straight junctions at 180 degrees. Limit to min() of nominal speeds.
00121                 if (cos_theta > -0.95F) {
00122                     // Compute maximum junction velocity based on maximum acceleration and junction deviation
00123                     float sin_theta_d2 = sqrtf(0.5F * (1.0F - cos_theta)); // Trig half angle identity. Always positive.
00124                     vmax_junction = min(vmax_junction, sqrtf(this->acceleration * this->junction_deviation * sin_theta_d2 / (1.0F - sin_theta_d2)));
00125                 }
00126             }
00127         }
00128     }
00129     block->max_entry_speed = vmax_junction;
00130 
00131     // Initialize block entry speed. Compute based on deceleration to user-defined minimum_planner_speed.
00132     float v_allowable = max_allowable_speed(-acceleration, minimum_planner_speed, block->millimeters); //TODO: Get from config
00133     block->entry_speed = min(vmax_junction, v_allowable);
00134 
00135     // Initialize planner efficiency flags
00136     // Set flag if block will always reach maximum junction speed regardless of entry/exit speeds.
00137     // If a block can de/ac-celerate from nominal speed to zero within the length of the block, then
00138     // the current block and next block junction speeds are guaranteed to always be at their maximum
00139     // junction speeds in deceleration and acceleration, respectively. This is due to how the current
00140     // block nominal speed limits both the current and next maximum junction speeds. Hence, in both
00141     // the reverse and forward planners, the corresponding block junction speed will always be at the
00142     // the maximum junction speed and may always be ignored for any speed reduction checks.
00143     if (block->nominal_speed <= v_allowable) { block->nominal_length_flag = true; }
00144     else { block->nominal_length_flag = false; }
00145 
00146     // Always calculate trapezoid for new block
00147     block->recalculate_flag = true;
00148 
00149     // Update previous path unit_vector and nominal speed
00150     memcpy(this->previous_unit_vec, unit_vec, sizeof(previous_unit_vec)); // previous_unit_vec[] = unit_vec[]
00151 
00152     // Math-heavy re-computing of the whole queue to take the new
00153     this->recalculate();
00154 
00155     // The block can now be used
00156     block->ready();
00157 
00158     THEKERNEL->conveyor->queue_head_block();
00159 }
00160 
00161 void Planner::recalculate() {
00162     Conveyor::Queue_t &queue = THEKERNEL->conveyor->queue;
00163 
00164     unsigned int block_index;
00165 
00166     Block* previous;
00167     Block* current;
00168 
00169     /*
00170      * a newly added block is decel limited
00171      *
00172      * we find its max entry speed given its exit speed
00173      *
00174      * for each block, walking backwards in the queue:
00175      *
00176      * if max entry speed == current entry speed
00177      * then we can set recalculate to false, since clearly adding another block didn't allow us to enter faster
00178      * and thus we don't need to check entry speed for this block any more
00179      *
00180      * once we find an accel limited block, we must find the max exit speed and walk the queue forwards
00181      *
00182      * for each block, walking forwards in the queue:
00183      *
00184      * given the exit speed of the previous block and our own max entry speed
00185      * we can tell if we're accel or decel limited (or coasting)
00186      *
00187      * if prev_exit > max_entry
00188      *     then we're still decel limited. update previous trapezoid with our max entry for prev exit
00189      * if max_entry >= prev_exit
00190      *     then we're accel limited. set recalculate to false, work out max exit speed
00191      *
00192      * finally, work out trapezoid for the final (and newest) block.
00193      */
00194 
00195     /*
00196      * Step 1:
00197      * For each block, given the exit speed and acceleration, find the maximum entry speed
00198      */
00199 
00200     float entry_speed = minimum_planner_speed;
00201 
00202     block_index = queue.head_i;
00203     current     = queue.item_ref(block_index);
00204 
00205     if (!queue.is_empty())
00206     {
00207         while ((block_index != queue.tail_i) && current->recalculate_flag)
00208         {
00209             entry_speed = current->reverse_pass(entry_speed);
00210 
00211             block_index = queue.prev(block_index);
00212             current     = queue.item_ref(block_index);
00213         }
00214 
00215         /*
00216          * Step 2:
00217          * now current points to either tail or first non-recalculate block
00218          * and has not had its reverse_pass called
00219          * or its calc trap
00220          * entry_speed is set to the *exit* speed of current.
00221          * each block from current to head has its entry speed set to its max entry speed- limited by decel or nominal_rate
00222          */
00223 
00224         float exit_speed = current->max_exit_speed();
00225 
00226         while (block_index != queue.head_i)
00227         {
00228             previous    = current;
00229             block_index = queue.next(block_index);
00230             current     = queue.item_ref(block_index);
00231 
00232             // we pass the exit speed of the previous block
00233             // so this block can decide if it's accel or decel limited and update its fields as appropriate
00234             exit_speed = current->forward_pass(exit_speed);
00235 
00236             previous->calculate_trapezoid(previous->entry_speed, current->entry_speed);
00237         }
00238     }
00239 
00240     /*
00241      * Step 3:
00242      * work out trapezoid for final (and newest) block
00243      */
00244 
00245     // now current points to the head item
00246     // which has not had calculate_trapezoid run yet
00247     current->calculate_trapezoid(current->entry_speed, minimum_planner_speed);
00248 }
00249 
00250 
00251 // Calculates the maximum allowable speed at this point when you must be able to reach target_velocity using the
00252 // acceleration within the allotted distance.
00253 float Planner::max_allowable_speed(float acceleration, float target_velocity, float distance) {
00254   return(
00255     sqrtf(target_velocity*target_velocity-2.0F*acceleration*distance)  //Was acceleration*60*60*distance, in case this breaks, but here we prefer to use seconds instead of minutes
00256   );
00257 }
00258 
00259