OpenClonk
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros
C4FoWBeam Class Reference

#include <C4FoWBeam.h>

Public Member Functions

 C4FoWBeam (int32_t iLeftX, int32_t iLeftY, int32_t iRightX, int32_t iRightY)
 
bool isDirty () const
 
bool isClean () const
 
C4FoWBeamgetNext () const
 
void setNext (C4FoWBeam *next)
 
int32_t getLeftX (int32_t y) const
 
int32_t getRightX (int32_t y) const
 
float getLeftXf (int32_t y) const
 
float getRightXf (int32_t y) const
 
int32_t getLeftEndY () const
 
int32_t getLeftEndX () const
 
float getLeftEndXf () const
 
int32_t getRightEndY () const
 
int32_t getRightEndX () const
 
float getRightEndXf () const
 
StdStrBuf getDesc () const
 
bool isLeft (int32_t x, int32_t y) const
 
bool isRight (int32_t x, int32_t y) const
 
bool isInside (int32_t x, int32_t y) const
 
void SetLeft (int32_t x, int32_t y)
 
void SetRight (int32_t x, int32_t y)
 
bool MergeRight (int32_t x, int32_t y)
 
bool MergeLeft (int32_t x, int32_t y)
 
C4FoWBeamSplit (int32_t x, int32_t y)
 
bool EliminateRight (int32_t x, int32_t y)
 
void MergeDirty ()
 
void Clean (int32_t y)
 
void Dirty (int32_t y)
 
void Prune (int32_t y)
 
void CompileFunc (StdCompiler *pComp)
 

Detailed Description

This class represents one beam. A beam is a triangle spanned by two rays: one going from the origin to the left delimiter point, one going from the origin to the right delimiter point.

LeftEndX/Y and RightEndX/Y are the positions where this beam hit a solid material pixel while LeftX/Y and RightX/Y are the positions at which this beam did not hit but merely streaked a solid pixel (= the neighboring beam hits it) and thus continues until *EndX/Y.

It is assumed that the beam always goes down in display coordinate system, thus the Y-position of the delimiting points is always > 0. C4FoWLightSection transforms the coordinate system after calculation to implement the beams that go into other directions. This class here always assumes one direction.

A beam is initially marked as "dirty", meaning that the end points of the beam haven't been found yet (by the ray trace algorithm) and the beam will extend further. When all beams are "clean", the algorithm is done.

Definition at line 37 of file C4FoWBeam.h.

Constructor & Destructor Documentation

C4FoWBeam::C4FoWBeam ( int32_t  iLeftX,
int32_t  iLeftY,
int32_t  iRightX,
int32_t  iRightY 
)
inline

Definition at line 40 of file C4FoWBeam.h.

Referenced by Split().

41  : iLeftX(iLeftX), iLeftY(iLeftY), iRightX(iRightX), iRightY(iRightY),
42  iLeftEndY(0), iRightEndY(0),
43  iError(0),
44  fDirty(true),
45  pNext(nullptr)
46  { }

Here is the caller graph for this function:

Member Function Documentation

void C4FoWBeam::Clean ( int32_t  y)

Set a new end point, making the beam "clean".

Definition at line 157 of file C4FoWBeam.cpp.

Referenced by Prune(), and C4FoWLightSection::Update().

158 {
159  // Search hit something, this beam is now clean.
160  iLeftEndY = y;
161  iRightEndY = y;
162  fDirty = false;
163 }

Here is the caller graph for this function:

void C4FoWBeam::CompileFunc ( StdCompiler pComp)

Definition at line 188 of file C4FoWBeam.cpp.

References mkNamingAdapt(), and StdCompiler::Value().

189 {
190  pComp->Value(mkNamingAdapt(iLeftX, "iLeftX"));
191  pComp->Value(mkNamingAdapt(iLeftY, "iLeftY"));
192  pComp->Value(mkNamingAdapt(iRightX, "iRightX"));
193  pComp->Value(mkNamingAdapt(iRightY, "iRightY"));
194  pComp->Value(mkNamingAdapt(iLeftEndY, "iLeftEndY"));
195  pComp->Value(mkNamingAdapt(iRightEndY, "iRightEndY"));
196  pComp->Value(mkNamingAdapt(iError, "iError"));
197  pComp->Value(mkNamingAdapt(fDirty, "fDirty"));
198 }
StdNamingAdapt< T > mkNamingAdapt(T &&rValue, const char *szName)
Definition: StdAdaptors.h:92
void Value(const T &rStruct)
Definition: StdCompiler.h:161

Here is the call graph for this function:

void C4FoWBeam::Dirty ( int32_t  y)

Extend this beam to the new maximum length, making it "dirty" because now the end points haven't been found anymore Called when the size of the light has been increased to the given value.

Definition at line 165 of file C4FoWBeam.cpp.

Referenced by C4FoWLightSection::Invalidate(), MergeDirty(), Split(), and C4FoWLightSection::Update().

166 {
167  // Got invalidated, beam is dirty until updated
168  iLeftEndY = y;
169  iRightEndY = y;
170  fDirty = true;
171 }

Here is the caller graph for this function:

bool C4FoWBeam::EliminateRight ( int32_t  x,
int32_t  y 
)

Makes this beam span from its left delimiter point to the right delimiter point of the next but one beam, removing the two beams in between in the process. In other words, removes the next beam and merges this beam with the next but one beam. Returns false and does not do the action in case the error threshold would be reached.

Definition at line 90 of file C4FoWBeam.cpp.

References C4FoWMergeThreshold, getLeftEndX(), getLeftEndY(), and isDirty().

Referenced by C4FoWLightSection::Update().

91 {
92  // Called on the beams left of the one getting eliminated
93  C4FoWBeam *pElim = pNext, *pMerge = pNext->pNext;
94  assert(!!pElim); assert(!!pMerge);
95  assert(!isDirty()); assert(!pMerge->isDirty());
96 
97  // Calc errors, add those accumulated on both merged beams
98  int32_t iErr = getDoubleTriangleSurface(
100  pMerge->getRightEndX(), pMerge->getRightEndY(),
101  x, y);
102  iErr += pMerge->iError;
103  if (iError + iErr > C4FoWMergeThreshold)
104  return false;
105 
106  // Do elimination
107  iRightX = pMerge->iRightX;
108  iRightY = pMerge->iRightY;
109  iRightEndY = pMerge->iRightEndY;
110  pNext = pMerge->pNext;
111  iError += iErr;
112  delete pElim;
113  delete pMerge;
114  return true;
115 }
int32_t getLeftEndY() const
Definition: C4FoWBeam.h:68
const int32_t C4FoWMergeThreshold
Definition: C4FoWBeam.cpp:23
bool isDirty() const
Definition: C4FoWBeam.h:57
int32_t getLeftEndX() const
Definition: C4FoWBeam.h:69

Here is the call graph for this function:

Here is the caller graph for this function:

StdStrBuf C4FoWBeam::getDesc ( ) const

Definition at line 36 of file C4FoWBeam.cpp.

References FormatString(), getLeftEndY(), getLeftX(), getRightEndY(), and getRightX().

Referenced by C4FoWLightSection::Update().

36  {
37  return FormatString("%d:%d@%d:%d%s",
38  getLeftX(1000),
39  getRightX(1000),
40  getLeftEndY(),
41  getRightEndY(),
42  fDirty ? "*" : "");
43 }
int32_t getLeftEndY() const
Definition: C4FoWBeam.h:68
int32_t getLeftX(int32_t y) const
Definition: C4FoWBeam.h:63
int32_t getRightX(int32_t y) const
Definition: C4FoWBeam.h:64
int32_t getRightEndY() const
Definition: C4FoWBeam.h:71
StdStrBuf FormatString(const char *szFmt,...)
Definition: StdBuf.cpp:270

Here is the call graph for this function:

Here is the caller graph for this function:

int32_t C4FoWBeam::getLeftEndX ( ) const
inline

Definition at line 69 of file C4FoWBeam.h.

References getLeftX().

Referenced by EliminateRight(), MergeLeft(), and MergeRight().

69 { return getLeftX(iLeftEndY); }
int32_t getLeftX(int32_t y) const
Definition: C4FoWBeam.h:63

Here is the call graph for this function:

Here is the caller graph for this function:

float C4FoWBeam::getLeftEndXf ( ) const
inline

Definition at line 70 of file C4FoWBeam.h.

References getLeftXf().

70 { return getLeftXf(iLeftEndY); }
float getLeftXf(int32_t y) const
Definition: C4FoWBeam.h:65

Here is the call graph for this function:

int32_t C4FoWBeam::getLeftEndY ( ) const
inline

Definition at line 68 of file C4FoWBeam.h.

Referenced by EliminateRight(), getDesc(), C4FoWLightSection::Invalidate(), MergeDirty(), and C4FoWLightSection::Update().

68 { return iLeftEndY; }

Here is the caller graph for this function:

int32_t C4FoWBeam::getLeftX ( int32_t  y) const
inline

Definition at line 63 of file C4FoWBeam.h.

Referenced by getDesc(), and getLeftEndX().

63 { return iLeftX * y / iLeftY; }

Here is the caller graph for this function:

float C4FoWBeam::getLeftXf ( int32_t  y) const
inline

Definition at line 65 of file C4FoWBeam.h.

Referenced by getLeftEndXf().

65 { return (iLeftX * y) / float(iLeftY); }

Here is the caller graph for this function:

C4FoWBeam* C4FoWBeam::getNext ( ) const
inline

Definition at line 59 of file C4FoWBeam.h.

Referenced by C4FoWLightSection::CalculateTriangles(), C4FoWLightSection::CompileFunc(), C4FoWLightSection::Dirty(), C4FoWLightSection::Invalidate(), MergeDirty(), C4FoWLightSection::Prune(), and C4FoWLightSection::Update().

59 { return pNext; }

Here is the caller graph for this function:

int32_t C4FoWBeam::getRightEndX ( ) const
inline

Definition at line 72 of file C4FoWBeam.h.

References getRightX().

Referenced by MergeLeft(), and MergeRight().

72 { return getRightX(iRightEndY); }
int32_t getRightX(int32_t y) const
Definition: C4FoWBeam.h:64

Here is the call graph for this function:

Here is the caller graph for this function:

float C4FoWBeam::getRightEndXf ( ) const
inline

Definition at line 73 of file C4FoWBeam.h.

References getRightXf().

73 { return getRightXf(iRightEndY); }
float getRightXf(int32_t y) const
Definition: C4FoWBeam.h:66

Here is the call graph for this function:

int32_t C4FoWBeam::getRightEndY ( ) const
inline

Definition at line 71 of file C4FoWBeam.h.

Referenced by getDesc(), and C4FoWLightSection::Invalidate().

71 { return iRightEndY; }

Here is the caller graph for this function:

int32_t C4FoWBeam::getRightX ( int32_t  y) const
inline

Definition at line 64 of file C4FoWBeam.h.

Referenced by getDesc(), and getRightEndX().

64 { return iRightX * y / iRightY; }

Here is the caller graph for this function:

float C4FoWBeam::getRightXf ( int32_t  y) const
inline

Definition at line 66 of file C4FoWBeam.h.

Referenced by getRightEndXf().

66 { return (iRightX * y) / float(iRightY); }

Here is the caller graph for this function:

bool C4FoWBeam::isClean ( ) const
inline

Definition at line 58 of file C4FoWBeam.h.

58 { return !fDirty; }
bool C4FoWBeam::isDirty ( ) const
inline

Definition at line 57 of file C4FoWBeam.h.

Referenced by EliminateRight(), C4FoWLightSection::Invalidate(), MergeDirty(), MergeLeft(), MergeRight(), Split(), and C4FoWLightSection::Update().

57 { return fDirty; }

Here is the caller graph for this function:

bool C4FoWBeam::isInside ( int32_t  x,
int32_t  y 
) const
inline

returns whether the given point is inside the triangle that is defined by this beam

Definition at line 88 of file C4FoWBeam.h.

References isLeft(), and isRight().

Referenced by Split().

88  {
89  return !isLeft(x, y) && !isRight(x, y);
90  }
bool isRight(int32_t x, int32_t y) const
Definition: C4FoWBeam.h:83
bool isLeft(int32_t x, int32_t y) const
Definition: C4FoWBeam.h:78

Here is the call graph for this function:

Here is the caller graph for this function:

bool C4FoWBeam::isLeft ( int32_t  x,
int32_t  y 
) const
inline

returns whether the given point is left of an imaginery line drawn from the origin to the left delimiter point (point is left of beam)

Definition at line 78 of file C4FoWBeam.h.

Referenced by C4FoWLightSection::Invalidate(), isInside(), MergeLeft(), and C4FoWLightSection::Update().

78  {
79  return iLeftX * y > x * iLeftY;
80  }

Here is the caller graph for this function:

bool C4FoWBeam::isRight ( int32_t  x,
int32_t  y 
) const
inline

returns whether the given point is right of an imaginery line drawn from the origin to the right delimiter point (point is right of beam)

Definition at line 83 of file C4FoWBeam.h.

Referenced by isInside(), and MergeRight().

83  {
84  return iRightX * y < x * iRightY;
85  }

Here is the caller graph for this function:

void C4FoWBeam::MergeDirty ( )

Definition at line 136 of file C4FoWBeam.cpp.

References Dirty(), getLeftEndY(), getNext(), and isDirty().

Referenced by C4FoWLightSection::Invalidate().

137 {
138  // As a rule, dirty beams following each other should
139  // always be merged, so splits can be reverted once
140  // the landscape changes.
141  C4FoWBeam *pWith = pNext;
142  assert(isDirty()); assert(!!pWith); assert(pWith->isDirty());
143 
144  // Figure out how far the new dirty beams reaches. Note that
145  // we might lose information about the landscape here.
146  Dirty(std::min(getLeftEndY(), pWith->getLeftEndY()));
147 
148  // Set right
149  iRightX = pWith->iRightX;
150  iRightY = pWith->iRightY;
151 
152  // Relink & delete
153  pNext = pWith->getNext();
154  delete pWith;
155 }
int32_t getLeftEndY() const
Definition: C4FoWBeam.h:68
void Dirty(int32_t y)
Definition: C4FoWBeam.cpp:165
bool isDirty() const
Definition: C4FoWBeam.h:57
C4FoWBeam * getNext() const
Definition: C4FoWBeam.h:59

Here is the call graph for this function:

Here is the caller graph for this function:

bool C4FoWBeam::MergeLeft ( int32_t  x,
int32_t  y 
)

Set the new left delimiter point to the given point if the resulting difference in size is less than the error threshold. If successfull, adds the introduced error to iError.

Asserts that the given point is really left of the right delimiter point

Definition at line 70 of file C4FoWBeam.cpp.

References C4FoWMergeThreshold, getLeftEndX(), getRightEndX(), isDirty(), and isLeft().

71 {
72  assert(!isDirty()); assert(isLeft(x, y));
73 
74  // Calculate error.
75  float iErr = getDoubleTriangleSurface(
76  getLeftEndX(), iLeftEndY,
77  getRightEndX(), iRightEndY,
78  x, y);
79  if (iError + iErr > C4FoWMergeThreshold)
80  return false;
81 
82  // Move left endpoint.
83  iLeftX = x;
84  iLeftY = y;
85  iLeftEndY = y;
86  iError += iErr;
87  return true;
88 }
const int32_t C4FoWMergeThreshold
Definition: C4FoWBeam.cpp:23
int32_t getRightEndX() const
Definition: C4FoWBeam.h:72
bool isDirty() const
Definition: C4FoWBeam.h:57
bool isLeft(int32_t x, int32_t y) const
Definition: C4FoWBeam.h:78
int32_t getLeftEndX() const
Definition: C4FoWBeam.h:69

Here is the call graph for this function:

bool C4FoWBeam::MergeRight ( int32_t  x,
int32_t  y 
)

Set the new right delimiter point to the given point if the resulting difference in size is less than the error threshold. If successfull, adds the introduced error to iError.

Asserts that the given point is really right of the right delimiter point

Definition at line 45 of file C4FoWBeam.cpp.

References C4FoWMergeThreshold, getLeftEndX(), getRightEndX(), isDirty(), and isRight().

Referenced by C4FoWLightSection::Update().

46 {
47  // Note: Right-merging is the most common and most important optimization.
48  // This procedure will probably be *hammered* as a result. Worth inlining?
49 
50  assert(!isDirty()); assert(isRight(x, y));
51 
52  // Calculate error. Note that simply summing up errors is not correct,
53  // strictly speaking (as new and old error surfaces might overlap). Still,
54  // this is quite elaborate already, no need to make it even more
55  int32_t iErr = getDoubleTriangleSurface(
56  getLeftEndX(), iLeftEndY,
57  getRightEndX(), iRightEndY,
58  x, y);
59  if (iError + iErr > C4FoWMergeThreshold)
60  return false;
61 
62  // Move right endpoint.
63  iRightX = x;
64  iRightY = y;
65  iRightEndY = y;
66  iError += iErr;
67  return true;
68 }
bool isRight(int32_t x, int32_t y) const
Definition: C4FoWBeam.h:83
const int32_t C4FoWMergeThreshold
Definition: C4FoWBeam.cpp:23
int32_t getRightEndX() const
Definition: C4FoWBeam.h:72
bool isDirty() const
Definition: C4FoWBeam.h:57
int32_t getLeftEndX() const
Definition: C4FoWBeam.h:69

Here is the call graph for this function:

Here is the caller graph for this function:

void C4FoWBeam::Prune ( int32_t  y)

Prune this beam to a new maximum length. Called when the size of the light has been decreased to the given value.

Definition at line 173 of file C4FoWBeam.cpp.

References Clean().

174 {
175  // Check which sides we need to prune
176  bool fLeft = (iLeftEndY >= y),
177  fRight = (iRightEndY >= y);
178  // If both sides got pruned, we are clean
179  // (can't possibly extend this beam further)
180  if (fLeft && fRight)
181  Clean(y);
182  else if (fLeft)
183  iLeftEndY = y;
184  if (fRight)
185  iRightEndY = y;
186 }
void Clean(int32_t y)
Definition: C4FoWBeam.cpp:157

Here is the call graph for this function:

void C4FoWBeam::SetLeft ( int32_t  x,
int32_t  y 
)
inline

Definition at line 92 of file C4FoWBeam.h.

Referenced by C4FoWLightSection::Update().

92 { iLeftX = x; iLeftY = y; }

Here is the caller graph for this function:

void C4FoWBeam::setNext ( C4FoWBeam next)
inline

Definition at line 60 of file C4FoWBeam.h.

Referenced by C4FoWLightSection::CompileFunc().

60 { pNext=next; }

Here is the caller graph for this function:

void C4FoWBeam::SetRight ( int32_t  x,
int32_t  y 
)
inline

Definition at line 93 of file C4FoWBeam.h.

93 { iRightX = x; iRightY = y; }
C4FoWBeam * C4FoWBeam::Split ( int32_t  x,
int32_t  y 
)

Split this beam into two: this beam and the returned one. The given point x,y is the position at which the two resulting beams are connected with their left/right endpoints. It is asserted that the given point is inside the previous beam. (So the beam can only made smaller)

Definition at line 117 of file C4FoWBeam.cpp.

References C4FoWBeam(), Dirty(), isDirty(), and isInside().

Referenced by C4FoWLightSection::Update().

118 {
119  // Make sure to never create negative-surface beams
120  assert(isDirty()); assert(isInside(x, y));
121 
122  // Allocate a new beam. Ugh, expensive.
123  C4FoWBeam *pBeam = new C4FoWBeam(x, y, iRightX, iRightY);
124  pBeam->Dirty(iLeftEndY);
125 
126  // Move to make space
127  iRightX = x;
128  iRightY = y;
129 
130  // Relink
131  pBeam->pNext = pNext;
132  pNext = pBeam;
133  return pBeam;
134 }
void Dirty(int32_t y)
Definition: C4FoWBeam.cpp:165
bool isDirty() const
Definition: C4FoWBeam.h:57
C4FoWBeam(int32_t iLeftX, int32_t iLeftY, int32_t iRightX, int32_t iRightY)
Definition: C4FoWBeam.h:40
bool isInside(int32_t x, int32_t y) const
Definition: C4FoWBeam.h:88

Here is the call graph for this function:

Here is the caller graph for this function:


The documentation for this class was generated from the following files: