Custom draw line function, why does coordinate orientation slow down the program?

Programming Questions

demiguel...

Custom draw line function, why does coordinate orientation slow down the program?

in Programming Questions • 1 year ago

I am writting my own draw line function in processing to improve speed when drawing large sets of lines from vector file (just a .txt with a bunch of coordinates that draw the map of seville). I am using the method pixel[int] to build such function but for some reason that i can not explain the program goes really fast when i enter the coordinates like this: drawline(y1,x1,y2,x2) but quite slow when its how its supposed to be: drawline(x1,y1,x2,y2) Is there a logical explanation for this?

The structure of the .txt code is simple and it goes like this: folder

The code of the Processing 1.5.1 sketch is below together with the structure of the .txt file, i have shortened it as much as possible and made it as tidy as I could. Thanks for the help!

1188156570;1188156570;37.417595;-5.9971519
1188156400;1188156400;37.4175115;-5.9970483
1188156720;1188156720;37.4174588;-5.9969338
1188156606;1188156606;37.4175833;-5.9966021
1188156462;1188156462;37.4177174;-5.9960534
1188156753;1188156753;37.4177413;-5.9958605
1188156643;1188156643;37.417703;-5.9955831
1132983943;1132983943;37.4176646;-5.995381
next
304791377;304791377;37.3968538;-6.0066269
1188156644;1188156644;37.3967509;-6.0064412
1188156521;1188156521;37.3956275;-6.0073602
next
1188216699;1188216699;37.4221365;-5.9959761
693311201;693311201;37.4253619;-5.9951655
1188216625;1188216625;37.4239123;-5.9924734
1188216567;1188216567;37.4233085;-5.9916937
1186512382;1186512382;37.4223597;-5.9910465
1188216642;1188216642;37.4216335;-5.9927836
1188216699;1188216699;37.4221365;-5.9959761
next

String[] polylines;
String[] streetArray=new String[0];
String[] empty=new String[0];
ArrayList vlist=new ArrayList();
float panX; float panY;

void setup() {
  size(600, 600);
  polylines=loadStrings("data/MapSeville.txt");
  panX=0; panY=0;
  prepare();
}

void draw() {
  background(255);
  PVector pan = pan();
  panX=panX+pan.x;
  panY=panY+pan.y;

  loadPixels();
  for(int i=0;i<vlist.size();i++){
    vertexgroup vg= (vertexgroup) vlist.get(i);
    for(int j=1;j<vg.listcoord.size();j++){
      Vertice v2=(Vertice) vg.listcoord.get((j-1));
      Vertice v1=(Vertice) vg.listcoord.get(j);
      float x1=v1.coord.x+panX;
      float y1=v1.coord.y+panY;
      float x2=v2.coord.x+panX;
      float y2=v2.coord.y+panY;
      drawline(x1, y1, x2, y2);//slow :( comment out this line and enable the next to see how smooth it can go
      //drawline(y1, x1, y2, x2);//fast!
    }
  } 
  updatePixels();
}

////////////////////////////// functions ////////////////////////////////////////////////

PVector pan(){
  PVector p;
  if (mousePressed){
    p = new PVector(mouseX-pmouseX, mouseY-pmouseY);
  }else{
    p=new PVector(0,0);
  }
  return p;
}

////////////////////

void drawline(float x1, float y1, float x2, float y2){
  int X1=int(x1);
  int X2=int(x2);
  color pink = color(0);
    if((X2>X1)){
      for (int i=0; i<=int(x2-x1); i++){ 
        if (((i+X1)>=0)&&((i+X1)<=width)){
          int g=int(y1+((y2-y1)/(x2-x1))*i)*(width) + i + X1;
          if ((g<width*height)&&(g>=0)){
            pixels[g]=pink;
          }
        }
      }
    }else if((X2<X1)){
      for (int i=0; i<=int(x1-x2); i++){
        if (((i+X2)>=0)&&((i+X2)<=width)){
          int f=int(y2+((y2-y1)/(x2-x1))*i)*(width) + i + X2;
          if ((f<width*height)&&(f>=0)){
            pixels[f]=pink; 
        }
      }
    }  
  }
}

//////////////////////////////

 void prepare(){
  for (int i=1;i<polylines.length;i++) {
    String[] pts = split(polylines[i], ";");

    if (pts.length>3) {
      streetArray=append(streetArray, polylines[i]); //adds coords strings to the array streetArray
    }
    if (pts.length==1) { //this is when the coords of a polyline ends: pts[0]==>"next" 
        vertexgroup vgroup;
        vgroup=new vertexgroup(create_polyArr(streetArray)); // this function is defined right below
        vlist.add(vgroup);
        streetArray=empty;
    }}}

    ArrayList create_polyArr(String[] streetpts) {
    ArrayList arrpts=new ArrayList();
    arrpts.clear();

    for (int i=0;i<streetpts.length;i++){ //iterates through coords strings of the polyline contained in streetpts
      String[] pts = split(streetpts[i], ";");
      float x=float(pts[3]);//get the x coord
      float y=float(pts[2]);//get the y coord
      x=((x+5.95)*15000+width/2);//scale and center coord x
      y=((-y+37.40)*15000+height/2);//scale and center coord y
      PVector coord=new PVector(x,y);
      Vertice govertex=new Vertice(coord);
      arrpts.add(govertex);
    }
    return(arrpts);
  }

 ////////////////////// end functions //////////////////////////////////

 //////////////////////// classes ///////////////////////////////////////

 class vertexgroup{

  ArrayList listcoord;

  vertexgroup(ArrayList _listcoord){
    listcoord=_listcoord;
  }}

  //////////

  class Vertice{

  PVector coord;

  Vertice(PVector _coord){
    coord=_coord;
  }}

  ////////////////////// end classes ///////////////////////////////////////

Update# I have uploaded both versions to my website on processing.js, now the fast version works more or smooth ok and the slow one simply doesnt move at all. See here: [fast]( http://417i.com/StackOverflow/FastMap/) and [slow]( http://417i.com/StackOverflow/SlowMap/)

Replies(10)

benja

Re: Custom draw line function, why does coordinate orientation slow down the program?

1 year ago

Hi,
i tested both versions and they seem to have the same speed. ( about 30 fps on my macbook with osx 10.5.8).

Just one thing about ArrayLists: If you use the typed version ...

ArrayList<vertexgroup> vlist=new ArrayList<vertexgroup>();

.. then you don't have to cast each time you use them:

vertexgroup vg= vlist.get(i);

And maybe start classnames with capital-letters to make convention-lovers happy ;)

demiguel...

Re: Re: Custom draw line function, why does coordinate orientation slow down the program?

1 year ago

hi benja, thx for the tips, i didnt know abt the typed version of arraylists, im sure it will make my life much easier : )

and convention for classnames accepted...

regarding the question, i really get les than 5-10 frames per second in the slow version, and like u said around 30 in the fast one. might only work in macs?

btw, have u seen the uploaded versions? ()those are online and working from a server... they have a big speed difference... and i really just changed the order of the coordinates. now im really lost : (

[fast]( http://417i.com/StackOverflow/FastMap/) and [slow]( http://417i.com/StackOverflow/SlowMap/)

additionally u can check the speed by clicking and dragging the mouse to pan over the map.

would be great if u could take a look at these thanks!

benja

Re: Custom draw line function, why does coordinate orientation slow down the program?

1 year ago

You are right, there is a difference when i look at the online-version.
When i run the code with the text-file from your online-example, then i get the same result. So it depends on the data you draw.

I saw that you draw one point for each x-value for every line.
So there are more points, if you have more horizontal lines. And dpeneding on the number of horizontal anf vertical lines, your code runs faster or slower.

demiguel...

Re: Re: Custom draw line function, why does coordinate orientation slow down the program?

1 year ago

Strangely enough it seems that the balance vertical-horizontal is worse (more horizontal) in the fast version.

I have printed out the number of pixels each of the versions are actually drawing, hope i didnt miscalculate, below are the details:

Total pixels drawn:

767350 pixels => fast version

664550 pixels => slow version

code to calculate number of pixels drawn:

line 5 (before setup()) ==> int count;

line 12 (inside setup()) ==> count=0;

and then function drawline just adds the counter:

void drawline(float x1, float y1, float x2, float y2){
int X1=int(x1);
int X2=int(x2);
color pink = color(0);
if((X2>X1)){
for (int i=0; i<=int(x2-x1); i++){
if (((i+X1)>=0)&&((i+X1)<=width)){
int g=i(y1+((y2-y1)/(x2-x1))*i)*(width) + i + X1;
if ((g<width*height)&&(g>=0)){
pixels[g]=pink;
count=count+1;
}
}
}
}else if((X2<X1)){
for (int i=0; i<=int(x1-x2); i++){
if (((i+X2)>=0)&&((i+X2)<=width)){
int f=int(y2+((y2-y1)/(x2-x1))*i)*(width) + i + X2;
if ((f<width*height)&&(f>=0)){
pixels[f]=pink;
count=count+1;
}
}
}
}
}

After ur hint I have changed the column order in the text file and then its the other way round, slow version goes fast and viceversa, so i think u pointed out a good clue because it definitely seems to be related to the data i draw from, but still i cant tell what it is exactly.

benja

Re: Custom draw line function, why does coordinate orientation slow down the program?

1 year ago

You are right, there is not a huge difference between the pixels, that are actually drawn.
But if you compare the number of loops that are executed within drawline(), then you will notice a significant difference.
Just moved the incrementation of "count" up to the beginning of the for-loop.

void drawline(float x1, float y1, float x2, float y2){
int X1=int(x1);
int X2=int(x2);
color pink = color(0);
    if((X2>X1)){
      for (int i=0; i<=int(x2-x1); i++){
        count++;
        if (((i+X1)>=0)&&((i+X1)<=width)){
          int g=int(y1+((y2-y1)/(x2-x1))*i)*(width) + i + X1;
          if ((g<width*height)&&(g>=0)){
            pixels[g]=pink;
          }
        }
      }
    }else if((X2<X1)){
      for (int i=0; i<=int(x1-x2); i++){
        count++;
        if (((i+X2)>=0)&&((i+X2)<=width)){
          int f=int(y2+((y2-y1)/(x2-x1))*i)*(width) + i + X2;
          if ((f<width*height)&&(f>=0)){
            pixels[f]=pink;
        }
      }
    }
}
}

fast version: 298.580 loops
slow version: 45.848.721 loops

benja

Re: Custom draw line function, why does coordinate orientation slow down the program?

1 year ago

just an idea to improve performance:
If both x-values are out of the screen, then just return from the drawline-function.
I changed the beginning of your drawline-function to this:

void drawline(float x1, float y1, float x2, float y2){
int X1=int(x1);
int X2=int(x2);
if (((X1<0) && (X2<0)) || ((X1>width) && (X2>width)) || ((y1<0) && (y2<0)) || ((y1>height) && (y2>height))) {

return;
}
[ ... ]

With that change, both version have about 40 fps.

edit: of course you should check for y-coordinates too, i changed the code.

demiguel...

Re: Re: Custom draw line function, why does coordinate orientation slow down the program?

1 year ago

it works like if it were magic! thanks a lot, i never thought the out-bounds would make such a big diference but since its pixel based it makes sense, now if i zoom out and see the whole map at once (case when the code draws all the lines - there are no lines out-bound) it still goes really fast!

ps. what do u think in general of this approach to draw vector data (i still have to work on making the lines more beautiful...)?

benja

Re: Custom draw line function, why does coordinate orientation slow down the program?

1 year ago

I like to see different ways to solve problems. And replacing native functions with custom ones can be very helpful, when optimizing for good performance.
One possible improvement could be to check if the lines are closer to a horizontal line or a vertical line. And iterate over y-coordinates instead of x-coordinates if they are more vertical. This way the vertical would not only consist out of a few points.

demiguel...

Re: Re: Custom draw line function, why does coordinate orientation slow down the program?

1 year ago

Yeah, that´ll be the next step, and then some antialiasing too, will need good luck for that!

oh, i posted the question on stackoverflow too, and there´s still no right answer - no idea wether u are interested in SO reputation but if u paste ur answer there i will click accepted.

http://stackoverflow.com/questions/12111906/custom-draw-line-function-why-does-coordinate-orientation-slow-down-the-program

Will keep the thread posted on the antialias stuff.

demiguel...

Re: Custom draw line function, why does coordinate orientation slow down the program?

1 year ago

Hi there, not sure if i should rather post this under "share ur work" but anyways i got some more or less decent antialias working, its good for strokeWeights between 0.5 and 1.2, its pretty fast i think... but would love to improve it further if any ideas :)

void drawline(float x1, float y1, float x2, float y2, float strokeW, color mycolor) { //optimized for stroke weights ranging from 0.5 to 1.2, decimal values dont decrease speed.
int X1=int(x1+0.5); int Y1=int(y1+0.5);
int X2=int(x2+0.5); int Y2=int(y2+0.5);
if(((X1<0)&&(X2<0))||((X1>width)&&(X2>width))||((y1<0)&&(y2<0))||((y1>height)&&(y2>height))){return;} // exit if points are off bounds
/*
int sW=int(100*strokeW);
int[] src={ -sW/2, -sW/2+10, -50, 50, sW/2-10, sW/2 };int[] steps = new int[2];// these 4 lines need improvement to avoid 45 degrees related problems.
if((sW<140)&&(sW>100)){steps=expand(steps,4);arrayCopy(src,0,steps,0,1);arrayCopy(src,2,steps,1,2);arrayCopy(src,5,steps,3,1);// what a nightmare, cant processing do better with arrays??
}else if(sW<=100){arrayCopy(src,0,steps,0,1);arrayCopy(src,src.length-1,steps,1,1);}else{steps=expand(steps,6);arrayCopy(src,steps);}
*/
PVector myline=new PVector(x2-x1, y2-y1);
PVector perp=new PVector(y2-y1, -(x2-x1));
float ex=x2-x1; float ey=y2-y1; float mx=ey/ex; float my=ex/ey;
perp.normalize(); PVector minusperp=PVector.mult(perp,-1);
int a=0;int b=0;int c=1;
if(abs(ey/ex)<=1){ //less than 45 degrees we iterate over x, else over y.
if ((X2>X1)){a=1;}else if(X2<X1){b=1;c=-1;}
for (int x=0; x<=int(c*(x2-x1)+0.5); x++){
float yline=mx*x+y1*a+y2*b;
float xline=x;
if (((x+X1*a+X2*b)>=0)&&((x+X1*a+X2*b)<width)&&(yline>=0)&&(yline<height)){
//for (int k=0;k<steps.length;k++) {//10 for strokeW==2, seems 20 already gives gaps between lines. If strokeW==1 then 50 is enough
for (int k=-50;k<=50;k=k+100) {
//PVector offsvec=PVector.mult(perp, steps[k]/100.0); //these divisions take time, possible to get rid of them?
PVector offsvec=PVector.mult(perp, k/100.0);
float offsetx=xline+offsvec.x;
float offsety=yline+offsvec.y;
int gx=int(offsetx+0.5);//gx and gy are the real coords of the pixel offsettes from the line
int gy=int(offsety+0.5);
int gt=gy*width+gx+X1*a+X2*b;
if((gt<width*height)&&(gt>=0)){ //reduce memory use: give him the product done already // could this move above the for loop? - danger of pixel array out of bounds
PVector trueoffsvec=new PVector(gx-xline, gy-yline);
float distance=abs(trueoffsvec.dot(perp));
float blendval=distance-(strokeW/2-0.5);
color origc=pixels[gy*width+gx+X1*a+X2*b];
float rval=red(mycolor)-blendval*(red(mycolor)-red(origc));// reduce memory use: give him the division done already strokeW/2
float gval=green(mycolor)-blendval*(green(mycolor)-green(origc));
float bval=blue(mycolor)-blendval*(blue(mycolor)-blue(origc));
// rval=constrain(rval, 0, 255);gval=constrain(gval, 0, 255);bval=constrain(bval, 0, 255);//no need for this line
color colorval=color(rval,gval,bval);
pixels[gy*width+gx+X1*a+X2*b]=colorval;
}
}
}
}
}else{ //here we iterate over y.
if ((Y2>Y1)){a=1;}else if(Y2<Y1){b=1;c=-1;}
for (int y=0; y<=int(c*(y2-y1)+0.5); y++){
float xline=my*y+x1*a+x2*b;
float yline=y;
if (((y+Y1*a+Y2*b)>=0)&&((y+Y1*a+Y2*b)<height)&&((xline>=0)&&(xline<width))){
//for (int k=0;k<steps.length;k++) {//10 for strokeW==2, seems 20 already gives gaps between lines. If strokeW==1 then 50 is enough
for (int k=-50;k<=50;k=k+100) {
//PVector offsvec=PVector.mult(perp, steps[k]/100.0); //these divisions take time, possible to get rid of them?
PVector offsvec=PVector.mult(perp, k/100.0);
float offsetx=xline+offsvec.x;
float offsety=yline+offsvec.y;
int gx=int(offsetx+0.5);//gx and gy are the real coords of the pixel offsettes from the line
int gy=int(offsety+0.5);
int gt=(gy+Y1*a+Y2*b)*width+gx;
if((gt<width*height)&&(gt>=0)){ //could this move above the for loop? - danger of pixel array out of bounds
PVector trueoffsvec=new PVector(gx-xline, gy-yline);
float distance=abs(trueoffsvec.dot(perp));
float blendval=distance-(strokeW/2-0.5);
color origc=pixels[(gy+Y1*a+Y2*b)*width+gx];
float rval=red(mycolor)-blendval*(red(mycolor)-red(origc));// reduce memory use: give him the division done already strokeW/2
float gval=green(mycolor)-blendval*(green(mycolor)-green(origc));
float bval=blue(mycolor)-blendval*(blue(mycolor)-blue(origc));
// rval=constrain(rval, 0, 255);gval=constrain(gval, 0, 255);bval=constrain(bval, 0, 255);//no need for this line
color colorval=color(rval,gval,bval);
pixels[(gy+Y1*a+Y2*b)*width+gx]=colorval;
}
}
}
}
}
}

Top Reply