nevrax.org : docs

00001 
+00007 /* Copyright, 2000, 2001 Nevrax Ltd.
+00008  *
+00009  * This file is part of NEVRAX NEL.
+00010  * NEVRAX NEL is free software; you can redistribute it and/or modify
+00011  * it under the terms of the GNU General Public License as published by
+00012  * the Free Software Foundation; either version 2, or (at your option)
+00013  * any later version.
+00014 
+00015  * NEVRAX NEL is distributed in the hope that it will be useful, but
+00016  * WITHOUT ANY WARRANTY; without even the implied warranty of
+00017  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+00018  * General Public License for more details.
+00019 
+00020  * You should have received a copy of the GNU General Public License
+00021  * along with NEVRAX NEL; see the file COPYING. If not, write to the
+00022  * Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+00023  * MA 02111-1307, USA.
+00024  */
+00025 
+00026 #include "std3d.h"
+00027 
+00028 #include "3d/quad_effect.h"
+00029 #include <algorithm>
+00030 #include <deque>
+00031 
+00032 namespace NL3D 
+00033 {
+00034 
+00035 // a 2d edge, ordered so that p1 is the highest point of the edge
+00036 struct CEdge
+00037 {
+00038         CEdge(const NLMISC::CVector2f &p1, const NLMISC::CVector2f &p2)
+00039         {
+00040                 if (p1.y < p2.y)
+00041                 {
+00042                         P1 = p1;
+00043                         P2 = p2;
+00044                 }
+00045                 else
+00046                 {
+00047                         P2 = p1;
+00048                         P1 = p2;
+00049                 }
+00050         }
+00051 
+00052         NLMISC::CVector2f P1, P2;
+00053 };
+00054 
+00055 // compares 2 edge, and take the highest
+00056 bool operator<(const CEdge &e1, const CEdge &e2) { return e1.P1.y < e2.P1.y; }
+00057 
+00058 typedef std::deque<CEdge> TEdgeList;
+00059 
+00060 
+00061 void CQuadEffect::makeRasters(const TPoint2DVect &poly
+00062                                                         , float quadWidth, float quadHeight
+00063                                                         , TRasters &dest, float &startY
+00064                                                    )
+00065 {
+00066 
+00067         dest.clear();
+00068     const float epsilon = 10E-5f;
+00069 
+00070         sint size = poly.size();
+00071         uint aelSize = 0; // size of active edge list
+00072 
+00073         sint k; // loop counter
+00074 
+00075 
+00076 
+00077         dest.clear();
+00078 
+00079         if (!size) return;
+00080 
+00081         static TEdgeList lel, ael; // the left edge list, and the active edge list
+00082         float highest = poly[0].y;
+00083         lel.clear();
+00084         ael.clear();
+00085         
+00087 
+00088         for (k = 0; k < size; ++k)
+00089         {
+00090 
+00091                 lel.push_front(
+00092                                                 CEdge(poly[k], poly[k == (size - 1) ? 0 : k + 1])
+00093                                   );
+00094                 if (poly[k].y < highest) { highest = poly[k].y; }               
+00095         }
+00096 
+00098         std::sort(lel.begin(), lel.end());
+00099 
+00100         bool  borderFound;
+00101         float left, right, inter, diff;
+00102         float currY = highest;
+00103         startY = highest;
+00104         
+00105         TEdgeList::iterator elIt; 
+00106 
+00107         do
+00108         {               
+00110                 while (size 
+00111                            && lel.begin()->P1.y < (currY +  quadHeight)
+00112                           )
+00113                 {
+00114                         ael.push_front(lel.front());
+00115                         lel.pop_front();
+00116                         --size;
+00117                         ++ aelSize;
+00118                 }
+00119 
+00120                 if (aelSize)
+00121                 {
+00122 
+00123                         borderFound = false;
+00124 
+00125                         for (elIt = ael.begin(); elIt != ael.end();)
+00126                         {
+00127                                 if (elIt->P2.y <= currY)
+00128                                 {
+00129                                         // edge has gone out of active edge list
+00130                                         elIt = ael.erase(elIt);
+00131                                         if (! --aelSize) return;
+00132                                         continue;
+00133                                 }
+00134                                 else
+00135                                 {
+00136 
+00141 
+00142                                         if (elIt->P1.y >= currY) 
+00143                                         {                                               
+00144                                                 if (!borderFound)
+00145                                                 {
+00146                                                         left = right = elIt->P1.x;
+00147                                                         borderFound = true;
+00148                                                 }
+00149                                                 else
+00150                                                 {
+00151                                                         left = std::min(left, elIt->P1.x);
+00152                                                         right = std::max(right, elIt->P1.x);
+00153                                                 }
+00154                                         }
+00155                                         else
+00156                                         {
+00157                                                 // compute intersection
+00158                                                 diff = elIt->P2.y - elIt->P1.y;
+00159                                                 if (diff > epsilon)
+00160                                                 {
+00161                                                         inter = elIt->P1.x + (elIt->P2.x - elIt->P1.x) * (currY - elIt->P1.y) / diff;
+00162                                                 }
+00163                                                 else
+00164                                                 {
+00165                                                         inter = elIt->P2.x;
+00166                                                 }
+00167 
+00168                                                 if (!borderFound)
+00169                                                 {
+00170                                                         left = right = inter;
+00171                                                         borderFound = true;
+00172                                                 }
+00173                                                 else
+00174                                                 {
+00175                                                         left = std::min(left, inter);
+00176                                                         right = std::max(right, inter);
+00177                                                 }
+00178                                         }
+00179 
+00181 
+00182                                         if (elIt->P2.y <= currY + quadHeight) 
+00183                                         {                                               
+00184                                                 if (!borderFound)
+00185                                                 {
+00186                                                         left = right = elIt->P2.x;
+00187                                                         borderFound = true;
+00188                                                 }
+00189                                                 else
+00190                                                 {
+00191                                                         left = std::min(left, elIt->P2.x);
+00192                                                         right = std::max(right, elIt->P2.x);
+00193                                                 }
+00194                                         }
+00195                                         else
+00196                                         {
+00197                                                 // compute intersection
+00198                                                 diff = elIt->P2.y - elIt->P1.y;
+00199                                                 if (diff > epsilon)
+00200                                                 {
+00201                                                         inter = elIt->P1.x + (elIt->P2.x - elIt->P1.x) * (currY + quadHeight - elIt->P1.y) / diff;
+00202                                                 }
+00203                                                 else
+00204                                                 {
+00205                                                         inter = elIt->P2.x;
+00206                                                 }
+00207 
+00208                                                 if (!borderFound)
+00209                                                 {
+00210                                                         left = right = inter;
+00211                                                         borderFound = true;
+00212                                                 }
+00213                                                 else
+00214                                                 {
+00215                                                         left = std::min(left, inter);
+00216                                                         right = std::max(right, inter);
+00217                                                 }
+00218                                         }
+00219                                         
+00220                                 }
+00221                                 ++ elIt;                                
+00222                         }               
+00223 
+00224                         dest.push_back(std::make_pair(left, right));
+00225                 }
+00226 
+00227                 currY += quadHeight;
+00228 
+00229         } while (size || aelSize);      
+00230 }
+00231 
+00232 //**
+00233 
+00234 void CQuadEffect::processPoly(const TPoint2DVect &poly
+00235                                                         , float quadWidth, float quadHeight
+00236                                                         , TPoint2DVect &dest
+00237                                                    )
+00238 {
+00239         static TRasters rDest;
+00240         float currY;
+00241         makeRasters(poly, quadWidth, quadHeight, rDest, currY);
+00242         if (dest.size())
+00243         {
+00244                 TRasters::const_iterator it, endIt = rDest.end();
+00245                 for (it = rDest.begin(); it != endIt; ++it)
+00246                 {
+00247                         const sint nbQuad = (sint) ceilf( (it->second - it->first) / quadWidth);
+00248                         float currX = it->first;
+00249                         for (sint k = 0; k < nbQuad; ++k)
+00250                         {
+00251                                 dest.push_back(NLMISC::CVector2f(currX, currY));                                                                                  
+00252                                 currX += quadWidth;
+00253                         }
+00254                         currY += quadHeight;
+00255                 }
+00256         }
+00257 }
+00258 
+00259 
+00260 } // NL3D
+
quad_effect.cpp
