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.
7 /***************************************/
9 /*** Cafu Potentially Visibility Set ***/
11 /***************************************/
16 #include "CaPVSWorld.hpp"
17 #include "Win32/Win32Console.hpp"
20 const time_t ProgramStartTime
=time(NULL
);
21 Win32ConsoleT Win32Console
;
22 ArrayT
<SuperLeafT
> SuperLeaves
;
23 ArrayT
<unsigned long> SuperLeavesPVS
;
24 unsigned long MasterSuperLeafNr
;
27 // This function determines the adjacency cell graph of the 'SuperLeaves'.
28 // It is filled-in and stored in the 'Neighbours' members of the 'SuperLeaves'.
29 void DetermineAdjacencyGraph()
31 Win32Console
.FunctionID("SuperLeaves Adjacency Graph");
33 for (unsigned long SL1Nr
=0; SL1Nr
<SuperLeaves
.Size(); SL1Nr
++)
34 for (unsigned long SL2Nr
=0; SL2Nr
<SuperLeaves
.Size(); SL2Nr
++)
36 if (SL1Nr
==SL2Nr
|| !BoundingBoxTest(SuperLeaves
[SL1Nr
].BB
, SuperLeaves
[SL2Nr
].BB
)) continue;
38 // Jedes Portal des ersten Leafs gegen jedes Portal des zweiten Leafs
39 // prüfen und testen, ob sie sich schneiden (dann sind sie durchlässig).
40 // BEACHTE: SuperLeaves haben *alle* Portale ihrer Leaves!
41 // D.h. es können sich nicht nur Portale auf ihrer konvexen Hülle befinden, sondern auch "innen drin".
42 // Wegen der Konvexität der SuperLeaves dürfte das aber keine Rolle spielen und folgendes müßte trotzdem korrekt funktionieren.
43 for (unsigned long Portal1Nr
=0; Portal1Nr
<SuperLeaves
[SL1Nr
].Portals
.Size(); Portal1Nr
++)
44 for (unsigned long Portal2Nr
=0; Portal2Nr
<SuperLeaves
[SL2Nr
].Portals
.Size(); Portal2Nr
++)
46 if (!PolygonOverlap(SuperLeaves
[SL1Nr
].Portals
[Portal1Nr
], SuperLeaves
[SL2Nr
].Portals
[Portal2Nr
])) continue;
48 // Folgender Check ist zwar redundant, aber zumindest sinnvoll.
49 // Da diese Funktion sowieso schnell genug ist, lasse ihn nicht weg!
50 if (PolygonWhatSide(SuperLeaves
[SL1Nr
].Portals
[Portal1Nr
], SuperLeaves
[SL2Nr
].Portals
[Portal2Nr
].Plane
)!=-3) continue;
52 ArrayT
<PolygonT
> NewPortals
;
53 PolygonChopUp(SuperLeaves
[SL2Nr
].Portals
[Portal2Nr
], SuperLeaves
[SL1Nr
].Portals
[Portal1Nr
], NewPortals
);
55 SuperLeaves
[SL1Nr
].Neighbours
.PushBackEmpty();
56 SuperLeaves
[SL1Nr
].Neighbours
[SuperLeaves
[SL1Nr
].Neighbours
.Size()-1].SuperLeafNr
=SL2Nr
;
57 SuperLeaves
[SL1Nr
].Neighbours
[SuperLeaves
[SL1Nr
].Neighbours
.Size()-1].SubPortal
=NewPortals
[NewPortals
.Size()-1];
65 // Markiere das SuperLeaf 'SLNr' als von 'MasterSuperLeafNr' aus sichtbar.
66 inline void FlagVisible(unsigned long SLNr
)
68 const unsigned long PVSTotalBitNr
=MasterSuperLeafNr
*SuperLeaves
.Size()+SLNr
;
69 const unsigned long PVS_W32_Nr
=PVSTotalBitNr
>> 5;
70 const unsigned long PVSBitMask
=1 << (PVSTotalBitNr
& 31);
72 SuperLeavesPVS
[PVS_W32_Nr
]|=PVSBitMask
;
76 // Bestimme die Sichtpyramide (Frustum), die eine Lichtquelle (LightSource) durch ein Loch (Hole) wirft.
77 // Dabei leuchtet die Lichtquelle in die entgegengesetzte(!!) Richtung ihres Normalenvektors, und das Loch
78 // läßt auch nur Licht in der Gegenrichtung seines Normalenvektors durch. Würde man das Loch zur Lichtquelle
79 // und umgekehrt machen (PolygonMirror), wäre das Frustum das gleiche, die Ebenen wären aber gespiegelt!
80 // Voraussetzung: Die Ebene der Lichtquelle schneidet nicht das Loch und umgekehrt. Dieser Fall wird nicht
81 // abgedeckt bzw. ist gar nicht durchdacht. Da die Leaves konvex sind usw. wird dies aber immer eingehalten!
82 inline void FindFrustum(const PolygonT
& LightSource
, const PolygonT
& Hole
, ArrayT
<PlaneT
>& Frustum
)
84 Frustum
.Clear(); // Frustum.ClearForOverwrite();
86 unsigned long V2
=Hole
.Vertices
.Size()-1;
87 for(unsigned long V3
=0; V3
<Hole
.Vertices
.Size(); V3
++)
89 for (unsigned long V1
=0; V1
<LightSource
.Vertices
.Size(); V1
++)
91 // Eigentlich würde ich hier gerne folgenden Wunsch-Code schreiben:
94 // PlaneT FrustumPlane(Hole.Vertices[V2], LightSource.Vertices[V1], Hole.Vertices[V3]);
98 // catch (DivisionByZero) { } // Nicht mögliche FrustumPlanes einfach ignorieren.
99 // Aus irgendeinem Grund ist die Verwendung oder das Fangen der DivisionByZero-Exception aber sehr langsam.
100 // Deshalb rolle ich lieber den PlaneT-Konstruktor aus, um ohne dieses Exception-Handling auszukommen.
101 // Das Programm wird *deutlich* schneller, ca. Faktor 1,5. Ob das eine Schwäche des Watcom-Compilers ist??
102 VectorT
Normal(VectorCross(Hole
.Vertices
[V3
]-Hole
.Vertices
[V2
], LightSource
.Vertices
[V1
]-Hole
.Vertices
[V2
]));
103 double NLength
=VectorLength(Normal
);
105 if (NLength
<0.1) continue;
106 Normal
=VectorScale(Normal
, 1.0/NLength
);
108 PlaneT
FrustumPlane(Normal
, VectorDot(Hole
.Vertices
[V2
], Normal
));
110 // Diese neue FrustumPlane nur dann akzeptieren, wenn das Hole auf ihrer Vorderseite liegt
111 // (konstruktionsbedingt sowieso der Fall!) und die LightSource auf ihrer Rückseite liegt.
112 // Wenn eine Edge des Hole in der Ebene der LightSource liegt, darf die LightSource
113 // auch in der FrustumPlane liegen.
114 if (PolygonWhatSide(LightSource
, FrustumPlane
)<0)
116 Frustum
.PushBack(FrustumPlane
);
124 // Rollen vertauschen: Das Loch sei nun die Lichtquelle, und die Lichtquelle das Loch! Siehe Skizze!
125 V2
=LightSource
.Vertices
.Size()-1;
126 for(V3
=0; V3
<LightSource
.Vertices
.Size(); V3
++)
128 for (unsigned long V1
=0; V1
<Hole
.Vertices
.Size(); V1
++) // Optimize: Check if edges are in already existing frustum planes!
130 // Eigentlich würde ich hier gerne folgenden Wunsch-Code schreiben:
133 // PlaneT FrustumPlane(LightSource.Vertices[V2], Hole.Vertices[V1], LightSource.Vertices[V3]);
137 // catch (DivisionByZero) { } // Nicht mögliche Ebenen einfach ignorieren.
138 // Aus irgendeinem Grund ist die Verwendung oder das Fangen der DivisionByZero-Exception aber sehr langsam.
139 // Deshalb rolle ich lieber den PlaneT-Konstruktor aus, um ohne dieses Exception-Handling auszukommen.
140 // Das Programm wird *deutlich* schneller, ca. Faktor 1,5. Ob das eine Schwäche des Watcom-Compilers ist??
141 VectorT
Normal(VectorCross(LightSource
.Vertices
[V3
]-LightSource
.Vertices
[V2
], Hole
.Vertices
[V1
]-LightSource
.Vertices
[V2
]));
142 double NLength
=VectorLength(Normal
);
144 if (NLength
<0.1) continue;
145 Normal
=VectorScale(Normal
, 1.0/NLength
);
147 PlaneT
FrustumPlane(Normal
, VectorDot(LightSource
.Vertices
[V2
], Normal
));
149 // Diese neue FrustumPlane nur dann akzeptieren, wenn die LightSource auf ihrer Rückseite
150 // liegt (konstruktionsbedingt sowieso der Fall!) und das Hole auf ihrer Vorderseite liegt.
151 // Wenn eine Edge der LightSource in der Ebene des Holes liegt, darf das Hole
152 // auch in der FrustumPlane liegen.
153 const signed char Side
=PolygonWhatSide(Hole
, FrustumPlane
); // Wegen dem Rollentausch ist die Orientierung für diesen Test falsch, ...
155 if (Side
==1 || Side
==-3)
157 Frustum
.PushBack(FrustumPlane
); // ...im Gesamten aber wieder richtig!
167 // Betrete das SuperLeaf 'SLNr' durch das 'EnteringPortal' des vorhergehenden SuperLeafs.
168 void FindVisibleLeaves(unsigned long SLNr
, const PolygonT
& MasterPortal
, const PolygonT
& EnteringPortal
)
172 // Das Frustum MasterPortal --> EnteringPortal bestimmen.
173 ArrayT
<PlaneT
> Frustum
;
174 FindFrustum(MasterPortal
, EnteringPortal
, Frustum
);
176 for (unsigned long NeighbourNr
=0; NeighbourNr
<SuperLeaves
[SLNr
].Neighbours
.Size(); NeighbourNr
++)
178 PolygonT NextPortal
=SuperLeaves
[SLNr
].Neighbours
[NeighbourNr
].SubPortal
;
180 // Abkürzung: Gleiche Ebene? Dann weiter mit dem nächsten Portal!
181 if (abs(PolygonWhatSide(NextPortal
, EnteringPortal
.Plane
))==3) continue;
183 // Clippe 'NextPortal' gegen das Frustum MasterPortal --> EnteringPortal.
184 static PolygonT ClipPortal
;
186 for (unsigned long FrustumNr
=0; FrustumNr
<Frustum
.Size(); FrustumNr
++)
188 const signed char Side
=PolygonWhatSide(NextPortal
, Frustum
[FrustumNr
]);
190 if (Side
==2) PolygonSplit(NextPortal
, Frustum
[FrustumNr
], NextPortal
, ClipPortal
);
191 else if (Side
!=1) break;
193 if (FrustumNr
<Frustum
.Size()) continue;
195 // Clippe 'MasterPortal' gegen das Frustum NextPortal --> EnteringPortal.
196 // Um die Portale nicht spiegeln zu müssen, das gespiegelte Frustum benutzen!
197 ArrayT
<PlaneT
> Frustum2
;
198 FindFrustum(EnteringPortal
, NextPortal
, Frustum2
);
200 PolygonT MP
=MasterPortal
;
202 for (FrustumNr
=0; FrustumNr
<Frustum2
.Size(); FrustumNr
++)
204 const signed char Side
=PolygonWhatSide(MP
, Frustum2
[FrustumNr
]);
206 if (Side
== 2) PolygonSplit(MP
, Frustum2
[FrustumNr
], ClipPortal
, MP
);
207 else if (Side
!=-1) break;
209 if (FrustumNr
<Frustum2
.Size()) continue;
211 FindVisibleLeaves(SuperLeaves
[SLNr
].Neighbours
[NeighbourNr
].SuperLeafNr
, MP
, NextPortal
);
218 Win32Console
.FunctionID("Potentially Visibility Set");
220 // Für jedes SuperLeaf das PVS bestimmen.
221 for (MasterSuperLeafNr
=0; MasterSuperLeafNr
<SuperLeaves
.Size(); MasterSuperLeafNr
++)
223 Win32Console
.RefreshStatusLine((double)MasterSuperLeafNr
/SuperLeaves
.Size());
225 FlagVisible(MasterSuperLeafNr
);
227 // Für den alten Algorithmus war hier vermerkt, daß "outer leaves" keine Neighbours/Portals haben,
228 // wegen der Eigenschaften von Portalize() und FillInside() des CaBSP Programms.
229 // Der neue Algorithmus verwendet SuperLeaves, bei denen überhaupt nicht zwischen "inner" und "outer" unterschieden wird.
230 // Alles was zählt, sind die Portale. Deshalb setzen sich SuperLeaves korrekt aus beliebigen Leaves eines Sub-Trees zusammen.
231 for (unsigned long NeighbourNr
=0; NeighbourNr
<SuperLeaves
[MasterSuperLeafNr
].Neighbours
.Size(); NeighbourNr
++)
233 const unsigned long NeighbourSLNr
=SuperLeaves
[MasterSuperLeafNr
].Neighbours
[NeighbourNr
].SuperLeafNr
;
234 const PolygonT
& MasterPortal
=SuperLeaves
[MasterSuperLeafNr
].Neighbours
[NeighbourNr
].SubPortal
;
236 // Der unmittelbare Nachbar ist auf jeden Fall sichtbar.
237 FlagVisible(NeighbourSLNr
);
239 for (unsigned long NNr
=0; NNr
<SuperLeaves
[NeighbourSLNr
].Neighbours
.Size(); NNr
++)
241 const unsigned long NeighboursNeighbourSLNr
=SuperLeaves
[NeighbourSLNr
].Neighbours
[NNr
].SuperLeafNr
;
242 const PolygonT
& EnteringPortal
=SuperLeaves
[NeighbourSLNr
].Neighbours
[NNr
].SubPortal
;
244 if (abs(PolygonWhatSide(MasterPortal
, EnteringPortal
.Plane
))==3) continue;
246 FindVisibleLeaves(NeighboursNeighbourSLNr
, MasterPortal
, EnteringPortal
);
251 printf("SuperLeavesPVS : done\n");
255 void WriteLogFileEntry(const char* WorldPathName
, unsigned long CheckSum
)
257 FILE* LogFile
=fopen("CaPVS.log", "a");
261 SYSTEMTIME SystemTime
;
262 char WorldName
[_MAX_FNAME
];
263 char ComputerName
[MAX_COMPUTERNAME_LENGTH
+1]="unknown";
264 unsigned long LengthCN
=MAX_COMPUTERNAME_LENGTH
+1;
265 unsigned long RunningSec
=(unsigned long)difftime(time(NULL
), ProgramStartTime
);
267 GetLocalTime(&SystemTime
);
268 GetComputerName(ComputerName
, &LengthCN
);
269 _splitpath(WorldPathName
, NULL
, NULL
, WorldName
, NULL
);
271 // Date, Time, WorldName, TimeForCompletion on [ComputerName]
272 fprintf(LogFile
, "%02u.%02u.%02u %2u:%02u %-16s%3u:%02u:%02u [%-16s] %10u\n",
273 SystemTime
.wDay
, SystemTime
.wMonth
, SystemTime
.wYear
% 100, SystemTime
.wHour
, SystemTime
.wMinute
,
274 WorldName
, RunningSec
/3600, (RunningSec
/60) % 60, RunningSec
% 60, ComputerName
, CheckSum
);
283 printf("USAGE: CaPVS Path/WorldName.cw [OPTIONS]\n");
285 printf("OPTIONS:\n");
286 printf("-maxRecDepthSL n : Leaves that are stored in the BSP tree and have a greater\n");
287 printf(" depth than this value get combined in a common SuperLeaf\n");
288 printf(" that is created at this depth value.\n");
289 printf("-minAreaSL a : BSP sub-trees whose non-detail faces have a common area of\n");
290 printf(" less than this value get combined in a SuperLeaf.\n");
291 printf("-onlySLs : Do not compute the PVS, just print out how many SuperLeaves\n");
292 printf(" would be created. Used for estimating the above parameter\n");
293 printf(" values (speed vs. quality).\n");
300 int main(int ArgC
, const char* ArgV
[])
302 unsigned long MaxRecDepthSL
=0xFFFFFFFF;
303 double MinAreaSL
=0.0;
304 bool OnlySuperLeaves
=false;
306 Win32Console
.InitScreen("Cafu Potentially Visibility Set Utility, Version 04", __DATE__
);
310 for (int ArgNr
=2; ArgNr
<ArgC
; ArgNr
++)
312 if (!stricmp(ArgV
[ArgNr
], "-maxRecDepthSL"))
315 if (ArgNr
>=ArgC
) Usage();
317 MaxRecDepthSL
=atoi(ArgV
[ArgNr
]);
318 printf("maxRecDepthSL == %u\n", MaxRecDepthSL
);
320 else if (!stricmp(ArgV
[ArgNr
], "-minAreaSL"))
323 if (ArgNr
>=ArgC
) Usage();
325 MinAreaSL
=atof(ArgV
[ArgNr
]);
326 if (MinAreaSL
<0.0) MinAreaSL
=0.0;
327 printf("minAreaSL == %.3f\n", MinAreaSL
);
329 else if (!stricmp(ArgV
[ArgNr
], "-onlySLs"))
331 OnlySuperLeaves
=true;
335 printf("Unknown option '%s'.\n", ArgV
[ArgNr
]);
342 printf("Load World %s\n", ArgV
[1]);
344 CaPVSWorldT
* CaPVSWorld
=new CaPVSWorldT(ArgV
[1], MaxRecDepthSL
, MinAreaSL
);
346 // Robustness against the 'sharp wedge' problem is granted:
347 // DetermineAdjacencyGraph() is the only place where PolygonOverlap() is called, but only once on *input* portals.
348 // Everywhere else (especially in BuildPVS() and its sub-functions), only PolygonSplit() and PolygonWhatSide() are called.
349 CaPVSWorld
->CreateSuperLeaves(SuperLeaves
);
350 if (OnlySuperLeaves
) return 0;
351 DetermineAdjacencyGraph();
353 // SuperLeavesPVS erzeugen und zurücksetzen (völlige Blindheit).
354 SuperLeavesPVS
.PushBackEmpty((SuperLeaves
.Size()*SuperLeaves
.Size()+31)/32);
355 for (unsigned long Vis
=0; Vis
<SuperLeavesPVS
.Size(); Vis
++) SuperLeavesPVS
[Vis
]=0;
357 // Berechne das PVS der SuperLeaves.
360 // 'SuperLeavesPVS' ins PVS der 'CaPVSWorld' übertragen.
361 CaPVSWorld
->StorePVS(SuperLeaves
, SuperLeavesPVS
);
363 // Drucke Statistiken aus und erhalte eine Prüfsumme zurück.
364 unsigned long CheckSum
=CaPVSWorld
->GetChecksumAndPrintStats();
366 // Speichere die World zurück auf Disk.
367 Win32Console
.FunctionID("Save World %s", ArgV
[1]);
368 CaPVSWorld
->SaveToDisk(ArgV
[1]);
371 WriteLogFileEntry(ArgV
[1], CheckSum
);
372 printf("COMPLETED.\n");
374 catch (const WorldT::LoadErrorT
& E
) { Win32Console
.Error(E
.Msg
); }
375 catch (const WorldT::SaveErrorT
& E
) { Win32Console
.Error(E
.Msg
); }