Jump to content
  • Advertisement
Sign in to follow this  
polyfrag

Line-Convex Hull Intersection not working

This topic is 2034 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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;
}

 

 

Share this post


Link to post
Share on other sites
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;

Share this post


Link to post
Share on other sites

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;
}

Share this post


Link to post
Share on other sites

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.+ p.y*normal.+ p.z*normal.z);

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

    return false;
}

Edited by DonTzzy

Share this post


Link to post
Share on other sites

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;
}

Share this post


Link to post
Share on other sites
  • 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)

Share this post


Link to post
Share on other sites

  • 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. Edited by polyfrag

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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;	//???
}

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!