1 #include "engine.h"
2
3 struct normal
4 {
5 int next;
6 vec surface;
7 };
8
9 struct nkey
10 {
11 ivec v;
12
nkeynkey13 nkey() {}
nkeynkey14 nkey(const ivec &origin, const vvec &offset)
15 : v(((origin.x&~VVEC_INT_MASK)<<VVEC_FRAC) | offset.x,
16 ((origin.y&~VVEC_INT_MASK)<<VVEC_FRAC) | offset.y,
17 ((origin.z&~VVEC_INT_MASK)<<VVEC_FRAC) | offset.z)
18 {}
19 };
20
21 struct nval
22 {
23 int flat, normals;
24
nvalnval25 nval() : flat(0), normals(-1) {}
26 };
27
htcmp(const nkey & x,const nkey & y)28 static inline bool htcmp(const nkey &x, const nkey &y)
29 {
30 return x.v == y.v;
31 }
32
hthash(const nkey & k)33 static inline uint hthash(const nkey &k)
34 {
35 return k.v.x^k.v.y^k.v.z;
36 }
37
38 hashtable<nkey, nval> normalgroups(1<<16);
39 vector<normal> normals;
40
41 VARW(lerpangle, 0, 44, 180);
42
43 static float lerpthreshold = 0;
44
addnormal(const ivec & origin,const vvec & offset,const vec & surface)45 static void addnormal(const ivec &origin, const vvec &offset, const vec &surface)
46 {
47 nkey key(origin, offset);
48 nval &val = normalgroups[key];
49 normal &n = normals.add();
50 n.next = val.normals;
51 n.surface = surface;
52 val.normals = normals.length()-1;
53 }
54
addnormal(const ivec & origin,const vvec & offset,int axis)55 static void addnormal(const ivec &origin, const vvec &offset, int axis)
56 {
57 nkey key(origin, offset);
58 nval &val = normalgroups[key];
59 val.flat += 1<<(4*axis);
60 }
61
findnormal(const ivec & origin,const vvec & offset,const vec & surface,vec & v)62 void findnormal(const ivec &origin, const vvec &offset, const vec &surface, vec &v)
63 {
64 nkey key(origin, offset);
65 const nval *val = normalgroups.access(key);
66 if(!val) { v = surface; return; }
67
68 v = vec(0, 0, 0);
69 int total = 0;
70 if(surface.x >= lerpthreshold) { int n = (val->flat>>4)&0xF; v.x += n; total += n; }
71 else if(surface.x <= -lerpthreshold) { int n = val->flat&0xF; v.x -= n; total += n; }
72 if(surface.y >= lerpthreshold) { int n = (val->flat>>12)&0xF; v.y += n; total += n; }
73 else if(surface.y <= -lerpthreshold) { int n = (val->flat>>8)&0xF; v.y -= n; total += n; }
74 if(surface.z >= lerpthreshold) { int n = (val->flat>>20)&0xF; v.z += n; total += n; }
75 else if(surface.z <= -lerpthreshold) { int n = (val->flat>>16)&0xF; v.z -= n; total += n; }
76 for(int cur = val->normals; cur >= 0;)
77 {
78 normal &o = normals[cur];
79 if(o.surface.dot(surface) >= lerpthreshold)
80 {
81 v.add(o.surface);
82 total++;
83 }
84 cur = o.next;
85 }
86 if(total > 1) v.normalize();
87 else if(!total) v = surface;
88 }
89
90 VARW(lerpsubdiv, 0, 2, 4);
91 VARW(lerpsubdivsize, 4, 4, 128);
92
93 static uint nmprog = 0;
94
show_calcnormals_nmprog()95 void show_calcnormals_nmprog()
96 {
97 float bar1 = float(nmprog) / float(allocnodes);
98 progress(bar1, "computing normals...");
99 }
100
101 #define CHECK_PROGRESS(exit) CHECK_CALCLIGHT_PROGRESS(exit, show_calcnormals_nmprog)
102
addnormals(cube & c,const ivec & o,int size)103 void addnormals(cube &c, const ivec &o, int size)
104 {
105 CHECK_PROGRESS(return);
106
107 if(c.children)
108 {
109 nmprog++;
110 size >>= 1;
111 loopi(8) addnormals(c.children[i], ivec(i, o.x, o.y, o.z, size), size);
112 return;
113 }
114 else if(isempty(c)) return;
115
116 vvec vvecs[8];
117 bool usefaces[6];
118 int vertused = calcverts(c, o.x, o.y, o.z, size, vvecs, usefaces);
119 vec verts[8];
120 loopi(8) if(vertused&(1<<i)) verts[i] = vvecs[i].tovec(o);
121 loopi(6) if(usefaces[i])
122 {
123 CHECK_PROGRESS(return);
124 if(c.texture[i] == DEFAULT_SKY) continue;
125
126 plane planes[2];
127 int numplanes = 0;
128 if(!flataxisface(c, i))
129 {
130 numplanes = genclipplane(c, i, verts, planes);
131 if(!numplanes) continue;
132 }
133 int subdiv = 0;
134 if(lerpsubdiv && size > lerpsubdivsize) // && faceedges(c, i) == F_SOLID)
135 {
136 subdiv = 1<<lerpsubdiv;
137 while(size/subdiv < lerpsubdivsize) subdiv >>= 1;
138 }
139 vec avg;
140 if(numplanes >= 2)
141 {
142 avg = planes[0];
143 avg.add(planes[1]);
144 avg.normalize();
145 }
146 int idxs[4];
147 loopj(4) idxs[j] = faceverts(c, i, j);
148 loopj(4)
149 {
150 const vvec &v = vvecs[idxs[j]], &vn = vvecs[idxs[(j+1)%4]];
151 if(v==vn) continue;
152 if(!numplanes)
153 {
154 addnormal(o, v, i);
155 if(subdiv < 2) continue;
156 ivec dv;
157 loopk(3) dv[k] = (int(vn[k]) - int(v[k])) / subdiv;
158 if(dv.iszero()) continue;
159 vvec vs(v);
160 loopk(subdiv - 1)
161 {
162 vs.add(dv);
163 addnormal(o, vs, i);
164 }
165 continue;
166 }
167 const vec &cur = numplanes < 2 || j == 1 ? planes[0] : (j == 3 ? planes[1] : avg);
168 addnormal(o, v, cur);
169 if(subdiv < 2) continue;
170 ivec dv;
171 loopk(3) dv[k] = (int(vn[k]) - int(v[k])) / subdiv;
172 if(dv.iszero()) continue;
173 vvec vs(v);
174 if(numplanes < 2) loopk(subdiv - 1)
175 {
176 vs.add(dv);
177 addnormal(o, vs, planes[0]);
178 }
179 else
180 {
181 vec dn(j==0 ? planes[0] : (j == 2 ? planes[1] : avg));
182 dn.sub(cur);
183 dn.div(subdiv);
184 vec n(cur);
185 loopk(subdiv - 1)
186 {
187 vs.add(dv);
188 n.add(dn);
189 addnormal(o, vs, vec(dn).normalize());
190 }
191 }
192 }
193 }
194 }
195
calcnormals()196 void calcnormals()
197 {
198 if(!lerpangle) return;
199 lerpthreshold = cos(lerpangle*RAD) - 1e-5f;
200 nmprog = 1;
201 loopi(8) addnormals(worldroot[i], ivec(i, 0, 0, 0, hdr.worldsize/2), hdr.worldsize/2);
202 }
203
clearnormals()204 void clearnormals()
205 {
206 normalgroups.clear();
207 normals.setsizenodelete(0);
208 }
209
calclerpverts(const vec & origin,const vec * p,const vec * n,const vec & ustep,const vec & vstep,lerpvert * lv,int & numv)210 void calclerpverts(const vec &origin, const vec *p, const vec *n, const vec &ustep, const vec &vstep, lerpvert *lv, int &numv)
211 {
212 float ul = ustep.squaredlen(), vl = vstep.squaredlen();
213 int i = 0;
214 loopj(numv)
215 {
216 if(j)
217 {
218 if(p[j] == p[j-1] && n[j] == n[j-1]) continue;
219 if(j == numv-1 && p[j] == p[0] && n[j] == n[0]) continue;
220 }
221 vec dir(p[j]);
222 dir.sub(origin);
223 lv[i].normal = n[j];
224 lv[i].u = ustep.dot(dir)/ul;
225 lv[i].v = vstep.dot(dir)/vl;
226 i++;
227 }
228 numv = i;
229 }
230
setlerpstep(float v,lerpbounds & bounds)231 void setlerpstep(float v, lerpbounds &bounds)
232 {
233 if(bounds.min->v + 1 > bounds.max->v)
234 {
235 bounds.nstep = vec(0, 0, 0);
236 bounds.normal = bounds.min->normal;
237 if(bounds.min->normal != bounds.max->normal)
238 {
239 bounds.normal.add(bounds.max->normal);
240 bounds.normal.normalize();
241 }
242 bounds.ustep = 0;
243 bounds.u = bounds.min->u;
244 return;
245 }
246
247 bounds.nstep = bounds.max->normal;
248 bounds.nstep.sub(bounds.min->normal);
249 bounds.nstep.div(bounds.max->v-bounds.min->v);
250
251 bounds.normal = bounds.nstep;
252 bounds.normal.mul(v - bounds.min->v);
253 bounds.normal.add(bounds.min->normal);
254
255 bounds.ustep = (bounds.max->u-bounds.min->u) / (bounds.max->v-bounds.min->v);
256 bounds.u = bounds.ustep * (v-bounds.min->v) + bounds.min->u;
257 }
258
initlerpbounds(const lerpvert * lv,int numv,lerpbounds & start,lerpbounds & end)259 void initlerpbounds(const lerpvert *lv, int numv, lerpbounds &start, lerpbounds &end)
260 {
261 const lerpvert *first = &lv[0], *second = NULL;
262 loopi(numv-1)
263 {
264 if(lv[i+1].v < first->v) { second = first; first = &lv[i+1]; }
265 else if(!second || lv[i+1].v < second->v) second = &lv[i+1];
266 }
267
268 if(int(first->v) < int(second->v)) { start.min = end.min = first; }
269 else if(first->u > second->u) { start.min = second; end.min = first; }
270 else { start.min = first; end.min = second; }
271
272 start.max = (start.min == lv ? &lv[numv-1] : start.min-1);
273 end.max = (end.min == &lv[numv-1] ? lv : end.min+1);
274
275 setlerpstep(0, start);
276 setlerpstep(0, end);
277 }
278
updatelerpbounds(float v,const lerpvert * lv,int numv,lerpbounds & start,lerpbounds & end)279 void updatelerpbounds(float v, const lerpvert *lv, int numv, lerpbounds &start, lerpbounds &end)
280 {
281 if(v >= start.max->v)
282 {
283 const lerpvert *next = (start.max == lv ? &lv[numv-1] : start.max-1);
284 if(next->v > start.max->v)
285 {
286 start.min = start.max;
287 start.max = next;
288 setlerpstep(v, start);
289 }
290 }
291 if(v >= end.max->v)
292 {
293 const lerpvert *next = (end.max == &lv[numv-1] ? lv : end.max+1);
294 if(next->v > end.max->v)
295 {
296 end.min = end.max;
297 end.max = next;
298 setlerpstep(v, end);
299 }
300 }
301 }
302
lerpnormal(float v,const lerpvert * lv,int numv,lerpbounds & start,lerpbounds & end,vec & normal,vec & nstep)303 void lerpnormal(float v, const lerpvert *lv, int numv, lerpbounds &start, lerpbounds &end, vec &normal, vec &nstep)
304 {
305 updatelerpbounds(v, lv, numv, start, end);
306
307 if(start.u + 1 > end.u)
308 {
309 nstep = vec(0, 0, 0);
310 normal = start.normal;
311 normal.add(end.normal);
312 normal.normalize();
313 }
314 else
315 {
316 vec nstart(start.normal), nend(end.normal);
317 nstart.normalize();
318 nend.normalize();
319
320 nstep = nend;
321 nstep.sub(nstart);
322 nstep.div(end.u-start.u);
323
324 normal = nstep;
325 normal.mul(-start.u);
326 normal.add(nstart);
327 normal.normalize();
328 }
329
330 start.normal.add(start.nstep);
331 start.u += start.ustep;
332
333 end.normal.add(end.nstep);
334 end.u += end.ustep;
335 }
336
newnormals(cube & c)337 void newnormals(cube &c)
338 {
339 if(!c.ext) newcubeext(c);
340 if(!c.ext->normals)
341 {
342 c.ext->normals = new surfacenormals[6];
343 memset(c.ext->normals, 128, 6*sizeof(surfacenormals));
344 }
345 }
346
freenormals(cube & c)347 void freenormals(cube &c)
348 {
349 if(c.ext) DELETEA(c.ext->normals);
350 }
351
352