nel/src/3d/quad_effect.cpp

   1 // NeL - MMORPG Framework <http://dev.ryzom.com/projects/nel/>
   2 // Copyright (C) 2010  Winch Gate Property Limited
   3 //
   4 // This program is free software: you can redistribute it and/or modify
   5 // it under the terms of the GNU Affero General Public License as
   6 // published by the Free Software Foundation, either version 3 of the
   7 // 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 Affero General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Affero General Public License
  15 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16
  17 #include "std3d.h"
  18
  19 #include "nel/3d/quad_effect.h"
  20 #include <algorithm>
  21 #include <deque>
  22
  23 #ifdef DEBUG_NEW
  24 #define new DEBUG_NEW
  25 #endif
  26
  27 namespace NL3D
  28 {
  29
  30 // a 2d edge, ordered so that p1 is the highest point of the edge
  31 struct CEdge
  32 {
  33         CEdge(const NLMISC::CVector2f &p1, const NLMISC::CVector2f &p2)
  34         {
  35                 if (p1.y < p2.y)
  36                 {
  37                         P1 = p1;
  38                         P2 = p2;
  39                 }
  40                 else
  41                 {
  42                         P2 = p1;
  43                         P1 = p2;
  44                 }
  45         }
  46
  47         NLMISC::CVector2f P1, P2;
  48 };
  49
  50 // compares 2 edge, and take the highest
  51 bool operator<(const CEdge &e1, const CEdge &e2) { return e1.P1.y < e2.P1.y; }
  52
  53 typedef std::deque<CEdge> TEdgeList;
  54
  55
  56 void CQuadEffect::makeRasters(const TPoint2DVect &poly
  57                                                         , float quadWidth, float quadHeight
  58                                                         , TRasters &dest, float &startY
  59                                                    )
  60 {
  61
  62         dest.clear();
  63         startY = 0.f;
  64
  65         sint size = (sint)poly.size();
  66
  67         if (!size) return;
  68
  69     const float epsilon = 10E-5f;
  70         uint aelSize = 0; // size of active edge list
  71
  72         sint k; // loop counter
  73
  74         static TEdgeList lel, ael; // the left edge list, and the active edge list
  75         float highest = poly[0].y;
  76         lel.clear();
  77         ael.clear();
  78
  79         /// build a segment list, and go through it;
  80
  81         for (k = 0; k < size; ++k)
  82         {
  83
  84                 lel.push_front(
  85                                                 CEdge(poly[k], poly[k == (size - 1) ? 0 : k + 1])
  86                                   );
  87                 if (poly[k].y < highest) { highest = poly[k].y; }
  88         }
  89
  90         /// sort the segs
  91         std::sort(lel.begin(), lel.end());
  92
  93         bool  borderFound;
  94         float left = 0.f, right = 0.f, inter, diff;
  95         float currY = highest;
  96         startY = highest;
  97
  98         TEdgeList::iterator elIt;
  99
 100         do
 101         {
 102                 /// fetch new segment into the ael
 103                 while (size
 104                            && lel.begin()->P1.y < (currY +  quadHeight)
 105                           )
 106                 {
 107                         ael.push_front(lel.front());
 108                         lel.pop_front();
 109                         --size;
 110                         ++ aelSize;
 111                 }
 112
 113                 if (aelSize)
 114                 {
 115
 116                         borderFound = false;
 117
 118                         for (elIt = ael.begin(); elIt != ael.end();)
 119                         {
 120                                 if (elIt->P2.y <= currY)
 121                                 {
 122                                         // edge has gone out of active edge list
 123                                         elIt = ael.erase(elIt);
 124                                         if (! --aelSize) return;
 125                                         continue;
 126                                 }
 127                                 else
 128                                 {
 129
 130                                         /** edge is in scope. compute its extreme positions
 131                                           * so we need to intersect it with the y = currY and y =  currY + quadHeight lines
 132                                           */
 133
 134                                         /// top of the edge
 135                                         if (elIt->P1.y >= currY)
 136                                         {
 137                                                 if (!borderFound)
 138                                                 {
 139                                                         left = right = elIt->P1.x;
 140                                                         borderFound = true;
 141                                                 }
 142                                                 else
 143                                                 {
 144                                                         left = std::min(left, elIt->P1.x);
 145                                                         right = std::max(right, elIt->P1.x);
 146                                                 }
 147                                         }
 148                                         else
 149                                         {
 150                                                 // compute intersection
 151                                                 diff = elIt->P2.y - elIt->P1.y;
 152                                                 if (diff > epsilon)
 153                                                 {
 154                                                         inter = elIt->P1.x + (elIt->P2.x - elIt->P1.x) * (currY - elIt->P1.y) / diff;
 155                                                 }
 156                                                 else
 157                                                 {
 158                                                         inter = elIt->P2.x;
 159                                                 }
 160
 161                                                 if (!borderFound)
 162                                                 {
 163                                                         left = right = inter;
 164                                                         borderFound = true;
 165                                                 }
 166                                                 else
 167                                                 {
 168                                                         left = std::min(left, inter);
 169                                                         right = std::max(right, inter);
 170                                                 }
 171                                         }
 172
 173                                         /// bottom of the edge
 174
 175                                         if (elIt->P2.y <= currY + quadHeight)
 176                                         {
 177                                                 if (!borderFound)
 178                                                 {
 179                                                         left = right = elIt->P2.x;
 180                                                         borderFound = true;
 181                                                 }
 182                                                 else
 183                                                 {
 184                                                         left = std::min(left, elIt->P2.x);
 185                                                         right = std::max(right, elIt->P2.x);
 186                                                 }
 187                                         }
 188                                         else
 189                                         {
 190                                                 // compute intersection
 191                                                 diff = elIt->P2.y - elIt->P1.y;
 192                                                 if (diff > epsilon)
 193                                                 {
 194                                                         inter = elIt->P1.x + (elIt->P2.x - elIt->P1.x) * (currY + quadHeight - elIt->P1.y) / diff;
 195                                                 }
 196                                                 else
 197                                                 {
 198                                                         inter = elIt->P2.x;
 199                                                 }
 200
 201                                                 if (!borderFound)
 202                                                 {
 203                                                         left = right = inter;
 204                                                         borderFound = true;
 205                                                 }
 206                                                 else
 207                                                 {
 208                                                         left = std::min(left, inter);
 209                                                         right = std::max(right, inter);
 210                                                 }
 211                                         }
 212
 213                                 }
 214                                 ++ elIt;
 215                         }
 216
 217                         dest.push_back(std::make_pair(left, right));
 218                 }
 219
 220                 currY += quadHeight;
 221
 222         }
 223         while (size || aelSize);
 224 }
 225
 226 //**
 227
 228 void CQuadEffect::processPoly(const TPoint2DVect &poly
 229                                                         , float quadWidth, float quadHeight
 230                                                         , TPoint2DVect &dest
 231                                                    )
 232 {
 233         static TRasters rDest;
 234         float currY;
 235         makeRasters(poly, quadWidth, quadHeight, rDest, currY);
 236         if (!dest.empty())
 237         {
 238                 TRasters::const_iterator it, endIt = rDest.end();
 239                 for (it = rDest.begin(); it != endIt; ++it)
 240                 {
 241                         const sint nbQuad = (sint) ceilf( (it->second - it->first) / quadWidth);
 242                         float currX = it->first;
 243                         for (sint k = 0; k < nbQuad; ++k)
 244                         {
 245                                 dest.push_back(NLMISC::CVector2f(currX, currY));
 246                                 currX += quadWidth;
 247                         }
 248                         currY += quadHeight;
 249                 }
 250         }
 251 }
 252
 253
 254 } // NL3D