[Кирпи4]

Извинтюляюсь за можно сказать некропост, но у меня хорошие новости.
Вот хороший код отсечения, но минус один - окклюдеры должны быть выпуклыми. А так всё замечательно работает, отсекает как надо.

Graphics3D 800,600
SetBuffer BackBuffer() 

;WireFrame True

; Types and variables for Edgelist
Type Edge
Field A,B
Field Surf
Field Tri1	 ; The triangle the edge belongs To
Field Tri2	 ; The adjacent triangle, if one exist
Field X1,Y1,X2,Y2
Field Visible
Field PlaneDist#	; The edgelist also contains the planes
Field PlaneNX#
Field PlaneNY#
Field PlaneNZ#
Field Parent
End Type

Type vector
Field x#
Field y#
Field z#
End Type
Global CProd.vector=New vector
Global DProd#

Type Occluder
Field Mesh
Field ID
End Type

Type Entity
Field Entity
Field Occluded
Field Radius#
End Type

box = CreateMesh()
surf=CreateSurface(box)
v0=AddVertex(surf,-1,1,1)
v1=AddVertex(surf,1,1,1)
v2=AddVertex(surf,1,1,-1)
v3=AddVertex(surf,-1,1,-1)
v4=AddVertex(surf,-1,-1,1)
v5=AddVertex(surf,1,-1,1)
v6=AddVertex(surf,1,-1,-1)
v7=AddVertex(surf,-1,-1,-1)
AddTriangle(surf,v0,v1,v3)
AddTriangle(surf,v1,v2,v3)
AddTriangle(surf,v4,v7,v5)
AddTriangle(surf,v7,v6,v5)
AddTriangle(surf,v3,v2,v7)
AddTriangle(surf,v2,v6,v7)
AddTriangle(surf,v4,v1,v0)
AddTriangle(surf,v4,v5,v1)
AddTriangle(surf,v2,v1,v6)
AddTriangle(surf,v1,v5,v6)
AddTriangle(surf,v0,v3,v4)
AddTriangle(surf,v3,v7,v4)
;
HideEntity box 

; Cams & Meshes
camera = CreateCamera()
PositionEntity camera,0,0,-5
CameraClsColor camera,150,150,220 

Global EdgeList.Edge
; Create occluder
Global OccludeList.Occluder
OccludeList.Occluder = New Occluder
OccludeList\ID = 1
OccludeList\Mesh = CopyEntity(box) 
PositionEntity OccludeList\mesh,-6,0,0
EntityAlpha OccludeList\mesh,0.8 

OccludeList.Occluder = New Occluder
OccludeList\ID = 2
OccludeList\Mesh = CopyEntity(box) 
PositionEntity OccludeList\mesh,-3,0,0
EntityAlpha OccludeList\mesh,0.8 

OccludeList.Occluder = New Occluder
OccludeList\ID = 3
OccludeList\Mesh = CopyEntity(box) 
PositionEntity OccludeList\mesh,0,0,0
EntityAlpha OccludeList\mesh,0.8 

OccludeList.Occluder = New Occluder
OccludeList\ID = 4
OccludeList\Mesh = CopyEntity(box) 
PositionEntity OccludeList\mesh,3,0,0
EntityAlpha OccludeList\mesh,0.8 

OccludeList.Occluder = New Occluder
OccludeList\ID = 5
OccludeList\Mesh = CopyEntity(box) 
PositionEntity OccludeList\mesh,6,0,0
EntityAlpha OccludeList\mesh,0.8 


; Create ordinary objects
Global EntityList.Entity

For v=0 To 50
EntityList.Entity = New Entity
EntityList\Entity = CreateSphere(16)
EntityList\Radius# = 0.5
PositionEntity EntityList\Entity,Rnd(-5,5),Rnd(-5,5),Rnd(100,5)
EntityColor EntityList\Entity,Rnd(50,255),Rnd(50,255),Rnd(50,255)
Next 

CenterPivot=CreatePivot()
light = CreateLight()
PositionEntity light,15,10,-15 
PointEntity light,CenterPivot

; Build the Edgelists
For OccludeList.Occluder = Each Occluder
BuildEdgeList OccludeList\ID,OccludeList\mesh
Next

; The mainloop
LastTime=MilliSecs()
Color 0,0,0
UseOcclusion=0

While Not KeyDown(1)
FrameCount=FrameCount+1

If KeyHit(57) Then
UseOcclusion=1-UseOcclusion

If UseOcclusion=0 Then
For EntityList.Entity = Each Entity
ShowEntity EntityList\Entity 
Next
EndIf

EndIf

;TurnEntity mesh,0,0.5,0

If KeyDown(200) Then
MoveEntity Camera,0,0.01,0 
EndIf	
If KeyDown(208) Then
MoveEntity Camera,0,-0.01,0 
EndIf	
If KeyDown(205) Then
MoveEntity Camera,0.01,0,0 
EndIf	
If KeyDown(203) Then
MoveEntity Camera,-0.01,0,0 
EndIf	
If KeyDown(201) Then
MoveEntity Camera,0,0,0.01 
EndIf	
If KeyDown(209) Then
MoveEntity Camera,0,0,-0.01 
EndIf	

RenderWorld

;Just for showing that the occluder doesn't need
;to be a static object
For OccludeList.Occluder = Each Occluder
TurnEntity OccludeList\Mesh,0,0.1,0 
Next


If UseOcclusion=1 Then
For EntityList.Entity = Each Entity
EntityList\Occluded=False
Next
For OccludeList.Occluder = Each Occluder
; Skip Updating the occluder if it is out of the view
If EntityInView(OccludeList\Mesh,Camera) Then
UpdateOccluderPlanes OccludeList\ID,OccludeList\Mesh,Camera
EndIf
Next

For EntityList.Entity = Each Entity
; Skip to check if entity already is out of the viewfrustum
If EntityInView(EntityList\Entity,Camera) Then
OccludeEntity(EntityList,Camera)
EndIf
Next

EndIf

TimeTaken=MilliSecs()-LastTime
If TimeTaken>=1000 Then
LastTime=MilliSecs()
FPS=FrameCount
FrameCount=0
EndIf

Text 0,10,"FPS:" + Str(FPS) 
If UseOcclusion=0 Then
Text 0,20,"Occlusion = " + "Off"
Else
Text 0,20,"Occlusion = " + "On"
EndIf
Text 0,30,"Rendered Tris:" + TrisRendered()
Text 0,40,"Press Space To Toggle Occlusion"


Flip False
Wend

End

; Functions

Function UpdateOccluderPlanes(OccID,occMesh,Cam)
; Loop through all Edges...
FirstRun=True
For EdgeList.Edge = Each Edge

If EdgeList\Parent=OccID Then

TriVis1 = TriVisible(Cam,occMesh,EdgeList\surf,EdgeList\Tri1)
TriVis2 = TriVisible(Cam,occMesh,EdgeList\surf,EdgeList\Tri2)

If TriVis1 Xor TriVis2 = True Then ; draw edge only if one triangle is visible and the other is hidden

x#=VertexX#(EdgeList\Surf,EdgeList\A)
y#=VertexY#(EdgeList\Surf,EdgeList\A)
z#=VertexZ#(EdgeList\Surf,EdgeList\A)
TFormPoint x#,y#,z#,occMesh,0
CameraProject Cam,TFormedX#(),TFormedY#(),TFormedZ#()	
EdgeList\X1=ProjectedX()
EdgeList\Y1=ProjectedY()

If FirstRun=True Then
MaxX=EdgeList\X1:MinX=EdgeList\X1
MaxY=EdgeList\Y1:MinY=EdgeList\Y1
FirstRun=False
Else
If EdgeList\X1>MaxX Then MaxX=EdgeList\X1
If EdgeList\X1<MinX Then MinX=EdgeList\X1
If EdgeList\Y1>MaxY Then MaxY=EdgeList\Y1
If EdgeList\Y1<MinY Then MinY=EdgeList\Y1
EndIf

x#=VertexX#(EdgeList\Surf,EdgeList\B)
y#=VertexY#(EdgeList\Surf,EdgeList\B)
z#=VertexZ#(EdgeList\Surf,EdgeList\B)
TFormPoint x#,y#,z#,occMesh,0
CameraProject Cam,TFormedX#(),TFormedY#(),TFormedZ#()	
EdgeList\X2=ProjectedX()
EdgeList\Y2=ProjectedY()

If EdgeList\X2>MaxX Then MaxX=EdgeList\X2
If EdgeList\X2<MinX Then MinX=EdgeList\X2
If EdgeList\Y2>MaxY Then MaxY=EdgeList\Y2
If EdgeList\Y2<MinY Then MinY=EdgeList\Y2

EdgeList\Visible=True
;Line EdgeList\X1,EdgeList\Y1,EdgeList\X2,EdgeList\Y2
Else
EdgeList\Visible=False
EndIf
EndIf
Next

; Calculate Midpoint
MidPointX=(MinX+MaxX)/2
MidPointY=(MinY+MaxY)/2

; Make sure every edge is in clockwise order, if not, swap the edges vertices
For EdgeList.Edge = Each Edge
If EdgeList\Parent=OccID Then
If EdgeList\Visible=True Then

If TriArea(EdgeList\X1,EdgeList\Y1,EdgeList\X2,EdgeList\Y2,MidPointX,MidPointY)<0 Then
TempHoldVertex=EdgeList\A
TempHoldX=EdgeList\X1
TempHoldY=EdgeList\Y1

EdgeList\A=EdgeList\B
EdgeList\X1=EdgeList\X2
EdgeList\Y1=EdgeList\Y2
EdgeList\B=TempHoldVertex
EdgeList\X2=TempHoldX
EdgeList\Y2=TempHoldY
EndIf

; Now calculate plane...
TFormPoint VertexX#(EdgeList\Surf,EdgeList\A),VertexY#(EdgeList\Surf,EdgeList\A),VertexZ#(EdgeList\Surf,EdgeList\A),occMesh,0
Vec1x#=EntityX#(Cam)-TFormedX#()
Vec1y#=EntityY#(Cam)-TFormedY#()
Vec1z#=EntityZ#(Cam)-TFormedZ#()
TFormPoint VertexX#(EdgeList\Surf,EdgeList\B),VertexY#(EdgeList\Surf,EdgeList\B),VertexZ#(EdgeList\Surf,EdgeList\B),occMesh,0
Vec2x#=EntityX#(Cam)-TFormedX#()
Vec2y#=EntityY#(Cam)-TFormedY#()
Vec2z#=EntityZ#(Cam)-TFormedZ#()
;	CrossProduct Vec1x#,Vec1y#,Vec1z#,Vec2x#,Vec2y#,Vec2z# 
Cpx#=(Vec1y#*Vec2z#)-(Vec1z#*Vec2y#)
Cpy#=(Vec1z#*Vec2x#)-(Vec1x#*Vec2z#)
Cpz#=(Vec1x#*Vec2y#)-(Vec1y#*Vec2x#)
;Normalize
TempDist#= Sqr(Cpx#*Cpx# + Cpy#*Cpy# + Cpz#*Cpz#)
Cpx#=Cpx#/TempDist#
Cpy#=Cpy#/TempDist#
Cpz#=Cpz#/TempDist#
EdgeList\PlaneNX#=Cpx#
EdgeList\PlaneNY#=Cpy#
EdgeList\PlaneNZ#=Cpz#

;EdgeList1\PlaneDist#=DotProduct(TFormedX#(),TFormedY#(),TFormedZ#(),CProd\x#,CProd\y#,CProd\z#)
EdgeList\PlaneDist#=((TFormedX#()*Cpx#)+(TFormedY#()*Cpy#)+(TFormedZ#()*Cpz#))

EndIf
EndIf
Next

End Function

Function OccludeEntity(CurrentEntity.Entity,Camera)
; Now check if object is occluded or not...

If CurrentEntity\Occluded=False Then ; If entity already is occluded, then skip this...

For OccludeList.Occluder = Each Occluder
; Skip the occluder if it's out of the viewfrustum
If EntityInView(OccludeList\Mesh,Camera)=False Then Goto SkipThisOccluder
EntityHidden=True
For EdgeList.Edge = Each Edge
If OccludeList\ID = EdgeList\Parent Then
If EdgeList\Visible=True Then
If ((EdgeList\PlaneNX#*EntityX#(CurrentEntity\Entity)+EdgeList\PlaneNY#*EntityY#(CurrentEntity\Entity)+EdgeList\PlaneNZ#*EntityZ#(CurrentEntity\Entity))-EdgeList\PlaneDist#+EntityList\Radius#)>-CurrentEntity\Radius# Then
EntityHidden=False
EndIf
EndIf
EndIf
Next

If EntityHidden=True Then
CurrentEntity\Occluded=True
;EntityColor EntityList\Entity,255,0,0
HideEntity CurrentEntity\Entity 
Exit
Else
CurrentEntity\Occluded=False
ShowEntity CurrentEntity\Entity
EndIf
.SkipThisOccluder
Next

EndIf
End Function


; Function for filling the edgelist with edges
Function BuildEdgeList(OccID,Entity)
For Surfnr = 1 To CountSurfaces(Entity)
Surf=GetSurface(Entity,Surfnr)
For TriNr = 0 To CountTriangles(Surf)-1
EdgeA=TriangleVertex(Surf,Trinr,0)
EdgeB=TriangleVertex(Surf,Trinr,1)
AddEdge(OccID,Surf,TriNr,EdgeA,EdgeB)

EdgeA=TriangleVertex(Surf,Trinr,1)
EdgeB=TriangleVertex(Surf,Trinr,2)
AddEdge(OccID,Surf,TriNr,EdgeA,EdgeB)

EdgeA=TriangleVertex(Surf,Trinr,2)
EdgeB=TriangleVertex(Surf,Trinr,0)
AddEdge(OccID,Surf,TriNr,EdgeA,EdgeB)
Next
Next


End Function

Function AddEdge(OccID,Surf,TriNr,A,B)
EdgeFound = False
For EdgeList.Edge = Each Edge
If OccID = EdgeList\Parent Then	
; Check if the given edge already exist in the list
; In that case just supply the triangle index
; The mesh must have shared vertices
If ((EdgeList\A = A And EdgeList\B = B) Or (EdgeList\A = B And EdgeList\B = A)) Then
EdgeFound = True
EdgeList\Tri2=TriNr
Exit
EndIf
EndIf
Next 

; If the edge wasn't found, add it
If EdgeFound = False Then
EdgeList.Edge = New Edge
EdgeList\A=A
EdgeList\B=B
EdgeList\Surf=Surf
EdgeList\Tri1=TriNr
EdgeList\Tri2=-1
EdgeList\Parent=OccID
EndIf

End Function


Function TriVisible(Camera,Entity,Surface,Triangle)

If Triangle=-1 Then
; This means that the edge has no adjacent triangle
; If this occurs the mesh isn't solid(closed) 
Return False
EndIf

ax#=VertexX#(Surface,TriangleVertex(Surface,Triangle,0))
ay#=VertexY#(Surface,TriangleVertex(Surface,Triangle,0))
az#=VertexZ#(Surface,TriangleVertex(Surface,Triangle,0))
bx#=VertexX#(Surface,TriangleVertex(Surface,Triangle,1))
by#=VertexY#(Surface,TriangleVertex(Surface,Triangle,1))
bz#=VertexZ#(Surface,TriangleVertex(Surface,Triangle,1))
cx#=VertexX#(Surface,TriangleVertex(Surface,Triangle,2))
cy#=VertexY#(Surface,TriangleVertex(Surface,Triangle,2))
cz#=VertexZ#(Surface,TriangleVertex(Surface,Triangle,2))

; Get vectors
v1x#=ax#-bx#
v1y#=ay#-by#
v1z#=az#-bz#
v2x#=ax#-cx#
v2y#=ay#-cy#
v2z#=az#-cz#

; Get crossproduct
cpx#=(v1y#*v2z#)-(v1z#*v2y#)
cpy#=(v1z#*v2x#)-(v1x#*v2z#)
cpz#=(v1x#*v2y#)-(v1y#*v2x#)

; Transform vector according to entity and normalize
TFormNormal cpx#,cpy#,cpz#,Entity,0
cpx#=TFormedX#()
cpy#=TFormedY#()
cpz#=TFormedZ#()

; Now we got the triangles normal
; Take the DotProduct from above normal and a distance vector
; from the camera and one of the triangles vertices
TFormPoint ax#,ay#,az#,Entity,0
camvecx#=EntityX#(Camera)-TFormedX#()
camvecy#=EntityY#(Camera)-TFormedY#()
camvecz#=EntityZ#(Camera)-TFormedZ#()

dp#=((camvecx#*cpx#)+(camvecy#*cpy#)+(camvecz#*cpz#))

If dp#>0 Then
Return True
Else
Return False
EndIf

End Function

Function TriArea(X1,Y1,X2,Y2,X3,Y3)
D = X1*Y2 + X2*Y3 + X3*Y1 - X1*Y3 - X2*Y1 - X3*Y2
Return D
End Function

;
;Cross and DotProduct functions
Function CrossProduct(x1#,y1#,z1#,x2#,y2#,z2#)
CProd\x#=(y1#*z2#)-(z1#*y2#)
CProd\y#=(z1#*x2#)-(x1#*z2#)
CProd\z#=(x1#*y2#)-(y1#*x2#)
End Function
Function DotProduct#(x1#,y1#,z1#,x2#,y2#,z2#)
DProd=((x1*x2)+(y1*y2)+(z1*z2))
Return DProd
End Function