Efficient computation of shadows

• US 9,262,861 B2
• Filed: 07/21/2014
• Issued: 02/16/2016
• Est. Priority Date: 06/24/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zhu, Teng-Hui, Hoford, John
• Primary Examiner(s): CHOW, JEFFREY J
• Application Number:
  US14/337,115
• Publication Number:
  US 20150371435A1
• Time in Patent Office: 575 Days
• US Class Current: 1/1
• CPC Class Codes: G06T 15/60 Shadow generation

Abstract

Methods and apparatus are provided for displaying shadows of polygonal light sources. A computing device can determine a light-source polygon of a polygonal light source, where the light-source polygon includes light-source vertices. The computing device can determine an occluding polygon between the light-source polygon and a background surface. The computing device can determine a shadow of the occluding polygon on the background surface by: for each light-source vertex, determining a vertex-shadow region of the background surface corresponding to a shadow cast upon the background surface by the occluding polygon for light emitted from the light-source vertex, determining an umbra of the shadow based on an intersection of the vertex-shadow regions, and determining a penumbra of the shadow based on a convex representation of a union of vertex-shadow regions. The computing device can display the shadow.

Claims

1. A method, comprising:

determining a light-source polygon of a polygonal light source configured to emit light using a computing device, wherein the light-source polygon comprises a plurality of light-source vertices;

determining an occluding polygon using the computing device, wherein the occluding polygon is between the light-source polygon and a background surface;

determining a shadow of the occluding polygon on the background surface using the computing device by at least;

for each light-source vertex in the plurality of light-source vertices, determining a vertex-shadow region of the background surface corresponding to a shadow cast upon the background surface by the occluding polygon for light emitted from the light-source vertex,

determining an umbra of the shadow of the occluding polygon based on an intersection of the plurality of vertex-shadow regions, and

determining a penumbra of the shadow of the occluding polygon based on a convex representation of a union of the plurality of vertex-shadow regions; and

displaying at least part of the shadow of the occluding polygon using the computing device.

2. The method of claim 1, wherein determining the convex representation of the union of the plurality of vertex-shadow regions comprises determining a convex hull of the union of the plurality of vertex-shadow regions.

3. The method of claim 1, wherein determining the convex representation of the union of the plurality of vertex-shadow regions comprises:

generating a smoothed convex hull by at least applying a filter to the convex hull; and

determining that the convex representation comprises the smoothed convex hull.

4. The method of claim 1, wherein the shadow of the occluding polygon comprises the umbra and the penumbra, and wherein determining the shadow of the occluding polygon comprises:

determining a shadow centroid based on a centroid of the umbra and the penumbra; and

determining a plurality of rays, wherein each ray of the plurality of rays starts at the shadow centroid and goes in a direction of the penumbra.

5. The method of claim 4, wherein determining the shadow of the occluding polygon comprises determining a plurality of polygons representing the penumbra, and wherein the plurality of polygons are based upon the plurality of rays.

6. The method of claim 5, wherein the umbra is associated with an umbra transparency value, wherein an outer edge of the penumbra is associated with a penumbra-outer-edge transparency value, wherein the umbra transparency value differs from the penumbra transparency value, and wherein each of the plurality of polygons representing the penumbra is associated with a polygon transparency value that is based on the umbra transparency value and/or the penumbra-outer-edge transparency value.

7. The method of claim 6, wherein the plurality of polygons representing the penumbra are arranged into one or more polygon layers, and wherein each polygon in a polygon layer of the one or more polygon layers is associated with a predetermined transparency value.

8. The method of claim 1, wherein the occluding polygon is based upon a rectangle.

9. The method of claim 1, wherein providing the display of at least part of the shadow comprises providing a display of the occluding polygon and the at least part of the shadow.

10. The method of claim 9, wherein the occluding polygon is a user-interface element of a graphical user interface (GUI), and wherein providing the display of at least part of the shadow comprises providing a display of the GUI that includes at least part of the occluding polygon and the at least part of the shadow.

11. A computing device, comprising:

a processor; and

a non-transitory computer readable medium configured to store at least executable instructions, wherein the executable instructions, when executed by the processor, cause the computing device to perform functions comprising;

determining a light-source polygon of a polygonal light source configured to emit light, wherein the light-source polygon comprises a plurality of light-source vertices,

determining an occluding polygon, wherein the occluding polygon is between the light-source polygon and a background surface,

determining a shadow of the occluding polygon on the background surface by at least;

for each light-source vertex in the plurality of light-source vertices, determining a vertex-shadow region of the background surface corresponding to a shadow cast upon the background surface by the occluding polygon for light emitted from the light-source vertex,

determining an umbra of the shadow of the occluding polygon based on an intersection of the plurality of vertex-shadow regions, and

determining a penumbra of the shadow of the occluding polygon based on a convex representation of a union of the plurality of vertex-shadow regions, and

displaying of at least part of the shadow of the occluding polygon.

12. The computing device of claim 11, wherein determining the convex representation of the union of the plurality of vertex-shadow regions comprises determining a convex hull of the union of the plurality of vertex-shadow regions.

13. The computing device of claim 12, wherein determining the convex representation of the union of the plurality of vertex-shadow regions comprises generating a smoothed convex hull by at least applying a filter to the convex hull.

14. The computing device of claim 11, wherein the shadow of the occluding polygon comprises the umbra and the penumbra, and wherein determining the shadow of the occluding polygon comprises:

determining a shadow centroid based on a centroid of the umbra and the penumbra; and

determining a plurality of rays, wherein each ray of the plurality of rays starts at the shadow centroid and goes in a direction of the penumbra.

15. The computing device of claim 14, wherein determining the shadow of the occluding polygon comprises determining a plurality of polygons representing the penumbra, and wherein the plurality of polygons are based upon the plurality of rays.

16. The computing device of claim 15, wherein the umbra is associated with an umbra transparency value, wherein an outer edge of the penumbra is associated with a penumbra-outer-edge transparency value, wherein the umbra transparency value differs from the penumbra transparency value, and wherein each of the plurality of polygons representing the penumbra is associated with a polygon transparency value that is based on the umbra transparency value and/or the penumbra-outer-edge transparency value.

17. The computing device of claim 16, wherein the plurality of polygons representing the penumbra are arranged into one or more polygon layers, and wherein each polygon in a polygon layer of the one or more polygon layers is associated with a predetermined transparency value.

18. The computing device of claim 11, wherein providing the display of at least part of the shadow comprises providing a display of the occluding polygon and the at least part of the shadow.

19. The computing device of claim 18, wherein the occluding polygon is a user-interface element of a graphical user interface (GUI), and wherein providing the display of at least part of the shadow comprises providing a display of the GUI that includes at least part of the occluding polygon and the at least part of the shadow.

20. An article of manufacture comprising a non-transitory computer readable medium configured to store at least executable instructions, wherein the executable instructions, when executed by a processor of a computing device, cause the computing device to perform functions comprising:

determining a light-source polygon of a polygonal light source configured to emit light, wherein the light-source polygon comprises a plurality of light-source vertices;

determining an occluding polygon, wherein the occluding polygon is between the light-source polygon and a background surface;

determining a shadow of the occluding polygon on the background surface by at least;

for each light-source vertex in the plurality of light-source vertices, determining a vertex-shadow region of the background surface corresponding to a shadow cast upon the background surface by the occluding polygon for light emitted from the light-source vertex,

determining an umbra of the shadow of the occluding polygon based on an intersection of the plurality of vertex-shadow regions, and

determining a penumbra of the shadow of the occluding polygon based on a convex representation of a union of the plurality of vertex-shadow regions; and

displaying of at least part of the shadow of the occluding polygon.