coplanar triangles

Blitz3D Forums/Blitz3D Programming/coplanar triangles

Warner

(Posted 2009) [#1]

Not sure if this is the right term, but is there a way to determine if two 3d triangles are overlapping ? I want to prevent 'z-order fighting' (on a single mesh)

Ross C

(Posted 2009) [#2]

I suppose you could use a line to triangle intersect code, that would tell you if a triangles edge is gooing straigh through the middle of another triangle?

Warner

(Posted 2009) [#3]

I find it difficult to explain what I mean. The triangles should be coplanar and overlapping, like the triangles in this example:

Graphics3D 800, 600, 0, 2
SetBuffer BackBuffer()

mesh1 = CreateMesh()
surf1 = CreateSurface(mesh1)
AddVertex surf1, 0, 2, 0
AddVertex surf1, 2, 0, 0
AddVertex surf1, 0, 0, 0
AddTriangle surf1, 0, 1, 2

mesh2 = CreateMesh()
surf2 = CreateSurface(mesh2)
AddVertex surf2, 1, 2, 0
AddVertex surf2, 3, 0, 0
AddVertex surf2, 0.5, 0.2, 0
AddTriangle surf2, 0, 1, 2

WireFrame 1

piv = CreatePivot()
cam = CreateCamera(piv)
MoveEntity cam,0,0,-5

Repeat

	TurnEntity piv, 0, 1, 0
	RenderWorld
	Flip
	
Until KeyHit(1)

End

I just can't seem to think of a good way to test for this.

Sledge

(Posted 2009) [#4]

Use MeshesIntersect(). You might have to extend each model into some sort of pyramid structure, mind, as I *think* (it's been a while) it fails if the geometry is flat and on the same plane.

Warner

(Posted 2009) [#5]

Indeed MeshesIntersect doesn't detect this type of overlap.
In my code, I merged two models, but some of the triangles are overlapping. I would like to scan the resulting mesh for these overlapping triangles, so I can remove them. For that reason, altering the mesh isn't really an option. It would interfere with the non-overlapping part of the mesh.

Ross C

(Posted 2009) [#6]

There must be a maths equaltion for detecting triangles intersecting... I'll have a look see when i get home. Worst comes to the worst, create a mesh with one triangle and another mesh with another triangle. Alter the both triangles to check through every combination of two triangles possible, using meshintersect every time.

H. T. U.

(Posted 2009) [#7]

Hmm, this seems familiar. You should be able to detect it through some modified inequality functions, but I've only used these on 2-dimensional graphs. It should work 3-dimensionally, but it will be more complex and I don't have any experience there. I'll see what I can do, but I'm not at home either :)

Ross C

(Posted 2009) [#8]

If the two triangle lie on the same plane, then a line intersect equation would also help here.

H. T. U.

(Posted 2009) [#9]

Such as this (it's 2d on the x and y axis)?

;find EOL of first and second lines:
x11=firstlinefirstvertexX
x12=firstlinesecondvertexX
y11=firstlinefirstvertexY
y12=firstlinesecondvertexY
m1=(y11-y12)/(x11-x12)
b1=-m1*x11+y11

x21=secondlinefirstvertexX
x22=secondlinesecondvertexX
y21=secondlinefirstvertexY
y22=secondlinesecondvertexY
m2=(y21-y22)/(x21-x22)
b2=-m2*x21+y21

;sort the smallest and largest Y coordinates
If y11>=y12
    ly1=y12
    gy1=y11
Else
    ly1=y11
    gy1=y12
End If

If y21>=y22
    ly2=y22
    gy2=y21
Else
    ly2=y21
    gy2=y22
End If

;check for intersection
If (b1-b2)<>0 And (m2-m1)<>0;if the lines aren't parallel or identical
    x=(b1-b2)/(m2-m1);intersection X coordinate
    If Not ((ly1<=m1*x+b1 And gy1>=m1*x+b1) And (ly2<=m2*x+b2 And gy2>=m2*x+b2));if the coordinate fits in both lines
        x=4096;a tag number that shows that there is no solution between the two lines
    End If
Else
    x=4096;a tag number that shows that there is no solution
End If
;X returns the intersect X point or no solution

I hope my math is correct (I don't have time to check it). Please note that this only checks intersection in two lines.

Ross C

(Posted 2009) [#10]

Nice piece of code man. *Ross steals*

REJLA

(Posted 2009) [#11]

Ok, I'm not writing a lot of code but the general idea is this:

consider that A1, A2, and A3 are the vector coordinates of the 3 edges of one of the triangles.
you can find the normal vector 'N' of the triangle by
A12=A2-A1
A13=A3-A1
N=the cross product of A12 and A13

Now consider that B1,B2, and B3 are the vector coordinates of the 3 edges of the second triangle.

the triangles are coplanar if all the vectors going from one of the edges of the first triangle to the edges of the second triangle area perpendicular to this normal triangle, so:
A1B1=B1-A1
A1B2=B2-A1
A1B3=B3-A1

the two triangles are coplanar if(A1B1*N=0 and A1B2*N=0 and A1B3*N=0)

the operation '*' indicates the dot product of two vectors

I hope this helps.

Warner

(Posted 2009) [#12]

Thanks! I'm on it, hopefully I can work something out now.