1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/graphics/windowing/windowserver/nga/SERVER/regionextend.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,336 @@
1.4 +// Copyright (c) 2008-2009 Nokia Corporation and/or its subsidiary(-ies).
1.5 +// All rights reserved.
1.6 +// This component and the accompanying materials are made available
1.7 +// under the terms of "Eclipse Public License v1.0"
1.8 +// which accompanies this distribution, and is available
1.9 +// at the URL "http://www.eclipse.org/legal/epl-v10.html".
1.10 +//
1.11 +// Initial Contributors:
1.12 +// Nokia Corporation - initial contribution.
1.13 +//
1.14 +// Contributors:
1.15 +//
1.16 +// Description:
1.17 +//
1.18 +
1.19 +#include <e32def.h>
1.20 +#include "regionextend.h"
1.21 +
1.22 +//Only call this if certain neither rectangle is empty.
1.23 +//Region rectangles are always non-empty
1.24 +inline /*static*/
1.25 +TRegionExtend::TOverlapFlags TestDifferenceNotEmpty(const TRect& aThis,const TRect& aThat)
1.26 + {
1.27 + struct SubAdd
1.28 + {
1.29 + inline static TRegionExtend::TOverlapFlags Conv(TInt delta)
1.30 + { //returns sub, exact or add for delta of each edge pair
1.31 + //neg --> +1 //pos --> +2 //zero ==> 0
1.32 + return TRegionExtend::TOverlapFlags(
1.33 + ((delta>>31)&1) +(((-delta)>>30)&2) );
1.34 + }
1.35 + };
1.36 + //could use SubAdd for this if...
1.37 + if ( aThis.iTl.iX>=aThat.iBr.iX
1.38 + || aThis.iTl.iY>=aThat.iBr.iY
1.39 + || aThat.iTl.iX>=aThis.iBr.iX
1.40 + || aThat.iTl.iY>=aThis.iBr.iY
1.41 + )
1.42 + return TRegionExtend::TOverlapFlags(TRegionExtend::EDiffers|TRegionExtend::ENoIntersect);
1.43 +
1.44 + TInt subAdd=( SubAdd::Conv(aThis.iTl.iX-aThat.iTl.iX)
1.45 + | SubAdd::Conv(aThis.iTl.iY-aThat.iTl.iY)
1.46 + | SubAdd::Conv(aThat.iBr.iX-aThis.iBr.iX)
1.47 + | SubAdd::Conv(aThat.iBr.iY-aThis.iBr.iY)
1.48 + );
1.49 + return
1.50 + TRegionExtend::TOverlapFlags(subAdd);
1.51 + }
1.52 +
1.53 +/** Calc total area of a list of non-intersecting rectangles (ie a region)
1.54 + * @param aThisRects the array of rectangles
1.55 + * @param aThisCount the number in the array
1.56 + */
1.57 +inline TUint RectListArea(const TRect* aThisRects,TInt aThisCount)
1.58 + {
1.59 + TInt thisArea=0;
1.60 + for (TInt stepThis=aThisCount-1;stepThis>=0;stepThis--)
1.61 + {
1.62 + TSize size=aThisRects[stepThis].Size();
1.63 + __ASSERT_DEBUG((size.iWidth|size.iHeight)<32768,User::Panic(_L("TRegionExtend"),4003));
1.64 + thisArea+=size.iWidth*size.iHeight;
1.65 + }
1.66 + return thisArea;
1.67 + }
1.68 +/** Returns the result code flag based on the calculated intersection of two areas
1.69 + * The intersection is always less than or equal to this and that.
1.70 + * @param aThisArea Start area
1.71 + * @param aIntersectArea Intersection
1.72 + * @param aThatArea Final area
1.73 + * @return
1.74 + * - EDiffers if both this and that differ from intersect
1.75 + * - EExact if both this and that are same as intersect
1.76 + * - ESub if only that is same as intersect, so this is bigger
1.77 + * - EAdd if only this is same as intersect, so that is bigger
1.78 + *
1.79 + **/
1.80 +inline TRegionExtend::TOverlapFlags AreaDiffResults(TUint aThisArea,TUint aIntersectArea,TUint aThatArea)
1.81 + {
1.82 + if (aThisArea>aIntersectArea)
1.83 + if (aThatArea>aIntersectArea)
1.84 + return TRegionExtend::EDiffers;
1.85 + else
1.86 + return TRegionExtend::ESub;
1.87 + else
1.88 + if (aThatArea>aIntersectArea)
1.89 + return TRegionExtend::EAdd;
1.90 + else
1.91 + return TRegionExtend::EExact;
1.92 + }
1.93 +/** Calculates the intersection area of one rectangle with an array of non intersecting rectangles
1.94 + * It is presumed that the caller will loop through all the cells of a target region,
1.95 + * repeating this call for a source region, so we can add an extra optimisation
1.96 + * to avoid revisiting any source rectangles that have been consumed completely in later passes.
1.97 + * The simplest test is that the source cell is wholy inside the target rect.
1.98 + * The simplest record is a bit field, but that only works up to 32 elements, then will not optimise further elements.
1.99 + * @param aThisCount num elements in rect array
1.100 + * @param aThisRects array of rectangles
1.101 + * @param aThatRect intersecting rectangle
1.102 + * @param aOptimiseThisBits record of elements of rect aray that have been fully consumed
1.103 + * @return total intersection area
1.104 + **/
1.105 +inline TUint TestDifferenceRegionInnerLoop(TInt aThisCount,const TRect* aThisRects,TRect& aThatRect,TUint& aOptimiseThisBits)
1.106 + {
1.107 + TUint intersectArea=0;
1.108 + for (TInt stepThis=aThisCount-1,bit=1;stepThis>=0;stepThis--,bit<<=1)
1.109 + {
1.110 + if (!(aOptimiseThisBits&bit))
1.111 + {
1.112 + const TRect& thisRect=aThisRects[stepThis];
1.113 + TRegionExtend::TOverlapFlags flags=TestDifferenceNotEmpty(thisRect,aThatRect);
1.114 + if (!(flags&TRegionExtend::ENoIntersect))
1.115 + {
1.116 + if (!(flags&TRegionExtend::EAdd))
1.117 + { //Skip rest of inner loop if a containing rect is found
1.118 + TSize size=aThatRect.Size();
1.119 + intersectArea+=size.iWidth*size.iHeight;
1.120 + if (!(flags&TRegionExtend::ESub)) //equal rects...
1.121 + { //skip this cell for rest of outer loop if a contains rect is found
1.122 + aOptimiseThisBits|=bit;
1.123 + }
1.124 + break; //this cell contains the target rect so don't bother checking any more
1.125 + }
1.126 + else
1.127 + if (!(flags&TRegionExtend::ESub))
1.128 + { //skip this cell for rest of outer loop if a contains rect is found
1.129 + aOptimiseThisBits|=bit;
1.130 + TSize size=thisRect.Size();
1.131 + intersectArea+=size.iWidth*size.iHeight;
1.132 + }
1.133 + else
1.134 + {
1.135 + TRect intersect=thisRect;
1.136 + intersect.Intersection(aThatRect);
1.137 + TSize size=intersect.Size();
1.138 + intersectArea+=size.iWidth*size.iHeight;
1.139 + }
1.140 + }
1.141 + }
1.142 + }
1.143 + return intersectArea;
1.144 + }
1.145 +/** Avoids the use of a temp region by performing area calc on the fly.
1.146 + * If both regions are empty then EOverlapNoIntersect only is returned.
1.147 + * @param aThat target region
1.148 + * @return flags from TOverlapFlags enumeration
1.149 + * - EExact =0 if rgions are exactly identical
1.150 + * - ESub Flagged if some rectangles are removed converting current region to that target
1.151 + * - EAdd Flagged if some rectangles are added converting current region to that target
1.152 + * - ENoIntersect if there is no common region between the current region and that target
1.153 + * - EErrorRegion One of the regions is signalling CheckError()
1.154 + **/
1.155 +TRegionExtend::TOverlapFlags TRegionExtend::TestDifference(const TRegion& aThat)const
1.156 + {
1.157 + TInt intersectArea=0;
1.158 + TInt thisArea=0;
1.159 + TInt thatArea=0;
1.160 + const TRect* thisRects=RectangleList();
1.161 + const TRect* thatRects=aThat.RectangleList();
1.162 + TInt thatCount=aThat.Count();
1.163 + TInt thisCount=Count();
1.164 +
1.165 + if (CheckError()||aThat.CheckError())
1.166 + return EErrorRegion;
1.167 + if (thisCount==0)
1.168 + if (thatCount==0)
1.169 + return ENoIntersect;
1.170 + else
1.171 + return TOverlapFlags(ENoIntersect|EAdd);
1.172 + //both regions are populated. How big is the intersection?
1.173 + //The following optimisation bit is that
1.174 + //if any rect is fully contained by a rect in the opposite region
1.175 + //then further compares against that rect are skipped. For this, inner loop is skipped immediately
1.176 + //Can track the first 32 rects of aThat. The remainder won't benefit from the optimisation
1.177 + TUint optimiseThisBits=0;
1.178 + for (TInt stepThat=thatCount-1;stepThat>=0;stepThat--)
1.179 + {
1.180 + TRect thatRect=thatRects[stepThat];
1.181 + intersectArea+=TestDifferenceRegionInnerLoop(thisCount,thisRects,thatRect,optimiseThisBits);
1.182 + }
1.183 + if (intersectArea==0)
1.184 + if (thatCount==0)
1.185 + return TOverlapFlags(ENoIntersect|ESub);
1.186 + else
1.187 + return TOverlapFlags(ENoIntersect|EAdd|ESub);
1.188 + thatArea=RectListArea(thatRects,thatCount);
1.189 + thisArea=RectListArea(thisRects,thisCount);
1.190 + return AreaDiffResults( thisArea, intersectArea, thatArea );
1.191 + }
1.192 +
1.193 +/** Avoids the use of a temp region by performing area calc on the fly.
1.194 + * This version further optimises the process by avoiding the client having to re-origin either region.
1.195 + * If both regions are empty then EOverlapNoIntersect only is returned.
1.196 + * @param aThat target region
1.197 + * @return flags from TOverlapFlags enumeration
1.198 + * - EExact =0 if rgions are exactly identical
1.199 + * - ESub Flagged if some rectangles are removed converting current region to that target
1.200 + * - EAdd Flagged if some rectangles are added converting current region to that target
1.201 + * - ENoIntersect if there is no common region between the current region and that target
1.202 + * - EErrorRegion One of the regions is signalling CheckError()
1.203 + **/
1.204 +TRegionExtend::TOverlapFlags TRegionExtend::TestDifference(const TRegion& aThat,TPoint aOffsetToThat)const
1.205 + {
1.206 + TInt intersectArea=0;
1.207 + TInt thisArea=0;
1.208 + TInt thatArea=0;
1.209 + const TRect* thisRects=RectangleList();
1.210 + const TRect* thatRects=aThat.RectangleList();
1.211 + TInt thatCount=aThat.Count();
1.212 + TInt thisCount=Count();
1.213 +
1.214 + if (CheckError()||aThat.CheckError())
1.215 + return EErrorRegion;
1.216 + if (thisCount==0)
1.217 + if (thatCount==0)
1.218 + return ENoIntersect;
1.219 + else
1.220 + return TOverlapFlags(ENoIntersect|EAdd);
1.221 + //both regions are populated. How big is the intersection?
1.222 + //The following optimisation bit is that
1.223 + //if any rect is fully contained by a rect in the opposite region
1.224 + //then further compares against that rect are skipped. For this, inner loop is skipped immediately
1.225 + //Can track the first 32 rects of aThat. The remainder won't benefit from the optimisation
1.226 + TUint optimiseThisBits=0;
1.227 + for (TInt stepThat=thatCount-1;stepThat>=0;stepThat--)
1.228 + {
1.229 + TRect thatRect=thatRects[stepThat];
1.230 + thatRect.Move(-aOffsetToThat.iX,-aOffsetToThat.iY); //this line is the only difference, but the next lump has a lot of parameters...
1.231 + intersectArea+=TestDifferenceRegionInnerLoop(thisCount,thisRects,thatRect,optimiseThisBits);
1.232 + }
1.233 + if (intersectArea==0)
1.234 + if (thatCount==0)
1.235 + return TOverlapFlags(ENoIntersect|ESub);
1.236 + else
1.237 + return TOverlapFlags(ENoIntersect|EAdd|ESub);
1.238 +
1.239 + thatArea=RectListArea(thatRects,thatCount);
1.240 + thisArea=RectListArea(thisRects,thisCount);
1.241 + return AreaDiffResults( thisArea, intersectArea, thatArea );
1.242 + }
1.243 +
1.244 +/** This returns the same comparrison flags between two rectangles.
1.245 + * Note that a zero return means exact intersection...
1.246 + * Intended as an internal method, but there doesn't seem to be a useful public alternative.
1.247 + * @param aThis source rectangle
1.248 + * @param aThat target rectangle
1.249 + * @return flags from TOverlapFlags enumeration
1.250 + * - EExact =0 if rgions are exactly identical
1.251 + * - ESub Flagged if some rectangles are removed converting this source rectangle to that target
1.252 + * - EAdd Flagged if some rectangles are added converting this source rectangle to that target
1.253 + * - ENoIntersect if there is no common region between this source rectangle and that target
1.254 + **/
1.255 +TRegionExtend::TOverlapFlags TRegionExtend::TestDifference(const TRect& aThis,const TRect& aThat)
1.256 + {
1.257 + if (aThis.IsEmpty())
1.258 + if (aThat.IsEmpty())
1.259 + return ENoIntersect;
1.260 + else
1.261 + return TOverlapFlags(EAdd|ENoIntersect);
1.262 + else
1.263 + if (aThat.IsEmpty())
1.264 + return TOverlapFlags(ESub|ENoIntersect);
1.265 + return TestDifferenceNotEmpty(aThis,aThat);
1.266 + }
1.267 +
1.268 +
1.269 +/** Returns total area of the region
1.270 + * @return total area
1.271 + **/
1.272 +TUint TRegionExtend::Area()const
1.273 +{
1.274 +return RectListArea(RectangleList(),Count());
1.275 +}
1.276 +
1.277 +/** Avoids the use of a temp region by performing area calc on the fly.
1.278 + * If both are empty then EOverlapNoIntersect only is returned.
1.279 + * @param aThat target rectangle
1.280 + * @return flags from TOverlapFlags enumeration
1.281 + * - EExact =0 if region exactly fills rectangle
1.282 + * - ESub Flagged if some rectangles are removed converting current region to that target
1.283 + * - EAdd Flagged if some rectangles are added converting current region to that target
1.284 + * - ENoIntersect if there is no common region between the current region and that target
1.285 + * - EErrorRegion One of the region is signalling CheckError()
1.286 + **/
1.287 +TRegionExtend::TOverlapFlags TRegionExtend::TestDifference(const TRect& aThat)const
1.288 + {
1.289 + TInt intersectArea=0;
1.290 + const TRect* thisRects=RectangleList();
1.291 + TInt thisCount=Count();
1.292 +
1.293 + if (aThat.IsEmpty())
1.294 + if (thisCount==0)
1.295 + return ENoIntersect;
1.296 + else
1.297 + return TOverlapFlags(ENoIntersect|ESub);
1.298 + if (CheckError())
1.299 + return EErrorRegion;
1.300 + TInt output=ENoIntersect;
1.301 + for (TInt stepThis=thisCount-1,bit=1;stepThis>=0;stepThis--,bit+=bit)
1.302 + {
1.303 + TOverlapFlags flags=TestDifferenceNotEmpty(thisRects[stepThis],aThat);
1.304 + if (!(flags&ENoIntersect))
1.305 + {
1.306 + if (!(flags&EAdd)) //the target rect does not add anything to this region element
1.307 + { //Skip rest of inner loop if a containing rect is found
1.308 + if ((flags&ESub)||thisCount>1)
1.309 + return ESub; //the region element is bigger or there are more region elements
1.310 + else
1.311 + return EExact;
1.312 + }
1.313 + else
1.314 + {
1.315 + TRect intersect=thisRects[stepThis];
1.316 + intersect.Intersection(aThat);
1.317 + TSize size=intersect.Size();
1.318 + __ASSERT_DEBUG((size.iWidth|size.iHeight)<32768,User::Panic(_L("TRegionExtend"),1003));
1.319 + intersectArea+=size.iWidth*size.iHeight;
1.320 +
1.321 + }
1.322 + output&=~ENoIntersect;
1.323 + }
1.324 + output|=(flags&ESub);
1.325 + }
1.326 + if (intersectArea==0)
1.327 + {
1.328 + return TOverlapFlags(output|EAdd);
1.329 + }
1.330 + TSize size=aThat.Size();
1.331 + __ASSERT_DEBUG((size.iWidth|size.iHeight)<32768,User::Panic(_L("TRegionExtend"),2003));
1.332 + TInt thatArea=size.iWidth*size.iHeight;
1.333 + if (thatArea>intersectArea)
1.334 + return TOverlapFlags(output|EAdd);
1.335 + else
1.336 + return TOverlapFlags(output);
1.337 + }
1.338 +
1.339 +