Part 12: Hidden Surface Removal and 3D model projection

Part 12: Hidden Surface Removal and 3D model projection

by | Aug 31, 2021 | Computer Graphics

Hidden Surface Removal

  1. One of the most challenging problems in computer graphics is the removal of hidden parts from images of solid objects.
  2. In real life, the opaque material of these objects obstructs the light rays from hidden parts and prevents us from seeing them.
  3. In the computer generation, no such automatic elimination takes place when objects are projected onto the screen coordinate system.
  4. Instead, all parts of every object, including many parts that should be invisible are displayed.
  5. To remove these parts to create a more realistic image, we must apply a hidden line or hidden surface algorithm to set of objects.
  6. The algorithm operates on different kinds of scene models, generate various forms of output or cater to images of different complexities.
  7. All use some form of geometric sorting to distinguish visible parts of objects from those that are hidden.
  8. Just as alphabetical sorting is used to differentiate words near the beginning of the alphabet from those near the ends.
  9. Geometric sorting locates objects that lie near the observer and are therefore visible.
  10. Hidden line and Hidden surface algorithms capitalize on various forms of coherence to reduce the computing required to generate an image.
  11. Different types of coherence are related to different forms of order or regularity in the image.
  12. Scan line coherence arises because the display of a scan line in a raster image is usually very similar to the display of the preceding scan line.
  13. Frame coherence in a sequence of images designed to show motion recognizes that successive frames are very similar.
  14. Object coherence results from relationships between different objects or between separate parts of the same objects.
  15. A hidden surface algorithm is generally designed to exploit one or more of these coherence properties to increase efficiency.
  16. Hidden surface algorithm bears a strong resemblance to two-dimensional scan conversions.

Types of hidden surface detection algorithms

  1. Object space methods
  2. Image space methods

Object space methods:

In this method, various parts of objects are compared. After comparison visible, invisible or hardly visible surface is determined. These methods generally decide visible surface. In the wireframe model, these are used to determine a visible line. So these algorithms are line based instead of surface based. Method proceeds by determination of parts of an object whose view is obstructed by other object and draws these parts in the same color.

Image space methods:

Here positions of various pixels are determined. It is used to locate the visible surface instead of a visible line. Each point is detected for its visibility. If a point is visible, then the pixel is on, otherwise off. So the object close to the viewer that is pierced by a projector through a pixel is determined. That pixel is drawn is appropriate color. These methods are also called a Visible Surface Determination. The implementation of these methods on a computer requires a lot of processing time and processing power of the computer.

The image space method requires more computations. Each object is defined clearly. Visibility of each object surface is also determined.

Differentiate between Object space and Image space method

Object Space Image Space
1. Image space is object based. It concentrates on geometrical relation among objects in the scene. 1. It is a pixel-based method. It is concerned with the final image, what is visible within each raster pixel.
2. Here surface visibility is determined. 2. Here line visibility or point visibility is determined.
3. It is performed at the precision with which each object is defined, No resolution is considered. 3. It is performed using the resolution of the display device.
4. Calculations are not based on the resolution of the display so change of object can be easily adjusted. 4. Calculations are resolution base, so the change is difficult to adjust.
5. These were developed for vector graphics system. 5. These are developed for raster devices.
6. Object-based algorithms operate on continuous object data. 6. These operate on object data.
7. Vector display used for object method has large address space. 7. Raster systems used for image space methods have limited address space.
8. Object precision is used for application where speed is required. 8. There are suitable for application where accuracy is required.
9. It requires a lot of calculations if the image is to enlarge. 9. Image can be enlarged without losing accuracy.
10. If the number of objects in the scene increases, computation time also increases. 10. In this method complexity increase with the complexity of visible parts.

Similarity of object and Image space method

In both method sorting is used a depth comparison of individual lines, surfaces are objected to their distances from the view plane.

Hidden Surface RemovalHidden Surface Removal

Considerations for selecting or designing hidden surface algorithms: Following three considerations are taken:

  1. Sorting
  2. Coherence
  3. Machine

Sorting: All surfaces are sorted in two classes, i.e., visible and invisible. Pixels are colored accordingly. Several sorting algorithms are available i.e.

  1. Bubble sort
  2. Shell sort
  3. Quick sort
  4. Tree sort
  5. Radix sort

Different sorting algorithms are applied to different hidden surface algorithms. Sorting of objects is done using x and y, z co-ordinates. Mostly z coordinate is used for sorting. The efficiency of sorting algorithm affects the hidden surface removal algorithm. For sorting complex scenes or hundreds of polygons complex sorts are used, i.e., quick sort, tree sort, radix sort. For simple objects selection, insertion, bubble sort is used.

Coherence

It is used to take advantage of the constant value of the surface of the scene. It is based on how much regularity exists in the scene. When we moved from one polygon of one object to another polygon of same object color and shearing will remain unchanged.

Types of Coherence

  1. Edge coherence
  2. Object coherence
  3. Face coherence
  4. Area coherence
  5. Depth coherence
  6. Scan line coherence
  7. Frame coherence
  8. Implied edge coherence

1. Edge coherence: The visibility of edge changes when it crosses another edge or it also penetrates a visible edge.

2. Object coherence: Each object is considered separate from others. In object, coherence comparison is done using an object instead of edge or vertex. If A object is farther from object B, then there is no need to compare edges and faces.
3. Face coherence: In this faces or polygons which are generally small compared with the size of the image.

4. Area coherence: It is used to group of pixels cover by same visible face.

5. Depth coherence: Location of various polygons has separated a basis of depth. Depth of surface at one point is calculated, the depth of points on rest of the surface can often be determined by a simple difference equation.

6. Scan line coherence: The object is scanned using one scan line then using the second scan line. The intercept of the first line.

7. Frame coherence: It is used for animated objects. It is used when there is little change in image from one frame to another.

8. Implied edge coherence: If a face penetrates in another, line of intersection can be determined from two points of intersection.

Algorithms used for hidden line surface detection

  1. Back Face Removal Algorithm
  2. Z-Buffer Algorithm
  3. Painter Algorithm
  4. Scan Line Algorithm
  5. Subdivision Algorithm
  6. Floating horizon Algorithm

3D Modelling System

It is a 2D modeling system plus the addition of some more extra primitives. 3D system includes all types of user-defined systems. The standard coordinate system used is called a world coordinate system. Whereas the user-defined coordinate system is called a user coordinate system.

It is of three types

    1. Solid Modelling System3D Modelling System

 

  1. Surface Modelling System
  2. Wireframe Models


Wireframe Models: It has a lot of other names also i.e.

  1. Edge vertex models
  2. Stick figure model
  3. Polygonal net
  4. Polygonal mesh
  5. Visible line detection method

Wireframe model consists of vertex, edge (line) and polygons. Edge is used to join vertex. Polygon is a combination of edges and vertices. The edges can be straight or curved. This model is used to define computer models of parts, especially for computer-assisted drafting systems. Wireframe models are Skelton of lines. Each line has two endpoints. The visibility or appearance or look of the surface can be should using wireframe. If any hidden section exists that will be removed or represented using dashed lines. For determining hidden surface, hidden lines methods or visible line methods are used.

Advantage

  1. It is simple and easy to create.
  2. It requires little computer time for creation.
  3. It requires a short computer memory, so the cost is reduced.
  4. Wireframe provides accurate information about deficiencies of the surface.
  5. It is suitable for engineering models composed of straight lines.
  6. The clipping process in the wireframe model is also easy.
  7. For realistic models having curved objects, roundness, smoothness is achieved.

Disadvantage

  1. It is given only information about the outlook if do not give any information about the complex part.
  2. Due to the use of lines, the shape of the object lost in cluttering of lines.
  3. Each straight line will be represented as collections of four fold lines using data points. So complexity will be increased.

Projection

It is the process of converting a 3D object into a 2D object. It is also defined as mapping or transformation of the object in projection plane or view plane. The view plane is displayed surface.

Projection

Part 7: Artificial Intelligence with Machine Learning(ML)

Part 7: Artificial Intelligence with Machine Learning(ML)

by | Aug 30, 2021 | Artificial Intelligence

Machine Learning (ML)

Learning means the acquisition of knowledge or skills through study or experience. Based on this, we can define machine learning (ML) as follows: It may be defined as the field of computer science, more specifically an application of artificial intelligence, which provides computer systems the ability to learn with data and improve from experience without being explicitly programmed. Basically, the main focus of machine learning is to allow the computers learn automatically without human intervention. Now the question arises that how such learning can be started and done? It can be started with the observations of data. The data can be some examples, instruction or some direct experiences too. Then on the basis of this input, machine makes better decision by looking for some patterns in data.

Types of Machine Learning (ML)

Machine Learning Algorithms helps computer system learn without being explicitly programmed. These algorithms are categorized into supervised or unsupervised. Let us now see a few algorithms:

Supervised machine learning algorithms

This is the most commonly used machine learning algorithm. It is called supervised because the process of algorithm learning from the training dataset can be thought of as a teacher supervising the learning process. In this kind of ML algorithm, the possible outcomes are already known and training data is also labeled with correct answers. It can be understood as follows:

Suppose we have input variables x and an output variable y and we applied an algorithm to learn the mapping function from the input to output such as −

Y = f(x)

Now, the main goal is to approximate the mapping function so well that when we have new input data (x), we can predict the output variable (Y) for that data.

Mainly supervised leaning problems can be divided into the following two kinds of problems −

  • Classification − A problem is called classification problem when we have the categorized output such as “black”, “teaching”, “non-teaching”, etc.
  • Regression − A problem is called regression problem when we have the real value output such as “distance”, “kilogram”, etc.

Decision tree, random forest, knn, logistic regression are the examples of supervised machine learning algorithms.

Unsupervised machine learning algorithms

As the name suggests, these kinds of machine learning algorithms do not have any supervisor to provide any sort of guidance. That is why unsupervised machine learning algorithms are closely aligned with what some call true artificial intelligence. It can be understood as follows:  Suppose we have input variable x, then there will be no corresponding output variables as there is in supervised learning algorithms.

In simple words, we can say that in unsupervised learning there will be no correct answer and no teacher for the guidance. Algorithms help to discover interesting patterns in data.

Unsupervised learning problems can be divided into the following two kinds of problem −

  • Clustering − In clustering problems, we need to discover the inherent groupings in the data. For example, grouping customers by their purchasing behavior.
  • Association − A problem is called association problem because such kinds of problem require discovering the rules that describe large portions of our data. For example, finding the customers who buy both x and y.

K-means for clustering, Apriori algorithm for association are the examples of unsupervised machine learning algorithms.

Reinforcement machine learning algorithms

These kinds of machine learning algorithms are used very less. These algorithms train the systems to make specific decisions. Basically, the machine is exposed to an environment where it trains itself continually using the trial and error method. These algorithms learn from past experience and tries to capture the best possible knowledge to make accurate decisions. Markov Decision Process is an example of reinforcement machine learning algorithms.

[wpsbx_html_block id=1891]

Most Common Machine Learning Algorithms

Linear Regression

It is one of the most well-known algorithms in statistics and machine learning. Basic concept −It is mainly linear regression is a linear model that assumes a linear relationship between the input variables say x and the single output variable say y. In other words, we can say that y can be calculated from a linear combination of the input variables x. The relationship between variables can be established by fitting a best line.

Types of Linear Regression

Linear regression is of the following two types:

  • Simple linear regression − A linear regression algorithm is called simple linear regression if it is having only one independent variable.
  • Multiple linear regression − A linear regression algorithm is called multiple linear regression if it is having more than one independent variable.

Linear regression is mainly used to estimate the real values based on continuous variable(s). For example, the total sale of a shop in a day, based on real values, can be estimated by linear regression.

Logistic Regression

  • It is a classification algorithm and also known as logit regression.
  • Mainly logistic regression is a classification algorithm that is used to estimate the discrete values like 0 or 1, true or false, yes or no based on a given set of independent variable. Basically, it predicts the probability hence its output lies in between 0 and 1.

Decision Tree

  • Decision tree is a supervised learning algorithm that is mostly used for classification problems.
  • Basically it is a classifier expressed as recursive partition based on the independent variables. Decision tree has nodes which form the rooted tree. Rooted tree is a directed tree with a node called “root”. Root does not have any incoming edges and all the other nodes have one incoming edge. These nodes are called leaves or decision nodes. For example, consider the following decision tree to see whether a person is fit or not.

Decision Tree

Support Vector Machine (SVM)

It is used for both classification and regression problems. But mainly it is used for classification problems. The main concept of SVM is

to plot each data item as a point in Support Vector Machinen-dimensional space with the value of each feature being the value of a particular coordinate. Here n would be the features we would have. Following is a simple graphical representation to understand the concept of SVM:

In the above diagram, we have two features hence we first need to plot these two variables in two dimensional space where each point has two co-ordinates, called support vectors. The line splits the data into two different classified groups. This line would be the classifier.

 

K-Nearest Neighbors (KNN)

It is used for both classification and regression of the problems. It is widely used to solve classification problems. The main concept of this algorithm is that it used to store all the available cases and classifies new cases by majority votes of its k neighbors. The case being then assigned to the class which is the most common amongst its K-nearest neighbors, measured by a distance function. The distance function can be Euclidean, Minkowski and Hamming distance. Consider the following to use KNN −

  • Computationally KNN are expensive than other algorithms used for classification problems.
  • The normalization of variables needed otherwise higher range variables can bias it.
  • In KNN, we need to work on pre-processing stage like noise removal.

K-Means Clustering

As the name suggests, it is used to solve the clustering problems. It is basically a type of unsupervised learning. The main logic of K-Means clustering algorithm is to classify the data set through a number of clusters. Follow these steps to form clusters by K-means −

  • K-means picks k number of points for each cluster known as centroids.
  • Now each data point forms a cluster with the closest centroids, i.e., k clusters.
  • Now, it will find the centroids of each cluster based on the existing cluster members.
  • We need to repeat these steps until convergence occurs.

Random Forest

It is a supervised classification algorithm. The advantage of random forest algorithm is that it can be used for both classification and regression kind of problems. Basically it is the collection of decision trees (i.e., forest) or you can say ensemble of the decision trees. The basic concept of random forest is that each tree gives a classification and the forest chooses the best classifications from them. Followings are the advantages of Random Forest algorithm:

  • Random forest classifier can be used for both classification and regression tasks.
  • They can handle the missing values.
  • It won’t over fit the model even if we have more number of trees in the forest.