Published in

SyncedReview

# A General Algorithm for Displaying Curved Patches

## The subdivision algorithm

1. How is the subdivision process terminated?
2. What happens to patches which do not cover a sample point?
3. What if a sub-patch intersects the edge of the screen or is behind the eye?
4. How many times must a patch be sub-divided?
5. What problems may result from discrete sampling?

# Sub-dividing a Cubic Curve

• Consider the cubic: f(t) = a x t³ + b x t² + c x t +d. The problem is to determine f(t) when f(t-h) and f(t+h) are known,
• where f(t+h) = a x (t+h)³ + b x (t+h)² + c x (t+h) x d, and f(t-h) = a x (t-h)³ + b x (t-h)² + c x (t-h) x d,
• where f(t-h) + f(t+h) can be calculated to be 2 x f(t) + 2 x (h² x ( 3 x (a x t +b) ) ),
• the midpoint is then f(t) = ( f(t-h) + f(t+h) )/ 2 — h² x ( 3 x (a x t +b) ).
• Let g(t) = h² x ( 3 x (a x t +b) ) be the mid point at t,
• then g(t-h) = h² x ( 3 x (a x (t-h) +b) ) and g(t+h) = h² x ( 3 x (a x (t+h) +b) ),
• calculating g(t-h) + g(t+h) = 2 x g(t),
• thus, g(t) = ( g(t-h) + g(t+h) ) /2 .
• f(t) = ( f(t-h) + f(t+h) )/ 2 — ( g(t-h) + g(t+h) ) /2.

# Extending Cubic Sub-division to Surfaces

1. the midpoints of each of the edges (sides) of the patch,
2. the midpoint of the patch itself.

# The Hidden Surface Problem

## A high-level description of the Z-buffer algorithm

• Scanline algorithm: Works on a row-by-row basis rather than a polygon-by-polygon or pixel-by-pixel basis.
• Warnock’s algorithm: Recursive subdivision of a screen until areas are obtained that are trivial to compute. Mostly used as a base for other algorithms, and is very parallel friendly.
• Painter’s algorithm: Sorts all the polygons in a scene by their depth and then paints them in this order, farthest to closest. Mostly used for (simple) video games.
• Ray tracing algorithm: Essentially geometric objects and physics done backwards. Imagine simply reversing the path that a light ray took to get to your eye, tracing it back to the source (or vice versa).

## A high-level description of the modified Newell algorithm

• Sort polygons into furthest minimum Z-order to nearest,
• For each polygon, check other polygons it may overlap with,
• See if any of the polygons are behind the polygon being tested,
• If so, move this polygon behind it,
• Split overlapping polygons into smaller pieces and repeat the above steps with each partition.

# Intensity, Sampling, Rastering, and Aliasing

## Intensity

• Calculate the intensity with the normal (orthogonal) to the surface,
• Define some intensity function to calculate the intensity,
• map the intensity values from some picture,
• modify existing intensities for shadow or transparency

## Sampling, Rastering, and Aliasing

• Pre-filtering: treats pixels as an area, and computes pixel colour based on the overlap of the scene’s objects with a pixel’s area
• Post-filtering: renders the scene at higher resolution, and computes the pixel value by a (weighted) average of the subpixels (supersampling)

# Concluding Remarks

--

--

## More from SyncedReview

We produce professional, authoritative, and thought-provoking content relating to artificial intelligence, machine intelligence, emerging technologies and industrial insights.

## Synced

29K Followers

AI Technology & Industry Review — syncedreview.com | Newsletter: http://bit.ly/2IYL6Y2 | Share My Research http://bit.ly/2TrUPMI | Twitter: @Synced_Global