# US 8,786,599 B2 · Segmentation of free-form shapes into chains of circular elements in computer graphics applications

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,786,599 B2
- Document ID: US8786599B2
- Status: Granted
- Kind: B2
- Application number: 13/167,918
- Filed: 2011-06-24
- Published: 2012-03-22
- Granted: 2014-07-22
- Earliest claimed: 2010-06-25
- Assignees: International Business Machines Corporation
- Applicants: Stefano Piergiovanni
- Inventors: Stefano Piergiovanni
- Web page: https://patentgrep.com/patent/US8786599B2

## CPC

- G06T 11/20: Drawing from basic elements
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

A solution for representing a free-form shape in a data-processing system is proposed. An illustrative method comprises associating sample points defining the free-form shape with a set of circular elements, and storing an indication of the circular elements. Associating includes determining a set of pivot points among the sample points in correspondence of maximum and minimum curvatures of the free-form shape, partitioning the sample points into a set of first groups of sample points each spanning around a corresponding pivot point and a set of second groups of sample points each extending according to a predefined minimum extent between a corresponding pair of adjacent first groups of sample points. Each first group is associated with a first circular element fitting the first group of sample points, and each second group is associated with at least one second circular element providing a predefined continuity with each adjacent first circular element.

## Claims

### Claim 1

A method for representing a free-form shape in a data-processing system, the method comprising:
providing an indication of a plurality of sample points defining the free-form shape;
determining a set of pivot points among the plurality of sample points corresponding to maximum and minimum curvatures of the free-form shape,
partitioning the plurality of sample points into a set of first groups of sample points and a set of second groups of sample points, each first group of sample points spanning around a corresponding pivot point and each second group of sample points extending according to a predefined minimum extent between a corresponding pair of adjacent first groups of sample points,
associating each first group of sample points with a first circular element fitting said each first group of sample points, and
associating each second group of sample points with a second circular element providing a predefined continuity with each first circular element adjacent to the second circular element; and
storing an indication of said circular elements into a memory of said data-processing system.

### Claim 2 (depends on 1)

The method of claim 1, wherein associating each second group of sample points with the second circular element providing the predefined continuity with each first circular element adjacent to the second circular element comprises:
associating a first of the set of second groups of sample points with the second circular element alone if the second circular element provides a tangent continuity with each first circular element adjacent to the second circular element; and
associating a second of the set of second groups of sample points with the second circular element and a third circular element if the second circular element provides a tangent continuity with each first circular element adjacent to the second circular element.

### Claim 3 (depends on 2)

The method of claim 2, wherein the free-form shape is a bi-dimensional free-form curve, and wherein each circular element is a bi-dimensional circular arc.

### Claim 4 (depends on 3)

The method of claim 3, wherein providing an indication of a plurality of sample points comprises:
providing a mathematical representation of the free-form curve, and
evaluating the mathematical representation with a predefined pitch along the free-form curve.

### Claim 5 (depends on 3)

The method of claim 3, wherein the sample points are ordered in a sequence, and determining a set of pivot points comprises:
calculating an indicator of curvature of the free-form curve at each sample point;
determining each relative maximum and each relative minimum of the indicators of curvature along the sequence; and
setting the pivot points to the sample points associated with the relative maximum and to the sample points associated with the relative minimum.

### Claim 6 (depends on 5)

The method of claim 5, wherein calculating an indicator of curvature of the free-form curve at each sample point comprises:
calculating a circumference passing through the each sample point and each adjacent sample point along the sequence; and
setting the indicator of curvature according to a radius of the circumference.

### Claim 7 (depends on 3)

The method of claim 3, wherein associating each first group of sample points with a first circular element comprises:
fitting a first group of sample points by an eligible first circular arc,
verifying a compliance of the eligible first circular arc with a set of segmentation constraints, and
associating the first group of sample points with the eligible first circular arc in response to a determination that the eligible first circular arc is compliant with the set of segmentation constraints; and
otherwise updating the first group of sample points and each second group of sample points adjacent to the first group of sample points.

### Claim 8 (depends on 7)

The method of claim 7, wherein fitting the first group of sample points by an eligible first circular arc comprises fitting the first group of sample points by an eligible first circular arc utilizing a least squares algorithm.

### Claim 9 (depends on 7)

The method of claim 7, wherein updating the first group of sample points and each second group of sample points adjacent to the first group of sample points comprises:
reducing the first group of sample points by at least one sample point in correspondence of at least one end thereof and increasing each second group of sample points adjacent to the first group of sample points by a corresponding at least one sample point.

### Claim 10 (depends on 7)

The method of claim 7, wherein associating the second group of sample points with a single second circular element comprises:
in response to an identification of an eligible second circular arc in tangent continuity with each first circular arc adjacent to the eligible second circular arc
verifying a compliance of the eligible second circular arc with the set of segmentation constraints; and
associating the second group of sample points with the eligible second circular arc in response to a determination that the eligible second circular arc is compliant with the set segmentation constraints; and
otherwise updating at least one adjacent first circular arc.

### Claim 11 (depends on 10)

The method of claim 10, wherein associating the second group of sample points with two second circular elements comprises:
identifying two eligible second circular arcs in tangent continuity with each adjacent first circular arc;
verifying a compliance of the two eligible second circular arcs with the set of segmentation constraints; and
associating the second group of sample points with the two eligible second circular arcs in response to a determination that the two eligible second circular arcs are compliant with the set of segmentation constraints; and
otherwise updating at least one adjacent first circular arc.

### Claim 12 (depends on 10)

The method of claim 10, wherein updating at least one adjacent first circular arc comprises:
shortening the at least one adjacent first circular arc by a predefined extent.

### Claim 13 (depends on 7)

The method of claim 7, wherein the set of segmentation constraints include data indicating at least two of a maximum distance between each sample point and a corresponding circular arc, a minimum length of the corresponding circular arc, and a minimum radius of corresponding circular arc.

### Claim 14

A non-transitory computer program product for representing a free-form shape, the computer program product comprising:
a computer readable storage medium having computer usable program code embodied therewith, the computer usable program code comprising a computer usable program code configured to:
provide an indication of a plurality of sample points defining the free-form shape;
determine a set of pivot points among the plurality of sample points corresponding to maximum and minimum curvatures of the free-form shape,
partition the plurality of sample points into a set of first groups of sample points and a set of second groups of sample points, each first group of sample points spanning around a corresponding pivot point and each second group of sample points extending according to a predefined minimum extent between a corresponding pair of adjacent first groups of sample points,
associate each first group of sample points with a first circular element fitting said each first group of sample points, and
associate each second group of sample points with a second circular element providing a predefined continuity with each first circular element adjacent to the second circular element; and
store an indication of said circular elements into a memory of said data-processing system.

### Claim 15 (depends on 14)

The computer program product of claim 14, wherein the computer usable program code configured to associate each second group of sample points with a second circular element providing a predefined continuity with each first circular element adjacent to the second circular element comprises the computer usable program code configured:
associate a first of the set of second groups of sample points with the second circular element alone if the second circular element provides a tangent continuity with each first circular element adjacent to the second circular element; and
associate a second of the set of second groups of sample points with the second circular element and a third circular element if the second circular element provides a tangent continuity with each first circular element adjacent to the second circular element.

### Claim 16 (depends on 15)

The computer program product of claim 15, wherein the free-form shape is a bi-dimensional free-form curve, and wherein each circular element is a bi-dimensional circular arc.

### Claim 17 (depends on 16)

The computer program product of claim 16, wherein the computer usable program code configured to provide an indication of a plurality of sample points comprises the computer usable program code configured to:
provide a mathematical representation of the free-form curve, and
evaluate the mathematical representation with a predefined pitch along the free-form curve.

### Claim 18 (depends on 16)

The computer program product of claim 16, wherein the sample points are ordered in a sequence, and the computer usable program code configured to determine a set of pivot points comprises the computer usable program code being configured to:
calculate an indicator of curvature of the free-form curve at each sample point;
determine each relative maximum and each relative minimum of the indicators of curvature along the sequence; and
set the pivot points to the sample points associated with the relative maximum and to the sample points associated with the relative minimum.

### Claim 19

A data-processing system comprising:
a memory;
a processor, coupled to said memory;
a segmentation engine operable to,
provide an indication of a plurality of sample points defining the free-form shape;
determine a set of pivot points among the plurality of sample points corresponding to maximum and minimum curvatures of the free-form shape,
partition the plurality of sample points into a set of first groups of sample points and a set of second groups of sample points, each first group of sample points spanning around a corresponding pivot point and each second group of sample points extending according to a predefined minimum extent between a corresponding pair of adjacent first groups of sample points,
associate each first group of sample points with a first circular element fitting said each first group of sample points, and
associate each second group of sample points with a second circular element providing a predefined continuity with each first circular element adjacent to the second circular element; and
store an indication of said circular elements into the memory of said data-processing system.

### Claim 20 (depends on 19)

The data processing system of claim 19, wherein the segmentation engine operable to associate each second group of sample points with a second circular element providing a predefined continuity with each first circular element adjacent to the second circular element comprises the segmentation engine being operable to:
associate a first of the set of second groups of sample points with the second circular element alone if the second circular element provides a tangent continuity with each first circular element adjacent to the second circular element; and
associate a second of the set of second groups of sample points with the second circular element and a third circular element if the second circular element provides a tangent continuity with each first circular element adjacent to the second circular element.