Friday, April 13, 2012

visible surface detection z-buffer algorithm in computer Graphics sample source code

This article is extension of my previous articles Projecting a 3D world co-ordinates into 2D perspective where I have drawn wireframe cube in perspective view. If we want to draw a solid object then we must decide the visible surface to render. The surface/object which we render at last that will display on screen irrespective of depth and can overwrite the nearest surface/object. So, we must implement the special method to find  out the visible surface and one of them is z-buffer method.
z-buffering is the management of image depth coordinates in three-dimensional (3-D) graphics, usually done in hardware, sometimes in software. It is one solution to the visibility problem, which is the problem of deciding which elements of a rendered scene are visible, and which are hidden. The painter's algorithm is another common solution which, though less efficient, can also handle non-opaque scene elements. Z-buffering is also known as depth buffering.
When an object is rendered, the depth of a generated pixel (z coordinate) is stored in a buffer (the z-buffer or depth buffer). This buffer is usually arranged as a two-dimensional array (x-y) with one element for each screen pixel. If another object of the scene must be rendered in the same pixel, the method compares the two depths and chooses the one closer to the observer. The chosen depth is then saved to the z-buffer, replacing the old one. In the end, the z-buffer will allow the method to correctly reproduce the usual depth perception: a close object hides a farther one. This is called z-culling.



Z-Buffer Algorithm:
Given: A list of polygons {P1,P2,.....Pn}
Output: A COLOR array, which displays the intensity of the visible polygon surfaces.
Initialize:
          note : z-depth and z-buffer(x,y) is positive........
                z-buffer(x,y)=max depth; and
                COLOR(x,y)=background color.

Begin:
      for(each polygon P in the polygon list) do{
         for(each pixel(x,y) that intersects P) do{
             Calculate z-depth of P at (x,y)
             If (z-depth < z-buffer[x,y]) then{
                  z-buffer[x,y]=z-depth;
                  COLOR(x,y)=Intensity of P at(x,y);
            }
         }
      }
  display COLOR array.

Here l will show you how to  implement it  in programming. Only few classes  is added to implement it on my previous article Projecting a 3D world co-ordinates into 2D perspective.Object is drawn by each pixel plot and fastest method is implement for pixel plot as in this articles Fastest method of pixel plot.
To find the depth of the polygon surfaces we must store the co-efficient of polygon.We can find the coefficient by solving equation of  three sides of polygon.Source code for storing co-efficient of polygon is given below.


Coefficient_Of_Polygon.cs


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace Graphics3Dto2D
{
    class Coefficient_Of_Plane
    {
        public double A, B, C, D;
        public Coefficient_Of_Plane()
        {
        }
            A = B = C = D = 0;
    }
}



Calculating the depth of polygon and checking  a pixel position (x,y) inside the polygon is done in another module.Source code is given below:

DepthBuffer.cs


using System;
using System.Collections.Generic;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
 
namespace Graphics3Dto2D
{
    class DepthBuffer
    {
 
        public Coefficient_Of_Plane COPLANE;
        public DepthBuffer()
        {
            COPLANE = new Coefficient_Of_Plane();
        }
        public Coefficient_Of_Plane Coefficient_Value(_3Dpoint pt1, _3Dpoint pt2, _3Dpoint pt3)
        {
           // double Y = 0;
            Coefficient_Of_Plane pt;
            pt = new Coefficient_Of_Plane();
            pt.A = (pt2.z - pt3.z) * (pt1.y - pt2.y) - (pt1.z - pt2.z) * (pt2.y - pt3.y);
            pt.B = (pt2.x - pt3.x) * (pt1.z - pt2.z) - (pt1.x - pt2.x) * (pt2.z - pt3.z);
            pt.C = (pt2.y - pt3.y) * (pt1.x - pt2.x) - (pt1.y - pt2.y) * (pt2.x - pt3.x);
            pt.D = - pt1.x * (pt2.y * pt3.z - pt2.z * pt3.y) + pt1.y * (pt2.x * pt3.z - pt2.z * pt3.x) - pt1.z * (pt2.x * pt3.y - pt2.y * pt3.x);
            return pt;
           
        }
        public double DepthValue(Coefficient_Of_Plane surface,int x,int y)
        {
           
            double z = 200;
            if (surface.B != 0)
                z = (-surface.A * x - surface.C * y - surface.D) / surface.B;
            return z;
        }
        public bool CheckInside(Point point1, Point point2, Point point3, int x, int y)
        {
            float fxyC, fxy;
            fxyC = point3.Y * (point2.X - point1.X) - point3.X * (point2.Y - point1.Y) + point1.X * (point2.Y - point1.Y) - point1.Y * (point2.X - point1.X);
            fxy =  y * (point2.X - point1.X) - x * (point2.Y - point1.Y) + point1.X * (point2.Y - point1.Y) - point1.Y * (point2.X - point1.X);
            if (((fxyC <= 0) && (fxy <= 0)) || ((fxyC >= 0) && (fxy >= 0)))
                return true;
            else
                return false;
        }
        //Subroutine to check any point(x,y) inside the triangle
        public bool inside_triangle_check(Point pt1, Point pt2, Point pt3, int x, int y)
        {
            
            bool check = CheckInside(pt1, pt2, pt3, x, y) && CheckInside(pt2, pt3, pt1, x, y) && CheckInside(pt3, pt1, pt2, x, y);
            if (check == true) return true;
            else return false;
        }
    }
}

There is also changes in Form1.cs class.Source code is given below:

Form1.cs


using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
//using System.Windows.Media;
 
namespace Graphics3Dto2D
{ 
    public partial class Form1 : Form
    {
        private Bitmap m_Canvas;
        
 
        private  DepthBuffer depthbuffer;
            
            Coefficient_Of_Plane[] surface= new Coefficient_Of_Plane[12];
            double [] depth=new double[12];
            _3Dpoint[] Dpoint =new _3Dpoint[8];
            int[,] _2dpoint = new int[8,2];
 
        private _3Dpoint temp;
 
        private  double neg = -20;
        private  double pov =  20;
        private  double near = 100;
        private  double far =  140;
        private  projection proc;
            
        private  double z_buffer;
        private  Color Finalcolor;
        private  Color []color=new Color[12];
        
        public Form1()
        {
            InitializeComponent();
            CenterToScreen();
            SetStyle(ControlStyles.ResizeRedraw, true);
 
 
            Dpoint[0] = new _3Dpoint(neg, near, pov);
            Dpoint[1] = new _3Dpoint(pov, near, pov);
            Dpoint[2] = new _3Dpoint(pov, near, neg);
            Dpoint[3] = new _3Dpoint(neg, near, neg);
            Dpoint[4] = new _3Dpoint(neg + 20, far, pov + 20);
            Dpoint[5] = new _3Dpoint(pov + 20, far, pov + 20);
            Dpoint[6] = new _3Dpoint(pov + 20, far, neg + 20);
            Dpoint[7] = new _3Dpoint(neg + 20, far, neg + 20);
 
           
          
 
            depthbuffer = new DepthBuffer();
            proc = new projection();
 
 
 
        }
        private void DrawCube()
        {
           
            
 
            for (int i = 0; i < 8; i++)
            {
                temp = new _3Dpoint(Dpoint[i]);
                if (proc.Trans_Point(temp))
                {
                    _2dpoint[i, 0] = proc.p1.h;
                    _2dpoint[i, 1] = proc.p1.v;
                }
                else
                {
                    MessageBox.Show("conversion is invalid");
                    break;
                }
            }
 
            Point point1 = new Point(_2dpoint[0, 0], _2dpoint[0, 1]);
            Point point2 = new Point(_2dpoint[1, 0], _2dpoint[1, 1]);
            Point point3 = new Point(_2dpoint[2, 0], _2dpoint[2, 1]);
            Point point4 = new Point(_2dpoint[3, 0], _2dpoint[3, 1]);
            Point point5 = new Point(_2dpoint[4, 0], _2dpoint[4, 1]);
            Point point6 = new Point(_2dpoint[5, 0], _2dpoint[5, 1]);
            Point point7 = new Point(_2dpoint[6, 0], _2dpoint[6, 1]);
            Point point8 = new Point(_2dpoint[7, 0], _2dpoint[7, 1]);
          
 
            //front surface dividing into two triangle
            surface[0] = depthbuffer.Coefficient_Value(Dpoint[0], Dpoint[1], Dpoint[2]); color[0] = Color.Blue;
            surface[1] = depthbuffer.Coefficient_Value(Dpoint[2], Dpoint[3], Dpoint[0]); color[1] = Color.Blue;
 
            //left surface dividing into two triangle
            surface[2] = depthbuffer.Coefficient_Value(Dpoint[0], Dpoint[4], Dpoint[7]); color[2] = Color.Red;
            surface[3] = depthbuffer.Coefficient_Value(Dpoint[7], Dpoint[3], Dpoint[0]); color[3] = Color.Red;
 
            //right surface dividing into two triangle
            surface[4] = depthbuffer.Coefficient_Value(Dpoint[1], Dpoint[5], Dpoint[6]); color[4] = Color.Green;
            surface[5] = depthbuffer.Coefficient_Value(Dpoint[6], Dpoint[2], Dpoint[1]); color[5] = Color.Green;
 
            //top surface dividing into two triangle
            surface[6] = depthbuffer.Coefficient_Value(Dpoint[0], Dpoint[1], Dpoint[5]); color[6] = Color.Orange;
            surface[7] = depthbuffer.Coefficient_Value(Dpoint[5], Dpoint[4], Dpoint[0]); color[7] = Color.Orange;
 
            //bottom surface dividing into two triangle
            surface[8] = depthbuffer.Coefficient_Value(Dpoint[3], Dpoint[2], Dpoint[6]); color[8] = Color.Yellow;
            surface[9] = depthbuffer.Coefficient_Value(Dpoint[6], Dpoint[7], Dpoint[3]); color[9] = Color.Yellow;
 
            //back surface dividing into two triangle
            surface[10] = depthbuffer.Coefficient_Value(Dpoint[4], Dpoint[5], Dpoint[6]); color[10] = Color.White;
            surface[11] = depthbuffer.Coefficient_Value(Dpoint[6], Dpoint[7], Dpoint[4]); color[11] = Color.White;
            
 
 
            m_Canvas = new Bitmap(1440, 920); // Doesn't have to be initialized here
 
            for (int x = 320; x < 1120; x++)
            {
                for (int y = 20; y < 820; y++)
                {
                    for (int numsurf = 0; numsurf < 12; numsurf++)
                    {
                        depth[numsurf] =200;
                        Finalcolor = Color.Gray;
                    }
                    //front
                    if (depthbuffer.inside_triangle_check(point1,point2,point3, x, y))
                        depth[0] = depthbuffer.DepthValue(surface[0], 0, 0);
                    if (depthbuffer.inside_triangle_check(point3, point4, point1, x, y))
                        depth[1] = depthbuffer.DepthValue(surface[1], 0, 0);
 
                    //left
                    if (depthbuffer.inside_triangle_check(point1, point5, point8, x, y))
                        depth[2] = depthbuffer.DepthValue(surface[2], 0, 0);
                    if (depthbuffer.inside_triangle_check(point8, point4, point1, x, y))
                        depth[3] = depthbuffer.DepthValue(surface[3], 0, 0);
 
                    //right
                    if (depthbuffer.inside_triangle_check(point2, point6, point7, x, y))
                        depth[4] = depthbuffer.DepthValue(surface[4], 0, 0);
                    if (depthbuffer.inside_triangle_check(point7, point3, point2, x, y))
                        depth[5] = depthbuffer.DepthValue(surface[5], 0, 0);
 
                    //top
                    if (depthbuffer.inside_triangle_check(point1, point2, point6, x, y))
                        depth[6] = depthbuffer.DepthValue(surface[6], 0, 0);
                    if (depthbuffer.inside_triangle_check(point6, point5, point1, x, y))
                        depth[7] = depthbuffer.DepthValue(surface[7], 0, 0);
 
                    //bottom
                    if (depthbuffer.inside_triangle_check(point4, point3, point7, x, y))
                        depth[8] = depthbuffer.DepthValue(surface[8], 0, 0);
                    if (depthbuffer.inside_triangle_check(point7, point8, point4, x, y))
                        depth[9] = depthbuffer.DepthValue(surface[9],0, 0);
 
                    //back
                    if (depthbuffer.inside_triangle_check(point5, point6, point7, x, y))
                        depth[10] = depthbuffer.DepthValue(surface[10], 0, 0);
                    if (depthbuffer.inside_triangle_check(point7, point8, point5, x, y))
                        depth[11] = depthbuffer.DepthValue(surface[11], 0, 0);
                    z_buffer = 200;
                    Finalcolor = Color.Gray;
                    for (int numsurf = 0; numsurf < 12; numsurf++)
                    {
                        
                        if (depth[numsurf] < z_buffer)
                        {
                            z_buffer = depth[numsurf];
                            Finalcolor=color[numsurf];
                        }
                    }
 
                    m_Canvas.SetPixel(x, y, Finalcolor);
                }
            }
 
            SetCanvasAsImage();
 
        }
        public void SetCanvasAsImage()
        {
            pictureBox1.Image = m_Canvas;
        }
        protected override void OnPaint(PaintEventArgs e)
        {
            DrawCube();
        }
 
    }
}

Copy Source code for other classes like CAMERA.cs, SCREEN.cs,3Dpoint.cs,2Dpoint.cs,Program.cs,Projection.cs from previous project Projecting a 3D world co-ordinates into 2D perspective.

You can also download the complete project file from here Download

2 comments:

  1. Hey! I am so excited to know if you have a lot of traffic on your weblog?

    ReplyDelete
  2. Hello , Dinesh ...........glad to see a really nice article. Could you please explain ... How can I implement the sub-division algorithm , the scan-line algorithm and also the painter's algorithm.... using this code? .............Thanks.

    ReplyDelete