|
 |
"Thorsten Froehlich" <tho### [at] trf de> 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
|
|
