Exact match. Not showing close matches.
PICList
Thread
'[PIC]:16bit/32bit Replacements for PIC16c7xx serie'
2001\04\01@154539
by
James Lee Williams

Hello,
Can some give me some alternative replacement microcontrollers which
provide at least a Parrallel slave port, PWM and timer modules and that
are RISC processors which are 16bit or 32bit cores. I need more
powerfull solution for controlling XY coordinated motion and it seems
that the PIC is just not suited for the job, because of the data size.
I am trying to control axis with 60" travels or more and need at least
24bit variables where the simple addition/substractions take only a
single cycle. Today, I am finding that just to cacluate the delt of
motion for one axis, it takes at least 35 cycles or more for 24bit on
the PIC micro. It takes 3 cycles to move X1 to arithmatic register,
another 3 cycles to move X2. Then another 25 to do the addition and
ther another 3 cycles to move the result. Now, I am attempting to use
the Bresenham algorithm to calculate step and direction signals for two
stepper motors on a 200steps/rev with a .1" lead screw. And the time to
do all of these basic simple calculations will not give me high enough
motion speeds even from a 20MHz Clock speeds.
Also, I am looking for one where I can get a cheep programmer and that
has an ASM editor and compiler similar to the MPLAB from microchip. I
am doing this as a hobbiest, so I don't have the finacial resources to
pay $1000 or greate that some of there places want for just the
developement environment.
Regards,
James

http://www.piclist.com hint: To leave the PICList
spam_OUTpiclistunsubscriberequestTakeThisOuTmitvma.mit.edu
2001\04\02@090754
by
Olin Lathrop
>>
Can some give me some alternative replacement microcontrollers which
provide at least a Parrallel slave port, PWM and timer modules and that
are RISC processors which are 16bit or 32bit cores. I need more
powerfull solution for controlling XY coordinated motion and it seems
that the PIC is just not suited for the job, because of the data size.
I am trying to control axis with 60" travels or more and need at least
24bit variables where the simple addition/substractions take only a
single cycle. Today, I am finding that just to cacluate the delt of
motion for one axis, it takes at least 35 cycles or more for 24bit on
the PIC micro. It takes 3 cycles to move X1 to arithmatic register,
another 3 cycles to move X2. Then another 25 to do the addition and
ther another 3 cycles to move the result. Now, I am attempting to use
the Bresenham algorithm to calculate step and direction signals for two
stepper motors on a 200steps/rev with a .1" lead screw. And the time to
do all of these basic simple calculations will not give me high enough
motion speeds even from a 20MHz Clock speeds.
<<
How fast DO you need it? Are you just a little off or a lot? 35
instructions at 20MHz clock is 7uS, or a rate of 143KHz. Would a 18Cxxx
running at twice that rate work?
********************************************************************
Olin Lathrop, embedded systems consultant in Littleton Massachusetts
(978) 7429014, .....olinKILLspam@spam@embedinc.com, http://www.embedinc.com

http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: >uP ONLY! [EE]:,[OT]: >Other [BUY]:,[AD]: >Ads
2001\04\02@094948
by
Bob Ammerman

> motion for one axis, it takes at least 35 cycles or more for 24bit on
> the PIC micro. It takes 3 cycles to move X1 to arithmatic register,
> another 3 cycles to move X2. Then another 25 to do the addition and
> ther another 3 cycles to move the result.
This seems rather excessive:
Given: X1 and X2 and RESULT are each 3 bytes long
movf X1,W
movwf RESULT
movf X1+1,W
movwf RESULT
movf X1+2,W
movwf RESULT
movf X2,W
addwf RESULT,F
movf X2+1,W
skpnc
incfsz X2+1,W
addwf RESULT+1,F
movf X2+2,W
skpnc
incfsz X2+2,W
addwf RESULT+2,F
16 total cycles to add two 24bit numbers and store the result in a third
number
If your answer overwrites one of your arguments (eg: X1 = X1+X2) then the
code is even shorter:
movf X2,W
addwf X1,F
movf X2+1,W
skpnc
incfsz X2+1,W
addwf X1+1,F
movf X2+2,W
skpnc
incfsz X2+2,W
addwf X1+2,F
Now it is just 10 cycles.
On an 18C it can be even faster:
movf X2,W
addwf X1,F
movf X2+1,W
addwfc X1+1,F
movf X2+2,W
addwfc X1+2,F
Just 6 cycles. And an 18C can go up to 10MIPs. So this would be only 0.6uS
per 24 bit add (or 1.2uS per add if the result isn't one of the addends).
Bob Ammerman
RAm Systems
(contract development of high performance, high function, lowlevel
software)

http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: >uP ONLY! [EE]:,[OT]: >Other [BUY]:,[AD]: >Ads
2001\04\02@101001
by
James Lee Williams
Yes this is an expensive operation if you consider this is just one
single addition operation when calculating Bresenham. I also have in
the background, packets coming in from the parrallel port from a PC,
which have to arrive within a reasonable time. I think it make take 100
instruction cycles or more to get a single byte from the parrallel port.
I did however calculate my worst case timing senerio of 100micoseconds
max, and that didn't take into account parrallel loading. If I can
calculate my next position in less than that, my linear motion can
achieve 10inchs per second or 600 inches per minute. This is a key
factor in the whole mess of things.
Regards,
James
{Original Message removed}
2001\04\02@150709
by
Olin Lathrop
>
Yes this is an expensive operation if you consider this is just one
single addition operation when calculating Bresenham. I also have in
the background, packets coming in from the parrallel port from a PC,
which have to arrive within a reasonable time. I think it make take 100
instruction cycles or more to get a single byte from the parrallel port.
I did however calculate my worst case timing senerio of 100micoseconds
max, and that didn't take into account parrallel loading. If I can
calculate my next position in less than that, my linear motion can
achieve 10inchs per second or 600 inches per minute. This is a key
factor in the whole mess of things.
<
The Bresenham algorithm only requires a single add operation per cycle.
This sounds like a small fraction of your overall 100uS requirement. With a
16xxx PIC running at 20MHz you get 500 instruction in 100uS, which sounds
like enough. With an 18xxx you get twice that many.
********************************************************************
Olin Lathrop, embedded systems consultant in Littleton Massachusetts
(978) 7429014, olinKILLspamembedinc.com, http://www.embedinc.com

http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: >uP ONLY! [EE]:,[OT]: >Other [BUY]:,[AD]: >Ads
2001\04\02@180453
by
James Lee Williams
Show me a version of Bresenham line algorithm where there is only one
addition per step.
As I see it, there is at least one addition and two subtractions.
We accumulate the error, that is one addition.
We shift left the error one for multiply by two.
We compare error with deltax which requires a subtraction at minimum.
That is one subtraction.
Based on the comparision, we may subtract deltax from the error and
increment the y axis. That is two subtractions.
Regards,
James
{Original Message removed}
2001\04\02@180655
by
Olin Lathrop
{Quote hidden}> Given: X1 and X2 and RESULT are each 3 bytes long
>
> movf X1,W
> movwf RESULT
> movf X1+1,W
> movwf RESULT
> movf X1+2,W
> movwf RESULT
>
> movf X2,W
> addwf RESULT,F
>
> movf X2+1,W
> skpnc
> incfsz X2+1,W
> addwf RESULT+1,F
>
> movf X2+2,W
> skpnc
> incfsz X2+2,W
> addwf RESULT+2,F
I like your method of SKIPNC followed by INCFSZ, I hadn't thought of that.
I have been using a far more clunky method with a temp variable to deal with
carry from propagate carry.
However, in case anyone may be copying and pasting this code, the last two
MOVWF in the first block should be to RESULT+1 and RESULT+2.
********************************************************************
Olin Lathrop, embedded systems consultant in Littleton Massachusetts
(978) 7429014, .....olinKILLspam.....embedinc.com, http://www.embedinc.com

http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: >uP ONLY! [EE]:,[OT]: >Other [BUY]:,[AD]: >Ads
2001\04\02@184455
by
Bob Ammerman

{Quote hidden}> > Given: X1 and X2 and RESULT are each 3 bytes long
> >
> > movf X1,W
> > movwf RESULT
> > movf X1+1,W
> > movwf RESULT
> > movf X1+2,W
> > movwf RESULT
> >
> > movf X2,W
> > addwf RESULT,F
> >
> > movf X2+1,W
> > skpnc
> > incfsz X2+1,W
> > addwf RESULT+1,F
> >
> > movf X2+2,W
> > skpnc
> > incfsz X2+2,W
> > addwf RESULT+2,F
>
> I like your method of SKIPNC followed by INCFSZ, I hadn't thought of that.
> I have been using a far more clunky method with a temp variable to deal
with
> carry from propagate carry.
>
> However, in case anyone may be copying and pasting this code, the last two
> MOVWF in the first block should be to RESULT+1 and RESULT+2.
>
> Olin Lathrop
oops!
By the way: I didn't invent this. It is in one of the Microchop app notes
and I've seen it used all over the place.
Bob Ammerman
RAm Systems
(contract development of high performance, high function, lowlevel
software)

http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: >uP ONLY! [EE]:,[OT]: >Other [BUY]:,[AD]: >Ads
2001\04\02@235516
by
Scott Dattalo

On Mon, 2 Apr 2001, Olin Lathrop wrote:
{Quote hidden}> > Given: X1 and X2 and RESULT are each 3 bytes long
> >
> > movf X1,W
> > movwf RESULT
> > movf X1+1,W
> > movwf RESULT
> > movf X1+2,W
> > movwf RESULT
> >
> > movf X2,W
> > addwf RESULT,F
> >
> > movf X2+1,W
> > skpnc
> > incfsz X2+1,W
> > addwf RESULT+1,F
> >
> > movf X2+2,W
> > skpnc
> > incfsz X2+2,W
> > addwf RESULT+2,F
>
> I like your method of SKIPNC followed by INCFSZ, I hadn't thought of that.
> I have been using a far more clunky method with a temp variable to deal with
> carry from propagate carry.
>
> However, in case anyone may be copying and pasting this code, the last two
> MOVWF in the first block should be to RESULT+1 and RESULT+2.
Is it worth mentioning that you can save one instruction? Or how about two more
if you don't care about the carry out?
Scott

http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: >uP ONLY! [EE]:,[OT]: >Other [BUY]:,[AD]: >Ads
2001\04\03@090136
by
Olin Lathrop
>>
Show me a version of Bresenham line algorithm where there is only one
addition per step.
As I see it, there is at least one addition and two subtractions.
We accumulate the error, that is one addition.
We shift left the error one for multiply by two.
We compare error with deltax which requires a subtraction at minimum.
That is one subtraction.
Based on the comparision, we may subtract deltax from the error and
increment the y axis. That is two subtractions.
<<
Bresenham's algorithm works on 3 numbers. I'll call them E, DEA, and DEB.
Once the setup is over, the algorithm goes like this:
loop:
if E >= 0
then
<take a B step>
E < E + DEB
else
<take an A step>
E < E + DEA
endif
goto loop;
The IF merely requires checking the sign bit of E, so I don't consider that
an "operation". You do have to add either DEA or DEB into E each step.
That's the add operation I was talking about. The A step and B step
operations are up to you, but an A step is usually advancing by 1 in the
minor axis, and a B step is leaving the minor axis value alone. What you do
with the major axis is also up to you, but you would usually advance it by
1. You also will need to terminate the loop. Since the number of
iterations can be determined ahead of time, this is usually just
decrementing a counter until it reaches zero.
So there is only one real math "operation" required, but I should have
mentioned the additional 2 or 3 increment/decrement operations per
iteration.
I don't know where you came up with the parts about shifting the error left
one bit and comparing it to deltax. I think you may be confusing the setup
with the running operation. There is lots of literature on this. You may
even be able to find Jack Bresenham's original paper in the IBM journal.
********************************************************************
Olin Lathrop, embedded systems consultant in Littleton Massachusetts
(978) 7429014, EraseMEolinspam_OUTTakeThisOuTembedinc.com, http://www.embedinc.com

http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics
2001\04\03@100642
by
James Lee Williams

I have personally never seen this version of the Bresenham.
At first look, I notice that your decision voxel determines if it will
set the y or the x value. When in fact, one axis will always make a
step regardless of any condition, except the end of the move opertion.
I would like to see the full algorithm you are using, because I have
been searching the net for days and none of the sites and links show it
this way. I basic algorithm I have been seeing all along is:
for(x=x1;x <= x2;x++)
{
<take an a step>
if((eps << 1) >= DeltaX)
{
<take an b step>
eps = DeltaX;
}
}
The pseudocode algorithm for this routine is written as:
E < 0, Y <Y1
FOR X <X1 TO X2 DO
STEP X
IF(E + M > 0.5)
E < (E+M)
ELSE Y < Y  1
E < E + M + 1
ENDIF
END FOR
This appears to look close to your method, but not completely. You see,
these are the algorithms that I keep finding when I search the web for
the Bresenham algorithm.
I like your solution, it is much simpler, but I can find any reference
to it on the web at all.
Regards,
James
{Original Message removed}
2001\04\03@101058
by
James Lee Williams
Oh, what I forgot to mention also is that every version of the this
algorithm was being used for graphics and hand nothing to do with
motion. Oh course if there is a different alogithm used for motion,
where can I find it? This seems to simplify the mater a lot. It there
one for a circle too?
Regards,
James
{Original Message removed}
2001\04\03@102015
by
Bob Ammerman
Lets see what we can do to transform this:
for(x=x1;x <= x2;x++)
{
<take an a step>
if((eps << 1) >= DeltaX)
{
<take an b step>
eps = DeltaX;
}
}
into something more effecient.
First
if ((eps << 1) >= DeltaX
Is (roughly, except for possible rounding issues) equivalent to:
if (eps >= DeltaX / 2)
But if we subtract DeltaX/2 from X before entering the loop then we have:
if (eps >= 0)
So now we have:
eps = DeltaX >> 1;
for(x=x1;x <= x2;x++)
{
<take an a step>
if(eps >= 0)
{
<take an b step>
eps = DeltaX;
}
}
Is that a little simpler?
Bob Ammerman
RAm Systems
(contract development of high performance, high function, lowlevel
software)

http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics
2001\04\03@102025
by
Bob Ammerman
>Oh, what I forgot to mention also is that every version of the this
>algorithm was being used for graphics and hand nothing to do with
>motion. Oh course if there is a different alogithm used for motion,
>where can I find it? This seems to simplify the mater a lot. It there
>one for a circle too?
>Regards,
>James
Yes, there is a Bresenham like algorithm for circles. It is basically a
second order extension of the line drawing algorithm. (You run a difference
equation on the DeltaX value as you go).
You should find this in any good book on graphics.
Bob Ammerman
RAm Systems
(contract development of high performance, high function, lowlevel
software)

http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics
2001\04\03@103012
by
James Lee Williams
Will this work for all octants of the coordinate system?
I now see the Bresenham completely transformed from what I have found,
which is good, because this is much more efficient.
Thanks,
James
{Original Message removed}
2001\04\03@103924
by
James Lee Williams
Opps serious error in my example I forgot to add the error voxel.
Should be:
for(x=x1; x<= x2;x++)
{
<take an x step>
eps += DeltaY; //Accumulated error ob deltay.
if((eps<<1) >= DeltaX)
{
<take an y step>
eps = DeltaX;
}
}
As I see this, It is as simple as it can be.
{Original Message removed}
2001\04\03@105023
by
Alan B. Pearce
>algorithm was being used for graphics and hand nothing to do with
>motion. Oh course if there is a different alogithm used for motion,
I would have thought in this context that graphics was "virtual motion" :)
After all you are doing the equivalent of XY motion when drawing the line  the
fact that there may be a colour filling operation afterwards/included is neither
here nor there.

http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics
2001\04\03@123321
by
Bob Ammerman
Oops serious error in my example I forgot to add the error voxel.
Should be:
for(x=x1; x<= x2;x++)
{
<take an x step>
eps += DeltaY; file://Accumulated error ob deltay.
if((eps<<1) >= DeltaX)
{
<take an y step>
eps = DeltaX;
}
}
As I see this, It is as simple as it can be.
Not at all.
Try this:
eps += DeltaY;
eps = DeltaX >> 1;
DeltaYmX = DeltaY  DeltaX;
for (x == x1; x<= x2; x++)
{
<take an x step>
if (eps >= 0)
<take a y step>
eps += DeltaYmX;
}
else
{
eps += DeltaY;
}
}
Now it looks a lot like Olin's version, doesn't it?
Bob Ammerman
RAm Systems
(contract development of high performance, high function, lowlevel
software)

http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics
2001\04\03@131100
by
Olin Lathrop
> for(x=x1;x <= x2;x++)
> {
> <take an a step>
> if(eps >= 0)
> {
> <take an b step>
> eps = DeltaX;
> }
> }
I didn't look thru how you got here, but EPS needs to be adjusted each
iteration, else you will never stop taking just A steps once you start.
Also, the point is to take an A *or* B step each iteration.
********************************************************************
Olin Lathrop, embedded systems consultant in Littleton Massachusetts
(978) 7429014, olinspam_OUTembedinc.com, http://www.embedinc.com

http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics
2001\04\03@131115
by
Olin Lathrop
> I have personally never seen this version of the Bresenham.
> At first look, I notice that your decision voxel determines if it will
> set the y or the x value.
I don't know what you mean by "decision voxel". Bresenham's original
algorithm was intended to draw a straight line between two pixels on a
plotter. The major axis was implicitly advanced by 1 each iteration. The
algorithm determines whether the minor axis is advanced by 1 or not for each
iteration. In other words, its job is to produce 1 bit of information each
iteration.
> When in fact, one axis will always make a
> step regardless of any condition, except the end of the move opertion.
Right. That's the major axis.
> I would like to see the full algorithm you are using, because I have
> been searching the net for days and none of the sites and links show it
> this way. I basic algorithm I have been seeing all along is:
>
> ...
>
> I like your solution, it is much simpler, but I can find any reference
> to it on the web at all.
What I posted is pretty much the standard way to do it. It is documented
lots of places, including Bresenham's original paper in the IBM Systems
Journal, Volume 4, Number 1, January 1965, pages 2530. I just looked at
the standard reference for computer graphics by Foley and Van Dam,
"Fundamentals of Interactive Computer Graphics", published by
AddisonWesley. They go thru a nice derivation then show the complete
algorithm. I wrote a paper once on how to extend Bresenham's algorithm so
the endpoints can be anywhere in a pixel, not just at the centers. This
paper includes a complete derivation of the basic algorithm, "Accurate
Rendering by Subpixel Addressing", IEEE Computer Graphics and Applications,
September 1990, pages 4553.
********************************************************************
Olin Lathrop, embedded systems consultant in Littleton Massachusetts
(978) 7429014, @spam@olinKILLspamembedinc.com, http://www.embedinc.com

http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics
2001\04\03@131124
by
Olin Lathrop
>>
Oh, what I forgot to mention also is that every version of the this
algorithm was being used for graphics and hand nothing to do with
motion. Oh course if there is a different alogithm used for motion,
where can I find it? This seems to simplify the mater a lot. It there
one for a circle too?
<<
Bresenham's original algorithm WAS for motion. He was moving an object
above a fixed table, you are trying to move the table. You have things
above the table like a drill or a router. He had a pen. Same thing.
By the way Bresenham developed the algorithm because the traditional
slope/fraction method wasn't fast enough on the limited computer available
to drive the plotter.
********************************************************************
Olin Lathrop, embedded systems consultant in Littleton Massachusetts
(978) 7429014, KILLspamolinKILLspamembedinc.com, http://www.embedinc.com

http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics
More... (looser matching)
 Last day of these posts
 In 2001
, 2002 only
 Today
 New search...