msClipPolygonRect() / msClipPolylineRect()

[Ed McNierney]

Frank -

I looked over this code and it is, as you say, extremely
straightforward.  Good job - but I agree with the inclination to move
forward rather than backporting.

To Sean's comment about GD clipping, trivial rejection is extremely
important.  We should always discard objects that cannot possibly need
to be drawn by discarding them EARLY in the pipeline, rather than
passing them all the way down to GD only to have it decide to do
nothing.  It might be worth considering whether objects that do indeed
need to be clipped should be passed along "as is" to GD for that task,
but that's a separate item from what Frank's done here.  It may be
*possible* that MapServer's attempts to clip objects to the output
bounding box might create a pessimal case in which GD is still doing a
lot of "clipping" to constrain output to the same rectangle (i.e. there
may be some redundant clipping for edge conditions we're creating
ourselves).

        - Ed

Ed McNierney
President and Chief Mapmaker
TopoZone.com / Maps a la carte, Inc.
73 Princeton Street, Suite 305
North Chelmsford, MA  01863
ed at topozone.com
(978) 251-4242  

-----Original Message-----
From: UMN MapServer Developers List [mailto:MAPSERVER-DEV at LISTS.UMN.EDU]
On Behalf Of Frank Warmerdam
Sent: Thursday, March 24, 2005 12:48 PM
To: MAPSERVER-DEV at LISTS.UMN.EDU
Subject: [UMN_MAPSERVER-DEV] msClipPolygonRect() / msClipPolylineRect()

Folks,

As part of an optimization project, funded by the Department of
Fisheries and Oceans I am digging through a few things.  I found that in
my test rendering something 15% of my time was spent in
msClipPolygonRect() as part of normal rendering.

A quick review highlighted that many of the features being put through
clipping were completely within the clip rectangle, so alot of work was
being done to accomplish no change.  I have modified
msClipPolygonRect() and msClipPolylineRect() in 4.5 CVS to return
immediately if they determine that the bounds of the shape are
completely within the clip rectangle.

In my case this cut the clipping time by about 50%.

My only concern with this change is whether there is any risk of
shapeObj bounds not being correct.  Does anyone know of circumstances
when the bound might not be in sync with the actual contents of the
shape?

I have applied the same change to msClipPolygonRect() though I don't use
it much in my test case.

I suspect that there may be futher opportunities for optimization on
this function. For instance, it doesn't seem like there is any point in
computing intersects for line segments where both end points are within
the search rect.

Best regards,
--
---------------------------------------+--------------------------------
---------------------------------------+------
I set the clouds in motion - turn up   | Frank Warmerdam,
warmerdam at pobox.com
light and sound - activate the windows | http://pobox.com/~warmerdam
and watch the world go round - Rush    | Geospatial Programmer for Rent