# US 7,412,360 B2 · 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 7,412,360 B2 - Document ID: US7412360B2 - Status: Granted - Kind: B2 - Application number: 10/363,220 - Filed: 2001-09-16 - Published: 2004-02-05 - Granted: 2008-08-12 - Earliest claimed: 2000-09-19 - Assignees: Technion Research & Development Foundation Limited - Inventors: Tatiana Surazhsky; Gershon Elber - Web page: https://patentgrep.com/patent/US7412360B2 ## 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 computer implemented method for deforming a plurality of shapes, each said shape being a character in a font set having a font style, said deforming preserving said font style, 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 said parametric curve lies in the parametric domain of said surface; for each of said shapes, forming a deformed character shape according to said parametric surface by performing a symbolic composition between said parametric surface and each said parametric curve thereby to generate a set of deformed parametric curves, each one of the plurality of shapes being a shape of a character; and for each of said shapes, outputting said deformed character shape while preserving said font style. ### Claim 2 (depends on 1) A method for deforming a plurality of shapes according to claim 1, wherein said parametric surface comprises a piecewise polynomial or rational (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 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 polynomial or rational (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 5 (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 6 (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 7 (depends on 6) A method for deforming a plurality of shapes according to claim 6, wherein said base curve is provided by interfacing with a user. ### Claim 8 (depends on 6) A method for deforming a plurality of shapes according to claim 6, further comprising reparameterizing said base curve for arc length. ### Claim 9 (depends on 6) A method for deforming a plurality of shapes according to claim 6, 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 10 (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 11 (depends on 10) A method for deforming a plurality of shapes according to claim 10, wherein a PPR curve comprises one of the following curves: polynomial spline, Hermite, Lagrange, Bezier, and B-spline. ### Claim 12 (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 13 (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 set of control points, and wherein said method further comprises forming a parametric representation of said parametric curve from said set of control points. ### Claim 14 (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 15 (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 said deformed character shape; and, outputting said points. ### Claim 16 (depends on 15) A method for deforming a plurality of shapes according to claim 15, further comprising displaying plurality of deformed character shapes. ### Claim 17 (depends on 16) A method for deforming a plurality of shapes according to claim 16, 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 18 (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 19 (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 20 (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 21 (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 22 (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 23 (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 24 (depends on 23) A method for deforming a plurality of shapes according to claim 23, wherein said PPR surface is further derived from a PPR shape curve. ### Claim 25 (depends on 23) A method for deforming a plurality of shapes according to claim 23, wherein said surface and said base curve are planar. ### Claim 26 (depends on 1) A method for deforming a plurality of shapes according to claim 1, wherein said surface is planar. ### Claim 27 (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 28 (depends on 27) A method for deforming a plurality of shapes according to claim 27, 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 29 (depends on 28) A method for deforming a plurality of shapes according to claim 28, wherein generating a frame further comprises reparameterizing said base curve for arc length. ### Claim 30 (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 surface 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 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 31 (depends on 30) A method for deforming a plurality of shapes according to claim 30, further comprising shading at least one of said plurality of shapes. ### Claim 32 (depends on 31) A method for deforming a plurality of shapes according to claim 31, wherein shading one of said shapes comprises controlling the width of at least one of said curves comprising said shape. ### Claim 33 (depends on 31) A method for deforming a plurality of shapes according to claim 31, wherein shading one of said shapes comprises assigning a weight to said shape thereby to control a property thereof. ### Claim 34 (depends on 33) A method for deforming a plurality of shapes according to claim 33, wherein said weighting comprises a vector thereby to provide color shading. ### Claim 35 (depends on 31) A method for deforming a plurality of shapes according to claim 31, 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 31) A method for deforming a plurality of shapes according to claim 31, wherein said shading comprises color shading. ### Claim 37 A computer-based shape deformer for deforming a plurality of shapes, each said shape being a character in a font set having a font style, said deforming preserving said font style, 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 lies in the parametric domain of said surface; a symbolic composition shape transformer for forming each of said shapes into a deformed character shape according to said parametric surface, by performing for each of said shapes a symbolic composition between said parametric surface and each said parametric curve, to generate a set of deformed parametric curves, each one of the plurality of shapes being a shape of a character; and an output interface for outputting said deformed character shape while preserving said font style. ### Claim 38 (depends on 37) The computer-based shape deformer according to claim 37, wherein said parametric surface comprises a piecewise polynomial or rational (PPR) surface. ### Claim 39 (depends on 38) The computer-based shape deformer according to claim 38, wherein all of said parametric curves comprise PPR curves. ### Claim 40 (depends on 39) The computer-based shape deformer according to claim 39, wherein said shape transformer comprises a surface subdivider for converting said surface into a set of polynomial or rational (PR) patches by subdividing said PPR surface at all its internal knots, 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 41 (depends on 37) The computer-based shape deformer according to claim 37, wherein at least one of said parametric curves comprises a PPR curve. ### Claim 42 (depends on 37) The computer-based shape deformer according to claim 37, wherein all of said parametric curves comprise PPR curves. ### Claim 43 (depends on 37) The computer-based shape deformer according to claim 37, further comprising an interface for interfacing with a user thereby to provide said surface. ### Claim 44 (depends on 37) The computer-based shape deformer according to claim 37, wherein at least one of said parametric curves comprises a set of control points, and wherein said shape deformer further comprises a curve regenerator for forming a parametric representation of said parametric curve from said set of control points. ### Claim 45 (depends on 37) The computer-based shape deformer according to claim 37, 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 said deformed character shape, and an output device for outputting said points. ### Claim 46 (depends on 45) The computer-based shape deformer according to claim 45, further comprising a display device for displaying plurality of deformed character shapes. ### Claim 47 (depends on 46) The computer-based 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 45) The computer-based shape deformer according to claim 45, further comprising an animator for generating successive frames form an image, said image comprising said plurality of shapes, wherein for each frame said animator provides 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 49 (depends on 48) The computer-based shape deformer according to claim 48, wherein said animator places 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 50 (depends on 49) The computer-based shape deformer according to claim 49, wherein said animator reparameterizes said base curve for arc length. ### Claim 51 (depends on 37) The computer-based shape deformer according to claim 37, wherein said shapes comprise members of an outline font. ### Claim 52 (depends on 37) The computer-based shape deformer according to claim 37, wherein said plurality of shapes comprises a sequence of shapes. ### Claim 53 (depends on 37) The computer-based shape deformer according to claim 37, wherein said plurality of shapes comprises a single shape. ### Claim 54 (depends on 37) The computer-based shape deformer according to claim 37, wherein said set of parametric curves comprises a single parametric curve. ### Claim 55 (depends on 37) The computer-based shape deformer according to claim 37, wherein at least one of said parametric curves comprises a Bezier curve. ### Claim 56 (depends on 37) The computer-based shape deformer according to claim 37, wherein said parametric surface comprises a PPR surface derived from a PPR base curve. ### Claim 57 (depends on 56) The computer-based shape deformer according to claim 56, wherein said parametric surface comprises a PPR surface derived from a PPR base curve and a PPR shape curve. ### Claim 58 (depends on 56) The computer-based shape deformer according to claim 56, wherein said parametric surface comprises a B-spline surface derived from a B-spline base curve. ### Claim 59 (depends on 56) The computer-based shape deformer according to claim 56, wherein said surface and said base curve are planar. ### Claim 60 (depends on 37) The computer-based shape deformer according to claim 37, 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 provides 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) The computer-based shape deformer according to claim 60, wherein said interface interfaces with a user thereby to provide said base curve. ### Claim 62 (depends on 60) The computer-based 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) The computer-based shape deformer according to claim 62, wherein said base curve reparameterizer reparameterizes 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) The computer-based shape deformer according claim 62, wherein said base curve reparameterizer reparameterizes said base curve such that selected shapes are emphasized. ### Claim 65 (depends on 60) The computer-based shape deformer according to claim 60, wherein said surface provider provides 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 37) The computer-based shape deformer according to claim 37, 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 surface, 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 67 (depends on 66) The computer-based shape deformer according to claim 66, wherein said 3D placer further comprises a shader for shading at least one of said plurality of shapes. ### Claim 68 (depends on 67) The computer-based shape deformer according to claim 67, wherein shading one of said shapes comprises controlling the width of at least one of said curves comprising said shape. ### Claim 69 (depends on 67) The computer-based shape deformer according to claim 67, wherein shading one of said shapes comprises assigning a weight to said shape thereby to control a property thereof. ### Claim 70 (depends on 69) The computer-based shape deformer according to claim 69, wherein said weighting comprises a vector thereby to provide color shading. ### Claim 71 (depends on 67) The computer-based shape deformer according to claim 67, 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 72 (depends on 67) The computer-based shape deformer according to claim 67, wherein said shading comprises color shading. ### Claim 73 A computer program product in a computer-readable storage device, the computer program product comprising software code portions which when executed on a computing device deform a plurality of shapes, each said shape being a character in a font set having a font style, said deforming preserving said font style, 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; for each of said shapes, forming a deformed character shape according to said parametric surface by performing a symbolic composition between said parametric surface and each said parametric curve thereby to generate a set of deformed parametric curves, each one of the plurality of shapes being a shape of a character; and for each of said shapes, outputting said deformed character shape while preserving said font style. ### Claim 74 (depends on 73) A computer program product according to claim 73, wherein said product is located on a server for download into said digital computing device via a computer network. ### Claim 75 (depends on 73) A computer program product according to claim 73, 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 76 (depends on 73) A computer program product according to claim 73, 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 77 (depends on 76) A computer program product according to claim 76, comprising further software code portions for performing the step of displaying plurality of deformed character shapes. ### Claim 78 (depends on 76) A computer program product according to claim 76, 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 79 (depends on 73) A computer program product according to claim 73, wherein said shapes comprise members of an outline font. ### Claim 80 (depends on 73) A computer program product according to claim 73, wherein at least one of said parametric curves comprises a Bezier curve. ### Claim 81 (depends on 73) A computer program product according to claim 73, wherein said parametric surface comprises a B-spline surface derived from a B-spline base curve. ### Claim 82 (depends on 81) A computer program product according to claim 81, 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 piecewise polynomial or rational (PPR) surface such that, when said second parameter equals a predefined value, said surface unites with said base curve. ### Claim 83 (depends on 82) A computer program product according to claim 82, comprising further software code portions for performing the step of reparameterizing said base curve for arc length. ### Claim 84 (depends on 73) A computer program product according to claim 73, wherein said parametric surface comprises a piecewise polynomial or rational (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 polynomial or rational (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 73) A computer program product according to claim 73, wherein said surface comprises a three dimensional parametric surface, the program product further comprising software code portions for performing the step of placing said plurality of shapes on a predefined number of strips on said three dimensional surface 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 86 (depends on 85) A computer program product according to claim 85, comprising further software code portions for performing the step of shading at least one of said plurality of shapes.