Leaf BSP Compiler

Übersicht

BlitzMax, BlitzMax NG

Codearchiv & Module

	Vertex Betreff: Leaf BSP Compiler	So, Jul 02, 2006 13:54 Antworten mit Zitat
Hi! Da ich eigentlich doch keine Lust habe, den Compiler weiter zu machen, gebe ich euch einfach mal den Sourcecode.... Alle Codes + Beispiele gibt es unter http://vertex.dreamfall.at/bsp...mpiler.zip Die Arbeit basiert auf: http://www.3dtechdev.com/tutor...trees.html http://www.3dtechdev.com/tutor...rytut.html(als Vortführung gedacht) TPlane.Intersect war das Schwirigste. Wie die Formel zu Stande kam: http://www.c-plusplus.de/forum...51582.html Code: [AUSKLAPPEN] [EINKLAPPEN] SuperStrict Framework BRL.StandardIO Import BRL.FileSystem Import BRL.LinkedList Import BRL.Math Const ZERO_TOLERANCE : Float = 0.0001 Const PLANE_FRONT : Int = 1 Const PLANE_BACK : Int = -1 Const PLANE_PLANAR : Int = 0 Const PLANE_SPLIT : Int = 2 Const SPLIT_FACTOR : Int = 10 Type TVector Field X : Float Field Y : Float Field Z : Float Method Set(X:Float, Y:Float, Z:Float) Self.X = X Self.Y = Y Self.Z = Z End Method Method Normalize(Vector:TVector) Local Length:Float, InvLength:Float Length = Vector.Length() If Length <> 0.0 Then InvLength = 1.0/Length Self.X = Vector.XInvLength Self.Y = Vector.YInvLength Self.Z = Vector.ZInvLength Else Self.X = 0.0 Self.Y = 1.0 Self.Z = 0.0 EndIf End Method Method Add(A:TVector, B:TVector) Self.X = A.X + B.X Self.Y = A.Y + B.Y Self.Z = A.Z + B.Z End Method Method Subtract(A:TVector, B:TVector) Self.X = A.X - B.X Self.Y = A.Y - B.Y Self.Z = A.Z - B.Z End Method Method Scale(Vector:TVector, Scalar:Float) Self.X = Vector.XScalar Self.Y = Vector.YScalar Self.Z = Vector.ZScalar End Method Method Cross(A:TVector, B:TVector) Self.X = A.YB.Z - A.ZB.Y Self.Y = A.ZB.X - A.XB.Z Self.Z = A.XB.Y - A.YB.X End Method Method Dot:Float(B:TVector) Return Self.XB.X + Self.YB.Y + Self.ZB.Z End Method Method Length:Float() Return Sqr(Self.XSelf.X + Self.YSelf.Y + Self.ZSelf.Z) End Method Method Read(Stream:TStream) Self.X = Stream.ReadFloat() Self.Y = Stream.ReadFloat() Self.Z = Stream.ReadFloat() End Method Method Copy(Vector:TVector) Self.X = Vector.X Self.Y = Vector.Y Self.Z = Vector.Z End Method Method Write(Stream:TStream) Stream.WriteFloat(Self.X) Stream.WriteFloat(Self.Y) Stream.WriteFloat(Self.Z) End Method End Type Type TLine Field Point1 : TVector Field Point2 : TVector Method New() Self.Point1 = New TVector Self.Point2 = New TVector End Method Method Intersect:Int(Plane:TPlane, Intersection:TVector) Local Dot1:Float, Dot2:Float, Time:Float Dot1 = Plane.Normal.Dot(Self.Point1) Dot2 = Plane.Normal.Dot(Self.Point2) If Abs(Dot2-Dot1) < ZERO_TOLERANCE Then Return False Time = (Plane.Distance - Dot1)/(Dot2 - Dot1) If Time < 0.0 Or Time > 1.0 Then Return False Intersection.Subtract(Self.Point2, Self.Point1) Intersection.Scale(Intersection, Time) Intersection.Add(Intersection, Self.Point1) Return True End Method Method Copy(Line:TLine) Self.Point1.Copy(Line.Point1) Self.Point2.Copy(Line.Point2) End Method End Type Type TTriangle Field Point1 : TVector Field Point2 : TVector Field Point3 : TVector Field Splitter : Int Method New() Self.Point1 = New TVector Self.Point2 = New TVector Self.Point3 = New TVector Self.Splitter = False End Method Method Side:Int(Plane:TPlane) Local Sides:Int[3], Index:Int Local FrontCount:Int, BackCount:Int, PlanarCount:Int, Normal:TVector Sides[0] = Plane.PointSide(Self.Point1) Sides[1] = Plane.PointSide(Self.Point2) Sides[2] = Plane.PointSide(Self.Point3) For Index = 0 To 2 If Sides[Index] = PLANE_FRONT Then FrontCount :+ 1 ElseIf Sides[Index] = PLANE_BACK Then BackCount :+ 1 Else PlanarCount :+ 1 FrontCount :+ 1 BackCount :+ 1 EndIf Next If PlanarCount = 3 Then Normal = New TVector Self.Normal(Normal) If Abs(Plane.Normal.Dot(Normal) - 1.0) < ZERO_TOLERANCE Then Return PLANE_FRONT Else Return PLANE_BACK EndIf ElseIf FrontCount = 3 Then Return PLANE_FRONT ElseIf BackCount = 3 Then Return PLANE_BACK Else Return PLANE_SPLIT EndIf End Method Method Split:Int(Plane:TPlane, FrontList:TList, BackList:TList) Local Sides:Int[3], Index:Int Local FrontCount:Int, BackCount:Int, PlanarCount:Int, Normal:TVector Local Edges:TLine[3], Splits:Int[3], Intersections:TVector[3] Local Triangles:TTriangle[3] Sides[0] = Plane.PointSide(Self.Point1) Sides[1] = Plane.PointSide(Self.Point2) Sides[2] = Plane.PointSide(Self.Point3) For Index = 0 To 2 If Sides[Index] = PLANE_FRONT Then FrontCount :+ 1 ElseIf Sides[Index] = PLANE_BACK Then BackCount :+ 1 Else PlanarCount :+ 1 FrontCount :+ 1 BackCount :+ 1 EndIf Next If PlanarCount = 3 Then Normal = New TVector Self.Normal(Normal) If Abs(Plane.Normal.Dot(Normal) - 1.0) < ZERO_TOLERANCE Then FrontList.AddLast(Self) Else BackList.AddLast(Self) EndIf Return False ElseIf FrontCount = 3 Then FrontList.AddLast(Self) Return False ElseIf BackCount = 3 Then BackList.AddLast(Self) Return False EndIf Edges[0] = New TLine Edges[0].Point1.Copy(Self.Point1) Edges[0].Point2.Copy(Self.Point2) Edges[1] = New TLine Edges[1].Point1.Copy(Self.Point2) Edges[1].Point2.Copy(Self.Point3) Edges[2] = New TLine Edges[2].Point1.Copy(Self.Point3) Edges[2].Point2.Copy(Self.Point1) For Index = 0 To 2 Intersections[Index] = New TVector Splits[Index] = Edges[Index].Intersect(Plane, Intersections[Index]) Next If Splits[0] And Splits[1] Then Triangles[0] = New TTriangle Triangles[0].Point1.Copy(Intersections[0]) Triangles[0].Point2.Copy(Self.Point2) Triangles[0].Point3.Copy(Intersections[1]) Triangles[1] = New TTriangle Triangles[1].Point1.Copy(Intersections[1]) Triangles[1].Point2.Copy(Self.Point3) Triangles[1].Point3.Copy(Self.Point1) Triangles[2] = New TTriangle Triangles[2].Point1.Copy(Self.Point1) Triangles[2].Point2.Copy(Intersections[0]) Triangles[2].Point3.Copy(Intersections[1]) Triangles[0].Splitter = Self.Splitter Triangles[1].Splitter = Self.Splitter Triangles[2].Splitter = Self.Splitter If Sides[1] = PLANE_FRONT Then FrontList.AddLast(Triangles[0]) BackList.AddLast(Triangles[1]) BackList.AddLast(Triangles[2]) Else BackList.AddLast(Triangles[0]) FrontList.AddLast(Triangles[1]) FrontList.AddLast(Triangles[2]) EndIf ElseIf Splits[1] And Splits[2] Then Triangles[0] = New TTriangle Triangles[0].Point1.Copy(Intersections[1]) Triangles[0].Point2.Copy(Self.Point3) Triangles[0].Point3.Copy(Intersections[2]) Triangles[1] = New TTriangle Triangles[1].Point1.Copy(Intersections[2]) Triangles[1].Point2.Copy(Self.Point1) Triangles[1].Point3.Copy(Self.Point2) Triangles[2] = New TTriangle Triangles[2].Point1.Copy(Self.Point2) Triangles[2].Point2.Copy(Intersections[1]) Triangles[2].Point3.Copy(Intersections[2]) Triangles[0].Splitter = Self.Splitter Triangles[1].Splitter = Self.Splitter Triangles[2].Splitter = Self.Splitter If Sides[0] = PLANE_FRONT Then FrontList.AddLast(Triangles[0]) FrontList.AddLast(Triangles[1]) BackList.AddLast(Triangles[2]) Else BackList.AddLast(Triangles[0]) BackList.AddLast(Triangles[1]) FrontList.AddLast(Triangles[2]) EndIf ElseIf Splits[2] And Splits[0] Then Triangles[0] = New TTriangle Triangles[0].Point1.Copy(Intersections[2]) Triangles[0].Point2.Copy(Self.Point1) Triangles[0].Point3.Copy(Intersections[0]) Triangles[1] = New TTriangle Triangles[1].Point1.Copy(Intersections[0]) Triangles[1].Point2.Copy(Self.Point2) Triangles[1].Point3.Copy(Self.Point3) Triangles[2] = New TTriangle Triangles[2].Point1.Copy(Self.Point3) Triangles[2].Point2.Copy(Intersections[2]) Triangles[2].Point3.Copy(Intersections[0]) Triangles[0].Splitter = Self.Splitter Triangles[1].Splitter = Self.Splitter Triangles[2].Splitter = Self.Splitter If Sides[0] = PLANE_FRONT Then FrontList.AddLast(Triangles[0]) BackList.AddLast(Triangles[1]) BackList.AddLast(Triangles[2]) Else FrontList.AddLast(Triangles[0]) BackList.AddLast(Triangles[1]) BackList.AddLast(Triangles[2]) EndIf ElseIf Splits[1] Then Triangles[0] = New TTriangle Triangles[0].Point1.Copy(Self.Point1) Triangles[0].Point2.Copy(Self.Point2) Triangles[0].Point3.Copy(Intersections[1]) Triangles[1] = New TTriangle Triangles[1].Point1.Copy(Intersections[1]) Triangles[1].Point2.Copy(Self.Point3) Triangles[1].Point3.Copy(Self.Point1) Triangles[0].Splitter = Self.Splitter Triangles[1].Splitter = Self.Splitter If Sides[1] = PLANE_FRONT Then FrontList.AddLast(Triangles[0]) BackList.AddLast(Triangles[1]) Else BackList.AddLast(Triangles[0]) FrontList.AddLast(Triangles[1]) EndIf ElseIf Splits[2] Then Triangles[0] = New TTriangle Triangles[0].Point1.Copy(Self.Point1) Triangles[0].Point2.Copy(Self.Point2) Triangles[0].Point3.Copy(Intersections[2]) Triangles[1] = New TTriangle Triangles[1].Point1.Copy(Intersections[2]) Triangles[1].Point2.Copy(Self.Point2) Triangles[1].Point3.Copy(Self.Point3) Triangles[0].Splitter = Self.Splitter Triangles[1].Splitter = Self.Splitter If Sides[0] = PLANE_FRONT Then FrontList.AddLast(Triangles[0]) BackList.AddLast(Triangles[1]) Else BackList.AddLast(Triangles[0]) FrontList.AddLast(Triangles[1]) EndIf ElseIf Splits[0] Then Triangles[0] = New TTriangle Triangles[0].Point1.Copy(Self.Point3) Triangles[0].Point2.Copy(Self.Point1) Triangles[0].Point3.Copy(Intersections[0]) Triangles[1] = New TTriangle Triangles[1].Point1.Copy(Intersections[0]) Triangles[1].Point2.Copy(Self.Point2) Triangles[1].Point3.Copy(Self.Point3) Triangles[0].Splitter = Self.Splitter Triangles[1].Splitter = Self.Splitter If Sides[0] = PLANE_FRONT Then FrontList.AddLast(Triangles[0]) BackList.AddLast(Triangles[1]) Else BackList.AddLast(Triangles[0]) FrontList.AddLast(Triangles[1]) EndIf EndIf Return True End Method Method Normal(Normal:TVector) Local Edge1:TVector, Edge2:TVector Edge1 = New TVector Edge2 = New TVector Edge1.Subtract(Self.Point2, Self.Point1) Edge2.Subtract(Self.Point3, Self.Point1) Normal.Cross(Edge1, Edge2) Normal.Normalize(Normal) End Method Method Copy(Triangle:TTriangle) Self.Point1.Copy(Triangle.Point1) Self.Point2.Copy(Triangle.Point2) Self.Point3.Copy(Triangle.Point3) End Method Method Write(Stream:TStream) Self.Point1.Write(Stream) Self.Point2.Write(Stream) Self.Point3.Write(Stream) End Method End Type Type TPlane Field Normal : TVector Field Distance : Float Method New() Self.Normal = New TVector End Method Method PointDistance:Float(Point:TVector) Return Self.Normal.Dot(Point) - Self.Distance End Method Method PointSide:Int(Point:TVector) Local Distance:Float Distance = Self.PointDistance(Point) If Abs(Distance) < ZERO_TOLERANCE Then Return PLANE_PLANAR ElseIf Distance > 0.0 Then Return PLANE_FRONT Else Return PLANE_BACK EndIf End Method Method FromTriangle(Triangle:TTriangle) Triangle.Normal(Self.Normal) Self.Distance = Self.Normal.Dot(Triangle.Point1) End Method Method Copy(Plane:TPlane) Self.Normal.Copy(Plane.Normal) Self.Distance = Plane.Distance End Method Method Write(Stream:TStream) Self.Normal.Write(Stream) Stream.WriteFloat(Self.Distance) End Method End Type Type TBox Field MinCorner : TVector Field MaxCorner : TVector Method New() Self.MinCorner = New TVector Self.MaxCorner = New TVector End Method Method Write(Stream:TStream) Self.MinCorner.Write(Stream) Self.MaxCorner.Write(Stream) End Method End Type Type TNode Global Count : Int Global List : TList Field ID : Int Field Partition : TPlane Field FrontNode : TNode Field BackNode : TNode Field FrontID : Int Field BackID : Int Field BoundingBox : TBox Field Triangles : TList Method New() TNode.Count :+ 1 TNode.List.AddLast(Self) Self.ID = TNode.Count Self.FrontID = -1 Self.BackID = -1 Self.BoundingBox = New TBox Self.Triangles = New TList End Method Method BuildChildren() Local Triangle:TTriangle Self.Partition = Self.FindPartition() If Not Self.Partition Then Return Self.FrontNode = New TNode Self.BackNode = New TNode Self.FrontID = Self.FrontNode.ID Self.BackID = Self.BackNode.ID For Triangle = EachIn Self.Triangles Triangle.Split(Self.Partition, Self.FrontNode.Triangles, .. Self.BackNode.Triangles) Next Self.FrontNode.BuildBoundingBox() Self.BackNode.BuildBoundingBox() Self.FrontNode.BuildChildren() Self.BackNode.BuildChildren() Self.Triangles.Clear() End Method Method FindPartition:TPlane() Local Plane:TPlane, SplitTriangle:TTriangle, Triangle:TTriangle Local Side:Int, FrontCount:Int, BackCount:Int, SplitCount:Int Local Efficiency:Int, Optimum:Int, OptimumTriangle:TTriangle, OptimumPlane:TPlane Plane = New TPlane OptimumPlane = Null Optimum = -1 For SplitTriangle = EachIn Self.Triangles If SplitTriangle.Splitter Then Continue Plane.FromTriangle(SplitTriangle) FrontCount = 0 BackCount = 0 SplitCount = 0 For Triangle = EachIn Self.Triangles If Triangle = SplitTriangle Then Continue Side = Triangle.Side(Plane) Select Side Case PLANE_FRONT FrontCount :+ 1 Case PLANE_BACK BackCount :+ 1 Case PLANE_SPLIT SplitCount :+ 1 End Select Next If (FrontCount = 0 Or BackCount = 0) And SplitCount = 0 Then Continue Efficiency = Abs(FrontCount - BackCount) + SplitCount*SPLIT_FACTOR If Optimum = -1 Or Efficiency < Optimum Then Optimum = Efficiency OptimumTriangle = New TTriangle OptimumPlane = New TPlane OptimumTriangle.Copy(SplitTriangle) OptimumPlane.Copy(Plane) EndIf Next If OptimumPlane Then OptimumTriangle.Splitter = True Return OptimumPlane End Method Method BuildBoundingBox() Local Triangle:TTriangle, MinX:Float, MaxX:Float, MinY:Float Local MaxY:Float, MinZ:Float, MaxZ:Float Triangle = TTriangle(Self.Triangles.First()) MinX = Triangle.Point1.X ; MaxX = MinX MinY = Triangle.Point1.Y ; MaxX = MinY MinZ = Triangle.Point1.Z ; MaxX = MinZ For Triangle = EachIn Self.Triangles If Triangle.Point1.X < MinX Then MinX = Triangle.Point1.X If Triangle.Point1.X > MaxX Then MaxX = Triangle.Point1.X If Triangle.Point1.Y < MinY Then MinY = Triangle.Point1.Y If Triangle.Point1.Y > MaxY Then MaxY = Triangle.Point1.Y If Triangle.Point1.Z < MinZ Then MinZ = Triangle.Point1.Z If Triangle.Point1.Z > MaxZ Then MaxZ = Triangle.Point1.Z If Triangle.Point2.X < MinX Then MinX = Triangle.Point2.X If Triangle.Point2.X > MaxX Then MaxX = Triangle.Point2.X If Triangle.Point2.Y < MinY Then MinY = Triangle.Point2.Y If Triangle.Point2.Y > MaxY Then MaxY = Triangle.Point2.Y If Triangle.Point2.Z < MinZ Then MinZ = Triangle.Point2.Z If Triangle.Point2.Z > MaxZ Then MaxZ = Triangle.Point2.Z If Triangle.Point3.X < MinX Then MinX = Triangle.Point3.X If Triangle.Point3.X > MaxX Then MaxX = Triangle.Point3.X If Triangle.Point3.Y < MinY Then MinY = Triangle.Point3.Y If Triangle.Point3.Y > MaxY Then MaxY = Triangle.Point3.Y If Triangle.Point3.Z < MinZ Then MinZ = Triangle.Point3.Z If Triangle.Point3.Z > MaxZ Then MaxZ = Triangle.Point3.Z Next Self.BoundingBox.MinCorner.X = MinX Self.BoundingBox.MinCorner.Y = MinY Self.BoundingBox.MinCorner.Z = MinZ Self.BoundingBox.MaxCorner.X = MaxX Self.BoundingBox.MaxCorner.Y = MaxY Self.BoundingBox.MaxCorner.Z = MaxZ End Method Method Write(Stream:TStream) Local Triangle:TTriangle Stream.WriteInt(Self.ID) Stream.WriteInt(Self.FrontID) Stream.WriteInt(Self.BackID) If Self.FrontID <> -1 Then Self.Partition.Write(Stream) Self.BoundingBox.Write(Stream) If Self.FrontID = -1 Then Stream.WriteInt(Self.Triangles.Count()) For Triangle = EachIn Self.Triangles Triangle.Write(Stream) Next EndIf End Method End Type Type TBSPCompiler Field Root : TNode Field Nodes : TList Field Partitions : TList Method New() Self.Root = New TNode End Method Method Compile() Self.Root.BuildBoundingBox() Self.Root.BuildChildren() End Method Function Load:TBSPCompiler(URL:Object) Local Stream:TStream, Compiler:TBSPCompiler, Count:Int, Index:Int Local Triangle:TTriangle Stream = ReadStream(URL) If Not Stream Then Return Null If Stream.ReadString(5) <> "RAW3D" Then Stream.Close() Return Null EndIf Compiler = New TBSPCompiler Count = Stream.ReadInt() For Index = 0 Until Count Triangle = New TTriangle Triangle.Point3.Read(Stream) Triangle.Point2.Read(Stream) Triangle.Point1.Read(Stream) Compiler.Root.Triangles.AddLast(Triangle) Next Stream.Close() Return Compiler End Function Function Save:Int(URL:Object) Local Stream:TStream, Node:TNode Stream = WriteFile(URL) If Not Stream Then Return False Stream.WriteString("BSP") Stream.WriteInt(TNode.List.Count()) For Node = EachIn TNode.List Node.Write(Stream) Next Stream.Close() Return True End Function End Type Ihr könnt nur die ZERO_TOLERANCE, sowie den SPLIT_FACTOR einstellen. ZERO_TOLLERANCE gibt an, ab wann ein Wert noch vom Compiler als 0 anerkannt wird. SPLIT_FACTOR bestimmt das Aussehen des BSP Baumes. Ist er sehr niedrig, so ist der Baum sehr ausgeglichen(Front und Back sind annähernd gleich) es treten aber viele Polygonsplits auf, die die Geometry erhöhen kann. Andersherum bleibt die Geometry annähernd gleich, könnte aber zu längeren Renderzeiten führen. Show.bmx zeigt nur alle Nodes + Boundingboxes nutzt aber nicht den BSP Baum, um optimiert zu rendern. mfg olli
vertex.dreamfall.at \| GitHub

Vertex

Betreff: Leaf BSP Compiler

So, Jul 02, 2006 13:54
Antworten mit Zitat

Hi!
Da ich eigentlich doch keine Lust habe, den Compiler weiter zu machen, gebe ich euch einfach mal den Sourcecode....

Alle Codes + Beispiele gibt es unter
http://vertex.dreamfall.at/bsp...mpiler.zip

Die Arbeit basiert auf:
http://www.3dtechdev.com/tutor...trees.html
http://www.3dtechdev.com/tutor...rytut.html(als Vortführung gedacht)

TPlane.Intersect war das Schwirigste. Wie die Formel zu Stande kam:
http://www.c-plusplus.de/forum...51582.html

Code: [AUSKLAPPEN]

SuperStrict

Framework BRL.StandardIO
Import BRL.FileSystem
Import BRL.LinkedList
Import BRL.Math

Const ZERO_TOLERANCE : Float = 0.0001
Const PLANE_FRONT : Int = 1
Const PLANE_BACK : Int = -1
Const PLANE_PLANAR : Int = 0
Const PLANE_SPLIT : Int = 2
Const SPLIT_FACTOR : Int = 10

Type TVector
Field X : Float
Field Y : Float
Field Z : Float

Method Set(X:Float, Y:Float, Z:Float)
   Self.X = X
   Self.Y = Y
   Self.Z = Z
End Method

Method Normalize(Vector:TVector)
   Local Length:Float, InvLength:Float

   Length = Vector.Length()
   If Length <> 0.0 Then
      InvLength = 1.0/Length
      Self.X = Vector.X*InvLength
      Self.Y = Vector.Y*InvLength
      Self.Z = Vector.Z*InvLength
   Else
      Self.X = 0.0
      Self.Y = 1.0
      Self.Z = 0.0
   EndIf
End Method

Method Add(A:TVector, B:TVector)
   Self.X = A.X + B.X
   Self.Y = A.Y + B.Y
   Self.Z = A.Z + B.Z
End Method

Method Subtract(A:TVector, B:TVector)
   Self.X = A.X - B.X
   Self.Y = A.Y - B.Y
   Self.Z = A.Z - B.Z
End Method

Method Scale(Vector:TVector, Scalar:Float)
   Self.X = Vector.X*Scalar
   Self.Y = Vector.Y*Scalar
   Self.Z = Vector.Z*Scalar
End Method

Method Cross(A:TVector, B:TVector)
   Self.X = A.Y*B.Z - A.Z*B.Y
   Self.Y = A.Z*B.X - A.X*B.Z
   Self.Z = A.X*B.Y - A.Y*B.X
End Method

Method Dot:Float(B:TVector)
   Return Self.X*B.X + Self.Y*B.Y + Self.Z*B.Z
End Method

Method Length:Float()
   Return Sqr(Self.X*Self.X + Self.Y*Self.Y + Self.Z*Self.Z)
End Method

Method Read(Stream:TStream)
   Self.X = Stream.ReadFloat()
   Self.Y = Stream.ReadFloat()
   Self.Z = Stream.ReadFloat()
End Method

Method Copy(Vector:TVector)
   Self.X = Vector.X
   Self.Y = Vector.Y
   Self.Z = Vector.Z
End Method

Method Write(Stream:TStream)
   Stream.WriteFloat(Self.X)
   Stream.WriteFloat(Self.Y)
   Stream.WriteFloat(Self.Z)
End Method
End Type

Type TLine
Field Point1 : TVector
Field Point2 : TVector

Method New()
   Self.Point1 = New TVector
   Self.Point2 = New TVector
End Method

Method Intersect:Int(Plane:TPlane, Intersection:TVector)
   Local Dot1:Float, Dot2:Float, Time:Float

   Dot1 = Plane.Normal.Dot(Self.Point1)
   Dot2 = Plane.Normal.Dot(Self.Point2)
   If Abs(Dot2-Dot1) < ZERO_TOLERANCE Then Return False

   Time = (Plane.Distance - Dot1)/(Dot2 - Dot1)
   If Time < 0.0 Or Time > 1.0 Then Return False

   Intersection.Subtract(Self.Point2, Self.Point1)
   Intersection.Scale(Intersection, Time)
   Intersection.Add(Intersection, Self.Point1)

   Return True
End Method

Method Copy(Line:TLine)
   Self.Point1.Copy(Line.Point1)
   Self.Point2.Copy(Line.Point2)
End Method
End Type

Type TTriangle
Field Point1 : TVector
Field Point2 : TVector
Field Point3 : TVector
Field Splitter : Int

Method New()
   Self.Point1 = New TVector
   Self.Point2 = New TVector
   Self.Point3 = New TVector
   Self.Splitter = False
End Method

Method Side:Int(Plane:TPlane)
   Local Sides:Int[3], Index:Int
   Local FrontCount:Int, BackCount:Int, PlanarCount:Int, Normal:TVector

   Sides[0] = Plane.PointSide(Self.Point1)
   Sides[1] = Plane.PointSide(Self.Point2)
   Sides[2] = Plane.PointSide(Self.Point3)

   For Index = 0 To 2
      If Sides[Index] = PLANE_FRONT Then
         FrontCount :+ 1
      ElseIf Sides[Index] = PLANE_BACK Then
         BackCount :+ 1
      Else
         PlanarCount :+ 1
         FrontCount :+ 1
         BackCount :+ 1
      EndIf
   Next

   If PlanarCount = 3 Then
      Normal = New TVector
      Self.Normal(Normal)
      If Abs(Plane.Normal.Dot(Normal) - 1.0) < ZERO_TOLERANCE Then
         Return PLANE_FRONT
      Else
         Return PLANE_BACK
      EndIf
   ElseIf FrontCount = 3 Then
      Return PLANE_FRONT
   ElseIf BackCount = 3 Then
      Return PLANE_BACK
   Else
      Return PLANE_SPLIT
   EndIf
End Method

Method Split:Int(Plane:TPlane, FrontList:TList, BackList:TList)
   Local Sides:Int[3], Index:Int
   Local FrontCount:Int, BackCount:Int, PlanarCount:Int, Normal:TVector
   Local Edges:TLine[3], Splits:Int[3], Intersections:TVector[3]
   Local Triangles:TTriangle[3]

   Sides[0] = Plane.PointSide(Self.Point1)
   Sides[1] = Plane.PointSide(Self.Point2)
   Sides[2] = Plane.PointSide(Self.Point3)

   For Index = 0 To 2
      If Sides[Index] = PLANE_FRONT Then
         FrontCount :+ 1
      ElseIf Sides[Index] = PLANE_BACK Then
         BackCount :+ 1
      Else
         PlanarCount :+ 1
         FrontCount :+ 1
         BackCount :+ 1
      EndIf
   Next

   If PlanarCount = 3 Then
      Normal = New TVector
      Self.Normal(Normal)
      If Abs(Plane.Normal.Dot(Normal) - 1.0) < ZERO_TOLERANCE Then
         FrontList.AddLast(Self)
      Else
         BackList.AddLast(Self)
      EndIf
      Return False
   ElseIf FrontCount = 3 Then
      FrontList.AddLast(Self)
      Return False
   ElseIf BackCount = 3 Then
      BackList.AddLast(Self)
      Return False
   EndIf

   Edges[0] = New TLine
   Edges[0].Point1.Copy(Self.Point1)
   Edges[0].Point2.Copy(Self.Point2)

   Edges[1] = New TLine
   Edges[1].Point1.Copy(Self.Point2)
   Edges[1].Point2.Copy(Self.Point3)

   Edges[2] = New TLine
   Edges[2].Point1.Copy(Self.Point3)
   Edges[2].Point2.Copy(Self.Point1)

   For Index = 0 To 2
      Intersections[Index] = New TVector
      Splits[Index] = Edges[Index].Intersect(Plane, Intersections[Index])
   Next

   If Splits[0] And Splits[1] Then
      Triangles[0] = New TTriangle
      Triangles[0].Point1.Copy(Intersections[0])
      Triangles[0].Point2.Copy(Self.Point2)
      Triangles[0].Point3.Copy(Intersections[1])

      Triangles[1] = New TTriangle
      Triangles[1].Point1.Copy(Intersections[1])
      Triangles[1].Point2.Copy(Self.Point3)
      Triangles[1].Point3.Copy(Self.Point1)

      Triangles[2] = New TTriangle
      Triangles[2].Point1.Copy(Self.Point1)
      Triangles[2].Point2.Copy(Intersections[0])
      Triangles[2].Point3.Copy(Intersections[1])

      Triangles[0].Splitter = Self.Splitter
      Triangles[1].Splitter = Self.Splitter
      Triangles[2].Splitter = Self.Splitter

      If Sides[1] = PLANE_FRONT Then
         FrontList.AddLast(Triangles[0])
         BackList.AddLast(Triangles[1])
         BackList.AddLast(Triangles[2])
      Else
         BackList.AddLast(Triangles[0])
         FrontList.AddLast(Triangles[1])
         FrontList.AddLast(Triangles[2])
      EndIf

   ElseIf Splits[1] And Splits[2] Then
      Triangles[0] = New TTriangle
      Triangles[0].Point1.Copy(Intersections[1])
      Triangles[0].Point2.Copy(Self.Point3)
      Triangles[0].Point3.Copy(Intersections[2])

      Triangles[1] = New TTriangle
      Triangles[1].Point1.Copy(Intersections[2])
      Triangles[1].Point2.Copy(Self.Point1)
      Triangles[1].Point3.Copy(Self.Point2)

      Triangles[2] = New TTriangle
      Triangles[2].Point1.Copy(Self.Point2)
      Triangles[2].Point2.Copy(Intersections[1])
      Triangles[2].Point3.Copy(Intersections[2])

      Triangles[0].Splitter = Self.Splitter
      Triangles[1].Splitter = Self.Splitter
      Triangles[2].Splitter = Self.Splitter

      If Sides[0] = PLANE_FRONT Then
         FrontList.AddLast(Triangles[0])
         FrontList.AddLast(Triangles[1])
         BackList.AddLast(Triangles[2])
      Else
         BackList.AddLast(Triangles[0])
         BackList.AddLast(Triangles[1])
         FrontList.AddLast(Triangles[2])
      EndIf
   ElseIf Splits[2] And Splits[0] Then
      Triangles[0] = New TTriangle
      Triangles[0].Point1.Copy(Intersections[2])
      Triangles[0].Point2.Copy(Self.Point1)
      Triangles[0].Point3.Copy(Intersections[0])

      Triangles[1] = New TTriangle
      Triangles[1].Point1.Copy(Intersections[0])
      Triangles[1].Point2.Copy(Self.Point2)
      Triangles[1].Point3.Copy(Self.Point3)

      Triangles[2] = New TTriangle
      Triangles[2].Point1.Copy(Self.Point3)
      Triangles[2].Point2.Copy(Intersections[2])
      Triangles[2].Point3.Copy(Intersections[0])

      Triangles[0].Splitter = Self.Splitter
      Triangles[1].Splitter = Self.Splitter
      Triangles[2].Splitter = Self.Splitter

      If Sides[0] = PLANE_FRONT Then
         FrontList.AddLast(Triangles[0])
         BackList.AddLast(Triangles[1])
         BackList.AddLast(Triangles[2])
      Else
         FrontList.AddLast(Triangles[0])
         BackList.AddLast(Triangles[1])
         BackList.AddLast(Triangles[2])
      EndIf
   ElseIf Splits[1] Then
      Triangles[0] = New TTriangle
      Triangles[0].Point1.Copy(Self.Point1)
      Triangles[0].Point2.Copy(Self.Point2)
      Triangles[0].Point3.Copy(Intersections[1])

      Triangles[1] = New TTriangle
      Triangles[1].Point1.Copy(Intersections[1])
      Triangles[1].Point2.Copy(Self.Point3)
      Triangles[1].Point3.Copy(Self.Point1)

      Triangles[0].Splitter = Self.Splitter
      Triangles[1].Splitter = Self.Splitter

      If Sides[1] = PLANE_FRONT Then
         FrontList.AddLast(Triangles[0])
         BackList.AddLast(Triangles[1])
      Else
         BackList.AddLast(Triangles[0])
         FrontList.AddLast(Triangles[1])
      EndIf
   ElseIf Splits[2] Then
      Triangles[0] = New TTriangle
      Triangles[0].Point1.Copy(Self.Point1)
      Triangles[0].Point2.Copy(Self.Point2)
      Triangles[0].Point3.Copy(Intersections[2])

      Triangles[1] = New TTriangle
      Triangles[1].Point1.Copy(Intersections[2])
      Triangles[1].Point2.Copy(Self.Point2)
      Triangles[1].Point3.Copy(Self.Point3)

      Triangles[0].Splitter = Self.Splitter
      Triangles[1].Splitter = Self.Splitter

      If Sides[0] = PLANE_FRONT Then
         FrontList.AddLast(Triangles[0])
         BackList.AddLast(Triangles[1])
      Else
         BackList.AddLast(Triangles[0])
         FrontList.AddLast(Triangles[1])
      EndIf
   ElseIf Splits[0] Then
      Triangles[0] = New TTriangle
      Triangles[0].Point1.Copy(Self.Point3)
      Triangles[0].Point2.Copy(Self.Point1)
      Triangles[0].Point3.Copy(Intersections[0])

      Triangles[1] = New TTriangle
      Triangles[1].Point1.Copy(Intersections[0])
      Triangles[1].Point2.Copy(Self.Point2)
      Triangles[1].Point3.Copy(Self.Point3)

      Triangles[0].Splitter = Self.Splitter
      Triangles[1].Splitter = Self.Splitter

      If Sides[0] = PLANE_FRONT Then
         FrontList.AddLast(Triangles[0])
         BackList.AddLast(Triangles[1])
      Else
         BackList.AddLast(Triangles[0])
         FrontList.AddLast(Triangles[1])
      EndIf
   EndIf

   Return True
End Method

Method Normal(Normal:TVector)
   Local Edge1:TVector, Edge2:TVector

   Edge1 = New TVector
   Edge2 = New TVector
   Edge1.Subtract(Self.Point2, Self.Point1)
   Edge2.Subtract(Self.Point3, Self.Point1)
   Normal.Cross(Edge1, Edge2)
   Normal.Normalize(Normal)
End Method

Method Copy(Triangle:TTriangle)
   Self.Point1.Copy(Triangle.Point1)
   Self.Point2.Copy(Triangle.Point2)
   Self.Point3.Copy(Triangle.Point3)
End Method

Method Write(Stream:TStream)
   Self.Point1.Write(Stream)
   Self.Point2.Write(Stream)
   Self.Point3.Write(Stream)
End Method
End Type

Type TPlane
Field Normal : TVector
Field Distance : Float

Method New()
   Self.Normal = New TVector
End Method

Method PointDistance:Float(Point:TVector)
   Return Self.Normal.Dot(Point) - Self.Distance
End Method

Method PointSide:Int(Point:TVector)
   Local Distance:Float

   Distance = Self.PointDistance(Point)
   If Abs(Distance) < ZERO_TOLERANCE Then
      Return PLANE_PLANAR
   ElseIf Distance > 0.0 Then
      Return PLANE_FRONT
   Else
      Return PLANE_BACK
   EndIf
End Method

Method FromTriangle(Triangle:TTriangle)
   Triangle.Normal(Self.Normal)
   Self.Distance = Self.Normal.Dot(Triangle.Point1)
End Method

Method Copy(Plane:TPlane)
   Self.Normal.Copy(Plane.Normal)
   Self.Distance = Plane.Distance
End Method

Method Write(Stream:TStream)
   Self.Normal.Write(Stream)
   Stream.WriteFloat(Self.Distance)
End Method
End Type

Type TBox
Field MinCorner : TVector
Field MaxCorner : TVector

Method New()
   Self.MinCorner = New TVector
   Self.MaxCorner = New TVector
End Method

Method Write(Stream:TStream)
   Self.MinCorner.Write(Stream)
   Self.MaxCorner.Write(Stream)
End Method
End Type

Type TNode
Global Count : Int
Global List : TList

Field ID : Int
Field Partition : TPlane
Field FrontNode : TNode
Field BackNode : TNode
Field FrontID : Int
Field BackID : Int
Field BoundingBox : TBox
Field Triangles : TList

Method New()
   TNode.Count :+ 1
   TNode.List.AddLast(Self)

   Self.ID = TNode.Count
   Self.FrontID = -1
   Self.BackID = -1
   Self.BoundingBox = New TBox
   Self.Triangles = New TList
End Method

Method BuildChildren()
   Local Triangle:TTriangle

   Self.Partition = Self.FindPartition()
   If Not Self.Partition Then Return

   Self.FrontNode = New TNode
   Self.BackNode = New TNode

   Self.FrontID = Self.FrontNode.ID
   Self.BackID = Self.BackNode.ID

   For Triangle = EachIn Self.Triangles
      Triangle.Split(Self.Partition, Self.FrontNode.Triangles, ..
         Self.BackNode.Triangles)
   Next

   Self.FrontNode.BuildBoundingBox()
   Self.BackNode.BuildBoundingBox()

   Self.FrontNode.BuildChildren()
   Self.BackNode.BuildChildren()

   Self.Triangles.Clear()
End Method

Method FindPartition:TPlane()
   Local Plane:TPlane, SplitTriangle:TTriangle, Triangle:TTriangle
   Local Side:Int, FrontCount:Int, BackCount:Int, SplitCount:Int
   Local Efficiency:Int, Optimum:Int, OptimumTriangle:TTriangle, OptimumPlane:TPlane

   Plane = New TPlane
   OptimumPlane = Null
   Optimum = -1
   For SplitTriangle = EachIn Self.Triangles
      If SplitTriangle.Splitter Then Continue
      Plane.FromTriangle(SplitTriangle)

      FrontCount = 0
      BackCount = 0
      SplitCount = 0

      For Triangle = EachIn Self.Triangles
         If Triangle = SplitTriangle Then Continue

         Side = Triangle.Side(Plane)
         Select Side
            Case PLANE_FRONT
               FrontCount :+ 1
            Case PLANE_BACK
               BackCount :+ 1
            Case PLANE_SPLIT
               SplitCount :+ 1
         End Select
      Next

      If (FrontCount = 0 Or BackCount = 0) And SplitCount = 0 Then Continue
      Efficiency = Abs(FrontCount - BackCount) + SplitCount*SPLIT_FACTOR
      If Optimum = -1 Or Efficiency < Optimum Then
         Optimum = Efficiency
         OptimumTriangle = New TTriangle
         OptimumPlane = New TPlane

         OptimumTriangle.Copy(SplitTriangle)
         OptimumPlane.Copy(Plane)
      EndIf
   Next

   If OptimumPlane Then OptimumTriangle.Splitter = True
   Return OptimumPlane
End Method

Method BuildBoundingBox()
   Local Triangle:TTriangle, MinX:Float, MaxX:Float, MinY:Float
   Local MaxY:Float, MinZ:Float, MaxZ:Float

   Triangle = TTriangle(Self.Triangles.First())
   MinX = Triangle.Point1.X ; MaxX = MinX
   MinY = Triangle.Point1.Y ; MaxX = MinY
   MinZ = Triangle.Point1.Z ; MaxX = MinZ

   For Triangle = EachIn Self.Triangles
      If Triangle.Point1.X < MinX Then MinX = Triangle.Point1.X
      If Triangle.Point1.X > MaxX Then MaxX = Triangle.Point1.X
      If Triangle.Point1.Y < MinY Then MinY = Triangle.Point1.Y
      If Triangle.Point1.Y > MaxY Then MaxY = Triangle.Point1.Y
      If Triangle.Point1.Z < MinZ Then MinZ = Triangle.Point1.Z
      If Triangle.Point1.Z > MaxZ Then MaxZ = Triangle.Point1.Z

      If Triangle.Point2.X < MinX Then MinX = Triangle.Point2.X
      If Triangle.Point2.X > MaxX Then MaxX = Triangle.Point2.X
      If Triangle.Point2.Y < MinY Then MinY = Triangle.Point2.Y
      If Triangle.Point2.Y > MaxY Then MaxY = Triangle.Point2.Y
      If Triangle.Point2.Z < MinZ Then MinZ = Triangle.Point2.Z
      If Triangle.Point2.Z > MaxZ Then MaxZ = Triangle.Point2.Z

      If Triangle.Point3.X < MinX Then MinX = Triangle.Point3.X
      If Triangle.Point3.X > MaxX Then MaxX = Triangle.Point3.X
      If Triangle.Point3.Y < MinY Then MinY = Triangle.Point3.Y
      If Triangle.Point3.Y > MaxY Then MaxY = Triangle.Point3.Y
      If Triangle.Point3.Z < MinZ Then MinZ = Triangle.Point3.Z
      If Triangle.Point3.Z > MaxZ Then MaxZ = Triangle.Point3.Z
   Next

   Self.BoundingBox.MinCorner.X = MinX
   Self.BoundingBox.MinCorner.Y = MinY
   Self.BoundingBox.MinCorner.Z = MinZ

   Self.BoundingBox.MaxCorner.X = MaxX
   Self.BoundingBox.MaxCorner.Y = MaxY
   Self.BoundingBox.MaxCorner.Z = MaxZ
End Method

Method Write(Stream:TStream)
   Local Triangle:TTriangle

   Stream.WriteInt(Self.ID)
   Stream.WriteInt(Self.FrontID)
   Stream.WriteInt(Self.BackID)
   If Self.FrontID <> -1 Then Self.Partition.Write(Stream)
   Self.BoundingBox.Write(Stream)

   If Self.FrontID = -1 Then
      Stream.WriteInt(Self.Triangles.Count())
      For Triangle = EachIn Self.Triangles
         Triangle.Write(Stream)
      Next
   EndIf
End Method
End Type

Type TBSPCompiler
Field Root : TNode
Field Nodes : TList
Field Partitions : TList

Method New()
   Self.Root = New TNode
End Method

Method Compile()
   Self.Root.BuildBoundingBox()
   Self.Root.BuildChildren()
End Method

Function Load:TBSPCompiler(URL:Object)
   Local Stream:TStream, Compiler:TBSPCompiler, Count:Int, Index:Int
   Local Triangle:TTriangle

   Stream = ReadStream(URL)
   If Not Stream Then Return Null

   If Stream.ReadString(5) <> "RAW3D" Then
      Stream.Close()
      Return Null
   EndIf

   Compiler = New TBSPCompiler
   Count = Stream.ReadInt()
   For Index = 0 Until Count
      Triangle = New TTriangle
      Triangle.Point3.Read(Stream)
      Triangle.Point2.Read(Stream)
      Triangle.Point1.Read(Stream)

      Compiler.Root.Triangles.AddLast(Triangle)
   Next

   Stream.Close()
   Return Compiler
End Function

Function Save:Int(URL:Object)
   Local Stream:TStream, Node:TNode

   Stream = WriteFile(URL)
   If Not Stream Then Return False

   Stream.WriteString("BSP")
   Stream.WriteInt(TNode.List.Count())
   For Node = EachIn TNode.List
      Node.Write(Stream)
   Next

   Stream.Close()
   Return True
End Function
End Type

Ihr könnt nur die ZERO_TOLERANCE, sowie den SPLIT_FACTOR einstellen. ZERO_TOLLERANCE gibt an, ab wann ein Wert noch vom Compiler als 0 anerkannt wird. SPLIT_FACTOR bestimmt das Aussehen des BSP Baumes. Ist er sehr niedrig, so ist der Baum sehr ausgeglichen(Front und Back sind annähernd gleich) es treten aber viele Polygonsplits auf, die die Geometry erhöhen kann. Andersherum bleibt die Geometry annähernd gleich, könnte aber zu längeren Renderzeiten führen.

Show.bmx zeigt nur alle Nodes + Boundingboxes nutzt aber nicht den BSP Baum, um optimiert zu rendern.

mfg olli

vertex.dreamfall.at | GitHub