# Triangle/Triangle Intersection

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

## Recommended Posts

Hi, Okay, I have been working on this pretty much all day, and could not get it working. The algorithm used is supposed to be "A Fast Triangle-Triangle Intersection Test" as described by Thomas Moeller. What happens at the moment is, that despite no intersection being the case, intersections are being calculated. If the result is "no intersection", this is in all cases I have tested, a correct result. I believe, that the first few steps work(rejecting if all points of a triangle are on the same side of the plane created by the other triangle). I tested that separately, and the results were always as expected. I think the problem is part of the intersection line calculation, but I do not have a clue whats wrong there. Well, here is the code for the TriangleTriangle intersection:
for (int triId1=0; triId1<obj1.polygons_qty; triId1++){
for (int triId2=0; triId2<obj2.polygons_qty; triId2++){
// transform both triangles, according to the model position
const polygon_type& p1 = obj1.polygon[triId1];
const polygon_type& p2 = obj2.polygon[triId2];
Vector3f tri1[] = {	// holds all vertex vectors for triangle 1
Vector3f(obj1.vertex[p1.a].x,obj1.vertex[p1.a].y,obj1.vertex[p1.a].z),
Vector3f(obj1.vertex[p1.b].x,obj1.vertex[p1.b].y,obj1.vertex[p1.b].z),
Vector3f(obj1.vertex[p1.c].x,obj1.vertex[p1.c].y,obj1.vertex[p1.c].z),
};
Vector3f tri2[] = {	// holds all vertex vectors for triangle 2
Vector3f(obj2.vertex[p2.a].x,obj2.vertex[p2.a].y,obj2.vertex[p2.a].z),
Vector3f(obj2.vertex[p2.b].x,obj2.vertex[p2.b].y,obj2.vertex[p2.b].z),
Vector3f(obj2.vertex[p2.c].x,obj2.vertex[p2.c].y,obj2.vertex[p2.c].z)
};
for(int ptId=0; ptId<3; ptId++){	// apply transforms on all vertices
tri1[ptId] = m1.instancetransform * tri1[ptId];
tri2[ptId] = m2.instancetransform * tri2[ptId];
}
Vector3f tri1Normal = Vector3f::cross(tri1[1]-tri1[0], tri1[2]-tri1[0]);
Vector3f tri2Normal = Vector3f::cross(tri2[1]-tri2[0], tri2[2]-tri2[0]);
// reject as trivial if all points of tri1 are on same side of plane created by tri2
float sideT1P0 = Vector3f::dot((tri2[0]-tri1[0]),tri2Normal);
float sideT1P1 = Vector3f::dot((tri2[0]-tri1[1]),tri2Normal);
float sideT1P2 = Vector3f::dot((tri2[0]-tri1[2]),tri2Normal);
if(	(sideT1P0>0.0f) == (sideT1P1>0.0f)
&& (sideT1P0>0.0f) == (sideT1P2>0.0f)){	// all on one side of a plane
break;
}
// reject as trivial if all points of tri2 are on same side of plane created by tri1
float sideT2P0 = Vector3f::dot((tri1[0]-tri2[0]),tri1Normal);
float sideT2P1 = Vector3f::dot((tri1[0]-tri2[1]),tri1Normal);
float sideT2P2 = Vector3f::dot((tri1[0]-tri2[2]),tri1Normal);
if(	(sideT2P0>0.0f) == (sideT2P1>0.0f)
&& (sideT2P0>0.0f) == (sideT2P2>0.0f)){	// all on one side of a plane
break;
}
// compute intersetion line
Vector3f pid = Vector3f::cross(tri1Normal, tri2Normal);	// plane intersection direction
Vector3f iP;// point on the intersection line of the planes
// determine max abs coordinate of planeIntersectionDir (gives more robust computations)
int maxc;{
if (abs(pid.getX()) > abs(pid.getY())) {
if (abs(pid.getX()) > abs(pid.getZ()))
maxc = 1;
else maxc = 3;
}
else {
if (abs(pid.getY()) > abs(pid.getZ()))
maxc = 2;
else maxc = 3;
}
}
// set maxcoord to zero and solve for the remaining coordinates
tri1Normal.normalise();
tri2Normal.normalise();
float d1 = Vector3f::dot(tri1Normal, tri1[0]);
float d2 = Vector3f::dot(tri2Normal, tri2[0]);
switch (maxc) {// depending on what is the max coordinate set intersectionPoint
case 1:                    // intersect with x=0
iP.set( 0.0f,

(d2*tri1Normal.getZ() - d1*tri2Normal.getZ()) / pid.getX(),
(d1*tri2Normal.getY() - d2*tri1Normal.getY()) / pid.getX());
break;
case 2:                    // intersect with y=0
iP.set(	(d1*tri2Normal.getZ() - d2*tri1Normal.getZ()) / pid.getY(),
0.0f,
(d2*tri1Normal.getX() - d1*tri2Normal.getX()) / pid.getY());
break;
case 3:                    // intersect with z=0
iP.set(	(d2*tri1Normal.getY() - d1*tri2Normal.getY()) / pid.getZ(),
(d1*tri2Normal.getX() - d2*tri1Normal.getX()) / pid.getZ(),
0.0f);
}
// project triangles onto intersection line and calculate intervals
// minimum and maximum values on the line for both triangles:
float minT1, maxT1;
float minT2, maxT2;
minT1 = Vector3f::dot(pid,tri1[0]-iP);
maxT1 = minT1;
minT2 = Vector3f::dot(pid,tri2[0]-iP);
maxT2 = minT2;
for(int ptId=1; ptId<3; ptId++){
float distT1=Vector3f::dot(pid,tri1[ptId]-iP);
minT1 = min(minT1, distT1);
maxT1 = max(maxT1, distT1);
float distT2=Vector3f::dot(pid,tri2[ptId]-iP);
minT2 = min(minT2, distT2);
maxT2 = max(maxT2, distT2);
}
// intersect the intervals
if(maxT1<minT2 || maxT2<minT1){
break;
}
return true;
}
}
return false;


The code might not be written very efficiently with all sorts of optimisations, but I would rather get it working at all, before doing such things. Thanks for any help, RonD

##### Share on other sites
Hi,

I think the problem was when calculating a point on the intersection line.
Another thing that can be improved is calculating the intervals. In your code, the intervals are te projection of the points on the intersection line. In fact the intervals are the intersections of the triangles edges with the intersection line. Anyway this is not a problem, becouse it just aproximates the intervals.

  			float d1 = Point3D::dot(tri1Normal, tri1[0]);    			float d2 = Point3D::dot(tri2Normal, tri2[0]);    			float den=0; //denominator    			switch (maxc) {    				case 1:                    			             den = tri1Normal.getY()*tri2Normal.getZ()- tri2Normal.getY()*tri1Normal.getZ();    					iP.set( 0.0f,    						(d1*tri2Normal.getZ() - d2*tri1Normal.getZ()) / den,    							(d2*tri1Normal.getY() - d1*tri2Normal.getY()) / den);    					break;    				case 2:                        				     den = tri2Normal.getX()*tri1Normal.getZ()- tri1Normal.getX()*tri2Normal.getZ();    					iP.set(	(d2*tri1Normal.getZ() - d1*tri2Normal.getZ()) / den,    							0.0f,    							(d1*tri2Normal.getX() - d2*tri1Normal.getX()) / den);    					break;    				case 3:                                             den = tri1Normal.getX()*tri2Normal.getY()- tri2Normal.getX()*tri1Normal.getY();    					iP.set(	(d1*tri2Normal.getY() - d2*tri1Normal.getY()) / den,    							(d2*tri1Normal.getX() - d1*tri2Normal.getX()) / den,    							0.0f);    			}

1. 1
Rutin
32
2. 2
3. 3
4. 4
5. 5

• 13
• 9
• 9
• 9
• 14
• ### Forum Statistics

• Total Topics
633325
• Total Posts
3011372
• ### Who's Online (See full list)

There are no registered users currently online

×