Leaf BSP Compiler

Übersicht BlitzMax, BlitzMax NG Codearchiv & Module

Neue Antwort erstellen

Vertex

Betreff: Leaf BSP Compiler

BeitragSo, Jul 02, 2006 13:54
Antworten mit Zitat
Benutzer-Profile anzeigen
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

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Codearchiv & Module

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group