AU767523B2 - Method and apparatus for constrained osculatory packing - Google Patents

Description

S&FRef: 562580

AUSTRALIA

PATENTS ACT 1990 COMPLETE SPECIFICATION FOR A STANDARD PATENT

ORIGINAL

Name and Address of Applicant: Canon Kabushiki Kaisha 30-2, Shimomaruko 3-chome, Ohta-ku Tokyo 146 Japan Actual Inventor(s): Address for Service: Cameron Bolitho Browne Spruson Ferguson St Martins Tower,Level 31 Market Street Sydney NSW 2000 (CCN 3710000177) Method and Apparatus for Constrained Osculatory Packing Invention Title: ASSOCIATED PROVISIONAL APPLICATION DETAILS [33] Country [31] Applic. No(s) AU PQ9676 [32] Application Date 25 Aug 2000 The following statement is a full description of this invention, including the best method of performing it known to me/us:- 5815c -1- METHOD AND APPARATUS FOR CONSTRAINED OSCULATORY PACKING Technical Field of the Invention The present invention relates generally to the field of computational geometry and, in particular, to performing osculatory packing of shapes within a defining boundary region. The present invention relates to a method and apparatus to performing osculatory packing of shapes within a defining boundary region. The invention also relates to a computer program product including a computer readable medium having recorded thereon a computer program to creating osculatory packing of shapes within a defining boundary region.

Background Art In the field of computer graphics it is often desirable to decorate or enhance given shapes to make them more visually interesting, eg for the purposes of advertising or web page design. This is generally done by adding texture to the region defined by a shape, such as filling the region with multiple instances of smaller objects, resulting in a more complex composite image. Circle packing can provide such a texture.

Traditional circle packing methods obey the following general conditions: the packing is reasonably dense and evenly distributed across the region; circles are positioned so as to give the impression of random placement and avoid noticeable locally repeating patterns; 20 circles do not intersect neighbouring circles; circles are tangential to and touching their nearest neighbours; and the packing is osculatory (ie. any available area is always covered by the largest possible circle).

The simplest prior art method of circle packing is the random placement of circles within the region. This is inefficient and does not satisfy conditions or above.

Apollonian packing is also known. This is achieved by placing at random unfilled points within the region, the largest circle that touches at least three other circles.

It satisfies all of the above conditions but does not allow control over properties of the individual circles, whose diameters are defined deterministically.

The related 1-tangent circle packing method (Pickover C, 1990, "Computers, Pattern, Chaos and Beauty", St Martin's Press, New York, p 332-6) is a prior art method which relaxes the condition that the filling circle touch at least three neighbours, and requires only that the filling circle touch at least 1 neighbour. This method is more 562580.doc efficient than Apollonian packing, satisfies all of the above conditions except and does not necessarily result in a deterministic packing. However, again 1-tangent packing does not provide control over properties of individual circles and results in random coverage of the area to be filled.

One known method of packing circles within bounded regions of arbitrary shape, varies packing density and properties of component circles according to the position of the circles with respect to reference objects or goals. However, this method can produce inaccurate results when the size of the shapes to be packed is constrained to a certain range.

The above mentioned methods are limited in that although some address the problem of even-distribution packings within a space, the methods are relatively inefficient, are not readily constrained, and do not provide for further manipulations of density or properties of components that the user may wish to apply. Given the computational nature of a packing method, it is advantageous if manipulations occur with a minimum of interaction from the user, but that the user also has reasonably precise control over the final result.

Summary of the Invention It is an object of the present invention to substantially overcome, or at least ameliorate, one or more disadvantages of existing arrangements.

According to one aspect of the present invention there is provided a method of packing circles within a bounded image, said method comprising the steps of: defining a boundary for said image; specifying parameters for said circles; placing at least one circle at each of a plurality of predetermined points, 25 tangentially to said boundary whilst maintaining a spatial relationship of at least one of said parameters; and placing at least one circle tangentially to at least two of said circles previously placed on said boundary.

S"According to another aspect of the present invention there is provided a method of packing circles within a bounded image, said method comprising the steps of: defining a boundary for said image; specifying parameters for said circles; nestling at least one of said circles into a corner defined by said boundary, depending on at least one of said parameters; 562580.doc placing at least one circle at each of a plurality of predetermined points, tangentially to said boundary whilst maintaining a spatial relationship of at least one of said parameters; and placing at least one circle tangentially to at least two of said circles previously placed on said boundary.

According to still another aspect of the present invention there is provided an apparatus for packing circles within a bounded image, said apparatus comprising: defining means for defining a boundary for said image; specifying means for specifying parameters for said circles; placing means for placing at least one circle at each of a plurality of predetermined points, tangentially to said boundary whilst maintaining a spatial relationship of at least one of said parameters, and for placing at least one circle tangentially to at least two of said circles previously placed on said boundary.

According to still another aspect of the present invention there is provided an apparatus for packing circles within a bounded image, said apparatus comprising: defining means for defining a boundary for said image; specifying means for specifying parameters for said circles; nestling means for nestling at least one of said circles into a corner defined by said boundary, depending on at least one of said parameters; 20 placing means for placing at least one circle at each of a plurality of predetermined points, tangentially to said boundary whilst maintaining a spatial relationship of at least one of said parameters, and for placing at least one circle tangentially to at least two of said circles previously placed on said boundary.

According to still another aspect of the present invention there is provided an S 25 apparatus for packing circles within a bounded image, said apparatus comprising: oo** a memory for storing a program; and a processor for executing the program, said program comprising code for performing the followings steps: defining a boundary for said image; specifying parameters for said circles; placing at least one circle at each of a plurality of predetermined points, tangentially to said boundary whilst maintaining a spatial relationship of at least one of said parameters; and placing at least one circle tangentially to at least two of said circles previously placed on said boundary.

562580.doc According to still another aspect of the present invention there is provided an apparatus for packing circles within a bounded image, said apparatus comprising: a memory for storing a program; and a processor for executing the program, said program comprising code for performing the followings steps: defining a boundary for said image; specifying parameters for said circles; nestling at least one of said circles into a corner defined by said boundary, depending on at least one of said parameters; placing at least one circle at each of a plurality of predetermined points, tangentially to said boundary whilst maintaining a spatial relationship of at least one of said parameters; and placing at least one circle tangentially to at least two of said circles previously placed on said boundary.

According to still another aspect of the present invention there is provided a program for packing circles within a bounded image, said program comprising: code for defining a boundary for said image; code for specifying parameters for said circles; code for placing at least one circle at each of a plurality of predetermined points, 20 tangentially to said boundary whilst maintaining a spatial relationship of at least one of said parameters; and code for placing at least one circle tangentially to at least two of said circles ooooo previously placed on said boundary.

According to still another aspect of the present invention there is provided a 25 program for packing circles within a bounded image, said program comprising: code for defining a boundary for said image; code for specifying parameters for said circles; S :code for nestling at least one of said circles into a corner defined by said #oooi boundary, depending on at least one of said parameters; code for placing at least one circle at each of a plurality of predetermined points, tangentially to said boundary whilst maintaining a spatial relationship of at least one of said parameters; and code for placing at least one circle tangentially to at least two of said circles previously placed on said boundary.

562580.doc Brief Description of the Drawings One or more embodiments of the present invention will now be described with reference to the drawings, in which: Fig l(a) shows a boundary outline and an interior region, describing the character Fig. l(b) shows a minimal circle with minimum radius m and a maximal circle with maximum radius M; Fig. 2 shows a circle C fitted to an acute interior corner represented by an internal angle a such that the circle is tangential to the outline edge and fitted as close to the corner a as possible; Fig. 3 shows a more complex example in which a corner is defined by line segments AB and AD that are too short to accommodate a minimum radius circle; Fig. 4 shows an obtuse interior angle o which represents the corner of an outline; Fig 5 shows the boundary outline and boundary outline describing the character after circles have been packed to all acute and obtuse corners of the boundary outlines; Fig. 6 shows a section of an outline bounded by the two corners at which circles •have been packed; Fig. 7 shows the expansion of seed point S into a circle C with two tangential neighbours C 1 and Cr; Fig. 8 shows the preferred manner of placement of a neighbouring circle Ce such that the circle is tangential to both an existing circle C and an outline edge AB; Fig. 9(a) shows an expected circle C. which is tangential to an existing circle C; Fig. 9(b) shows an actual circle that has been effectively rolled away from 25 another circle until the circle is both tangential to the other circle and an outline edge *.segment; Fig. 10(a) shows an expected circle that is tangential to both an existing circle C and an outline edge segment AB, and intersects another existing circle Ci; S"Fig. 10(b) shows an actual circle Ca fitted so that the actual circle is tangential to another circle, an edge segment AB and a further circle; Fig. 1 l(a) shows an expected circle that is tangential to both an existing circle and an outline edge segment AB; Fig. l(b) shows an actual circle Ca fitted so that the circle is tangential to another circle, line segment AB and line segment DE; 562580.doc

I

Fig. 12 shows a seed point that has been expanded to create a new circle that is within a predetermined threshold distance d from a neighbouring circle; Fig. 13 shows three circles after seed expansion has occurred, and the corresponding normal vectors and r; Fig. 14 shows inverse normal vectors 1' and r' that project in the direction opposite to the directed pair normal vectors and r, for the circles of Fig. 13; Fig. 15 shows the boundary outline and boundary outline describing the character after the packing of acute corners, obtuse corners and outline stretch packing have been completed; Fig. 16(a) shows a directed pair formed by circles C, and Cr; Fig. 16(b) shows an actual circle Ca fitted tangentially to the circles C and Cr of Fig. 16(b); Fig. 17 shows the fitting of circles to inverted normals and r'; Fig. 18(a) shows an expected circle fitted tangentially to a directed pair formed by circles C, and C, where circle Ce intersects an existing circle Ci; Fig. 18(b) showg an actual fitted circle Ca fitted to be tangential to the circles CI, C, and Ci, of Fig. 18(a); Fig. 19(a) shows an expected circle C. fitted tangentially to a directed pair formed by circles CI and Cr, where circle Ce intersects an existing outline edge AB; 20 Fig. 19(b) shows the actual fitted circle Ca fitted to be tangential to the circles C 1 C, 1903 and the outline edge AB of Fig. 19(b); Fig. 20 shows a predetermined spacing value that can be used to fit two circles C 1 and Cr such that a minimum spacing of '2S' is guaranteed between circles C 1 and Cr; 25 Fig. 21 shows a spacing value OS that can be used in fitting overlapping circles

C

1 and Cr; Fig. 22 is a flowchart showing a method of packing circles within a bounded region; S°Fig. 23 is a flowchart showing a method of outline packing; Fig. 24 shows an example where it is desired to fit a circle tangential to an existing circle C within the range delineated by existing circles C 1 to the left of circle and Cr to the right of circle; Fig 25 shows the circles of Fig. 24 packed in a preferred manner; and Fig. 26 is a schematic block diagram of a general purpose computer upon which arrangements of the present invention can be practiced.

562580.doc Detailed Description including Best Mode Where reference is made in any one or more of the accompanying drawings to steps and/or features, which have the same reference numerals, those steps and/or features have for the purposes of this description the same function(s) or operation(s), unless the contrary intention appears.

Some portions of the description which follows are explicitly or implicitly presented in terms of algorithms and symbolic representations of operations on data within a computer memory. These algorithmic descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. An algorithm is here, and generally, conceived to be a self-consistent sequence of steps leading to a desired result. The steps are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated. It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like.

It should be borne in mind, however, that the above and similar terms are to be eeoc associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise, and as apparent from the 20 following, it will be appreciated that throughout the present specification, discussions *e utilizing terms such as "scanning", "calculating", "determining", "replacing", "generating" "initializing", "outputting", or the like, refer to the action and processes of a computer system, or similar electronic device, that manipulates and transforms data represented as physical (electronic) quantities within the registers and memories of the computer system into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.

S.

The present specification also discloses apparatus for performing the operations of the methods. Such apparatus may be specially constructed for the required purposes, or may comprise a general purpose computer or other device selectively activated or reconfigured by a computer program stored in the computer. The algorithms and displays presented herein are not inherently related to any particular computer or other apparatus.

Various general purpose machines may be used with programs in accordance with the teachings herein. Alternatively, the construction of more specialized apparatus to perform 562580.doc the required method steps may be appropriate. The structure of a conventional general purpose computer will appear from the description below.

In addition, the present specification also discloses a computer readable medium comprising a computer program for performing the operations of the methods. The computer readable medium is taken herein to include any transmission medium for communicating the computer program between a source and a designation. The transmission medium may include storage devices such as magnetic or optical disks, memory chips, or other storage devices suitable for interfacing with a general purpose computer. The transmission medium may also include a hard-wired medium such as exemplified in the Internet system, or wireless medium such as exemplified in the GSM mobile telephone system. The computer program is not intended to be limited to any particular programming language and implementation thereof. It will be appreciated that a variety of programming languages and coding thereof may be used to implement the teachings of the invention as described herein.

A method of packing circles within bounded regions of arbitrary shape is to be disclosed in which circle size is constrained to a range and settings such as spacing and packing density are subject to automatic variation according to the position of the circles 9**o :with respect to reference objects or goals. The method of packing circles provides very good reproducibility.

For ease of explanation, the steps of the method are described with reference to circle packing for 2-dimensional regions that describe character shapes. However, it is not intended that the present invention be limited to the described method. For example, ***other arrangements have application to packing any planar geometric shape that can be tested for intersection with the region boundary and existing planar shapes, for arbitrarily shaped 2-dimensional regions defined by a set of closed curves. The outline region boundary can be polygonised to convert it to a series of line segments.

Fig. 22 is a flowchart showing the method of packing circles within a bounded 8* region. The process begins at the first step 2201, where a user inputs a minimum circle 909S*S S" radius m, a maximum circle radius M, and a spacing value S. The spacing value S can be applied to parametrically control spacing between packed circles which will be explained in more detail later in this description. The user also inputs the region boundary at step 2201. The region boundary can be user drawn or alternatively, the region boundary can be read from a computer file such as a font file or a postscript file. At the next step 2203, a directed circle pair list is created for storing directed circle pairs. The directed circle pair list is used to store details of directed circle pairs created during the process of 562580.doc packing a region. A directed circle pair is created when two circles are packed tangentially to each other. An example of a directed circle pair is shown in Fig. 13, where circle C 1301 forms a directed pair with the right tangential neighbour Cr 1304. The process continues at the next step 2205, where the region boundary outline is packed.

The outline packing process will be described in detail below with reference to Fig. 23. At the next step 2207, a check is performed to determine if the directed circle pair list is empty. If the check returns true then the process concludes. Otherwise the process continues to step 2209 where a next circle pair is selected from the directed circle pair list.

At the next step 2211, a check is performed to determine if a circle can be placed tangentially to the left of the pair selected step 2209. If the check returns false then the process continues to step 2217. Otherwise, the process proceeds to step 2213, where a circle is placed tangentially to the left of the pair selected at step 2209. As will be explained later in this document, the circle is placed with respect to a primary normal vector, which results from the directed pair. As a result of the placement of the circle two new directed pairs are formed. At the next step 2215, the two new directed pairs are added to the directed pair list and the process proceeds to step 2217.

At step 2217, a check is performed to determine if a circle can be placed tangentially to the right of the pair selected at step 2209. If the check returns false then the process continues to step 2219. Otherwise, the process proceeds to step 2221, where a 20 circle is placed tangentially to the right of the pair selected at step 2209. Again, as will be explained later in this document, the circle is placed with respect to a primary normal vector, which results from the directed pair. As a result of the placement of the circle, two new directed pairs are formed. At the next step 2223, the two new directed pairs are added to the directed pair list and the process proceeds to step 2219. At step 2219, the pair selected at step 2209 is removed from the directed pair list and the process returns to step 2207.

Fig. 23 is a flowchart showing the method of outline packing. The outline packing method will be explained with reference to an example as illustrated in Figs. 1 to 15. Fig l(a) shows boundary outline 101, boundary outline 103 and an interior region 30 102, describing the character The region 102 is to be filled with circles constrained in size from minimal circle 103 with minimum radius m 104 to maximal circle 105 with maximum radius M 106, as seen in Fig. In accordance with one arrangement, the maximum radius M and the minimum radius m can be the same. The process of Fig. 23 begins at step 2301, where the acute corners of the region boundary outline are packed.

For example, Fig. 2 shows a circle C 202 fitted to an acute interior corner represented by 562580.doc the internal angle a 201 such that the circle 202 is tangential to the outline edge and fitted as close to the comer a 201 as possible. The circle C 202 is tangential to the two outline edge segments defined by point AB 203 and AD 204 that meet at corner a and straddle comer a. Preferably, only minimum radius circles are fitted to acute corners to give optimal definition of the outline shape.

Fig. 3 shows a more complex example in which a corner 301 is defined by line segments AB 305 and AD 306 that are too short to accommodate the minimum radius circle. The expected circle Ce 302 packed to the line segments 305, 306 intersects the boundary outline at points 307 and 309. Therefore, in order to pack the circle 302 to the corner 301, the circle 302 is effectively rolled away from the corner 301 until an actual circle of minimum radius Ca 304 can be placed tangential to the outline edge and straddling the corner 301.

At the next step 2303, the obtuse corners of the region outline are packed. For example, Fig. 4 shows an obtuse interior angle o 401 which represents the corner 107 of outline 103. The obtuse interior angle o 401 and interior bisector b 402, are packed with two circles C 1 403 and C 2 404. The two circles 403, 404 are packed so that the circles 403 and 404 are tangential to line AB 405 and bisector b 402 and line AD 406 and bisector b 402, respectively, and are hence tangential to each other. If necessary, a circle can be rolled away from an obtuse comer until non-intersecting placement is possible.

20 Circles 403 and 404 of Fig. 4, can be set to the minimum radius m to ensure optimal definition of a character shape by fitting corners of the character shape as closely **as possible. However, preferably the circles packed to an obtuse comer (eg. 403, 404) are made unequal to avoid visible packing artefacts in the final image. This can require some modification so that circles 403 and 404 are tangential to each other rather than being 25 independently tangential to the bisector 402.

Fig 5 shows the boundary outline 101 and boundary outline 103 describing the character after circles have been packed to all acute (eg. 500) and obtuse (eg. 501) corners of the boundary outlines 101,103.

The process of Fig. 23 continues at the next step 2305, where obtuse pairs are 30 added to the directed pair list created at step 2203. At the next step 2307, seed points are created for the region outline boundary. For example, Fig. 6 shows a section of outline 103 bounded by the two corners 107 and 109 at which circles have been packed. The section of outline 103 is referred to as a stretch and the process of packing an outline section like section outline 103 is referred to as stretch packing. A series of seed points (eg. 601, 604) have been marked along the section of outline 103, such that the seed 562580.doc -11points are substantially evenly distributed but include a nominal amount of random displacement to avoid uniformity. Preferably, each seed point is placed less than the minimum radius m from neighbouring seed points. If an outline contains no corners, then any point along the outline may be selected at random as the starting point for placing seed points.

The process of placing the circles at the seed points is referred as expanding the seed points. This process will be explained in more detail in the following paragraphs.

At the next step 2309, a check is performed to determine if there are any remaining seed points to be expanded. If there are no remaining seed points to be expanded the process proceeds to step 2207 of Fig. 22. Otherwise the process proceeds to step 2311, where a next seed point is selected for expansion. At the next step 2313, a check is performed to determine if the selected seed point can be expanded. This decision is made based on whether a circle of minimum radius can be placed at the seed point without intersecting any existing circles or boundary outlines. If the selected seed point cannot be expanded then the process proceeds to step 2315, where the selected seed point is deleted and the process returns to step 2309. If the selected seed point can be expanded at step 2313, then the process proceeds to step 2315, where a circle is placed at the selected seed point. For example, Fig. 7 shows the expansion of seed point S 601 into a circle C 703 with two tangential neighbours C 1 704 and Cr 705. As seen in Fig. 7, a circle C 703 is placed at point S 601 such that centre of the circle C lies along the inward-facing normal n 702 from the outline curve 103 at point S 601. Circles CI 704 and Cr 705 are placed **tangential to both circle 703 and the outline edge 103. Some seed points such as S1 706 and S, 707 can be eclipsed from the placement of C, C 1 and Cr, and these seed points can be removed from the process.

Fig. 8 shows the preferred manner of placement of a neighbouring circle Ce 801 such the circle 801 is tangential to both an existing circle C 802 and an outline edge AB 803. However, some problems can arise that require special handling during the placement of neighbouring circles. For example, Fig. 9(a) shows an expected circle Ce 901 which is tangential to an existing circle C 902. However, the outline edge segment AB 903 is not itself tangential to the circle 901 due to the shortness of edge AB. In order to pack the corner 905, it is not sufficient to simply extrapolate line AB. As seen in Fig.

the actual circle 904 is effectively rolled away from circle 902 until it is both tangential to the circle 902 and the outline edge segment BD 905.

Fig. 10(a) shows an expected circle 1001 that is tangential to both existing circle C 1002 and an outline edge segment AB 1003, and intersects another existing circle Ci 562580.doc -12- 1004. In this instance, the actual circle Ca 1005 is fitted so that the circle 1005 is tangential to circle 1002, the edge segment AB 1003 and circle 1004, using any known geometric method, as seen in Fig. 10(b). If the radius of circle 1005 is smaller than m, then the circle 1005 is deleted to ensure that size constraints are met, and optionally existing circles 1002 and 1004 can be repacked for better fit.

Fig. 11l(a) shows an expected circle 1101 that is tangential to both an existing circle 1102 and an outline edge segment AB 1103. As seen in Fig. 11l(a), circle 1101 intersects another outline edge segment DE 1104. In this instance, the actual circle Ca 1105 is fitted so that the circle 1105 is tangential to circle 1107, line segment AB 1103 and line segment DE 1104, as seen in Fig. 1 using well-known geometric methods.

If the radius of circle 1105 is smaller than m then the circle 1105 is deleted to ensure that size constraints are met, and optionally existing circle 1107 can be repacked for a better fit.

Returning to the process of Fig. 23, after step 2315, the process proceeds to step 2317, where a check is performed to determine if the circle has a left neighbour that is within a predetermined distance threshold d of the circle. For example, Fig. 12 shows a seed point 1203 that has been expanded to create new circle 1201. To complete the boundary packing process a circle needs to be fitted to the right of circle 1201. However, *.eo existing circle Cn 1202 is within a predetermined threshold distance d 1204. Therefore, a circle (or two circles) can be packed so that the circle is tangential to circle 1201, circle 1202 and outline edge AB 1205. Preferably, the predetermined threshold distance is m+M. This provides that the packing around an outline edge segment is seamlessly tangential, without being overly uniform. A similar terminating condition occurs when placing a tangential neighbour to the left of circle 1201.

If the circle has a left neighbour that is within a predetermined distance threshold d of the circle, at step 2317, then the process proceeds to step 2319 where a circle is packed to left of the circle placed at step 2315.

Fig. 13 shows three circles 1301, 1302 and 1304 after seed expansion has occurred. Circle C 1301 forms a directed circle pair with the left tangential neighbour C 1 30 1302 of the circle 1301. Further, circle C 1301 forms a directed pair with the right tangential neighbour Cr 1304. For each neighbour of the circle 1301 it is possible to define a vector (eg. 1303 and 1305) from a first member (ie. circle 1302) of the pair to the second member (ie.1301), and from the vector 1303 a normal vector can be defined. For example, normal vectors 1306 and r 1307 both project to the left side of the directed 562580.doc -13pairs formed by circle 1301, 1302 and 1301, 1304, respectively. Vectors 1306 and 1307 are referred to as the primary normals.

Fig. 14 shows the inverse normal vectors 1' 1401 and r' 1402 that project in the direction opposite to the directed pair normal vectors 1 1302 and r 1304. Vectors 1' 1401 and r' 1402 are referred to as the inverted normals. Pairs of circles packed to obtuse corners as described above also form directed pairs having associated primary and inverted normals.

After step 2319, the process proceeds to step 2321, where the new directed pairs created as a result of the placement and packing of circles at steps 2315 and 2319, respectively, are added to the directed pair list created at step 2203 of Fig. 22.

If the circle does not have a left neighbour that is within the predetermined distance threshold d of the circle, at step 2317, then the process proceeds to step 2323, where a check is performed to determine if a circle can be placed to the left of the circle placed at step 2315. If the check at step 2323 returns true, then the process proceeds to step 2325, where one or more circles are nestled to the left of the circle placed at step 2315. At the next step 2327, any new directed pairs created as a result of the placement and nestling of circles at steps 2315 and 2325, respectively, are added to the directed pair list created at step 2203 of Fig. 22. If the check at step 2323 returns false (eg. where an outline or existing circles intrude into the area to the left thereby not allowing any circles to be placed to the left), then the process proceeds to step 2329.

After step 2321 or step 2327, step 2329 is performed where a check is made to determine if the circle placed at step 2315 has a right neighbour that is within a predetermined distance threshold d of the circle. The process then proceeds to steps 2331, 2333, 2335, 2337 or 2339 for the right of the circle placed at step 2315, in a similar manner to the steps 2319, 2321, 2323, 2325 and 2327 discussed above and, steps 2331, 2333, 2335, 2337 or 2339 will not be explained any further. After steps 2333, 2335 or 2339, the process returns to step 2315.

Fig. 15 shows the boundary outline 101 and boundary outline 103 describing the character after the packing of acute corners, obtuse corners and outline stretch packing 30 have been completed. Primary normal vectors (eg. 1501) are shown for each directed pair of circles (eg. 1502).

The process of packing a circle to fit tangentially to an existing pair will now be explained with reference to the following examples as shown in Figs. 16(a) to 21.

Fig. 16(a) shows a directed pair formed by circles C 1 1601 and Cr 1602. Fig. 16(a) also shows an expected circle 1604 placed to the same side of the pair as primary normal n 562580.doc 14- 1603. Due to the geometrical properties of circle fitting, placing the centroid of the circle 1604 exactly along the normal n is not desirable unless circles 1601 and 1602 have identical radii, however the direction of n can indicate the vicinity in which a circle can be placed. In the instance that circles 1601 and 1602 do not have identical radii, a suitable radius r is selected for Ce within the range m M and actual circle Ca 1605 is fitted tangential to circle C 1 1601 and Cr 1602 using well-known geometric methods, as shown in Fig. 16(b).

The placement of actual circle Ca 1605 forms two new directed tangential pairs, namely CICa indicated by vector 1606 and CaCr indicated by vector 1607 from which primary normal vectors l 1608 and r 1609 can be derived. The placement process can then be applied recursively to these new pairs. This is the simplest case of fitting to a pair, where no interference with existing geometric elements occurs. New inverted normals can also be generated if so desired, but it is generally sufficient to proceed with primary normals only.

Fig. 17 shows that a similar fitting of circles can be made to the inverted normals 1' 1701 and r' 1702. However, the normals 1701 and 1702 point in the direction of an enclosed space and a circle can be fitted to one of 1' and r' if necessary. Preferably, inverted placements are only performed if there is a significant difference between minimum radius m and maximum radius M. For ease of explanation, only primary normals will be considered in the following examples.

Fig. 18(a) shows an expected circle 1801 fitted tangentially to a directed pair :.:"formed by circles CI 1802 and Cr 1803. However, circle Ce 1801 intersects an existing circle Ci 1804. As seen in Fig. 18(b), the actual fitted circle Ca 1805 is fitted to be tangential to C 1 1802, Cr 1803 and Ci 1804, using the well known Apollonian packing geometric method. This forms four new directed pairs: CiCa indicated by vector 1810, CaCi indicated by vector 1812, CiCa (not indicated) and CaCr indicated by vector 1814.

Each of the new directed pairs has corresponding primary vectors: 1 1806, 1 1807, I' 1808 and r 1809, as shown in Fig. 18(b), to which it is possible to fit new circles and recursively generate new pairs. If the expected circle Ce 1801 intersects more than one i 30 existing circle, then the closest such intersecting circle is chosen. If the radius of actual circle Ca 1805 is below minimum radius m then Ca should be deleted.

Fig. 19(a) shows an expected circle Ce 1901 fitted tangentially to a directed pair formed by circles C 1 1902 and Cr 1903. However, circle 1901 intersects existing outline edge AB 1904. As seen in Fig. 19(b), the actual fitted circle Ca 1905 is fitted to be tangential to circle C 1 1902, circle C, 1903 and outline edge AB 1904, using well known 562580.doc geometric methods. This forms two new directed pairs: CICa indicated by vector 1910 and CCr indicated by vector 1914. Each of these new directed pairs has a corresponding primary normal vectors: 1 1906 and r 1907, as shown in Fig. 19(b), to which it is possible to fit new circles and recursively generate new pairs. Since the outline edge AB 1904 has been packed it is not necessary to further pack towards the vectors 1906 and 1907.

However, to guarantee an optimal fit it is preferable that the possibility of further packing being tested for.

A spacing value can be applied to parametrically control spacing between packed circles. Fig. 20 shows a predetermined spacing value 2003 that can be used to fit the two circles CI 2001 and Cr 2002 such that a minimum spacing of '2S' is guaranteed between circles C 2001 and C, 2002. The spacing value S is not applied to tangent-fitting to the outline edge AB 2004 to ensure that the definition of the outline is not degraded.

An overlapping spacing value 'OS' can also be applied to parametrically control overlap between packed shapes. For example, as seen in Fig. 21, a spacing value OS 2103 can be used in fitting the circles C, 2101 and C, 2102 such that an overlap of 2S is guaranteed between any pair of overlapping circles. As seen in Fig. 21, the overlap spacing value is not applied to tangent fitting to the outline edge AB 2104 to ensure that the definition of an outline shape is not degraded. Preferably, the spacing value S and the spacing value OS are set to the same value such that S can be used to space both overlapping and non-overlapping circles. In this instance, negative values of S are interpreted as overlap and positive values of S can be interpreted as spacing.

The described method provides a number of advantages over existing packing methods. For example, Fig. 24 shows a situation where it is desired to fit a circle tangentially to existing circle C 2401 within the range 2404 delineated by existing circles CI 2402 to the left of circle 2401 and Cr 2403 to the right of circle 2401. Using the 0 prior art tangent-i packing method the resulting circle may be fitted at any of a continuous set of locations (eg. 2405) within the range a. This includes the leftmost limit p *2406 tangential to both C, 2402 and C 2401, and the rightmost limit 2407 tangential to 30 both C 2401 and Cr 2403, but also includes all positions within the range a (eg. 2405).

The limits 2406 and 2407, are the optimal placements for a packed circle so as to guarantee the greatest number of tangencies within the packing, and hence the densest packing.

562580.doc 16- Fig. 25 shows the circles 2401, 2402 and 2403 packed in a preferred manner, where only the leftmost circle CI, 2501 and rightmost circle Cr' 2502 are packed within the range a, hence achieving a superior packing over the tangent-1 method.

As discussed above, the methods discussed above have application to packing any planar geometric shape that can be tested for intersection with the region boundary and existing planar shapes, for arbitrarily shaped 2-dimensional regions defined by a set of closed curves. Further, the circles or other shapes packed in accordance with the method described herein allow for the packing of any defined region with any arbitrary image object. For example, for each circle packed into a defined region in accordance with the method described herein, an image object (eg. a "flower") can be positioned and scaled with respect to the circle thereby providing a decorative effect to the region.

The aforementioned preferred method(s) comprise a particular control flow.

There are many other variants of the described method(s) which use different control flows and which do not depart from the spirit or scope of the present invention.

Furthermore one or more of the steps of the preferred method(s) may be performed in parallel rather sequential.

The method of packing circles within bounded regions of arbitrary shape is preferably practiced using a general-purpose computer system 2600, such as that shown Sin Fig. 26 wherein the processes of Figs. 1 to 25 may be implemented as software, such as an application program executing within the computer system 2600. In particular, the steps of method of packing circles within bounded regions of arbitrary shape are effected by instructions in the software that are carried out by the computer. The software may be divided into two separate parts; one part for carrying out the packing of circles within bounded regions of arbitrary shape; and another part to manage the user interface between the latter and the user. The software may be stored in a computer readable medium, including the storage devices described below, for example. The software is loaded into the computer from the computer readable medium, and then executed by the computer. A computer readable medium having such software or computer program recorded on it is a computer program product. The use of the computer program product in the computer 30 preferably effects an advantageous apparatus for packing circles within bounded regions of arbitrary shape.

The computer system 2600 comprises a computer module 2601, input devices such as a keyboard 2602 and mouse 2603, output devices including a printer 2615 and a display device 2614. A Modulator-Demodulator (Modem) transceiver device 2616 is used by the computer module 2601 for communicating to and from a communications 562580.doc -17network 2620, for example connectable via a telephone line 2621 or other functional medium. The modem 2616 can be used to obtain access to the Internet, and other network systems, such as a Local Area Network (LAN) or a Wide Area Network (WAN).

The computer module 2601 typically includes at least one processor unit 2605, a memory unit 2606, for example formed from semiconductor random access memory (RAM) and read only memory (ROM), input/output interfaces including a video interface 2607, and an I/O interface 2613 for the keyboard 2602 and mouse 2603 and optionally a joystick (not illustrated), and an interface 2608 for the modem 2616. A storage device 2609 is provided and typically includes a hard disk drive 2610 and a floppy disk drive 2611. A magnetic tape drive (not illustrated) may also be used. A CD- ROM drive2612 is typically provided as a non-volatile source of data. The components 2605 to 2613 of the computer module 2601, typically communicate via an interconnected bus 2604 and in a manner which results in a conventional mode of operation of the computer system 2600 known to those in the relevant art. Examples of computers on which the arrangements can be practised include IBM-PC's and compatibles, Sun Sparcstations or alike computer systems evolved therefrom.

Typically, the application program is resident on the hard disk drive 2610 and read and controlled in its execution by the processor 2605. Intermediate storage of the program and any data fetched from the network 2620 may be accomplished using the semiconductor memory 2606, possibly in concert with the hard disk drive 2610. In some instances, the application program may be supplied to the user encoded on a CD-ROM or floppy disk and read via the corresponding drive 2612 or 2611, or alternatively may be read by the user from the network 2620 via the modem device 2616. Still further, the software can also be loaded into the computer system 2600 from other computer readable medium including magnetic tape, a ROM or integrated circuit, a magneto-optical disk, a radio or infra-red transmission channel between the computer module 2601 and another device, a computer readable card such as a PCMCIA card, and the Internet and Intranets including email transmissions and information recorded on websites and the like. The foregoing is merely exemplary of relevant computer readable mediums. Other computer 30 readable media may alternatively be practiced.

The method of packing circles within bounded regions of arbitrary shape may alternatively be implemented in dedicated hardware such as one or more integrated circuits performing the functions or sub functions of Figs. 1 to 25. Such dedicated hardware may include graphic processors, digital signal processors, or one or more microprocessors and associated memories.

562580.doc 18- The foregoing describes only some embodiments of the present invention, and modifications and/or changes can be made thereto without departing from the scope and spirit of the invention, the embodiments being illustrative and not restrictive.

In the context of this specification, the word "comprising" means "including principally but not necessarily solely" or "having" or "including" and not "consisting only of'. Variations of the word comprising, such as "comprise" and "comprises" have corresponding meanings.

g* oo* 562580.doc

Claims (8)

1. 2. The method according to claim 1, comprising the further step C 1 of nestling at least one of said circles into a corner defined by said boundary, depending on at least one of said parameters.
2. 3. The method according to claim 1, wherein said circle that is placed tangentially in step to at least two of said circles, is placed relative to a normal vector defined by said at least two circles.
3. 4. The method according to claim 1, wherein said plurality of predetermined points :are substantially evenly positioned on said boundary.
4. 5. The method according to claim 1, wherein said plurality of predetermined points are substantially randomly distributed on said boundary.
5. 6. The method according to claim 1, comprising the further step C 2 of placing at least two circles at each interior obtuse angle defined by said boundary.
6. 7. The method according to claim 6, wherein said at least two circles placed at each interior obtuse angle are of different size.
7. 8. The method according to claim 1, wherein said parameters include a minimum radius.
8. 562580.doc 9. The method according to claim 1, wherein said parameters include a maximum radius. The method according to claim 1, wherein said parameters include a spacing value. 11. The method according to claim 8, wherein circles smaller than said minimum radius are discarded. 12. The method according to claim 1, wherein an object can be placed with respect to each of said circles. 13. The method according to claims 8 and 9, wherein said maximum radius and said minimum radius are equal. 14. A method of packing circles within a bounded image, said method comprising the steps of: defining a boundary for said image; specifying parameters for said circles; nestling at least one of said circles into a corner defined by said boundary, depending on at least one of said parameters; o! placing at least one circle at each of a plurality of predetermined points, tangentially to said boundary whilst maintaining a spatial relationship of at least one of .said parameters; and 25 placing at least one circle tangentially to at least two of said circles previously placed on said boundary. An apparatus for packing circles within a bounded image, said apparatus -comprising: 30 defining means for defining a boundary for said image; specifying means for specifying parameters for said circles; placing means for placing at least one circle at each of a plurality of predetermined points, tangentially to said boundary whilst maintaining a spatial relationship of at least one of said parameters, and for placing at least one circle tangentially to at least two of said circles previously placed on said boundary. 562580.doc -21 16. The apparatus according to claim 15, further comprising means for nestling at least one of said circles into a corner defined by said boundary, depending on at least one of said parameters. 17. The apparatus according to claim 15, wherein said circle that is placed tangentially to at least two of said circles, is placed relative to a normal vector defined by said at least two circles. 18. The apparatus according to claim 15, wherein said plurality of predetermined points are substantially evenly positioned on said boundary. 19. The apparatus according to claim 15, wherein said plurality of predetermined points are substantially randomly distributed on said boundary. The apparatus according to claim 15, further comprising means for placing at least two circles at each interior obtuse angle defined by said boundary. .21. The method according to claim 20, wherein said at least two circles placed at S 20 each interior obtuse angle are of different size. 22. The apparatus according to claim 15, wherein said parameters include a minimum radius. .ooo•r 23. The apparatus according to claim 15, wherein said parameters include a maximum radius. 24. The apparatus according to claim 15, wherein said parameters include a spacing S'value. The apparatus according to claim 22, wherein circles smaller than said minimum radius are discarded. 26. The apparatus according to claim 15, wherein an object can be placed with respect to each of said circles. 562580.doc -22- 27. The apparatus according to any one of claims 22 and 23, wherein said maximum radius and said minimum radius are equal. 28. An apparatus for packing circles within a bounded image, said apparatus comprising: defining means for defining a boundary for said image; specifying means for specifying parameters for said circles; nestling means for nestling at least one of said circles into a corner defined by said boundary, depending on at least one of said parameters; placing means for placing at least one circle at each of a plurality of predetermined points, tangentially to said boundary whilst maintaining a spatial relationship of at least one of said parameters, and for placing at least one circle tangentially to at least two of said circles previously placed on said boundary. 29. An apparatus for packing circles within a bounded image, said apparatus comprising: a memory for storing a program; and a processor for executing the program, said program comprising code for a 20 performing the followings steps: 0. defining a boundary for said image; 'o0 specifying parameters for said circles; placing at least one circle at each of a plurality of predetermined points, tangentially to said boundary whilst maintaining a spatial relationship of at least one of 25 said parameters; and placing at least one circle tangentially to at least two of said circles previously placed on said boundary. o 30. An apparatus for packing circles within a bounded image, said apparatus 30 comprising: a memory for storing a program; and a processor for executing the program, said program comprising code for performing the followings steps: defining a boundary for said image; specifying parameters for said circles; 562580.doc -23- nestling at least one of said circles into a corner defined by said boundary, depending on at least one of said parameters; placing at least one circle at each of a plurality of predetermined points, tangentially to said boundary whilst maintaining a spatial relationship of at least one of said parameters; and placing at least one circle tangentially to at least two of said circles previously placed on said boundary. 31. A program for packing circles within a bounded image, said program comprising: code for defining a boundary for said image; code for specifying parameters for said circles; code for placing at least one circle at each of a plurality of predetermined points, tangentially to said boundary whilst maintaining a spatial relationship of at least one of said parameters; and code for placing at least one circle tangentially to at least two of said circles previously placed on said boundary. 32. A program for packing circles .within a bounded image, said program t 4 comprising: :0o code for defining a boundary for said image; code for specifying parameters for said circles; code for nestling at least one of said circles into a corner defined by said d:es: boundary, depending on at least one of said parameters; code for placing at least one circle at each of a plurality of predetermined points, tangentially to said boundary whilst maintaining a spatial relationship of at least one of said parameters; and code for placing at least one circle tangentially to at least two of said circles °previously placed on said boundary. 0 33. A method of packing circles within a bounded image, said method being substantially as hereinbefore described with reference to any one of the embodiments as illustrated in Figs. 1 to 26. 562580.doc -24- 34. An apparatus for packing circles within a bounded image, said apparatus being substantially as hereinbefore described with reference to any one of the embodiments as illustrated in Figs. 1 to 26. 35. A program for packing circles within a bounded image, said program being substantially as hereinbefore described with reference to any one of the embodiments as illustrated in Figs. 1 to 26. DATED this the Thirteenth Day of August, 2001 Canon Kabushiki Kaisha Patent Attorneys for the Applicant SPRUSON FERGUSON *ooooo* o0 o 562580.doc