unit BeRoCSGBSP;
(*****************************************************************************
**        Copyright 2014 Benjamin Rosseaux. All rights reserved.             *
******************************************************************************
**
** Boost Software License - Version 1.0 - August 17th, 2003
**
** Permission is hereby granted, free of charge, to any person or organization
** obtaining a copy of the software and accompanying documentation covered by
** this license (the "Software") to use, reproduce, display, distribute,
** execute, and transmit the Software, and to prepare derivative works of the
** Software, and to permit third-parties to whom the Software is furnished to
** do so, all subject to the following:
**
** The copyright notices in the Software and this entire statement, including
** the above license grant, this restriction and the following disclaimer,
** must be included in all copies of the Software, in whole or in part, and
** all derivative works of the Software, unless such copies or derivative
** works are solely in the form of machine-executable object code generated by
** a source language processor.
**
** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
** IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
** FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
** SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
** FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
** ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
** DEALINGS IN THE SOFTWARE.
**
******************************************************************************
**                                                                           *
** The views and conclusions contained in the software and documentation are *
** those of the authors and should not be interpreted as representing        *
** official policies, either expressed or implied, of Benjamin Rosseaux.     *
**                                                                           *
******************************************************************************)
{$ifdef fpc}
 {$mode delphi}
{$endif}
{$hints off}
{$j+}

interface

uses SysUtils,Classes,Math,GDFWMath;

const COPLANAR=0;
      FRONT=1;
      BACK=2;
      SPANNING=3;

type PCSGBSPVertex=^TCSGBSPVertex;
     TCSGBSPVertex=object
      public
       Position:TVector3;
       Normal:TVector3;
       TexCoord:TVector2;
     end;

     PCSGBSPPolygonVertices=^TCSGBSPPolygonVertices;
     TCSGBSPPolygonVertices=object
      public
       Vertices:array of TCSGBSPVertex;
       CountVertices:longint;
       procedure Initialize;
       procedure Deinitialize;
       function Clone:TCSGBSPPolygonVertices;
       procedure Add(const Vertex:TCSGBSPVertex);
     end;

     PCSGBSPPolygon=^TCSGBSPPolygon;
     TCSGBSPPolygon=object
      public
       Vertices:TCSGBSPPolygonVertices;
       Plane:TPlane;
       procedure Initialize;
       procedure Deinitialize;
       procedure CalculateProperties;
       procedure Flip;
       function Clone:TCSGBSPPolygon;
       function ClassifyVertex(const Vertex:TVector3):longint;
       function ClassifySide(const Polygon:TCSGBSPPolygon):longint;
     end;

     TCSGBSPPolygons=array of TCSGBSPPolygon;

     PCSGBSPPolygonList=^TCSGBSPPolygonList;
     TCSGBSPPolygonList=object
      public
       Polygons:TCSGBSPPolygons;
       CountPolygons:longint;
       procedure Initialize;
       procedure Deinitialize;
       function Clone:TCSGBSPPolygonList;
       procedure Add(const Polygon:TCSGBSPPolygon);
     end;

     TCSGBSPNode=class
      public
       PolygonList:TCSGBSPPolygonList;
       Divider:TCSGBSPPolygon;
       HasDivider:boolean;
       FrontNode:TCSGBSPNode;
       BackNode:TCSGBSPNode;
       constructor Create(const InputPolygonList:TCSGBSPPolygonList);
       destructor Destroy; override;
       function IsConvex:boolean;
       procedure Build(const InputPolygonList:TCSGBSPPolygonList);
       procedure AllPolygons(var OutputPolygonList:TCSGBSPPolygonList);
       function Clone:TCSGBSPNode;
       function Invert:TCSGBSPNode;
       procedure ClipPolygons(const InputPolygonList:TCSGBSPPolygonList;var OutputPolygonList:TCSGBSPPolygonList);
       procedure ClipTo(Node:TCSGBSPNode);
     end;

     TCSGBSPTree=class
      public
       Root:TCSGBSPNode;
       constructor Create(const InputPolygonList:TCSGBSPPolygonList); overload;
       constructor Create(const Node:TCSGBSPNode); overload;
       destructor Destroy; override;
       function Subtract(OtherTree:TCSGBSPTree):TCSGBSPNode;
       function Union(OtherTree:TCSGBSPTree):TCSGBSPNode;
       function Intersection(OtherTree:TCSGBSPTree):TCSGBSPNode;
       function Difference(OtherTree:TCSGBSPTree):TCSGBSPNode;
       function Invert:TCSGBSPNode;
       procedure GetTrianglePolygons(out OutputPolygonList:TCSGBSPPolygonList);
     end;

procedure TCSGBSPPolygonSplit(const This,Polygon:TCSGBSPPolygon;var CoplanarFrontList,CoplanarBackList,FrontList,BackList:TCSGBSPPolygonList);

implementation

uses BeRoDoubleToString;

const EPSILON=1e-6;


procedure TCSGBSPPolygonVertices.Initialize;

begin
 Vertices:=nil;
 CountVertices:=0;
end;

procedure TCSGBSPPolygonVertices.Deinitialize;
begin
 SetLength(Vertices,0);
 CountVertices:=0;
end;


function TCSGBSPPolygonVertices.Clone:TCSGBSPPolygonVertices;

begin

 result.Initialize;

 result.Vertices:=copy(Vertices);

 result.CountVertices:=CountVertices;
end;


procedure TCSGBSPPolygonVertices.Add(const Vertex:TCSGBSPVertex);

begin

 if (CountVertices+1)>length(Vertices) then begin

  SetLength(Vertices,(CountVertices+1)*2);
 end;
 Vertices[CountVertices]:=Vertex;
 inc(CountVertices);
end;


procedure TCSGBSPPolygon.Initialize;

begin
 Vertices.Initialize;
end;

procedure TCSGBSPPolygon.Deinitialize;
begin
 Vertices.Deinitialize;
end;


procedure TCSGBSPPolygonList.Initialize;

begin
 Polygons:=nil;
 CountPolygons:=0;
end;

procedure TCSGBSPPolygon.CalculateProperties;

begin
 Plane.Normal:=Vector3Norm(Vector3Cross(Vector3Sub(Vertices.Vertices[2].Position,Vertices.Vertices[0].Position),Vector3Sub(Vertices.Vertices[1].Position,Vertices.Vertices[0].Position)));
 Plane.Distance:=-Vector3Dot(Plane.Normal,Vertices.Vertices[0].Position);
end;

procedure TCSGBSPPolygon.Flip;
var i:longint;
    Vertex:TCSGBSPVertex;
begin
 for i:=0 to (Vertices.CountVertices shr 1)-1 do begin
  Vertex:=Vertices.Vertices[i];
  Vertices.Vertices[i]:=Vertices.Vertices[Vertices.CountVertices-(i+1)];
  Vertices.Vertices[Vertices.CountVertices-(i+1)]:=Vertex;
 end;
 Plane.Normal:=Vector3Neg(Plane.Normal);
 Plane.Distance:=-Plane.Distance;
end;

function TCSGBSPPolygon.Clone:TCSGBSPPolygon;
begin
 result.Initialize;
 result.Vertices:=Vertices.Clone;
 result.Plane:=Plane;
end;


function TCSGBSPPolygon.ClassifyVertex(const Vertex:TVector3):longint;

var SideValue:single;

begin

 SideValue:=Vector3Dot(Plane.Normal,Vertex)+Plane.Distance;

 if SideValue<(-EPSILON) then begin

  result:=BACK;

 end else if SideValue>EPSILON then begin

  result:=FRONT;

 end else begin

  result:=COPLANAR;

 end;

end;


function TCSGBSPPolygon.ClassifySide(const Polygon:TCSGBSPPolygon):longint;

var i,Positive,Negative:longint;

begin

 Positive:=0;

 Negative:=0;

 for i:=0 to Polygon.Vertices.CountVertices-1 do begin

  case ClassifyVertex(Polygon.Vertices.Vertices[i].Position) of

   BACK:begin

    inc(Negative);

   end;

   FRONT:begin

    inc(Positive);

   end;

  end;

 end;

 if (Positive>0) and (Negative=0) then begin

  result:=FRONT;

 end else if (Positive=0) and (Negative>0) then begin

  result:=BACK;

 end else if (Positive=0) and (Negative=0) then begin

  result:=COPLANAR;

 end else begin

  result:=SPANNING;

 end;

end;


procedure TCSGBSPPolygonSplit(const This,Polygon:TCSGBSPPolygon;var CoplanarFrontList,CoplanarBackList,FrontList,BackList:TCSGBSPPolygonList);

var i,j,ci,cj:longint;

    t:single;

    fv,bv:TCSGBSPPolygonVertices;

    vi,vj:PCSGBSPVertex;

    v:TCSGBSPVertex;

    p:TCSGBSPPolygon;

begin

 case This.ClassifySide(Polygon) of

  COPLANAR:begin

   if Vector3Dot(This.Plane.Normal,Polygon.Plane.Normal)>0.0 then begin

    CoplanarFrontList.Add(Polygon);

   end else begin

    CoplanarBackList.Add(Polygon);

   end;

  end;

  FRONT:begin

   FrontList.Add(Polygon);

  end;

  BACK:begin

   BackList.Add(Polygon);

  end;

  else {SPANNING:}begin

   fv.Initialize;

   bv.Initialize;

   try

    for i:=0 to Polygon.Vertices.CountVertices-1 do begin

     j:=i+1;

     if j>=Polygon.Vertices.CountVertices then begin

      j:=0;

     end;

     vi:=@Polygon.Vertices.Vertices[i];

     vj:=@Polygon.Vertices.Vertices[j];

     ci:=This.ClassifyVertex(vi^.Position);

     cj:=This.ClassifyVertex(vj^.Position);

     if ci<>BACK then begin

      fv.Add(vi^);

     end;

     if ci<>FRONT then begin

      bv.Add(vi^);

     end;

     if (ci or cj)=SPANNING then begin

      t:=(Vector3Dot(This.Plane.Normal,vi^.Position)+This.Plane.Distance)/Vector3Dot(This.Plane.Normal,Vector3Sub(vj^.Position,vi^.Position));

      v.Position:=Vector3Lerp(vi^.Position,vj^.Position,t);

      v.Normal:=Vector3Lerp(vi^.Normal,vj^.Normal,t);

      v.TexCoord:=Vector2Lerp(vi^.TexCoord,vj^.TexCoord,t);

      fv.Add(v);

      bv.Add(v);

     end;

    end;

    if fv.CountVertices>=3 then begin

     p.Vertices:=fv.Clone;

     p.CalculateProperties;

     FrontList.Add(p);

    end;

    if bv.CountVertices>=3 then begin

     p.Vertices:=bv.Clone;

     p.CalculateProperties;

     BackList.Add(p);

    end;

   finally

    fv.Deinitialize;

    bv.Deinitialize;

   end;

  end;

 end;

end;


procedure TCSGBSPPolygonList.Deinitialize;

var i:longint;

begin
 for i:=0 to CountPolygons-1 do begin
  Polygons[i].Deinitialize;
 end;
 SetLength(Polygons,0);
 CountPolygons:=0;
end;


function TCSGBSPPolygonList.Clone:TCSGBSPPolygonList;
var i:longint;
begin
 result.Initialize;
 for i:=0 to CountPolygons-1 do begin
  result.Add(Polygons[i].Clone);
 end;
end;

procedure TCSGBSPPolygonList.Add(const Polygon:TCSGBSPPolygon);

begin

 if (CountPolygons+1)>length(Polygons) then begin
  SetLength(Polygons,(CountPolygons+1)*2);
 end;
 Polygons[CountPolygons]:=Polygon;
 inc(CountPolygons);
end;


constructor TCSGBSPNode.Create(const InputPolygonList:TCSGBSPPolygonList);

var i:longint;

    FrontList,BackList:TCSGBSPPolygonList;

begin

 inherited Create;
 PolygonList.Initialize;
 FillChar(Divider,SizeOf(TCSGBSPPolygon),AnsiChar(#0));
 HasDivider:=false;
 FrontNode:=nil;
 BackNode:=nil;
 FrontList.Initialize;
 BackList.Initialize;
 try
  if InputPolygonList.CountPolygons>0 then begin
   Divider:=InputPolygonList.Polygons[0].Clone;
   HasDivider:=true;
   for i:=0 to InputPolygonList.CountPolygons-1 do begin
    TCSGBSPPolygonSplit(Divider,InputPolygonList.Polygons[i],PolygonList,PolygonList,FrontList,BackList);
   end;
   if FrontList.CountPolygons>0 then begin
    FrontNode:=TCSGBSPNode.Create(FrontList);
   end;
   if BackList.CountPolygons>0 then begin
    BackNode:=TCSGBSPNode.Create(BackList);
   end;
  end;
 finally
  FrontList.Deinitialize;
  BackList.Deinitialize;
 end;
end;

destructor TCSGBSPNode.Destroy;
begin
 PolygonList.Deinitialize;
 Divider.Deinitialize;
 FreeAndNil(FrontNode);
 FreeAndNil(BackNode);
 inherited Destroy;
end;

function TCSGBSPNode.IsConvex:boolean;
var i,j:longint;
begin
 result:=true;
 for i:=0 to PolygonList.CountPolygons-1 do begin
  for j:=0 to PolygonList.CountPolygons-1 do begin
   if (i<>j) and (PolygonList.Polygons[i].ClassifySide(PolygonList.Polygons[j])<>BACK) then begin
    result:=false;
    exit;
   end;
  end;
 end;
end;

procedure TCSGBSPNode.Build(const InputPolygonList:TCSGBSPPolygonList);
var i:longint;
    FrontList,BackList:TCSGBSPPolygonList;

begin
 FrontList.Initialize;
 BackList.Initialize;
 try
  if InputPolygonList.CountPolygons>0 then begin

   if not HasDivider then begin
    Divider:=InputPolygonList.Polygons[0].Clone;
   end;
   for i:=0 to InputPolygonList.CountPolygons-1 do begin
    TCSGBSPPolygonSplit(Divider,InputPolygonList.Polygons[i],PolygonList,PolygonList,FrontList,BackList);
   end;
   if FrontList.CountPolygons>0 then begin
    if assigned(FrontNode) then begin
     FrontNode.Build(FrontList);
    end else begin
     FrontNode:=TCSGBSPNode.Create(FrontList);
    end;
   end;
   if BackList.CountPolygons>0 then begin
    if assigned(BackNode) then begin
     BackNode.Build(BackList);
    end else begin
     BackNode:=TCSGBSPNode.Create(BackList);
    end;
   end;
  end;
 finally
  FrontList.Deinitialize;
  BackList.Deinitialize;
 end;
end;

procedure TCSGBSPNode.AllPolygons(var OutputPolygonList:TCSGBSPPolygonList);
var i:longint;
begin
 for i:=0 to PolygonList.CountPolygons-1 do begin
  OutputPolygonList.Add(PolygonList.Polygons[i].Clone);
 end;
 if assigned(FrontNode) then begin
  FrontNode.AllPolygons(OutputPolygonList);
 end;
 if assigned(BackNode) then begin
  BackNode.AllPolygons(OutputPolygonList);
 end;
end;

function TCSGBSPNode.Clone:TCSGBSPNode;
var EmptyList:TCSGBSPPolygonList;
begin
 EmptyList.Initialize;
 try
  result:=TCSGBSPNode.Create(EmptyList);
  result.PolygonList:=PolygonList.Clone;
  result.Divider:=Divider.Clone;
  result.HasDivider:=HasDivider;
  if assigned(FrontNode) then begin
   result.FrontNode:=FrontNode.Clone;
  end else begin
   result.FrontNode:=nil;
  end;
  if assigned(BackNode) then begin
   result.BackNode:=BackNode.Clone;
  end else begin
   result.BackNode:=nil;
  end;
 finally
  EmptyList.Deinitialize;
 end;
end;

function TCSGBSPNode.Invert:TCSGBSPNode;
var i:longint;
    Temp:TCSGBSPNode;
begin
 for i:=0 to PolygonList.CountPolygons-1 do begin
  PolygonList.Polygons[i].Flip;
 end;
 Divider.Flip;
 if assigned(FrontNode) then begin
  FrontNode.Invert;
 end;
 if assigned(BackNode) then begin
  BackNode.Invert;
 end;
 Temp:=FrontNode;
 FrontNode:=BackNode;
 BackNode:=Temp;
 result:=self;
end;

procedure TCSGBSPNode.ClipPolygons(const InputPolygonList:TCSGBSPPolygonList;var OutputPolygonList:TCSGBSPPolygonList);
var i:longint;
    FrontList,BackList,TempList:TCSGBSPPolygonList;
begin
 FrontList.Initialize;
 BackList.Initialize;
 TempList.Initialize;
 try
  if HasDivider then begin
   for i:=0 to InputPolygonList.CountPolygons-1 do begin
    TCSGBSPPolygonSplit(Divider,InputPolygonList.Polygons[i],PolygonList,PolygonList,FrontList,BackList);
   end;
   if assigned(FrontNode) then begin
    TempList:=FrontList.Clone;
    FrontList.Deinitialize;
    FrontNode.ClipPolygons(TempList,FrontList);
   end;
   if assigned(BackNode) then begin
    TempList:=BackList.Clone;
    BackList.Deinitialize;
    BackNode.ClipPolygons(TempList,BackList);
   end else begin
    BackList.Deinitialize;
   end;
   for i:=0 to FrontList.CountPolygons-1 do begin
    OutputPolygonList.Add(FrontList.Polygons[i]);
   end;
   for i:=0 to BackList.CountPolygons-1 do begin
    OutputPolygonList.Add(BackList.Polygons[i]);
   end;
  end else begin
   for i:=0 to InputPolygonList.CountPolygons-1 do begin
    OutputPolygonList.Add(InputPolygonList.Polygons[i]);
   end;
  end;
 finally
  FrontList.Deinitialize;
  BackList.Deinitialize;
  TempList.Deinitialize;
 end;
end;

procedure TCSGBSPNode.ClipTo(Node:TCSGBSPNode);
var TempList:TCSGBSPPolygonList;
begin
 TempList.Initialize;
 try
  TempList:=PolygonList.Clone;
  PolygonList.Deinitialize;
  Node.ClipPolygons(TempList,PolygonList);
 finally
  TempList.Deinitialize;
 end;
 if assigned(FrontNode) then begin
  FrontNode.ClipTo(Node);
 end;
 if assigned(BackNode) then begin
  BackNode.ClipTo(Node);
 end;
end;

constructor TCSGBSPTree.Create(const InputPolygonList:TCSGBSPPolygonList);
begin
 inherited Create;
 Root:=TCSGBSPNode.Create(InputPolygonList);
end;

constructor TCSGBSPTree.Create(const Node:TCSGBSPNode);
begin
 inherited Create;
 Root:=Node;
end;

destructor TCSGBSPTree.Destroy;
begin
 FreeAndNil(Root);
 inherited Destroy;
end;

function TCSGBSPTree.Subtract(OtherTree:TCSGBSPTree):TCSGBSPNode;
var a,b:TCSGBSPNode;
    TempList:TCSGBSPPolygonList;
begin
 b:=nil;
 TempList.Initialize;
 try
  a:=Root.Clone;
  b:=OtherTree.Root.Clone;
  a.Invert;
  a.ClipTo(b);
  b.ClipTo(a);
  b.Invert;
  b.ClipTo(a);
  b.Invert;
  b.AllPolygons(TempList);
  a.Build(TempList);
  a.Invert;
  result:=a;
 finally
  TempList.Deinitialize;
  b.Free;
 end;
end;

function TCSGBSPTree.Union(OtherTree:TCSGBSPTree):TCSGBSPNode;
var a,b:TCSGBSPNode;
    TempList:TCSGBSPPolygonList;
begin
 b:=nil;
 TempList.Initialize;
 try
  a:=Root.Clone;
  b:=OtherTree.Root.Clone;
  a.ClipTo(b);
  b.ClipTo(a);
  b.Invert;
  b.ClipTo(a);
  b.Invert;
  b.AllPolygons(TempList);
  a.Build(TempList);
  result:=a;
 finally
  TempList.Deinitialize;
  b.Free;
 end;
end;

function TCSGBSPTree.Intersection(OtherTree:TCSGBSPTree):TCSGBSPNode;
var a,b:TCSGBSPNode;
    TempList:TCSGBSPPolygonList;
begin
 b:=nil;
 TempList.Initialize;
 try
  a:=Root.Clone;
  b:=OtherTree.Root.Clone;
  a.Invert;
  b.ClipTo(a);
  b.Invert;
  a.ClipTo(a);
  b.ClipTo(a);
  b.AllPolygons(TempList);
  a.Build(TempList);
  a.Invert;
  result:=a;
 finally
  TempList.Deinitialize;
  b.Free;
 end;
end;

function TCSGBSPTree.Difference(OtherTree:TCSGBSPTree):TCSGBSPNode;
var a,b:TCSGBSPNode;
    TempList:TCSGBSPPolygonList;
begin
 a:=nil;
 b:=nil;
 TempList.Initialize;
 try
  a:=Root.Clone;
  b:=OtherTree.Root.Clone;

  a.ClipTo(b);
  b.ClipTo(a);
  b.Invert;
  b.ClipTo(a);
  b.Invert;
  b.AllPolygons(TempList);
  a.Build(TempList);

  b.Free;
  
  b:=OtherTree.Root.Clone;
  b.ClipTo(a);
  a.ClipTo(b);
  a.Invert;
  a.ClipTo(b);
  a.Invert;
  a.AllPolygons(TempList);
  b.Build(TempList);

  result:=b.Clone;
 finally
  TempList.Deinitialize;
  a.Free;
  b.Free;
 end;
end;


function TCSGBSPTree.Invert:TCSGBSPNode;
begin
 result:=Root.Clone.Invert;
end;

procedure TCSGBSPTree.GetTrianglePolygons(out OutputPolygonList:TCSGBSPPolygonList);
var i,j:longint;
    TempList:TCSGBSPPolygonList;
    Polygon:TCSGBSPPolygon;
begin
 TempList.Initialize;
 Polygon.Initialize;
 try
  Root.AllPolygons(TempList);
  SetLength(Polygon.Vertices.Vertices,3);
  Polygon.Vertices.CountVertices:=3;
  for i:=0 to TempList.CountPolygons-1 do begin
   for j:=2 to TempList.Polygons[i].Vertices.CountVertices-1 do begin
    Polygon.Vertices.Vertices[0]:=TempList.Polygons[i].Vertices.Vertices[0];
    Polygon.Vertices.Vertices[1]:=TempList.Polygons[i].Vertices.Vertices[j-1];
    Polygon.Vertices.Vertices[2]:=TempList.Polygons[i].Vertices.Vertices[j];
    Polygon.CalculateProperties;
    OutputPolygonList.Add(Polygon.Clone);
   end;
  end;
 finally
  Polygon.Deinitialize;
  TempList.Deinitialize;
 end;
end;

end.