# CMSC 451 University of Maryland Dynamic Programming Discussion

Description

4 attachmentsSlide 1 of 4attachment_1attachment_1attachment_2attachment_2attachment_3attachment_3attachment_4attachment_4

Unformatted Attachment Preview

There are two important aspects of dynamic programming which are
(1) breaking a problem into smaller parts and (2) storing or
“memoizing” results/calculations to avoid redundant work. While
common examples are often optimization to recursive solutions, the
above two concepts can be applied to many things, and I present
a real-world implementation.
Instead saying “memoizing”, I believe a more common term is
simply caching. Large programs (and computers in general) cache
many different things to save on redundant work and it is no different
here. For my example of dynamic programming, I will describe how I
have used it for calculating shadow and lighting when rendering
graphics.
Without Dynamic Programming
First a quick description of how shadow and light could be calculated
without the aid of dynamic programming. Consider a scene of various
geometry and an array of lights with various properties set.
1. Set a shadow render target
2. Render all shadows cast from the geometry based on the lights
position
3. Set a scene render target
4. Bind any material, normal, and color data
calculation
6. Repeat for all lights
To break down the cost of this the texture sampling is the most
expensive operation. That is where for each fragment that light is
drawn to, the shadow and other texture data must be read. In the
above that would mean a sample rate of 4 per fragment, per
light. Fragments are a bit different than “just pixels”, but for simplicity
let’s say it is 1-to-1 at a resolution of 1920×1080. That means 2,073,600
fragments, and a total sample rate per light of 8,294,400. I stress per
light because the following exposes how costly that is.
With Dynamic Programming
So, how could dynamic programming break this down into smaller
problems while caching as much information as possible to save on
work?
1. Set a shadow render target
2. Render a batch of shadow data at a single time (**explained later)
3. Set material, normal, and color render targets
4. Render all three at once
5. Set a scene render target
6. Bind the three textures from step 3 and the shadow data
7. Render the entire batch of lights at once while reading the
Looking at the sample rate now it is still 8,294,400, but for
as many lights as can be fit into a single batch–or no longer per
light. At a minimum that would be 32 with the red, green, blue, and
alpha (RGBA) of a texel set at 1 byte each. The first algorithm would
cost 265,420,800 samples to render 32 lights, but with caching and
breaking things apart into smaller steps (shadow, materials, and final
render) the difference is vast. This keeps the sample rate at a constant
4 as long as the scene manages to only use 32 or less lights a time. For
reference, a sample rate of 4 is average for a common mobile device
with graphics capabilities. Using only 2 lights in the non-dynamic
solution would double that.
Rendering an entire batch of shadow data into a texture at once is my
own solution which I have developed. I mentioned the number of
bytes in a texel, because the key is packing corresponding shadow
values into the separate bits of the RGBA. Each light is given an index 1
– 32, and when all lights render in a batch the index is used with a
bitwise operation to flip the corresponding bit. Then later when the
light is rendered the same indexed light can unpack that same bit with
another bitwise operation to determine where shadows should be. At
the cost of memory it is possible to use texels with more than 32 bits
each.
Another important step when rendering the shadow bits is to use
depth testing with “equal to” comparison. This is to prevent a single
light index from casing overlapping shadows upon itself which would
ruin the entire process.
If we take a peek at what this bitwise shadow map looks like after
compiled it is the following:
Captured on the exact same frame as that shadow map is the final
In the images only a few lights are being rendered, and use the green
channel alone to pack bits. This is on purpose just for the example
images because it would be hard to make out any corresponding
shapes if all 32 bits were in use–although the computer would have no
The second pseudo-code steps above are referred to as a type deferred
reduce the problem size and cache more data at once than the normal
deferred rendering pipeline.
If you are curious how deferred rendering works, here is an
images on the left where I break about the cached data to show it for
example purposes. It too is an example of breaking up an entire job
into smaller steps where data is cached. In this case it is called a gbuffer which stores information for later use.

attachment

6 Pages

Tags:
programming

computer

Dynamic

User generated content is uploaded by users for the purposes of learning and should be used following Studypool’s honor code & terms of service.

## Reviews, comments, and love from our customers and community:

### Article Writing

Keep doing what you do, I am really impressed by the work done.

Researcher

### PowerPoint Presentation

I am speechless…WoW! Thank you so much!

#### Stacy V.

Part-time student

### Dissertation & Thesis

This was a very well-written paper. Great work fast.

Student

### Annotated Bibliography

I love working with this company. You always go above and beyond and exceed my expectations every time.

Student

### Book Report / Review

I received my order wayyyyyyy sooner than I expected. Couldn’t ask for more.

Student

### Essay (Any Type)

On time, perfect paper

Student

### Case Study

Awesome! Great papers, and early!

#### Kaylin Green

Student

Thank you Dr. Rebecca for editing my essays! She completed my task literally in 3 hours. For sure will work with her again, she is great and follows all instructions

Researcher

### Critical Thinking / Review

Extremely thorough summary, understanding and examples found for social science readings, with edits made as needed and on time. Transparent

Customer

Perfect!

Student