triangles intersecting in 3d space(very very important)


(kos) #1

i am currently doing a project on a T-REX.i’m surely gonna animate it.but sometimes it happens when two faces are too close when they are deformed by armatures they intersect each other resulting a very ugly deformation.to get reed of it i thought of making some python script that will restrict the faces to intersect at the time of animation.but the problem is what the unique condition is satisfied when two triangles intersect each other(the faces are imaginally devided in triangles).anybody can tell me the condition of intersecting two triangle in 3d space.i used to be a good student in maths.but as time passed by i forgot everything. :-?


(Kid Tripod) #2

i don’t think this answers that question, but that problem is why i use subsurfs a lot with armature vertex deformations, as it means you points are further apart and don’t overlap. (It might help you, but it might alter the appearance and it will increase render time.) You might have more luck stopping one vertex moving past the over and causing the problem in the first place. Shouldn’t be too hard, if you can work out which vertex it is! I’d recommend the python forum for more information.


(S68) #3

I’m going to write down something, quickly. With no mathematical proof, so take this with care

A triangle is a three vertex - three edges stuff.

Two triangles intersects if AT least one of the edges of a triangle intersect the surface of the other.

This reconduct the problem to three separate checks: checking if a segment (the edge of triangle 1) intersects triangle 2.

This is a first for edge=1,2,3 cycle

To check if an edge intersects a triangle you must first check if the infinite line containing the segment (is is easy to write the line, knowing the two segments ends (x1,y1,z1) and (x2,y2,z2) the line is

(x-x1)/(x2-x1)=(y-y1)/(y2-y1)=(z-z1)/(z2-z1)

and the plane containing the triangle (can’t remember the formula by hart, but it is easy)

The compute the intersection between the plane and the line.

IF the intersection plane-line is a point P which is on the line (of course) BUT outside the segment then the wo cannot intersect.

IF point P is WITHIN the segment then they MIGHT intersect, so you must
check if P is WITHIN the triangle or not.

If it is then you have intersection.

I hope this helps

Stefano


(kos) #4

i do not have much time to read your solution thoroughly right now…but i think it will certainly help.i too thought of the same concept of yours…and will try to modify it.actually we need some kind of flexors in blender.