src/game/renders/opengl/r_atlas.pas

   1 (* Copyright (C)  Doom 2D: Forever Developers
   2  *
   3  * This program is free software: you can redistribute it and/or modify
   4  * it under the terms of the GNU General Public License as published by
   5  * the Free Software Foundation, version 3 of the License ONLY.
   6  *
   7  * This program is distributed in the hope that it will be useful,
   8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
   9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  10  * GNU General Public License for more details.
  11  *
  12  * You should have received a copy of the GNU General Public License
  13  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  14  *)
  15 {$INCLUDE ../../../shared/a_modes.inc}
  16 unit r_atlas;
  17
  18 interface
  19
  20   type
  21     TAtlasNode = class
  22       private
  23         left, right, up: TAtlasNode;
  24         mL, mT, mR, mB: Integer;
  25         leaf: Boolean;
  26
  27       public
  28         constructor Create;
  29         destructor Destroy; override;
  30
  31         procedure Dealloc;
  32
  33         function GetWidth (): Integer; inline;
  34         function GetHeight (): Integer; inline;
  35
  36         property x: Integer read mL;
  37         property y: Integer read mT;
  38         property width: Integer read GetWidth;
  39         property height: Integer read GetHeight;
  40
  41         property l: Integer read mL;
  42         property t: Integer read mT;
  43         property r: Integer read mR;
  44         property b: Integer read mB;
  45     end;
  46
  47     TAtlas = class
  48       public
  49         constructor Create (w, h: Integer);
  50         destructor Destroy; override; (* also destroed attached nodes *)
  51
  52         (* never free TAtlasNode directly, use Dealloc method. *)
  53         function CreateNode (): TAtlasNode; virtual; (* allocate empty node (user defined type) *)
  54         function Alloc (w, h: Integer): TAtlasNode;  (* allocate node and attach it *)
  55
  56         function GetWidth (): Integer; inline;
  57         function GetHeight (): Integer; inline;
  58
  59       private
  60         root: TAtlasNode;
  61
  62         function NewNode (p: TAtlasNode; w, h: Integer): TAtlasNode;
  63
  64       public
  65         property w: Integer read GetWidth;
  66         property h: Integer read GetHeight;
  67     end;
  68
  69
  70 implementation
  71
  72   procedure FreeNodeRecursive (n: TAtlasNode);
  73   begin
  74     if n <> nil then
  75     begin
  76       FreeNodeRecursive(n.left);
  77       FreeNodeRecursive(n.right);
  78       n.Free();
  79     end;
  80   end;
  81
  82   function IsLeafTree (n: TAtlasNode): Boolean;
  83   begin
  84     result := (n <> nil) and (n.leaf or IsLeafTree(n.left) or IsLeafTree(n.right))
  85   end;
  86
  87   (* --------- TNode --------- *)
  88
  89   constructor TAtlasNode.Create;
  90   begin
  91     inherited;
  92   end;
  93
  94   destructor TAtlasNode.Destroy;
  95     var p: TAtlasNode;
  96   begin
  97     p := self.up;
  98     if p <> nil then
  99     begin
 100       if p.left = self then
 101         p.left := nil
 102       else if p.right = self then
 103         p.right := nil
 104     end;
 105     self.up := nil;
 106     if self.left <> nil then
 107       self.left.Free;
 108     if self.right <> nil then
 109       self.right.Free;
 110     inherited;
 111   end;
 112
 113   procedure TAtlasNode.Dealloc;
 114     var p: TAtlasNode;
 115   begin
 116     ASSERT(self.leaf = true);
 117     ASSERT(self.right = nil);
 118     ASSERT(self.left = nil);
 119     self.leaf := false;
 120     p := self.up;
 121     while p <> nil do
 122     begin
 123       ASSERT(p.leaf = false);
 124       ASSERT(p.left <> nil);
 125       ASSERT(p.right <> nil);
 126       if IsLeafTree(p) = false then
 127       begin
 128         FreeNodeRecursive(p.left); p.left := nil;
 129         FreeNodeRecursive(p.right); p.right := nil;
 130         p := p.up
 131       end
 132       else
 133       begin
 134         p := nil
 135       end
 136     end
 137   end;
 138
 139   function TAtlasNode.GetWidth (): Integer;
 140   begin
 141     result := self.r - self.l + 1;
 142   end;
 143
 144   function TAtlasNode.GetHeight (): Integer;
 145   begin
 146     result := self.b - self.t + 1;
 147   end;
 148
 149   (* --------- TAtlas --------- *)
 150
 151   constructor TAtlas.Create (w, h: Integer);
 152   begin
 153     inherited Create();
 154     self.root := self.CreateNode();
 155     ASSERT(self.root <> nil);
 156     self.root.mR := w - 1;
 157     self.root.mB := h - 1;
 158   end;
 159
 160   destructor TAtlas.Destroy;
 161   begin
 162     FreeNodeRecursive(self.root.left);
 163     FreeNodeRecursive(self.root.right);
 164     inherited;
 165   end;
 166
 167   function TAtlas.GetWidth (): Integer;
 168   begin
 169     result := self.root.r {- self.root.l} + 1;
 170   end;
 171
 172   function TAtlas.GetHeight (): Integer;
 173   begin
 174     result := self.root.b {- self.root.t} + 1;
 175   end;
 176
 177   function TAtlas.CreateNode (): TAtlasNode;
 178   begin
 179     result := TAtlasNode.Create()
 180   end;
 181
 182   function TAtlas.NewNode (p: TAtlasNode; w, h: Integer): TAtlasNode;
 183     var n: TAtlasNode;
 184   begin
 185     ASSERT(p <> nil);
 186     ASSERT(w > 0);
 187     ASSERT(h > 0);
 188     if p.left <> nil then
 189     begin
 190       ASSERT(p.right <> nil);
 191       n := NewNode(p.left, w, h);
 192       if n = nil then
 193         n := NewNode(p.right, w, h);
 194       result := n;
 195     end
 196     else if p.leaf or (p.width < w) or (p.height < h) then
 197     begin
 198       result := nil;
 199     end
 200     else if (p.width = w) and (p.height = h) then
 201     begin
 202       p.leaf := true;
 203       result := p;
 204     end
 205     else
 206     begin
 207       p.left := self.CreateNode();
 208       p.right := self.CreateNode();
 209       if (p.left = nil) or (p.right = nil) then
 210       begin
 211         (* failed to allocate nodes *)
 212         if p.left <> nil then
 213           p.left.Free();
 214         if p.right <> nil then
 215           p.right.Free();
 216         p.left := nil;
 217         p.right := nil;
 218         result := nil;
 219       end
 220       else
 221       begin
 222         p.left.up := p;
 223         p.right.up := p;
 224         if p.width - w > p.height - h then
 225         begin
 226           p.left.mL := p.l;
 227           p.left.mT := p.t;
 228           p.left.mR := p.l + w - 1;
 229           p.left.mB := p.b;
 230           p.right.mL := p.l + w;
 231           p.right.mT := p.t;
 232           p.right.mR := p.r;
 233           p.right.mB := p.b;
 234         end
 235         else
 236         begin
 237           p.left.mL := p.l;
 238           p.left.mt := p.t;
 239           p.left.mR := p.r;
 240           p.left.mB := p.t + h - 1;
 241           p.right.mL := p.l;
 242           p.right.mT := p.t + h;
 243           p.right.mR := p.r;
 244           p.right.mB := p.b;
 245         end;
 246         result := NewNode(p.left, w, h);
 247       end
 248     end
 249   end;
 250
 251   function TAtlas.Alloc (w, h: Integer): TAtlasNode;
 252     var n: TAtlasNode;
 253   begin
 254     ASSERT(w > 0);
 255     ASSERT(h > 0);
 256     n := nil;
 257     if (w <= self.w) and (h <= self.h) then
 258     begin
 259       n := NewNode(self.root, w, h);
 260       if n <> nil then
 261         ASSERT(n.leaf);
 262     end;
 263     result := n
 264   end;
 265
 266 end.