Line-Convex Hull Intersection not working

Started by
7 comments, last by polyfrag 10 years, 11 months ago

What's wrong with my code?


bool PointBehindPlane(Vec3f p, Vec3f normal, float dist)
{
	float result = p.x*normal.x + p.y*normal.y + p.z*normal.z + dist;
	
	//if(result < 0)
	if(result < EPSILON)
		return true;

	return false;
}

// line intersects plane?
bool LineInterPlane(Vec3f* line, Vec3f norm, float d, Vec3f* inter)
{
	Vec3f change = line[1] - line[0];

	float denom = Dot(norm, change);

	if(fabs(denom) <= EPSILON)
		return false;
		
	float SegScalar = (d - Dot(norm, line[0])) / denom;
		
	//TODO: Check if SegScalar is [0.0, 1.0]?
	if(SegScalar < 0.0f)
		return false;
		
	*inter = change * SegScalar + line[0];

	return true;
}

// http://thejuniverse.org/PUBLIC/LinearAlgebra/LOLA/planes/std.html
void MakePlane(Vec3f* norm, float* d, Vec3f point, Vec3f setnorm)
{
	*norm = setnorm;
	*d = Dot(setnorm, point);
}

void MakeHull(Vec3f* norms, float* ds, Vec3f pos, float radius, float height)
{
	MakePlane(&norms[0], &ds[0], pos + Vec3f(0, height, 0), Vec3f(0, 1, 0));	//up
	MakePlane(&norms[1], &ds[1], pos + Vec3f(0, 0, 0), Vec3f(0, -1, 0));		//down
	MakePlane(&norms[2], &ds[2], pos + Vec3f(-radius, 0, 0), Vec3f(-1, 0, 0));	//left
	MakePlane(&norms[3], &ds[3], pos + Vec3f(radius, 0, 0), Vec3f(1, 0, 0));	//right
	MakePlane(&norms[4], &ds[4], pos + Vec3f(0, 0, -radius), Vec3f(0, 0, -1));	//front
	MakePlane(&norms[5], &ds[5], pos + Vec3f(0, 0, radius), Vec3f(0, 0, 1));	//back
}

// line intersects convex hull?
bool LineInterHull(Vec3f* line, Vec3f* norms, float* ds, int numplanes)
{
	bool* hasinter = new bool[numplanes];
	Vec3f* inter = new Vec3f[numplanes];

	for(int i=0; i<numplanes; i++)
	{
		hasinter = LineInterPlane(line, norms, ds, &inter);
	}

	for(int i=0; i<numplanes; i++)
	{
		if(hasinter)
		{
			bool allin = true;
			for(int j=0; j<numplanes; j++)
			{
				if(i == j)
					continue;

				if(!PointBehindPlane(inter, norms[j], ds[j]))
				{
					allin = false;
					break;
				}
			}
			if(allin)
			{
				delete [] hasinter;
				delete [] inter;

				return true;
			}
		}
	}

	delete [] hasinter;
	delete [] inter;

	return false;
}

Advertisement

for(int i=0; i {
if(hasinter)
{
bool allin = true;
for(int j=0; j {
if(i == j)
continue;

if(!PointBehindPlane(inter, norms[j], ds[j]))
{
allin = false;
break;
}
}
if(allin)
{
delete [] hasinter;
delete [] inter;

return true;
}
}
}

delete [] hasinter;
delete [] inter;

return false;

;>;>

This might work, but I'm not 100% sure:

for(int i=0; i<numplanes; i++)
{
if(hasinter[i])
{
for(int j=0; j<numplanes; j++)
{
if(i == j)
continue;

if(!PointBehindPlane(inter[i], norms[j], ds[j]))
{
delete [] hasinter;
delete [] inter;


return false;
}
}
}
}

delete [] hasinter;
delete [] inter;

return true;

It's saying that the intersection point (286.852, 2, 423.175) isn't behind the plane (1,0,0), d=289.256.

What's wrong with this math?


bool PointBehindPlane(Vec3f p, Vec3f normal, float dist)
{
	float result = p.x*normal.x + p.y*normal.y + p.z*normal.z + dist;
	//1*286.852 + 0*2 + 0*423.175 + 289.256 = 286.852
	
	//if(result < 0)
	if(result < EPSILON)
		return true;

	return false;
}

float result = p.x*normal.x + p.y*normal.y + p.z*normal.z + dist;

bool PointBehindPlane(Vec3f p, Vec3f normal, float dist)
{
// float result = p.x*normal.x + p.y*normal.y + p.z*normal.z + dist;

float result = dist - (p.x*normal.x + p.y*normal.y + p.z*normal.z);


//if(result < 0)
if(result < EPSILON)
return true;

return false;
}

Now it's saying (284.875, 2, 424.645) isn't behind (0,-1,0),d=0.


bool PointBehindPlane(Vec3f p, Vec3f normal, float dist)
{
	//float result = p.x*normal.x + p.y*normal.y + p.z*normal.z + dist;
	// 1*286.852 + 0*2 + 0*423.175 + 289.256 = 286.852

	float result = dist - (p.x*normal.x + p.y*normal.y + p.z*normal.z);
	// 0 - (0*284.875 + -1*2 + 0*424.645) = 2

	//if(result < 0)
	if(result < EPSILON)
		return true;

	return false;
}
  • You shouldn't be allocating memory within a function like in LineInterHull, it's not necessary and slow. Just rearrange your test so that you merge both loops into one, and hence no need to cache the intersection data.
  • Pass your vectors by const reference rather than by value.
  • the line in MakePlane should be *d = -Dot( setnorm, point ). This is because the plane equation is defined as: a*x + b*y + c*z + d = 0, where (a,b,c) is the normal and d is the plane 'distance', so d = -(a*x + b*y + c*z)

  • the line in MakePlane should be *d = -Dot( setnorm, point ). This is because the plane equation is defined as: a*x + b*y + c*z + d = 0, where (a,b,c) is the normal and d is the plane 'distance', so d = -(a*x + b*y + c*z)
Does that mean d is the distance from the plane TO the origin (instead of distance along the normal to the plane)?

I'm getting:
plane=(0,1,0),-2
plane=(0,-1,0),-0
plane=(-1,0,0),281.256
plane=(1,0,0),-289.256
plane=(0,0,-1),419.972
plane=(0,0,1),-427.972
The first one pointing upward should be 2 units above origin.

That gives me an erroneous intersection at (286.882, -2, 421.707) because the planes only go down to 0 and up to +2.

Using -d for LineInterPlane I found a mistake:


// line intersects convex hull?
bool LineInterHull(const Vec3f* line, const Vec3f* norms, const float* ds, const int numplanes)
{
	for(int i=0; i<numplanes; i++)
    {
		Vec3f inter;
        if(LineInterPlane(line, norms, -ds, &inter))
        {
            for(int j=0; j<numplanes; j++)
            {
                if(i == j)
                    continue;
				
				if(!PointBehindPlane(inter, norms[j], ds[j]))
                    return false;
            }

			return true;
        }
    }

    return true;	//???
}

void MakePlane(Vec3f* norm, float* d, Vec3f point, Vec3f setnorm)
{
	*norm = setnorm;
	*d = -Dot(setnorm, point);
}

It works now.

Another correction


// line intersects convex hull?
bool LineInterHull(const Vec3f* line, const Vec3f* norms, const float* ds, const int numplanes)
{
	for(int i=0; i<numplanes; i++)
    {
		Vec3f inter;
        if(LineInterPlane(line, norms, -ds, &inter))
        {
			bool allin = true;
			for(int j=0; j<numplanes; j++)
			{
				if(i == j)
					continue;

				if(!PointBehindPlane(inter, norms[j], ds[j]))
				{
					allin = false;
					break;
				}
			}
			if(allin)
			{
				return true;
			}
        }
    }

    return false;	//???
}

This topic is closed to new replies.

Advertisement