Leaf BSP Compiler
Übersicht

![]() |
VertexBetreff: Leaf BSP Compiler |
![]() 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 |
Übersicht


Powered by phpBB © 2001 - 2006, phpBB Group