mercator  0.4.0
A terrain generation library for the Worldforge system.
AreaShader.cpp
1 // This file may be redistributed and modified only under the terms of
2 // the GNU General Public License (See COPYING for details).
3 // Copyright (C) 2005 Alistair Riddoch
4 
5 #ifdef HAVE_CONFIG_H
6 #include "config.h"
7 #endif
8 
9 #include "AreaShader.h"
10 #include "Area.h"
11 #include "iround.h"
12 #include "Segment.h"
13 #include "Surface.h"
14 
15 #include <list>
16 #include <set>
17 #include <iostream>
18 #include <algorithm>
19 #include <cmath>
20 
21 #include <cassert>
22 
23 namespace Mercator
24 {
25 
26 typedef WFMath::Point<2> Point2;
27 typedef WFMath::Vector<2> Vector2;
28 
29 const WFMath::CoordType ROW_HEIGHT = 1 / 4.0f; // 4x over-sample
30 
32 class Edge
33 {
34 public:
39  Edge(const Point2& a, const Point2& b)
40  {
41  // horizontal segments should be discarded earlier
42  assert(a.y() != b.y());
43 
44  if (a.y() < b.y()) {
45  m_start = a;
46  m_seg = b - a;
47  } else {
48  m_start = b;
49  m_seg = a - b;
50  }
51 
52  // normal gradient is y/x, here we use x/y. seg.y() will be != 0,
53  // as we already asserted above.
54  m_inverseGradient = m_seg.x() / m_seg.y();
55  }
56 
58  Point2 start() const { return m_start; }
60  Point2 end() const { return m_start + m_seg; }
61 
67  WFMath::CoordType xValueAtZ(WFMath::CoordType z) const
68  {
69  WFMath::CoordType x = m_start.x() + ((z - m_start.y()) * m_inverseGradient);
70  // std::cout << "edge (" << m_start << ", " << m_start + m_seg << ") at z=" << z << " has x=" << x << std::endl;
71  return x;
72  }
73 
78  bool operator<(const Edge& other) const
79  {
80  return m_start.y() < other.m_start.y();
81  }
82 private:
84  Point2 m_start;
86  Vector2 m_seg;
88  WFMath::CoordType m_inverseGradient;
89 };
90 
92 class EdgeAtZ
93 {
94 public:
98  explicit EdgeAtZ(WFMath::CoordType y) : m_y(y) {}
99 
101  bool operator()(const Edge& u, const Edge& v) const
102  {
103  return u.xValueAtZ(m_y) < v.xValueAtZ(m_y);
104  }
105 private:
107  WFMath::CoordType m_y;
108 };
109 
110 static void contribute(Surface& s,
111  unsigned int x, unsigned int z,
112  WFMath::CoordType amount)
113 {
114  unsigned int sz = s.getSize() - 1;
115  if ((x == 0) || (x == sz))
116  amount *= 2;
117 
118  if ((z == 0) || (z == sz))
119  amount *= 2;
120 
121  s(x, z, 0) = std::min(static_cast<ColorT>(I_ROUND(amount * 255)) + s(x,z,0), 255);
122 }
123 
124 static void span(Surface& s,
125  WFMath::CoordType z,
126  WFMath::CoordType xStart,
127  WFMath::CoordType xEnd)
128 {
129  assert(xStart <= xEnd);
130 
131  // quantize and accumulate into the buffer data
132  unsigned int row = I_ROUND(z),
133  ixStart = I_ROUND(xStart),
134  ixEnd = I_ROUND(xEnd);
135 
136  //std::cout << "span @ z=" << row << ", " << ixStart << " -> " << ixEnd << std::endl;
137 
138  if (ixStart == ixEnd) {
139  contribute(s, ixStart, row, ROW_HEIGHT * (xEnd - xStart));
140  } else {
141  contribute(s, ixStart, row, ROW_HEIGHT * (ixStart - xStart + 0.5f));
142 
143  for (unsigned int i=ixStart+1; i < ixEnd; ++i)
144  contribute(s, i, row, ROW_HEIGHT);
145 
146  contribute(s, ixEnd, row, ROW_HEIGHT * (xEnd - ixEnd + 0.5f));
147  }
148 }
149 
150 static void scanConvert(const WFMath::Polygon<2>& inPoly, Surface& sf)
151 {
152  if (!inPoly.isValid()) return;
153 
154  std::list<Edge> pending;
155  std::vector<Edge> active;
156 
157  Point2 lastPt = inPoly.getCorner(inPoly.numCorners() - 1);
158  for (std::size_t p=0; p < inPoly.numCorners(); ++p) {
159  Point2 curPt = inPoly.getCorner(p);
160 
161  // skip horizontal edges
162  if (curPt.y() != lastPt.y())
163  pending.emplace_back(lastPt, curPt);
164 
165  lastPt = curPt;
166  }
167 
168  if (pending.empty()) return;
169 
170  // sort edges by starting (lowest) z value
171  pending.sort();
172  active.push_back(pending.front());
173  pending.pop_front();
174 
175  // advance to the row of the first z value, and ensure z sits in the
176  // middle of sample rows - we do this by offseting by 1/2 a row height
177  // if you don't do this, you'll find alternating rows are over/under
178  // sampled, producing a charming striped effect.
179  WFMath::CoordType z = std::floor(active.front().start().y()) + ROW_HEIGHT * 0.5f;
180 
181  for (; !pending.empty() || !active.empty(); z += ROW_HEIGHT)
182  {
183  while (!pending.empty() && (pending.front().start().y() <= z)) {
184  active.push_back(pending.front());
185  pending.pop_front();
186  }
187 
188  // sort by x value - note active will be close to sorted anyway
189  std::sort(active.begin(), active.end(), EdgeAtZ(z));
190 
191  // delete finished edges
192  for (unsigned int i=0; i< active.size(); ) {
193  if (active[i].end().y() <= z)
194  active.erase(active.begin() + i);
195  else
196  ++i;
197  }
198 
199  // draw pairs of active edges
200  for (unsigned int i=1; i < active.size(); i += 2)
201  span(sf, z, active[i - 1].xValueAtZ(z), active[i].xValueAtZ(z));
202  } // of active edges loop
203 }
204 
206  Shader(false /* no color */, true),
207  m_layer(layer)
208 {
209 
210 }
211 
213 {
214  const Segment::Areastore& areas(s.getAreas());
215  return (areas.count(m_layer) > 0);
216 }
217 
219 {
220  ColorT * data = s.getData();
221  unsigned int size = s.getSegment().getSize();
222 
223  unsigned int buflen = size * size;
224  for (unsigned int i = 0; i < buflen; ++i) data[i] = 0;
225 
226  auto& areas = s.m_segment.getAreas();
227  auto it = areas.lower_bound(m_layer);
228  auto itend = areas.upper_bound(m_layer);
229 
230  for (;it != itend; ++it) {
231  // apply to surface in turn
232  if (it->second.area->isHole()) {
233  //TODO: shadeHole
234  } else
235  shadeArea(s, *it->second.area);
236  } // of areas in layer
237 }
238 
239 void AreaShader::shadeArea(Surface& s, const Area& ar) const
240 {
241  WFMath::Polygon<2> clipped = ar.clipToSegment(s.m_segment);
242  assert(clipped.isValid());
243 
244  if (clipped.numCorners() == 0) return;
245 
246  Point2 segOrigin = s.m_segment.getRect().lowCorner();
247  clipped.shift(Point2(0,0) - segOrigin);
248  scanConvert(clipped, s);
249 }
250 
251 } // of namespace
The edge of an area parallel to the x axis.
Definition: AreaShader.cpp:92
DataType * getData()
Accessor for a pointer to buffer containing data values.
Definition: Buffer.h:63
Point2 start() const
Accessor for the point describing the start of the edge.
Definition: AreaShader.cpp:58
unsigned int getSize() const
Accessor for the size of segment, m_res + 1.
Definition: Buffer.h:53
AreaShader(int layer)
Constructor.
Definition: AreaShader.cpp:205
WFMath::Polygon< 2 > clipToSegment(const Segment &s) const
Clip the shape of this area to a given segment.
Definition: Area.cpp:244
WFMath::AxisBox< 2 > getRect() const
The 2d area covered by this segment.
Definition: Segment.cpp:337
Data store for terrain surface data.
Definition: Surface.h:23
bool checkIntersect(const Segment &) const override
Check whether this Shader has any effect on the given Segment.
Definition: AreaShader.cpp:212
void shade(Surface &s) const override
Populate a Surface with data.
Definition: AreaShader.cpp:218
WFMath::CoordType xValueAtZ(WFMath::CoordType z) const
Determine the x coordinate at a given y coordinate.
Definition: AreaShader.cpp:67
bool operator()(const Edge &u, const Edge &v) const
Determine which edge crosses this edge at a lower x coordinate.
Definition: AreaShader.cpp:101
int getSize() const
Accessor for array size of this segment.
Definition: Segment.h:88
Edge(const Point2 &a, const Point2 &b)
Constructor.
Definition: AreaShader.cpp:39
Class storing heightfield and other data for a single fixed size square area of terrain defined by fo...
Definition: Segment.h:37
const Areastore & getAreas() const
Accessor for multimap of Area objects.
Definition: Segment.h:201
const Segment & m_segment
The terrain height segment this buffer is associated with.
Definition: Surface.h:28
Base class for Shader objects which create surface data for use when rendering terrain.
Definition: Shader.h:25
The edge of an area.
Definition: AreaShader.cpp:32
const Segment & getSegment() const
Accessor for the terrain height segment this surface is associated with.
Definition: Surface.h:37
EdgeAtZ(WFMath::CoordType y)
Definition: AreaShader.cpp:98
std::multimap< int, AreaEntry > Areastore
STL multimap of pointers to Area objects affecting this segment.
Definition: Segment.h:48
bool operator<(const Edge &other) const
Compare the y coordinate of the start with another edge.
Definition: AreaShader.cpp:78
Region of terrain surface which is modified.
Definition: Area.h:28
Point2 end() const
Determine the point describing the end of the edge.
Definition: AreaShader.cpp:60