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
23namespace Mercator
24{
25
26typedef WFMath::Point<2> Point2;
27typedef WFMath::Vector<2> Vector2;
28
29const WFMath::CoordType ROW_HEIGHT = 1 / 4.0f; // 4x over-sample
30
32class Edge
33{
34public:
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 }
82private:
84 Point2 m_start;
86 Vector2 m_seg;
88 WFMath::CoordType m_inverseGradient;
89};
90
93{
94public:
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 }
105private:
107 WFMath::CoordType m_y;
108};
109
110static 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
124static 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
150static 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
239void 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
AreaShader(int layer)
Constructor.
Definition: AreaShader.cpp:205
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
Region of terrain surface which is modified.
Definition: Area.h:29
WFMath::Polygon< 2 > clipToSegment(const Segment &s) const
Clip the shape of this area to a given segment.
Definition: Area.cpp:244
DataType * getData()
Accessor for a pointer to buffer containing data values.
Definition: Buffer.h:63
The edge of an area parallel to the x axis.
Definition: AreaShader.cpp:93
bool operator()(const Edge &u, const Edge &v) const
Determine which edge crosses this edge at a lower x coordinate.
Definition: AreaShader.cpp:101
EdgeAtZ(WFMath::CoordType y)
Definition: AreaShader.cpp:98
The edge of an area.
Definition: AreaShader.cpp:33
Point2 start() const
Accessor for the point describing the start of the edge.
Definition: AreaShader.cpp:58
Point2 end() const
Determine the point describing the end of the edge.
Definition: AreaShader.cpp:60
WFMath::CoordType xValueAtZ(WFMath::CoordType z) const
Determine the x coordinate at a given y coordinate.
Definition: AreaShader.cpp:67
Edge(const Point2 &a, const Point2 &b)
Constructor.
Definition: AreaShader.cpp:39
bool operator<(const Edge &other) const
Compare the y coordinate of the start with another edge.
Definition: AreaShader.cpp:78
Class storing heightfield and other data for a single fixed size square area of terrain defined by fo...
Definition: Segment.h:37
std::multimap< int, AreaEntry > Areastore
STL multimap of pointers to Area objects affecting this segment.
Definition: Segment.h:48
WFMath::AxisBox< 2 > getRect() const
The 2d area covered by this segment.
Definition: Segment.cpp:337
int getSize() const
Accessor for array size of this segment.
Definition: Segment.h:88
const Areastore & getAreas() const
Accessor for multimap of Area objects.
Definition: Segment.h:201
Base class for Shader objects which create surface data for use when rendering terrain.
Definition: Shader.h:25
Data store for terrain surface data.
Definition: Surface.h:23
const Segment & getSegment() const
Accessor for the terrain height segment this surface is associated with.
Definition: Surface.h:37
const Segment & m_segment
The terrain height segment this buffer is associated with.
Definition: Surface.h:28