DrawLine's clipping performance test

[Monsieur OUXX]

I'm currently working on a tool that requires me to draw very large straight lines onto a small drawing surface. For example, lines that go from coordinates (-5000,-5000) to (5000,5000), onto a 320x200 DrawingSurface. That allows me to draw a grid onto a canvas, as well as vanishing lines (they go very far on the sides of the image).

I've tested how long it takes to simply use DrawLine, and I came to the conculsion that it is very long, because there seems to be no clipping or coordinates checking built into AGS. All tests done in a 32-bits game with Direct3D9.

Here is the sample code:

Code: ags

    int limit = 500000;
    int i;
    bool hasAlpha = false;
    DynamicSprite* ds=DynamicSprite.Create(320, 200, hasAlpha);
    DrawingSurface* s = ds.GetDrawingSurface();
    
    //STEP 1 : takes 19s
    Display("Click when ready for step 1.");
    i=0;
    while (i<limit)
    {
       s.DrawLine(-3200,  -2000,  3200,  2000);
       i++;
    }
    
    //STEP 2 : takes 3s
    Display("Click when ready for step 2.");
    i=0;
    while (i<limit)
    {
       s.DrawLine(0,  0,  320,  200);
       i++;
    }

    //STEP 3 : takes 10s
    Display("Click when ready for step 3.");
    i=0;
    while (i<limit)
    {
       s.DrawLine2( -3200,  -2000,  3200,  2000,  COLOR_LIGHTGRAY);
       i++;
    }
    
    //FINISH
    Display("All over.");
    s.Release();
    ds.Delete();

As you can see, step 1 (with the big coordinates) takes 19s versus 3s with "clipped" coordinates. That's 6 times longer.
Now you'll see that I can reduce it to 10s (so about 50% performance gain) by using my very own clipping function, a.k.a. DrawLine2, relying on some C implementation that I've found on the web :

Spoiler

Code: ags

 
// "Cohen Sutherland" line clipping. 
//  It draws only the part of the line that is within the viewport.
//
// Originally found at http://electrofriends.com/source-codes/software-programs/c/graphics/c-program-to-implement-the-cohen-sutherland-line-clipping-algorithm/
// credits ???

enum outcode {
  TOP = 1, 
  BOTTOM=2, 
  RIGHT=4, 
  LEFT=8
};

int compute_outcode(float x, float y, 		float xmin, float ymin, float xmax, float ymax)
{
  int oc = 0;

  if (y > ymax)
    oc = oc | TOP;
  else if (y < ymin)
    oc = oc | BOTTOM;


  if (x > xmax)
    oc = oc | RIGHT;
  else if (x < xmin)
    oc = oc | LEFT;

  return oc;
}

void DrawLine2(this DrawingSurface*,  int xx1,  int yy1, int xx2,  int yy2,  int color)
{
  
    int c = this.DrawingColor;
    this.DrawingColor = color;
  
    float xmin = 0.0;  float ymin = 0.0; float xmax = IntToFloat(this.Width); float ymax = IntToFloat(this.Height); 
    float x1 = IntToFloat(xx1); float x2 = IntToFloat(xx2); float y1 = IntToFloat(yy1); float y2 = IntToFloat(yy2);
    
    bool accept = false;
    bool done = false;

    int outcode1 = compute_outcode (x1, y1, xmin, ymin, xmax, ymax);
    int outcode2 = compute_outcode (x2, y2, xmin, ymin, xmax, ymax);
    while (!done)
    {
      
        if (outcode1 == 0 && outcode2 == 0)
        {
            accept = true;
            done = true;
        }
        else if (outcode1 & outcode2)
        {
            done = true;
        }
        else
        {
            float x, y;
            int outcode_ex;
            if (outcode1!= 0) outcode_ex = outcode1; else outcode_ex = outcode2;
            
            if (outcode_ex & TOP)
            {
              x = x1 + (x2 - x1) * (ymax - y1) / (y2 - y1);
              y = ymax;
            }
       
            else if (outcode_ex & BOTTOM)
            {
              x = x1 + (x2 - x1) * (ymin - y1) / (y2 - y1);
              y = ymin;
            }
            else if (outcode_ex & RIGHT)
            {
              y = y1 + (y2 - y1) * (xmax - x1) / (x2 - x1);
              x = xmax;
            }
            else
            {
              y = y1 + (y2 - y1) * (xmin - x1) / (x2 - x1);
              x = xmin;
            }
            if (outcode_ex == outcode1)
            {
              x1 = x;
              y1 = y;
              outcode1 = compute_outcode (x1, y1, xmin, ymin, xmax, ymax);
            }
            else
            {
              x2 = x;
              y2 = y;
              outcode2 = compute_outcode (x2, y2, xmin, ymin, xmax, ymax);
            }
        }
    }
 
    if (accept)
      this.DrawLine(FloatToInt(x1), FloatToInt(y1), FloatToInt(x2), FloatToInt(y2));

}

[close]

Now I can't think of any possible scenario where that would be useful to ANYBODY (or maybe crazy people like Radiant, who make vector-based games ) but I thought I'd share.
If some day the C++ team felt like implementing the boundaries check, then it's all ready to use, out of the box.

EDIT: I've gained less than 1 second by putting the code of "compute_outcome" inline (directly where it's called), so the benefit is insignificant.

[selmiak]

maybe digging into the released sourcecode of the art of dying by dkh will help. The level editor is pretty nifty and had long line drawing functions.

[Monsieur OUXX]

maybe digging into the released sourcecode of the art of dying by dkh will help. The level editor is pretty nifty and had long line drawing functions.

I didn't know that the source code is public and never noticed it has a level editor! (the demo was too hard for me, I gave up) (I'm not good at platformers). I'm going to look into this.


EDIT: I looked at the source and didn't find any "long line" drawing routine. Only regular lines to draw short things like rectangles and such.

[Crimson Wizard]

there seems to be no clipping or coordinates checking built into AGS.

If there were not, the pixels would be drawn outside of bitmap in memory...
The question is rather what Allegro library is doing when coordinates are beyond the bitmap bounds. For example, it could do similar calculations, but with less efficient algorithm. But this is something to be investigated.

[Monsieur OUXX]

If there were not, the pixels will be drawn outside of bitmap in memory...

Well yeah by my tests clearly show that the computing time is proportional to the actual length of the line, regardless of the boundaries. So I guess the test is done at the very end, after computing each pixel's coordinates individually.

[Crimson Wizard]

If there were not, the pixels will be drawn outside of bitmap in memory...

Well yeah by my tests clearly show that the computing time is proportional to the actual length of the line, regardless of the boundaries. So I guess the test is done at the very end, after computing each pixel's coordinates individually.

Yes, it apparently does so, from the looks of the library code.



E:
Allegro has 2 line drawing functions: a non-clipping line and "Cohen-Sutherland line clipping". There is also a warning that the latter is less precise.
AGS always calls the first one. Perhaps the solution would be to create a new script function, e.g. FastLine() that would call the clipping version?

[Crimson Wizard]

Alright, please try this out:
http://www.mediafire.com/download/2qudq8c9qeh5g6n/ags-3.3.5--fastline-test.7z

I exported Allegro's fastline() function as DrawingSurface.DrawFastLine(). It reduces the Step 1 of your example to about 5 seconds.

[Monsieur OUXX]

Alright, please try this out:
http://www.mediafire.com/download/2qudq8c9qeh5g6n/ags-3.3.5--fastline-test.7z

I exported Allegro's fastline() function as DrawingSurface.DrawFastLine(). It reduces the Step 1 of your example to about 5 seconds.

Yes indeed, it's much faster.

However, I *HATE* to say that (trust me, I really do), but I'm not sure it's a good idea to have two DrawLine functions. The reason why the second one is faster might be lost to less "educated" scripters, and actually add confusion because they wouldn't know when not to use it (not to mention, maintenance: documentation, etc.). I know that if I was you, I'd be supremely annoyed that my immediate feature implementation is rejected by the very person who suggested it. But I'm really being honest.

I'd like to know the opinion of the community on this.

[Monsieur OUXX]

....or maybe it's OK, but you'd need to add this to the documentation:

FastLine


DrawingSurface.FastLine(int from_x, int from_y, int to_x, int to_y,
                        optional int thickness)

A variation of function "DrawLine" that can draw the line faster under some specific conditions. Draws a line from (FROM_X, FROM_Y) to (TO_X, TO_Y) in the surface's current drawing colour.
The thickness parameter allows you to specify how thick the line is, the default being 1 pixel.

NOTE: The X and Y co-ordinates given are ROOM co-ordinates, not SCREEN co-ordinates. This means that in a scrolling room you can draw outside the current visible area.

When to use:

This function will make you gain speed only if the line is larger than the target DrawingSurface. For example, if you decide to draw a line that goes from (-100,-100) to (400,300) onto a 320x200 DrawingSurface.

When not to use:

This function will cause some accuracy loss in (from_x, from_y) and (to_x, to_y). In other words, a line drawn with DrawLine and a line drawn with FastLine will not overlap perfectly.
Here is a sample code that will demonstrate the accuracy loss. The dark red pixels show you where the lines don't exactly overlap.

DrawingSurface *surface = Room.GetDrawingSurfaceForBackground();
surface.DrawingColor = Game.GetColorFromRGB(100,0,0); //dark red
surface.DrawLine(-200, -200, 600, 400);
surface.DrawingColor = Game.GetColorFromRGB(0,100,00); //dark green
surface.FastLine(-200, -200, 600, 400);
surface.Release();

General example:

DrawingSurface *surface = Room.GetDrawingSurfaceForBackground();
surface.DrawingColor = 14;
surface.FastLine(-500, -500, 500, 500); //this line is larger than the target drawing surface
surface.Release();

will draw a line from the left top of the screen (0,0) to the middle of the screen (160,100);

See Also: DrawingSurface.DrawLine, DrawingSurface.DrawingColor

[Crimson Wizard]

However, I *HATE* to say that (trust me, I really do), but I'm not sure it's a good idea to have two DrawLine functions. The reason why the second one is faster might be lost to less "educated" scripters, and actually add confusion because they wouldn't know when not to use it (not to mention, maintenance: documentation, etc.). I know that if I was you, I'd be supremely annoyed that my immediate feature implementation is rejected by the very person who suggested it. But I'm really being honest.

Well, this were my thought as well. The build I made is an experimental one, and I was not going to make any final decisions with it.
The separation of "slow" line and fast line functions seem to be specific to Allegro 4. I checked other similar SDKs, and neither Allegro 5 nor SDL2 have such options. Then again, they may use different algorithms to draw the line (I guess they both have 3D texture as a drawing surface).

I guess it has to be investigated whether the "fastline" actually has precision errors, as noted in comments to the code, and what are these look like. And if there are better (more accurate?) alternatives to draw a clipped line.

[Retro Wolf]

How about keeping one draw function, but have an extra argument to define which drawing algorithm to use. If left blank it uses the default one.

[Crimson Wizard]

How about keeping one draw function, but have an extra argument to define which drawing algorithm to use. If left blank it uses the default one.

I am afraid that will be even worse. Extra arguments are easy to forget, and less explicit than extra function.

[ollj]

use a custom enum as extra argument, it still makes it possible to mess up, but it makes manual input harder to mess up.

often you need 2 functions, like, one that is faster for drawing long lines that are mostly outside of your paintable area.
and another function that is faster drawing lines that are mostly inside the paintable area.

if you want 1 for both, merge them, and add a parameter, a boolean or enum, with a default value, to chose which variant you want to use.

like, for sorting functions of integer arrays, dont make 12 sorting functions, make 1 sorting function that also takes +1 integer that sets what subroutine is chosen, use an enum for easy stup.

---


the draweline command is simple and dumb. better performance for all the lowres tasks on average.

but it may calculate a lot of point positions before it can realize that that point is far outside your view.

if you want to draw WAY out of frame|view you better use some trigonometry to calculate intersection point of your view|frame, a rectangle. with the line you want to draw.
of course that may slightly move your line, removing a bit accuracy.

your screen is a rectangle made of 4 lines.
check foe each of these lines where the your drawing line intersects with these 4 lines

https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection

its easy to check if these 4 intersection points are 0<=x<=screen_size
and only 2 of the 3 intersections should pass that filter.
then you draw a line between these 2 points.

http://wiki.secondlife.com/wiki/Geometric#Line_and_Line.2C_intersection_point

[Crimson Wizard]

The advantage of enum parameter is that it makes it easier to pass this as a parameter through several script functions.
The disadvantage is that it is less explicit when you read the code. Also, if there are more than one optional parameters, you must define all preceding ones if you want to use one in the end.
But since both functions have same practical output and only differ in method, I guess enum could be better here after all.

[Monsieur OUXX]

YEah I have nothing against an enum parameter made optional to be sure it doesn't confuse anyone. If it's the very last one, then the chances that someone screws up with their values when typing all the preceding ones is very low, since this parameter is the most obscure of them all. My only regret is that, as demonstrated a few years ago, an extra parameter in AGS function calls is significantly slightly (yes, "significantly slightly", lol) slower. But, really no big deal. If it's an optional parameter then I don't know how the compiler works internally but with some luck it could just call the function without piling up that parameter in memory and without copying over its value. Hurray!

@Crimson Wizard: the accuracy issue is minor, and it's easy to understand why it happens : When the regular algorithm draws a line, you know that it shuffles the step with its own internal logic (e.g. : increase Y every 5 horizontal pixels). It all relies on internal calculations.
  Now, if you start your line outside the picture, imagine that it intersects your drawing surface from the top. You can't really predict where exactly the line will start "appearing" within your drawing surface (you could be one pixel off to the left or to the right), unless you draw the whole fucking line. But that's what you're trying to avoid.
  The Cohen Sutherland aproach is really naive (yet efficient) and that explains why it's the one both Allegro and I have been using. It's very easy to understand: You calculate on which borders your line intersect with the DrawingSurface, then you interpolate the coordinates of these inetresction poinst on the edges of the surface (it's simple maths really: y=ax+b )and in the end you draw a line between these intersections.
  However the intersection point predicted by "y=ax+b" is not exactly the same as the one evaluated by the drawing algorithm. So the start and end pixels of the simplified line might not be exactly the same as the regular line. And that's why your simplified line might be one or two pixels off, every few pixels.

@ollj : congrats, you're actually trying to recreate Cohen Sutherland from scratch

[Snarky]

You can't really predict where exactly the line will start "appearing" within your drawing surface (you could be one pixel off to the left or to the right), unless you draw the whole fucking line.

I'm pretty sure you could without too much difficulty, but it's just not really worth it.

[Gilbert]

Hmmm. Instead of adding an optional parameter, while not get/set the algorithm to use with a separate property?
(We already have a lot of cases like that, one example is the game-wide variable Speech.Style
and if we think it's not important enough to have its own enum and variable name, we may just add this feature to SetGameOption() and GetGameOption().)
So that when once set in code, the remaining DrawLine() calls will stick to one single algorithm, until it is changed again.
This makes no change in codes for existing projects. For example:

Code: ags

SetGameOption(OPT_DRAWLINEMODE, 1); //Say 0 for original(default) algorithm and 1 for fast algorithm
s.DrawLine(blah);
s.DrawLine(blah bla);
...

[Gurok]

There's no need to change code in existing projects anyway, Gilbert. If the optional parameter is last in the list of parameters and defaults to the old algorithm (eAccurate?), existing DrawLine calls won't be affected.

An optional parameter also better matches the use of DrawLine. You don't, for instance, expect all lines for a project to be drawn with one algorithm or another. It's something handled on a case-by-case basis. I don't know about you, but I tend to think options should be reserved for situations where there is a need to do things globally.

An enum is really the nicest solution to this problem. I was actually about to suggest it myself, before ollj did.



I'd like to add to Monsieur OUXX's analysis that it should actually be possible to homogenise the output of the two algorithms. For us to maintain compatibility though, we'd have to look at rewriting FastLine.

[Gilbert]

Of course I know the parameter is optional, but contrary to your idea, I think it is preferable to have all (or rather, a bundle of) DrawLine() calls to have the same algorithm.

For example, you may add an option to the game, so that the players may toggle which algorithm to use, depending on how powerful their rigs are. And this will not affect an already existing project, in which all the DrawLine() functions are not affected.

[Crimson Wizard]

For example, you may add an option to the game, so that the players may toggle which algorithm to use, depending on how powerful their rigs are.

I think this is superfluous. Most human players probably won't notice the (visual) difference in how the line is drawn.