Logo Search packages:      
Sourcecode: pcb2gcode version File versions  Download package

surface.cpp

/*
 * This file is part of pcb2gcode.
 *
 * Copyright (C) 2009, 2010 Patrick Birnzain <pbirnzain@users.sourceforge.net>
 *
 * pcb2gcode 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.
 *
 * pcb2gcode 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.
 *
 * You should have received a copy of the GNU General Public License
 * along with pcb2gcode.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "surface.hpp"
using std::pair;

// color definitions for the ARGB32 format used

#define OPAQUE 0xFF000000
#define RED 0xFF0000FF
#define GREEN 0xFF00FF00
#define BLUE 0xFFFF0000
#define WHITE ( RED | GREEN | BLUE )
// while equal by value, OPAQUE is used for |-ing and BLACK for setting or comparison
#define BLACK ( RED & GREEN & BLUE )

void Surface::make_the_surface(uint width, uint height)
{
      pixbuf = Gdk::Pixbuf::create(Gdk::COLORSPACE_RGB,
                             true, 8, width, height);

      cairo_surface = Cairo::ImageSurface::create(pixbuf->get_pixels(),
                                        Cairo::FORMAT_ARGB32, width, height, pixbuf->get_rowstride());
}

#include <boost/foreach.hpp>

#include <iostream>
using std::cerr;
using std::endl;

#define PRC(x) *(reinterpret_cast<guint32*>(x))

Surface::Surface( guint dpi, ivalue_t min_x, ivalue_t max_x, ivalue_t min_y, ivalue_t max_y )
      : dpi(dpi), min_x(min_x), max_x(max_x), min_y(min_y), max_y(max_y),
        zero_x(-min_x*(ivalue_t)dpi + (ivalue_t)procmargin), zero_y(-min_y*(ivalue_t)dpi + (ivalue_t)procmargin), clr(32)
{
      guint8* pixels;
      int stride;
      make_the_surface( (max_x - min_x) * dpi + 2*procmargin, (max_y - min_y) * dpi + 2*procmargin );
      usedcolors.push_back(BLACK);
      usedcolors.push_back(WHITE);

      /* "Note that the buffer is not cleared; you will have to fill it completely yourself." */
      printf("clearing\n");
        pixels = cairo_surface->get_data();
        stride = cairo_surface->get_stride();
        for(int y = 0; y < pixbuf->get_height(); y++ )
        {
                for(int x = 0; x < pixbuf->get_width(); x++ )
                {
                        PRC(pixels + x*4 + y*stride) = BLACK;
                }
        }
}

void Surface::render( boost::shared_ptr<LayerImporter> importer ) throw(import_exception)
{
      importer->render(cairo_surface, dpi, min_x - static_cast<ivalue_t>(procmargin)/dpi,
                   min_y - static_cast<ivalue_t>(procmargin)/dpi );
}

#include <iostream>
using std::cout;
using std::endl;

using std::list;
double distancePointLine(const icoordpair &x,const icoordpair &la,const  icoordpair &lb)
{
      icoordpair nab; //normal vector to a-b= {-ab_y,ab_x}
      nab.first=-(la.second-lb.second);
      nab.second=(la.first-lb.first);
      double lnab=sqrt(nab.first*nab.first+nab.second*nab.second);
      double skalar; //product

      skalar=nab.first*(x.first-la.first)+nab.second*(x.second-la.second);
      return fabs(skalar/lnab );
}

void simplifypath(shared_ptr<icoords> outline, double accuracy)
{
      //take two points of the path
      // and their interconnecting path.
      // if the distance between all intermediate points and this line is smaller
      // than the accuracy, all the points in between can be removed..
      bool change;
      int lasterased=0;
      const bool debug=false;
      std::list<icoordpair> l;
      for(int i=0;i<outline->size();i++)
      {
            icoordpair &ii=(*outline)[i];
            l.push_back(ii);
      }

      if (debug) cerr<<"outline size:"<<outline->size()<<endl;
      int pos=0;
      do //cycle until no two points can be combined..
      {
            change=false;

            list<icoordpair>::iterator a=l.begin();
            do
            {
                  list<icoordpair>::iterator b,c;
                  b=a;b++;
                  c=b;c++;
                  if((b==l.end()))
                        break;
                  double d=distancePointLine(*b, *a,*c);
                  if((d<accuracy) )
                  {

                        if(debug) cerr<<"erasing at"<<pos<<" of "<<l.size()<<" d="<<d<<endl;
                        a=l.erase(b);
                        change=true;
                  }
                  else
                        a=b;
                  pos++;
            }while(a!=l.end());
            //change=false;
      }
      while(change);

      if(debug) cout<<"copying"<<endl;
      outline->resize(0);
      for( list<icoordpair>::iterator a=l.begin();a!=l.end();a++)
            outline->push_back(*a);
      if(debug) cerr<<"outline size:"<<outline->size()<<endl;

}


vector< shared_ptr<icoords> >
Surface::get_toolpath( shared_ptr<RoutingMill> mill, bool mirrored, bool mirror_absolute )
{
      Isolator* iso = dynamic_cast<Isolator*>(mill.get());
      int extra_passes = iso?iso->extra_passes:0;

      coords components = fill_all_components();

      int added = -1;
      int contentions = 0;
      int grow = mill->tool_diameter / 2 * dpi;
      ivalue_t double_mirror_axis = mirror_absolute ? 0 : (min_x + max_x);

      vector< shared_ptr<icoords> > toolpath;

      for( int pass = 0; pass <= extra_passes && added != 0; pass++ )
      {
            for(int i = 0; i < grow && added != 0; i++)
            {
                  added = 0;

                  BOOST_FOREACH( coordpair c, components ) {
                        added += grow_a_component(c.first, c.second, contentions);
                  }
            }

            coords inside, outside;

            BOOST_FOREACH( coordpair c, components ) {
                  calculate_outline( c.first, c.second, outside, inside );
                  inside.clear();

                  shared_ptr<icoords> outline( new icoords() );

                  // i'm not sure wheter this is the right place to do this...
                  // that "mirrored" flag probably is a bad idea.
                  BOOST_FOREACH( coordpair c, outside ) {
                        outline->push_back( icoordpair(
                                              // tricky calculations
                                              mirrored ? (double_mirror_axis - xpt2i(c.first)) : xpt2i(c.first),
                                              min_y + max_y - ypt2i(c.second) ) );
                  }

                  if(0) simplifypath(outline,0.005);
                  outside.clear();
                  toolpath.push_back(outline);
            }
      }

      if(contentions) {
            cerr << "Warning: pcb2gcode hasn't been able to fulfill all"
                 << " clearance requirements and tried a best effort approach"
                 << " instead. You may want to check the g-code output and"
                 << " possibly use a smaller milling width.\n";
      }

      save_debug_image("traced");
      return toolpath;
}

guint32 Surface::get_an_unused_color()
{
      bool badcol;
      do
      {
            badcol=false;
            clr = rand();

            for(int i=0;i<usedcolors.size();i++)
            {
                  if(usedcolors[i]==clr)
                  {
                        badcol=true;
                        break;
                  }
            }
      }while(badcol);
      usedcolors.push_back(clr);
      return clr;
}

//try to find white pixels, aka uncolored pixels, and do some floodfilling with a random color based on them.
//returns the list floodfill-seed points
std::vector< std::pair<int,int> > Surface::fill_all_components()
{
      std::vector< pair<int,int> > components;
      int max_x = cairo_surface->get_width() - 1;
      int max_y = cairo_surface->get_height() - 1;
      guint8* pixels = cairo_surface->get_data();
      int stride = cairo_surface->get_stride();

      for(int y = 0; y <= max_y; y ++)
      {
            for(int x = 0; x <= max_x; x ++)
            {
                  if( (PRC(pixels + x*4 + y*stride) | OPAQUE) == WHITE )
                  {
                        components.push_back( pair<int,int>(x,y) );
                        fill_a_component(x, y, get_an_unused_color());
                  }
            }
      }

      return components;
}

#include <stack>

// fill_a_component does not do any image boundary checks out of performance reasons.
void Surface::fill_a_component(int x, int y, guint32 argb)
{
      guint32 newclr = argb;

      guint8* pixels = cairo_surface->get_data();
      int stride = cairo_surface->get_stride();

      guint8* here = pixels + x*4 + y*stride;
      guint8* maxhere = pixels + (cairo_surface->get_width()-1)*4 + (cairo_surface->get_height()-1)*stride;

      guint32 ownclr = PRC(here);

      std::stack< pair<int, int> > queued_pixels;
      queued_pixels.push( pair<int, int>(x,y) );

      while( queued_pixels.size() )
      {
            pair<int,int> current_pixel = queued_pixels.top();
            x = current_pixel.first;
            y = current_pixel.second;
            queued_pixels.pop();

            here = pixels + x*4 + y*stride;
            PRC(here) = newclr;

            if( here+4 <= maxhere && PRC(here+4) == ownclr )
                  queued_pixels.push( pair<int,int>(x+1, y) );
            if( pixels <= here-4 && PRC(here-4) == ownclr )
                  queued_pixels.push( pair<int,int>(x-1, y) );
            if( here+stride <= maxhere && PRC(here+stride) == ownclr )
                  queued_pixels.push( pair<int,int>(x, y+1) );
            if( pixels <= here-stride && PRC(here-stride) == ownclr )
                  queued_pixels.push( pair<int,int>(x, y-1) );
            if( here+4+stride <= maxhere && PRC(here+4+stride) == ownclr )
                  queued_pixels.push( pair<int,int>(x+1, y+1) );
            if( here-4+stride <= maxhere && PRC(here-4+stride) == ownclr )
                  queued_pixels.push( pair<int,int>(x-1, y+1) );
            if( pixels <= here+4-stride && PRC(here+4-stride) == ownclr )
                  queued_pixels.push( pair<int,int>(x+1, y-1) );
            if( pixels <= here-4-stride && PRC(here-4-stride) == ownclr )
                  queued_pixels.push( pair<int,int>(x-1, y-1) );
      }

      cairo_surface->mark_dirty();
}

// starting from a pixel at xy within a "component" aka a blob of same-colored pixels, increase x until it is next to a new color
void Surface::run_to_border(int& x, int& y)
{
      guint8* pixels = cairo_surface->get_data();
      int stride = cairo_surface->get_stride();

      guint32 start_color = PRC(pixels + x*4 + y * stride);

      if( start_color == 0 ) {
            PRC(pixels + x*4 + y * stride) = RED;
            save_debug_image("error_runtoborder");
            std::stringstream msg;
            msg << "run_to_border: start_color == 0 at ("
                << x << "," << y << ")\n";
            throw std::logic_error( msg.str() );
      }

      while( PRC(pixels + x*4 + y*stride) == start_color )
            x++;
}

int offset8[8][2] = {{1,0}, {1,1}, {0,1}, {-1,1}, {-1,0}, {-1,-1}, {0,-1}, {1,-1}};
int offset4[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};

// true if free for growing components
inline bool Surface::allow_grow(int x, int y, guint32 ownclr)
{
      if(x <= 0 || y <= 0)
            return false;
      if(x >= cairo_surface->get_width()-1)
            return false;
      if(y >= cairo_surface->get_height()-1)
            return false;

      guint8* pixels = cairo_surface->get_data();
      int stride = cairo_surface->get_stride();

      for(int i = 7; i >= 0; i--)
      {
            int cx = x + offset8[i][0];
            int cy = y + offset8[i][1];

            guint8* pixel = pixels + cx * 4 + cy * stride;

            // surrounding pixel != own color, not black -> other component!
            if( PRC(pixel) != ownclr && ( PRC(pixel) | OPAQUE) != BLACK )
                  return false;
      }

      return true;
}

int growoff_o[3][3][2] =
{
      {{ 0,-1}, {-1,-1}, {-1,0}},
      {{ 1,-1}, { 0, 0}, {-1,1}},
      {{ 1, 0}, { 1, 1}, { 0,1}}
};

int growoff_i[3][3][2] =
{
      {{-1, 0}, {-1, 1}, {0, 1}},
      {{-1,-1}, { 0, 0}, {1, 1}},
      {{ 0,-1}, { 1,-1}, {1, 0}}
};

void Surface::calculate_outline(const int x, const int y,
                        vector< pair<int,int> >& outside, vector< pair<int,int> >& inside)
{
      guint8* pixels = cairo_surface->get_data();
      int stride = cairo_surface->get_stride();
      int max_y = cairo_surface->get_height();

      guint32 owncolor = PRC(pixels + x*4 + y*stride);

      int xstart = x;
      int ystart = y;

      run_to_border(xstart,ystart); //change xstart so that xstart++ would be outside of the component
      int xout = xstart;
      int yout = ystart;
      int xin = xout-1;
      int yin = yout;

      outside.push_back( pair<int,int>(xout, yout) );

      int blasts = 0;

      while(true)
      {
            int i;
            int steps = 0; // number of steps done in 1 iteration of the while loop

            // step outside
            for(i = 0; i < 8; i++)
            {
                  int xoff = xout - xin + 1;
                  int yoff = yout - yin + 1;
                  int xnext = xin + growoff_o[xoff][yoff][0];
                  int ynext = yin + growoff_o[xoff][yoff][1];

                  if(xnext == xstart && ynext == ystart)
                  {
                        outside.push_back( pair<int,int>(xout, yout) );
                        outside.push_back( pair<int,int>(xstart, ystart) );
                        return;
                  }

                  if(xnext<0 || ynext<0 || xnext>stride || ynext>max_y)
                  {
                        save_debug_image("error_outerpath");
                        std::stringstream msg;
                        msg << "Outside path reaches image margins at " << xin << "," << yin << ")\n";
                        throw std::logic_error( msg.str() );
                  }

                  guint8* next = pixels + xnext*4 + ynext*stride;

                  if( PRC(next) != owncolor )
                  {
                        outside.push_back( pair<int,int>(xout, yout) );
                        xout = xnext;
                        yout = ynext;
                  }
                  else
                        break;
            }
            if( i == 8 ) {
                  save_debug_image("error_outsideoverstepping");
                  std::stringstream msg;
                  msg << "Outside over-stepping at in(" << xin << "," << yin << ")\n";
                  throw std::logic_error( msg.str() );
            }

            steps += i;


            // step inside
            for(i = 0; i < 8; i++)
            {
                  int xoff = xin - xout + 1;
                  int yoff = yin - yout + 1;
                  int xnext = xout + growoff_i[xoff][yoff][0];
                  int ynext = yout + growoff_i[xoff][yoff][1];
                  // next pixel  is checked clockwise
                  guint8* next = pixels + xnext*4 + ynext*stride;
                  if(xnext<0  || ynext<0 || xnext>stride || ynext>max_y)
                  {
                        save_debug_image("error_innerpath");
                        std::stringstream msg;
                        msg << "Inside path reaches image margins at " << xin << "," << yin << ")\n";
                        throw std::logic_error( msg.str() );
                  }

                  if( PRC(next) == owncolor )
                  {
                        inside.push_back( pair<int,int>(xin, yin) );
                        xin = xnext;
                        yin = ynext;
                  }
                  else
                        break;
            }
            if( i == 8 ) {
                  save_debug_image("error_insideoverstepping");
                  std::stringstream msg;
                  msg << "Inside over-stepping at out(" << xout << "," << yout << ")\n";
                  throw std::logic_error( msg.str() );
            }

            steps += i;

            // check whether we made any progress calculating the trace outline.
            // if we haven't, our algorithm is deadlocked by stray pixels
            // we try to resolve this by enforcing the algorithm's constraints
            // for the components
            if( steps == 0 ) {
                  int changes = 0;
                  // test constraints for surrounding pixels, enforce if necessary
                  for(i = 0; i < 8; i++) {
                        int cx = xin + offset8[i][0];
                        int cy = yin + offset8[i][1];
                        guint8* pixel = pixels + cx * 4 + cy * stride;

                        if( allow_grow( cx, cy, owncolor) ) {
                              PRC(pixel) = owncolor;
                              changes++;
                        }
                        
                        // if a component pixel can't be reached non-diagonally, clear it
                        // even if it was set just now
                        int j;
                        for(j = 0; j < 4; j++) {
                              if( PRC( pixels + (cx + offset4[j][0]) * 4
                                     + (cy + offset4[j][1]) * stride )
                                  != BLACK ) break;
                        }
                        if( j == 4 ) {
                              PRC(pixel) = BLACK;
                              changes++;
                        }
                  }
                  if( allow_grow(xstart, ystart, owncolor) )
                        PRC(pixels+xstart*4+ystart*stride) = owncolor;
                  
                  if( changes == 0 ) {
                        PRC(pixels + xin*4 + yin*stride) |= RED;
                        PRC(pixels + xout*4 + yout*stride) |= BLUE;
                        save_debug_image("failed_repair");
                        std::stringstream msg;
                        msg << "Failed repairing @ (" << xin << "," << yin << ")\n";
                        throw std::logic_error( msg.str() );
                  } else
                        blasts++;

                  // start right at the beginning. still more efficient than keeping
                  // the history necessary to be able to continue next to the problem.
                  inside.clear();
                  outside.clear();
                  xstart = x;
                  ystart = y;
                  run_to_border(xstart,ystart);
                  xout = xstart;
                  yout = ystart;
                  xin = xout-1;
                  yin = yout;
                  outside.push_back( pair<int,int>(xout, yout) );
                  continue;
            }
      }

      fprintf(stderr, "blasts: %d", blasts);
}

guint Surface::grow_a_component(int x, int y, int& contentions)
{
      if( x < 0 || x >= cairo_surface->get_width() || y < 0 || y >= cairo_surface->get_height() ) {
            std::stringstream msg;
            msg << "grow_a_component(): invalid starting point: (" << x << "," << y << ")";
            throw std::logic_error( msg.str() );
      }

      contentions = 0;

      vector< pair<int,int> > outside, inside;
      calculate_outline(x, y, outside, inside);

      guint8* pixels = cairo_surface->get_data();
      int stride = cairo_surface->get_stride();

      uint pixels_changed = 0;

      guint32 ownclr = PRC(pixels + x*4 + y*stride);

      for(uint i = 0; i < outside.size(); i++)
      {
            pair<int,int> coord = outside[i];

            if( allow_grow(coord.first, coord.second, ownclr) )
            {
                  PRC(pixels + coord.first*4 + coord.second*stride) = ownclr;
                  pixels_changed++;
            } else {
                  contentions++;
            }
      }



      return pixels_changed;
}

void Surface::add_mask( shared_ptr<Surface> mask_surface) {
      Cairo::RefPtr<Cairo::ImageSurface> mask_cairo_surface = mask_surface->cairo_surface;

      int max_x = cairo_surface->get_width();
      int max_y = cairo_surface->get_height();
      int stride = cairo_surface->get_stride();

      if(
            max_x != mask_cairo_surface->get_width() ||
            max_y != mask_cairo_surface->get_height() ||
            stride != mask_cairo_surface->get_stride()
            ) {
            throw std::logic_error( "Surface shapes don't match." );
      }

      guint8* pixels = cairo_surface->get_data();
      guint8* mask_pixels = mask_cairo_surface->get_data();

      for(int y = 0; y < max_y; y ++)
      {
            for(int x = 0; x < max_x; x ++)
            {
                  PRC(pixels + x*4 + y*stride) &= PRC(mask_pixels + x*4 + y*stride); /* engrave only on the surface area */
                  PRC(pixels + x*4 + y*stride) |= (~PRC(mask_pixels + x*4 + y*stride) & (RED | BLUE)); /* tint the outiside in an own color to block extension */
            }
      }
}

#include <boost/format.hpp>

void Surface::save_debug_image(string message)
{
      static uint debug_image_index = 0;

      opacify(pixbuf);
      pixbuf->save( (boost::format("outp%1%_%2%.png") % debug_image_index % message).str() , "png");
      debug_image_index++;
}

void Surface::opacify( Glib::RefPtr<Gdk::Pixbuf> pixbuf )
{
      int stride = pixbuf->get_rowstride();
      guint8* pixels = pixbuf->get_pixels();
      for(int y = 0; y < pixbuf->get_height(); y++ )
      {
            for(int x = 0; x < pixbuf->get_width(); x++ )
            {
                  PRC(pixels + x*4 + y*stride) |= OPAQUE;
            }
      }
}

void Surface::fill_outline ( double linewidth )
{
      /* paint everything white that can not be reached from outside the image */

      int stride = pixbuf->get_rowstride();
      guint8* pixels = pixbuf->get_pixels();

      /* in order to find out what is "outside", we need to walk "around' the image */
      for(int x = 0; x < pixbuf->get_width(); x++ )
      {
            if(PRC(pixels + x*4 + 0*stride) != BLACK) throw std::logic_error( "Non-black pixel at top border" );
            if(PRC(pixels + x*4 + (pixbuf->get_height() - 1)*stride) != BLACK) throw std::logic_error( "Non-black pixel at bottom border" );
      }
      for(int y = 0; y < pixbuf->get_height(); y++ )
      {
            if(PRC(pixels + 0*4 + y*stride) != BLACK) throw std::logic_error( "Non-black pixel at left border" );
            if(PRC(pixels + (pixbuf->get_width() - 1)*4 + y*stride) != BLACK) throw std::logic_error( "Non-black pixel at right border" );
      }

      fill_a_component(0, 0, BLUE);

      /* everything else (that is, the area of the board) will be black
       *
       * saving the line where black starts for later when we need something
       * black so grow's run_to_border can work.
       */
      int first_line_with_black = 0;
      for(int y = 0; y < pixbuf->get_height(); y++ )
      {
            for(int x = 0; x < pixbuf->get_width(); x++ )
            {
                  if(PRC(pixels + x*4 + y*stride) != BLUE) {
                        PRC(pixels + x*4 + y*stride) = BLACK;
                        if(first_line_with_black == 0) {
                              first_line_with_black = y;
                        }
                  } 
            }
      }

      /* compensate for growth induced by line thicknesses.
       *
       * this could be done by growing the outline by a reduced amount later
       * (providing the lines are not wider than the tool), but by doing the
       * reduction now, the lines are already compensated for in the masking
       * step. thus, the engraving bit will really engrave once around the
       * outline instead of engraving in an area that is going to be removed,
       * potentially creating neater edges and providing a more realistic
       * rendition in png and gcode previews.
       */
      int grow = linewidth / 2 * dpi;
      int contentions = 0;
      int added = 0;
      for(int i = 0; i < grow; ++i)
      {
            // starting at the very left 
            added = grow_a_component(0, first_line_with_black + grow, contentions);
      }
      // if you can think of a sane situation in which either of this could
      // occur and nevertheless give a meaningful result, change it to a
      // warning.
      if(!added) throw std::logic_error( "Shrinking the outline by half the line width came to a halt." );
      if(contentions) throw std::logic_error( "Shrinking the outline collided with something while there should not be anything." );

      for(int y = 0; y < pixbuf->get_height(); y++ )
      {
            for(int x = 0; x < pixbuf->get_width(); x++ )
            {
                  if(PRC(pixels + x*4 + y*stride) == BLUE)
                        PRC(pixels + x*4 + y*stride) = BLACK;
                  else
                        PRC(pixels + x*4 + y*stride) = WHITE;
            }
      }

      save_debug_image("outline_filled");
}

Generated by  Doxygen 1.6.0   Back to index