Ultimate Tricky Mesh Question of the Week
Blitz3D Forums/Blitz3D Programming/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) |
| ||
| 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) 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. 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. 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
|
   |