Ultimate Tricky Mesh Question of the Week

Ok, here's a tricky one for all you math / mesh wizards out there. My brain has been in a continuous loop for the past couple of days trying to sort this out, but I don't think my math is up to the task. I'm hoping someone here will be able to help me out or at least steer me in the right direction!

Here's the problem. I have 2 or more simple meshes that I'm creating on the fly. They only need to be flat triangles with no real 3d depth. As I do this, or after I do this, I need to determine whether or not they overlap, and if they do, I need to create a separate mesh that exactly matches their intersection. (this is so that I can handle that intersected area differently visually and computationally).

I've considered 2 possible approaches to this, but both have their difficulties and challenges.

1. The first approach i've considered is giving the meshes a little depth and then linepicking extensively from where the meshes are originating from to try to find the points where it collides with the other mesh, record these and then try to build a mesh out of them. 2 things make this really difficult -- I have to also linepick backwards towards the original object to find the end of the intersection, and i think that it will be very challenging to build the mesh correctly once i've found the intersection points (not sure how to organize all those points so that i can connect them right).

2. The second approach i've considered is to try to do some old-fashioned 2d wizardry, rendering the scene to image buffers and trying to figure out the intersections based on colors. If I were to render the scene top-down I could pretty easily show the intersections in a different color (by making the meshes additive), but once i've done that, it seems like i'll be stuck doing a whole mess of "readpixelfast"s which will be slow. Once I finished that, I could presumably place the result in a texture and give the UV coords to make it overlay the meshes correctly, though, which would be pretty simple.

So does anyone have suggestions for either approach?

If I go with the mesh way, is there a way to evaluate these intersections without all the linepicking? (i guess with straight up math?) Or is there some other method that I'm missing?

If I go with the second method, is there a way that I could evaluate the colors of the image / intersecting areas without reading every pixel to test its color? Maybe using images as textures overlaying one another? I am afraid I am out of my depth :)

Ok, I think I'll shut up now. Please let me know if you have any questions or suggestions!

cheers,
roland

So, these triangles exist on the same plane so we can treat them as 2D (e.g. ignore the Z coords of the verts)?

When an intersection occurs, do you want to leave the original triangles as they are, or do you want to 'cut' the intersection out of them?

Do you need to check for intersection between more than 2 triangles, ever?

I'd definately go the math route for this. You could basically use a line intersection function to determine all points of intersection between the edges of the 2 tris - these will be your new vertex coords.

There's actually going to be more to it than that as the intersection may be a polygon with more than 3 sides. Look at The Star of David for a worse case senario. This'll require some intelligent triangulation of the intersection poly. Hmm, actually, the actual triangulation wont be that difficult.

Just thinking out loud, here. :P

Let me see if I can expand a little to give you a better idea of the situation.

The meshes all exist on the same plane, so you can treat them as 2d. They are made up of many triangles, though, not just one. To make matters even worse, there is the possibility of having to check between more than 2 meshes as well -- it is possible that 3 or more meshes may intersect at any given point.

Here's a diagram that might help to explain what this looks like... I can post some code later if that would help test as well. in this diagram, the green dots represent the origin of the meshes that are being generated -- these can be rotated and the triangles (shown by white lines) are cast out from the origin to a set distance at the angle specified.

In this diagram, there is a red mesh and a blue mesh, and their intersection is shown as magenta. I outlined the intersection just to make it more clear what area would need to be treated differently.



To answer your other question, big10p, I don't think it matters if the original triangles are left or not -- i will probably have the intersected mesh obscure them either way.

Thanks for your help -- and keep the questions coming :)

cheers,
roland

Hello.

Me not much of 3d wiz, but think aloud sometimes. Could you not break the triangles into many little triangles and do a set of collisions based on those? Hope you get what I'm getting at...?

Goodbye.

Hey SoggyP -- thanks for the reply!

I thought about doing this last night while i was lying awake ruminating on the problem. It seems like it might be a good idea to try it out, especially if i have a faster collision interface, like ColDet.

My only concern is that it would not be a high enough resolution to preserve the appearance of the actual intersection. That's the unfortunate side-effect of using simple geometric shapes -- it can be pretty obvious when they aren't exact.

I do like this idea, though. I wonder what the best method of checking each sub-triangle would be?

You could probably adapt (simplify) my mesh clipping code to solve this (click on my profile to access my code archive entries).

It may also be a good idea to have a hidden, proxy mesh attached to each entity - i.e. a single triangle that represents the outer edges. You could then chop one of the proxy meshes up, using the edges of all the other meshes that intersect with it.

Why do your 'things' have to comprise many triangles?

Is this for some kind of light effect?

Hi again big10p, and thanks for the heads up on your clipping code --- i'll go check it out and see what i can make of it...

you're absolutely right -- this is for a 2d lighting effect. I evaluate each segment with linepicks to check for intersections, and limit the segment to the intersection to simulate shadowing inside the light ray. That portion of the code works really well, but makes this portion much more difficult.

Woa, that code is seriously badass. Nice work!!!

I have some ideas for using it, but it's going to take some time for me to figure out exactly how to use it right. I'm thinking that if I use the clipping function to slice up every angle that is important, I'll be able to achieve the effect that I'm looking for.

I'm not sure:

a) i'll be able to keep track of all the sliced off meshes (especially as I'll have to clip each operation twice to get each half separately)

and

b) it will be fast enough... even with really simple meshes (~ 20 -30 tris), i wonder if it will be able to do as many as 100 or 200 clips per frame? seems like it would be asking a lot to do that and still achieve 60fps.

But it's definitely worth exploring. It might provide some other options once I start that I'm not seeing as well... if you have any suggestions for using it properly that i'm not thinking of, i'd love to hear 'em!

thanks,

roland

Fredborg has some nice code to fill in an outline with tri's. If you could get all the intersect points, you could easily make the mesh using this code.

Another way you could do this.

It's similar to a lightmap, and may work better than the triangle idea, as you'll be able to blend the texture with the texture of the ground below. Create a texture to cover the area of the ground. Even if it's just the area in view. Then, each frame, point the camera from above, render ONLY the light polygons onto a black backround, or grey (128,128,128) depending on if you want thedark parts to darken, or remain a neutral colour. Then, COPYRECT this onto your texture used to cover the ground area.

If you do this every frame, you'll probably need to use the VRAM flag on the texture your copying to, you won't need to worry about the amount of light polygons, or the intersection. TIP: when rendering, you could try and change the camera view distance to just what you need to render the light polygons, giving you less chance of having overlapping issues.

I might give this a try when i get home to show you what i mean. It's pretty straight forward though :o)

As I understand it, you won't need the sliced off sections: as it stands, the code clips a copy of a mesh - the original mesh remains unaltered.

Having said that, as you need to perform more than one clip on a mesh, I'd optimize the code so that it actually clips the mesh passed in - this'll allow you to remove the initial code that copies the mesh. Instead, make a copy of the mesh yourself, before performing all the required clips on it.

A further optimization would be to use a proxy mesh, as I mentioned in my last post. This would mean the initial mesh to clip would be a single triangle, instead of many, as used in your main meshes.

There should be other optimizations to be had, too. For example, as these are basically 2D meshes, a constant can be used for the vertex coords of the unused dimension.

Well, I guess only testing will tell. :) However, I think it should be fast enough, given the optimizations I mention above. As I see it, you only need to do 3 clips when 2 meshes intersect; 6 clips when 3 intersect, etc. Also, some of those clips may actually 'miss', improving the speed of the operation.

Hey Ross, that piece of code from FredBorg sounds really useful -- i'll see if i can find it.

I've considered doing the lightmapping type of routine that you've described here, and while I think it would work fine for the simple light effect, I don't think that it will be sufficient to satisfy the requirements that I have for the handling of the intersected areas. I'm afraid I need to actually outline each color area (including the intersected areas) with a stronger outline of its color. I can't figure out how I could handle this type of effect on a texture.

big10p -- i'm wondering if it would be simpler to use some more straighforward line-line intersection equations to determine intersection points rather than to clip the meshes? this of course means that i would have to create the tris from the intersected portions, but might be simpler... I was messing with the clipping code last night and couldn't quite figure out how to set the plane in the right place using only one positioning variable (y)... i guess i need to take some more time trying to wrap my head around that.

If anyone has ever seen a simple function to take 2 triangles and extract their overlapping portions, i would love to see that. I think that's what i am going to focus on next using the equation for finding an intersection on 2 lines.

ok, major progress here (i think). I've implemented some really useful things from the code archives, and I am SOOOO close to getting this to be exactly as it should be, at least for really simple cases.

Here's how it's working now:

For each triangles, I evaluate all of the potential intersections of each segment with the segments of the other triangle. This ends up being 15 cases, and works splendidly. Each of these intersections are exactly as they should be.

Now that I have these intersections, I need to mesh them. Therein lies the trouble. They are evaluated arbitrarily, and therefore I cannot intelligently mesh them. In the code posted below I'm trying to use FredBorg's awesome tesselation code to accomplish this, but it isn't working correctly.

Any ideas how to proceed? There are a couple of paths that would seem to solve these problems. I can:

1. figure out how to check the intersections in the correct order to order the verts in the proper fashion so that they form the right tris,

2. implement a new tesselation algo to try to make tris out of these arbitrarily arranged verts

3. figure out why it's not working right with FredBorg's code

any ideas?

thanks,
roland

here's my working code. I apologize for the extra stuff in here (camera projections and 2d ops to draw the interesections -- these no longer work because they are before the updateworld() and renderworld() but i've been too lazy to take them out).

Graphics3D 800,600,0,2
SeedRnd MilliSecs()

Const VERTEXLIMIT	= 999

Const DEGENERATE	= 0
Const CONCAVE		= 1
Const CONVEX		= 2

Type tessVert
	Field x#,y#,z#,u#,v#,n
End Type

Type tessSurf
	Field v0.tessVert[VERTEXLIMIT]
	Field v1.tessVert[VERTEXLIMIT]
	Field v2.tessVert[VERTEXLIMIT]
	Field n_tris
End Type

Dim tsv.tessVert(0)

Global mE0x#,mE0y#,mE0z#	
Global mE1x#,mE1y#,mE1z#				
Global mNx#,mNy#,mNz#,mA#
Global tessNx#,tessNy#,tessNz#


pivot = CreatePivot()
cam = CreateCamera(pivot)
PositionEntity cam,0,0,30
PointEntity cam,pivot

tri1 = CreateMesh()
tri1surf = CreateSurface(tri1)
tri1angle# = 45
tri1x# = -15
tri1y# = 10
tri1width# = 15
tri1length# = 20
EntityFX tri1,2+32+1

tri2 = CreateMesh()
tri2surf = CreateSurface(tri2)
tri2angle# = -45
tri2x# = 15
tri2y# = 10
tri2width# = 15
tri2length# = 20

EntityColor tri2,150,150,150

Global intersectx#
Global intersecty#


mesh = CreateMesh()
surf = CreateSurface(mesh)
EntityColor mesh,0,0,255


While Not KeyHit(1)

ClearSurface tri1surf

	If KeyHit(57)
		wire = Not wire
		WireFrame wire
	End If


If KeyDown(203) Then tri1x = tri1x+.2
If KeyDown(205) Then tri1x = tri1x-.2
If KeyDown(200) Then tri1y = tri1y+.2
If KeyDown(208) Then tri1y = tri1y-.2

If KeyDown(30) Then tri1angle = tri1angle+1
If KeyDown(44) Then tri1angle = tri1angle-1


;update first triangle
;ClearSurface tri1surf

dx# = Sin(tri1angle-tri1width)*tri1length
dy# = -Cos(tri1angle-tri1width)*tri1length

dx2# = Sin(tri1angle+tri1width)*tri1length
dy2# = -Cos(tri1angle+tri1width)*tri1length

tri1v0 = AddVertex(tri1surf,tri1x,tri1y,0)
tri1v1 = AddVertex(tri1surf,tri1x+dx,tri1y+dy,0)
tri1v2 = AddVertex(tri1surf,tri1x+dx2,tri1y+dy2,0)


VertexColor tri1surf,tri1v0,255,0,0,.5
VertexColor tri1surf,tri1v1,0,255,0,.5
VertexColor tri1surf,tri1v2,0,0,255,.5

AddTriangle tri1surf,tri1v0,tri1v1,tri1v2

UpdateNormals tri1

;update second triangle
ClearSurface tri2surf

t2dx# = Sin(tri2angle-tri2width)*tri2length
t2dy# = -Cos(tri2angle-tri2width)*tri2length

t2dx2# = Sin(tri2angle+tri2width)*tri2length
t2dy2# = -Cos(tri2angle+tri2width)*tri2length

tri2v0 = AddVertex(tri2surf,tri2x,tri2y,0)
tri2v1 = AddVertex(tri2surf,tri2x+t2dx,tri2y+t2dy,0)
tri2v2 = AddVertex(tri2surf,tri2x+t2dx2,tri2y+t2dy2,0)


AddTriangle tri2surf,tri2v0,tri2v1,tri2v2

UpdateNormals tri2


;all necessary checks to determine triangle to triangle intersection points

;t1 rightside against t2 rightside
If linesIntersect(tri1x,tri1y,tri1x+dx,tri1y+dy,tri2x,tri2y,tri2x+t2dx,tri2y+t2dy) = True
	CameraProject cam,intersectx,intersecty,0
	Oval ProjectedX(),ProjectedY(),3,3

	tess_AddVert(intersectx,intersecty,.5)

EndIf

;t1 leftside against t2 rightside
If linesIntersect(tri1x,tri1y,tri1x+dx2,tri1y+dy2,tri2x,tri2y,tri2x+t2dx,tri2y+t2dy) = True
	CameraProject cam,intersectx,intersecty,0
	Oval ProjectedX(),ProjectedY(),3,3

	tess_AddVert(intersectx,intersecty,.5)
EndIf

;t1 leftside against t2 leftside
If linesIntersect(tri1x,tri1y,tri1x+dx2,tri1y+dy2,tri2x,tri2y,tri2x+t2dx2,tri2y+t2dy2) = True
	CameraProject cam,intersectx,intersecty,0
	Oval ProjectedX(),ProjectedY(),3,3

	tess_AddVert(intersectx,intersecty,.5)
EndIf

;t1 rightside against t2 leftside
If linesIntersect(tri1x,tri1y,tri1x+dx,tri1y+dy,tri2x,tri2y,tri2x+t2dx2,tri2y+t2dy2) = True
	CameraProject cam,intersectx,intersecty,0
	Oval ProjectedX(),ProjectedY(),3,3

	tess_AddVert(intersectx,intersecty,.5)
EndIf

;t1 end against t2 end
If linesIntersect(tri1x+dx2,tri1y+dy2,tri1x+dx,tri1y+dy,tri2x+t2dx,tri2y+t2dy,tri2x+t2dx2,tri2y+t2dy2) = True
	CameraProject cam,intersectx,intersecty,0
	Oval ProjectedX(),ProjectedY(),3,3

	tess_AddVert(intersectx,intersecty,.5)
EndIf

;t1 end against t2 rightside
If linesIntersect(tri1x+dx2,tri1y+dy2,tri1x+dx,tri1y+dy,tri2x,tri2y,tri2x+t2dx,tri2y+t2dy) = True
	CameraProject cam,intersectx,intersecty,0
	Oval ProjectedX(),ProjectedY(),3,3

	tess_AddVert(intersectx,intersecty,.5)
EndIf

;t1 end against t2 leftside
If linesIntersect(tri1x+dx2,tri1y+dy2,tri1x+dx,tri1y+dy,tri2x,tri2y,tri2x+t2dx2,tri2y+t2dy2) = True
	CameraProject cam,intersectx,intersecty,0
	Oval ProjectedX(),ProjectedY(),3,3

	tess_AddVert(intersectx,intersecty,.5)
EndIf

;t1 rightside against t2 end
If linesIntersect(tri1x,tri1y,tri1x+dx,tri1y+dy,tri2x+t2dx,tri2y+t2dy,tri2x+t2dx2,tri2y+t2dy2) = True
	CameraProject cam,intersectx,intersecty,0
	Oval ProjectedX(),ProjectedY(),3,3

	tess_AddVert(intersectx,intersecty,.5)
EndIf

;t1 leftside against t2 end
If linesIntersect(tri1x,tri1y,tri1x+dx2,tri1y+dy2,tri2x+t2dx,tri2y+t2dy,tri2x+t2dx2,tri2y+t2dy2) = True
	CameraProject cam,intersectx,intersecty,0
	Oval ProjectedX(),ProjectedY(),3,3

	tess_AddVert(intersectx,intersecty,.5)
EndIf


;test if tri1's verts are inside tri2:
If InTriangle(tri1x,tri1y,tri2x,tri2y,tri2x+t2dx,tri2y+t2dy,tri2x+t2dx2,tri2y+t2dy2) = True
	CameraProject cam,tri1x,tri1y,0
	Oval ProjectedX(),ProjectedY(),3,3

	tess_AddVert(tri1x,tri1y,.5)
EndIf

If InTriangle(tri1x+dx,tri1y+dy,tri2x,tri2y,tri2x+t2dx,tri2y+t2dy,tri2x+t2dx2,tri2y+t2dy2) = True
	CameraProject cam,tri1x+dx,tri1y+dy,0
	Oval ProjectedX(),ProjectedY(),3,3

	tess_AddVert(tri1x+dx,tri1y+dy,.5)
EndIf

If InTriangle(tri1x+dx2,tri1y+dy2,tri2x,tri2y,tri2x+t2dx,tri2y+t2dy,tri2x+t2dx2,tri2y+t2dy2) = True
	CameraProject cam,tri1x+dx2,tri1y+dy2,0
	Oval ProjectedX(),ProjectedY(),3,3

	tess_AddVert(tri1x+dx2,tri1y+dy2,.5)
EndIf


;test if tri2's verts are inside tri1:
If InTriangle(tri2x,tri2y,tri1x,tri1y,tri1x+dx,tri1y+dy,tri1x+dx2,tri1y+dy2) = True
	CameraProject cam,tri2x,tri2y,0
	Oval ProjectedX(),ProjectedY(),3,3

	tess_AddVert(tri2x,tri2y,.5)
EndIf

If InTriangle(tri2x+t2dx,tri2y+t2dy,tri1x,tri1y,tri1x+dx,tri1y+dy,tri1x+dx2,tri1y+dy2) = True
	CameraProject cam,tri2x+t2dx,tri2y+t2dy,0
	Oval ProjectedX(),ProjectedY(),3,3

	tess_AddVert(tri2x+t2dx,tri2y+t2dy,.5)
EndIf

If InTriangle(tri2x+t2dx2,tri2y+t2dy2,tri1x,tri1y,tri1x+dx,tri1y+dy,tri1x+dx2,tri1y+dy2) = True
	CameraProject cam,tri2x+t2dx2,tri2y+t2dy2,0
	Oval ProjectedX(),ProjectedY(),3,3

	tess_AddVert(tri2x+t2dx2,tri2y+t2dy2,.5)
EndIf



		tris = tess_Triangulate()
	
		;
		; Build a real 3D surface from the tessSurf
		ClearSurface surf
		For tessVert.TessVert = Each TessVert
			AddVertex surf,tessVert\x,tessVert\y,tessVert\z
		Next
		tessSurf.TessSurf = First TessSurf
		For t = 0 To tessSurf\n_tris-1
			AddTriangle surf,tessSurf\v0[t]\n,tessSurf\v1[t]\n,tessSurf\v2[t]\n
		Next		
		UpdateNormals mesh
		
		;
		; Clean up :)
		tess_Clean()

	FreeEntity meshcopy
	meshcopy = CopyMesh(mesh)
	EntityColor meshcopy,0,0,255
	FlipMesh meshcopy
	

UpdateWorld()
RenderWorld()

;Text 320,  0,"Tris - "+tris+" | Time - "+ms+" ms",True


Flip



Wend



Function linesIntersect(x1#,y1#, x2#,y2#, x3#,y3#, x4#,y4#)

	numeratorA#  = (x4-x3)*(y1-y3)-(y4-y3)*(x1-x3)
	numeratorB#  = (x2-x1)*(y1-y3)-(y2-y1)*(x1-x3)
	denominator# = (y4-y3)*(x2-x1)-(x4-x3)*(y2-y1)

	If denominator = 0.0 Then
		Return False
	Else
		Ua# = numeratorA/denominator
		Ub# = numeratorB/denominator
		range1# = Ua >= 0.0 And Ua <= 1.0
		range2# = Ub >= 0.0 And Ub <= 1.0
		If range1 And range2 Then
			intersectX# = (x1 + Ua*(x2-x1))
			intersectY# = (y1 + Ua*(y2-y1))
			Return True
		Else
			Return False
		End If
    End If
End Function


;x0, y0 = point, others are triangle verts.
Function InTriangle(x0#,y0#,x1#,y1#,x2#,y2#,x3#,y3#)

	b0# =  (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)
	b1# = ((x2 - x0) * (y3 - y0) - (x3 - x0) * (y2 - y0)) / b0 
	If b1 <= 0 Then Return False
	
	b2# = ((x3 - x0) * (y1 - y0) - (x1 - x0) * (y3 - y0)) / b0
	If b2 <= 0 Then Return False

	b3# = ((x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0)) / b0 
	If b3 <= 0 Then Return False
	
	Return True
	
End Function


Function tess_Clean()
	
	Delete Each tessVert
	Delete Each tessSurf
	
End Function

Function tess_AddVert(x#,y#,z#=0.0,u#=0.0,v#=0.0)
	
	p.tessVert = Last tessVert
	If (p = Null)
		n = 0
	Else
		n = p\n+1
	End If
		
	p.tessVert = New tessVert
	p\x		= x
	p\y		= y
	p\z		= z
	p\u		= u
	p\v		= v
	p\n		= n
	
End Function

Function tess_ComputeNormal()

	tessNx# = 0.0
	tessNy# = 0.0
	tessNz# = 0.0

	For a.tessVert = Each tessVert
		b.tessVert = After a
		If b = Null Then Exit
		
        tessNx = tessNx + ((a\y - b\y ) * ( a\z + b\z))
        tessNy = tessNy + ((a\z - b\z ) * ( a\x + b\x))
        tessNz = tessNz + ((a\x - b\x ) * ( a\y + b\y))
	Next
	
	; Normalize it, not really nescessary
	; just nicer to look at :)
	Local d# = Sqr(tessNx*tessNx + tessNy*tessNy + tessNz*tessNz)
	If d>0.0
		tessNx = tessNx/d
		tessNy = tessNy/d
		tessNz = tessNz/d
	End If

End Function

Function tess_Triangulate()

	Local n_tris = 0
	Local n_verts = 0
	Local noErrors = True

	; Close the polygon, by adding the first vert after the last
	p.tessVert = First tessVert
	If Not (p=Null)
		tess_AddVert(p\x,p\y,p\z,p\u,p\v)
	End If

	; Get the normal of the entire polygon
	tess_ComputeNormal()

	; Count number of vertices
	n_verts = -1
	For p.tessVert = Each tessVert
		n_verts = n_verts + 1
	Next

	; Index the vertices
	Dim tsv(n_verts)
	n = 0
	For p.tessVert = Each tessVert
		tsv(n) = p
		n = n + 1
	Next

	; Prepare a TessSurf
	surf.TessSurf	= New TessSurf
	surf\n_tris		= 0

	; Now it gets funny
	While n_verts=>3 And noErrors = True
	
		noErrors = False
		
		i = 0
		j = 1
		k = 2
		While k<(n_verts+3)
			If n_verts=0 Then Exit

			ib = i Mod n_verts
			jb = j Mod n_verts
			kb = k Mod n_verts
		
			Select tess_TriangleArea(ib,jb,kb)
				Case CONVEX:
					If tess_IsAnyPointInside(ib,jb,kb,n_verts) 
						; Triangle is ok, but it cross another part of the polygon
						i = j
						j = k
						k = k + 1
					Else
						; Triangle is ok, so build it
						tess_AddTriangle(surf,ib,jb,kb)
						n_tris   = n_tris + 1
						n_verts  = tess_RemoveVertex(jb,n_verts)
						noErrors = True
					End If
					
				Case CONCAVE:
					; Triangle faces the wrong way
					i = j
					j = k
					k = k + 1
				
				Case DEGENERATE:
					; Bad triangle (zero area)
					n_verts  = tess_RemoveVertex(jb,n_verts)
					noErrors = True
		
			End Select
		Wend
		
	Wend
	
	Return n_tris
	
End Function

Function tess_TriangleArea(i,j,k)
	
	Local v0.tessVert = tsv(i)
	Local v1.tessVert = tsv(j)
	Local v2.tessVert = tsv(k)

	mE0x# = v0\x-v2\x
	mE0y# = v0\y-v2\y
	mE0z# = v0\z-v2\z
	
	mE1x# = v1\x-v2\x
	mE1y# = v1\y-v2\y
	mE1z# = v1\z-v2\z				

	mNx# = mE0y * mE1z - mE0z * mE1y
	mNy# = mE0z * mE1x - mE0x * mE1z
	mNz# = mE0x * mE1y - mE0y * mE1x
		
	mA# = (mNx*mNx + mNy*mNy + mNz*mNz)

	If Abs(mA) < 0.000001
		Return DEGENERATE
	End If
	
	If (mNx#*tessNx# + mNy#*tessNy# + mNz#*tessNz#) < 0.0
		Return CONCAVE
	Else
		Return CONVEX
	End If
	
End Function

Function tess_RemoveVertex(j,n_verts)

	For i = j+1 To n_verts
		tsv(i-1)=tsv(i)
	Next
	Return n_verts-1
		
End Function

Function tess_AddTriangle(surf.tessSurf,i,j,k)

	surf\v0[ surf\n_tris ] = tsv(i)
	surf\v1[ surf\n_tris ] = tsv(j)
	surf\v2[ surf\n_tris ] = tsv(k)
	surf\n_tris = surf\n_tris + 1
	Return surf\n_tris
	
End Function

Function tess_IsAnyPointInside(i,j,k,n_verts)

	For ip=0 To n_verts
    	If (ip<i) Or (ip>k)
			If tess_IsPointInside(tsv(ip),tsv(k))
				Return True
			End If
		End If
	Next

	Return False
	
End Function

Function tess_IsPointInside(point.tessVert,q2.tessVert)

	Local pmq2x# = point\x - q2\x
	Local pmq2y# = point\y - q2\y
	Local pmq2z# = point\z - q2\z		
	
	Local ntmpx# = 0.0
	Local ntmpy# = 0.0
	Local ntmpz# = 0.0
	
	Local b0# = 0.0
	Local b1# = 0.0

	ntmpx# = pmq2y * mE1z - pmq2z * mE1y
	ntmpy# = pmq2z * mE1x - pmq2x * mE1z
	ntmpz# = pmq2x * mE1y - pmq2y * mE1x
	b0# = mNx*ntmpx + mNy*ntmpy + mNz*ntmpz
	If b0 <= 0.0 Then Return False
	
	ntmpx# = mE0y * pmq2z - mE0z * pmq2y
	ntmpy# = mE0z * pmq2x - mE0x * pmq2z
	ntmpz# = mE0x * pmq2y - mE0y * pmq2x
	b1# = mNx*ntmpx + mNy*ntmpy + mNz*ntmpz
	If b1 <= 0.0 Then Return False
	
    If (mA-B0-B1)>0.0
		Return True
	Else
		Return False
	End If

End Function

Function tess_TriNormal(v0x#,v0y#,v0z#,v1x#,v1y#,v1z#,v2x#,v2y#,v2z#)
	
	ax#=v1x-v0x
	ay#=v1y-v0y
	az#=v1z-v0z
	
	bx#=v2x-v1x
	by#=v2y-v1y
	bz#=v2z-v1z
	
	tessNx#=(ay#*bz#)-(az#*by#)
	tessNy#=(az#*bx#)-(ax#*bz#)
	tessNz#=(ax#*by#)-(ay#*bx#)

End Function