| Revision as of 08:35, 29 January 2005 editFlamurai (talk | contribs)Extended confirmed users5,682 editsm name change← Previous edit | Revision as of 09:11, 29 January 2005 edit undoFlamurai (talk | contribs)Extended confirmed users5,682 edits rewrite; see talk for commentsNext edit → | ||
| Line 1: | Line 1: | ||
| In ], '''hidden surface determination''' is the process used to determine which surfaces and parts of surfaces are not visible from a certain viewpoint. A hidden surface determination algorithm is a solution to the '''visibility problem''', which was one of the first major problems in the field of 3D computer graphics. The process of hidden surface determination is sometimes called '''hiding''', and such an algorithm is sometimes called a '''hider'''. | |||
| <!-- Hidden Face Removal --> | |||
| <!-- original article by Matthew Wegner --> | |||
| <!-- February 14, 2004 --> | |||
| '''Hidden surface determination''' is a technique used in ] for drawing a ] scene correctly. It is also implemented to save time, because if a face cannot be seen, that means it should not be drawn in the scene, and therefore you don't have to waste ] cycles drawing it. This article deals with several methods of hidden face removal. | |||
| Hidden surface determination is necessary to render an image correctly, as parts of the image that are not visible should not be drawn. It also speeds up rendering since objects that aren't visible can be removed from the ]. | |||
| == Backface culling == | |||
| There are many techniques for hidden surface determination, and the core differences between most rendering algorithms is how they handle this problem. Some of the more common techniques include: | |||
| In ''backface culling'' we want to remove or "cull" the backfaces from an object we are drawing. A backface is essentially what it sounds like; the back of something. But of what? Well, that would be the backface of what are usually referred to as ]s or facets. ] objects are made up of polygons or facets, which are made up of ]. One property of polygons is that they generally have a particular direction they are facing. The direction a polygon is facing is determined by its ]. The normal is a ] which is perpendicular to the polygon which can also be said to be a ] (as defined in ].) The normal sticks out of the front of the polygon, and so, in backface culling, we only want to draw polygons that are facing us. You may be asking yourself, "Why would we want to do that?" Well, first of all, as with most hidden face removal techniques, it saves time. For example, with a cube, we can only see a maximum of three faces at any one time. Considering there are six faces in a cube, drawing only those three can save at least 50% of the work from the rest of your ]. Also, this makes objects appear to be more solid. With a ], you can see right through it to the other side. But, if you look at your monitor, you can't see the back of it, right? That's the principle backface culling works on. | |||
| ; Backface culling : Since ]es are hollow shells, not solid objects, the back side of some faces, or ]s, in the mesh will face the camera. Typically, there is no reason to draw such faces. | |||
| == View frustum culling == | |||
| ; Viewing frustum culling : The ] is a geometric representation of the volume visible to the virtual camera. Naturally, objects outside this volume will not be visible in the final image, so they are discarded. Often, objects lie on the boundary of the viewing frustum. These objects are cut into pieces along this boundary in a process called ''clipping'', and the pieces that lie outside the frustum are discarded. | |||
| ; Occlusion culling : Occlusion culling is the process of determining which portions of objects are hidden by other objects from a given viewpoint. This is one of the fundamental problems in computer graphics, and many different occlusion culling algorithms have been developed. The simplest is ], in which polygons are sorted, then drawn back to front. The most common in real-time computer graphics is ], in which the depth value at each pixel is stored as each polygon is rendered. The pixel is only overwritten if the depth value of the current point is less than the depth value stored in the z-buffer. Both of these methods operate on polygon meshes. ], which can also operate on parametric geometry, attempts to model the path of light rays into a viewpoint by tracing rays from the viewpoint into the scene. The first object the ray intersects is rendered, as it naturally is the object visible to the camera. | |||
| ; Contribution culling : Often, objects are so far away that they do not contribute signficantly to the final image. These objects are thrown away if their screen ] is too small. | |||
| Though hidden surface determination is most often used to determine what is visible in the final image, it is also has other applications, such as determining which parts of objects are in shadow. | |||
| With ''View frustum culling'' we set up a sort of sideways pyramid, representing the viewer's field of vision. Any ]s falling totally outside of it, are ignored in rendering. A polygon partially inside it is clipped to the view, so we only draw the parts that are actually being seen. Finally, a polygon totally inside is drawn normally. The obvious way to accomplish this, is to check every polygon with the view ]. Well, that may work when there are only a few objects, but if you're viewing a complex scene, with numerous objects and things to be rendered, it takes up more CPU cycles than it really needs to, because there is a faster way. We can speed this process up by dividing the scene up into octrees, which is a cube split along each axis, x, y, and z. For the areas of the scene that have more objects in them, we can continue to divide each ] into smaller ones, for more precision, while fairly empty areas can make do with one big box. The reason for all these boxes, and boxes of boxes is that we can test the boxes themselves against the view frustum. But we only check the parent boxes at first (the parent boxes being the big ones that were divided.) If a parent box is totally outside the view frustum, we don't need to check any of the smaller boxes inside it, because logically, they aren't in the view frustum either. However, if a parent box IS in the view frustum, in part or in whole, we can then check which of the child boxes are inside the view frustum. Then, we only render polygons that are inside boxes in the view frustum. | |||
| ] | |||
| == Occlusion culling == <!-- This needs more info on other areas --> | |||
| ''Occlusion culling'' checks which objects are in front of others and draws them in the correct order. An object which is in front of another, and therefore blocking part or all of it from sight is said to "occlude" that object. BSP (]) trees (used in ] and ]) are an example of occlusion culling. There are several forms of occlusion culling, but the one I know best is Z-Buffering. In the Z-Buffer, the z values for each pixel are stored. When plotting a pixel in a ], for example, we check to see if the value for that pixel is closer to the camera than the pixel we are plotting. A good way to find this out is through ]. If the current value is closer to the camera, then we don't plot the pixel we wanted, but otherwise, pixel plotting goes ahead as normal. This is one of the most accurate ways to properly order your drawing, so things appear in the right order, but also very time consuming. Not only do we have to run a check for any pixel we want to plot, but after we're done, we have to reset the buffer, so we can perform the check again. There are however optimizations for this method, to cut down some of the time, but seeing as I'm still learning this method, I can't tell you how things like "1/z" work exactly. <!-- This ought to be explained properly --> | |||
| A primitive method, called Z-Ordering, is to get the overall depth of the polygons (by average of the defining points), sort them, then drawing in the reverse order (deeper first, closer last).<!-- Added by Dalvi. Can be erased when the article is completed with appropriate info --> <!-- Thanks for bringing that up, I forgot about z-ordering. Fixed spelling error, added name of method --> | |||
| == Contribution culling == | |||
| Basically ''contribution culling'' checks projection values and if they are too small, or off-screen, you don't draw the ]/]. | |||
Revision as of 09:11, 29 January 2005
In 3D computer graphics, hidden surface determination is the process used to determine which surfaces and parts of surfaces are not visible from a certain viewpoint. A hidden surface determination algorithm is a solution to the visibility problem, which was one of the first major problems in the field of 3D computer graphics. The process of hidden surface determination is sometimes called hiding, and such an algorithm is sometimes called a hider.
Hidden surface determination is necessary to render an image correctly, as parts of the image that are not visible should not be drawn. It also speeds up rendering since objects that aren't visible can be removed from the graphics pipeline.
There are many techniques for hidden surface determination, and the core differences between most rendering algorithms is how they handle this problem. Some of the more common techniques include:
- Backface culling
- Since meshes are hollow shells, not solid objects, the back side of some faces, or polygons, in the mesh will face the camera. Typically, there is no reason to draw such faces.
- Viewing frustum culling
- The viewing frustum is a geometric representation of the volume visible to the virtual camera. Naturally, objects outside this volume will not be visible in the final image, so they are discarded. Often, objects lie on the boundary of the viewing frustum. These objects are cut into pieces along this boundary in a process called clipping, and the pieces that lie outside the frustum are discarded.
- Occlusion culling
- Occlusion culling is the process of determining which portions of objects are hidden by other objects from a given viewpoint. This is one of the fundamental problems in computer graphics, and many different occlusion culling algorithms have been developed. The simplest is painter's algorithm, in which polygons are sorted, then drawn back to front. The most common in real-time computer graphics is z-buffering, in which the depth value at each pixel is stored as each polygon is rendered. The pixel is only overwritten if the depth value of the current point is less than the depth value stored in the z-buffer. Both of these methods operate on polygon meshes. Ray tracing, which can also operate on parametric geometry, attempts to model the path of light rays into a viewpoint by tracing rays from the viewpoint into the scene. The first object the ray intersects is rendered, as it naturally is the object visible to the camera.
- Contribution culling
- Often, objects are so far away that they do not contribute signficantly to the final image. These objects are thrown away if their screen projection is too small.
Though hidden surface determination is most often used to determine what is visible in the final image, it is also has other applications, such as determining which parts of objects are in shadow.
Category: