in UVAtlas/isochart/isochartutil.cpp [59:294]
static void CalculateSegmentsIntersection(
const XMFLOAT2& p0, const XMFLOAT2& p1, // Two ports of segment 1
const XMFLOAT2& p3, const XMFLOAT2& p4, // Two ports of segment 2
XMFLOAT2& intersection,
float& fT,
float& fS)
{
float x0, x1, x3, x4;
float y0, y1, y3, y4;
x0 = p0.x;
y0 = p0.y;
x1 = p1.x;
y1 = p1.y;
x3 = p3.x;
y3 = p3.y;
x4 = p4.x;
y4 = p4.y;
fT = -2.0f; // Set fT and fS to a value out of the range [0.0, 1.0]
fS = -2.0f;
// if line degenerates into point, return
if (IsInZeroRange(x1 - x0) && IsInZeroRange(y1 - y0))
{
return;
}
if (IsInZeroRange(x4 - x3) && IsInZeroRange(y4 - y3))
{
return;
}
// if x3 == x4
if (IsInZeroRange(x3 - x4))
{
// Logically, y4 - y3 must not be zero here. or else the function will return before
// run to here. Using assert here only for check the potential error
// (such as Stack Overflow), and tell the readers why we need not defend
// devide-zero exception, when using y4 - y3 or y3 - y4 as denominator
// The other assert(!IsInZeroRange(...)) in the function also have the same
// target as this.
assert(!IsInZeroRange(y4 - y3));
if (IsInZeroRange(x0 - x1))
{
// x0 = x3 = x;
// y0 + fT*(y1-y0) = y3 + fS*(y4-y3) = y;
assert(!IsInZeroRange(y1 - y0));
// line1 & line2 are parallels. No intersection, return directly.
if (!IsInZeroRange(x3 - x0))
{
return;
}
else // line1 & line2 overlap, Select one point on overlapped segment as intersection
{
intersection.x = x0;
if (!CalculateOverlappedSegmentsIntersection(
y0, y1, y3, y4, intersection.y))
{
return;
}
//y0 + fT*(y1-y0) = intersection.y
//y3 + fS*(y4-y3) = intersection.y
fT = (intersection.y - y0) / (y1 - y0);
fS = (intersection.y - y3) / (y4 - y3);
return;
}
}
else // x0 != x1
{
// x0 + fT*(x1-x0) = x3 = x;
// y0 + fT*(y1-y0) = y3 + fS*(y4-y3) = y
fT = (x3 - x0) / (x1 - x0);
intersection.x = x3;
intersection.y = y0 + fT * (y1 - y0);
fS = (intersection.y - y3) / (y4 - y3);
return;
}
}
else if (IsInZeroRange(y3 - y4))
{
assert(!IsInZeroRange(x4 - x3));
if (IsInZeroRange(y0 - y1))
{
// x0 + fT*(x1 - x0) = x3 + fS*(x4 - x3) = x
// y0 = y3 = y
assert(!IsInZeroRange(x0 - x1));
if (!IsInZeroRange(y3 - y0))
{
return;
}
else
{
intersection.y = y0;
if (!CalculateOverlappedSegmentsIntersection(
x0, x1, x3, x4, intersection.x))
{
return;
}
// x0 + fT*(x1 - x0) = intersection.x
// x3 + fS*(x4 - x3) = intersection.x
fT = (intersection.x - x0) / (x1 - x0);
fS = (intersection.x - x3) / (x4 - x3);
return;
}
}
else // y0 != y1
{
// x0 + fT*(x1 - x0) = x3 + fS*(x4 - x3) = x
// y0 + fT*(y1 - y0) = y3 = y
fT = (y3 - y0) / (y1 - y0);
intersection.x = x0 + fT * (x1 - x0);
intersection.y = y3;
fS = (intersection.x - x3) / (x4 - x3);
return;
}
}
else if (IsInZeroRange(x0 - x1))
{
// x0 = x3 + fS*(x4 - x3) = x
// y0 + fT*(y1 - y0) = y3 + fS*(y4 - y3) = y
assert(!IsInZeroRange(y0 - y1));
assert(!IsInZeroRange(x3 - x4));
fS = (x0 - x3) / (x4 - x3);
intersection.x = x0;
intersection.y = y3 + fS * (y4 - y3);
fT = (intersection.y - y0) / (y1 - y0);
return;
}
else if (IsInZeroRange(y0 - y1))
{
// x0 + fT*(x1 - x0) = x3 + fS*(x4 - x3) = x
// y0 = y3 + fS*(y4 - y3) = y
assert(!IsInZeroRange(x0 - x1));
assert(!IsInZeroRange(y3 - y4));
fS = (y0 - y3) / (y4 - y3);
intersection.x = x3 + fS * (x4 - x3);
intersection.y = y0;
fT = (intersection.x - x0) / (x1 - x0);
return;
}
else
{
assert(!IsInZeroRange(x1 - x0));
assert(!IsInZeroRange(x4 - x3));
assert(!IsInZeroRange(y1 - y0));
assert(!IsInZeroRange(y4 - y3));
// x0 + fT*(x1 - x0) = x3 + fS*(x4 - x3) = x
// y0 + fT*(y1 - y0) = y3 + fS*(y4 - y3) = y
// 1. Check if two lines are parallel
float v1[2], v2[2], fLength;
v1[0] = x1 - x0;
v1[1] = y1 - y0;
fLength = IsochartSqrtf(v1[0] * v1[0] + v1[1] * v1[1]);
if (IsInZeroRange(fLength))
{
return;
}
v1[0] /= fLength;
v1[1] /= fLength;
v2[0] = x4 - x3;
v2[1] = y4 - y3;
fLength = IsochartSqrtf(v2[0] * v2[0] + v2[1] * v2[1]);
v2[0] /= fLength;
v2[1] /= fLength;
// 2. Two lines are parallel.
if (fabsf(v1[0] * v2[1] - v1[1] * v2[0])
< ISOCHART_ZERO_EPS / 2.0f)
{
v1[0] = (x3 - x0) / (x1 - x0);
v1[1] = (y3 - y0) / (y1 - y0);
if (!IsInZeroRange(v1[0] - v1[1]))//Two lines are not overlapped, return
{
return;
}
else //Calculate intersection of overlapped lines
{
if (!CalculateOverlappedSegmentsIntersection(
x0, x1, x3, x4, intersection.x))
{
return;
}
fT = (intersection.x - x0) / (x1 - x0);
fS = (intersection.x - x3) / (x4 - x3);
intersection.y = y0 + fT * (y1 - y0);
return;
}
}
else // 3. two Lines are not parallel, resolve the original equation to get fT and fS
{
fT = ((x3 - x0) * (y4 - y3) - (y3 - y0) * (x4 - x3)) / ((x1 - x0) * (y4 - y3) - (y1 - y0) * (x4 - x3));
intersection.x = x0 + fT * (x1 - x0);
intersection.y = y0 + fT * (y1 - y0);
if (fabsf(x4 - x3) > fabsf(y4 - y3))
{
fS = (intersection.x - x3) / (x4 - x3);
}
else
{
fS = (intersection.y - y3) / (y4 - y3);
}
return;
}
}
}