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 1 of 2  [1] 2  Next page →

#3085 — hi-res graphics animation, dynamically generated shape tables

I have a question regarding hi-res graphics animation in assembly language, that I am wondering if anybody can offer any advice on? Any insights are greatly appreciated. 


-Goal

In the context of a game, fire a projectile in the shape of a line, from a dynamic starting location (screen byte & line address), to a dynamic target location (screen byte & line address)  

Ultimately I’m hoping to do something more complex than a simple line (like a lightning bolt), but a line seems like a good proof of concept. Let’s say the line shape is 16 pixels long X 1 pixels wide.



-An approach I’ve considered

It seems like at the top level view, this task should be broken into two steps: generate the shape table, and then execute an animation loop using the shape table.

Regarding the shape table. If I were given a fixed starting position and target position, I think I would calculate the slope of the line (rise/run), draw it out on an x/y axis grid, then convert the points on the grid to the appropriate hex values and memory locations to draw it on the video screen. 

However, since the start and target location are dynamic, it seems I would need to calculate the hex values, screen bytes, and line addresses dynamically as well.

I’m speculating that a way to do this might be to dynamically calculate one row of the shape table at a time by placing a value in the accumulator and using LSR/ASL to move the bit into the correct position to turn on the desired pixel based on the slope of the line. 

Am I on the right track or is there a different approach that would work better?  


Once I have the shape table generated, I think I know what to do to animated it. I’ve already done animation where the shape moves multiple screen bytes at a time (sprites moving on a tile graphics grid). I think the main difference here is I’ll want the line shape to move more with more granularity, for smoother movement. When shapes moves at less than 1 screen byte at a time my understanding it that I’ll need multiple shape tables to reflect the different layouts that can occur.



-One other thought

I haven’t programmed in Applesoft basic for decades but generating the shape table for a line between two points seems a lot like what HPLOT does, if I recall :-)

Though, even if the HPLOT subroutine could be accessed from assembly language, speed is an important constraint in this scenario as there are lots of other things going on at the point in the game where the “fired projectile” would occur. 

Additionally, after HPLOT draws a line, extracting the hex values from video memory into an easy-to-work-with shape table seems like a real pain given the memory map of the hi-res screen. My graphics subroutines are setup to calculate line addresses based on a y-axis line/row number, not the other way around. 

And, I'm trying to understand the principles involved in any event. 

But, if there is an angle with an assembly language HPLOT call that I'm overlooking I'd appreciate any insight. 


Thanks!


Mark

[toc] | [next] | [standalone]

#3086

Mark Lemmert <mark.lemmert@gmail.com> wrote:
> I have a question regarding hi-res graphics animation in assembly
> language, that I am wondering if anybody can offer any advice on? Any
> insights are greatly appreciated. 
> 
> 
> -Goal
> 
> In the context of a game, fire a projectile in the shape of a line, from
> a dynamic starting location (screen byte & line address), to a dynamic
> target location (screen byte & line address)  
> 
> Ultimately I’m hoping to do something more complex than a simple line
> (like a lightning bolt), but a line seems like a good proof of concept.
> Let’s say the line shape is 16 pixels long X 1 pixels wide.
> 
> 
> 
> -An approach I’ve considered
> 
> It seems like at the top level view, this task should be broken into two
> steps: generate the shape table, and then execute an animation loop using the shape table.
> 
> Regarding the shape table. If I were given a fixed starting position and
> target position, I think I would calculate the slope of the line
> (rise/run), draw it out on an x/y axis grid, then convert the points on
> the grid to the appropriate hex values and memory locations to draw it on
> the video screen. 
> 
> However, since the start and target location are dynamic, it seems I
> would need to calculate the hex values, screen bytes, and line addresses
> dynamically as well.
> 
> I’m speculating that a way to do this might be to dynamically calculate
> one row of the shape table at a time by placing a value in the
> accumulator and using LSR/ASL to move the bit into the correct position
> to turn on the desired pixel based on the slope of the line. 
> 
> Am I on the right track or is there a different approach that would work better?  
> 
> 
> Once I have the shape table generated, I think I know what to do to
> animated it. I’ve already done animation where the shape moves multiple
> screen bytes at a time (sprites moving on a tile graphics grid). I think
> the main difference here is I’ll want the line shape to move more with
> more granularity, for smoother movement. When shapes moves at less than 1
> screen byte at a time my understanding it that I’ll need multiple shape
> tables to reflect the different layouts that can occur.
> 
> 
> 
> -One other thought
> 
> I haven’t programmed in Applesoft basic for decades but generating the
> shape table for a line between two points seems a lot like what HPLOT does, if I recall :-)
> 
> Though, even if the HPLOT subroutine could be accessed from assembly
> language, speed is an important constraint in this scenario as there are
> lots of other things going on at the point in the game where the “fired
> projectile” would occur. 
> 
> Additionally, after HPLOT draws a line, extracting the hex values from
> video memory into an easy-to-work-with shape table seems like a real pain
> given the memory map of the hi-res screen. My graphics subroutines are
> setup to calculate line addresses based on a y-axis line/row number, not
> the other way around. 
> 
> And, I'm trying to understand the principles involved in any event. 
> 
> But, if there is an angle with an assembly language HPLOT call that I'm
> overlooking I'd appreciate any insight. 
> 
> 
> Thanks!
> 
> 
> Mark
> 

Yes, HPLOT uses a variant of Bresenham's algorithm to draw "straight" lines
between two points, which is what you need to do to generate your
line-shaped bitmap(s). 

But 16 pixels is pretty short and the shape is in motion, so its exact
slope is probably not very critical. Even less critical if it's a lightning
bolt. 

You can probably get away with only one or two angles besides horizontal
and vertical, which would allow precomputing the shapes and doing symmetry
transforms (do one quadrant and reflect the shapes to get the other three).

-- 
-michael - NadaNet 3.1 and AppleCrate II:  http://michaeljmahon.com

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

#3088

On Wednesday, September 28, 2016 at 4:15:46 PM UTC-5, mjm...@aol.com wrote:
> > -Goal
> > 
> > In the context of a game, fire a projectile in the shape of a line, from
> > a dynamic starting location (screen byte & line address), to a dynamic
> > target location (screen byte & line address)  
> > 
> > Ultimately I’m hoping to do something more complex than a simple line
> > (like a lightning bolt), but a line seems like a good proof of concept.
> > Let’s say the line shape is 16 pixels long X 1 pixels wide.

> You can probably get away with only one or two angles besides horizontal
> and vertical, which would allow precomputing the shapes and doing symmetry
> transforms (do one quadrant and reflect the shapes to get the other three).

That's a good point. I'm not really sure how many angles I would need, but maybe it's better to start with this simpler method and see if it gets the job done. 

So let's say I had 4 shape tables, in addition to horizontal and vertical, which contains the lightning bolt at different angles. Would selecting the shape table based on the slope of the hypothetical line between the start and target points be a good approach?

Thanks!

Mark

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

#3090

Mark Lemmert <mark.lemmert@gmail.com> wrote:
> On Wednesday, September 28, 2016 at 4:15:46 PM UTC-5, mjm...@aol.com wrote:
>>> -Goal
>>> 
>>> In the context of a game, fire a projectile in the shape of a line, from
>>> a dynamic starting location (screen byte & line address), to a dynamic
>>> target location (screen byte & line address)  
>>> 
>>> Ultimately I’m hoping to do something more complex than a simple line
>>> (like a lightning bolt), but a line seems like a good proof of concept.
>>> Let’s say the line shape is 16 pixels long X 1 pixels wide.
> 
>> You can probably get away with only one or two angles besides horizontal
>> and vertical, which would allow precomputing the shapes and doing symmetry
>> transforms (do one quadrant and reflect the shapes to get the other three).
> 
> That's a good point. I'm not really sure how many angles I would need,
> but maybe it's better to start with this simpler method and see if it gets the job done. 
> 
> So let's say I had 4 shape tables, in addition to horizontal and
> vertical, which contains the lightning bolt at different angles. Would
> selecting the shape table based on the slope of the hypothetical line
> between the start and target points be a good approach?
> 
> Thanks!
> 
> Mark

Yes, that should work fine. 

The advantage of a jagged "lightning bolt" is that its angular orientation
is not critical. You should probably start with just horizontal, vertical,
45 degrees left and 45 degrees right. 

When animated, that's likely to look "good enough". 
-- 
-michael - NadaNet 3.1 and AppleCrate II:  http://michaeljmahon.com

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

#3087

Having multiple "pre-computed" shape tables, aka sprites, or glyphs, is a common optimization technique.  Pre-computed bit-masks are you friend for fast HGR graphics.  This is the classic trade-off between time vs space.

Do you "need" full 360 degree lines? Or can you get away with a partial sub-set?

For advanced techniques, the magic words you are looking for are "compiled sprites".

Officially I don't know if anyone has implemented it on the Apple.  Thy used to be popular in the early 90's on the x86.

Most games that I've inspected just use bitmask and shits since the data usually can't be represented algorithmically.

Hope this helps give you some more ideas.

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

#3089

On Wednesday, September 28, 2016 at 6:27:15 PM UTC-5, Michael Pohoreski wrote:
> Having multiple "pre-computed" shape tables, aka sprites, or glyphs, is a common optimization >technique.  Pre-computed bit-masks are you friend for fast HGR graphics.  This is the classic trade-off >between time vs space.
> 
> Do you "need" full 360 degree lines? Or can you get away with a partial sub-set?

Thanks for your reply. 

Probably not 360 degrees. From your post and the other it sounds like it may be worth considering manually calculating a few shape tables at different angles, loading them from disk into memory and then selecting the one with the best fit based on the slope if the line. 

> 
> For advanced techniques, the magic words you are looking for are "compiled sprites".
> 
> Officially I don't know if anyone has implemented it on the Apple.  Thy used to be popular in the early 90's on the x86.
> 
> Most games that I've inspected just use bitmask and shits since the data usually can't be represented algorithmically.
> 
> Hope this helps give you some more ideas.

Thanks for the information. I did some reading on compiled sprites and if I understood correctly the essence of the technique is to have the program generate the machine language to draw the shape. Pretty cool! I'm not sure that I'll need to go to that point, but great to know about it just in case. 


Mark

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

#3091

> Most games that I've inspected just use bitmask and shits since the data usually can't be represented algorithmically.

Come on, they weren't that bad.  Oh, you meant "shifts". ;-)

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

#3092

On Thursday, September 29, 2016 at 9:21:34 PM UTC-7, qkumba wrote:
> > Most games that I've inspected just use bitmask and shits since the data usually can't be represented algorithmically.
> 
> Come on, they weren't that bad.  Oh, you meant "shifts". ;-)

Oh, ffffart. LOL, yup, Freudian slip. :-)

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

#3099

Follow-up to original post.

I dove in and got started on this project. I’m currently working on setting up a subroutine to animate the movement of the line shape using the slope of the line between the start and target locations. Once I have that done, I’ll do more exploration on whether some kind of dynamic shape table or compiled sprite is needed to get the angle of my line shape pointed at a visually acceptable vector toward the target vs. just using a couple static shape tables at different angles as was suggested.
  

As an update from the OP, I don’t think that I’m going to need to do draws at horizontal increments of less than 1 screen byte. Phew! I was prepared to setup the multiple shape tables per shape necessary to do that, but I don’t mind the reduced complexity by avoiding that :-) What I found was that a 1 screen byte horizontal increment actually works great because it causes a bit of a blur when the object is moving; perfect for an arrow, crossbow bold, lighting bolt, etc. 

Shoehorning the slope = rise/run formula into assembly language is proving an interesting challenge. 

The draw subroutine is setup and “working”, but there are some issues. I’m trying to get the line to pass through a 14 pixel X 16 pixel target. It doesn’t need to pass through the target dead center, I think anywhere within that 14x16 square will visually look fine.

I'm doing the calculations by hand for now, and hard coding the rise/run, but doing the calcs in a way that I know I can code in assembler. The challenge I’m encountering doing this relates to the remainder value. 

(quick assumption discloser: I have a subroutine that does “real” division which I anticipate using and most rise/run scenarios result in a whole number plus remainder) 

A few observations about the remainder value and other math issues:

*If run is greater than rise, I just use a slope of 1/1 and it works fine.  

*If I ignore the remainder value completely, sometimes the line passes through the 14x16 pixel target, sometimes it doesn’t. 

*The largest remainder values exist when the objects are at opposite ends of the screen (i.e. when the run is pretty long)

*The sensitivity to the remainder value is greater with sharper angles (i.e. when the slope value is larger)

For example, with the start and target at opposite edges of the screen (my right edge is about 2/3 of the way across the actual hi-res screen), if I get a slope of 2 remainder 2 and ignore the remainder, the target is still hit. On the other hand, with the start/target much closer together, let’s say a slop of 5 remainder 2, the target is missed. If I round the slope up to 6, then the target is hit.

To math folks, I’m probably stating obvious stuff here. I was never a math-wiz in school. I felt pretty good that I even remembered the slope formula :-)
 

Here is a link to a video example of a slope 5, remainder 2 scenario. The line shape isn’t pointed at an angle yet, but when played at slow motion I can tell that even if it was, it would not pass through the 14x16 pixel target. 

https://www.dropbox.com/s/a6pcxvi5e72bnws/Projectile_testing1.MOV?dl=0



There are two tactics I can think of to deal with this: 

1) setup some rules where the slope is rounded up if the slope is > V. I’d use trial and error to figure a good value for V. 

2) with shorter slopes, rounding up can be too much of a correction. In these cases, I’m considering installing a sub-counter in the rise/rise loop, where the shape is inc/dec an extra hi-res line every few screen bytes.


I’m new to implementing geometry mathematics in 6502, and only vaguely familiar with the geometry, so I’m not sure if I’m on the right track or not. Any insights anybody might have are much appreciated. 

In any event, I’ll continue to post my findings in this adventure. I’m determined to get this to work somehow, whether it takes a shoe horn, or even a crowbar.  



On another note, my drawing subroutine for these kinds of shapes uses and AND mask and an ORA mask to blend the shape into the background. Many thanks to Michael Pohoreski for his post earlier this year giving a detailed example of this concept!

https://groups.google.com/forum/#!topic/comp.sys.apple2.programmer/cgxZOBIL728

Very helpful in pulling this together.  



Mark

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

#3107

On Saturday, 8 October 2016 06:23:26 UTC+13, Mark Lemmert  wrote:
> Shoehorning the slope = rise/run formula into assembly language is proving an interesting challenge. 

Michael Mahon has already mentioned that Bresenham's algorithm is a way to
draw lines. You need to do the same thing, but instead of plotting pixels
you'll be drawing your shape as you animate it along the line.

If you google for integer only Bresenham's algorithm you'll find eg:
http://tech-algorithm.com/articles/drawing-line-using-bresenham-algorithm/
http://www.gamedev.net/page/resources/_/technical/game-programming/line-drawing-algorithm-explained-r1275

Cheers,
Nick.

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

#3112

Nick,

Thanks for refocusing my attention on that, and for the links. 

It's looking like to use something like Bresenham's algorithm I would have to move my shape in horizontal increments of less than one screen byte, which I'd prefer to avoid due to the memory requirements for all the extra shape tables involved. 

I'm going to fiddle around with my current setup a bit more and see if I can get it close enough, but if not it looks like Bresenham's is the way to go. 

Mark



On Sunday, October 9, 2016 at 6:55:58 PM UTC-5, Nick Westgate wrote:
> On Saturday, 8 October 2016 06:23:26 UTC+13, Mark Lemmert  wrote:
> > Shoehorning the slope = rise/run formula into assembly language is proving an interesting challenge. 
> 
> Michael Mahon has already mentioned that Bresenham's algorithm is a way to
> draw lines. You need to do the same thing, but instead of plotting pixels
> you'll be drawing your shape as you animate it along the line.
> 
> If you google for integer only Bresenham's algorithm you'll find eg:
> http://tech-algorithm.com/articles/drawing-line-using-bresenham-algorithm/
> http://www.gamedev.net/page/resources/_/technical/game-programming/line-drawing-algorithm-explained-r1275
> 
> Cheers,
> Nick.

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

#3113

On Tuesday, 11 October 2016 14:07:56 UTC+13, Mark Lemmert  wrote:
> It's looking like to use something like Bresenham's algorithm I would have to move my shape in horizontal increments of less than one screen byte

Not so. Just have your X units in bytes.

Cheers,
Nick.

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

#3137

On Sunday, October 9, 2016 at 4:55:58 PM UTC-7, Nick Westgate wrote:
> On Saturday, 8 October 2016 06:23:26 UTC+13, Mark Lemmert  wrote:
> > Shoehorning the slope = rise/run formula into assembly language is proving an interesting challenge. 
> 
> Michael Mahon has already mentioned that Bresenham's algorithm is a way to
> draw lines. You need to do the same thing, but instead of plotting pixels
> you'll be drawing your shape as you animate it along the line.
> 
> If you google for integer only Bresenham's algorithm you'll find eg:
> http://tech-algorithm.com/articles/drawing-line-using-bresenham-algorithm/
> http://www.gamedev.net/page/resources/_/technical/game-programming/line-drawing-algorithm-explained-r1275
> 
> Cheers,
> Nick.

Nick and Michael have the correct solution.

I prefer Rosetta Code to see how the implementation details differ by language / idiom:
https://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm

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

#3138

Hi Michael,

Thanks for the reply.

I've done some more work since my last post. 

It turns out that I ended up with something very similar to Bresenham's algorithm, in that I divided the screen into 8 octets and vary the rise/run math accordingly. I had the code to do this already because my MOB flocking algorithm does the same thing to determine which direction to move in is the closest to the player (center of the screen). 

The main difference between my "final" code and Bresenham's algorithm that I can see is that I'm using real division to calculate the slope and Bresenham's somehow avoids that; I couldn't quite figure out how. 

By using real division I end up with a remainder with many slope cases. However, I was able to bandaid that issue by doing an extra rise (line) increment per run (screen byte) increment if the remainder is > $0A. 

I probably don't have the most efficient/accurate solution but it works for this particular application where the inaccuracies are not visually noticeable. 


That said, the bottom fell out with really steep angles. Not because of the slope division remainder issue, but that a 1 screen byte horizontal increment is just to much when the sprites are in adjacent tile columns. This creates a situation where the run would be 2 screen bytes and the rise could be the entire screen.  The result is an arrow that wobbles really bad :-)

So I've been working on tackling horizontal increments at less that 1 screen byte and was just working on a post about that. I also realized that a 1 screen byte increment would cause color problems with shapes like fireballs. Oops. 


Mark





On Monday, October 17, 2016 at 12:19:53 PM UTC-5, Michael Pohoreski wrote:
> Nick and Michael have the correct solution.
> 
> I prefer Rosetta Code to see how the implementation details differ by language / idiom:
> https://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm

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

#3140

On Monday, October 17, 2016 at 11:55:18 AM UTC-7, Mark Lemmert wrote:
> Hi Michael,
> 
> Thanks for the reply.
> 
> I've done some more work since my last post. 
> 
> It turns out that I ended up with something very similar to Bresenham's algorithm, in that I divided the screen into 8 octets and vary the rise/run math accordingly. I had the code to do this already because my MOB flocking algorithm does the same thing to determine which direction to move in is the closest to the player (center of the screen). 

OK, good, you're familiar with octants. We'll talk about that briefly.


> The main difference between my "final" code and Bresenham's algorithm that I can see is that I'm using real division to calculate the slope and Bresenham's somehow avoids that; I couldn't quite figure out how. 

A naive implementation uses division.
An optimized version uses integer subtraction.

The magic words are "fixed point"

How do we get there?

Recall, that the slope-y-intercept line equation is:

 y = f(x) = mx+b

where:

 m = slope = dy / dx
 b = y-intercept; that is, the line crosses the y-axis at <0,b>

Given 2 points ...

* starting point <x0,y0>
* end point <x1,y1>

... our task is to figure out how to draw a line.

For simplicity, let's assume two things:

* x0 <= x1; that is x0 is on the left, x1 is on the right, and
* our line is >= 0 and <= 45 degrees. That is, y0 <= y1; our line is in octant zero.  It is convenient to sub-divide the standard Cartesian quadrants into half so we end up with this:

Octants:

  \2|1/
  3\|/0
 ---+---
  4/|\7
  /5|6\

This implies that:

 dy = y1 - y0
 dx = x1 - x0

What we are really asking is this:

For some point on the line at <Xa,Ya>:

* What is the y location of the next adjacent pixel <Xa+1,?> ?

Using our line equation:

 Ya = f(x  ) = mx     + b
 Yb = f(x+1) = m(x+1) + b

Subtract the two equations:

 Ya - Yb = mx + b - (m(x+1) + b)
 Ya - Yb = mx + b -  m(x+1) - b
 Ya - Yb = mx - m(x+1)

Factor 'm':

 Ya - Yb = m*(x - (x+1))

Simplify 'x':

 Ya - Yb = m*(x - x - 1)
 Ya - Yb = m * -1

Substitute 'm':

 Ya - Yb = (dy/dx) * -1
 Ya - Yb = -dy/dx

Solve for 'Yb':

 Ya + dy/dx = Yb
 Yb = dy/dx + Ya

Hmm, that looks very familiar. :-)

However, our pixels are quantized. This means the pixel adjacent to our starting pixel <Xa,Ya> *must* either be at:

* <Xa+1, Ya>, or
* <Xa+1,Ya+1>


+----+----+
|    |Xa+1| 
|    |Ya+1| 
+----+----+  
| Xa |Xa+1|
| Ya |Ya  | 
+----+----+

Here is a picture to help:

https://salonibaweja10.files.wordpress.com/2014/09/screenshot-from-2014-09-10-233839.png

If we examine the vertical line at <Xa+1,?> we have this geometry:

 . <Xa+1,Ya+1>
 . <x,y>
 . <Xa+1,Ya>

How do we decide which one <Xa+1,Ya+1> or <Xa+1,Ya> is the "correct one" or "best" pixel ?

By examining the distance from the line to the two locations!

 . <Xa+1,Ya+1> Our quantized choice (b)
 ^
 |
 | d2
 |
 v
 . <x,y>  = <Xa+1,?> Actual point on the line
 ^
 |
 | d1
 |
 v
 . <Xa+1,Ya> Our quantized choice (a)

Note: NOTE to scale!

That is:

 d1 = y    - Ya
 d2 = Ya+1 - y
 
There are 2 cases to consider in order to determine which quantized pixel is closest to the actual line:

 d1 <= d2 then the adjacent pixel is at <Xa+1,Ya>
 d1 >  d2 then the adjacent pixel is at <Xa+1,Ya+1>

Instead of comparing d1, d2, we look at the sign of the two:

 s = d1 - d2

That is:

 if (s > 0) then we want <Xa+1,Ya>
 if (s < 0) then we want <Xa+1,Ya+1>

To be continued ...

References:

https://csustan.csustan.edu/~tom/Lecture-Notes/Graphics/Bresenham-Line/Bresenham-Line.pdf

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

#3141

Hi Michael,

Thanks much for this detailed example! It is very enlightening. Questions below. 

On Wednesday, October 19, 2016 at 8:54:06 PM UTC-5, Michael Pohoreski wrote:
> What we are really asking is this:
> 
> For some point on the line at <Xa,Ya>:
> 
> * What is the y location of the next adjacent pixel <Xa+1,?> ?

Makes sense. I'm rust on the equations but I think I followed the math you outlined to get here. 


> 
> Using our line equation:
> 
>  Ya = f(x  ) = mx     + b
>  Yb = f(x+1) = m(x+1) + b
> 
> Subtract the two equations:
> 
>  Ya - Yb = mx + b - (m(x+1) + b)
>  Ya - Yb = mx + b -  m(x+1) - b
>  Ya - Yb = mx - m(x+1)
> 
> Factor 'm':
> 
>  Ya - Yb = m*(x - (x+1))
> 
> Simplify 'x':
> 
>  Ya - Yb = m*(x - x - 1)
>  Ya - Yb = m * -1
> 
> Substitute 'm':
> 
>  Ya - Yb = (dy/dx) * -1
>  Ya - Yb = -dy/dx
> 
> Solve for 'Yb':
> 
>  Ya + dy/dx = Yb
>  Yb = dy/dx + Ya
> 
> Hmm, that looks very familiar. :-)
> 
> However, our pixels are quantized. This means the pixel adjacent to our starting pixel <Xa,Ya> *must* either be at:
> 
> * <Xa+1, Ya>, or
> * <Xa+1,Ya+1>

Ok, this was a lightbulb moment. If I understand correctly, said another way, from any given point on the line in this octant, the next pixel is always 1 pixel to the right on the x-axis and the choice is whether to increment the y-axis by 1 pixel or keep the y-axis the same. It's a binary choice; how appropriate :-)


> How do we decide which one <Xa+1,Ya+1> or <Xa+1,Ya> is the "correct one" or "best" pixel ?
> 
> By examining the distance from the line to the two locations!
> 
>  . <Xa+1,Ya+1> Our quantized choice (b)
>  ^
>  |
>  | d2
>  |
>  v
>  . <x,y>  = <Xa+1,?> Actual point on the line
>  ^
>  |
>  | d1
>  |
>  v
>  . <Xa+1,Ya> Our quantized choice (a)
> 
> Note: NOTE to scale!
> 
> That is:
> 
>  d1 = y    - Ya
>  d2 = Ya+1 - y


So I think the concept of this makes sense to me. The destination (x2, y2) is a fixed point on a grid. The current point on the line (Xa, Ya) is a fixed point on the grid. Either (Xa+1, Ya) or (Xa+1, Ya+1) is closer to x2,y2, and the pixel that is closer is the the next best pixel in the line. Or if both options are the same distance that either pixel works equally well.  

Is that correct?

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. 

Thanks again!

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

#3142

On Thursday, October 20, 2016 at 11:17:11 AM UTC-7, Mark Lemmert wrote:
> Hi Michael,
> 
> Thanks much for this detailed example! It is very enlightening. Questions below. 

Sadly I won't be able to write up part 2 tonight, but I can answer your some questions tonight before I'm out ...


> So I think the concept of this makes sense to me. The destination (x2, y2) is a fixed point on a grid. The current point on the line (Xa, Ya) is a fixed point on the grid. Either (Xa+1, Ya) or (Xa+1, Ya+1) is closer to x2,y2, and the pixel that is closer is the the next best pixel in the line.

Either (Xa+1, Ya) or (Xa+1, Ya+1) is closer to a point on the line end point at (x2,y2), but yes, your thinking is basically correct.

> Or if both options are the same distance that either pixel works equally well.  
> Is that correct?

Yes. Either point could exactly be the same distance away.  As long as you are consistent it doesn't matter (too much) which one you pick.

 
> 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.

There is an alternative derivation, that is much simpler -- I'm debating whether or not to use that explanation.  I might end up using both.

I'll keep you posted !

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

#3143

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 why calculating the distance gets hairy :-)

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


Mark

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

#3158

I threw this demo together to see how the various line algorithms compare:

http://htmlpreview.github.io/?https://raw.githubusercontent.com/Michaelangel007/js_bresenham_line/master/index.html

https://cdn.rawgit.com/Michaelangel007/js_bresenham_line/master/index.html

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

#3136

On Friday, October 7, 2016 at 10:23:26 AM UTC-7, Mark Lemmert wrote:
> Many thanks to Michael Pohoreski for his post earlier this year giving a detailed example of this concept!
> https://groups.google.com/forum/#!topic/comp.sys.apple2.programmer/cgxZOBIL728
> 
> Very helpful in pulling this together.  

I still need to catch up on your last post but glad I was able to help !

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web