Hi all,
The volume story continues. :)
The current cyl<->cyl test is quite naive and does not handle the common
case with cylinders of non-infinite length.
I've picked up some code from the net which fixes this, and this time it
is useful in OpenSG. However, it uses capsules (cyls with hemispheres at
the ends) instead of cylinders, so it is not entirely accurate either,
although much better than the existing test. Capsules are faster and
easier to handle than flat-capped cylinders, so a replacement might be
an idea for 2.0?
See attached file for source code on the test (it's an extract from my
sources, thus lacking of includes and such stuff). I hope it'll be useful.
Best regards,
/Marcus
P.S. W.r.t. some comments in osg::Line on handling of
infinite/semi-infinite/non-infinite lines, I think it should be split
into separate classes for Line, Ray and Segment, respectively. Makes it
easier to understand and reason about geometric code. Naturally, they
could all use a common parent class if deemed useful. (Updating CylVol
to use an Segment would then be a nice touch. :)
bool myCylIntersect(const CylinderVolume * cyl1, const CylinderVolume * cyl2)
{
Pnt3f p1, p2;
Vec3f v1, v2;
cyl1->getAxis(p1, v1);
cyl2->getAxis(p2, v2);
return dist3D_Segment_to_Segment(p1, v1, p2, v2) <= (cyl1->getRadius() +
cyl2->getRadius());
}
//
http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm#dist3D_Segment_to_Segment()
// Adapted for OpenSG by Marcus Lindblom 2005-09-06
// Copyright 2001, softSurfer (www.softsurfer.com)
// This code may be freely used and modified for any purpose
// providing that this copyright notice is included with it.
// SoftSurfer makes no warranty for this code, and cannot be held
// liable for any real or imagined damage resulting from its use.
// Users of this code must verify correctness for their application.
// Assume that classes are already given for the objects:
// Point and Vector with
// coordinates {float x, y, z;}
// operators for:
// Point = Point ± Vector
// Vector = Point - Point
// Vector = Vector ± Vector
// Vector = Scalar * Vector
// Line and Segment with defining points {Point P0, P1;}
// Track with initial position and velocity vector
// {Point P0; Vector v;}
//===================================================================
float dist3D_Segment_to_Segment( const Pnt3f& s1p, const Vec3f& s1d,
const Pnt3f& s2p, const Vec3f& s2d)
{
const float SMALL_NUM = 1e-9f; // anything that avoids division overflow
const Vec3f& u = s1d;
const Vec3f& v = s2d;
Vec3f w = s1p - s2p;
float a = u.dot(u); // always >= 0
float b = u.dot(v);
float c = v.dot(v); // always >= 0
float d = u.dot(w);
float e = v.dot(w);
float D = a*c - b*b; // always >= 0
float sc, sN, sD = D; // sc = sN / sD, default sD = D >= 0
float tc, tN, tD = D; // tc = tN / tD, default tD = D >= 0
// compute the line parameters of the two closest points
if (D < SMALL_NUM) { // the lines are almost parallel
sN = 0.0; // force using point P0 on segment S1
sD = 1.0; // to prevent possible division by 0.0 later
tN = e;
tD = c;
}
else { // get the closest points on the infinite lines
sN = (b*e - c*d);
tN = (a*e - b*d);
if (sN < 0.0) { // sc < 0 => the s=0 edge is visible
sN = 0.0;
tN = e;
tD = c;
}
else if (sN > sD) { // sc > 1 => the s=1 edge is visible
sN = sD;
tN = e + b;
tD = c;
}
}
if (tN < 0.0) { // tc < 0 => the t=0 edge is visible
tN = 0.0;
// recompute sc for this edge
if (-d < 0.0)
sN = 0.0;
else if (-d > a)
sN = sD;
else {
sN = -d;
sD = a;
}
}
else if (tN > tD) { // tc > 1 => the t=1 edge is visible
tN = tD;
// recompute sc for this edge
if ((-d + b) < 0.0)
sN = 0;
else if ((-d + b) > a)
sN = sD;
else {
sN = (-d + b);
sD = a;
}
}
// finally do the division to get sc and tc
sc = (abs(sN) < SMALL_NUM ? 0.0 : sN / sD);
tc = (abs(tN) < SMALL_NUM ? 0.0 : tN / tD);
// get the difference of the two closest points
Vec3f dP = w + (sc * u) - (tc * v); // = S1(sc) - S2(tc)
return dP.length(); // return the squared distance
}
