[SOLVED] CS data structure algorithm Java CS580

CS580

CS580
Computer Graphics Rendering
Overview
Ulrich Neumann

What Will be Covered?

Image package
Photoshop

CAD package

Graphics Design

Applications

Computer Graphics
Auto CAD
Modeling package
3D Studio Max

Animation package
Flash, Digimation

3D Graphics

Video

Virtual
Reality
Animation
Visualization

Movie
Effects

Games
Algorithms
Research

Web Design

*
Talk about different requirements for real-time vs. Non-real-time

Time, quality

Target Course Audience

Application programmer
Use a library (OpenGL, Java)
What does the call do?
Build graphics apps

Graphics developer
Create or extend a library for others to use
How does the function work?
Design and create a function to do X

*

Introduction to CG

Computer Graphics

The technology to convert created or collected data into visual representations

Model
Render focus of this course
Display

*

CS580 Course Structure

Core rendering algorithms
Advanced topics
Term Project
per team
HW 1
HW 2
HW 3
HW 4
HW 5
HW 6
Exam 1
Exam 2

Graphics Process
Rendering
Transform, Light, Shade, & Rasterize
Surface Model
Image Display
Geometric Model
Scene Model

64.bin

Geometry Modeling
There are many ways to describe or represent geometry
Explicit geometry:

Triangle meshes, Patches, Subdivision surfaces,
Implicit geometry:

Sphere surface defined by x2 + y2 + z2 = 10
Fractal sets, procedural definition,
Volume data:

Samples from MRI, ultra-sound, simulation

Example of Triangle Meshes

65.psd

66.unknown

Making Geometric Models
Rendering
3D scanner
Computer vision
Model libraries
Interaction

Geometric Modeling
Points, Lines, Surfaces,

Making Surface (Appearance) Models
Rendering
Scanner
Paint
Image libraries
Camera

Surface Parameters
Color, BRDF, Opacity,

Rendering
Rendering
Transformation
Lighting and Shading
Scan Conversion or Rasterization
Surface Model
Geometric Model

+
=
Image Display

70.bin

71.bin

72.bin

Image Display
scene models and rendering algorithms
Image representation in memory devices
display device
Rendering
Image Representation
Pixel array,
Stroke list, NC cut list,

Optical Modulation
CRT, LCD, Plasma, Ink, 3D fab

Digital Images: pixels

*

76.bin

77.bin

78.bin

Frame Buffer
Frame Buffer
A block of dedicated memory, that contains the pixel data that is passed to the display system
Data for each pixel encodes color and/or other properties (e.g., opacity)

Frame Buffer Concepts

Pixel:One element of a frame buffer
a uniquely addressable point in an image
Pixel depth:Number of bytes per-pixel in the buffer
e.g., 8-bits (1 byte) for each of
RGBA (Red, Green, Blue, Alpha) = 4 bytes/pixel
Resolution:Width Height (in pixels)
e.g., 640480, 12801024, 19201080, 38402160
Buffer size:Total memory allocated for frame buffer
width height pixel depth

Frame Buffer Z Value
A Z-buffer is required by a popular algorithm for solving the hidden-surface removal (HSR) problem
Think of the pixel Z value as the distance from the camera to the surface seen in that pixel
Each pixel holds a Z value in addition to color and alpha
Often, Z-values at pixels are a 32-bit signed integer (4 bytes)
More details when we get to hidden surface removal lectures and HW2

Note that pixels in the FB can also hold other intermediate calculation values in addition to color and Z values
Leads to deep pixels whole data structures per pixel

How Much Frame Buffer Memory?
Frame Buffer Size = Width Height Depth
Width Height = the image resolution (# of pixels)
Depth is the amount of data stored at each pixel (# of bytes)

For example:
Let width=640 and height=480 (a common small image size for webcams)
Let each pixel hold 24-bits of color (8-bits for each of R, G, B)
Let alpha be an 8-bit value and let Z be 32-bits

Then: Frame Buffer Size = 640 480 (24 + 8 + 32 bits)
= 640 480 64 bits = 640 480 8 bytes
= 2,457,600 bytes

Display Devices

CRT (Cathode Ray Tube),
LCD (Liquid Crystal Displays), Plasma, Projection, HMD, Volumetric 3D, Stereo,

Important Parameters:
size, resolution, field of view, pixel-pitch, color range, brightness, refresh-rate, black level, update mode (e.g., interlaced), distortion,

*

Applications: Movie Effects

Jurassic Park
Three Academy Awards for its ground-breaking visual and sound effects
Geris Game
Academy Award-winning of the best animated short film, 1997.

Games

Visualization

Simulation

83.bin

Medical Visualization

84.bin

Engineering

Immersion

Virtual Reality
Augmented Reality
Natural Interaction

HW 1
Display functions (due 1 week) (~1 hr)
Browse.h, .c, and .cpp files of HW1.zip
You only need to fill in functions of rend.cpp

Data Application Renderer Display
Start by building display functions
Work backwards so you always see an output

hw1.txt (1)
During the course of the assignments, you will build a small but usefulgraphics library.Well call it the Gz library, and all functions, vars, etc, will be named accordingly.

Certain standards will apply to make the code interfaces consistent.Consistency will be established by prepared include files and an Application Program Interface (API).

The include files you need for this assignment are Gz.h and rend.h.
Both of these are found in the zip file HW1.zip.

There are several other files there that may be useful.

rend.cppYour task for this assignment is to flesh out the functions in rend.cpp and compile and execute the complete app.

Application.cpp Defines pointers for renderer and frame buffer.Just use this module do not change it.

Application1.cppThis application is complete and calls the display functions you will write.Browse it and understand it.Dont modify it, just use it.

rectsA data file used by Application1.You should be able to figure it out.

output_sample.ppm A ppm-format result image which can be viewed with Irfanview.A similar file should be created by running your HW1 code.Your background color may vary from the sample.

hw1.txt (2)

All displays are addressed by pixel coordinates, and accept or return pixel values.Upper left pixel is (x=0, y=0).x increases to the right, and y increases downward (raster order).

A flush operation writes the accumulated pixels to a disk file.Disk files will be in the ppm file format.A ppm file has an ascii header with xs and ys image-dimensions and a binary 3-byte pixel format:

P6 xs ys 255r
rgbrgbrgbrgb

A sample ppm header is:P6 512 480 255r.This would be correct for an image with 512 pixels horizontally and 480 pixels vertically.
DownloadIrfanView for viewing PPM files (many others work too)

The flush operation also copies the display pixels to the screen framebuffer note these pixels are written in bgr-order.See the code comments for details.

Renderer objects hide the organization of pixel memory and its allocation from the application and renderer.In HW1, only the application creates, frees, and flushes the Renderer.The renderer buffer size is determined by the application.
The number of pixels in the GzRender frame buffer should be same as the number of pixels in the GzRender pixel buffer.
Pixels are written by using the Put call.Defining the API interfaces makes the Application and Renderer library display-device independent.
See the rend.cpp file for a complete description of the API

Application1 Pixel Drawing

some initialization
then read input file and draw pixels into display buffer

intulx, uly, lrx, lry, r, g, b;
while( fscanf(infile, %d %d %d %d %d %d %d,
&ulx, &uly, &lrx, &lry, &r, &g, &b) == 7) {
for (j = uly; j <= lry; j++) {for (i = ulx; i <= lrx; i++) {m_pRender->GzPut(i, j, r, g, b, 1, 0);
}
}
}

m_pRender->GzFlushDisplay2File(outfile); /* write out display pixels to ppm file*/
m_pRender->GzFlushDisplay2FrameBuffer();// write out or update display pixels to MS Windows frame buffer

Gz.h

/*universal constants */
#define GZ_SUCCESS0
#define GZ_FAILURE1

#define RED 0/* array indices for color vector */
#define GREEN1
#define BLUE 2

#define X 0/* array indices for 3D vectors */
#define Y 1
#define Z 2

#define U 0/* array indices for texture coords */
#define V 1

/**********************/
/* Boundary constants */
#defineMAXXRES1024/* put bound on size in case of error */
#defineMAXYRES1024

Gz.h

/* Types and Structures used by the renderer */

typedef void*GzPointer;
typedef float GzColor[3];
typedef short GzIntensity;
/* 0-4095 in lower 12-bits of 16-bit short allocated for each RGBA component */
typedef intGzDepth;/* signed int z for clipping */

#ifndef GZ_PIXEL
typedefstruct {
GzIntensityred;
GzIntensitygreen;
GzIntensityblue;
GzIntensityalpha;
GzDepth z;
} GzPixel;
#define GZ_PIXEL
#endif;

Note:
Pixel structure holds everything we need in the frame buffer

Do bounds checking and logical correction or error management of
xres, yres (image size)
GzIntensity (RGB values)

rend.cpp (1)

GzRender::GzRender(int xRes, int yRes)
{
/* HW1.1 create a MS Windows frame buffer
allocate memory for 3 bytes(B,G,R) per-pixel atindicated resolution
Use as startup initialization for all HW */
}

GzRender::~GzRender()
{
/* HW1.2 clean up, free buffer memory */
}

int GzRender::GzDefault()
{
/* HW1.3 set pixel buffer to some default values */
Start of frame initialization for all HW
return GZ_SUCCESS;
}
int GzRender::GzPut(int i, int j, GzIntensity r, GzIntensity g, GzIntensity b, GzIntensity a, GzDepth z)
{
/* HW1.4 write pixel values into the buffer */
return GZ_SUCCESS;
}

int GzRender::GzGet(int i, int j, GzIntensity *r, GzIntensity *g, GzIntensity *b, GzIntensity *a, GzDepth *z)
{
/* HW1.5 retrieve a pixel information from the pixel buffer */
return GZ_SUCCESS;
}

rend.cpp (2)

int GzRender::GzFlushDisplay2File(FILE* outfile)
{
/* HW1.6 write image to ppm file P6 %d %d 255r */

return GZ_SUCCESS;
}

int GzRender::GzFlushDisplay2FrameBuffer()
{
/* HW1.7 write pixels to framebuffer:
put the pixels into the MS Win frame buffer
CAUTION: when storing the pixels into the frame buffer, the order is blue, green, and red
NOT red, green, and blue !!!
*/

return GZ_SUCCESS;
}

rects
1050200320320043203254
3005551144490042002189
-100222600270333322122121
222-5027058843218341898
250250400500218012095333
10020030030040005000444
47018099999941002030620
-100-1004015020010003000
Output image
PPM file format has an ascii header

followed by 8-bit binary pixel color values
in raster order (UL to LR)

For example:
P6 256 256 255
RGBRGBRGB.
Produces a 256256 image

Note that background color is your choice it doesnt have to match this image

HW1 pitfalls
Bounds check the parameters passed to the display functions
pixel coords ignore off-screen coordinate commands
pixel GzIntensity values clamp to 0-4095 within 16-bit short
Both Flush commands requires conversion of GzIntensity to 8-bit rgb componentbytes
Drop LS 4-bits by right-shifting and then use low byte of GzIntensity value

15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0
0
0
0
0
a
b
c
d
e
f
g
h
i
j
k
l
0
0
0
0
0
0
0
0
a
b
c
d
e
f
g
h
GzIntensity is a 16 bit signed short
We allow a range of 12-bits (0-4095) for valid values.Upper 4-bits are always zeros.
We convert to 8-bits (0-255) for required PPM (or screen) format.Right shift 4-times with zero-fill
Final 8-bit unsigned color (rgb) is created by casting (copy) to an unsigned char
a
b
c
d
e
f
g
h