InnovationQ/InnovationQ Plus content will be updated on Sunday, June 25, 10am ET, with new patent and non-patent literature collections. Click here to learn more.
Browse Prior Art Database

Fast drawing of complex polygons/polygonal areas

IP.com Disclosure Number: IPCOM000010838D
Original Publication Date: 2003-Jan-24
Included in the Prior Art Database: 2003-Jan-24
Document File: 4 page(s) / 75K

Publishing Venue



Clipping is standard technology. The present invention supports the clipping algorithms in graphics hardware by presenting to them simplified polygons, and simplifications are done very efficiently (only comparisons, no calculations) and only when needed. Therefore the resulting user experience (drawing speed) is maximized.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 50% of the total text.

Page 1 of 4

Fast drawing of complex polygons/polygonal areas

1. Introduction

Any application drawing eg. cartographic data has to draw many, typically complex, polygons. Efficient and therefore quick drawing of polygons and polygonal areas is the key aspect of todays Geo Information Systems. Even simple map drawing applications depend for interactive usability on very short display update times. The user of such an application will zoom in and zoom out, change focus, and most importantly, wants any operation to be done immediately. This is still a problem even if the graphic hardware support is immense today.

    The basic operation for drawing polygons is that of "clipping" ([2],[3]), that is to determine the area of the polygon being visible. Clipping of a polygon is the operation of determining the polygon's intersection with the visible area. This operation is expensive because of the involved rational arithmetic. Even modern graphic cards quickly come to the point of slow drawing if many complex polygons are involved.

2. Problem statement

    The challenge for most applications is either to find a balance between polygon resolution and display speed or to make use of many different resolutions for the same set of polygons.

3. Solution

    The present invention solves the problems described by making use of a single high resolution base of polygons and a polgon reduction technique for the actual drawing comprising two operations:

    OP1) point collapsing: if two successive points of a polygon will be mapped to the same pixel of the display device, then it is allowed to remove one without any change on the display.

    OP2) point reduction: if three succesive points of the polygon will be mapped all either
above the top
right to the right border
below the bottom
left to the left border of the actual view, then the middle point may be removed from the polygon without changing the drawing of the polygon (and...