gemrb/core/Polygon.cpp

   1 /* GemRB - Infinity Engine Emulator
   2  * Copyright (C) 2003 The GemRB Project
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  17  *
  18  */
  19
  20 #include "Polygon.h"
  21
  22 #include "win32def.h"
  23
  24 #include "Interface.h"
  25
  26 #include <algorithm>
  27 #include <cstring>
  28 #include <vector>
  29
  30 Gem_Polygon::Gem_Polygon(Point* points, unsigned int cnt, Region *bbox)
  31 {
  32         if (cnt) {
  33                 this->points = ( Point * ) malloc( cnt * sizeof( Point ) );
  34                 memcpy( this->points, points, cnt * sizeof( Point ) );
  35         } else {
  36                 this->points = NULL;
  37         }
  38         count = cnt;
  39         if(bbox) BBox=*bbox;
  40         else RecalcBBox();
  41
  42         ComputeTrapezoids();
  43 }
  44
  45 Gem_Polygon::~Gem_Polygon(void)
  46 {
  47         if (points) {
  48                 free( points );
  49         }
  50 }
  51
  52 void Gem_Polygon::RecalcBBox()
  53 {
  54         if(!count) {
  55                 BBox.x=BBox.y=BBox.w=BBox.h=0;
  56                 return;
  57         }
  58         BBox.x=points[0].x;
  59         BBox.y=points[0].y;
  60         BBox.w=points[0].x;
  61         BBox.h=points[0].y;
  62         unsigned int i;
  63         for(i=1; i<count; i++) {
  64                 if(points[i].x<BBox.x) {
  65                         BBox.x=points[i].x;
  66                 }
  67                 if(points[i].x>BBox.w) {
  68                         BBox.w=points[i].x;
  69                 }
  70                 if(points[i].y<BBox.y) {
  71                         BBox.y=points[i].y;
  72                 }
  73                 if(points[i].y>BBox.h) {
  74                         BBox.h=points[i].y;
  75                 }
  76         }
  77         BBox.w-=BBox.x;
  78         BBox.h-=BBox.y;
  79 }
  80
  81 bool Gem_Polygon::PointIn(const Point &p) const
  82 {
  83         if(!BBox.PointInside(p) ) return false;
  84         return PointIn(p.x, p.y);
  85 }
  86
  87 bool Gem_Polygon::PointIn(int tx, int ty) const
  88 {
  89         register int   j, yflag0, yflag1, xflag0 , index;
  90         bool inside_flag = false;
  91         Point* vtx0, * vtx1;
  92
  93         if (count<3) {
  94                 return false;
  95         }
  96         index = 0;
  97
  98         vtx0 = &points[count - 1];
  99         yflag0 = ( vtx0->y >= ty );
 100         vtx1 = &points[index];
 101
 102         for (j = count + 1; --j ;) {
 103                 yflag1 = ( vtx1->y >= ty );
 104                 if (yflag0 != yflag1) {
 105                         xflag0 = ( vtx0->x >= tx );
 106                         if (xflag0 == ( vtx1->x >= tx )) {
 107                                 if (xflag0)
 108                                         inside_flag = !inside_flag;
 109                         } else {
 110                                 if (( vtx1->x -
 111                                         ( vtx1->y - ty ) * ( vtx0->x - vtx1->x ) /
 112                                         ( vtx0->y - vtx1->y ) ) >= tx) {
 113                                         inside_flag = !inside_flag;
 114                                 }
 115                         }
 116                 }
 117                 yflag0 = yflag1;
 118                 vtx0 = vtx1;
 119                 vtx1 = &points[++index];
 120         }
 121         return inside_flag;
 122 }
 123
 124 // returns twice the area of triangle a, b, c.
 125 // (can also be negative depending on orientation of a,b,c)
 126 inline int area2(const Point& a, const Point& b, const Point& c)
 127 {
 128         return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
 129 }
 130
 131
 132 // return (c is to the left of a-b)
 133 inline bool left(const Point& a, const Point& b, const Point& c)
 134 {
 135         return (area2(a, b, c) > 0);
 136 }
 137
 138 // { return (c is collinear with a-b)
 139 inline bool collinear(const Point& a, const Point& b, const Point& c)
 140 {
 141         return (area2(a, b, c) == 0);
 142 }
 143
 144 // Find the intersection of two segments, if any.
 145 // If the intersection is one of the endpoints, or the lines are
 146 // parallel, false is returned.
 147 // The point returned has the actual intersection coordinates rounded down
 148 // to integers
 149 static bool intersectSegments(Point& a, Point& b, Point& c, Point& d, Point& s)
 150 {
 151         if (collinear(a, b, c) || collinear(a, b, d) ||
 152                 collinear(c, d, a) || collinear(c, d, b))
 153                 return false;
 154
 155         if (!((left(a, b, c) != left(a, b, d)) &&
 156                 (left(c, d, a) != left(c, d, b))))
 157                 return false;
 158
 159         __int64 A1 = area2(c, d, a);
 160         __int64 A2 = area2(d, c, b);
 161
 162         s.x = (short) ((b.x*A1 + a.x*A2) / (A1 + A2));
 163         s.y = (short) ((b.y*A1 + a.y*A2) / (A1 + A2));
 164
 165         return true;
 166 }
 167
 168 // find the intersection of a segment with a horizontal scanline, if any
 169 static bool intersectSegmentScanline(Point& a, Point& b, int y, int& x)
 170 {
 171         int y1 = a.y - y;
 172         int y2 = b.y - y;
 173
 174         if (y1 * y2 > 0) return false;
 175         if (y1 == 0 && y2 == 0) return false;
 176
 177         x = a.x + ((b.x - a.x)*y1)/(y1-y2);
 178         return true;
 179 }
 180
 181
 182 struct ScanlineInt {
 183         int x;
 184         int pi;
 185         Gem_Polygon* p;
 186
 187         bool operator<(const ScanlineInt& i2) const
 188         {
 189                 if (x < i2.x)
 190                         return true;
 191
 192                 if (x > i2.x)
 193                         return false;
 194
 195                 Point& a = p->points[pi];
 196                 Point& b = p->points[(pi+1)%(p->count)];
 197                 Point& c = p->points[i2.pi];
 198                 Point& d = p->points[(i2.pi+1)%(p->count)];
 199
 200                 int dx1 = a.x - b.x;
 201                 int dx2 = c.x - d.x;
 202                 int dy1 = a.y - b.y;
 203                 int dy2 = c.y - d.y;
 204
 205                 if (dy1 < 0) {
 206                         dy1 *= -1;
 207                         dx1 *= -1;
 208                 }
 209
 210                 if (dy2 < 0) {
 211                         dy2 *= -1;
 212                         dx2 *= -1;
 213                 }
 214
 215                 if (dx1 * dy2 > dx2 * dy1) return true;
 216
 217                 return false;
 218         }
 219
 220 };
 221
 222
 223 void Gem_Polygon::ComputeTrapezoids()
 224 {
 225         if (count < 3) return;
 226         //the loader never should load such a large polygon,
 227         //because the polygon count is supposed to be a 16 bit value
 228         if (count > 65535) {
 229                 printMessage("Polygon", "Invalid Polygon!\n", LIGHT_RED);
 230                 abort();
 231         }
 232
 233         trapezoids.clear();
 234         std::vector<int> ys;
 235         ys.reserve(2*count);
 236
 237         // y coords of vertices
 238         unsigned int i;
 239
 240         for (i = 0; i < count; ++i)
 241                 ys.push_back(points[i].y);
 242
 243         Point p;
 244         // y coords of self-intersections
 245         for (unsigned int i1 = 0; i1 < count; ++i1) {
 246                 Point& a = points[i1];
 247                 Point& b = points[(i1+1)%count];
 248
 249                 // intersections with horizontal lines don't matter
 250                 if (a.y == b.y) continue;
 251
 252                 for (unsigned int i2 = i1+2; i2 < count; ++i2) {
 253                         Point& c = points[i2];
 254                         Point& d = points[(i2+1)%count];
 255
 256                         // intersections with horizontal lines don't matter
 257                         if (c.y == d.y) continue;
 258
 259                         if (intersectSegments(a, b, c, d, p)) {
 260                                 ys.push_back(p.y);
 261                         }
 262                 }
 263         }
 264
 265         std::sort(ys.begin(), ys.end());
 266
 267         std::vector<ScanlineInt> ints;
 268         ints.reserve(count);
 269
 270         Trapezoid t;
 271         ScanlineInt is;
 272         is.p = this;
 273         std::list<Trapezoid>::iterator iter;
 274
 275         unsigned int yi = 0;
 276         int cury = ys[0];
 277
 278         // TODO: it's possible to keep a set of 'active' edges and only check
 279         // scanline intersections of those edges.
 280
 281
 282         while (yi < ys.size() - 1) {
 283                 while (yi < ys.size() && ys[yi] == cury) ++yi;
 284                 if (yi == ys.size()) break;
 285                 int nexty = ys[yi];
 286
 287                 t.y1 = cury;
 288                 t.y2 = nexty;
 289
 290                 // Determine all scanline intersections at level nexty.
 291                 // This includes edges which have their lower vertex at nexty,
 292                 // but excludes edges with their upper vertex at nexty.
 293                 // (We're taking the intersections along the 'upper' edge of
 294                 // the nexty scanline.)
 295                 ints.clear();
 296                 for (i = 0; i < count; ++i) {
 297                         Point& a = points[i];
 298                         Point& b = points[(i+1)%count];
 299
 300                         if (a.y == b.y) continue;
 301
 302                         if (a.y == nexty) {
 303                                 if (b.y - nexty < 0) {
 304                                         is.x = a.x;
 305                                         is.pi = i;
 306                                         ints.push_back(is);
 307                                 }
 308                         } else if (b.y == nexty) {
 309                                 if (a.y - nexty < 0) {
 310                                         is.x = b.x;
 311                                         is.pi = i;
 312                                         ints.push_back(is);
 313                                 }
 314                         } else {
 315                                 int x;
 316                                 if (intersectSegmentScanline(a, b, nexty, x)) {
 317                                         is.x = x;
 318                                         is.pi = i;
 319                                         ints.push_back(is);
 320                                 }
 321                         }
 322                 }
 323
 324                 std::sort(ints.begin(), ints.end());
 325                 unsigned int newtcount = (unsigned int) (ints.size() / 2);
 326
 327                 for (i = 0; i < newtcount; ++i) {
 328                         t.left_edge = ints[2*i].pi;
 329                         t.right_edge = ints[2*i+1].pi;
 330
 331
 332                         bool found = false;
 333
 334                         // merge trapezoids with old one if it's just a continuation
 335                         for (iter = trapezoids.begin(); iter != trapezoids.end(); ++iter) {
 336                                 Trapezoid& oldt = *iter;
 337                                 if (oldt.y2 == cury &&
 338                                         oldt.left_edge == t.left_edge &&
 339                                         oldt.right_edge == t.right_edge)
 340                                 {
 341                                         oldt.y2 = nexty;
 342                                         found = true;
 343                                         break;
 344                                 }
 345                         }
 346
 347                         if (!found)
 348                                 trapezoids.push_back(t);
 349                 }
 350
 351                 // Done with this strip
 352                 cury = nexty;
 353         }
 354 }
 355
 356
 357 // wall polygons
 358 void Wall_Polygon::SetBaseline(const Point &a, const Point &b)
 359 {
 360         if ((a.x<b.x) || ((a.x==b.x) && (a.y<b.y)) ) {
 361                 base0=a;
 362                 base1=b;
 363                 return;
 364         }
 365         base0=b;
 366         base1=a;
 367 }
 368
 369 bool Wall_Polygon::PointCovered(const Point &p) const
 370 {
 371         if (wall_flag&WF_DISABLED)
 372                 return false;
 373         if (wall_flag&WF_BASELINE) {
 374                 if (base0.x > base1.x)
 375                         return left(base0, base1, p);
 376                 else
 377                         return left(base1, base0, p);
 378         }
 379         return true;
 380 }
 381
 382 bool Wall_Polygon::PointCovered(int tx, int ty) const
 383 {
 384         Point p((short) tx, (short) ty);
 385         return PointCovered(p);
 386 }
 387