Efficient computation of shadows for circular light sources

• US 9,639,976 B2
• Filed: 10/31/2014
• Issued: 05/02/2017
• Est. Priority Date: 10/31/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zhu, Teng-Hui, Craik, Christopher
• Primary Examiner(s): BROOME, SAID A
• Application Number:
  US14/530,282
• Publication Number:
  US 20160125642A1
• Time in Patent Office: 914 Days
• Field of Search: None
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 15/08 Volume rendering
• CPC Class Codes: G06T 15/506 Illumination models
• CPC Class Codes: G06T 15/60 Shadow generation
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 2200/04 involving 3D image data
• CPC Class Codes: G06T 2200/24 involving graphical user interfaces [GUIs]

Abstract

Methods and apparatus are provided for displaying shadows of circular light sources. A computing device can determine a light source and an occluding polygon that is between the light source and a receiver surface, where the occluding polygon includes vertices connected by edges. The computing device can determine a shadow of the occluding polygon on the receiver surface by at least: determining, for a particular vertex, a projection vertex on the receiver surface by projecting a ray from the center point through the particular vertex; determining an outline polygon based on the projection vertex; determining a projection circle around the projection vertex; determining a penumbra of the shadow based on exterior tangents outside of the outline polygon; and determining an umbra of the shadow based on interior tangents inside the outline polygon. The computing device can display at least part of the shadow.

Claims

1. A method, comprising:

determining a light source configured to emit light using a computing device, wherein the light source comprises a center point;

determining an occluding polygon using the computing device, wherein the occluding polygon is between the light source and a receiver surface, and wherein the occluding polygon comprises a plurality of occluding-polygon vertices connected by occluding-polygon edges;

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

for a particular occluding-polygon vertex in the plurality of occluding-polygon vertices, determining a projection vertex on the receiver surface based on a ray projected from the center point through the particular occluding-polygon vertex;

determining an outline polygon based on the projection vertex;

determining a projection circle around the projection vertex;

determining a penumbra of the shadow of the occluding polygon based on one or more exterior tangents to the projection circle that are outside of the outline polygon; and

determining an umbra of the shadow of the occluding polygon based on one or more interior tangents to the projection circle that are inside of the outline polygon; and

providing at least part of the shadow of the occluding polygon for display using the computing device.

2. The method of claim 1, wherein determining the projection circle around the projection vertex comprises determining a radius for the projection circle based on a height of a corresponding occluding-polygon vertex above the receiver surface.

3. The method of claim 1, wherein the outline polygon comprises a plurality of projection vertices connected by outline-polygon edges, and wherein the plurality of projection vertices comprises the projection vertex.

4. The method of claim 3, wherein determining the penumbra comprises:

determining a particular outline-polygon edge of the outline-polygon edges, wherein the particular outline-polygon edge connects a first projection vertex to a second projection vertex, wherein the first projection vertex is associated with a first projection circle, and wherein the second projection vertex is associated with a second projection circle;

determining a normal to the particular outline-polygon edge;

determining a first intersection of a first ray with the first projection circle, wherein the first ray starts at the first projection vertex and is directed along the normal to the particular outline-polygon edge, and wherein the first intersection is outside of the outline polygon;

determining a second intersection of a second ray with the second projection circle, wherein the second ray starts at the second projection vertex and is directed along the normal to the particular outline-polygon edge, and wherein the second intersection is outside of the outline polygon; and

determining a particular exterior tangent that comprises a line segment between the first intersection and the second intersection, wherein the penumbra comprises the particular exterior tangent.

5. The method of claim 3, wherein determining the umbra comprises:

determining a particular outline-polygon edge of the outline-polygon edges, wherein the particular outline-polygon edge connects a first projection vertex to a second projection vertex, wherein the first projection vertex is associated with a first projection circle, and wherein the second projection vertex is associated with a second projection circle;

determining a centroid of the outline polygon;

determining a first intersection of a first ray with the first projection circle, wherein the first ray starts at the centroid of the outline polygon and is directed through the first projection vertex, and wherein the first intersection is inside of the outline polygon;

determining a second intersection of a second ray with the second projection circle, wherein the second ray starts at the centroid of the outline polygon and is directed through the second projection vertex, and wherein the second intersection is inside of the outline polygon; and

determining a particular interior tangent that comprises a line segment between the first intersection and the second intersection, wherein the umbra comprises the particular interior tangent.

6. The method of claim 1, further comprising:

determining a projection matrix, wherein the projection matrix is configured to determine a projection of at least a portion of a three-dimensional viewing volume onto the receiver surface, and wherein the viewing volume includes the light source and the occluding polygon;

determining an ambient-outline polygon by projecting the occluding polygon onto the receiver surface using the projection matrix, wherein the ambient-outline polygon comprises a plurality of ambient-outline vertices, and wherein each of the ambient-outline vertices corresponds to an occluding-polygon vertex;

for each ambient-outline vertex, determining an ambient-outline circle around the ambient-outline vertex; and

determining an ambient shadow of the occluding polygon based on exterior tangents to the ambient-outline circles that are outside of the ambient-outline polygon.

7. The method of claim 6, wherein providing the at least part of the shadow of the occluding polygon for display comprises providing at least part of the ambient shadow for display.

8. The method of claim 1, wherein providing the at least part of the shadow of the occluding polygon for display comprises providing at least part of the umbra and/or at least part of the penumbra for display.

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

10. The method of claim 1, wherein the occluding polygon is a user-interface element of a graphical user interface (GUI), and wherein providing the at least part of the shadow of the occluding polygon for display 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:

one or more processors; and

data storage configured to store at least executable instructions, wherein the executable instructions, when executed by the one or more processors, cause the computing device to perform functions comprising;

determining a light source configured to emit light, wherein the light source comprises a center point;

determining an occluding polygon between the light source and a receiver surface, wherein the occluding polygon comprises a plurality of occluding-polygon vertices connected by occluding-polygon edges;

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

for a particular occluding-polygon vertex in the plurality of occluding-polygon vertices, determining a projection vertex on the receiver surface based on a ray projected from the center point through the particular occluding-polygon vertex;

determining an outline polygon based on the projection vertex;

determining a projection circle around the projection vertex;

determining a penumbra of the shadow of the occluding polygon based on one or more exterior tangents to the projection circle that are outside of the outline polygon; and

determining an umbra of the shadow of the occluding polygon based on one or more interior tangents to the projection circle that are inside of the outline polygon; and

providing at least part of the shadow of the occluding polygon for display.

12. The computing device of claim 11, wherein determining the projection circle around the projection vertex comprises determining a radius for the projection circle based on a height of a corresponding occluding-polygon vertex above the receiver surface.

13. The computing device of claim 11, wherein the outline polygon comprises a plurality of projection vertices connected by outline-polygon edges, and wherein the plurality of projection vertices comprises the projection vertex.

14. The computing device of claim 13, wherein determining the penumbra comprises:

determining a particular outline-polygon edge of the outline-polygon edges, wherein the particular outline-polygon edge connects a first projection vertex to a second projection vertex, wherein the first projection vertex is associated with a first projection circle, and wherein the second projection vertex is associated with a second projection circle;

determining a normal to the particular outline-polygon edge;

determining a first intersection of a first ray with the first projection circle, wherein the first ray starts at the first projection vertex and is directed along the normal to the particular outline-polygon edge, and wherein the first intersection is outside of the outline polygon;

determining a second intersection of a second ray with the second projection circle, wherein the second ray starts at the second projection vertex and is directed along the normal to the particular outline-polygon edge, and wherein the second intersection is outside of the outline polygon; and

determining a particular exterior tangent of the exterior tangents that comprises a line segment between the first intersection and the second intersection, wherein the penumbra comprises the particular exterior tangent.

15. The computing device of claim 13, wherein determining the umbra comprises:

determining a particular outline-polygon edge of the outline-polygon edges, wherein the particular outline-polygon edge connects a first projection vertex to a second projection vertex, wherein the first projection vertex is associated with a first projection circle, and wherein the second projection vertex is associated with a second projection circle;

determining a centroid of the outline polygon;

determining a first intersection of a first ray with the first projection circle, wherein the first ray starts at the centroid of the outline polygon and is directed through the first projection vertex, and wherein the first intersection is inside of the outline polygon;

determining a second intersection of a second ray with the second projection circle, wherein the second ray starts at the centroid of the outline polygon and is directed through the second projection vertex, and wherein the second intersection is inside of the outline polygon; and

determining a particular interior tangent that comprises a line segment between the first intersection and the second intersection, wherein the umbra comprises the particular interior tangent.

16. The computing device of claim 11, wherein the functions further comprise:

determining a projection matrix, wherein the projection matrix is configured to determine a projection of at least a portion of a three-dimensional viewing volume onto the receiver surface, and wherein the viewing volume includes the light source and the occluding polygon;

determining an ambient-outline polygon by projecting the occluding polygon onto the receiver surface using the projection matrix, wherein the ambient-outline polygon comprises a plurality of ambient-outline vertices, and wherein each of the ambient-outline vertices corresponds to an occluding-polygon vertex;

for each ambient-outline vertex, determining an ambient-outline circle around the ambient-outline vertex; and

determining an ambient shadow of the occluding polygon based on exterior tangents to the ambient-outline circles that are outside of the ambient-outline polygon.

17. The computing device of claim 16, wherein providing the at least part of the shadow of the occluding polygon for display comprises providing at least part of the ambient shadow for display.

18. The computing device of claim 11, wherein providing the at least part of the shadow of the occluding polygon for display comprises providing at least part of the umbra and/or at least part of the penumbra for display.

19. The computing device of claim 11, 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 including a tangible computer-readable storage medium having instructions stored thereon that, in response to execution by one or more processors of a computing device, cause the computing device to perform functions comprising:

determining a light source configured to emit light, wherein the light source comprises a center point;

determining an occluding polygon between the light source and a receiver surface, wherein the occluding polygon comprises a plurality of occluding-polygon vertices connected by occluding-polygon edges;

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

for each occluding-polygon vertex in the plurality of occluding-polygon vertices, determining a projection vertex on the receiver surface based on a ray projected from the center point through the occluding-polygon vertex;

determining an outline polygon based on the projection vertex;

determining a projection circle on the receiver surface around the projection vertex;

determining a penumbra of the shadow of the occluding polygon based on one or more exterior tangents to the projection circle that are outside of the outline polygon; and

determining an umbra of the shadow of the occluding polygon based on one or more interior tangents to the projection circle that are inside of the outline polygon; and

providing at least part of the shadow of the occluding polygon for display.