Method, system, and computer program product for visibility culling of terrain

• US 20020135591A1
• Filed: 08/08/2001
• Published: 09/26/2002
• Est. Priority Date: 02/09/2001
• Status: Active Grant

• Current Assignee: Activision Publishing Incorporated (Microsoft Corporation)
• Original Assignee: Intrinsic Graphics, Inc.
• Inventors: Zhang, Hansong
• Granted Patent: US 7,027,046 B2
• Time in Patent Office: Days
• US Class Current: 345/582
• CPC Class Codes: G06T 15/40 Hidden part removal
• CPC Class Codes: G06T 17/05 Geographic models

Abstract

A method, system, and computer program product are provided for visibility culling of terrain. A height field is perspective modulated. An occlusion height field is generated based on an orthographic height propagation of the perspective modulated height field. Graphics data is culled based on the generated occlusion height field. Texturing and blending operations can be used to accelerate the perspective modulation. A perspective modulation disk is used to modulate the first height field along radial slices from a viewpoint. Texture from a one-dimensional texture with distance values is mapped to the radial slices to obtain the perspective modulated height field. Generating an occlusion height field can also be carried out using texturing and blending and can be hardware-accelerated. According to a further feature, a shift disk or shift texture is used.

Claims

1. A method for visibility culling, comprising:

(A) modulating a first height field as a function of distance to obtain a perspective modulated height field; and

(B) generating an occlusion height field based on an orthographic height propagation of the perspective modulated height field.

2. The method of claim 1, further comprising:

(C) culling graphics data based on the occlusion height field generated in step (B).

3. The method of claim 1, wherein said step (A) comprises modulating the first height field as an inverse function of distance to obtain the perspective modulated height field.

4. The method of claim 1, wherein said step (A) comprises modulating the first height field as an inverse function of distance scaled by a scaling factor to obtain the perspective modulated height field.

5. The method of claim 1, wherein said step (A) includes mapping texture from a one-dimensional texture, the one-dimensional texture having a set of texels addressed by a set of texture coordinates and wherein values of the set of texels are an inverse function of the respective set of texture coordinates.

6. The method of claim 1, wherein said step (A) comprises:

drawing a perspective modulation disk of radial slices on top of the first height field centered at a viewpoint V; and

mapping texture from a one-dimensional texture to obtain the perspective modulated height field.

7. The method of claim 6, wherein said step (A) further comprises blending texels mapped from the one-dimensional texture and corresponding samples in the first height field to obtain the perspective modulated height field.

8. The method of claim 1, wherein said step (B) comprises:

(i) comparing height values of the perspective-modulated height field at first and second sample locations separated by a propagation distance d, the first location being closer to the viewpoint than the second location; and

(ii) updating the height value of the second location with the greater height value determined in said comparing step.

9. The method of claim 8, wherein said step (B) comprises a series of iterations, wherein said steps (i) and (ii) are performed for multiple sampling locations along the lengths of the radial slices, and wherein the incremental distance between two sampling locations is fixed throughout the series of iterations.

10. The method of claim 8, wherein said step (B) comprises a series of iterations, wherein said steps (i) and (ii) are performed for multiple sampling locations along the lengths of the radial slices, and wherein the incremental distance between two sampling locations is varied throughout the series of iterations.

11. The method of claim 1, wherein the first height field is stored as a first height field texture and the perspective modulated height field is stored in a color channel of a frame buffer, said step (B) comprises:

drawing a first shift disk including texture mapping texels from the first height field texture; and

blending the texture mapped texels and the color values of the perspective modulated height field stored in the color channel of the frame buffer to obtain an updated shift disk, the updated shift disk having updated color values representing the updated height values based on a maximum comparison and texture coordinates shifted by an incremental distance.

12. The method of claim 1, wherein the perspective modulated height field is drawn in a first texture, and a dependent shift texture stores a set of texture coordinates, said step (B) comprises:

drawing a first shift disk including performing a per-pixel texture operation to shift texture coordinates in the dependent shift texture by an incremental distance along radial directions from a viewpoint; and

blending the texture mapped texels and the color values of the perspective modulated height field stored in the color channel of the frame buffer to obtain an updated shift disk, the updated shift disk having updated color values representing the updated height values based on a maximum comparison and texture coordinates shifted by an incremental distance.

13. The method of claim 1, further comprising, prior to said step (A), the step of subtracting a height value at a viewpoint from each height sample in an original height field to obtain the first height field.

14. The method of claim 1, wherein said steps (A) and (B) are accelerated in hardware.

17. The system of claim 16, further comprising:

(C) culling means for culling graphics data based on the occlusion height field generated in step (B).

19. The system of claim 18, wherein the graphics subsystem includes a texture mapping unit and a blending unit, and wherein the visibility culling controller controls the texture mapping unit to modulate a first height field as a function of distance to obtain a perspective modulated height field and controls the texture mapping unit and the blending unit to generate the occlusion height field based on an orthographic height propagation of the perspective modulated height field.

20. The system of claim 19, wherein the texture mapping unit and the blending unit carry out processing operations in hardware such that the texture mapping unit modulates a first height field as a function of distance to obtain a perspective modulated height field in a processing operation implemented at least in part in hardware and the texture mapping unit and the blending unit generate the occlusion height field based on an orthographic height propagation of the perspective modulated height field in another processing operation implemented at least in part in hardware.

15. A routine for hardware-accelerated visibility culling, comprising:

drawing an original height field to obtain a first image in a frame buffer color channel;

drawing a polygon of the same size as the domain of a height field with a constant color representative of the height at a viewpoint to obtain a second image in the frame buffer, said drawing including blending to subtract the polygon color from the first image frame buffer color, such that a polygon having a color equal to a viewpoint reference height field is stored as the second image in the frame buffer, the reference height field being equal to the original height minus the constant color height;

drawing a perspective modulation disk, including texture mapping with a first texture addressed by a first set of texture coordinates, blending to modulate the second image frame buffer color channel value by the texels in the first texture, and storing a resultant perspective modulated image as a second texture addressed by a second set of texture coordinates, wherein the first texture includes a one-dimensional array of texels having values which are a function of the first set of texture coordinates, and the second texture includes a two-dimensional array of texels having values which represent a perspective modulation of the viewpoint reference height field; and

for each propagation,

modifying a shift disk to shift texture coordinates by a respective propagation distance; and

drawing an updated shift disk with texture mapped from the second texture, including blending with a maximum blending function that saves a maximum height value between two compared sampling locations along radial directions on the shift disk.

16. A system for visibility culling, comprising:

(A) modulating means for modulating a first height field as a function of distance to obtain a perspective modulated height field; and

(B) generating means for generating an occlusion height field based on an orthographic height propagation of the perspective modulated height field.

18. A system, comprising:

a host computer; and

a graphics subsystem coupled to the host computer;

wherein the host computer includes a visibility culling controller that controls the graphics subsystem to modulate a first height field as a function of distance to obtain a perspective modulated height field and to generate an occlusion height field based on an orthographic height propagation of the perspective modulated height field.

21. A system, comprising:

a visibility culling controller that controls a graphics subsystem to modulate a first height field as a function of distance to obtain a perspective modulated height field, and to generate an occlusion height field based on an orthographic height propagation of the perspective modulated height field.

22. The system of claim 21, wherein the graphics subsystem carries out processing operations in hardware such that modulation of the first height field as a function of distance to obtain a perspective modulated height field is carried out in a processing operation implemented at least in part in hardware and generation of the occlusion height field based on an orthographic height propagation of the perspective modulated height field is carried out in another processing operation implemented at least in part in hardware.

27. The system of claim 26, wherein the graphics pipeline comprises an OPENGL graphics pipeline.

23. A visibility culling controller, comprising:

first control logic that enables a graphics subsystem to modulate a first height field as a function of distance to obtain a perspective modulated height field; and

second control logic that enables a graphics subsystem to generate an occlusion height field based on an orthographic height propagation of the perspective modulated height field.

24. A computer program product comprising a computer useable medium having computer program logic recorded thereon for enabling a processor to render a computer scene, said computer program logic comprising:

first computer readable code that enables a processor to modulate a first height field as a function of distance to obtain a perspective modulated height field; and

; and

second control logic that enables a processor to generate an occlusion height field based on an orthographic height propagation of the perspective modulated height field.

25. A visibility culling controller, comprising:

first control logic that modulates a first height field as a function of distance to obtain a perspective modulated height field; and

second control logic that generates an occlusion height field based on an orthographic height propagation of the perspective modulated height field.

26. A system, comprising:

a visibility culling controller;

a first height field; and

a graphics pipeline;

wherein, in response to the visibility culling controller, the graphics pipeline carries out operations in multiple passes to modulate the first height field as a function of distance to obtain a perspective modulated height field, and to generate an occlusion height field based on an orthographic height propagation of the perspective modulated height field.