1 #include "doomdata.h"
2 #include "tarray.h"
3 #include "r_defs.h"
4 #include "x86.h"
5
6 struct FPolySeg;
7 struct FMiniBSP;
8
9 struct FEventInfo
10 {
11 int Vertex;
12 DWORD FrontSeg;
13 };
14
15 struct FEvent
16 {
17 FEvent *Parent, *Left, *Right;
18 double Distance;
19 FEventInfo Info;
20 };
21
22 class FEventTree
23 {
24 public:
25 FEventTree ();
26 ~FEventTree ();
27
28 FEvent *GetMinimum ();
GetSuccessor(FEvent * event)29 FEvent *GetSuccessor (FEvent *event) const { FEvent *node = Successor(event); return node == &Nil ? NULL : node; }
GetPredecessor(FEvent * event)30 FEvent *GetPredecessor (FEvent *event) const { FEvent *node = Predecessor(event); return node == &Nil ? NULL : node; }
31
32 FEvent *GetNewNode ();
33 void Insert (FEvent *event);
34 FEvent *FindEvent (double distance) const;
35 void DeleteAll ();
36
PrintTree()37 void PrintTree () const { PrintTree (Root); }
38
39 private:
40 FEvent Nil;
41 FEvent *Root;
42 FEvent *Spare;
43
44 void DeletionTraverser (FEvent *event);
45 FEvent *Successor (FEvent *event) const;
46 FEvent *Predecessor (FEvent *event) const;
47
48 void PrintTree (const FEvent *event) const;
49 };
50
51 struct FSimpleVert
52 {
53 fixed_t x, y;
54 };
55
56 extern "C"
57 {
58 int ClassifyLine2 (node_t &node, const FSimpleVert *v1, const FSimpleVert *v2, int sidev[2]);
59 #ifndef DISABLE_SSE
60 int ClassifyLineSSE1 (node_t &node, const FSimpleVert *v1, const FSimpleVert *v2, int sidev[2]);
61 int ClassifyLineSSE2 (node_t &node, const FSimpleVert *v1, const FSimpleVert *v2, int sidev[2]);
62 #ifdef BACKPATCH
63 #ifdef __GNUC__
64 int ClassifyLineBackpatch (node_t &node, const FSimpleVert *v1, const FSimpleVert *v2, int sidev[2]) __attribute__((noinline));
65 #else
66 int __declspec(noinline) ClassifyLineBackpatch (node_t &node, const FSimpleVert *v1, const FSimpleVert *v2, int sidev[2]);
67 #endif
68 #endif
69 #endif
70 }
71
72 class FNodeBuilder
73 {
74 struct FPrivSeg
75 {
76 int v1, v2;
77 int sidedef;
78 int linedef;
79 sector_t *frontsector;
80 sector_t *backsector;
81 DWORD next;
82 DWORD nextforvert;
83 DWORD nextforvert2;
84 int loopnum; // loop number for split avoidance (0 means splitting is okay)
85 DWORD partner; // seg on back side
86 DWORD storedseg; // seg # in the GL_SEGS lump
87
88 int planenum;
89 bool planefront;
90 FPrivSeg *hashnext;
91 };
92 struct FPrivVert : FSimpleVert
93 {
94 DWORD segs; // segs that use this vertex as v1
95 DWORD segs2; // segs that use this vertex as v2
96
97 bool operator== (const FPrivVert &other)
98 {
99 return x == other.x && y == other.y;
100 }
101 };
102 struct FSimpleLine
103 {
104 fixed_t x, y, dx, dy;
105 };
106 union USegPtr
107 {
108 DWORD SegNum;
109 FPrivSeg *SegPtr;
110 };
111 struct FSplitSharer
112 {
113 double Distance;
114 DWORD Seg;
115 bool Forward;
116 };
117
118 struct glseg_t : public seg_t
119 {
120 DWORD Partner;
121 };
122
123
124 // Like a blockmap, but for vertices instead of lines
125 class IVertexMap
126 {
127 public:
128 virtual ~IVertexMap();
129 virtual int SelectVertexExact(FPrivVert &vert) = 0;
130 virtual int SelectVertexClose(FPrivVert &vert) = 0;
131 private:
132 IVertexMap &operator=(const IVertexMap &);
133 };
134
135 class FVertexMap : public IVertexMap
136 {
137 public:
138 FVertexMap (FNodeBuilder &builder, fixed_t minx, fixed_t miny, fixed_t maxx, fixed_t maxy);
139 ~FVertexMap ();
140
141 int SelectVertexExact (FPrivVert &vert);
142 int SelectVertexClose (FPrivVert &vert);
143
144 private:
145 FNodeBuilder &MyBuilder;
146 TArray<int> *VertexGrid;
147
148 fixed_t MinX, MinY, MaxX, MaxY;
149 int BlocksWide, BlocksTall;
150
151 enum { BLOCK_SHIFT = 8 + FRACBITS };
152 enum { BLOCK_SIZE = 1 << BLOCK_SHIFT };
153
154 int InsertVertex (FPrivVert &vert);
GetBlock(fixed_t x,fixed_t y)155 inline int GetBlock (fixed_t x, fixed_t y)
156 {
157 assert (x >= MinX);
158 assert (y >= MinY);
159 assert (x <= MaxX);
160 assert (y <= MaxY);
161 return (unsigned(x - MinX) >> BLOCK_SHIFT) + (unsigned(y - MinY) >> BLOCK_SHIFT) * BlocksWide;
162 }
163 };
164
165 class FVertexMapSimple : public IVertexMap
166 {
167 public:
168 FVertexMapSimple(FNodeBuilder &builder);
169
170 int SelectVertexExact(FPrivVert &vert);
171 int SelectVertexClose(FPrivVert &vert);
172 private:
173 int InsertVertex(FPrivVert &vert);
174
175 FNodeBuilder &MyBuilder;
176 };
177
178 friend class FVertexMap;
179 friend class FVertexMapSimple;
180
181 public:
182 struct FLevel
183 {
184 vertex_t *Vertices; int NumVertices;
185 side_t *Sides; int NumSides;
186 line_t *Lines; int NumLines;
187
188 fixed_t MinX, MinY, MaxX, MaxY;
189
190 void FindMapBounds();
ResetMapBoundsFLevel191 void ResetMapBounds()
192 {
193 MinX = FIXED_MAX;
194 MinY = FIXED_MAX;
195 MaxX = FIXED_MIN;
196 MaxY = FIXED_MIN;
197 }
198 };
199
200 struct FPolyStart
201 {
202 int polynum;
203 fixed_t x, y;
204 };
205
206 FNodeBuilder (FLevel &level);
207 FNodeBuilder (FLevel &level,
208 TArray<FPolyStart> &polyspots, TArray<FPolyStart> &anchors,
209 bool makeGLNodes);
210 ~FNodeBuilder ();
211
212 void Extract (node_t *&nodes, int &nodeCount,
213 seg_t *&segs, glsegextra_t *&glsegextras, int &segCount,
214 subsector_t *&ssecs, int &subCount,
215 vertex_t *&verts, int &vertCount);
216 const int *GetOldVertexTable();
217
218 // These are used for building sub-BSP trees for polyobjects.
219 void Clear();
220 void AddPolySegs(FPolySeg *segs, int numsegs);
221 void AddSegs(seg_t *segs, int numsegs);
222 void BuildMini(bool makeGLNodes);
223 void ExtractMini(FMiniBSP *bsp);
224
225 static angle_t PointToAngle (fixed_t dx, fixed_t dy);
226
227 // < 0 : in front of line
228 // == 0 : on line
229 // > 0 : behind line
230
231 static inline int PointOnSide (int x, int y, int x1, int y1, int dx, int dy);
232
233 private:
234 IVertexMap *VertexMap;
235 int *OldVertexTable;
236
237 TArray<node_t> Nodes;
238 TArray<subsector_t> Subsectors;
239 TArray<DWORD> SubsectorSets;
240 TArray<FPrivSeg> Segs;
241 TArray<FPrivVert> Vertices;
242 TArray<USegPtr> SegList;
243 TArray<BYTE> PlaneChecked;
244 TArray<FSimpleLine> Planes;
245
246 TArray<int> Touched; // Loops a splitter touches on a vertex
247 TArray<int> Colinear; // Loops with edges colinear to a splitter
248 FEventTree Events; // Vertices intersected by the current splitter
249
250 TArray<FSplitSharer> SplitSharers; // Segs colinear with the current splitter
251
252 DWORD HackSeg; // Seg to force to back of splitter
253 DWORD HackMate; // Seg to use in front of hack seg
254 FLevel &Level;
255 bool GLNodes; // Add minisegs to make GL nodes?
256
257 // Progress meter stuff
258 int SegsStuffed;
259
260 void FindUsedVertices (vertex_t *vertices, int max);
261 void BuildTree ();
262 void MakeSegsFromSides ();
263 int CreateSeg (int linenum, int sidenum);
264 void GroupSegPlanes ();
265 void GroupSegPlanesSimple ();
266 void FindPolyContainers (TArray<FPolyStart> &spots, TArray<FPolyStart> &anchors);
267 bool GetPolyExtents (int polynum, fixed_t bbox[4]);
268 int MarkLoop (DWORD firstseg, int loopnum);
269 void AddSegToBBox (fixed_t bbox[4], const FPrivSeg *seg);
270 int CreateNode (DWORD set, unsigned int count, fixed_t bbox[4]);
271 int CreateSubsector (DWORD set, fixed_t bbox[4]);
272 void CreateSubsectorsForReal ();
273 bool CheckSubsector (DWORD set, node_t &node, DWORD &splitseg);
274 bool CheckSubsectorOverlappingSegs (DWORD set, node_t &node, DWORD &splitseg);
275 bool ShoveSegBehind (DWORD set, node_t &node, DWORD seg, DWORD mate); int SelectSplitter (DWORD set, node_t &node, DWORD &splitseg, int step, bool nosplit);
276 void SplitSegs (DWORD set, node_t &node, DWORD splitseg, DWORD &outset0, DWORD &outset1, unsigned int &count0, unsigned int &count1);
277 DWORD SplitSeg (DWORD segnum, int splitvert, int v1InFront);
278 int Heuristic (node_t &node, DWORD set, bool honorNoSplit);
279
280 // Returns:
281 // 0 = seg is in front
282 // 1 = seg is in back
283 // -1 = seg cuts the node
284
285 inline int ClassifyLine (node_t &node, const FPrivVert *v1, const FPrivVert *v2, int sidev[2]);
286
287 void FixSplitSharers (const node_t &node);
288 double AddIntersection (const node_t &node, int vertex);
289 void AddMinisegs (const node_t &node, DWORD splitseg, DWORD &fset, DWORD &rset);
290 DWORD CheckLoopStart (fixed_t dx, fixed_t dy, int vertex1, int vertex2);
291 DWORD CheckLoopEnd (fixed_t dx, fixed_t dy, int vertex2);
292 void RemoveSegFromVert1 (DWORD segnum, int vertnum);
293 void RemoveSegFromVert2 (DWORD segnum, int vertnum);
294 DWORD AddMiniseg (int v1, int v2, DWORD partner, DWORD seg1, DWORD splitseg);
295 void SetNodeFromSeg (node_t &node, const FPrivSeg *pseg) const;
296
297 int CloseSubsector (TArray<glseg_t> &segs, int subsector, vertex_t *outVerts);
298 DWORD PushGLSeg (TArray<glseg_t> &segs, const FPrivSeg *seg, vertex_t *outVerts);
299 void PushConnectingGLSeg (int subsector, TArray<glseg_t> &segs, vertex_t *v1, vertex_t *v2);
300 int OutputDegenerateSubsector (TArray<glseg_t> &segs, int subsector, bool bForward, double lastdot, FPrivSeg *&prev, vertex_t *outVerts);
301
302 static int STACK_ARGS SortSegs (const void *a, const void *b);
303
304 double InterceptVector (const node_t &splitter, const FPrivSeg &seg);
305
306 void PrintSet (int l, DWORD set);
307
308 FNodeBuilder &operator= (const FNodeBuilder &) { return *this; }
309 };
310
311 // Points within this distance of a line will be considered on the line.
312 // Units are in fixed_ts.
313 const double SIDE_EPSILON = 6.5536;
314
315 // Vertices within this distance of each other will be considered as the same vertex.
316 #define VERTEX_EPSILON 6 // This is a fixed_t value
317
PointOnSide(int x,int y,int x1,int y1,int dx,int dy)318 inline int FNodeBuilder::PointOnSide (int x, int y, int x1, int y1, int dx, int dy)
319 {
320 // For most cases, a simple dot product is enough.
321 double d_dx = double(dx);
322 double d_dy = double(dy);
323 double d_x = double(x);
324 double d_y = double(y);
325 double d_x1 = double(x1);
326 double d_y1 = double(y1);
327
328 double s_num = (d_y1-d_y)*d_dx - (d_x1-d_x)*d_dy;
329
330 if (fabs(s_num) < 17179869184.f) // 4<<32
331 {
332 // Either the point is very near the line, or the segment defining
333 // the line is very short: Do a more expensive test to determine
334 // just how far from the line the point is.
335 double l = d_dx*d_dx + d_dy*d_dy; // double l = sqrt(d_dx*d_dx+d_dy*d_dy);
336 double dist = s_num * s_num / l; // double dist = fabs(s_num)/l;
337 if (dist < SIDE_EPSILON*SIDE_EPSILON) // if (dist < SIDE_EPSILON)
338 {
339 return 0;
340 }
341 }
342 return s_num > 0.0 ? -1 : 1;
343 }
344
ClassifyLine(node_t & node,const FPrivVert * v1,const FPrivVert * v2,int sidev[2])345 inline int FNodeBuilder::ClassifyLine (node_t &node, const FPrivVert *v1, const FPrivVert *v2, int sidev[2])
346 {
347 #ifdef DISABLE_SSE
348 return ClassifyLine2 (node, v1, v2, sidev);
349 #else
350 #if defined(__SSE2__) || defined(_M_X64)
351 // If compiling with SSE2 support everywhere, just use the SSE2 version.
352 return ClassifyLineSSE2 (node, v1, v2, sidev);
353 #elif defined(_MSC_VER) && _MSC_VER < 1300
354 // VC 6 does not support SSE optimizations.
355 return ClassifyLine2 (node, v1, v2, sidev);
356 #else
357 // Select the routine based on our flag.
358 #ifdef BACKPATCH
359 return ClassifyLineBackpatch (node, v1, v2, sidev);
360 #else
361 if (CPU.bSSE2)
362 return ClassifyLineSSE2 (node, v1, v2, sidev);
363 else
364 return ClassifyLine2 (node, v1, v2, sidev);
365 #endif
366 #endif
367 #endif
368 }
369