Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.sys.apple2.programmer > #3085 > unrolled thread

hi-res graphics animation, dynamically generated shape tables

Back to article view | Back to comp.sys.apple2.programmer

Contents

  hi-res graphics animation, dynamically generated shape tables Mark Lemmert <mark.lemmert@gmail.com> - 2016-09-28 12:20 -0700
    Re: hi-res graphics animation, dynamically generated shape tables Michael J. Mahon <mjmahon@aol.com> - 2016-09-28 16:15 -0500
      Re: hi-res graphics animation, dynamically generated shape tables Mark Lemmert <mark.lemmert@gmail.com> - 2016-09-28 21:47 -0700
        Re: hi-res graphics animation, dynamically generated shape tables Michael J. Mahon <mjmahon@aol.com> - 2016-09-29 12:50 -0500
    Re: hi-res graphics animation, dynamically generated shape tables Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-09-28 16:27 -0700
      Re: hi-res graphics animation, dynamically generated shape tables Mark Lemmert <mark.lemmert@gmail.com> - 2016-09-28 21:54 -0700
      Re: hi-res graphics animation, dynamically generated shape tables qkumba <peter.ferrie@gmail.com> - 2016-09-29 21:21 -0700
        Re: hi-res graphics animation, dynamically generated shape tables Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-09-30 00:06 -0700
    Re: hi-res graphics animation, dynamically generated shape tables Mark Lemmert <mark.lemmert@gmail.com> - 2016-10-07 10:23 -0700
      Re: hi-res graphics animation, dynamically generated shape tables Nick Westgate <nick.westgate@gmail.com> - 2016-10-09 16:55 -0700
        Re: hi-res graphics animation, dynamically generated shape tables Mark Lemmert <mark.lemmert@gmail.com> - 2016-10-10 18:07 -0700
          Re: hi-res graphics animation, dynamically generated shape tables Nick Westgate <nick.westgate@gmail.com> - 2016-10-10 19:43 -0700
        Re: hi-res graphics animation, dynamically generated shape tables Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-10-17 10:19 -0700
          Re: hi-res graphics animation, dynamically generated shape tables Mark Lemmert <mark.lemmert@gmail.com> - 2016-10-17 11:55 -0700
            Re: hi-res graphics animation, dynamically generated shape tables Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-10-19 18:54 -0700
              Re: hi-res graphics animation, dynamically generated shape tables Mark Lemmert <mark.lemmert@gmail.com> - 2016-10-20 11:17 -0700
                Re: hi-res graphics animation, dynamically generated shape tables Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-10-20 18:52 -0700
                  Re: hi-res graphics animation, dynamically generated shape tables Mark Lemmert <mark.lemmert@gmail.com> - 2016-10-21 15:41 -0700
                Re: hi-res graphics animation, dynamically generated shape tables Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-10-24 19:15 -0700
      Re: hi-res graphics animation, dynamically generated shape tables Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-10-17 10:15 -0700
    Re: hi-res graphics animation, dynamically generated shape tables Mark Lemmert <mark.lemmert@gmail.com> - 2016-10-21 15:43 -0700
      Re: hi-res graphics animation, dynamically generated shape tables Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-10-24 09:01 -0700
        Re: hi-res graphics animation, dynamically generated shape tables 6502workshop@gmail.com - 2016-11-05 10:29 -0700
      Re: hi-res graphics animation, dynamically generated shape tables Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-10-24 09:01 -0700
        Re: hi-res graphics animation, dynamically generated shape tables Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-10-24 10:30 -0700
      Re: hi-res graphics animation, dynamically generated shape tables Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-10-24 10:18 -0700

Page 2 of 2 — ← Prev page 1 [2]

#3144

On Thursday, October 20, 2016 at 8:52:17 PM UTC-5, Michael Pohoreski wrote: 
> Sadly I won't be able to write up part 2 tonight, but I can answer your some questions tonight before I'm out ... 

Thanks! 

> > I am struggling a bit with the d1/d2 formula. What does Y refer to? I understand what Y2, Ya, and Yb are, but the only mention I saw of Y was in the y = mx+b equation, in which my understanding is that X and Y to refer to any point on the line. 
> 
> Correct. Y refers to an arbitrary point on the line.  It is the exact floating-point value -- well as "exact" as floating-point can be. :-) 
> 
> It might help to review this image: 
> 
> https://salonibaweja10.files.wordpress.com/2014/09/screenshot-from-2014-09-10-233839.png 
> 
> The diagram uses: 
> 
> * Yi+1, which I call Ya+1, and 
> * Yi, which I call Ya. 
> 
> It might to think of this way: 
> 
> * You can see that y is the "expected" value, and 
> * either Yi+1 or Yi is the "actual" value. 
> 
> We're trying to minimize the error between the two, that is: 
> 
>  error1 = expected_y - actual_Ya 
>  error2 = expected_y - actual_Ya+1 
> 
> The calculations with d1, d2 gets hairy real fast -- which is why it is taking so long to write up part 2.  I want to personally verify the proof.  It _does_ simply -- It just takes longer. 

Ah, I think I get it. y is a not necessarily a point on the grid. I see why calculating the distance gets hairy :-) 

I look forward to part II when you have time to write it! 

Mark

[toc] | [prev] | [next] | [standalone]

#3152

On Friday, October 21, 2016 at 3:43:05 PM UTC-7, Mark Lemmert wrote:
> Ah, I think I get it. y is a not necessarily a point on the grid. I see why calculating the distance gets hairy :-) 
> 
> I look forward to part II when you have time to write it! 

As promised here is Part 2.

Part of the reason this took so long is that most of the reference material I found WAY over-complicated this.  I would rather present the material in a clear fashion then drown the reader in a sea of simplifying.

As mentioned last time: d1, and d2 are the distance above and below the idealized line.

https://www.tutorialspoint.com/computer_graphics/images/dupper_and_dlower.jpg

The line divides the space into two:

https://upload.wikimedia.org/wikipedia/commons/5/5a/Line_1.5x%2B1_--_planes.svg

Let's calculate d1, d2, and s:

 s = d1 - d2
 s = (y - Ya) - (Ya+1 - y)
 s = y - Ya - Ya-1 + y
 s = 2*y - 2*Ya - 1
 s = 2*[m*(Xa + 1) + b] - 2*Ya - 1
 s = 2*m*(Xa + 1) + 2*b - 2*Ya - 1

Recall that

 y = mx + b

Solving for b:

  b = y - m*x
  b = Y0 - dy/dx*X0

Then:

 s = 2*m*(Xa+1) + 2*[Y0-m*X0] - 2*Ya - 1
 s = 2*dy/dx*(Xa + 1) + 2*(Y0-dy/dx*X0) - 2*Ya - 1

The problem is we are still dividing. :-/ If we multiply both sides by dx we'll remove the division:

s*dx = dx*[2*dy/dx*(Xa + 1) + 2*(Y0-dy/dx*X0) - 2*Ya - 1]

Hmm, this is getting pretty hairy fast.

We _could_ solve this (See earlier references) but there is an much easier way. (Don't worry, the math works out the same.)

NOTE: For the gory details see:
https://salonibaweja10.wordpress.com/tag/derivation-of-bresenham-line-algorithm/

The reason I point out the above detour is because sometimes we don't always know how the math will turn out.  Sometimes we need to "follow" the equations to see if this becoming simpler or more complicated.  If complicated -- it might be worth it to see if a simpler solution exists.  It is best when we can derive the same results 2 different ways. :-)

To be continued in Part 3

[toc] | [prev] | [next] | [standalone]

#3173

On Monday, October 24, 2016 at 11:01:14 AM UTC-5, Michael Pohoreski wrote: 
> Part of the reason this took so long is that most of the reference material I >found WAY over-complicated this.  I would rather present the material in a >clear fashion then drown the reader in a sea of simplifying.

Thanks perfect, thank you!
 

> The reason I point out the above detour is because sometimes we don't always >know how the math will turn out.  Sometimes we need to "follow" the equations >to see if this becoming simpler or more complicated.  If complicated -- it >might be worth it to see if a simpler solution exists.  It is best when we can >derive the same results 2 different ways. :-)
> 
> To be continued in Part 3

Especially with something this complex that makes a lot of sense.


>Which one looks best in context of your needs is something that needs to be >determined.
>
>Hope this helps! 

It does, thanks!


Mark

[toc] | [prev] | [next] | [standalone]

#3153

Part 3

There is an derivation called the "mid-point" proof that I'll use instead.

Recall, the equation of the line:

 y = mx + b

Let's rewrite this as a Function in terms of x and y: F(x,y):

 y = mx + b
 y = dy/dx * x + b
 dx*y = dy*x + b
 0 = dy*x -dx*y + b

This is a linear equation of the form:

 A*x + B*y + C

That is

 A =  dy
 B = -dx
 C =  b

OK, let's "reset" back to calculating the distance between the idealized and quantized points on the line.

For the second column we want to know the error from the idealized line to the vertical midpoint relative to the first column:

+----+----+ 
|    |X0+1| 
|    |Y0+1| 
+----+----+ <- Y0+1/2
| X0 |X0+1| 
| Y0 |Y0  | 
+----+----+ 

 s = f( X0+1, Y0+1/2 ) - f( X0,Y0 )
   = [A*(X0+1) + B*(Y0+1/2) + C] - [A*X0 + B*Y0 + C]
   = A*X0 + A + B*Y0 + B*1/2 + C- A*X0 - B*Y0 - C
   =        A        + B*1/2
   = dy - dx/2

if (s < 0) pick X0+1,Y0
if (s > 0) pick X0+1,Y0+1 -- refer back to the Half-Space diagram from above

Since all we care about is the sign, we can remove the division via multiplication:

 s = dy - dx/2
 2*s = 2*(dy - dx/2)
 2*s = 2*dy - dx

That gives us our initial s, but we need to see how s changes over x.

+----+----+----+
|....|....|X0+2|  
|....|....|Y0+2| 
+----+----+----+ <- Y0+3/2
|....|....|X0+2|  
|....|....|Y0+1| 
+----+----+----+ <- Y0+1/2
|....|....|X0+2|
|....|....|Y0+0| 
+----+----+----+

For the 3rd column we want to know the error from our previous spot.

If we should be low the line:

s = f( X0+2, Y0+1/2 ) - f( X0+1, Y0+1/2 )
  = [A*(X0+2) + B*(Y0+1/2) + C] - [A*(X0+1) + B*(Y0+1/2) + C]
  = A*X0 + 2*A + B*Y0 + B*1/2 + C - A*X0 - A - B*Y0 - B*1/2 - C
  = 2*A - A
  = A
  = dy

If we should be above the line:

s = f( X0+2, Y0+3/2 ) - f( X0+1, Y0+1/2 )
  = [A*(X0+2) + B*(Y0+3/2) + C] - [A*(X0+1) + B*(Y0+1/2) + C]
  = A*X0 + 2*A + B*Y0 + B*3/2 + C - A*X0 - A - B*Y0 - B/2 - C
  = 2*A - A + B*3/2 - B*1/2
  = A + B
  = dy - dx

What does this mean?

We are _accumulating_ the relative error per column.  

If (s < 0) we increment s by +dy for each column
if (s > 0) we increment s by +dy - dx for each column; also we undershot the y so we need to increase that too.

    if (s < 0)
        s += dy
    else
    {
        s += dy -dx
        y++;
    }

Since there is a common term of +dy this is usually factored out and optimized as:

    if (s > 0)
    { 
        s -= dx;
        y++;
    }
    s += dy;


Our **integer** line drawing function ends up like:

function line2( x0, y0, x1, y1, color )
{
    var x, y = y0;
    var dx = x1 - x0;
    var dy = y1 - y0;
    var s  = 2*dy - dx;

    for( x = x0; x <= x1; ++x )
    {
        putpixel( x, y, color );

        if (s > 0)
        { 
            s -= dx;
            y++;
        }
        s += dy;
    }
}


I've thrown together a Javascript example:
https://github.com/Michaelangel007/js_bresenham_line

References:
Check line.js

[toc] | [prev] | [next] | [standalone]

#3156

On Monday, October 24, 2016 at 9:01:44 AM UTC-7, Michael Pohoreski wrote:

Part 3b -- Supplement

> Our **integer** line drawing function ends up like:
> 
> function line2( x0, y0, x1, y1, color )
> {
>     var x, y = y0;
>     var dx = x1 - x0;
>     var dy = y1 - y0;
>     var s  = 2*dy - dx;
> 
>     for( x = x0; x <= x1; ++x )
>     {
>         putpixel( x, y, color );
> 
>         if (s > 0)
>         { 
>             s -= dx;
>             y++;
>         }
>         s += dy;
>     }
> }

Update:

In order to preserve symmetry, the compare should be: >= instead of >

if (s >= 0)

Check out linei() and linej() in line.js

[toc] | [prev] | [next] | [standalone]

#3154

Part 4

Another way to derive the line drawing algorithm is incrementally.

Let's start with a "dumb" line drawing.

 for x = X0 to X1
   putpixel( x, y )

Unfortunately this just draws a horizontal line. :-/  What we want is this:

 for x = X0 to X1
   putpixel( x, y )
   figure out new y

Sometimes we increment y, sometimes we don't:

 for x = X0 to X1
   putpixel( x, y )
   if( incrementY )
      y = y + 1

If we use floating-point this becomes easy if we keep track of the error:

 e = 0;
 m = dy/dx;
 for x = X0 to X1
   putpixel( x, y )
   e += m;
   if (e > 0.5)
      e = e - 1
      y = y + 1

We want to get rid of that 0.5 and use integers

 e = 0;
 m = 2*dy/dx;
 for x = X0 to X1
   putpixel( x, y )
   e += m;
   if (e > 1)
      e = e - 2
      y = y + 1

We also want to get rid of that division -- we need to multiply all the terms by dx; this means all terms involving m need to be updated:


 e = 0;
 m = 2*dy;
 for x = X0 to X1
   putpixel( x, y )
   e += m;
   if (e > dx)
      e = e - 2*dx
      y = y + 1

We also want to compare the sign instead of 'e > dx' -- we can change that by offsetting the initial term.

 e = -dx;
 m = 2*dy;
 for x = X0 to X1
   putpixel( x, y )
   e += m;
   if (e > 0)
      e = e - 2*dx
      y = y + 1

I've updated my GitHub repo with this variation. See line3() line4() line5()

If you inspect these different variations you'll notice that the slope is "shifted over" by a pixel.

For example, these 3 lines are equivalent:

XXX.
...X

XX..
..XX

X...
.XXX

Which one looks best in context of your needs is something that needs to be determined.

Hope this helps!

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.sys.apple2.programmer

csiph-web