FrameRgn slow on XP/2K fast on ME

[Morten]

Is there any news from Microsoft as to the speed of FrameRgn on these
platforms?

I have come across John Hornick (MS) and Jeff Partch discussion from
Feb-March, and I am extreemely interested. Do anyone know of an SP or
a workaround that will speed up the FrameRgn on XP/2K? I assume if th

Hoping for a positive reply.

Thanks in advance
Morten


Background:
I am using VC++6.0, and have met the same problem as Jeff Partch. Ie.
That FrameRgn, is exeedingly slow on my Win2000/XP computers.

I make connectivity maps in bitmapped images using combine
rgnNew.CombineRgn(this, &rgn,RGN_OR);
and end up with seriously big and complex Regions

The user move the cursor over a region, and it gets highlighted.
The call "PtInRegion(point)" is quite fast, but getting the region
framed, is a slow grinding process.


The OnUpdateCode is this (The class CArea is derived from CRgn with a
few helper functions such as index to speed up things rather than
using the EqualRgn function).

if(m_LastDrawnArea.GetIndex()!=GetDocument()->m_AreaOfInterest.GetIndex()
)
{
CBrush brush(RGB(255,255,255));
int iOldRop2=dc.SetROP2(R2_NOT);
//Deletete previous
dc.FrameRgn( &m_LastDrawnArea,&brush,2,2);
m_LastDrawnArea=GetDocument()->m_AreaOfInterest;
dc.FrameRgn( &m_LastDrawnArea,&brush,2,2);
dc.SetROP2(iOldRop2);
brush.DeleteObject();
}



Particularly when you like I have generally 3 or more views (all
bitmap illustrations of different properties of the sample) open at
the same time and want to FrameRgn in all.

[Feng Yuan [MSFT]]

Can you give an example on how complicated your region is?

There is no region at the DDI level, to GDI has to convert region into a
path. You should consider converting the region to a path yourself.

I guess you region changes incrementally. If this is the case, you just need
to update the changed portion of the region boundary.

[Morten]

Dear Feng Yuan
My regions are quite complicated. A rect count of 2000+ is not
unusual. Regularly I have regions even bigger (up to about 40K).
I dont know what you mean by changing it into a path. If you mean like
a scribble list then this is unlikely to be possible since regions are
created by first making 1D lists "xstips" and "ystrips" (CList
<CRect,&CRect>) and then combining these to a list of 2D islands
(CAreas), that then can be analysed...
The areas will be of any shape with any shaped holes with any number
sort of areas inside.
But: If you know of code that deduces the path for any randomly
complicated CRgn I would be very gratefull.

I am still quite surpriced about the lack of speed, of the framing,
and I am now putting in a (user defined) limit so that the only CRgn
with a rectcount smaller than say 2000 will be highlighted on screen.

I more recently have found problems in the RectInRegion(rect) aswell.
It occasionally gives me false positives which means that two non
connected regions gets falsely connected into one. I can send you the
RGNDATA if you think that you can help me on that one..... I am very
much considering rewriting the code for RectInRegion(rect) myself
although I fear that it will be slower than the MS.

I get the feeling that I may be using MS CRgns for more than they are
designed, or at least that the implementation, is not quite up the
level I need for my application.


Thanks for any enlightment

Morten

CMyArea::CreateOneOfManyAreas(lists.....)
{
CreateRectRgnIndirect(XList.RemoveTail());
while(AddList(YList))
{
if(!AddList(XList))
break;
}
}

BOOL CArea::AddList(CStripList& list)
{

if(list.IsEmpty())
return FALSE;

POSITION pos=list.GetTailPosition();
POSITION nextpos=pos;
BOOL bReturn=FALSE;
if(!pos)
return FALSE;
CRect rect;

CRgn rgn;
do
{
pos=nextpos;
rect=list.GetPrev(nextpos);
if(RectInRegion(rect))
{
rgn.CreateRectRgnIndirect(rect);
CombineRgn(this, &rgn,RGN_OR);
rgn.DeleteObject();
list.RemoveAt(pos);
bReturn=TRUE;
}
}while(nextpos);
return bReturn;
}


CMyArea::GetRectCount()
{
DWORD nSize=GetRegionData( NULL, 0);

LPBYTE pData = new BYTE[nSize];

RGNDATA *pRgnData = (RGNDATA*)pData;
GetRegionData( pRgnData, nSize);

m_iRectCount=pRgnData->rdh.nCount;

delete[] pData;

return m_iRectCount;
}

Post by Feng Yuan [MSFT]
Can you give an example on how complicated your region is?
There is no region at the DDI level, to GDI has to convert region into a
path. You should consider converting the region to a path yourself.
I guess you region changes incrementally. If this is the case, you just need
to update the changed portion of the region boundary.

[Feng Yuan [MSFT]]

GDI region is implemented as a dynamic array of SCAN, which is an 'array' of
intervals. The key data structure for region is allocated in kernel mode
address space, there there is a limitation on the size it can grow. Your
code shows adding rect to region gradually, based on the 'dynamic array'
implementation, the speed is O(N^2). To read more about this, check Section
3.8 of my book.

At the DDI level, there is no entry point corresponding to FrameRgn call, so
GDI may have to generate an outline of the region and may be call
DrvStrokePath. But constructing a huge path can be expensive too.

Region is mainly designed for clipping implementation. So region with 2000+
random rectangles can really be a performance problem.

You should definitely consider design your own data structure for your
problem, for example using a tree structure to represent your region. You
should be able to improve performance a lot.

Win32 API does have its limitation when you really push the limit. For
example:

1) Try to create a 40 MB DDB.
2) Try to print something 30 meter long at 4800 dpi.
3) Try to insert 1 million items into a tree view and then delete the tree
view.
4) Try to allocate 1.5 GB of memory.

Feng Yuan (www.fengyuan.com)