Line Drawing

[NoCforMe]

It might be a case of inverting the the y by subtracting the y given from the y max value but don't know if I want to go that far. We will see.

If you do, the formula would be really simple:

Yactual = -YCartesian + Ymax

[FORTRANS]

Hi Tim,

In any case, I think my next step is to treat each quadrant in its own routine and to get that working.

   The last time I tried coding a general purpose line drawing routine,
I wrote code for the four quadrants, horizontal lines, vertical lines,
and the two diagonal lines.  Those last four could be coded up rather
easily, and could be faster than a general purpose line drawing routine.

Regards,

Steve

Edit:   With the four special case lines, it should be eight octants, not
four quadrants.

SRN

[daydreamer]

Steve try port your old code to 32 bit using ddraw or SDL interface to access Max hires screen memory in win32 coding ?
I tried bresenham circle algo and pixelshader approach to use sqrt( x^2+y^2 )

[NoCforMe]

The last time I tried coding a general purpose line drawing routine,
I wrote code for the four quadrants, horizontal lines, vertical lines,
and the two diagonal lines.

I understand everything except why you deal differently with "diagonal" lines (I assume by this you mean lines where the slope is exactly 1 or -1, right?) Why would you need to do that?

I checked with my old DIY line-drawing routine and it works fine with "diagonal" lines.

[FORTRANS]

Hi,

I understand everything except why you deal differently with "diagonal" lines (I assume by this you mean lines where the slope is exactly 1 or -1, right?) Why would you need to do that?

   It has been a while since I last looked at it, but it was either
for increased speed or reduced "bookkeeping".  For either it allows
for not updating variables and testing for when to update things.
Just run a loop to its end.

Regards,

Steve N.

[FORTRANS]

Hi,

   Looked at some old notes, not any actual code.  I was
trying to get the fastest code possible.  Mostly in mode
6 screen format (640x200x1).  Also mode 13 and some VESA
modes.  It looks as if I spent way too much time and effort
for what I finally ended up using.

   I looked at line drawing code by Abrash, Wilton, and the
Waite Group.  And tried out some different algorithms with
my own code.  Including drawing from both ends to meet in
the middle.

   The slow mode 6 code that started the whole exercise was
more flexible and useful in the end.  Speeded it up a little
bit, but not as much as I had wanted.  Basically, I needed
a routine that allowed for differing pixel types for drawing
things like fat lines or XORed lines.  All the faster line
drawing routines had only one type of pixel, direct writing
to the screen.

Cheers,

Steve N.

Cheers,

Steve N.

[NoCforMe]

Looked at some old notes, not any actual code.  I was
trying to get the fastest code possible.  Mostly in mode
6 screen format (640x200x1).  Also mode 13 and some VESA
modes.  It looks as if I spent way too much time and effort
for what I finally ended up using.

Steve, have a look at what I posted on the subject in the Workshop.
I can't for the life of me figure why your code was so complicated. Mine has exactly 4 cases:
o Horizontal and vertical lines are drawn separately, since the general drawing code would fail on them;
o Lines where Y₀ > Y₁ are simply mirrored (the endpoints are swapped) and drawn "backwards";
o Otherwise, all line drawing is handled by the same code, regardless of quadrant/octant.

So instead of caring about quadrants/octants, I only care about what I guess you could call left or right vertical halves (regarding that Y₀ > Y₁ business).

Now I'm certainly not claiming any speed records, but it seems to be reasonably fast, and not overly complicated.

[FORTRANS]

Hi,

I can't for the life of me figure why your code was so complicated. Mine has exactly 4 cases:

   I was trying every and any thing.  It got complicated in an attempt
to speed things up by special casing things and trying to optimize the
specific routines separately.  Essentially lots of special code to
replace general purpose code.  If you try every thing, most will end up
being rather bad.  Throw the bad out and try using what's left over.

   It was interesting at the time.  And may have taught me something.
But not useful in general, I suppose.

Regards,

Steve N.

[NoCforMe]

Well, don't feel too bad. Even our most abject failures tend to teach us something useful.

[tda0626]

I was going to implement this from the Bresenham Algo wiki. Looks like it checks for 4 cases. What other cases would there be?

Code Select Expand



plotLine(x0, y0, x1, y1)
    if abs(y1 - y0) < abs(x1 - x0)
        if x0 > x1
            plotLineLow(x1, y1, x0, y0)
        else
            plotLineLow(x0, y0, x1, y1)
        end if
    else
        if y0 > y1
            plotLineHigh(x1, y1, x0, y0)
        else
            plotLineHigh(x0, y0, x1, y1)
        end if
    end if



[NoCforMe]

Can your plotLineXXX() routines handle horizontal and vertical lines? Those would be the other two cases to check for, I would think. (If the plot routine can handle horiz. & vert., no need to check for them.)

Remember: horizontal: slope = 0. Vertical: slope = ∞

[tda0626]

Don't think it will be an issue.

[tda0626]

I have been at this for awhile now and can't figure this problem out so I am asking for some help.

I am trying to get this new line drawing program to work where it draws the different types of lines except vertical and horizontal ones, which will be taken care of later. When drawing from top-right to bottom-left or vice versa, it does not draw correctly, see the picture attached and the source code to this post . This has me stumped! If someone could look over my code and let me know if they see what the issue is, it would be appreciated. Thanks!

[_japheth]

I am trying to get this new line drawing program to work where it draws the different types of lines except vertical and horizontal ones, which will be taken care of later. When drawing from top-right to bottom-left or vice versa, it does not draw correctly, see the picture attached and the source code to this post . This has me stumped! If someone could look over my code and let me know if they see what the issue is, it would be appreciated. Thanks!

I also once implemented the Bresenham thing. Your algorithm for PCorrect was definitely wrong.

Attached is your modified sample. It should work. I also added an implementation of mine, which is now deactive, but may be activated.

[tda0626]

I also once implemented the Bresenham thing. Your algorithm for PCorrect was definitely wrong.

Thank you for all you do!

Would you mind going into more detail why PCorrect is wrong? I got the PCorrect calculation from the Bresenham Line Algo page:

Code Select Expand

plotLineLow(x0, y0, x1, y1)

D = (2 * dy) - dx

plotLineHigh(x0, y0, x1, y1)

D = (2 * dx) - dy


Also, what is

Code Select Expand

@f in the code? I have never seen that.


Tim