# US 2004/0024575 A1 · Method and apparatus for shape deformation and placement

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

- Number: US 2004/0024575 A1
- Document ID: US20040024575A1
- Status: Published application
- Kind: A1
- Application number: 10/363,220
- Filed: 2003-03-06
- Published: 2004-02-05
- Earliest claimed: 2000-09-19
- Assignees: Technion Research & Development Foundation Limited
- Inventors: Tatiana Surazhsky; Gershon Elber
- Web page: https://patentgrep.com/patent/US20040024575A1

## CPC

- G06T 3/18: Image warping, e.g. rearranging pixels individually
- G06T 11/23: using straight lines or curves
- G06T 17/30: Polynomial surface description
- G06T 19/20: Editing of three-dimensional [3D] images, e.g. changing shapes or colours, aligning objects or positioning parts
- G06T 2219/2021: Shape modification
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

A method for deforming a plurality of shapes is described wherein each of the shapes comprises a set of parametric curves. The method comprises: providing a parametric surface, and forming a deformed shape for each of the shapes by performing a symbolic composition between the parametric surface and each parametric curve from the set of parametric curves comprising the shape being deformed. The parametric surface is defined by two parameters varying over a parametric domain, such that each of the parametric curves comprising the shapes lies in the parametric domain of the surface.

## Claims

### Claim 1

A method for deforming a plurality of shapes, wherein each of said shapes comprises a set of parametric curves, said method comprising:
providing a parametric surface having a first and a second parameter varying over a parametric domain, such that each of said parametric curves comprising said shapes lies in the parametric domain of said surface; and,
for each of said shapes, forming a deformed shape according to said parametric surface by performing a symbolic composition between said parametric surface and each parametric curve from the set of parametric curves comprising said shape thereby to generate a set of deformed parametric curves.

### Claim 2 (depends on 1)

A method for deforming a plurality of shapes according to claim 1, wherein said parametric surface comprises a PPR surface.

### Claim 3 (depends on 2)

A method for deforming a plurality of shapes according to claim 2, wherein all of said parametric curves comprise PPR curves.

### Claim 4 (depends on 1)

A method for deforming a plurality of shapes according to claim 1, wherein at least one of said parametric curves comprises a PPR curve.

### Claim 5 (depends on 1)

A method for deforming a plurality of shapes according to claim 1, wherein all of said parametric curves comprise PPR curves.

### Claim 6 (depends on 2)

A method for deforming a plurality of shapes according to claim 2, wherein a PPR surface comprises one of the following surfaces: polynomial spline, Hermite, Lagrange, Bezier, and B-spline.

### Claim 7 (depends on 4)

A method for deforming a plurality of shapes according to claim 4, wherein a PPR curve comprises one of the following curves: polynomial spline, Hermite, Lagrange, Bezier, and B-spline.

### Claim 8 (depends on 1)

A method for deforming a plurality of shapes according to claim 1, wherein at least one of said curves comprises a set of control points, and wherein said method further comprises forming a parametric representation of said curve from said set of control points.

### Claim 9 (depends on 1)

A method for deforming a plurality of shapes according to claim 1, wherein said surface is provided by interfacing with a user.

### Claim 10 (depends on 1)

A method for deforming a plurality of shapes according to claim 1, further comprising:
calculating the placement of a plurality of points along each curve from the set of deformed parametric curves comprising each of said deformed shapes; and, outputting said points.

### Claim 11 (depends on 10)

A method for deforming a plurality of shapes according to claim 10, further comprising displaying said plurality of deformed shapes.

### Claim 12 (depends on 11)

A method for deforming a plurality of shapes according to claim 11, wherein said points are displayed by one of a group of devices comprising:
cathode ray tube (CRT), flat panel display, electroluminescent display, gas plasma display, liquid crystal display, laser printer, liquid crystal printer, LED printer, and ink-jet printer.

### Claim 13 (depends on 1)

A method for deforming a plurality of shapes according to claim 1, wherein at least one of said shapes comprises a character.

### Claim 14 (depends on 1)

A method for deforming a plurality of shapes according to claim 1, wherein said shapes comprise members of an outline font.

### Claim 15 (depends on 1)

A method for deforming a plurality of shapes according to claim 1, wherein said plurality of shapes comprises a sequence of shapes.

### Claim 16 (depends on 1)

A method for deforming a plurality of shapes according to claim 1, wherein said plurality of shapes comprises a single shape.

### Claim 17 (depends on 1)

A method for deforming a plurality of shapes according to claim 1, wherein said set of parametric curves comprises a single parametric curve.

### Claim 18 (depends on 1)

A method for deforming a plurality of shapes according to claim 1, wherein at least one of said parametric curves comprises a Bezier curve.

### Claim 19 (depends on 1)

A method for deforming a plurality of shapes according to claim 1, wherein said parametric surface comprises a PPR surface derived from a PPR base curve.

### Claim 20 (depends on 19)

A method for deforming a plurality of shapes according to claim 19, wherein said PPR surface is further derived from a PPR shape curve.

### Claim 21 (depends on 1)

A method for deforming a plurality of shapes according to claim 1, wherein said surface is planar.

### Claim 22 (depends on 19)

A method for deforming a plurality of shapes according to claim 19, wherein said surface and said base curve are planar.

### Claim 23 (depends on 3)

A method for deforming a plurality of shapes according to claim 3, wherein performing said symbolic composition between said PPR surface and each of said PPR curves comprises:
converting said PPR surface into a set of PR patches by subdividing said surface at all its internal knots;
converting each of said PPR curves into a set of PR segments by subdividing said curve at each value corresponding to an internal knot of the curve and also at each value corresponding to an internal knot of said surface; and,
performing a symbolic composition between each of said PR patches and each PR segment within the parametric domain of said PR patch.

### Claim 24 (depends on 2)

A method for deforming a plurality of shapes according to claim 2, further comprising placing said plurality of shapes along a base curve by:
providing a base curve; and,
providing said surface to be a PPR surface such that, when said second parameter equals a predefined value, said surface unites with said base curve.

### Claim 25 (depends on 24)

A method for deforming a plurality of shapes according to claim 24, wherein said base curve is provided by interfacing with a user.

### Claim 26 (depends on 24)

A method for deforming a plurality of shapes according to claim 24, further comprising reparameterizing said base curve for arc length.

### Claim 27 (depends on 24)

A method for deforming a plurality of shapes according to claim 24, wherein providing said surface to be a PPR surface further comprises providing said surface such that said surface unites with a predefined shape curve when said first parameter is at any constant value in the parametric domain of said surface.

### Claim 28 (depends on 1)

A method for deforming a plurality of shapes according to claim 1, further comprising providing animation effects by generating successive frames of an image, said image comprising said plurality of shapes, wherein generating a frame comprises:
providing a parametric surface; and,
for each of said shapes, forming a deformed shape according to said parametric surface.

### Claim 29 (depends on 28)

A method for deforming a plurality of shapes according to claim 28, wherein generating a frame further comprises placing said plurality of shapes along a base curve by:
providing a PPR base curve; and,
providing said surface to be a PPR surface such that, when said second parameter equals a predefined value, said surface unites with said base curve.

### Claim 30 (depends on 29)

A method for deforming a plurality of shapes according to claim 29, wherein generating a frame further comprises reparameterizing said base curve for arc length.

### Claim 31 (depends on 1)

A method for deforming a plurality of shapes according to claim 1, wherein said surface comprises a three dimensional parametric surface, said method further comprising placing said plurality of shapes on a predefined number of strips on said three dimensional shape by:
splitting said surface into said number of strips;
determining the arc length of each of said strips;
subdividing said plurality of shapes into said number of lines, such that each strip on said surface is associated with a subset of said shapes, wherein the size of each subset is determined by the relative arc lengths of said strips; and,
placing each subset of shapes on said associated strip.

### Claim 32 (depends on 31)

A method for deforming a plurality of shapes according to claim 31, further comprising shading at least one of said plurality of shapes.

### Claim 33 (depends on 32)

A method for deforming a plurality of shapes according to claim 32, wherein shading one of said shapes comprises controlling the width of at least one of said curves comprising-said shape.

### Claim 34 (depends on 32)

A method for deforming a plurality of shapes according to claim 32, wherein shading one of said shapes comprises assigning a weight to said shape thereby to control a property thereof.

### Claim 35 (depends on 32)

A method for deforming a plurality of shapes according to claim 32, wherein said shading is determined by at least one of the following factors:
light intensity, light direction, viewing direction, direction of the reflected light, ambient light, diffuse light, specular light, silhouette enhancement, and distance.

### Claim 36 (depends on 32)

A method for deforming a plurality of shapes according to claim 32, wherein said shading comprises color shading.

### Claim 37 (depends on 34)

A method for deforming a plurality of shapes according to claim 34, wherein said weighting comprises a vector thereby to provide color shading.

### Claim 38

A shape deformer for deforming a plurality of shapes, wherein each of said shapes comprises a set of parametric curves, said deformer comprising:
a surface provider for providing a parametric surface having a first and a second parameter varying over a parametric domain, such that each of said parametric curves comprising said shapes lies in the parametric domain of said surface; and,
a shape transformer for forming each of said shapes into a deformed shape according to said parametric surface, by performing for each of said shapes a symbolic composition between said parametric surface and each parametric curve from the set of parametric curves comprising said shape, to generate a set of deformed parametric curves.

### Claim 39 (depends on 38)

A shape deformer according to claim 38, wherein said parametric surface comprises a PPR surface.

### Claim 40 (depends on 39)

A shape deformer according to claim 39, wherein all of said parametric curves comprise PPR curves.

### Claim 41 (depends on 38)

A shape deformer according to claim 38, wherein at least one of said parametric curves comprises a PPR curve.

### Claim 42 (depends on 38)

A shape deformer according to claim 38, wherein all of said parametric curves comprise PPR curves.

### Claim 43 (depends on 38)

A shape deformer according to claim 38, further comprising an interface for interfacing with a user thereby to provide said surface.

### Claim 44 (depends on 38)

A shape deformer according to claim 38, wherein at least one of said curves comprises a set of control points, and wherein said shape deformer further comprises a curve regenerator for forming a parametric representation of said curve from said set of control points.

### Claim 45 (depends on 38)

A shape deformer according to claim 38, further comprising a calculator for calculating the placement of a plurality of points along each curve from the set of deformed parametric curves comprising each of said shapes, and an output device for outputting said points.

### Claim 46 (depends on 45)

A shape deformer according to claim 45, further comprising a display device for displaying said deformed plurality of shapes.

### Claim 47 (depends on 46)

A shape deformer according to claim 46, wherein said display device is one of a group of devices comprising: cathode ray tube (CRT), flat panel display, electroluminescent display, gas plasma display, liquid crystal display, laser printer, liquid crystal printer, LED printer, and ink-jet printer.

### Claim 48 (depends on 38)

A shape deformer according to claim 38, wherein at least one of said shapes comprises a character.

### Claim 49 (depends on 38)

A shape deformer according to claim 38, wherein said shapes comprise members of an outline font.

### Claim 50 (depends on 38)

A shape deformer according to claim 38, wherein said plurality of shapes comprises a sequence of shapes.

### Claim 51 (depends on 38)

A shape deformer according to claim 38, wherein said plurality of shapes comprises a single shape.

### Claim 52 (depends on 38)

A shape deformer according to claim 38, wherein said set of parametric curves comprises a single parametric curve.

### Claim 53 (depends on 38)

A shape deformer according to claim 38, wherein at least one of said parametric curves comprises a Bezier curve.

### Claim 54 (depends on 38)

A shape deformer according to claim 38, wherein said parametric surface comprises a PPR surface derived from a PPR base curve.

### Claim 55 (depends on 54)

A shape deformer according to claim 54, wherein said parametric surface comprises a PPR surface derived from a PPR base curve and a PPR shape curve.

### Claim 56 (depends on 54)

A shape deformer according to claim 54, wherein said parametric surface comprises a B-spline surface derived from a B-spline base curve.

### Claim 57 (depends on 54)

A shape deformer according to claim 54, wherein said surface and said base curve are planar.

### Claim 58 (depends on 40)

A shape deformer according to claim 40, wherein said shape transformer comprises a surface subdivider for converting said surface into a set of PR patches by subdividing said PPR surface at all its internal knots, and a compositioner for performing a symbolic composition between said each of said PPR curves and said set of Bezier surfaces.

### Claim 59 (depends on 58)

A shape deformer according to claim 58, wherein said compositioner further comprises a curve subdivider for converting each of said PPR curves into a set of PR segments by subdividing said curve at each value corresponding to an internal knot of the curve and also at each value corresponding to an internal knot of said surface, and a sub-compositioner for performing a symbolic composition between each of said PR patches and the corresponding PR segments.

### Claim 60 (depends on 38)

A shape deformer according to claim 38, further comprising a shape placer for placing said plurality of shapes along a base curve, wherein said shape placer comprises a base curve provider for providing a PPR base curve, and wherein said surface provider is operable to provide said surface to be a PPR surface such that, when said second parameter equals a predefined value, said surface unites with said base curve.

### Claim 61 (depends on 60)

A shape deformer according to claim 60, wherein said interface is further operable to interface with a user thereby to provide said base curve.

### Claim 62 (depends on 60)

A shape deformer according to claim 60, further comprising a base curve reparameterizer for reparameterizing said base curve thereby to resize said shapes.

### Claim 63 (depends on 62)

A shape deformer according to claim 62, wherein said base curve reparameterizer is operable to reparameterize said base curve such that the sizing of said shapes after deformation corresponds to the sizing of said shapes prior to deformation.

### Claim 64 (depends on 62)

A shape deformer according claim 62, wherein said base curve reparameterizer is operable to reparameterize said base curve such that selected shapes are emphasized.

### Claim 65 (depends on 60)

A shape deformer according to claim 60, wherein said surface provider is operable to provide said surface to be a PPR surface such that said surface unites with a predefined PPR shape curve when said first parameter is at any constant value in the parametric domain of said surface.

### Claim 66 (depends on 45)

A shape deformer according to claim 45, further comprising an animator for generating successive frames an image, said image comprising said set of shapes, wherein for each frame said animator is operable to provide a parametric surface, to form a deformed plurality of shapes according to said parametric surface, to calculate the placement of a plurality of points along each of said deformed shapes, and to output said points.

### Claim 67 (depends on 66)

A shape deformer according to claim 66, wherein said animator is further operable to place said plurality of shapes along a PPR base curve by providing said surface to be a PPR surface such that, when said second parameter equals a predefined value, said surface unites with said base curve.

### Claim 68 (depends on 67)

A shape deformer according to claim 67, wherein said animator is further operable to reparameterize said base curve for arc length.

### Claim 69 (depends on 38)

A shape deformer according to claim 38, wherein said surface comprises a three dimensional parametric surface, and wherein said shape deformer further comprises a 3D placer for placing said plurality of shapes on a predefined number of strips on said three dimensional shape, said 3D placer comprising a surface splitter for splitting said surface into said number of strips, an arc length measurer for determining the arc length of each of said strips, a subdivider for subdividing said plurality of shapes into said number strips, such that each strip on said surface is associated with a subset of said shapes, wherein the size of each subset is determined by the relative lengths of said strips, and a line placer placing each subset of shapes on said associated strip.

### Claim 70 (depends on 69)

A shape deformer according to claim 69, wherein said 3D placer further comprises a shader for shading at least one of said plurality of shapes.

### Claim 71 (depends on 70)

A shape deformer according to claim 70, wherein shading one of said shapes comprises controlling the width of at least one of said curves comprising said shape.

### Claim 72 (depends on 70)

A shape deformer according to claim 70, wherein shading one of said shapes comprises assigning a weight to said shape thereby to control a property thereof.

### Claim 73 (depends on 70)

A shape deformer according to claim 70, wherein said shading is determined by at least one of the following factors: light intensity, light direction, viewing direction, direction of the reflected light, ambient light, diffuse light, specular light, silhouette enhancement, and distance.

### Claim 74 (depends on 70)

A shape deformer according to claim 70, wherein said shading comprises color shading.

### Claim 75 (depends on 72)

A shape deformer according to claim 72, wherein said weighting comprises a vector thereby to provide color shading.

### Claim 76

A computer program product directly loadable into the internal memory of a digital computing device, comprising software code portions for deforming a plurality of shapes, wherein each of said shapes comprises a set of parametric curves, by performing the steps of:
providing a parametric surface having a first and a second parameter varying over a parametric domain, such that each of said parametric curves comprising said shapes lies in the parametric domain of said parametric surface; and,
for each of said shapes, forming a deformed shape according to said parametric surface by performing a symbolic composition between said parametric surface and each parametric curve from the set of parametric curves comprising said shape thereby to generate a set of deformed parametric curves;
when said product is run on said computing device.

### Claim 77 (depends on 76)

A computer program product according to claim 76, wherein said product is located on a server for download into said digital computing device via a computer network.

### Claim 78 (depends on 76)

A computer program product according to claim 76, wherein said product is located on one of a group of storage media comprising: compact disc (CD), digital versatile disc (DVD), floppy disk, hard disk, and magnetic tape.

### Claim 79 (depends on 76)

A computer program product according to claim 76, comprising further software code portions for performing the steps of:
calculating the placement of a plurality of points along each curve from the set of deformed parametric curves comprising each of said shapes; and, outputting said points.

### Claim 80 (depends on 79)

A computer program product according to claim 79, comprising further software code portions for performing the step of displaying said plurality of deformed shapes.

### Claim 81 (depends on 76)

A computer program product according to claim 76, wherein said shapes comprise members of an outline font.

### Claim 82 (depends on 76)

A computer program product according to claim 76, wherein at least one of said parametric curves comprises a Bezier curve.

### Claim 83 (depends on 76)

A computer program product according to claim 76, wherein said parametric surface comprises a B-spline surface derived from a B-spline base curve.

### Claim 84 (depends on 76)

A computer program product according to claim 76, wherein said parametric surface comprises a PPR surface and all of said parametric curves comprise PPR curves, and wherein performing said symbolic composition between said surface and each of said PPR curves comprises:
converting said PPR surface into a set of PR patches by subdividing said surface at all its internal knots;
converting each of said PPR curves into a set of PR segments by subdividing said curve at each value corresponding to an internal knot of the curve and also at each value corresponding to an internal knot of said surface; and,
performing a symbolic composition between each of said PR patches and each PR segment within the parametric domain of said PR patch.

### Claim 85 (depends on 83)

A computer program product according to claim 83, comprising further software code portions for performing the step of placing said plurality of shapes along a base curve by:
providing a base curve; and,
providing said surface to be a PPR surface such that, when said second parameter equals a predefined value, said surface unites with said base curve.

### Claim 86 (depends on 85)

A computer program product according to claim 85, comprising further software code portions for performing the step of reparameterizing said base curve for arc length.

### Claim 87 (depends on 79)

A computer program product according to claim 79, comprising further software code portions for performing the step of providing animation effects by generating successive frames of an image, said image comprising said plurality of shapes, wherein generating a frame comprises:
providing a parametric surface; and,
for each of said shapes, forming a deformed shape according to said parametric surface.

### Claim 88 (depends on 76)

A computer program product according to claim 76, wherein said surface comprises a three dimensional parametric surface, comprising further software code portions for performing the step of placing said plurality of shapes on a predefined number of strips on said three dimensional shape by:
splitting said surface into said number of strips;
determining the arc length of each of said strips;
subdividing said plurality of shapes into said number strips, such that each strip on said surface is associated with a subset of said shapes, wherein the size of each subset is determined by the relative arc lengths of said strips; and,
placing each subset of shapes on said associated strip.

### Claim 89 (depends on 88)

A computer program product according to claim 88, comprising further software code portions for performing the step of shading at least one of said plurality of shapes.
