// Skip the next paragraph if you like.. nothing too important
now my colllision detection works mainly by bounding spheres - one for object itself and one for each part.. when two objects collide their bspheres are checked against the bspheres of others - ill get around to optimizing which to check with which later - and when a sphere collision is found the bsptree of one is checked against the keylines of ohers... im pretty sure it is quite a fast collision detection for its accuracy. in some cases (both living things) the bbsp-keyline checks are reversed(one object against the other and then the other way round too)
So as deducted from the previous paragraph i need to find good central points for bounding spheres that would leave minimal free space inside. AS the central point and radius finding are preprocessing, the algorithm can be quite slow. What I thought of was basic geometry (not like i know much beyound 2-d functions with triangles i learnt in 9-th grade last year) Im not sure of the terms in english but when finding the central point of a triangle for outer circle, one would draw a line which is perpendicular to the side on two sides(normally 3 on paper for accuracy but two will do)and use the point where they cross. Now i figured that finding 3 longest distances between points in an object, finding the centers of these lines and generating planes to simulate the perpendicular lines(plane normals being the same direction the lines go) and finding the point where the 3 planes cross would give a pretty good central point.
I have heared all sorts of different ideas some better, some worse. All i want now is to know IF THIS THEORY IS SOUND - no better or other ideas please
Heres the source:
#define LARGEST_FLOAT 340000000000000000000000000000000000000.f
#define SMALLEST_FLOAT -LARGEST_FLOAT
float GenerateBoundingSphere(PartTemplate * part, point3 * cp) //Used as utility to generate bounding sphere radius and central point best suited for collision detection
{
int points[3][2], test[2];
int i,k,m;
float lenghts[3];
float buf,buf1;
plane a,b,c,bufplane;
if (cp==NULL)
cp=new point3;
if (part->VertexCount==2)
{
*cp=(part->Vertices[0].p+part->Vertices[1].p)/2;
return (part->Vertices[0].p-part->Vertices[1].p).Mag()/2;
}
if (part->VertexCount==1)
{
*cp=part->Vertices[0].p;
return 0.00000000000000000001f; // a particle:)
}
if (part->VertexCount<=0)
return -1.f;
for(i=0;i<part->VertexCount;i++)
for(k=i+1;k<part->VertexCount;k++)
{
buf=(part->Vertices[i].p-part->Vertices[k].p).MagSquared();
for(m=0;m<3;m++)
if (buf>lenghts[m])
{
points[m][0]=i;
points[m][1]=k;
lenghts[m]=buf;
}
}
a=cPlane((part->Vertices[points[0][0]].p - part->Vertices[points[0][1]].p).Normalized(),
(part->Vertices[points[0][0]].p + part->Vertices[points[0][1]].p)/2);
b=cPlane((part->Vertices[points[1][0]].p - part->Vertices[points[1][1]].p).Normalized(),
(part->Vertices[points[1][0]].p + part->Vertices[points[1][1]].p)/2);
c=cPlane((part->Vertices[points[2][0]].p - part->Vertices[points[2][1]].p).Normalized(),
(part->Vertices[points[1][0]].p + part->Vertices[points[2][1]].p)/2);
if (a.n==b.n) //This is a straightforward switching of planes and their tip points
{
*cp=c.n; c.n=b.n; b.n=*cp;
i=points[1][0]; k=points[1][1]; points[1][0]=points[2][0]; points[1][1]=points[2][1]; points[2][0]=i; points[2][1]=k;
buf=c.d; c.d=b.d; b.d=buf;
}
if (a.n==c.n || b.n==c.n)
{
lenghts[2]=SMALLEST_FLOAT;
test[0]=points[2][0];
test[1]=points[2][0];
// Same cycle as previously exept now it makes shure it doesnt generate parallel planes
for(i=0;i<part->VertexCount;i++)
for(k=i+1;k<part->VertexCount;k++)
{
if (( i==points[0][0] && k==points[0][1]) ||
( i==points[1][0] && k==points[1][1]) ||
( i==test[0] && k==test[1] ))
continue;
buf=(part->Vertices[i].p-part->Vertices[k].p).MagSquared();
if (buf>lenghts[2])
{
*cp=(part->Vertices[i].p - part->Vertices[k].p).Normalized();
if (*cp==a.n || *cp==b.n)
continue;
points[2][0]=i;
points[2][1]=k;
lenghts[2]=buf;
}
}
}
if (lenghts[2]==SMALLEST_FLOAT) // or initial value which is with "-" -- something which a lenght cannot really be -- basically means no new value has been found
return -1.f;
c=cPlane((part->Vertices[points[2][0]].p - part->Vertices[points[2][1]].p).Normalized(),
(part->Vertices[points[1][0]].p + part->Vertices[points[2][1]].p)/2);
*cp=cMatrix4( a.n.x, a.n.y, a.n.z, -a.d,
b.n.x, b.n.y, b.n.z, -b.d,
c.n.x, c.n.y, c.n.z, -c.d,
0, 0, 0, 1)*cPoint3(0,0,0);
buf1=0;
for(i=0;i<3;i++)
for(k=0;k<2;k++)
{
buf=(part->Vertices[points[i][k]].p-*cp).MagSquared();
if (buf>buf1)
buf1=buf;
}
return (float)sqrt(buf1);
};
Also i have posted this on another forum on this site and recieved nothign which i wanted. I hope peaople on this board know this stuff better tho
[edited by - Velochy on July 25, 2002 2:52:40 AM]
