Jump to content
  • Advertisement
Sign in to follow this  
RonD

Triangle/Triangle Intersection

This topic is 3502 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

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 this post


Link to post
Share on other sites
Advertisement
Hi,

I think the problem was when calculating a point on the intersection line.
I made some adjustments and now it's working.
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);
}

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!