CaSHL/Init1.cpp

   1 /*
   2 Cafu Engine, http://www.cafu.de/
   3 Copyright (c) Carsten Fuchs and other contributors.
   4 This project is licensed under the terms of the MIT license.
   5 */
   6
   7 // Initialisiert die FacePVS-Matrix, für die nach Ausführung dieser Funktion folgende Eigenschaften gelten:
   8 //
   9 //     1) FacePVS[i][j]==     NO_VISIBILITY   iff   Face[i] can  NOT        see Face[j]
  10 //        FacePVS[i][j]==PARTIAL_VISIBILITY   iff   Face[i] can (PARTIALLY) see Face[j]
  11 //        FacePVS[i][j]==   FULL_VISIBILITY   iff   Face[i] can  FULLY      see Face[j]
  12 //
  13 //     2) FacePVS[i][i]==NO_VISIBILITY für alle i (NO_VISIBILITY auf der Diagonalen), d.h. keine Face kann sich selbst sehen!
  14 //
  15 //     3) FacePVS[i][j]==FacePVS[j][i], d.h. die FacePVS-Matrix ist symmetrisch
  16 //
  17 void InitializeFacePVSMatrix(const CaSHLWorldT& CaSHLWorld, const bool UseFullVis)
  18 {
  19     const cf::SceneGraph::BspTreeNodeT& Map=CaSHLWorld.GetBspTree();
  20
  21     printf("\n%-50s %s\n", "*** Initialize FacePVS matrix ***", GetTimeSinceProgramStart());
  22
  23
  24     // 1. Allokiere neuen Speicher für die FacePVS-Matrix
  25     FacePVS.Clear();
  26     FacePVS.PushBackEmpty(Map.FaceChildren.Size());
  27
  28     for (unsigned long Face1Nr=0; Face1Nr<Map.FaceChildren.Size(); Face1Nr++) FacePVS[Face1Nr].PushBackEmpty(Map.FaceChildren.Size());
  29
  30     printf("Faces (n):                                   %10lu\n", Map.FaceChildren.Size());
  31     printf("Bytes allocated for FacePVS matrix (n^2):    %10lu\n", Map.FaceChildren.Size()*Map.FaceChildren.Size());
  32
  33
  34     // 2. Initialisiere alle Elemente mit NO_VISIBILITY
  35     for (unsigned long Face1Nr=0; Face1Nr<Map.FaceChildren.Size(); Face1Nr++)
  36         for (unsigned long Face2Nr=0; Face2Nr<Map.FaceChildren.Size(); Face2Nr++)
  37             FacePVS[Face1Nr][Face2Nr]=NO_VISIBILITY;
  38
  39
  40     // 3. Setze nun die aus dem Map.PVS abgeleiteten Werte ein.
  41     //    Für alle Leaves L, markiere also alle Faces aller Leaves im PVS von L als sichtbar von allen Faces von L aus.
  42     //    Wichtig: Dies handhabt auch diejenigen Faces richtig, die größer sind als ein Leaf, also mehrere Leaves begrenzen!
  43     ArrayT<bool> FaceSetBool;
  44     FaceSetBool.PushBackEmpty(Map.FaceChildren.Size());
  45
  46     for (unsigned long Leaf1Nr=0; Leaf1Nr<Map.Leaves.Size(); Leaf1Nr++)
  47     {
  48         for (unsigned long Face1Nr=0; Face1Nr<Map.FaceChildren.Size(); Face1Nr++) FaceSetBool[Face1Nr]=false;
  49
  50         // Setze für alle Faces F aller Leaves im PVS von Leaf1Nr FaceSetBool[F] auf true.
  51         // Wichtig: Auch Leaf1Nr liegt im (eigenen) PVS von Leaf1Nr!
  52         for (unsigned long Leaf2Nr=0; Leaf2Nr<Map.Leaves.Size(); Leaf2Nr++)
  53         {
  54             unsigned long PVSTotalBitNr=Leaf1Nr*Map.Leaves.Size()+Leaf2Nr;
  55             unsigned long PVS_W32_Nr   =PVSTotalBitNr >> 5;
  56
  57             if ((Map.PVS[PVS_W32_Nr] >> (PVSTotalBitNr & 31)) & 1)
  58                 for (unsigned long Face2Nr=0; Face2Nr<Map.Leaves[Leaf2Nr].FaceChildrenSet.Size(); Face2Nr++)
  59                     FaceSetBool[Map.Leaves[Leaf2Nr].FaceChildrenSet[Face2Nr]]=true;
  60         }
  61
  62         ArrayT<unsigned long> FaceSetList;
  63         for (unsigned long Face1Nr=0; Face1Nr<Map.FaceChildren.Size(); Face1Nr++) if (FaceSetBool[Face1Nr]) FaceSetList.PushBack(Face1Nr);
  64
  65         // Markiere für alle Faces F im Leaf1Nr, daß alle Faces F' aller Leaves im PVS von Leaf1Nr von F aus sichtbar sind,
  66         // aber auch die umgekehrte Sichtbarkeit, also daß F von F' aus sichtbar ist, um Symmetrie zu garantieren.
  67         for (unsigned long Face1Nr=0; Face1Nr<Map.Leaves[Leaf1Nr].FaceChildrenSet.Size(); Face1Nr++)
  68             for (unsigned long Face2Nr=0; Face2Nr<FaceSetList.Size(); Face2Nr++)
  69             {
  70                 FacePVS[Map.Leaves[Leaf1Nr].FaceChildrenSet[Face1Nr]][FaceSetList[Face2Nr]]=PARTIAL_VISIBILITY;
  71                 FacePVS[FaceSetList[Face2Nr]][Map.Leaves[Leaf1Nr].FaceChildrenSet[Face1Nr]]=PARTIAL_VISIBILITY;
  72             }
  73     }
  74
  75
  76     // 4. Für die Statistik: Zähle die Anzahl der PARTIAL_VISIBILITY-Elemente in der FacePVS-Matrix
  77     unsigned long VisCount=0;
  78
  79     for (unsigned long Face1Nr=0; Face1Nr<Map.FaceChildren.Size(); Face1Nr++)
  80         for (unsigned long Face2Nr=0; Face2Nr<Map.FaceChildren.Size(); Face2Nr++)
  81             if (FacePVS[Face1Nr][Face2Nr]==PARTIAL_VISIBILITY) VisCount++;
  82
  83     if (VisCount==Map.FaceChildren.Size()*Map.FaceChildren.Size())
  84     {
  85         printf("\nWARNING: NON-TRIVIAL PVS INFORMATION REQUIRED FOR SENSIBLE LIGHTING!\n");
  86         printf("   [You may choose to ignore this warning, but lighting will take much longer.]\n\n");
  87     }
  88     printf("# matrix elements set to 'PARTIAL':          %10lu  (%7.3f%%)\n", VisCount, 100.0*double(VisCount)/double(Map.FaceChildren.Size()*Map.FaceChildren.Size()));
  89
  90
  91     // 5. Optimierung der FacePVS-Matrix, Teil 1:
  92     //    Beim Map.PVS handelt es sich um den Leaf-Allgemeinfall. Nutze hier den Spezialfall aus, daß wir nur die Sichtbarkeit
  93     //    von einer *Face* aus bestimmen wollen und die Tatsache, daß alles unterhalb oder in der Ebene einer Face F nicht von
  94     //    F aus sichtbar sein kann! (Das heißt insbesondere auch, daß F sich nicht selbst sehen kann!)
  95     for (unsigned long Face1Nr=0; Face1Nr<Map.FaceChildren.Size(); Face1Nr++)
  96     {
  97         // Zuerst (wegen oben) muß eine Face sich noch selbst sehen können
  98         if (FacePVS[Face1Nr][Face1Nr]==NO_VISIBILITY) printf("WARNING: FacePVS[i][i]==NO_VISIBILITY\n");
  99         FacePVS[Face1Nr][Face1Nr]=NO_VISIBILITY;
 100
 101         for (unsigned long Face2Nr=Face1Nr+1; Face2Nr<Map.FaceChildren.Size(); Face2Nr++)
 102             if (FacePVS[Face1Nr][Face2Nr]==PARTIAL_VISIBILITY || FacePVS[Face2Nr][Face1Nr]==PARTIAL_VISIBILITY)
 103             {
 104                 Polygon3T<double>::SideT Side1=Map.FaceChildren[Face2Nr]->Polygon.WhatSideSimple(Map.FaceChildren[Face1Nr]->Polygon.Plane, MapT::RoundEpsilon);
 105                 Polygon3T<double>::SideT Side2=Map.FaceChildren[Face1Nr]->Polygon.WhatSideSimple(Map.FaceChildren[Face2Nr]->Polygon.Plane, MapT::RoundEpsilon);
 106
 107                 if (FacePVS[Face1Nr][Face2Nr]!=FacePVS[Face2Nr][Face1Nr]) printf("WARNING: FacePVS[i][j]!=FacePVS[j][i]\n");
 108
 109                 if (Side1!=Polygon3T<double>::Front && Side1!=Polygon3T<double>::Both &&
 110                     Side2!=Polygon3T<double>::Front && Side2!=Polygon3T<double>::Both)
 111                 {
 112                     FacePVS[Face1Nr][Face2Nr]=NO_VISIBILITY;
 113                     FacePVS[Face2Nr][Face1Nr]=NO_VISIBILITY;
 114                 }
 115             }
 116     }
 117
 118
 119     // 6. Zähle die Anzahl der PARTIAL_VISIBILITY-Elemente in der FacePVS-Matrix nach erster Optimierung
 120     VisCount=0;
 121
 122     for (unsigned long Face1Nr=0; Face1Nr<Map.FaceChildren.Size(); Face1Nr++)
 123         for (unsigned long Face2Nr=0; Face2Nr<Map.FaceChildren.Size(); Face2Nr++)
 124             if (FacePVS[Face1Nr][Face2Nr]==PARTIAL_VISIBILITY) VisCount++;
 125
 126     printf("Still 'PARTIAL' after 1st optimization pass: %10lu  (%7.3f%%)\n", VisCount, 100.0*double(VisCount)/double(Map.FaceChildren.Size()*Map.FaceChildren.Size()));
 127
 128
 129     // 7. Optimierung der FacePVS-Matrix, Teil 2:
 130     //    Faces ohne Lightmap (z.B. mit Sky-Materials) emitieren kein Licht (Initialisierung des Sonnenlichts folgt unten)
 131     //    und reflektieren auch keins. Deshalb können sie als "unsichtbar" aus dem FacePVS entfernt werden!
 132     for (unsigned long Face1Nr=0; Face1Nr<Map.FaceChildren.Size(); Face1Nr++)
 133     {
 134         if (!Map.FaceChildren[Face1Nr]->Material->UsesGeneratedSHLMap())
 135         {
 136             printf("WARNING: Got a patch mesh that doesn't use a generated SHL map! Material name is \"%s\".\n", Map.FaceChildren[Face1Nr]->Material->Name.c_str());
 137
 138             for (unsigned long Face2Nr=0; Face2Nr<Map.FaceChildren.Size(); Face2Nr++)
 139             {
 140                 FacePVS[Face1Nr][Face2Nr]=NO_VISIBILITY;
 141                 FacePVS[Face2Nr][Face1Nr]=NO_VISIBILITY;
 142             }
 143         }
 144     }
 145
 146
 147     // 8. Zähle die Anzahl der PARTIAL_VISIBILITY-Elemente in der FacePVS-Matrix nach zweiter Optimierung
 148     VisCount=0;
 149
 150     for (unsigned long Face1Nr=0; Face1Nr<Map.FaceChildren.Size(); Face1Nr++)
 151         for (unsigned long Face2Nr=0; Face2Nr<Map.FaceChildren.Size(); Face2Nr++)
 152             if (FacePVS[Face1Nr][Face2Nr]==PARTIAL_VISIBILITY) VisCount++;
 153
 154     printf("Still 'PARTIAL' after 2nd optimization pass: %10lu  (%7.3f%%)\n", VisCount, 100.0*double(VisCount)/double(Map.FaceChildren.Size()*Map.FaceChildren.Size()));
 155     printf("    (%.2f faces visible in average from each face.)\n", double(VisCount)/double(Map.FaceChildren.Size()));
 156
 157
 158     // 9. BIS JETZT: Nur NO_VISIBILITY- und PARTIAL_VISIBILITY-Einträge.
 159     //    JETZT NEU: Bestimme, welche der PARTIAL_VISIBILITY-Einträge sogar FULL_VISIBILITY-Einträge sind.
 160     ArrayT< BoundingBox3T<double> > FaceBBs;
 161
 162     // Zuerst mal Bounding-Boxes für alle Faces erstellen.
 163     for (unsigned long Face1Nr=0; Face1Nr<Map.FaceChildren.Size(); Face1Nr++)
 164         FaceBBs.PushBack(BoundingBox3T<double>(Map.FaceChildren[Face1Nr]->Polygon.Vertices));
 165
 166     for (unsigned long Face1Nr=UseFullVis ? 0 : Map.FaceChildren.Size(); Face1Nr<Map.FaceChildren.Size(); Face1Nr++)
 167     {
 168         printf("%5.1f%%\r", (double)Face1Nr/Map.FaceChildren.Size()*100.0);
 169         fflush(stdout);
 170
 171         for (unsigned long Face2Nr=Face1Nr+1; Face2Nr<Map.FaceChildren.Size(); Face2Nr++)
 172         {
 173             // Faces, die sich nicht mal teilweise sehen können, können sich erst recht nicht komplett sehen.
 174             if (FacePVS[Face1Nr][Face2Nr]==NO_VISIBILITY) continue;
 175
 176             // Faces, die sich "schon aus sich heraus" (T-artige Anordnung) nur teilweise sehen können, können sich nicht komplett sehen.
 177             if (Map.FaceChildren[Face1Nr]->Polygon.WhatSideSimple(Map.FaceChildren[Face2Nr]->Polygon.Plane, MapT::RoundEpsilon)!=Polygon3T<double>::Front) continue;
 178             if (Map.FaceChildren[Face2Nr]->Polygon.WhatSideSimple(Map.FaceChildren[Face1Nr]->Polygon.Plane, MapT::RoundEpsilon)!=Polygon3T<double>::Front) continue;
 179
 180             // Faces, zwischen denen möglicherweise ein Terrain liegt, können sich nicht komplett sehen.
 181             BoundingBox3T<double> ConvexHullBB(Map.FaceChildren[Face1Nr]->Polygon.Vertices);
 182             ConvexHullBB.Insert(Map.FaceChildren[Face2Nr]->Polygon.Vertices);
 183             ConvexHullBB=ConvexHullBB.GetEpsilonBox(-MapT::RoundEpsilon);
 184
 185             // Bilde die ConvexHull über die Faces Face1Nr und Face2Nr,
 186             // wobei alle Normalenvektoren dieser ConvexHull nach *INNEN* zeigen!
 187             ArrayT< Plane3T<double> > ConvexHull;
 188
 189             // Auf diese HullPlanes können wir nicht verzichten -- im Occluders-Array werden wir Occluder haben,
 190             // die von Face[Face1Nr] ODER Face[Face2Nr] aus mindestens PARTIAL sichbar sind!
 191             ConvexHull.PushBack(Map.FaceChildren[Face1Nr]->Polygon.Plane);
 192             ConvexHull.PushBack(Map.FaceChildren[Face2Nr]->Polygon.Plane);
 193
 194             // Teil 1: Planes von der einen Seite aus anlegen
 195             for (unsigned long Vertex1Nr=0; Vertex1Nr<Map.FaceChildren[Face1Nr]->Polygon.Vertices.Size(); Vertex1Nr++)
 196             {
 197                 // Beuge degenerierten und mehrfach vorkommenden HullPlanes vor
 198                 if (fabs(Map.FaceChildren[Face2Nr]->Polygon.Plane.GetDistance(Map.FaceChildren[Face1Nr]->Polygon.Vertices[Vertex1Nr]))<0.1) continue;
 199
 200                 for (unsigned long Vertex2Nr=0; Vertex2Nr<Map.FaceChildren[Face2Nr]->Polygon.Vertices.Size(); Vertex2Nr++)
 201                 {
 202                     // Dieser try/catch-Block sollte trotz obigem Test nicht entfernt werden, denn es gibt keine Garantieen!
 203                     try
 204                     {
 205                         Plane3T<double> HullPlane(Map.FaceChildren[Face2Nr]->Polygon.Vertices[Vertex2Nr], Map.FaceChildren[Face1Nr]->Polygon.Vertices[Vertex1Nr],
 206                                                   Map.FaceChildren[Face2Nr]->Polygon.Vertices[Vertex2Nr+1<Map.FaceChildren[Face2Nr]->Polygon.Vertices.Size() ? Vertex2Nr+1 : 0], MapT::RoundEpsilon);
 207
 208                         if (Map.FaceChildren[Face1Nr]->Polygon.WhatSideSimple(HullPlane, MapT::RoundEpsilon)!=Polygon3T<double>::Front) continue;
 209                         if (Map.FaceChildren[Face2Nr]->Polygon.WhatSideSimple(HullPlane, MapT::RoundEpsilon)!=Polygon3T<double>::Front) continue;
 210
 211                         ConvexHull.PushBack(HullPlane);
 212                     }
 213                     catch (const DivisionByZeroE&) {}
 214                 }
 215             }
 216
 217             // Teil 2: Planes von der anderen Seite aus anlegen (Notwendig! Betrachte gegenüberstehendes Dreieck und Quadrat!)
 218             for (unsigned long Vertex2Nr=0; Vertex2Nr<Map.FaceChildren[Face2Nr]->Polygon.Vertices.Size(); Vertex2Nr++)
 219             {
 220                 // Beuge degenerierten und mehrfach vorkommenden HullPlanes vor
 221                 if (fabs(Map.FaceChildren[Face1Nr]->Polygon.Plane.GetDistance(Map.FaceChildren[Face2Nr]->Polygon.Vertices[Vertex2Nr]))<0.1) continue;
 222
 223                 for (unsigned long Vertex1Nr=0; Vertex1Nr<Map.FaceChildren[Face1Nr]->Polygon.Vertices.Size(); Vertex1Nr++)
 224                 {
 225                     // Dieser try/catch-Block sollte trotz obigem Test nicht entfernt werden, denn es gibt keine Garantieen!
 226                     try
 227                     {
 228                         Plane3T<double> HullPlane(Map.FaceChildren[Face1Nr]->Polygon.Vertices[Vertex1Nr], Map.FaceChildren[Face2Nr]->Polygon.Vertices[Vertex2Nr],
 229                                                   Map.FaceChildren[Face1Nr]->Polygon.Vertices[Vertex1Nr+1<Map.FaceChildren[Face1Nr]->Polygon.Vertices.Size() ? Vertex1Nr+1 : 0], MapT::RoundEpsilon);
 230
 231                         if (Map.FaceChildren[Face2Nr]->Polygon.WhatSideSimple(HullPlane, MapT::RoundEpsilon)!=Polygon3T<double>::Front) continue;
 232                         if (Map.FaceChildren[Face1Nr]->Polygon.WhatSideSimple(HullPlane, MapT::RoundEpsilon)!=Polygon3T<double>::Front) continue;
 233
 234                         ConvexHull.PushBack(HullPlane);
 235                     }
 236                     catch (const DivisionByZeroE&) {}
 237                 }
 238             }
 239
 240             // Bilde ein Array der in Frage kommenden Occluder.
 241             ArrayT< Polygon3T<double> > Occluders;
 242
 243             for (unsigned long FaceNr=0; FaceNr<Map.FaceChildren.Size(); FaceNr++)
 244             {
 245                 if (!ConvexHullBB.Intersects(FaceBBs[FaceNr])) continue;
 246
 247                 // TODO: if (Face[FaceNr].Alpha<255 || Face[FaceNr].RenderMode==Masked) continue;
 248
 249                 if ((FacePVS[Face1Nr][FaceNr]!=NO_VISIBILITY) ||
 250                     (FacePVS[Face2Nr][FaceNr]!=NO_VISIBILITY)) Occluders.PushBack(Map.FaceChildren[FaceNr]->Polygon);
 251             }
 252
 253             // Clippe die Occluder gegen die ConvexHull.
 254             for (unsigned long HullPlaneNr=0; HullPlaneNr<ConvexHull.Size(); HullPlaneNr++)
 255                 for (unsigned long OccluderNr=0; OccluderNr<Occluders.Size(); OccluderNr++)
 256                     switch (Occluders[OccluderNr].WhatSideSimple(ConvexHull[HullPlaneNr], MapT::RoundEpsilon))
 257                     {
 258                         case Polygon3T<double>::Both:
 259                             // Occluder splitten und Front-Teil behalten.
 260                             Occluders[OccluderNr]=Occluders[OccluderNr].GetSplits(ConvexHull[HullPlaneNr], MapT::RoundEpsilon)[0];
 261                             break;
 262
 263                         case Polygon3T<double>::Front:
 264                             // Occluder bleibt unverändert in der Liste.
 265                             break;
 266
 267                         default:
 268                             // Diesen Occluder aus der Liste löschen.
 269                             Occluders[OccluderNr]=Occluders[Occluders.Size()-1];
 270                             Occluders.DeleteBack();
 271                             OccluderNr--;
 272                             break;
 273                     }
 274
 275             // Es sind noch Occluder in der ConvexHull, keine gegenseitige komplette Sichtbarkeit.
 276             if (Occluders.Size()) continue;
 277
 278             // Die Faces Face1Nr und Face2Nr können sich gegenseitig komplett sehen!
 279             FacePVS[Face1Nr][Face2Nr]=FULL_VISIBILITY;
 280             FacePVS[Face2Nr][Face1Nr]=FULL_VISIBILITY;
 281         }
 282     }
 283
 284
 285     // 10. Zähle die Anzahl der FULL_VISIBILITY-Elemente in der FacePVS-Matrix.
 286     unsigned long PartialVisCount=VisCount;
 287     VisCount=0;
 288
 289     for (unsigned long Face1Nr=0; Face1Nr<Map.FaceChildren.Size(); Face1Nr++)
 290         for (unsigned long Face2Nr=0; Face2Nr<Map.FaceChildren.Size(); Face2Nr++)
 291             if (FacePVS[Face1Nr][Face2Nr]==FULL_VISIBILITY) VisCount++;
 292
 293     printf("Number of 'FULL' visibility entries:         %10lu  (%7.3f%%)\n", VisCount, 100.0*double(VisCount)/double(Map.FaceChildren.Size()*Map.FaceChildren.Size()));
 294     printf("    (These are %.2f%% of the 'PARTIAL' entries!)\n", 100.0*double(VisCount)/double(PartialVisCount));
 295 }