LZScene

1
//
2
// This unit is part of the GLScene Engine https://github.com/glscene
3
//
4
{
5
   Enhanced silhouette classes.
6

7
   Introduces more evolved/specific silhouette generation and management
8
   classes.
9

10
   CAUTION : both connectivity classes leak memory.
11

12
	 History :  
13
       04/11/10 - DaStr - Restored Delphi5 and Delphi6 compatibility  
14
       28/03/07 - DaStr - Renamed parameters in some methods
15
                             (thanks Burkhard Carstens) (Bugtracker ID = 1678658)
16
       16/03/07 - DaStr - Added explicit pointer dereferencing
17
                             (thanks Burkhard Carstens) (Bugtracker ID = 1678644)
18
       26/09/03 - EG - Improved performance of TConnectivity data construction
19
       19/06/03 - MF - Split up Connectivity classes
20
       10/06/03 - EG - Creation (based on code from Mattias Fagerlund)
21
    
22
}
23
unit GLSilhouette;
24

25
interface
26

27
{$I GLScene.inc}
28

29
uses Classes, GLVectorGeometry, GLVectorLists, GLCrossPlatform;
30

31
type
32
   // TGLSilhouetteStyle
33
   //
34
   TGLSilhouetteStyle = (ssOmni, ssParallel);
35

36
   // TGLSilhouetteParameters
37
   //
38
   { Silouhette generation parameters.
39
      SeenFrom and LightDirection are expected in local coordinates. }
40
   TGLSilhouetteParameters = packed record
41
      SeenFrom, LightDirection : TAffineVector;
42
      Style : TGLSilhouetteStyle;
43
      CappingRequired : Boolean;
44
   end;
45

46
   // TGLSilhouette
47
   //
48
   { Base class storing a volume silhouette.
49
      Made of a set of indexed vertices defining an outline, and another set
50
      of indexed vertices defining a capping volume. Coordinates system
51
      is the object's unscaled local coordinates system. 
52
      This is the base class, you can use the TGLSilhouette subclass if you
53
      need some helper methods for generating the indexed sets. }
54
   TGLSilhouette = class
55
      private
56
          
57
         FVertices : TVectorList;
58
         FIndices : TIntegerList;
59
         FCapIndices : TIntegerList;
60
         FParameters : TGLSilhouetteParameters;
61

62
      protected
63
          
64
         procedure SetIndices(const value : TIntegerList);
65
         procedure SetCapIndices(const value : TIntegerList);
66
         procedure SetVertices(const value : TVectorList);
67

68
      public
69
          
70
         constructor Create; virtual;
71
         destructor Destroy; override;
72

73
         property Parameters : TGLSilhouetteParameters read FParameters write FParameters;
74
         property Vertices : TVectorList read FVertices write SetVertices;
75
         property Indices : TIntegerList read FIndices write SetIndices;
76
         property CapIndices : TIntegerList read FCapIndices write SetCapIndices;
77

78
         procedure Flush;
79
         procedure Clear;
80

81
         procedure ExtrudeVerticesToInfinity(const origin : TAffineVector);
82

83
         { Adds an edge (two vertices) to the silhouette.
84
            If TightButSlow is true, no vertices will be doubled in the
85
            silhouette list. This should only be used when creating re-usable
86
            silhouettes, because it's much slower. }
87
         procedure AddEdgeToSilhouette(const v0, v1 : TAffineVector;
88
                                       tightButSlow : Boolean);
89
         procedure AddIndexedEdgeToSilhouette(const Vi0, Vi1 : integer);
90

91
         { Adds a capping triangle to the silhouette.
92
            If TightButSlow is true, no vertices will be doubled in the
93
            silhouette list. This should only be used when creating re-usable
94
            silhouettes, because it's much slower. }
95
         procedure AddCapToSilhouette(const v0, v1, v2 : TAffineVector;
96
                                      tightButSlow : Boolean);
97

98
         procedure AddIndexedCapToSilhouette(const vi0, vi1, vi2 : Integer);
99
   end;
100

101
   // TBaseConnectivity
102
   //
103
   TBaseConnectivity = class
104
       protected
105
          FPrecomputeFaceNormal: boolean;
106

107
          function GetEdgeCount: integer; virtual;
108
          function GetFaceCount: integer; virtual;
109
       public
110
          property EdgeCount : integer read GetEdgeCount;
111
          property FaceCount : integer read GetFaceCount;
112

113
          property PrecomputeFaceNormal : boolean read FPrecomputeFaceNormal;
114
          procedure CreateSilhouette(const ASilhouetteParameters : TGLSilhouetteParameters; var ASilhouette : TGLSilhouette; AddToSilhouette : boolean); virtual;
115

116
          constructor Create(APrecomputeFaceNormal : boolean); virtual;
117
   end;
118

119
   // TConnectivity
120
   //
121
   TConnectivity = class(TBaseConnectivity)
122
       protected
123
          { All storage of faces and adges are cut up into tiny pieces for a reason,
124
          it'd be nicer with Structs or classes, but it's actually faster this way.
125
          The reason it's faster is because of less cache overwrites when we only
126
          access a tiny bit of a triangle (for instance), not all data.}
127
          FEdgeVertices : TIntegerList;
128
          FEdgeFaces : TIntegerList;
129
          FFaceVisible : TByteList;
130
          FFaceVertexIndex : TIntegerList;
131
          FFaceNormal : TAffineVectorList;
132
          FVertexMemory : TIntegerList;
133
          FVertices : TAffineVectorList;
134

135
          function GetEdgeCount: integer; override;
136
          function GetFaceCount: integer; override;
137

138
          function ReuseOrFindVertexID(const seenFrom : TAffineVector;
139
                     aSilhouette : TGLSilhouette; index : Integer) : Integer;
140
       public
141
          { Clears out all connectivity information. }
142
          procedure Clear; virtual;
143

144
          procedure CreateSilhouette(const silhouetteParameters : TGLSilhouetteParameters; var aSilhouette : TGLSilhouette; AddToSilhouette : boolean); override;
145

146
          function AddIndexedEdge(vertexIndex0, vertexIndex1 : integer; FaceID: integer) : integer;
147
          function AddIndexedFace(vi0, vi1, vi2 : integer) : integer;
148

149
          function AddFace(const vertex0, vertex1, vertex2 : TAffineVector) : integer;
150
          function AddQuad(const vertex0, vertex1, vertex2, vertex3 : TAffineVector) : integer;
151

152
          property EdgeCount : integer read GetEdgeCount;
153
          property FaceCount : integer read GetFaceCount;
154

155
          constructor Create(APrecomputeFaceNormal : boolean); override;
156
          destructor Destroy; override;
157
   end;
158

159
//-------------------------------------------------------------
160
//-------------------------------------------------------------
161
//-------------------------------------------------------------
162
implementation
163

164
//-------------------------------------------------------------
165
//-------------------------------------------------------------
166
//-------------------------------------------------------------
167

168
uses SysUtils;
169

170
// ------------------
171
// ------------------ TGLSilhouette ------------------
172
// ------------------
173

174
// Create
175
//
176
constructor TGLSilhouette.Create;
177
begin
178
   inherited;
179
   FVertices:=TVectorList.Create;
180
   FIndices:=TIntegerList.Create;
181
   FCapIndices:=TIntegerList.Create;
182
end;
183

184
// Destroy
185
//
186
destructor TGLSilhouette.Destroy;
187
begin
188
   FCapIndices.Free;
189
   FIndices.Free;
190
   FVertices.Free;
191
   inherited;
192
end;
193

194
// SetIndices
195
//
196
procedure TGLSilhouette.SetIndices(const value : TIntegerList);
197
begin
198
   FIndices.Assign(value);
199
end;
200

201
// SetCapIndices
202
//
203
procedure TGLSilhouette.SetCapIndices(const value : TIntegerList);
204
begin
205
   FCapIndices.Assign(value);
206
end;
207

208
// SetVertices
209
//
210
procedure TGLSilhouette.SetVertices(const value : TVectorList);
211
begin
212
   FVertices.Assign(value);
213
end;
214

215
// Flush
216
//
217
procedure TGLSilhouette.Flush;
218
begin
219
   FVertices.Flush;
220
   FIndices.Flush;
221
   FCapIndices.Flush;
222
end;
223

224
// Clear
225
//
226
procedure TGLSilhouette.Clear;
227
begin
228
   FVertices.Clear;
229
   FIndices.Clear;
230
   FCapIndices.Clear;
231
end;
232

233
// ExtrudeVerticesToInfinity
234
//
235
procedure TGLSilhouette.ExtrudeVerticesToInfinity(const origin : TAffineVector);
236
var
237
   i, nv, ni, nc, k : Integer;
238
   vList, vListN : PVectorArray;
239
   iList, iList2 : PIntegerArray;
240
begin
241
   // extrude vertices
242
   nv:=Vertices.Count;
243
   Vertices.Count:=2*nv;
244
   vList:=Vertices.List;
245
   vListN:=@vList[nv];
246
   for i:=0 to nv-1 do begin
247
      vListN^[i].V[3]:=0;
248
      VectorSubtract(PAffineVector(@vList[i])^, origin, PAffineVector(@vListN[i])^);
249
   end;
250
   // change silhouette indices to quad indices
251
   ni:=Indices.Count;
252
   Indices.Count:=2*ni;
253
   iList:=Indices.List;
254
   i:=ni-2; while i>=0 do begin
255
      iList2:=@iList^[2*i];
256
      iList2^[0]:=iList^[i];
257
      iList2^[1]:=iList^[i+1];
258
      iList2^[2]:=iList^[i+1]+nv;
259
      iList2^[3]:=iList^[i]+nv;
260
      Dec(i, 2);
261
   end;
262
   // add extruded triangles to capIndices
263
   nc:=CapIndices.Count;
264
   CapIndices.Capacity:=2*nc;
265
   iList:=CapIndices.List;
266
   for i:=nc-1 downto 0 do begin
267
      k:=iList^[i];
268
      CapIndices.Add(k);
269
      iList^[i]:=k+nv;
270
   end;
271
end;
272

273
// ------------------
274
// ------------------ TGLSilhouette ------------------
275
// ------------------
276

277
// AddEdgeToSilhouette
278
//
279
procedure TGLSilhouette.AddEdgeToSilhouette(const v0, v1 : TAffineVector;
280
                                            tightButSlow : Boolean);
281
begin
282
   if tightButSlow then
283
      Indices.Add(Vertices.FindOrAddPoint(v0),
284
                  Vertices.FindOrAddPoint(v1))
285
   else Indices.Add(Vertices.Add(v0, 1),
286
                    Vertices.Add(v1, 1));
287
end;
288

289
// AddIndexedEdgeToSilhouette
290
//
291
procedure TGLSilhouette.AddIndexedEdgeToSilhouette(const Vi0, Vi1 : integer);
292

293
begin
294
   Indices.Add(Vi0, Vi1);
295
end;
296

297
// AddCapToSilhouette
298
//
299
procedure TGLSilhouette.AddCapToSilhouette(const v0, v1, v2 : TAffineVector;
300
                                           tightButSlow : Boolean);
301
begin
302
   if tightButSlow then
303
      CapIndices.Add(Vertices.FindOrAddPoint(v0),
304
                     Vertices.FindOrAddPoint(v1),
305
                     Vertices.FindOrAddPoint(v2))
306
   else CapIndices.Add(Vertices.Add(v0, 1),
307
                       Vertices.Add(v1, 1),
308
                       Vertices.Add(v2, 1));
309
end;
310

311
// AddIndexedCapToSilhouette
312
//
313
procedure TGLSilhouette.AddIndexedCapToSilhouette(const vi0, vi1, vi2 : Integer);
314
begin
315
  CapIndices.Add(vi0, vi1, vi2);
316
end;
317

318
// ------------------
319
// ------------------ TBaseConnectivity ------------------
320
// ------------------
321

322
{ TBaseConnectivity }
323

324
constructor TBaseConnectivity.Create(APrecomputeFaceNormal: boolean);
325
begin
326
  FPrecomputeFaceNormal := APrecomputeFaceNormal;
327
end;
328

329
procedure TBaseConnectivity.CreateSilhouette(const ASilhouetteParameters : TGLSilhouetteParameters; var ASilhouette : TGLSilhouette; AddToSilhouette : boolean);
330
begin
331
  // Purely virtual!
332
end;
333

334
// ------------------
335
// ------------------ TConnectivity ------------------
336
// ------------------
337

338
function TBaseConnectivity.GetEdgeCount: integer;
339
begin
340
  result := 0;
341
end;
342

343
function TBaseConnectivity.GetFaceCount: integer;
344
begin
345
  result := 0;
346
end;
347

348
{ TConnectivity }
349

350
constructor TConnectivity.Create(APrecomputeFaceNormal : boolean);
351
begin
352
  FFaceVisible := TByteList.Create;
353

354
  FFaceVertexIndex := TIntegerList.Create;
355
  FFaceNormal := TAffineVectorList.Create;
356

357
  FEdgeVertices := TIntegerList.Create;
358
  FEdgeFaces := TIntegerList.Create;
359

360
  FPrecomputeFaceNormal := APrecomputeFaceNormal;
361

362
  FVertexMemory := TIntegerList.Create;
363

364
  FVertices := TAffineVectorList.Create;
365
end;
366

367
destructor TConnectivity.Destroy;
368
begin
369
  Clear;
370

371
  FFaceVisible.Free;
372
  FFaceVertexIndex.Free;
373
  FFaceNormal.Free;
374

375
  FEdgeVertices.Free;
376
  FEdgeFaces.Free;
377

378
  FVertexMemory.Free;
379

380
  if Assigned(FVertices) then
381
    FVertices.Free;
382

383
  inherited;
384
end;
385

386
procedure TConnectivity.Clear;
387
begin
388
  FEdgeVertices.Clear;
389
  FEdgeFaces.Clear;
390
  FFaceVisible.Clear;
391
  FFaceVertexIndex.Clear;
392
  FFaceNormal.Clear;
393
  FVertexMemory.Clear;
394

395
  if FVertices<>nil then
396
    FVertices.Clear;
397
end;
398

399
// CreateSilhouette
400
//
401
procedure TConnectivity.CreateSilhouette(
402
            const silhouetteParameters : TGLSilhouetteParameters;
403
            var aSilhouette : TGLSilhouette; addToSilhouette : boolean);
404
var
405
   i : Integer;
406
   vis : PIntegerArray;
407
   tVi0, tVi1 : Integer;
408
   faceNormal : TAffineVector;
409
   face0ID, face1ID : Integer;
410
   faceIsVisible : Boolean;
411
   verticesList : PAffineVectorArray;
412
begin
413
   if not Assigned(aSilhouette) then
414
      aSilhouette:=TGLSilhouette.Create
415
   else if not AddToSilhouette then
416
      aSilhouette.Flush;
417

418
   // Clear the vertex memory
419
   FVertexMemory.Flush;
420

421
   // Update visibility information for all Faces
422
   vis:=FFaceVertexIndex.List;
423
   for i:=0 to FaceCount-1 do begin
424
      if FPrecomputeFaceNormal then
425
         faceIsVisible:=(PointProject(silhouetteParameters.SeenFrom,
426
                                      FVertices.List^[vis^[0]],
427
                                      FFaceNormal.List^[i])
428
                         >=0)
429
      else begin
430
         verticesList:=FVertices.List;
431
         faceNormal:=CalcPlaneNormal(verticesList^[vis^[0]],
432
                                     verticesList^[vis^[1]],
433
                                     verticesList^[vis^[2]]);
434
         faceIsVisible:=(PointProject(silhouetteParameters.SeenFrom,
435
                                      FVertices.List^[vis^[0]], faceNormal)
436
                         >=0);
437
      end;
438

439
      FFaceVisible[i]:=Byte(faceIsVisible);
440

441
      if (not faceIsVisible) and silhouetteParameters.CappingRequired then
442
         aSilhouette.CapIndices.Add(ReuseOrFindVertexID(silhouetteParameters.SeenFrom, aSilhouette, vis^[0]),
443
                                    ReuseOrFindVertexID(silhouetteParameters.SeenFrom, aSilhouette, vis^[1]),
444
                                    ReuseOrFindVertexID(silhouetteParameters.SeenFrom, aSilhouette, vis^[2]));
445
      vis:=@vis[3];      
446
   end;
447

448
   for i:=0 to EdgeCount-1 do  begin
449
      face0ID:=FEdgeFaces[i*2+0];
450
      face1ID:=FEdgeFaces[i*2+1];
451

452
      if (face1ID=-1) or (FFaceVisible.List^[face0ID]<>FFaceVisible.List^[face1ID]) then begin
453
         // Retrieve the two vertice values add add them to the Silhouette list
454
         vis:=@FEdgeVertices.List[i*2];
455

456
         // In this moment, we _know_ what vertex id the vertex had in the old
457
         // mesh. We can remember this information and re-use it for a speedup
458
         if FFaceVisible.List^[Face0ID]=0 then begin
459
            tVi0 := ReuseOrFindVertexID(silhouetteParameters.SeenFrom, aSilhouette, vis^[0]);
460
            tVi1 := ReuseOrFindVertexID(silhouetteParameters.SeenFrom, aSilhouette, vis^[1]);
461
            aSilhouette.Indices.Add(tVi0, tVi1);
462
         end else if Face1ID>-1 then begin
463
            tVi0 := ReuseOrFindVertexID(silhouetteParameters.SeenFrom, aSilhouette, vis^[0]);
464
            tVi1 := ReuseOrFindVertexID(silhouetteParameters.SeenFrom, aSilhouette, vis^[1]);
465
            aSilhouette.Indices.Add(tVi1, tVi0);
466
         end;
467
      end;
468
   end;
469
end;
470

471
function TConnectivity.GetEdgeCount: integer;
472
begin
473
  result := FEdgeVertices.Count div 2;
474
end;
475

476
function TConnectivity.GetFaceCount: integer;
477
begin
478
  result := FFaceVisible.Count;
479
end;
480

481
// ReuseOrFindVertexID
482
//
483
function TConnectivity.ReuseOrFindVertexID(
484
     const seenFrom : TAffineVector; aSilhouette : TGLSilhouette; index : Integer) : Integer;
485
var
486
   pMemIndex : PInteger;
487
   memIndex, i : Integer;
488
   oldCount : Integer;
489
   list : PIntegerArray;
490
begin
491
   if index>=FVertexMemory.Count then begin
492
      oldCount:=FVertexMemory.Count;
493
      FVertexMemory.Count:=index+1;
494

495
      list:=FVertexMemory.List;
496
      for i:=OldCount to FVertexMemory.Count-1 do
497
         list^[i]:=-1;
498
   end;
499

500
   pMemIndex:=@FVertexMemory.List[index];
501

502
   if pMemIndex^=-1 then begin
503
      // Add the "near" vertex
504
      memIndex:=aSilhouette.Vertices.Add(FVertices.List^[index], 1);
505
      pMemIndex^:=memIndex;
506
      Result:=memIndex;
507
   end else Result:=pMemIndex^;
508
end;
509

510
// AddIndexedEdge
511
//
512
function TConnectivity.AddIndexedEdge(
513
            vertexIndex0, vertexIndex1 : Integer; faceID : Integer) : Integer;
514
var
515
   i : Integer;
516
   edgesVertices : PIntegerArray;
517
begin
518
   // Make sure that the edge doesn't already exists
519
   edgesVertices:=FEdgeVertices.List;
520
   for i:=0 to EdgeCount-1 do begin
521
      // Retrieve the two vertices in the edge
522
      if    ((edgesVertices^[0]=vertexIndex0) and (edgesVertices^[1]=vertexIndex1))
523
         or ((edgesVertices^[0]=vertexIndex1) and (edgesVertices^[1]=vertexIndex0)) then begin
524
         // Update the second Face of the edge and we're done (this _MAY_
525
         // overwrite a previous Face in a broken mesh)
526
         FEdgeFaces[i*2+1]:=faceID;
527
         Result:=i*2+1;
528
         Exit;
529
      end;
530
      edgesVertices:=@edgesVertices[2];
531
   end;
532

533
   // No edge was found, create a new one
534
   FEdgeVertices.Add(vertexIndex0, vertexIndex1);
535
   FEdgeFaces.Add(faceID, -1);
536

537
   Result:=EdgeCount-1;
538
end;
539

540
// AddIndexedFace
541
//
542
function TConnectivity.AddIndexedFace(vi0, vi1, vi2 : Integer) : Integer;
543
var
544
   faceID : integer;
545
begin
546
   FFaceVertexIndex.Add(vi0, vi1, vi2);
547

548
   if FPrecomputeFaceNormal then
549
      FFaceNormal.Add(CalcPlaneNormal(FVertices.List^[Vi0],
550
                                      FVertices.List^[Vi1],
551
                                      FVertices.List^[Vi2]));
552

553
   faceID:=FFaceVisible.Add(0);
554

555
   AddIndexedEdge(vi0, vi1, faceID);
556
   AddIndexedEdge(vi1, vi2, faceID);
557
   AddIndexedEdge(vi2, vi0, faceID);
558

559
   result:=faceID;
560
end;
561

562
function TConnectivity.AddFace(const Vertex0, Vertex1, Vertex2: TAffineVector) : integer;
563
var
564
  Vi0, Vi1, Vi2 : integer;
565
begin
566
  Vi0 := FVertices.FindOrAdd(Vertex0);
567
  Vi1 := FVertices.FindOrAdd(Vertex1);
568
  Vi2 := FVertices.FindOrAdd(Vertex2);
569

570
  result := AddIndexedFace(Vi0, Vi1, Vi2);
571
end;
572

573
function TConnectivity.AddQuad(const Vertex0, Vertex1, Vertex2,
574
  Vertex3: TAffineVector): integer;
575
var
576
  Vi0, Vi1, Vi2, Vi3 : integer;
577
begin
578
  Vi0 := FVertices.FindOrAdd(Vertex0);
579
  Vi1 := FVertices.FindOrAdd(Vertex1);
580
  Vi2 := FVertices.FindOrAdd(Vertex2);
581
  Vi3 := FVertices.FindOrAdd(Vertex3);
582

583
  // First face
584
  result := AddIndexedFace(Vi0, Vi1, Vi2);
585

586
  // Second face
587
  AddIndexedFace(Vi2, Vi3, Vi0);
588
end;
589

590
end.
591