//Filush :DDDDDDDDDDD//
//Prezentuje :PP     //
//~~~~OCTREE !!~~~~~~//

unit octree;

interface
  uses OpenGL, GL, glaux;

const
 MAX_TRIANGLES_IN_NODE = 1024;

type
 PVertex=^TVertex;
 TVertex = Record
   x,y,z: glFloat;
 end;

 PVertex3d=^TVertex3d;
 TVertex3d=record
   x,y,z: glDouble;
 end;

 PFullVertex=^TFullVertex;
 TFullVertex = record
   u,v: glFloat;
   n,ver:TVertex;
 end;

 PPolygonPointer = ^TPolygonPointer;
 TPolygonPointer = record
   v:array[0..2] of PFullVertex;
 end;

 PPolygon = ^TPolygon;
 TPolygon = record
   v:array[0..2] of TFullVertex;
 end;

 PPolygonPointerArray = ^TPolygonPointerArray;
 TPolygonPointerArray = array of TPolygonPointer;
 PPolygonArray = ^TPolygonArray;
 TPolygonArray = array of TPolygon;

//Poczatek Octree ;]
            //Główny Węzeł
 PNode = ^TNode;
 TNode = object
   polygons : array of TPolygonPointer;
   pos : TVertex3d;
   size : TVertex3d;
   numPoly : integer;
   numChildren : Byte;
   polyID : glUint;
   Mother : PNode;
   children : array of PNode;
   smallest : boolean;
   Function HowManyPolygons : Integer;
   procedure CreateVBO;
   Procedure Divide;
   Procedure DrawPolygons;
   Procedure Check;
   Procedure Draw;
   Procedure Clear;
 end;

//Główna Klasa Octree ;]

 TOctree = class
  public
   mainNode : PNode;
   Procedure DrawOctree(const drawPol, DrawNodes:Boolean; const Lighted:Boolean=TRUE; const Textured:Boolean=TRUE);
   Constructor Create(polygons:PPolygonArray);
   Destructor Destroy;
  end;

 var
  MaxPol : integer;
  AssignedPol : Integer;

implementation

uses Main;

//Konstruktor Klasy Octree
Constructor TOctree.Create(polygons : PPolygonArray);
 var
  i,j : Integer;
  maxSize,minSize : TVertex;
 begin
  maxSize := polygons^[0].v[0].ver;
  minSize := polygons^[0].v[0].ver;
   for i:=0 to High(polygons^) do
   for j:=0 to 2 do
    with polygons^[i].v[j].ver do
      begin
       if x > maxSize.x then maxSize.x :=x;
       if y > maxSize.x then maxSize.x :=y;
       if z > maxSize.x then maxSize.x :=z;

       if x < minSize.x then minSize.x :=x;
       if y < minSize.x then minSize.x :=y;
       if z < minSize.x then minSize.x :=z;
      end;
    New(MainNode);
    MainNode.pos.x :=(maxSize.x + minSize.x)/2;
    MainNode.pos.y :=(maxSize.x + minSize.x)/2;
    MainNode.pos.z :=(maxSize.x + minSize.x)/2;
    MainNode.size.x :=(maxSize.x - minSize.x)/2;
    MainNode.size.y :=(maxSize.x - minSize.x)/2;
    MainNode.size.z :=(maxSize.x - minSize.x)/2;
    MainNode.smallest := FALSE;
    SetLength(MainNode.polygons,Length(polygons^));
    for i:=0 to Length(polygons^)-1 do
    for j:=0 to 2 do
      MainNode.polygons[i].v[j] :=@polygons^[i].v[j];
    MaxPol:=Length(polygons^);
    MainNode.Divide;

 end;
//Ile wielok&#261;tów
Function TNode.HowManyPolygons: Integer;
 var
  i,j : Integer;
  Inside : boolean;
 begin
  if Length(mother^.polygons) = 0 then Exit;
  numPoly := 0;
  for i:=0 to Length(Mother^.polygons)-1 do
   begin
    Inside := FALSE;
    for j:=0 to 2 do
     with mother^.polygons[i].v[j].ver do
      begin
       if Mother^.polygons[i].v[0] <> nil then     //jezeli przynalezy do innego "liscia" ;]
        if (not Inside) and
         (x >= pos.x - size.x) and
         (y >= pos.y - size.y) and
         (z >= pos.z - size.z) and
         (x <= pos.x + size.x) and
         (y <= pos.y + size.y) and
         (z <= pos.z + size.z) then Inside := TRUE;
      end;
    if Inside then
     begin
      Inc(numPoly);
      SetLength(polygons,numPoly);
      polygons[numPoly-1] :=Mother^.polygons[i];
      Mother^.polygons[i].v[0] := nil;
     end;
   end;
  Result := numPoly;
end;

//TWORZENIE VBO
Procedure TNode.CreateVBO;
 var
  i,k: Integer;
  VBOPointer: Pointer;
  VBOVertex: PFullVertex;
   begin
    glGenBuffersARB(1, @polyID);
    glBindBufferARB(GL_ARRAY_BUFFER_ARB, polyID);
    glEnableClientState(GL_VERTEX_ARRAY);
    glBufferDataARB(GL_ARRAY_BUFFER_ARB,numPoly*3*SizeOf(TFullVertex),nil,GL_STATIC_DRAW_ARB);
    VBOPointer := glMapBufferARB(GL_ARRAY_BUFFER_ARB,GL_WRITE_ONLY_ARB);
     for i:=0 to  numPoly-1 do
     for k:=0 to 2 do
       begin
        VBOVertex :=VBOPointer;
        VBOVertex^ :=polygons[i].v[k]^;
        Inc(Integer(VBOPointer),SizeOf(TFullVertex));
       end;
     glUnMapBufferARB(GL_ARRAY_BUFFER_ARB);

    end;
//Dzielenie Drzewa ;-)
Procedure TNode.Divide;
 var
  TempNodes: array[0..7] of PNode;
  i: integer;
 begin
  for i:=0 to 7 do New(TempNodes[i]);
  numChildren:=0;

  TempNodes[0].pos.x :=pos.x - size.x/2;   //Przeliczanie osmiu wez&#322;ów (dzieci)
  TempNodes[0].pos.y :=pos.y + size.y/2;
  TempNodes[0].pos.z :=pos.z - size.z/2;

  TempNodes[1].pos.x :=pos.x - size.x/2;
  TempNodes[1].pos.y :=pos.y + size.y/2;
  TempNodes[1].pos.z :=pos.z - size.z/2;

  TempNodes[2].pos.x :=pos.x - size.x/2;
  TempNodes[2].pos.y :=pos.y + size.y/2;
  TempNodes[2].pos.z :=pos.z - size.z/2;

  TempNodes[3].pos.x :=pos.x - size.x/2;
  TempNodes[3].pos.y :=pos.y + size.y/2;
  TempNodes[3].pos.z :=pos.z - size.z/2;

  TempNodes[4].pos.x :=pos.x - size.x/2;
  TempNodes[4].pos.y :=pos.y + size.y/2;
  TempNodes[4].pos.z :=pos.z - size.z/2;

  TempNodes[5].pos.x :=pos.x - size.x/2;
  TempNodes[5].pos.y :=pos.y + size.y/2;
  TempNodes[5].pos.z :=pos.z - size.z/2;

  TempNodes[6].pos.x :=pos.x - size.x/2;
  TempNodes[6].pos.y :=pos.y + size.y/2;
  TempNodes[6].pos.z :=pos.z - size.z/2;

  TempNodes[7].pos.x :=pos.x - size.x/2;
  TempNodes[7].pos.y :=pos.y + size.y/2;
  TempNodes[7].pos.z :=pos.z - size.z/2;
  for i:=0 to 7 do
   begin
    TempNodes[i].size.x :=size.x/2;
    TempNodes[i].size.y :=size.y/2;
    TempNodes[i].size.z :=size.z/2;
    TempNodes[i].smallest :=FALSE;
    TempNodes[i].Mother :=@Self;
   end;
  for i:=0 to 7 do
   begin
    if TempNodes[i].HowManyPOlygons > 0 then
     begin
      inc(numChildren);
      SetLength(Children,numCildren);
      Children[numChildren-1] :=TempNodes[i];
       if Children[numChildren-1].numPoly < MAX_TRIANGLES_IN_NODE then
        begin
         Children[numChildren-1].smallest :=TRUE;
         Children[numChildren-1].CreateVBO;
         Inc(AssignedPol,children[numChildren-1].numPoly);
        end;
      end else Dispose(TempNodes[i]);
    end;
  for i:=0 to numChildren-1 do
   if not children[i].smallest then children[i].Divide;  //Podziel Wezly ktore sa za duze
 end;
//Rysowanie Noda ;]
Procedure TNode.Draw;
 var
  i: Integer;
 begin
  if Frunstum.IsBoxWithin(pos.x,pos.y,pos.z,size.x,size.y,size.z) = FALSE then Exit;
   with pos do
   begin
    glBegin(GL_LINES);
     glVertex3f(x-size.x,y-size.y,z-size.z);
     glVertex3f(x+size.x,y-size.y,z-size.z);
     glVertex3f(x-size.x,y+size.y,z-size.z);
     glVertex3f(x+size.x,y+size.y,z-size.z);
     glVertex3f(x-size.x,y-size.y,z+size.z);
     glVertex3f(x+size.x,y-size.y,z+size.z);
     glVertex3f(x-size.x,y+size.y,z+size.z);
     glVertex3f(x+size.x,y+size.y,z+size.z);

     glVertex3f(x+size.x,y+size.y,z+size.z);
     glVertex3f(x+size.x,y+size.y,z+size.z);
     glVertex3f(x+size.x,y+size.y,z-size.z);
     glVertex3f(x+size.x,y+size.y,z-size.z);
     glVertex3f(x-size.x,y+size.y,z+size.z);
     glVertex3f(x-size.x,y-size.y,z+size.z);
     glVertex3f(x-size.x,y+size.y,z-size.z);
     glVertex3f(x-size.x,y-size.y,z-size.z);

     glVertex3f(x+size.x,y+size.y,z+size.z);
     glVertex3f(x+size.x,y+size.y,z-size.z);
     glVertex3f(x+size.x,y-size.y,z+size.z);
     glVertex3f(x+size.x,y-size.y,z-size.z);
     glVertex3f(x-size.x,y-size.y,z+size.z);
     glVertex3f(x-size.x,y-size.y,z-size.z);
     glVertex3f(x-size.x,y+size.y,z+size.z);
     glVertex3f(x-size.x,y+size.y,z-size.z);
    glEnd;
   end;
   if Length(children) > 0 then Exit;
   glBindBufferARB(GL_ARRAY_BUFFER_ARB,polyID);
   glInterleavedArrays(GL_T2F_N3F_V3F,SizeOf(TFullVertex),nil);
    glDrawArrays(GL_TRIANGLES,0,numPoly*3);
 end;


end.