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

Groups > comp.lang.c > #53998 > unrolled thread

C-Programming

Back to article view | Back to comp.lang.c

Contents

  C-Programming arvindgupta01031988@gmail.com - 2014-12-06 11:09 -0800
    Re: C-Programming "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2014-12-06 11:16 -0800
    Re: C-Programming James Kuyper <jameskuyper@verizon.net> - 2014-12-06 14:46 -0500
      Re: C-Programming Kleuske <kleuske@nowhere.net> - 2014-12-07 10:48 +0000
        Re: C-Programming Keith Thompson <kst-u@mib.org> - 2014-12-07 07:43 -0800
    Re: C-Programming Siri Crews <chine.bleu@yahoo.com> - 2014-12-06 12:22 -0800
      Re: C-Programming gordonb.ukogy@burditt.org (Gordon Burditt) - 2014-12-19 03:29 -0600
        Re: C-Programming Siri Crews <chine.bleu@yahoo.com> - 2014-12-19 01:34 -0800
          Re: C-Programming Richard Heathfield <invalid@see.sig.invalid> - 2014-12-19 10:18 +0000
            Re: C-Programming jacob navia <jacob@spamsink.net> - 2014-12-19 17:42 +0100
              Re: C-Programming rouben@shadow.(none) (Rouben Rostamian) - 2014-12-19 19:00 +0000
                Re: C-Programming jacob navia <jacob@spamsink.net> - 2014-12-19 20:31 +0100
                  Re: C-Programming jacob navia <jacob@spamsink.net> - 2014-12-19 20:42 +0100
                Re: C-Programming Keith Thompson <kst-u@mib.org> - 2014-12-19 11:54 -0800
          Re: C-Programming raltbos@xs4all.nl (Richard Bos) - 2014-12-19 11:29 +0000
            Re: C-Programming Noob <root@127.0.0.1> - 2014-12-20 10:22 +0100
              Re: C-Programming Keith Thompson <kst-u@mib.org> - 2014-12-20 11:48 -0800
          Re: C-Programming Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-12-19 03:33 -0800
            Re: C-Programming Siri Crews <chine.bleu@yahoo.com> - 2014-12-19 04:02 -0800
        Re: C-Programming glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-12-19 17:28 +0000
    Re: C-Programming jacob navia <jacob@spamsink.net> - 2014-12-06 21:27 +0100
    Re: C-Programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-12-07 13:07 +0000
    Re: C-Programming David Brown <david.brown@hesbynett.no> - 2014-12-08 01:24 +0100
      Re: C-Programming Tim Rentsch <txr@alumni.caltech.edu> - 2014-12-16 04:44 -0800
        Re: C-Programming David Brown <david.brown@hesbynett.no> - 2014-12-16 15:02 +0100
          Re: C-Programming BartC <bc@freeuk.com> - 2014-12-16 18:27 +0000
            Re: C-Programming David Brown <david.brown@hesbynett.no> - 2014-12-17 01:01 +0100
              Re: C-Programming BartC <bc@freeuk.com> - 2014-12-17 00:23 +0000
          Re: C-Programming Tim Rentsch <txr@alumni.caltech.edu> - 2014-12-16 16:30 -0800
            Re: C-Programming David Brown <david.brown@hesbynett.no> - 2014-12-17 02:18 +0100
              Re: C-Programming Tim Rentsch <txr@alumni.caltech.edu> - 2014-12-16 18:23 -0800
                Re: C-Programming David Brown <david.brown@hesbynett.no> - 2014-12-17 09:59 +0100
                  Re: C-Programming Tim Rentsch <txr@alumni.caltech.edu> - 2014-12-17 08:52 -0800
                    Re: C-Programming David Brown <david.brown@hesbynett.no> - 2014-12-18 11:11 +0100
                      Re: C-Programming Tim Rentsch <txr@alumni.caltech.edu> - 2014-12-18 09:49 -0800
            Re: C-Programming JohnF <john@please.see.sig.for.email.com> - 2014-12-17 10:14 +0000
              Re: C-Programming Richard Heathfield <invalid@see.sig.invalid> - 2014-12-17 14:26 +0000
                Re: C-Programming Tim Rentsch <txr@alumni.caltech.edu> - 2014-12-17 09:13 -0800
                  Re: C-Programming Richard Heathfield <invalid@see.sig.invalid> - 2014-12-17 17:34 +0000
                    Re: C-Programming Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-12-17 23:26 -0800
                      Re: C-Programming Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-12-18 00:21 -0800
                      Re: C-Programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-12-18 17:06 +0000
                        Re: C-Programming Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-12-18 09:29 -0800
                          Re: C-Programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-12-19 02:36 +0000
                            Re: C-Programming Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-12-19 03:41 -0800
                    Re: C-Programming Tim Rentsch <txr@alumni.caltech.edu> - 2014-12-18 08:52 -0800
                Re: C-Programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-12-17 23:23 +0000
                  Re: C-Programming BartC <bc@freeuk.com> - 2014-12-18 00:02 +0000
                  Re: C-Programming Richard Heathfield <invalid@see.sig.invalid> - 2014-12-18 00:15 +0000
                    Re: C-Programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-12-18 16:37 +0000
                      Re: C-Programming Richard Heathfield <invalid@see.sig.invalid> - 2014-12-18 18:08 +0000
                        Re: C-Programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-12-19 02:40 +0000
                          Re: C-Programming Richard Heathfield <invalid@see.sig.invalid> - 2014-12-19 07:51 +0000
              Re: C-Programming Tim Rentsch <txr@alumni.caltech.edu> - 2014-12-17 09:07 -0800
                Re: C-Programming JohnF <john@please.see.sig.for.email.com> - 2014-12-19 04:22 +0000
                  Re: C-Programming Tim Rentsch <txr@alumni.caltech.edu> - 2014-12-19 09:22 -0800
                    Re: C-Programming Greg Martin <greg.at.softsprocket@dot.com> - 2014-12-20 02:39 +0000
                      Re: C-Programming JohnF <john@please.see.sig.for.email.com> - 2014-12-20 06:57 +0000
    Re: C-Programming Tim Rentsch <txr@alumni.caltech.edu> - 2014-12-15 23:53 -0800

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

#54912

On Thursday, December 18, 2014 7:26:34 AM UTC, Malcolm McLean wrote:
> On Wednesday, December 17, 2014 5:34:16 PM UTC, Richard Heathfield wrote:
>
> You do that for x and y. If either delta1_x or delta1_y goes over
> 0.5, halve all the delta values. If it goes  below 0.125, double
> them.
>
To clarify, you need to halve and double d,  delta1, delta2 and delta3 
are then given by the formula.  

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

#54966

Malcolm McLean <malcolm.mclean5@btinternet.com> writes:

> On Wednesday, December 17, 2014 5:34:16 PM UTC, Richard Heathfield wrote:
>> 
>> Thank you. I wasn't aware of that. My Bezier-drawing function uses only 
>> two control points (I /was/ aware that you can use more, but two seemed
>> to me to be a sufficiency for the time being), 
>>
>> It has, of course, become the tradition, when I post ancient code, for 
>> people to find a good half-dozen bugs in it. No doubt the same will happen 
>> here. But this code does draw splines, really it does. :-)
>> 
> It's a reasonable approach, but not very fast or high quality.
> You won't get every pixel for extreme curves, and you're calling
> a lot of multiplications.
> You can draw a Bezier a lot faster by forwards differencing.
>
> First express as two cubics in x and y, with t being the time variable.
>
>       a3 = -x0 + 3 * cpax + -3 * cpbx + x3;
> 	a2 = 3 * x0 + -6 * cpax + 3 * cpbx;
> 	a1 = -3 * x0 + 3 * cpax;
> 	a0 = x0
>
> Now we can draw a cubic at 100 points by calculating 
>
> f(t) = a0 + a1*t + a2*t^2 + a3*t^3
>
> d  = 0.01
>
> the forward difference algorithm becomes
> t[0] = 0;
> f(0) = a0;
> delta1 = a1 *d + a2 *d^2 + a3*d^3
> delta2 = 2*a2*d^2 + 6*a3*d^3
> delta3 = 6 *a3 *d^3
> for i = 1 to k do
>    t[i] = t[i-1] + d
>    f(t[i]) = f(t[i-1]) + delta1
>   delta1 = delta1 + delta2
>   delta2 = delta2 + delta3
> endfor
>
> You do that for x and y.

Being for a fixed number of steps, this has the same problem of missed
pixels and/or not producing tight curves very well.  But...

> If either delta1_x or delta1_y goes over
> 0.5, halve all the delta values. If it goes  below 0.125, double
> them. Then you're sampling at sub-Nyquist frequency, with is 0.5
> of the grid and guaranteed a pixel-perfect curve.

I don't follow this.  My (no doubt naive) attempt to code your halving
and doubling does not produce the right curve.  Can you give the pseudo
code for this pixel-correct version?

-- 
Ben.

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

#54972

On Thursday, December 18, 2014 5:07:03 PM UTC, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
> 
> > If either delta1_x or delta1_y goes over
> > 0.5, halve all the delta values. If it goes  below 0.125, double
> > them. Then you're sampling at sub-Nyquist frequency, with is 0.5
> > of the grid and guaranteed a pixel-perfect curve.
> 
> I don't follow this.  My (no doubt naive) attempt to code your halving
> and doubling does not produce the right curve.  Can you give the pseudo
> code for this pixel-correct version?
> 
I way over-simplified this.

The forwards differencing gives us three sets of values that represent
steps in a delta t, say 0.01. To get 100 x, y values, we add delta1
to our start point. Then we add delta2 to delta1 to give us the 
next increment. Then we add delta3 to delta2 to give us the next
increment to delta2. That's where it stops, since it's cubic, 
it only has three levels of difference. (You can use the same principle
for polynomials of arbitrary high degree).

If the step size is too large, we want to halve delta1. But we
can't just halve delta2 and delta3. 

You've got to work back.

I just looked up the formula. However when I check, I see there's
actually a bug. dt is not halved and doubled, though it is very
nearly.

while (fabs(firstFDX) + fabs(firstFDY) > 1)
{
thirdXprime = thirdFDX / 8;
			secondXprime = secondFDX / 4 - thirdXprime;
			firstXprime = firstFDX / 2;

			thirdYprime = thirdFDY / 8;
			secondYprime = secondFDY / 4 - thirdYprime;
			firstYprime = firstFDY / 2;

			firstFDX = firstXprime;
			secondFDX = secondXprime;
			thirdFDX = thirdXprime;

			firstFDY = firstYprime;
			secondFDY = secondYprime;
			thirdFDY = thirdYprime;

			dt /= 2;
		}
		while (fabs(firstFDX) + fabs(firstFDY) < 0.25)
		{
			firstXprime = firstFDX * 2 + secondFDX;
			secondXprime = (secondFDX + thirdFDX) * 4;
			thirdXprime = thirdFDX * 8;

			firstYprime = firstFDY * 2 + secondFDY;
			secondYprime = (secondFDY + thirdFDY) * 4;
			thirdYprime = thirdFDY * 8;

			firstFDX = firstXprime;
			secondFDX = secondXprime;
			thirdFDX = thirdXprime;

			firstFDY = firstYprime;
			secondFDY = secondYprime;
			thirdFDY = thirdYprime;

			dt *= 2;
		}

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

#55030

Malcolm McLean <malcolm.mclean5@btinternet.com> writes:

> On Thursday, December 18, 2014 5:07:03 PM UTC, Ben Bacarisse wrote:
>> Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
>> 
>> > If either delta1_x or delta1_y goes over
>> > 0.5, halve all the delta values. If it goes  below 0.125, double
>> > them. Then you're sampling at sub-Nyquist frequency, with is 0.5
>> > of the grid and guaranteed a pixel-perfect curve.
>> 
>> I don't follow this.  My (no doubt naive) attempt to code your halving
>> and doubling does not produce the right curve.  Can you give the pseudo
>> code for this pixel-correct version?
>> 
> I way over-simplified this.
>
> The forwards differencing gives us three sets of values that represent
> steps in a delta t, say 0.01. To get 100 x, y values, we add delta1
> to our start point. Then we add delta2 to delta1 to give us the 
> next increment. Then we add delta3 to delta2 to give us the next
> increment to delta2. That's where it stops, since it's cubic, 
> it only has three levels of difference. (You can use the same principle
> for polynomials of arbitrary high degree).
>
> If the step size is too large, we want to halve delta1. But we
> can't just halve delta2 and delta3. 
>
> You've got to work back.
>
> I just looked up the formula. However when I check, I see there's
> actually a bug. dt is not halved and doubled, though it is very
> nearly.

I don't follow this.

> while (fabs(firstFDX) + fabs(firstFDY) > 1)
> {
> thirdXprime = thirdFDX / 8;
> 			secondXprime = secondFDX / 4 - thirdXprime;
> 			firstXprime = firstFDX / 2;
>
> 			thirdYprime = thirdFDY / 8;
> 			secondYprime = secondFDY / 4 - thirdYprime;
> 			firstYprime = firstFDY / 2;

I think you have a bug.  As written, the two curves (equal dt and
adaptive dt) don't match, but I found a paper that describes this method
("Adaptive Forward Differencing for Rendering Curves and Surfaces" by
Lien, Shantz and Pratt) and that has (translated into your form)

  firstXprime = firstFDX / 2 - secondXprime / 2;

Anyway, thanks for this.  With that correction the two curves match and
I have another adaptive spline method.

> 			firstFDX = firstXprime;
> 			secondFDX = secondXprime;
> 			thirdFDX = thirdXprime;
>
> 			firstFDY = firstYprime;
> 			secondFDY = secondYprime;
> 			thirdFDY = thirdYprime;
>
> 			dt /= 2;
> 		}
> 		while (fabs(firstFDX) + fabs(firstFDY) < 0.25)
> 		{
> 			firstXprime = firstFDX * 2 + secondFDX;
> 			secondXprime = (secondFDX + thirdFDX) * 4;
> 			thirdXprime = thirdFDX * 8;
>
> 			firstYprime = firstFDY * 2 + secondFDY;
> 			secondYprime = (secondFDY + thirdFDY) * 4;
> 			thirdYprime = thirdFDY * 8;
>
> 			firstFDX = firstXprime;
> 			secondFDX = secondXprime;
> 			thirdFDX = thirdXprime;
>
> 			firstFDY = firstYprime;
> 			secondFDY = secondYprime;
> 			thirdFDY = thirdYprime;
>
> 			dt *= 2;
> 		}

-- 
Ben.

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

#55054

On Friday, December 19, 2014 2:36:32 AM UTC, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
> 
> > On Thursday, December 18, 2014 5:07:03 PM UTC, Ben Bacarisse wrote:
> >> Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
> >> 
> >> > If either delta1_x or delta1_y goes over
> >> > 0.5, halve all the delta values. If it goes  below 0.125, double
> >> > them. Then you're sampling at sub-Nyquist frequency, with is 0.5
> >> > of the grid and guaranteed a pixel-perfect curve.
> >> 
> >> I don't follow this.  My (no doubt naive) attempt to code your halving
> >> and doubling does not produce the right curve.  Can you give the pseudo
> >> code for this pixel-correct version?
> >> 
> > I way over-simplified this.
> >
> > The forwards differencing gives us three sets of values that represent
> > steps in a delta t, say 0.01. To get 100 x, y values, we add delta1
> > to our start point. Then we add delta2 to delta1 to give us the 
> > next increment. Then we add delta3 to delta2 to give us the next
> > increment to delta2. That's where it stops, since it's cubic, 
> > it only has three levels of difference. (You can use the same principle
> > for polynomials of arbitrary high degree).
> >
> > If the step size is too large, we want to halve delta1. But we
> > can't just halve delta2 and delta3. 
> >
> > You've got to work back.
> >
> > I just looked up the formula. However when I check, I see there's
> > actually a bug. dt is not halved and doubled, though it is very
> > nearly.
> 
> I don't follow this.
> 
> > while (fabs(firstFDX) + fabs(firstFDY) > 1)
> > {
> > thirdXprime = thirdFDX / 8;
> > 			secondXprime = secondFDX / 4 - thirdXprime;
> > 			firstXprime = firstFDX / 2;
> >
> > 			thirdYprime = thirdFDY / 8;
> > 			secondYprime = secondFDY / 4 - thirdYprime;
> > 			firstYprime = firstFDY / 2;
> 
> I think you have a bug.  As written, the two curves (equal dt and
> adaptive dt) don't match, but I found a paper that describes this method
> ("Adaptive Forward Differencing for Rendering Curves and Surfaces" by
> Lien, Shantz and Pratt) and that has (translated into your form)
> 
>   firstXprime = firstFDX / 2 - secondXprime / 2;
> 
> Anyway, thanks for this.  With that correction the two curves match and
> I have another adaptive spline method.
> 
Thank you.
It just goes to show that you really need to work through mathematics
yourself. Unfortunately a lot the Bezier stuff I've been doing has
been very difficult (for me, I don't think a professional mathematician
would think it was particularly advanced, it's just two cubics
after all).

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

#54965

Richard Heathfield <invalid@see.sig.invalid> writes:

> Tim Rentsch wrote:
>
>> Richard Heathfield <invalid@see.sig.invalid> writes:
>> 
>>> JohnF wrote:
>>>
>>>> Tim Rentsch <txr@alumni.caltech.edu> wrote:
>>>>> [... nice recursive algorithms for some things ... ]
>>>
>>> Some fractals, I'd agree with.  Bezier curves, though?  It never
>>> even occurred to me to draw these recursively, and I didn't have
>>> any particular difficulty with the iterative method.  Am I doing
>>> something wrong?
>> 
>> There is a well-known technique (which I've forgotten) for taking
>> a set of four Bezier control points, and dividing it into two
>> sets of control points for the two "halves" of the Bezier curve.
>> Recurse until the control points are suitably co-linear (or close
>> together) that the "curve" can be drawn as a straight line.  A
>> simple definition, and one that automatically adapts as needed to
>> draw only those lines needed to represent the curve accurately.
>
> Thank you.  I wasn't aware of that.  My Bezier-drawing function
> uses only two control points

Terminology confusion - the code you posted is for what I would
call a Bezier curve with four control points (and that might or
might not match some sort of "official" terminology).  So the
two cases we dealing with are in fact the same case.

> (I /was/ aware that you can use more,
> but two seemed to me to be a sufficiency for the time being), so
> that might explain why I hadn't looked any further than:
>
>   for(v = 0.0; v <= 1.0; v += inc)
>   {
>     neg = 1.0 - v;
>
>     xv = 1 * 1         * neg * neg * neg * x0 +
>          3 * v         * neg * neg       * cpax +
>          3 * v * v     * neg             * cpbx +
>          1 * v * v * v * 1               * x1;
>     yv = 1 * 1         * neg * neg * neg * y0 +
>          3 * v         * neg * neg       * cpay +
>          3 * v * v     * neg             * cpby +
>          1 * v * v * v * 1               * y1;
>     xi = xv;
>     yi = yv;
>     if(xi >= 0 && xi < fb->width &&
>        yi >= 0 && yi < fb->height)
>     {
>       set_pixel(fb, xi, yi, colour);
>     }
>   }
>
> The control points are (cpax, cpay) and (cpbx, cpby), in case it
> wasn't obvious.

I was going to respond with essentially the same function
definition that Ben Bacarisse posted, but he was quicker
on the draw so I'll just reference that one.

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

#54894

Richard Heathfield <invalid@see.sig.invalid> writes:

> JohnF wrote:
>
>> Tim Rentsch <txr@alumni.caltech.edu> wrote:
>>> <<snip>>
>>> As for recursive implementations in C having no practical utility,
>>> that may be true for factorial, but it certainly is not true for
>>> other uses.  In particular, for Fibonacci numbers, the fastest
>>> implementation in C I have seen used a recursive definition (ie,
>>> the C code was itself recursive). <<snip>>
>> 
>> Various algorithms, like generating bezier curves and some fractals,
>> are naturally recursive -- pretty easy to express and code recursively,
>> and will pretty much drive you crazy if you try to think it through
>> and code it iteratively, regardless of language.
>
> Some fractals, I'd agree with. Bezier curves, though? It never even occurred 
> to me to draw these recursively, and I didn't have any particular difficulty 
> with the iterative method. Am I doing something wrong?

I am sure you are not doing anything wrong, but there are other ways.

The usual recursive solution comes in two flavours both, based on what's
called De Casteljau's algorithm.  In one flavour you use this
numerically, but the prettiest version is a direct geometric realisation
of it.  To

  draw_curve(p1, c1, c2, p2);

(that's the curve from p1 to p2 using c1 and c2 as control points) you
calculate 6 mid-points and draw two smaller curves:

  p1c1 = mid(p1, c1);
  c1c2 = mid(c1, c2);
  c2p2 = mid(c2, p2);
  p1c1c1c2 = mid(p1c1, c1c2);
  c1c2c2p2 = mid(c1c2, c2p2);
  m = mid(p1c1c1c2, c1c2c2p2);

  draw_curve(p1, p1c1, p1c1c1c2, m);
  draw_curve(m, c1c2c2p2, c2p2, p2);

To see what's happening, draw the lines p1-c1, c1-c2 and c2-p2.  Now
draw lines between the mid-points of each consecutive pair of these
lines.  Then do the same between the mid-points of every consecutive
pair you now have... and so on.  (If you are like me, you need to draw
it to see what's happening but it's just the high-tech version of the
art with string and nails that I remember doing at school.)

The recursion stops (and you draw a line) when some metric becomes small
enough.  You can use a recursion count, some measure of the distance
between the end points, or some measure of the "bend" in the curve (or
some combination of these, of course).

-- 
Ben.

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

#54900

On 17/12/2014 23:23, Ben Bacarisse wrote:
> Richard Heathfield <invalid@see.sig.invalid> writes:

>> Some fractals, I'd agree with. Bezier curves, though? It never even occurred
>> to me to draw these recursively, and I didn't have any particular difficulty
>> with the iterative method. Am I doing something wrong?

> The usual recursive solution comes in two flavours both, based on what's
> called De Casteljau's algorithm.  In one flavour you use this
> numerically, but the prettiest version is a direct geometric realisation
> of it.  To
>
>    draw_curve(p1, c1, c2, p2);
>
> (that's the curve from p1 to p2 using c1 and c2 as control points) you
> calculate 6 mid-points and draw two smaller curves:
>
>    p1c1 = mid(p1, c1);
>    c1c2 = mid(c1, c2);
>    c2p2 = mid(c2, p2);
>    p1c1c1c2 = mid(p1c1, c1c2);
>    c1c2c2p2 = mid(c1c2, c2p2);
>    m = mid(p1c1c1c2, c1c2c2p2);
>
>    draw_curve(p1, p1c1, p1c1c1c2, m);
>    draw_curve(m, c1c2c2p2, c2p2, p2);


I've tried this, and it worked first time!

(Here: http://pastebin.com/iNwREWpW

Code not in C obviously; this little language belongs to an old CAD 
application. When I used the same points to create an actual Bezier 
curve, the two paths were pretty much the same.

It uses 'procedural' programming too...)

-- 
Bartc

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

#54903

Ben Bacarisse wrote:

<snip>
 
> The recursion stops (and you draw a line) when some metric becomes small
> enough.  You can use a recursion count, some measure of the distance
> between the end points, or some measure of the "bend" in the curve (or
> some combination of these, of course).

Thanks, Ben - that article is a keeper. Duly saved for later study.
 
-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

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

#54963

Richard Heathfield <invalid@see.sig.invalid> writes:

> Ben Bacarisse wrote:
>
> <snip>
>  
>> The recursion stops (and you draw a line) when some metric becomes small
>> enough.  You can use a recursion count, some measure of the distance
>> between the end points, or some measure of the "bend" in the curve (or
>> some combination of these, of course).
>
> Thanks, Ben - that article is a keeper. Duly saved for later study.

I'm glad, but I notice my informal description is wrong.  The "join the
midpoints of every consecutive pair of lines form the previous step"
method is what you do with a quadratic spline (and one control point).
For the cubic case, it is the double "join the mid-points and then the
mid-points of those" action that is repeated.  (The pseudo code is fine,
it's just the description that went off the rails.)

I note you might be doing pixel drawing.  You can easily make this
method adaptive so as to avoid the need to draw lines, but I don't know
if this method is suitable for that use.

-- 
Ben.

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

#54978

Ben Bacarisse wrote:

> Richard Heathfield <invalid@see.sig.invalid> writes:
> 
>> Ben Bacarisse wrote:
>>
>> <snip>
>>  
>>> The recursion stops (and you draw a line) when some metric becomes small
>>> enough.  You can use a recursion count, some measure of the distance
>>> between the end points, or some measure of the "bend" in the curve (or
>>> some combination of these, of course).
>>
>> Thanks, Ben - that article is a keeper. Duly saved for later study.
> 
> I'm glad, but I notice my informal description is wrong.  The "join the
> midpoints of every consecutive pair of lines form the previous step"
> method is what you do with a quadratic spline (and one control point).
> For the cubic case, it is the double "join the mid-points and then the
> mid-points of those" action that is repeated.  (The pseudo code is fine,
> it's just the description that went off the rails.)

Thanks for the heads-up. I'd better save that paragraph too. :-)

> 
> I note you might be doing pixel drawing.  You can easily make this
> method adaptive so as to avoid the need to draw lines, but I don't know
> if this method is suitable for that use.

That's all right - I have a line-drawing routine as well (although of course 
it ends up drawing pixels eventually). Brasenham, if I have remembered the 
name correctly.
 
-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

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

#55031

Richard Heathfield <invalid@see.sig.invalid> writes:
<snip>
> That's all right - I have a line-drawing routine as well (although of course 
> it ends up drawing pixels eventually). Brasenham, if I have remembered the 
> name correctly.

Bresenham.

-- 
Ben.

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

#55039

Ben Bacarisse wrote:

> Richard Heathfield <invalid@see.sig.invalid> writes:
> <snip>
>> That's all right - I have a line-drawing routine as well (although of
>> course it ends up drawing pixels eventually). Brasenham, if I have
>> remembered the name correctly.
> 
> Bresenham.

Mr Bresenham, I apologise most sincerely. Ben, thank you for the correction.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

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

#54866

JohnF <john@please.see.sig.for.email.com> writes:

> Tim Rentsch <txr@alumni.caltech.edu> wrote:
>> <<snip>>
>> As for recursive implementations in C having no practical
>> utility, that may be true for factorial, but it certainly is not
>> true for other uses.  In particular, for Fibonacci numbers, the
>> fastest implementation in C I have seen used a recursive
>> definition (ie, the C code was itself recursive). <<snip>>
>
> Various algorithms, like generating bezier curves and some
> fractals, are naturally recursive -- pretty easy to express and
> code recursively, and will pretty much drive you crazy if you try
> to think it through and code it iteratively, regardless of
> language.

Usually I am wary when someone says some approach is "naturally"
one thing or another.  Often something seems natural only because
it's how it was first learned or what someone is used to.  One of
the greatest scientists of the 20th century, Richard Feynman,
thought there is value in being familiar with different ways of
looking at the same picture (or theory, or problem, whatever),
and to some degree as many different ways as you can.  I am
inclined to side with this viewpoint.

That said, certain problems do have a very pretty solution when
seen from a certain perspective (such as a recursive one), and it
would be rather foolish to imagine the prettiness has no value.

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

#55033

Tim Rentsch <txr@alumni.caltech.edu> wrote:
> JohnF <john@please.see.sig.for.email.com> writes:
>> Tim Rentsch <txr@alumni.caltech.edu> wrote:
>>> <<snip>>
>>> As for recursive implementations in C having no practical
>>> utility, that may be true for factorial, but it certainly is not
>>> true for other uses.  In particular, for Fibonacci numbers, the
>>> fastest implementation in C I have seen used a recursive
>>> definition (ie, the C code was itself recursive). <<snip>>
>>
>> Various algorithms, like generating bezier curves and some
>> fractals, are naturally recursive -- pretty easy to express and
>> code recursively, and will pretty much drive you crazy if you try
>> to think it through and code it iteratively, regardless of
>> language.
> 
> Usually I am wary when someone says some approach is "naturally"
> one thing or another.  Often something seems natural only because
> it's how it was first learned or what someone is used to.  One of
> the greatest scientists of the 20th century, Richard Feynman,
> thought there is value in being familiar with different ways of
> looking at the same picture (or theory, or problem, whatever),
> and to some degree as many different ways as you can.  I am
> inclined to side with this viewpoint.

Sure, beauty/elegance/etc is in the eye/mind of the beholder.
   Physics looks at this kind of thing from a slightly different
perspective (I note you're from cal tech, and so would naturally
cite Feynman; and my ms is in physics, so you know I'm not going
to pass up an opportunity to comment:).
   When programming, you typically have a well-defined objective
you're trying to achieve, so the basic question is the shortest/best
path to it (though "best" can be ill-defined). With physics,
the end-game, so to speak, is itself quite murky (answers just
lead to more questions, etc, and I think most physicists would
cast a somewhat jaundiced eye at the likelihood for any "theory of
everything"), so it can be crucial to consider all possible different
approaches to the same regime of phenomena.
   Physicists can also look at different approaches when trying
to come up with efficient numerical solutions (simulated annealing
pops to mind, for no particular reason, as an elegant approach to
that class of problems), and those cases are pretty much identical
to the point of view of programming cases. But I'd guess the "value"
(your word above) Feynman was referring to arose from an entirely
different perspective.

> That said, certain problems do have a very pretty solution when
> seen from a certain perspective (such as a recursive one), and it
> would be rather foolish to imagine the prettiness has no value.

That's kind of what I meant. If you google these things, the
majority of discussions will cite recursive algorithms as
the more natural/elegant/etc. And I'd bet a survey of programmers
would conclude the same. Most "beholders" of this kind of stuff
are looking at it with similarly-trained "eyes".
-- 
John Forkosh  ( mailto:  j@f.com  where j=john and f=forkosh )

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

#55090

JohnF <john@please.see.sig.for.email.com> writes:

> Tim Rentsch <txr@alumni.caltech.edu> wrote:
>> JohnF <john@please.see.sig.for.email.com> writes:
>>> Tim Rentsch <txr@alumni.caltech.edu> wrote:
>>>> <<snip>>

>> Usually I am wary when someone says some approach is "naturally"
>> one thing or another.  Often something seems natural only because
>> it's how it was first learned or what someone is used to.  One of
>> the greatest scientists of the 20th century, Richard Feynman,
>> thought there is value in being familiar with different ways of
>> looking at the same picture (or theory, or problem, whatever),
>> and to some degree as many different ways as you can.  I am
>> inclined to side with this viewpoint.
>
> Sure, beauty/elegance/etc is in the eye/mind of the beholder.
>    Physics looks at this kind of thing from a slightly different
> perspective (I note you're from cal tech, and so would naturally
> cite Feynman; [snip]

My comment about Feynman is prompted by later reading of the
Feynman biography written by James Gleick;  I didn't have much to
do with Feynman (or physics really, beyond the two years of
required physics classes) while I was a student.  If you haven't
read Gleick's book, I thoroughly recommend it.

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

#55112

On 2014-12-19, Tim Rentsch <txr@alumni.caltech.edu> wrote:
> JohnF <john@please.see.sig.for.email.com> writes:
>
>> Tim Rentsch <txr@alumni.caltech.edu> wrote:
>>> JohnF <john@please.see.sig.for.email.com> writes:
>>>> Tim Rentsch <txr@alumni.caltech.edu> wrote:
>>>>> <<snip>>
>
>>> Usually I am wary when someone says some approach is "naturally"
>>> one thing or another.  Often something seems natural only because
>>> it's how it was first learned or what someone is used to.  One of
>>> the greatest scientists of the 20th century, Richard Feynman,
>>> thought there is value in being familiar with different ways of
>>> looking at the same picture (or theory, or problem, whatever),
>>> and to some degree as many different ways as you can.  I am
>>> inclined to side with this viewpoint.
>>
>> Sure, beauty/elegance/etc is in the eye/mind of the beholder.
>>    Physics looks at this kind of thing from a slightly different
>> perspective (I note you're from cal tech, and so would naturally
>> cite Feynman; [snip]
>
> My comment about Feynman is prompted by later reading of the
> Feynman biography written by James Gleick;  I didn't have much to
> do with Feynman (or physics really, beyond the two years of
> required physics classes) while I was a student.  If you haven't
> read Gleick's book, I thoroughly recommend it.

The quality of any discussion will be improved by a citation of one of
the greatest minds ever. His own books are well worth reading, even
if comprehension can be a challenge. I am neither mathematician or
pysicist but considermy life greatly improved by the works of Feynman.


-- 
http://www.softsprocket.com

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

#55118

Greg Martin <greg.at.softsprocket@dot.com> wrote:
> On 2014-12-19, Tim Rentsch <txr@alumni.caltech.edu> wrote:
>> JohnF <john@please.see.sig.for.email.com> writes:
>>> Tim Rentsch <txr@alumni.caltech.edu> wrote:
>>>> JohnF <john@please.see.sig.for.email.com> writes:
>>>>> Tim Rentsch <txr@alumni.caltech.edu> wrote:
>>>>>> <<snip>>
>>
>>>> Usually I am wary when someone says some approach is "naturally"
>>>> one thing or another.  Often something seems natural only because
>>>> it's how it was first learned or what someone is used to.  One of
>>>> the greatest scientists of the 20th century, Richard Feynman,
>>>> thought there is value in being familiar with different ways of
>>>> looking at the same picture (or theory, or problem, whatever),
>>>> and to some degree as many different ways as you can.  I am
>>>> inclined to side with this viewpoint.
>>>
>>> Sure, beauty/elegance/etc is in the eye/mind of the beholder.
>>>    Physics looks at this kind of thing from a slightly different
>>> perspective (I note you're from cal tech, and so would naturally
>>> cite Feynman; [snip]
>>
>> My comment about Feynman is prompted by later reading of the
>> Feynman biography written by James Gleick;  I didn't have much to
>> do with Feynman (or physics really, beyond the two years of
>> required physics classes) while I was a student.  If you haven't
>> read Gleick's book, I thoroughly recommend it.
> 
> The quality of any discussion will be improved by a citation of one of
> the greatest minds ever. His own books are well worth reading, even
> if comprehension can be a challenge. I am neither mathematician or
> pysicist but consider my life greatly improved by the works of Feynman.

For people interested in this kind of stuff, but without the
prerequisites for rigorous discussion, I always (absolutely
and invariably always) recommend Feynman's
 http://www.amazon.com/The-Character-Physical-Modern-Library/dp/0679601279
And I'm seeing from google that there's apparently a youtube video
 https://www.youtube.com/watch?v=j3mhkYbznBk
of his public lectures on which the book is based (I hadn't been
aware of that before).
-- 
John Forkosh  ( mailto:  j@f.com  where j=john and f=forkosh )

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

#54640

arvindgupta01031988@gmail.com writes:

> How to use a recursive function in C ?

I presume your question is how to use recursion in C.  Here
are two small examples.  First, compare strings of unsigned
char's.  This function works like strcmp() but with unsigned
char rather than char:

    int
    compare( unsigned char *a, unsigned char *b ){
        if(  *a == 0  ||  *a != *b  )  return  *a - *b;
        return  compare( a+1, b+1 );
    }

If we have reached the end of string 'a', or if the first
element of 'a' is different than the first element of 'b'
(which may be zero), then we know the answer (how the answer
is calculated may look a bit funny, but it works as long as
a regular int is wider than unsigned char).  If that does
not hold, that is, if we have not reached the end of 'a',
and the first element of 'a' and 'b' are the same (which
implies we have not reached the end of 'b' either), then
the result is just that of using the compare() function
on the rest of the two strings - 'compare( a+1, b+1 )'.

Second example - count the number of "words" in a string.
A "word" is a consecutive sequence of non-blank characters,
with at least one blank between words (but perhaps not
before the first word or after the last).  For this problem
we have two mutually recursive functions, plus one to start
things off:

    static int skip( char *, int );
    static int scan( char *, int );

    static int
    words_in( char *s ){
        return  skip( s, 0 );
    }

    int
    skip( char *s, int n ){
        if(  *s == 0    )  return  n;
        if(  *s != ' '  )  return  scan( s, n+1 );
        return  skip( s+1, n );
    }

    int
    scan( char *s, int n ){
        if(  *s == 0    )  return  n;
        if(  *s == ' '  )  return  skip( s, n );
        return  scan( s+1, n );
    }

The entry routine words_in() just calls skip() with the start
of the string and an initial count of zero.

The routines skip() and scan() are for skipping blanks and
scanning over characters in a work, respectively.  In either
case, if the element encountered is zero, we have reached
the end of the string, so we just return the paramenter used
to count up the result.  Otherwise, if we are skip()'ing,
and we see a non-blank character, then we need to scan(),
with a one-higher value of 'n' because a new word just
started;  and conversely, if we are scan()'ing and see a
blank character, then we need to skip() to get to the start
of the next word (if any).  And kind of obviously, if we
are skip()'ing and we see a blank, or scan()'ing and see
a non-blank (and also non-zero), then we continue by calling
skip() or scan() respectively with the same value of 'n' but
one element further on in the string.

The skip() and scan() functions can be written in various
different ways, including a performance improvement that
avoids retesting some characters.  The important thing
though is to see how the recursion works its way through the
string without ever needing to "back up".  At any point in
the recursion, the final answer is purely a function of the
parameters and whether we are in skip() or scan().  That
"no backing up" property also holds for compare(), only a
little more easily in that case because the characters
passed over don't affect the final result and here they do;
that's why we need the extra parameter 'n' in this case.
But there is a nice payoff for recursing in this way:  in
many cases compilers will optimize the function calls into
unconditional branches rather than call instructions.  That
is in fact the case with these examples when using gcc -O2
or higher.

There are other cases where recursion is not of this type
but more needs to be done after a call that is recursive.
In such cases normally a fair amount of care is taken to
protect against recursion depth getting too large, which is
likely to run into stack size limits.  By comparison,
functions of the "no backing up" variety (and which are
recognized and optimized as such by the compiler, which is
basically what is meant here) can easily process millions or
billions of elements with only a tiny (and constant) amount
of stack space.

[toc] | [prev] | [standalone]

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

Back to top | Article view | comp.lang.c

csiph-web