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).
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