optimized trianglefacing calculation, per Vic's recommendation (yes it's all one...
[xonotic/darkplaces.git] / r_shadow.c
1
2 #include "quakedef.h"
3
4 mempool_t *r_shadow_mempool;
5
6 int maxshadowelements;
7 int *shadowelements;
8 int maxtrianglefacinglight;
9 qbyte *trianglefacinglight;
10
11 void r_shadow_start(void)
12 {
13         // allocate vertex processing arrays
14         r_shadow_mempool = Mem_AllocPool("R_Shadow");
15         maxshadowelements = 0;
16         shadowelements = NULL;
17         maxtrianglefacinglight = 0;
18         trianglefacinglight = NULL;
19 }
20
21 void r_shadow_shutdown(void)
22 {
23         maxshadowelements = 0;
24         shadowelements = NULL;
25         maxtrianglefacinglight = 0;
26         trianglefacinglight = NULL;
27         Mem_FreePool(&r_shadow_mempool);
28 }
29
30 void r_shadow_newmap(void)
31 {
32 }
33
34 void R_Shadow_Init(void)
35 {
36         R_RegisterModule("R_Shadow", r_shadow_start, r_shadow_shutdown, r_shadow_newmap);
37 }
38
39 void R_Shadow_Volume(int numverts, int numtris, float *vertex, int *elements, int *neighbors, vec3_t relativelightorigin, float projectdistance, int visiblevolume)
40 {
41         int i, *e, *n, *out, tris;
42         float *v0, *v1, *v2, temp[3], f;
43 // terminology:
44 //
45 // frontface:
46 // a triangle facing the light source
47 //
48 // backface:
49 // a triangle not facing the light source
50 //
51 // shadow volume:
52 // an extrusion of the backfaces, beginning at the original geometry and
53 // ending further from the light source than the original geometry
54 // (presumably at least as far as the light's radius, if the light has a
55 // radius at all), capped at both front and back to avoid any problems
56 //
57 // description:
58 // draws the shadow volumes of the model.
59 // requirements:
60 // vertex loations must already be in vertex before use.
61 // vertex must have capacity for numverts * 2.
62
63         // make sure trianglefacinglight is big enough for this volume
64         if (maxtrianglefacinglight < numtris)
65         {
66                 maxtrianglefacinglight = numtris;
67                 if (trianglefacinglight)
68                         Mem_Free(trianglefacinglight);
69                 trianglefacinglight = Mem_Alloc(r_shadow_mempool, maxtrianglefacinglight);
70         }
71
72         // make sure shadowelements is big enough for this volume
73         if (maxshadowelements < numtris * 24)
74         {
75                 maxshadowelements = numtris * 24;
76                 if (shadowelements)
77                         Mem_Free(shadowelements);
78                 shadowelements = Mem_Alloc(r_shadow_mempool, maxshadowelements * sizeof(int));
79         }
80
81         // make projected vertices
82         // by clever use of elements we'll construct the whole shadow from
83         // the unprojected vertices and these projected vertices
84         for (i = 0, v0 = vertex, v1 = vertex + numverts * 4;i < numverts;i++, v0 += 4, v1 += 4)
85         {
86                 VectorSubtract(v0, relativelightorigin, temp);
87                 f = projectdistance / sqrt(DotProduct(temp,temp));
88                 VectorMA(v0, f, temp, v1);
89         }
90
91         // check which triangles are facing the light
92         for (i = 0, e = elements;i < numtris;i++, e += 3)
93         {
94                 // calculate triangle facing flag
95                 v0 = vertex + e[0] * 4;
96                 v1 = vertex + e[1] * 4;
97                 v2 = vertex + e[2] * 4;
98                 // we do not need to normalize the surface normal because both sides
99                 // of the comparison use it, therefore they are both multiplied the
100                 // same amount...  furthermore the subtract can be done on the
101                 // vectors, saving a little bit of math in the dotproducts
102 #if 1
103                 // fast version
104                 // subtracts v1 from v0 and v2, combined into a crossproduct,
105                 // combined with a dotproduct of the light location relative to the
106                 // first point of the triangle (any point works, since the triangle
107                 // is obviously flat), and finally a comparison to determine if the
108                 // light is infront of the triangle (the goal of this statement)
109                 trianglefacinglight[i] =
110                    (relativelightorigin[0] - v0[0]) * ((v0[1] - v1[1]) * (v2[2] - v1[2]) - (v0[2] - v1[2]) * (v2[1] - v1[1]))
111                  + (relativelightorigin[1] - v0[1]) * ((v0[2] - v1[2]) * (v2[0] - v1[0]) - (v0[0] - v1[0]) * (v2[2] - v1[2]))
112                  + (relativelightorigin[2] - v0[2]) * ((v0[0] - v1[0]) * (v2[1] - v1[1]) - (v0[1] - v1[1]) * (v2[0] - v1[0])) > 0;
113 #else
114                 // readable version
115                 {
116                 float dir0[3], dir1[3],
117
118                 // calculate two mostly perpendicular edge directions
119                 VectorSubtract(v0, v1, dir0);
120                 VectorSubtract(v2, v1, dir1);
121
122                 // we have two edge directions, we can calculate a third vector from
123                 // them, which is the direction of the surface normal (it's magnitude
124                 // is not 1 however)
125                 CrossProduct(dir0, dir1, temp);
126
127                 // this is entirely unnecessary, but kept for clarity
128                 //VectorNormalize(temp);
129
130                 // compare distance of light along normal, with distance of any point
131                 // of the triangle along the same normal (the triangle is planar,
132                 // I.E. flat, so all points give the same answer)
133                 // the normal is not normalized because it is used on both sides of
134                 // the comparison, so it's magnitude does not matter
135                 trianglefacinglight[i] = DotProduct(relativelightorigin, temp) >= DotProduct(v0, temp);
136                 }
137 #endif
138         }
139
140         // output triangle elements
141         out = shadowelements;
142         tris = 0;
143
144         // check each backface for bordering frontfaces,
145         // and cast shadow polygons from those edges,
146         // also create front and back caps for shadow volume
147         for (i = 0, e = elements, n = neighbors;i < numtris;i++, e += 3, n += 3)
148         {
149                 if (!trianglefacinglight[i])
150                 {
151                         // triangle is backface and therefore casts shadow,
152                         // output front and back caps for shadow volume
153                         // front cap (with flipped winding order)
154                         out[0] = e[0];
155                         out[1] = e[2];
156                         out[2] = e[1];
157                         // rear cap
158                         out[3] = e[0] + numverts;
159                         out[4] = e[1] + numverts;
160                         out[5] = e[2] + numverts;
161                         out += 6;
162                         tris += 2;
163                         // check the edges
164                         if (n[0] < 0 || trianglefacinglight[n[0]])
165                         {
166                                 out[0] = e[0];
167                                 out[1] = e[1];
168                                 out[2] = e[1] + numverts;
169                                 out[3] = e[0];
170                                 out[4] = e[1] + numverts;
171                                 out[5] = e[0] + numverts;
172                                 out += 6;
173                                 tris += 2;
174                         }
175                         if (n[1] < 0 || trianglefacinglight[n[1]])
176                         {
177                                 out[0] = e[1];
178                                 out[1] = e[2];
179                                 out[2] = e[2] + numverts;
180                                 out[3] = e[1];
181                                 out[4] = e[2] + numverts;
182                                 out[5] = e[1] + numverts;
183                                 out += 6;
184                                 tris += 2;
185                         }
186                         if (n[2] < 0 || trianglefacinglight[n[2]])
187                         {
188                                 out[0] = e[2];
189                                 out[1] = e[0];
190                                 out[2] = e[0] + numverts;
191                                 out[3] = e[2];
192                                 out[4] = e[0] + numverts;
193                                 out[5] = e[2] + numverts;
194                                 out += 6;
195                                 tris += 2;
196                         }
197                 }
198         }
199         // draw the volume
200         if (visiblevolume)
201         {
202                 qglDisable(GL_CULL_FACE);
203                 R_Mesh_Draw(numverts * 2, tris, shadowelements);
204                 qglEnable(GL_CULL_FACE);
205         }
206         else
207         {
208                 qglColorMask(0,0,0,0);
209                 qglEnable(GL_STENCIL_TEST);
210                 // increment stencil if backface is behind depthbuffer
211                 qglCullFace(GL_BACK); // quake is backwards, this culls front faces
212                 qglStencilOp(GL_KEEP, GL_INCR, GL_KEEP);
213                 R_Mesh_Draw(numverts * 2, tris, shadowelements);
214                 // decrement stencil if frontface is infront of depthbuffer
215                 qglCullFace(GL_FRONT); // quake is backwards, this culls back faces
216                 qglStencilOp(GL_KEEP, GL_DECR, GL_KEEP);
217                 R_Mesh_Draw(numverts * 2, tris, shadowelements);
218                 // restore to normal quake rendering
219                 qglDisable(GL_STENCIL_TEST);
220                 qglStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
221                 qglColorMask(1,1,1,1);
222         }
223 }
224
225 void R_Shadow_VertexLight(int numverts, float *vertex, float *normals, vec3_t relativelightorigin, float lightradius2, float lightdistbias, float lightsubtract, float *lightcolor)
226 {
227         int i;
228         float *n, *v, *c, f, dist, temp[3];
229         // calculate vertex colors
230         for (i = 0, v = vertex, c = varray_color, n = normals;i < numverts;i++, v += 4, c += 4, n += 3)
231         {
232                 VectorSubtract(relativelightorigin, v, temp);
233                 c[0] = 0;
234                 c[1] = 0;
235                 c[2] = 0;
236                 c[3] = 1;
237                 f = DotProduct(n, temp);
238                 if (f > 0)
239                 {
240                         dist = DotProduct(temp, temp);
241                         if (dist < lightradius2)
242                         {
243                                 f = ((1.0f / (dist + lightdistbias)) - lightsubtract) * (f / sqrt(dist));
244                                 c[0] = f * lightcolor[0];
245                                 c[1] = f * lightcolor[1];
246                                 c[2] = f * lightcolor[2];
247                         }
248                 }
249         }
250 }
251
252 void R_Shadow_RenderLightThroughStencil(int numverts, int numtris, int *elements, vec3_t relativelightorigin, float *normals)
253 {
254         // only draw light where this geometry was already rendered AND the
255         // stencil is 0 (non-zero means shadow)
256         qglDepthFunc(GL_EQUAL);
257         qglEnable(GL_STENCIL_TEST);
258         qglStencilFunc(GL_EQUAL, 0, 0xFF);
259         R_Mesh_Draw(numverts, numtris, elements);
260         qglDisable(GL_STENCIL_TEST);
261         qglDepthFunc(GL_LEQUAL);
262 }
263
264 void R_Shadow_ClearStencil(void)
265 {
266         qglClearStencil(0);
267         qglClear(GL_STENCIL_BUFFER_BIT);
268 }