"Thorsten Froehlich" <tho### [at] trfde> wrote in message
news:3cda9ef6@news.povray.org...
> In article <3cda78bf$1@news.povray.org> , "Gleb" <gk1### [at] sotonacuk> wrote:
>
> A Catmull-Rom spline can extend "beyond" its control points.  It is not a
> matter of converting to some other spline type.  The problem is to
determine
> the bounds of a Catmull-Rom spline segment by just looking at the control
> points, which is simply not possible due to the nature of this spline
type.
>
> To clarify my original point:
>
> This is not going to be fixed because nobody in the team has the time to
look
> into this mess.  Making wild suggestions won't help ;-)
>
> Only plain and simple source code, based on the available sphere_sweep
code
> that can be found in MegaPOV, if contributed by someone _soon_, will fix
the
> problem in the initial 3.5 release.  The code was already been broken in
the
> original patch :-(  Its author apparently did not know a good way how to
fix
> it either, so don't expect magic from us!

Why not ;)


Thank you for pointing the source,
it would be easier to explain what I mean.

In the source mentioned every spline segment
of this scaring Catmull-Rom spline
is internally represented as four polynomial coefficients, say
a3, a2, a1 and a0. Actual curve segment is calculated
as a3*t^3+a2*t^2+a1*t+a0. And every such a segment has two
control points at its ends from original definition.
And of course, the curve can escape the set of original control points.
What I'm talking about is that there are two "additional control points"
hidden inside this polynomial, because the same beast can also be
represented as
a3*t^3+a2*t^2+a1*t+a0 = A*(1-t)^3+3*B*t*(1-t)^2+3*C*t^2*(1-t)+D*t^3
which is the other scaring thing, Bezier spline segment.
In this form(for exactly the same curve) we have four control points,
A, B, C, D, where A and D are the same as the original Catmull-Rom spline
segment control points, but we also have two additional control points,
B and C. And our segment now can't escape the convex hull
of that set of the four control points.
And if there is already working code for calculating the bounding box
for Bezier spline segments, we can feed it with these four control
points - that's all.

On the other hand the method suggested by Tor Olav may be even better
(more precise).


Regards,

Gleb

Post a reply to this message

On Thu, 09 May 2002 18:08:14 +0200, "Thorsten Froehlich" <tho### [at] trfde>
wrote:
> Only plain and simple source code, based on the available sphere_sweep code
> that can be found in MegaPOV, if contributed by someone _soon_, will fix the
> problem in the initial 3.5 release.  The code was already been broken in the
> original patch :-(  Its author apparently did not know a good way how to fix
> it either, so don't expect magic from us!

I have not noticed any announcement that somebody started to code this so I
used some part of my night to prepare code. Some notes:
- I did it completly without parser/compiler so it is not verified for syntax
  (in particular I wrote something in C long time ago and I don't remeber
  referencing rules)
- I was tired (but enthusiastic about it)
- I hope it isn't too late and used spline equations are correct
- I added some helper functions and made note how it could be improved by
  adding Bound union of boxes to additionaly optimize intersection test
- I used MEGAPOV 0.6a source

// *******************************************************************

DBL Compute_B_Spline_Value(DBL t)
{
  // should be best to code this using already defined B_Matrix
  return 1/6*(-p0+3*p1-3*p2+p3)*t^3
        +1/2*(p0-2*p1+p2)*t^2
        +1/2*(-p0+p2)*t
        +1/6*(p0+4*p1+p2);
}

void Compute_Min_Max_B_Spline(DBL p0,p1,p2,p3,*minp,*maxp)
{
  DBL a,b,c,delta;

  // first derivative of spline equation is
  // 1/2*(-p0+3*p1-3*p2+p3)*t^2+(p0-2*p1+p2)*t-1/2*p0+1/2*p2

  a=1/2*(-p0+3*p1-3*p2+p3);
  b=p0-2*p1+p2;
  c=(-p0+p2)/2;
  d=b*b-4*a*c;
  if ((d<0)||(a==0)) // for unexpected errors return the biggest bbox
    {
      t1=0;
      t2=1;
    }
  else
    {
      // parameter for extremas
      t1=(-b-sqrt(d))/(2*a);
      t2=(-b+sqrt(d))/(2*a);
      // parameter should be clipped to visible part of segment
      t1=min(max(t1,0),1);
      t2=min(max(t2,0),1);
    }
  t1 = Compute_B_Spline_Value(t1);
  t2 = Compute_B_Spline_Value(t2);
  minp = min( t1, t2 );
  maxp = max( t1, t2 );
}

DBL Compute_Catmull_Rom_Spline_Value(DBL t)
{
  // should be best to code this using already defined Catmull_Rom_Matrix
  return ((2*p1)+(-p0+p2)*t+(2*p0-5*p1+4*p2-p3)*t^2+(-p0+3*p1-3*p2+p3)*t^3)/2;
}

void Compute_Min_Max_Catmull_Rom_Spline(DBL p0,p1,p2,p3,*minp,*maxp)
{
  DBL a,b,c,delta;

  // first derivative of spline equation is
  // -1/2*p0+1/2*p2+(2*p0-5*p1+4*p2-p3)*t+3/2*(-p0+3*p1-3*p2+p3)*t^2

  a=3*(-p0+3*p1-3*p2+p3)/2;
  b=2*p0-5*p1+4*p2-p3;
  c=(-p0+p2)/2;
  d=b*b-4*a*c;
  if ((d<0)||(a==0)) // for unexpected errors return the biggest bbox
    {
      t1=0;
      t2=1;
    }
  else
    {
      // parameter for extremas
      t1=(-b-sqrt(d))/(2*a);
      t2=(-b+sqrt(d))/(2*a);
      // parameter should be clipped to visible part of segment
      t1=min(max(t1,0),1);
      t2=min(max(t2,0),1);
    }
  t1 = Compute_Catmull_Rom_Spline_Value(t1);
  t2 = Compute_Catmull_Rom_Spline_Value(t2);
  minp = min( t1, t2 );
  maxp = max( t1, t2 );
}

void Compute_Sphere_Sweep_BBox(Sphere_Sweep)
SPHERE_SWEEP *Sphere_Sweep;
{
  VECTOR mins,maxs,segmins,segmaxs;
  int i,number_of_segments;
  DBL min_radius,max_radius;

  if( Sphere_Sweep->Interpolation == LINEAR_SPLINE)
    number_of_segments=Sphere_Sweep->Num_Modeling_Spheres-1;
  else
    number_of_segments=Sphere_Sweep->Num_Modeling_Spheres-3;

  // set initial value for general bbox extents
  // to one of "visible" control points of object
  Assign_Vector( mins , Sphere_Sweep->Modeling_Sphere[1].Center );
  Assign_Vector( maxs , Sphere_Sweep->Modeling_Sphere[1].Center );

  for (i = 0; i < number_of_segments; i++)
    {
      // set initial value for local bbox extents
      // to one of "visible" control points of segment
      Assign_Vector( segmins , Sphere_Sweep->Modeling_Sphere[i+1].Center );
      Assign_Vector( segmaxs , Sphere_Sweep->Modeling_Sphere[i+1].Center );

      switch (Sphere_Sweep->Interpolation)
      {
         case B_SPLINE:
           Compute_Min_Max_B_Spline(
             Sphere_Sweep->Modeling_Sphere[I  ].Center[X],
             Sphere_Sweep->Modeling_Sphere[i+1].Center[X],
             Sphere_Sweep->Modeling_Sphere[i+2].Center[X],
             Sphere_Sweep->Modeling_Sphere[i+3].Center[X],
             segmins[X],
             segmaxs[X]
           )
           Compute_Min_Max_B_Spline(
             Sphere_Sweep->Modeling_Sphere[I  ].Center[Y],
             Sphere_Sweep->Modeling_Sphere[i+1].Center[Y],
             Sphere_Sweep->Modeling_Sphere[i+2].Center[Y],
             Sphere_Sweep->Modeling_Sphere[i+3].Center[Y],
             segmins[Y],
             segmaxs[Y]
           )
           Compute_Min_Max_B_Spline(
             Sphere_Sweep->Modeling_Sphere[I  ].Center[Z],
             Sphere_Sweep->Modeling_Sphere[i+1].Center[Z],
             Sphere_Sweep->Modeling_Sphere[i+2].Center[Z],
             Sphere_Sweep->Modeling_Sphere[i+3].Center[Z],
             segmins[Z],
             segmaxs[Z]
           )
           Compute_Min_Max_B_Spline(
             Sphere_Sweep->Modeling_Sphere[I  ].Radius,
             Sphere_Sweep->Modeling_Sphere[i+1].Radius,
             Sphere_Sweep->Modeling_Sphere[i+2].Radius,
             Sphere_Sweep->Modeling_Sphere[i+3].Radius,
             min_radius,
             max_radius
           )
         break;
         case CATMULL_ROM_SPLINE:
           Compute_Min_Max_Catmull_Rom_Spline(
             Sphere_Sweep->Modeling_Sphere[I  ].Center[X],
             Sphere_Sweep->Modeling_Sphere[i+1].Center[X],
             Sphere_Sweep->Modeling_Sphere[i+2].Center[X],
             Sphere_Sweep->Modeling_Sphere[i+3].Center[X],
             segmins[X],
             segmaxs[X]
           )
           Compute_Min_Max_Catmull_Rom_Spline(
             Sphere_Sweep->Modeling_Sphere[I  ].Center[Y],
             Sphere_Sweep->Modeling_Sphere[i+1].Center[Y],
             Sphere_Sweep->Modeling_Sphere[i+2].Center[Y],
             Sphere_Sweep->Modeling_Sphere[i+3].Center[Y],
             segmins[Y],
             segmaxs[Y]
           )
           Compute_Min_Max_Catmull_Rom_Spline(
             Sphere_Sweep->Modeling_Sphere[I  ].Center[Z],
             Sphere_Sweep->Modeling_Sphere[i+1].Center[Z],
             Sphere_Sweep->Modeling_Sphere[i+2].Center[Z],
             Sphere_Sweep->Modeling_Sphere[i+3].Center[Z],
             segmins[Z],
             segmaxs[Z]
           )
           Compute_Min_Max_Catmull_Rom_Spline(
             Sphere_Sweep->Modeling_Sphere[I  ].Radius,
             Sphere_Sweep->Modeling_Sphere[i+1].Radius,
             Sphere_Sweep->Modeling_Sphere[i+2].Radius,
             Sphere_Sweep->Modeling_Sphere[i+3].Radius,
             min_radius,
             max_radius
           )
         break;
         case LINEAR_SPLINE:
           segmins[X] = min( segmins[X],
                        Sphere_Sweep->Modeling_Sphere[i].Center[X] );
           segmins[Y] = min( segmins[Y], 
                        Sphere_Sweep->Modeling_Sphere[i].Center[Y] );
           segmins[Z] = min( segmins[Z], 
                        Sphere_Sweep->Modeling_Sphere[i].Center[Z] );
           segmaxs[X] = max( segmins[X], 
                        Sphere_Sweep->Modeling_Sphere[i].Center[X] );
           segmaxs[Y] = max( segmins[Y], 
                        Sphere_Sweep->Modeling_Sphere[i].Center[Y] );
           segmaxs[Z] = max( segmins[Z], 
                        Sphere_Sweep->Modeling_Sphere[i].Center[Z] );
           max_radius = max( Sphere_Sweep->Modeling_Sphere[i].Radius , 
                        Sphere_Sweep->Modeling_Sphere[i+1].Radius );
         break;
      }

      // consider maximal value of radius
      mins[X] = mins[X]-max_radius;
      mins[Y] = mins[Y]-max_radius;
      mins[Z] = mins[Z]-max_radius;
      maxs[X] = maxs[X]+max_radius;
      maxs[Y] = maxs[Y]+max_radius;
      maxs[Z] = maxs[Z]+max_radius;

      // here you can create box{mins maxs} object as bounding object
      // of current segment - for further optimization union of bounding
      // objects can be used as Bound field of current sphere_sweep

      // compare segment extents with object extents
      mins[X] = min( segmins[X], mins[X] );
      mins[Y] = min( segmins[Y], mins[Y] );
      mins[Z] = min( segmins[Z], mins[Z] );
      maxs[X] = max( segmins[X], maxs[X] );
      maxs[Y] = max( segmins[Y], maxs[Y] );
      maxs[Z] = max( segmins[Z], maxs[Z] );
    }

  Make_BBox_from_min_max(Sphere_Sweep->BBox, mins, maxs);

  if (Sphere_Sweep->Trans != NULL)
    {
      Recompute_BBox(&Sphere_Sweep->BBox, Sphere_Sweep->Trans);
    }
}

// *******************************************************************

ABX

Post a reply to this message

wrote:

> - I was tired (but enthusiastic about it)

yes, I was tired, I found mistake:

>      // consider maximal value of radius
>      mins[X] = mins[X]-max_radius;
>      mins[Y] = mins[Y]-max_radius;
>      mins[Z] = mins[Z]-max_radius;
>      maxs[X] = maxs[X]+max_radius;
>      maxs[Y] = maxs[Y]+max_radius;
>      maxs[Z] = maxs[Z]+max_radius;
>
>      // here you can create box{mins maxs} object as bounding object

should be:

      // consider maximal value of radius
      segmins[X] = segmins[X]-max_radius;
      segmins[Y] = segmins[Y]-max_radius;
      segmins[Z] = segmins[Z]-max_radius;
      segmaxs[X] = segmaxs[X]+max_radius;
      segmaxs[Y] = segmaxs[Y]+max_radius;
      segmaxs[Z] = segmaxs[Z]+max_radius;

      // here you can create box{segmins segmaxs} object as bounding object

ABX

Post a reply to this message

"W?odzimierz ABX Skiba" <abx### [at] babilonorg> wrote in message
news:d091eu092vqvbnn84edd8h1hv63t6bd27h@4ax.com...

> void Compute_Min_Max_B_Spline(DBL p0,p1,p2,p3,*minp,*maxp)
> {
>   DBL a,b,c,delta;
>
>   // first derivative of spline equation is
>   // 1/2*(-p0+3*p1-3*p2+p3)*t^2+(p0-2*p1+p2)*t-1/2*p0+1/2*p2
>
>   a=1/2*(-p0+3*p1-3*p2+p3);
>   b=p0-2*p1+p2;
>   c=(-p0+p2)/2;
>   d=b*b-4*a*c;
>   if ((d<0)||(a==0)) // for unexpected errors return the biggest bbox
>     {
>       t1=0;
>       t2=1;
>     }
>   else
>     {
>       // parameter for extremas
>       t1=(-b-sqrt(d))/(2*a);
>       t2=(-b+sqrt(d))/(2*a);
>       // parameter should be clipped to visible part of segment
>       t1=min(max(t1,0),1);
>       t2=min(max(t2,0),1);
>     }
>   t1 = Compute_B_Spline_Value(t1);
>   t2 = Compute_B_Spline_Value(t2);
>   minp = min( t1, t2 );
>   maxp = max( t1, t2 );
> }
>
> DBL Compute_Catmull_Rom_Spline_Value(DBL t)
> {
>   // should be best to code this using already defined Catmull_Rom_Matrix
>   return
((2*p1)+(-p0+p2)*t+(2*p0-5*p1+4*p2-p3)*t^2+(-p0+3*p1-3*p2+p3)*t^3)/2;
> }
>
> void Compute_Min_Max_Catmull_Rom_Spline(DBL p0,p1,p2,p3,*minp,*maxp)
> {
>   DBL a,b,c,delta;
>
>   // first derivative of spline equation is
>   // -1/2*p0+1/2*p2+(2*p0-5*p1+4*p2-p3)*t+3/2*(-p0+3*p1-3*p2+p3)*t^2
>
>   a=3*(-p0+3*p1-3*p2+p3)/2;
>   b=2*p0-5*p1+4*p2-p3;
>   c=(-p0+p2)/2;
>   d=b*b-4*a*c;
>   if ((d<0)||(a==0)) // for unexpected errors return the biggest bbox
>     {
>       t1=0;
>       t2=1;
>     }
>   else
>     {
>       // parameter for extremas
>       t1=(-b-sqrt(d))/(2*a);
>       t2=(-b+sqrt(d))/(2*a);
>       // parameter should be clipped to visible part of segment
>       t1=min(max(t1,0),1);
>       t2=min(max(t2,0),1);
>     }
>   t1 = Compute_Catmull_Rom_Spline_Value(t1);
>   t2 = Compute_Catmull_Rom_Spline_Value(t2);
>   minp = min( t1, t2 );
>   maxp = max( t1, t2 );
> }


Two remarks:
1) the only difference between procedures Compute_Min_Max_B_Spline and
Compute_Min_Max_Catmull_Rom_Spline is their polynomial coefficients a,b,c,d,
maybe it's better to put this common part in a separate procedure;

2) the curve can possibly reach its min/max at its ends, when t=0 and t=1.

Regards,

Gleb

Post a reply to this message

On Tue, 14 May 2002 19:15:10 +0100, "Gleb" <gk1### [at] sotonacuk> wrote:
> Two remarks:
> 1) the only difference between procedures Compute_Min_Max_B_Spline and
> Compute_Min_Max_Catmull_Rom_Spline is their polynomial coefficients a,b,c,d,
> maybe it's better to put this common part in a separate procedure;

That was obvious conclusion when I wrote this stuff, moreover it could be
probably written in general form with one matrix as parameter (valid also
for linear spline) but I had no access to compiler and net to make it so I
wrote simplest form I could at that moment.

> 2) the curve can possibly reach its min/max at its ends, when t=0 and t=1.

so whole discussion has no sense ? :-)

ABX

Post a reply to this message

"W?odzimierz ABX Skiba" <abx### [at] babilonorg> wrote in message
news:e6u3eu0h9scfphre7glpfvadu0bbsvbikt@4ax.com...
> > 2) the curve can possibly reach its min/max at its ends, when t=0 and
t=1.
>
> so whole discussion has no sense ? :-)

Of course it has :)
The only thing to fix this is to check that after calculating the local
min/max values for x,y,z.

Post a reply to this message

wrote:
>  return local: news.povray.org/e3piut8anmf4cli4pnfmstadgc3nleqvb2@4ax.com

I can still cause crash with RC5. Just a few Render/Stop/Render/Stop cycles.

> not works as (I) expected
>  splines:      news.povray.org/m4f7cug9ch19jbve8m8prf4vl8ima0rsma@4ax.com
>  bounding:     news.povray.org/2g0dcu8kasg84pqde8hdq9d60nkoa1cvka@4ax.com
>  evaluate msg: news.povray.org/4nhfduk9gon9m76s6f6vu3k8gsjf7rrdjp@4ax.com

Any chance to see 'Known bugs' list. None of listed is fixed but I don't want
bother too much - I just don't know what is current status of those reports.

ABX

Post a reply to this message

<abx### [at] babilonorg> wrote:

>>  return local: news.povray.org/e3piut8anmf4cli4pnfmstadgc3nleqvb2@4ax.com
>
> I can still cause crash with RC5. Just a few Render/Stop/Render/Stop cycles.

Works fine here.

>> not works as (I) expected
>>  splines:      news.povray.org/m4f7cug9ch19jbve8m8prf4vl8ima0rsma@4ax.com

The report is incomplete.  The behavior you reported that could be reproduced
without a scene has been fixed and for the rest an example is needed.

>>  bounding:     news.povray.org/2g0dcu8kasg84pqde8hdq9d60nkoa1cvka@4ax.com

Won't be fixed in 3.5 as previously explained.

>>  evaluate msg: news.povray.org/4nhfduk9gon9m76s6f6vu3k8gsjf7rrdjp@4ax.com

Not a bug.

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

On Mon, 20 May 2002 15:21:58 +0200, "Thorsten Froehlich" <tho### [at] trfde>
wrote:
> > >  return local: news.povray.org/e3piut8anmf4cli4pnfmstadgc3nleqvb2@4ax.com
> >
> > I can still cause crash with RC5. Just a few Render/Stop/Render/Stop cycles.
>
> Works fine here.

Works fine here for nearly every render. But crashes after a few cycles
Render/Stop/Render/.../Render/Stop without finishing rendering.

> > > not works as (I) expected
> > >  splines:      news.povray.org/m4f7cug9ch19jbve8m8prf4vl8ima0rsma@4ax.com
>
> The report is incomplete.  The behavior you reported that could be reproduced
> without a scene has been fixed and for the rest an example is needed.

What is wrong in example I posted in
pckkduod909g1736lrlm75pakanfm5rs3u@4ax.com ?


> > >  bounding:     news.povray.org/2g0dcu8kasg84pqde8hdq9d60nkoa1cvka@4ax.com
>
> Won't be fixed in 3.5 as previously explained.

Previously was explained it won't be fixed "unless someone comes up with code
to determine the bounding box of a Catmull-Rom spline segment". What is wrong
with code I posted in ftb1euon0h27vscfcjmfjd1cuqlbmvrluh@4ax.com ?

ABX

Post a reply to this message

Skiba <abx### [at] babilonorg>  wrote:

> Works fine here for nearly every render. But crashes after a few cycles
> Render/Stop/Render/.../Render/Stop without finishing rendering.

But then it can be a million things and doesn't even have to do anything with
macros.  If it can't be reproduced, I am afraid it won't get fixed ... of
course, what would really help is an always crashing example.

> What is wrong in example I posted in
> pckkduod909g1736lrlm75pakanfm5rs3u@4ax.com ?

Nothing except thata I didn't remember this particular example.  I think I
have found that problem now and assume it was the only one left from your list
of spline problems?

> Previously was explained it won't be fixed "unless someone comes up with code
> to determine the bounding box of a Catmull-Rom spline segment". What is wrong
> with code I posted in ftb1euon0h27vscfcjmfjd1cuqlbmvrluh@4ax.com ?

To quote you in that thread:
>- I did it completly without parser/compiler so it is not verified for syntax
>   (in particular I wrote something in C long time ago and I don't remeber
>   referencing rules)
> - I was tired (but enthusiastic about it)
> - I hope it isn't too late and used spline equations are correct
> - I added some helper functions and made note how it could be improved by
>   adding Bound union of boxes to additionaly optimize intersection test

Essentially, my ikdea of some providing code was "fully tested" code, not code
I would need to debug myself and that would possibly need several iterations
until it completely works.  Without having time for it that is really the only
thing that could have been used.  Anyway, it is probably too late now.

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message