- Number
- 9633459
- Published
- 2017-04-25
- Filed
- 2013-08-23
- Assignee
- DISNEY ENTERPRISES, INC.
- Inventors
- Frattarola; Gary et al.
- CPC
- G06T11/40
- Verdict
- Low Notable software
- Source
- Google Patents · FreePatentsOnline
The keeper's note
Generates a 3D convex/concave hull mesh from point-cloud data for use in modeling and simulation.
Abstract
Methods and systems are disclosed for generating a hull that mayhave concavities. One example of such a method includes creating a collection of columns representing a first hull, growing the first hull by increasing a height of one or more columns, creating a collection of rows representing a second hull, growing the second hull by increasing a width of one or more rows, and creating a third hull by combing the first and second hulls.
Background
BRIEF DESCRIPTION OF THE DRAWINGS(1) FIG. 1 is a flowchart for one embodiment of a method for creating a hull that may have concavities.(2) FIG. 1A is a flowchart for one embodiment of a method for creating a hull that may have concavities.(3) FIG. 2 is a flowchart for one embodiment of a method for creatinga hull that may have concavities.(4) FIG. 3A illustrates a collection of columns derived from an image and that form a first hull.(5) FIG. 3B illustrates a collection of rows derived from an image and that form a second hull.(6) FIGS. 4A through 4D illustrate methods to grow columns and rows in a hull.(7) FIG. 5 illustrates a hull that may be created using one of the methods from FIGS. 1, 1A, or 2.(8) FIG. 6 illustrates one example of a polygon mesh that corresponds to the hull from(9) FIG. 5 overlaid on an image.(10) FIG. 7 is a block diagram of a computer graphics system for creating a hull that may have concavities.(11) FIG. 8 is a flowchart for one embodiment of a method for generating a polygon mesh.(12) FIG. 9 is a flowchart for one embodiment of a method for generating a polygon mesh.(13) FIGS. 10A through 10F are flowcharts for generating a polygon mesh.(14) FIGS. 11A and 11B illustrate scan line run lengths that may be used during the process of generating a polygonmesh.(15) FIGS. 12A through 12C illustrate rectangles that may be divided and combined during the process of generating a polygon mesh.(16) FIG. 13 illustrates one example of a polygon mesh overlaid o
Claims
1. A method, comprising: creating, by a processor, a collection of columns based on an upper pixel of interest and a lower pixel of interest for each ofa plurality of vertical lines of an image, the collection of columns representing a firsthull; growing, by the processor, the first hull by increasing a height of one or more columns in the collection of columns based on a comparison between positions of the upper and/or lower pixels of interest for two or more adjacent vertical lines of the image, whereinthe height of the one or more columns in the collection of columns is increased based on the positions of the upper and/or lower pixels of interest for two or more adiacent vertical lines of the image being within a first error tolerance of each other; creating, by theprocessor, a collection of rows based on a leftmost pixel of interest and a rightmost pixel of interest for each of a plurality of horizontal lines of the image, the collection ofrows representing a second hull; growing, by the processor, the second hull by increasinga width of one or more rows in the collection of rows based on a comparison between positions of the leftmost and/or rightmost pixels of interest for two or more adjacent horizontal lines of the image, wherein the width of the one or more rows in the collection of rowsis increased based on the positions of the leftmost and/or rightmost pixels of interest for two or more adiacent horizontal lines of the image being within a second error tolerance of each other; creating, by the processor, a third hull by combining the first and second hulls; and generating, by the processor, a polygon mesh corresponding to the third hull,wherein the polygon mesh defines a number of pixels of the image to be rendered for display; and rendering, by the processor, a sprite for display, wherein the sprite includes pixels located within the polygon mesh.
12. A method, comprising: creating, by a processor, ahull based on outermost pixels of interest for each of a plurality of lines of an image, wherein the lines extend in a first direction; growing, by the processor, the hull in the first direction based on comparisons between positions of the outermost pixels of interestfor two or more lines of the image that are adjacent in a second direction, wherein the hull is grown in the first direction based on the positions of the outermost pixels of interest for two or more lines that are adjacent in the second direction being within a first error tolerance of each other; generating, by the processor, a polygon mesh to fill the hull; and rendering, by the processor, a sprite for display, wherein the sprite includes pixels located within the polygon mesh.
15. A method, comprising creating, by a processor, a collection of columns based on an upper pixel of interest and a lower pixel of interest for each of a plurality of vertical lines of an image; creating, by the processor, a collection of rows based on a leftmost pixel of interest and a rightmost pixel of interest for each of a plurality of horizontal lines of the image; extending, one or more columns in a vertical direction based on a horizontally adjacent column, wherein the one or more columns are extended based on the positions of the upper and/or lower pixels of interest for the one or more columns and the horizontally adjacent column being within a first error tolerance of each other; defining, by the processor a hull that includes pixels represented in both the collection of columns and the collection of rows; and rendering, by the processor, a plurality of pixels, wherein the plurality of pixels comprises only the pixels included in the hull.
18. A system, comprising: a processor configured to create a hull based on outermost pixels of interest for each of a plurality of lines of an image, grow the hull in a first dimension based on comparisons between positions of the outermost pixels of interest for two or more adjacent lines of the image in a second dimension, wherein the hull is grown in the first dimension based on the positions of the outermost pixels of interest for the two or more adjacent lines of the image in the second dimension being within a firsterror tolerance of each other, and generate a polygon mesh to fill the hull; and a display coupled to the processor and configured to render a plurality of pixels within the polygon mesh generated by the processor.