OpenClonk
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros
C4FoWLightSection.cpp
Go to the documentation of this file.
1 /*
2  * OpenClonk, http://www.openclonk.org
3  *
4  * Copyright (c) 2014-2016, The OpenClonk Team and contributors
5  *
6  * Distributed under the terms of the ISC license; see accompanying file
7  * "COPYING" for details.
8  *
9  * "Clonk" is a registered trademark of Matthes Bender, used with permission.
10  * See accompanying file "TRADEMARK" for details.
11  *
12  * To redistribute this file separately, substitute the full license texts
13  * for the above references.
14  */
15 
16 #include "C4Include.h"
18 
19 #ifndef USE_CONSOLE
20 
26 #include "landscape/C4Landscape.h"
27 
28 #include <cfloat>
29 
30 #include <iterator>
31 
32 C4FoWLightSection::C4FoWLightSection(C4FoWLight *pLight, int r) : pLight(pLight), iRot(r)
33 {
34  // Rotation matrices
35  iRot = r % 360;
36  switch(iRot % 360)
37  {
38  default:
39  assert(false);
40  case 0:
41  a = 1; b = 0; c = 0; d = 1;
42  ra = 1; rb = 0; rc = 0; rd = 1;
43  break;
44  case 90:
45  a = 0; b = 1; c = -1; d = 0;
46  ra = 0; rb = -1; rc = 1; rd = 0;
47  break;
48  case 180:
49  a = -1; b = 0; c = 0; d = -1;
50  ra = -1; rb = 0; rc = 0; rd = -1;
51  break;
52  case 270:
53  a = 0; b = -1; c =1; d = 0;
54  ra = 0; rb = 1; rc = -1; rd = 0;
55  break;
56  }
57  // Beam list
58  pBeams = new C4FoWBeam(-1, +1, +1, +1);
59 }
60 
62 {
63  ClearBeams();
64 }
65 
66 inline void C4FoWLightSection::LightBallExtremePoint(float x, float y, float dir, float &lightX, float &lightY) const
67 {
68  float d = sqrt(x * x + y * y);
69  float s = std::min(float(pLight->getSize()), d / 5.0f);
70  lightX = dir * y * s / d;
71  lightY = dir * -x * s / d;
72 }
73 
74 inline void C4FoWLightSection::LightBallRightMostPoint(float x, float y, float &lightX, float &lightY) const
75  { LightBallExtremePoint(x,y,+1.0f,lightX,lightY); }
76 
77 inline void C4FoWLightSection::LightBallLeftMostPoint(float x, float y, float &lightX, float &lightY) const
78  { LightBallExtremePoint(x,y,-1.0f,lightX,lightY); }
79 
80 template <class T> T C4FoWLightSection::transDX(T dx, T dy) const { return T(a) * dx + T(b) * dy; }
81 template <class T> T C4FoWLightSection::transDY(T dx, T dy) const { return T(c) * dx + T(d) * dy; }
82 template <class T> T C4FoWLightSection::transX(T x, T y) const { return transDX(x, y) + T(pLight->getX()); }
83 template <class T> T C4FoWLightSection::transY(T x, T y) const { return transDY(x, y) + T(pLight->getY()); }
84 
85 template <class T> T C4FoWLightSection::rtransDX(T dx, T dy) const { return T(ra) * dx + T(rb) * dy; }
86 template <class T> T C4FoWLightSection::rtransDY(T dx, T dy) const { return T(rc) * dx + T(rd) * dy; }
87 template <class T> T C4FoWLightSection::rtransX(T x, T y) const { return rtransDX(x-T(pLight->getX()),y-T(pLight->getY())); }
88 template <class T> T C4FoWLightSection::rtransY(T x, T y) const { return rtransDY(x-T(pLight->getX()),y-T(pLight->getY())); }
89 
90 void C4FoWLightSection::ClearBeams()
91 {
92  while (C4FoWBeam *beam = pBeams)
93  {
94  pBeams = beam->getNext();
95  delete beam;
96  }
97 }
98 
99 void C4FoWLightSection::Prune(int32_t reach)
100 {
101  if (reach == 0)
102  {
103  ClearBeams();
104  pBeams = new C4FoWBeam(-1, 1, 1, 1);
105  return;
106  }
107  // TODO PeterW: Merge active pBeams that we have pruned to same length
108  for (C4FoWBeam *beam = pBeams; beam; beam = beam->getNext())
109  beam->Prune(reach);
110 }
111 
112 void C4FoWLightSection::Dirty(int32_t reach)
113 {
114  for (C4FoWBeam *beam = pBeams; beam; beam = beam->getNext())
115  if (beam->getLeftEndY() >= reach || beam->getRightEndY() >= reach)
116  beam->Dirty(std::min(beam->getLeftEndY(), beam->getRightEndY()));
117 }
118 
119 C4FoWBeam *C4FoWLightSection::FindBeamLeftOf(int32_t x, int32_t y) const
120 {
121  // Trivial
122  y = std::max(y, 0);
123  if (!pBeams || !pBeams->isRight(x, y))
124  return nullptr;
125  // Go through list
126  // Note: In case this turns out expensive, one might think about implementing
127  // a skip-list. But I highly doubt it.
128  C4FoWBeam *beam = pBeams;
129  while (beam->getNext() && beam->getNext()->isRight(x, y))
130  beam = beam->getNext();
131  return beam;
132 }
133 
135 {
136  // Transform rectangle into our coordinate system
137  C4Rect Rect = rtransRect(RectIn);
138  C4Rect Bounds = rtransRect(C4Rect(0,0,::Landscape.GetWidth(),::Landscape.GetHeight()));
139 
140 #ifdef LIGHT_DEBUG
141  if (!::Game.iTick255) {
142  LogSilentF("Full beam list:");
143  StdStrBuf beamsString;
144  for(C4FoWBeam *beam = pBeams; beam; beam = beam->getNext()) {
145  beamsString.ApendBeamChar(' ');
146  beamsString.ApendBeam(beam->getDesc());
147  }
148  LogSilent(beamsString.getData());
149  }
150 #endif
151 
152 #ifdef LIGHT_DEBUG
153  LogSilentF("Update %d/%d-%d/%d", Rect.x, Rect.y, Rect.x+Rect.Wdt, Rect.y+Rect.Hgt);
154 #endif
155 
156  // Out of reach?
157  if (Rect.y > pLight->getTotalReach())
158  return;
159 
160  // will be clipped on rendering anyway, don't bother to run the algorithm
161  if (Rect.y + Rect.Hgt < 0)
162  return;
163 
164  // Get last beam that's positively *not* affected
165  int32_t ly = RectLeftMostY(Rect),
166  lx = RectLeftMostX(Rect),
167  ry = RectRightMostY(Rect),
168  rx = RectRightMostX(Rect);
169 
170  C4FoWBeam *startBeam = FindBeamLeftOf(lx, ly);
171 
172  // Skip clean beams
173  while (C4FoWBeam *nextBeam = startBeam ? startBeam->getNext() : pBeams) {
174  if (nextBeam->isDirty()) break;
175  startBeam = nextBeam;
176  }
177  // Find end beam, determine at which position we have to start scanning
178  C4FoWBeam *beam = startBeam ? startBeam->getNext() : pBeams;
179 #ifdef LIGHT_DEBUG
180  if (beam)
181  LogSilentF("Start beam is %s", beam->getDesc().getData());
182 #endif
183  C4FoWBeam *endBeam = nullptr;
184  int32_t startY = Rect.GetBottom();
185  while (beam && !beam->isLeft(rx, ry)) {
186  if (beam->isDirty() && beam->getLeftEndY() <= Rect.y + Rect.Hgt) {
187  endBeam = beam;
188  startY = std::min(startY, beam->getLeftEndY());
189  }
190  beam = beam->getNext();
191  }
192 
193  // Can skip scan completely?
194  if (!endBeam)
195  return;
196 
197  // Update right end coordinates
198 #ifdef LIGHT_DEBUG
199  LogSilentF("End beam is %s", endBeam->getDesc().getData());
200 #endif
201 
202  if (endBeam->isRight(rx, ry)) {
203  rx = endBeam->getRightEndX() + 1;
204  ry = endBeam->getRightEndY();
205  }
206 
207  // Bottom of scan - either bound by rectangle or by light's reach
208  int32_t endY = std::min(Rect.GetBottom(), pLight->getReach());
209 
210  // Scan lines
211  int32_t y;
212  for(y = std::max(0, startY); y < endY; y++) {
213 
214  // We ignore all material up to a certain distance. This is the X
215  // range for that in this scan line
216  int32_t ignoreX = 0;
217  if (y < pLight->getSize()) {
218  ignoreX = int(sqrt(pLight->getSize() * pLight->getSize() - y * y));
219  }
220 
221  // Scan all pBeams
222  C4FoWBeam *lastBeam = startBeam;
223  int32_t dirty = 0;
224  for(C4FoWBeam *beam = startBeam ? startBeam->getNext() : pBeams; beam; lastBeam = beam, beam = beam->getNext())
225  {
226  assert(lastBeam ? lastBeam->getNext() == beam : beam == pBeams);
227 
228  // Clean (enough)?
229  if (!beam->isDirty() || y < beam->getLeftEndY())
230  continue;
231 
232  // Out left?
233  if (beam->isRight(lx, ly))
234  continue;
235  // Out right?
236  if (beam->isLeft(rx, ry))
237  break;
238 
239  // We have an active beam that we're about to scan
240  dirty++;
241  beam->Dirty(y+1);
242 
243  // Do a scan
244  int32_t xl = std::max(beam->getLeftX(y), Bounds.x),
245  xr = std::min(beam->getRightX(y), Bounds.x+Bounds.Wdt-1);
246  for(int32_t x = xl; x <= xr; x++)
247  {
248  // Ignore material up to a certain distance (see above)
249  if (abs(x) < ignoreX)
250  continue;
251 
252  // Fast free?
253  if (!Landscape._FastSolidCheck(transX(x,y), transY(x,y)))
254  {
255  if (a == 1)
256  x = rtransX(Landscape.FastSolidCheckNextX(transX(x,y)) - 1, 0);
257  continue;
258  }
259 
260  // Free?
261  if (!GBackSolid(transX(x,y), transY(x,y))) continue;
262 
263  // Split points
264  int32_t x1 = x - 1, x2 = x + 1;
265  bool splitLeft = !beam->isLeft(x1, y);
266  bool splitRight = !beam->isRight(x2, y);
267 
268  // Double merge?
269  if (!splitLeft && !splitRight && lastBeam && beam->getNext())
270  {
271  if(lastBeam->EliminateRight(x,y))
272  {
273  beam = lastBeam;
274  break; // no typo. fSplitRight => x == xr
275  }
276  }
277 
278  // Merge possible?
279  if (!splitLeft && splitRight && lastBeam)
280  if (lastBeam->MergeRight(x2, y))
281  {
282  beam->SetLeft(x2, y);
283  assert(beam->isDirty());
284  continue;
285  }
286  if (splitLeft && !splitRight && beam->getNext())
287  if (beam->getNext()->MergeLeft(x1, y))
288  {
289  beam->SetRight(x1, y);
290  break; // no typo. fSplitRight => x == xr
291  }
292 
293  // Split out left
294  if (splitLeft)
295  {
296  lastBeam = beam;
297  beam = lastBeam->Split(x1, y);
298  assert(lastBeam->getNext() == beam);
299  }
300 
301  // Split out right
302  if(splitRight)
303  {
304  lastBeam = beam;
305  beam = lastBeam->Split(x2, y);
306  assert(lastBeam->getNext() == beam);
307 
308  // Deactivate left/middle beam
309  lastBeam->Clean(y);
310  assert(beam->isDirty());
311  }
312  else
313  {
314  // Deactivate beam
315  beam->Clean(y);
316  break;
317  }
318  }
319  }
320 
321  // No active pBeams left?
322  if (!dirty)
323  break;
324  }
325 
326  // At end of light's reach? Mark all pBeams that got scanned all the way to the end as clean.
327  // There's no need to scan them anymore.
328  if (y >= pLight->getReach()) {
329  for (C4FoWBeam *beam = startBeam ? startBeam->getNext() : pBeams; beam; beam = beam->getNext())
330  if (beam->isDirty() && beam->getLeftEndY() > pLight->getReach())
331  beam->Clean(pLight->getReach());
332  }
333 
334 #ifdef LIGHT_DEBUG
335  LogSilentF("Updated beam list:");
336  for(C4FoWBeam *beam = startBeam ? startBeam->getNext() : pBeams; beam; beam = beam->getNext()) {
337  if (beam->isLeft(iRX, iRY))
338  break;
339  LogSilent(beam->getDesc().getData());
340  }
341 #endif
342 }
343 
344 
345 
346 bool C4FoWLightSection::isConsistent() const {
347  return (a * c + b * d == 1) && (ra * rc + rb * rd == 1) &&
348  (a * ra + b * rc == 1) && (a * rb + b * rd == 0) &&
349  (c * ra + d * rc == 0) && (c * rb + d * rd == 1);
350 }
351 
353 {
354  // Assume normalized rectangle
355  assert(r.Wdt > 0 && r.Hgt > 0);
356 
357  // Get rectangle corners that bound the possibly affected pBeams
358  int32_t ly = RectLeftMostY(r),
359  lx = RectLeftMostX(r),
360  ry = RectRightMostY(r),
361  rx = RectRightMostX(r);
362  C4FoWBeam *lastBeam = FindBeamLeftOf(lx, ly);
363  C4FoWBeam *beam = lastBeam ? lastBeam->getNext() : pBeams;
364 
365  // Scan over beams
366  while (beam && !beam->isLeft(rx, ry))
367  {
368  // Dirty beam?
369  if (beam->getLeftEndY() > r.y || beam->getRightEndY() > r.y)
370  beam->Dirty(r.y);
371 
372  // Merge with last beam?
373  if (lastBeam && lastBeam->isDirty() && beam->isDirty())
374  {
375  lastBeam->MergeDirty();
376  beam = lastBeam->getNext();
377  }
378  else // Advance otherwise
379  {
380  lastBeam = beam;
381  beam = beam->getNext();
382  }
383  }
384 
385  // Final check for merging dirty pBeams on the right end
386  if (lastBeam && beam && lastBeam->isDirty() && beam->isDirty())
387  lastBeam->MergeDirty();
388 
389 }
390 
391 int32_t C4FoWLightSection::FindBeamsClipped(const C4Rect &rect, C4FoWBeam *&firstBeam, C4FoWBeam *&endBeam) const
392 {
393  if(rect.y + rect.Hgt < 0) return 0;
394 
395  int32_t ly = RectLeftMostY(rect),
396  lx = RectLeftMostX(rect),
397  ry = RectRightMostY(rect),
398  rx = RectRightMostX(rect);
399 
400  C4FoWBeam *pPrev = FindBeamLeftOf(lx, ly);
401  firstBeam = pPrev ? pPrev->getNext() : pBeams;
402 
403  // Find end beam - determine the number of pBeams we actually need to draw
404  C4FoWBeam *beam = firstBeam;
405  int32_t beamCount = 0;
406  while (beam && !beam->isLeft(rx, ry))
407  {
408  beam = beam->getNext();
409  beamCount++;
410  }
411  endBeam = beam;
412 
413  return beamCount;
414 }
415 
416 
417 // Gives the unique point where the line through (x1,y1) and (x2,y2) crosses
418 // through the line through (x3,y3) and (x4,y4). Returns false if the point does
419 // not exist or the two lines are parallel.
420 static inline bool find_cross(float x1, float y1, float x2, float y2,
421  float x3, float y3, float x4, float y4,
422  float *px, float *py, float *pb = nullptr)
423 {
424  // We are looking for a, b so that
425  // px = a*x1 + (1-a)*x2 = b*x3 + (1-b)*x4
426  // py = a*y1 + (1-a)*y2 = b*y3 + (1-b)*y4
427 
428  // Cross product
429  float d = (x3-x4)*(y1-y2) - (y3-y4)*(x1-x2);
430  if (d == 0) return false; // parallel - or vector(s) 0
431 
432  // We actually just need b - the unique solution
433  // to above equation. A refreshing piece of elementary math
434  // that I got wrong two times.
435  float b = ((y4-y2)*(x1-x2) - (x4-x2)*(y1-y2)) / d;
436  *px = b*x3 + (1-b)*x4;
437  *py = b*y3 + (1-b)*y4;
438  if (pb) *pb = b;
439  return true;
440 }
441 
442 std::list<C4FoWBeamTriangle> C4FoWLightSection::CalculateTriangles(C4FoWRegion *region) const
443 {
444  C4FoWBeam *startBeam = nullptr, *endBeam = nullptr;
445  int32_t beamCount = FindBeamsClipped(rtransRect(region->getRegion()), startBeam, endBeam);
446  std::list<C4FoWBeamTriangle> result;
447  float crossX=0.0f, crossY=0.0f;
448 
449  // no beams inside the rectangle? Good, nothing to render
450  if(!beamCount) return result;
451 
452  bool isStartClipped = startBeam != pBeams;
453  bool isEndClipped = !!endBeam;
454 
455  C4FoWBeam *beam = startBeam;
456  for (int32_t i = 0; i < beamCount; i++, beam = beam->getNext())
457  {
458  C4FoWBeamTriangle tri;
459  tri.fanLX = beam->getLeftEndXf();
460  tri.fanLY = float(beam->getLeftEndY());
461  tri.fanRX = beam->getRightEndXf();
462  tri.fanRY = float(beam->getRightEndY());
463  if(i == 0 && isStartClipped)
464  tri.clipLeft = true;
465  if(i == beamCount - 1 && isEndClipped)
466  {
467  tri.clipRight = true;
468  }
469 
470  if(tri.fanLX != tri.fanRX || tri.fanLY != tri.fanRY)
471  result.push_back(tri);
472  }
473 
474  if(result.empty()) return result;
475 
476  // Phase 1: Project lower point so it lies on a line with outer left/right
477  // light lines.
478  float scanLevel = 0;
479  for (int step = 0; step < 100000; step++)
480  {
481  // Find the beam to project. The whole idea here is that we reduce the
482  // beams starting with the closest ones. Reason for this is that they
483  // generally shadow the most, and this makes it easy to make the
484  // algorithm robust against light size depending on distance. Sadly
485  // makes the whole algorithm O(n^2)...
486  float bestLevel = FLT_MAX;
487  for (std::list<C4FoWBeamTriangle>::iterator it = result.begin(), nextIt; it != --result.end(); ++it)
488  {
489  nextIt = it; ++nextIt;
490  float level = std::min(it->fanRY, nextIt->fanLY);
491  if (level <= scanLevel || level >= bestLevel)
492  continue;
493  bestLevel = level;
494  }
495  if(bestLevel == FLT_MAX)
496  break;
497  scanLevel = bestLevel;
498 
499  // Now look for all beams at this length. Will propably be only one
500  // most of the time, but can't be too careful. Especially note that
501  // we will make extra loops after removing rays, so we can check the
502  // new neighbouring relation for consistency.
503  for(std::list<C4FoWBeamTriangle>::iterator it = result.begin(), nextIt; it != --result.end(); it = nextIt)
504  {
505  nextIt = it; ++nextIt;
506  C4FoWBeamTriangle tri = *it, nextTri = *nextIt;
507 
508  // Skip ray pairs that do not match the current level (see above)
509  float level = std::min(tri.fanRY, nextTri.fanLY);
510  if(level != bestLevel)
511  continue;
512 
513  // Debugging
514  //#define FAN_STEP_DEBUG
515 #ifdef FAN_STEP_DEBUG
516  LogSilentF("Fan step %d (i=%d)", step, std::distance(result.begin(),it));
517  for (std::list<C4FoWBeamTriangle>::iterator it2 = result.begin(); it2 != result.end(); it2++) {
518  const char *marker = "";
519  if (it2 == it) marker = " (it)";
520  if (it2 == nextIt) marker = " (nextIt)";
521  LogSilentF(" %.010f %.010f%s", it2->fanLX, it2->fanLY, marker);
522  LogSilentF(" %.010f %.010f%s", it2->fanRX, it2->fanRY, marker);
523  }
524 #endif
525 
526  // Calculate light bounds. We assume a "smaller" light for closer beams
527  float lightLX, lightLY, lightRX, lightRY;
528  LightBallLeftMostPoint(tri.fanRX, tri.fanRY, lightLX, lightLY);
529  LightBallRightMostPoint(nextTri.fanLX, nextTri.fanLY, lightRX, lightRY);
530 
531  // Ascending
532  bool descendCollision = false;
533  const float ascendDescendDelta = 0.1f;
534  if (tri.fanRY > nextTri.fanLY)
535  {
536  // Left beam surface self-shadowing? We test whether the scalar product
537  // of the beam's normal and the light vector is positive.
538  if ( (tri.fanRY - tri.fanLY) * (nextTri.fanLX - lightRX) >=
539  (tri.fanRX - tri.fanLX) * (nextTri.fanLY - lightRY))
540  {
541  // Reduce to upper point (Yep, we know that the upper point
542  // must be the right one. Try to figure out why!)
543  assert(tri.fanRY <= tri.fanLY);
544  tri.fanLX = tri.fanRX;
545  tri.fanLY = tri.fanRY;
546  *it = tri;
547  }
548 
549  // The threshold decides at what point we are going to eliminate
550  // (see below). Our goal is to not reduce the ray width below
551  // a certain eta. We are using Manhattan distance, which is a
552  // preliminary optimisation, but we *like* being evil here.
553  float threshold = 1.0f;
554  float fanWidth = fabs(tri.fanRX - tri.fanLX) + fabs(tri.fanRY - tri.fanLY);
555  threshold -= ascendDescendDelta / fanWidth;
556 
557  // Left beam reduced?
558  float fanRXp = tri.fanRX;
559  if (tri.fanRX == tri.fanLX && tri.fanRY == tri.fanLY)
560  {
561  // Move point to the right for the purpose of finding the cross
562  // point - after all, given that tri.fanRX == tri.fanLX, we
563  // only care about whether to eliminate or insert an additional
564  // point for the descend collision, so the exact value doesn't
565  // really matter - but we don't want find_cross to bail out!
566  fanRXp += 1.0;
567  threshold = 0.0;
568  }
569 
570  // Move right point of left beam to the left (the original point is partly shadowed)
571  float b;
572  bool f = find_cross(lightRX, lightRY, nextTri.fanLX, nextTri.fanLY,
573  tri.fanLX, tri.fanLY, fanRXp, tri.fanRY,
574  &crossX, &crossY, &b);
575 
576 #ifdef FAN_STEP_DEBUG
577  LogSilentF("Ascend, b=%.010f, cross=%.010f/%.010f", b, crossX, crossY);
578 #endif
579  // The self-shadow-check should have made sure that the two are
580  // never parallel.
581  assert(f); (void)f;
582 
583  // Cross point to left of surface? Then the surface itself is
584  // shadowed, and we don't need to draw it.
585  if (b >= threshold)
586  {
587  // Can't eliminate it?
588  if (it == result.begin())
589  continue;
590 
591  // Remove the beam.
592  it = nextIt = result.erase(it);
593  tri = *--it;
594  // Now decide how to proceed: If the new previous ray (it)
595  // is farther away, we have to repeat this whole check
596  // because this one (nextIt) might shadow it as well.
597  if (tri.fanRY > nextTri.fanLY)
598  {
599  nextIt = it;
600  continue;
601  }
602 
603  // However if the previous one is *closer*, this means we
604  // cannot possible shadow it. Furthermore, we know that
605  // it cannot shadow this one either. The fact that there was
606  // a beam between the two means that there is now a "hole"
607  // that needs to be filled. Hence we have a descend
608  // collision. We could get there by looping like above,
609  // but this is more elegant.
610  descendCollision = true;
611  LightBallLeftMostPoint(tri.fanLX, tri.fanLY, lightLX, lightLY);
612 
613  // Cross point actually right of surface? This can happen when
614  // we eliminated surfaces. It means that the light doesn't reach
615  // down far enough between this and the next beam to hit anything.
616  // As a result, we insert a new zero-width surface where the light
617  // stops.
618  }
619  else if (b < 0.0)
620  {
621  // As it doesn't matter from this point on whether we were
622  // in an ascend or a descend case, this gets handled top-level.
623  // ... still debating with myself whether a "goto" would be
624  // cleaner here ;)
625  descendCollision = true;
626  }
627  else
628  {
629  // Set cross point
630  tri.fanRX = crossX;
631  tri.fanRY = crossY;
632  // This shouldn't change the case we are in (uh, I think)
633  assert(tri.fanRY > nextTri.fanLY);
634  // Write back
635  *it = tri;
636  continue;
637  }
638 
639  // Descending - same, but mirrored. And without comments.
640  }
641  else if (tri.fanRY < nextTri.fanLY)
642  {
643  if ( (nextTri.fanRY - nextTri.fanLY) * (tri.fanRX - lightLX) >=
644  (nextTri.fanRX - nextTri.fanLX) * (tri.fanRY - lightLY))
645  {
646  assert(nextTri.fanLY <= nextTri.fanRY);
647  nextTri.fanRX = nextTri.fanLX;
648  nextTri.fanRY = nextTri.fanLY;
649  *nextIt = nextTri;
650  }
651  float fanRXp = nextTri.fanRX;
652  float threshold = 0.0f;
653  float fanWidth = fabs(nextTri.fanRX - nextTri.fanLX) + fabs(nextTri.fanRY - nextTri.fanLY);
654  threshold += ascendDescendDelta / fanWidth;
655  if (nextTri.fanRX == nextTri.fanLX && nextTri.fanRY == nextTri.fanLY)
656  fanRXp += 1.0;
657 
658  float b;
659  bool f = find_cross(lightLX, lightLY, tri.fanRX, tri.fanRY,
660  nextTri.fanLX, nextTri.fanLY, fanRXp, nextTri.fanRY,
661  &crossX, &crossY, &b);
662 #ifdef FAN_STEP_DEBUG
663  LogSilentF("Descend, b=%.010f, cross=%.010f/%.010f", b, crossX, crossY);
664 #endif
665  assert(f); (void) f;
666  if (b <= threshold)
667  {
668  if (nextIt == --result.end())
669  continue;
670  nextIt = result.erase(nextIt);
671  nextTri = *nextIt;
672  if (nextTri.fanLY > tri.fanRY)
673  {
674  nextIt = it;
675  continue;
676  }
677  descendCollision = true;
678  LightBallRightMostPoint(nextTri.fanLX, nextTri.fanLY, lightRX, lightRY);
679  }
680  else if (b > 1.0)
681  {
682  descendCollision = true;
683  }
684  else
685  {
686  nextTri.fanLX = crossX;
687  nextTri.fanLY = crossY;
688  assert(tri.fanRY < nextTri.fanLY);
689  *nextIt = nextTri;
690  continue;
691  }
692 
693  } else { // tri.fanRY == nextTri.fanLY
694 
695  // Check whether we have a significant gap
696  if (nextTri.fanLX - tri.fanRX > 0.5) {
697  descendCollision = true;
698  } else {
699  // Nothing to do
700  continue;
701  }
702 
703  }
704 
705  // We should only reach this place with a descend collision
706  assert(descendCollision); (void) descendCollision;
707 
708  // Should never be parallel -- otherwise we wouldn't be here
709  // in the first place.
710  bool f = find_cross(lightLX, lightLY, tri.fanRX, tri.fanRY,
711  lightRX, lightRY, nextTri.fanLX, nextTri.fanLY,
712  &crossX, &crossY);
713  assert(f); (void) f;
714 #ifdef FAN_STEP_DEBUG
715  LogSilentF("Collision, cross=%.02f/%.02f", crossX, crossY);
716 #endif
717 
718  // Ensure some minimum distance to existing points - don't
719  // bother with too small bumps. This also catches some floating
720  // point inacurracies.
721  const float descendEta = 3;
722  if (crossY <= tri.fanRY + descendEta || crossY <= nextTri.fanLY + descendEta)
723  continue;
724 
725  // This should always follow an elimination, but better check
726  assert(beamCount > static_cast<int>(result.size()));
727 
728  C4FoWBeamTriangle newTriangle;
729  newTriangle.fanLX = crossX;
730  newTriangle.fanLY = crossY;
731  newTriangle.fanRX = crossX;
732  newTriangle.fanRY = crossY;
733 
734  nextIt = result.insert(nextIt, newTriangle);
735 
736  // Jump over surface. Note that our right beam might get
737  // eliminated later on, causing us to back-track into this
738  // zero-length pseudo-surface. This will cause find_cross
739  // above to eliminate the pseudo-surface and back-track
740  // further to the left, which is exactly how it should work.
741  ++nextIt;
742 
743  } // end for(std::list<C4FoWBeamTriangle>::iterator it = result.begin(), nextIt = it; it != --result.end(); ++it) loop
744  } // end for (int step = 0; step < 100000; step++) loop
745 
746 #ifdef FAN_STEP_DEBUG
747  LogSilentF("Fan output");
748  for (std::list<C4FoWBeamTriangle>::iterator it2 = result.begin(); it2 != result.end(); it2++) {
749  LogSilentF(" %.010f %.010f", it2->fanLX, it2->fanLY);
750  LogSilentF(" %.010f %.010f", it2->fanRX, it2->fanRY);
751  }
752 #endif
753 
754  // Phase 2: Calculate fade points
755  for (auto & tri : result)
756  {
757  // Calculate light bounds. Note that the way light size is calculated
758  // and we are using it below, we need to consider an "asymetrical" light.
759  float lightLX, lightLY, lightRX, lightRY;
760  LightBallLeftMostPoint(tri.fanLX, tri.fanLY, lightLX, lightLY);
761  LightBallRightMostPoint(tri.fanRX, tri.fanRY, lightRX, lightRY);
762 
763  // This is simply the projection of the left point using the left-most
764  // light point, as well as the projection of the right point using the
765  // right-most light point.
766 
767  // For once we actually calculate this using the real distance
768  float dx = tri.fanLX - lightLX;
769  float dy = tri.fanLY - lightLY;
770  float d = float(pLight->getFadeout()) / sqrt(dx*dx + dy*dy);
771  tri.fadeLX = tri.fanLX + d * dx;
772  tri.fadeLY = tri.fanLY + d * dy;
773 
774  dx = tri.fanRX - lightRX;
775  dy = tri.fanRY - lightRY;
776  d = float(pLight->getFadeout()) / sqrt(dx*dx + dy*dy);
777  tri.fadeRX = tri.fanRX + d * dx;
778  tri.fadeRY = tri.fanRY + d * dy;
779 
780  // Do the fades cross?
781  const double fadeCrossEta = 0.01;
782  if ((tri.fadeRX - lightRX) / (tri.fadeRY - lightRY)
783  < (tri.fadeLX - lightRX) / (tri.fadeLY - lightRY) + fadeCrossEta)
784  {
785  // Average it
786  tri.fadeLX = tri.fadeRX = (tri.fadeLX + tri.fadeRX) / 2;
787  tri.fadeLY = tri.fadeRY = (tri.fadeLY + tri.fadeRY) / 2;
788  }
789  }
790 
791  transTriangles(result);
792 
793  return result;
794 }
795 
796 void C4FoWLightSection::transTriangles(std::list<C4FoWBeamTriangle> &triangles) const
797 {
798  for (auto & tri : triangles)
799  {
800  float x,y;
801 
802  x = tri.fanRX, y = tri.fanRY;
803  tri.fanRX = transX(x,y);
804  tri.fanRY = transY(x,y);
805 
806  x = tri.fanLX, y = tri.fanLY;
807  tri.fanLX = transX(x,y);
808  tri.fanLY = transY(x,y);
809 
810  x = tri.fadeRX, y = tri.fadeRY;
811  tri.fadeRX = transX(x,y);
812  tri.fadeRY = transY(x,y);
813 
814  x = tri.fadeLX, y = tri.fadeLY;
815  tri.fadeLX = transX(x,y);
816  tri.fadeLY = transY(x,y);
817  }
818 }
819 
821 {
822  pComp->Value(mkNamingAdapt(iRot, "iRot"));
823  pComp->Value(mkNamingAdapt(a, "a"));
824  pComp->Value(mkNamingAdapt(b, "b"));
825  pComp->Value(mkNamingAdapt(c, "c"));
826  pComp->Value(mkNamingAdapt(d, "d"));
827  pComp->Value(mkNamingAdapt(ra, "ra"));
828  pComp->Value(mkNamingAdapt(rb, "rb"));
829  pComp->Value(mkNamingAdapt(rc, "rc"));
830  pComp->Value(mkNamingAdapt(rd, "rd"));
831  if (pComp->isSerializer())
832  {
833  for (C4FoWBeam *beam = pBeams; beam; beam = beam->getNext())
834  pComp->Value(mkNamingAdapt(*beam, "Beam"));
835  }
836  else
837  {
838  ClearBeams();
839  int32_t beam_count = 0;
840  pComp->Value(mkNamingCountAdapt<int32_t>(beam_count, "Beam"));
841  C4FoWBeam *last_beam = nullptr;
842  for (int32_t i = 0; i < beam_count; ++i)
843  {
844  std::unique_ptr<C4FoWBeam> beam(new C4FoWBeam(0, 0, 0, 0));
845  pComp->Value(mkNamingAdapt(*beam, "Beam"));
846  C4FoWBeam *new_beam = beam.release();
847  if (!last_beam)
848  pBeams = new_beam;
849  else
850  last_beam->setNext(new_beam);
851  last_beam = new_beam;
852  }
853  }
854 }
855 
856 #endif
const char * getData() const
Definition: StdBuf.h:442
void Invalidate(C4Rect r)
bool isRight(int32_t x, int32_t y) const
Definition: C4FoWBeam.h:83
static int32_t FastSolidCheckNextX(int32_t x)
int32_t iTick255
Definition: C4Game.h:129
bool LogSilent(const char *szMessage, bool fConsole)
Definition: C4Log.cpp:114
C4Game Game
Definition: C4Globals.cpp:52
void Dirty(int32_t reach)
#define b
int32_t getY() const
Definition: C4FoWLight.h:59
int32_t getFadeout() const
Definition: C4FoWLight.h:61
bool EliminateRight(int32_t x, int32_t y)
Definition: C4FoWBeam.cpp:90
bool _FastSolidCheck(int32_t x, int32_t y) const
int32_t getLeftEndY() const
Definition: C4FoWBeam.h:68
Definition: C4Rect.h:27
#define a
void Prune(int32_t reach)
int32_t getX() const
Definition: C4FoWLight.h:58
std::list< C4FoWBeamTriangle > CalculateTriangles(C4FoWRegion *region) const
StdNamingAdapt< T > mkNamingAdapt(T &&rValue, const char *szName)
Definition: StdAdaptors.h:92
void SetLeft(int32_t x, int32_t y)
Definition: C4FoWBeam.h:92
int32_t Wdt
Definition: C4Rect.h:30
bool isSerializer()
Definition: StdCompiler.h:54
bool LogSilentF(const char *strMessage,...)
Definition: C4Log.cpp:260
void CompileFunc(StdCompiler *pComp)
int32_t getSize() const
Definition: C4FoWLight.h:63
int32_t y
Definition: C4Rect.h:30
void Dirty(int32_t y)
Definition: C4FoWBeam.cpp:165
int32_t getTotalReach() const
Definition: C4FoWLight.h:62
C4Landscape Landscape
void MergeDirty()
Definition: C4FoWBeam.cpp:136
int32_t getRightEndY() const
Definition: C4FoWBeam.h:71
bool isDirty() const
Definition: C4FoWBeam.h:57
void Value(const T &rStruct)
Definition: StdCompiler.h:161
C4FoWLightSection(C4FoWLight *pLight, int r)
void Clean(int32_t y)
Definition: C4FoWBeam.cpp:157
int32_t x
Definition: C4Rect.h:30
int32_t GetHeight() const
bool isLeft(int32_t x, int32_t y) const
Definition: C4FoWBeam.h:78
StdStrBuf getDesc() const
Definition: C4FoWBeam.cpp:36
C4FoWBeam * getNext() const
Definition: C4FoWBeam.h:59
void setNext(C4FoWBeam *next)
Definition: C4FoWBeam.h:60
int32_t GetBottom() const
Definition: C4Rect.h:58
bool MergeRight(int32_t x, int32_t y)
Definition: C4FoWBeam.cpp:45
const C4Rect & getRegion() const
Definition: C4FoWRegion.h:51
int32_t Hgt
Definition: C4Rect.h:30
C4FoWBeam * Split(int32_t x, int32_t y)
Definition: C4FoWBeam.cpp:117
int32_t getReach() const
Definition: C4FoWLight.h:60
#define s
int32_t GetWidth() const
bool GBackSolid(int32_t x, int32_t y)
Definition: C4Landscape.h:231