# 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.

## 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 on other sites

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


1. 1
2. 2
3. 3
4. 4
Rutin
15
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633724
• Total Posts
3013554
×