3D object representations

Polygon surfaces-polygon tables-plane equations-polygon meshes

Object descriptions are stored as sets of surface polygons

The surfaces are described with linear equations

Polygon table

data is placed into the polygon table for    processing

Polygon data table can be organised into two groups

  geometric table

attribute table

Quadric surfaces-sphere-ellipsoid-torus

Described with second degree eqns.

Ex. Sphere,ellipsoids,tori,paraboloids,hyperboloids

Sphere

     A spherical surface with radius ‘r’ centered on the coordinate origin is defined as a set of points(x,y,z) that satisfy the equation

           x2  +  y2  +  z2  =  r2

In parametric form,

                        x  =  r CosΦCosΘ

                        y   = r Cos ΦSinΘ

                        z   = r Sin Φ 

Blobby objects-definition and example

            Don’t maintain a fixed shape

            Change surface characteristics in certain motions

Ex. Water droplet, Molecular structures

                f(x,y,z) = Σk b ke-ak rk2  - T = 0

     r = √x2 + y2 + z2

       T  =some threshold

      a,b used to adjust the amount of bloobiness.

   Spline-representation-interpolation

           it is a composite curve formed with polynomial pieces satisfying a specified continuity conditions at the boundary of the pieces

Bezier curves

       can be fitted to any no. of control points

       degree of bezier polynomial is determined by the number of control points and their relative position

Bezier curve is specified by

      Boundary conditions

      Characterising matrix

            Blending function

DIGITAL DIFFERENTIAL ANALYZER (DDA) ALGORTIHM

Algorithm

#define ROUND(a) ((int)(a+0.5))

voidlineDDA (int xa, int ya, int xb, int yb)

 {

int dx = xb - xa, dy = yb - ya, steps, k;

floatxIncrement, yIncrement, x = xa, y = ya;

if (abs (dx) > abs (dy) steps = abs (dx) ;

else steps = abs dy);

xIncrement = dx / (float) steps;

yIncrement = dy / (float) steps

setpixel (ROUND(x), ROUND(y) ) :

for (k=0; k<steps; k++)

{

x += xIncrement;

 y += yIncrement;

setpixel (ROUND(x), ROUND(y));

}

}

Algorithm Description:

Step 1 :Accept Input as two endpoint pixel positions

Step 2: Horizontal and vertical differences between the endpoint positions are assigned to parameters dx and dy (Calculate dx=xb-xa and dy=yb-ya).

Step 3:The difference with the greater magnitude determines the value of parameter steps.

Step 4 :Starting with pixel position (xa, ya), determine the offset needed at each step to generate the next pixel position along the line path.

Step 5: loop the following process for steps number of times

a. Use a unit of increment or decrement in the x and y direction

b. if xa is less than xb the values of increment in the x and y directions are 1 and m

c. if xa is greater than xb then the decrements -1 and – m are used.

Ray Tracing / Ray Casting

Tracing / Ray Casting

- Provides a related , powerful approach to render scenes

Overview of Ray Tracing Process

Pseudo code of a ray tracer:

  for(int r = 0; r <nRows ; r++)

  for(int c = 0; c <nCols ; c++)

            {

1.                   build the rc-th ray

2.                   find all intersections of the rc-th ray with objects in the scene

3.                  Identify the intersection that lies closest to and in front of the eye

4.                  Compute the hit point where the ray hits this object and the normal vector at that point

5.                  Find the color of the light returning to the eye along the ray from the point of intersection

6.                   place the color in the rc-th pixel

}                                 

Intersection of a Ray with an Object

Common shapes used in ray tracing

§     Sphere

§     Cylinder

§     Cone cube

§     hex cone

If ‘S’ is the starting point of a ray and ‘c’ is its direction then the ray that intersects with a shape is given by

  r(t) = S + ct         // implicit form of shape is F(P)

Condition for r(t) to coincide with a point of the surface is

  F(r(t)) = 0

The hit time t_hit  can be found by solving

  F(S+ c t_hit ) = 0

Intersection of a Ray with the Generic Plane

§      generic plane – xy plane or z = 0

§     Implicit form is F(x ,y , z) = z

§     The ray S+ct intersects the generic plane when

            S_z +c_zt_h = 0 , where t_h = - ( S_z  /  c_z )

If c_z = 0 , the ray is moving parallel to the plane & there is no intersection

Otherwise , the ray hits the plane at the point P_hit = S – c(S_z / c_z )

Intersection of a Ray with the Generic Shape

§     Consider a generic shape whose implicit form is F(P) = |P|² – 1

§     The point of intersection of the ray is given by |S + ct |²   - 1 = 0

  |c|²T² + 2.(S.C)t + (|S|² - 1) = 0   which is of the form At²  +2Bt + c = 0

by solving   t_h = -(B/A) ±(√B² – AC)/ A

ü    If B²  - Ac is ‘-’ ve , the ray misses the sphere

ü    If B²  - Ac  is zero , the ray grazes the sphere at one point

ü    If B²  - Ac is ‘+’ ve , there are 2 hit times t₁& t₂

creation of images by iterated functions

1.                  Experimental copier

—                 Take an initial image I₀

—     Produce new image I₁ by superimposing several reduced versions of I₀

—     Feed I₁ back to the copier to generate I₂

—     Repeat the process to obtain a sequence of images I_0, I_1, I_2,… called orbit of I₀

2.S-copier

-                      Superimposes three smaller versions of whatever image is fed onto it and repeated iterations may result in Sierpinski triangle

Generating images

—     The 3 lenses present in the copier reduces the i/p image to one half of its size and moves it to a new position

—     The reduced and shifted images are superimposed on printed o/p

—     Each lens performs its own affine transformation

IFS – it is a collection of ‘N’ affine transformations T_i  for I = 1,2,…N         

Theory of copying process

Method:

-                      Using the lenses present in the copier draw the o/p image by transforming the points present in the i/p image

Working:

 Let I be the i/p image to the copier, then the i-th lens builds the new set of points denoted by  T_i (I) and adds them to the image being produced at the current iteration.

The o/p image is obtained by superimposing the three transformed images created by the three lenses

                        o/p image = T₁(I) U  T₂(I) U T₃(I)

Overall mapping from i/p to o/p is denoted by W(.)

                        W(.) = T₁(.) UT₂(.) UT₃(.)

Drawing the  k-th iterate

Choices of Initial images ( I₀ )

1.                  Polyline

2.                  Single point

Chaos Game ( Random Iteration Algorithm)

•                produces the picture of an attractor

•                produces pictures in a non recursive way

Ex. Sierpinski gasket