1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
|
#pragma once
#include "map.h"
#include "../../render/gl_3d.h"
const F32 BSP_NORM_EPSILON = 0.0001f;
const F32 BSP_DIST_EPSILON = 0.01f;
const I32 BSP_DEPTH_MAX = 1024;
struct BSP_PLANE {
VEC3 normal;
F32 dist;
const bool operator==( const BSP_PLANE& other ) const {
return fabsf( normal.x - other.normal.x ) < BSP_NORM_EPSILON &&
fabsf( normal.y - other.normal.y ) < BSP_NORM_EPSILON &&
fabsf( normal.z - other.normal.z ) < BSP_NORM_EPSILON &&
fabsf( dist - other.dist ) < BSP_DIST_EPSILON;
}
};
enum BspSide_t {
BSP_SIDE_FRONT = 1,
BSP_SIDE_BACK = 2,
BSP_SIDE_ON = 4,
BSP_SIDE_SPAN = 8,
};
struct BSP_FACE {
I32 propid;
I32 id;
LIST<MAP_VERTEX> verts{};
LIST<VERTEX3D> render_verts{};
VEC3 mins;
VEC3 maxs;
};
struct BSP_NODE {
BSP_PLANE plane;
I32 front;
I32 back;
};
struct BSP_EDGE {
BSP_PLANE plane;
U32 face;
VEC3 v1, v2;
};
struct BSP_LEAF {
U32 first;
U32 count;
I32 cluster;
LIST<BSP_EDGE> edges;
};
struct BSP_WINDING {
LIST<VEC3> points;
};
struct BSP_PORTAL {
BSP_WINDING w; // winding
BSP_PLANE plane;
I32 front;
I32 back;
};
struct BSP_CLUSTER {
I32 first;
I32 count;
I32 pvs_off;
};
struct BSP_PORTAL_STACK_FRAME {
I32 idx;
LIST<BSP_PLANE> planes;
};
struct BSP_PORTAL_NODE {
I32 leaf;
BSP_WINDING w;
};
struct BSP_PORTAL_QUEUE {
I32 front;
BSP_WINDING frustum;
};
struct BSP_BITSET : public LIST<U32> {};
struct BSP {
LIST<BSP_NODE> nodes;
LIST<BSP_LEAF> leaves;
LIST<BSP_FACE> faces;
// >= 0 = node, < 0 = leaf
I32 root;
WORLD_MAP* map;
LIST<BSP_PORTAL> portals;
LIST<BSP_CLUSTER> clusters;
BSP_BITSET pvs_bits;
};
extern LIST<BSP_PLANE> bsp_map_get_planes( WORLD_MAP* map );
extern LIST<BSP_FACE> bsp_map_get_faces( WORLD_MAP* map );
extern BSP* bsp_build_map( WORLD_MAP* map );
extern void bsp_free( BSP* bsp );
inline U8 bsp_is_leaf( I32 child ) { return child < 0; }
inline I32 bsp_leaf_index( I32 child ) { return ~child; }
inline F32 bsp_plane_dist( const BSP_PLANE& p, const VEC3& v ) { return vec_dot( p.normal, v ) - p.dist; }
inline SURF_PROPS* bsp_face_get_props( WORLD_MAP* w, BSP_FACE* s ) {
return s->propid < 0 ?
map_props_get_special( w, s->propid ) :
&w->props[s->propid];
}
inline VEC3 bsp_face_get_normal( BSP_FACE* f ){
VEC3 v0 = f->verts.data[0].pos;
VEC3 v1 = f->verts.data[1].pos;
VEC3 v2 = f->verts.data[2].pos;
return vec_normalize( vec_cross( v1 - v0, v2 - v0 ) );
}
inline U8 bsp_face_is_axis_aligned( BSP_FACE* f ) {
VEC3 n = bsp_face_get_normal( f );
for( U32 i = 0; i < 3; ++i ) {
if( n[i] && fabsf( n[i] ) != 1.f )
return 0;
}
return 1;
}
inline void bsp_face_calc_extents( BSP_FACE* f ) {
VEC3 mins{ +INFINITY, +INFINITY, +INFINITY }, maxs{ -INFINITY, -INFINITY, -INFINITY };
for( U32 i = 0; i < f->verts.size; ++i ) {
VEC3 v = f->verts.data[i].pos;
mins.x = min( mins.x, v.x );
mins.y = min( mins.y, v.y );
mins.z = min( mins.z, v.z );
maxs.x = max( maxs.x, v.x );
maxs.y = max( maxs.y, v.y );
maxs.z = max( maxs.z, v.z );
}
f->mins = mins;
f->maxs = maxs;
}
|
