diff options
Diffstat (limited to 'graphics/sketch/Doc/sketch/Hidden-surface-removal.html')
-rw-r--r-- | graphics/sketch/Doc/sketch/Hidden-surface-removal.html | 100 |
1 files changed, 100 insertions, 0 deletions
diff --git a/graphics/sketch/Doc/sketch/Hidden-surface-removal.html b/graphics/sketch/Doc/sketch/Hidden-surface-removal.html new file mode 100644 index 0000000000..daf8ad4311 --- /dev/null +++ b/graphics/sketch/Doc/sketch/Hidden-surface-removal.html @@ -0,0 +1,100 @@ +<html lang="en"> +<head> +<title>Hidden surface removal - Sketch</title> +<meta http-equiv="Content-Type" content="text/html"> +<meta name="description" content="Sketch"> +<meta name="generator" content="makeinfo 4.7"> +<link title="Top" rel="start" href="index.html#Top"> +<link rel="up" href="Caveats.html#Caveats" title="Caveats"> +<link rel="prev" href="Clipping.html#Clipping" title="Clipping"> +<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage"> +<!-- +Copyright (C) 2005, 2006, 2007, 2008 Eugene K. Ressler. + +This manual is for `sketch', version 0.2 (build 131), +Saturday, August 09, 2008, a program that converts descriptions of simple +three-dimensional scenes into static drawings. This version generates +`PSTricks' or `PGF/TikZ' code suitable for use with the +TeX document processing system. + +`Sketch' is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +Sketch is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with `sketch'; see the file COPYING.txt. If not, see +http://www.gnu.org/copyleft.--> +<meta http-equiv="Content-Style-Type" content="text/css"> +<style type="text/css"><!-- + pre.display { font-family:inherit } + pre.format { font-family:inherit } + pre.smalldisplay { font-family:inherit; font-size:smaller } + pre.smallformat { font-family:inherit; font-size:smaller } + pre.smallexample { font-size:smaller } + pre.smalllisp { font-size:smaller } + span.sc { font-variant:small-caps } + span.roman { font-family: serif; font-weight: normal; } +--></style> +</head> +<body> +<div class="node"> +<p> +<a name="Hidden-surface-removal"></a>Previous: <a rel="previous" accesskey="p" href="Clipping.html#Clipping">Clipping</a>, +Up: <a rel="up" accesskey="u" href="Caveats.html#Caveats">Caveats</a> +<hr><br> +</div> + +<!-- node-name, next, previous, up --> +<h4 class="subsection">4.4.3 Hidden surface removal and polygon splitting</h4> + +<p><code>Sketch</code> uses the <dfn>depth sort algorithm</dfn> +<a name="index-depth-sort-493"></a><a name="index-hidden-surface-algorithm-494"></a>for hidden surface removal. This is a very old technique due to +Newell.<a rel="footnote" href="#fn-1" name="fnd-1"><sup>1</sup></a> It is +generally regarded as too slow for real time graphics, but it is +ideal for our purpose where speed is not very important.<a rel="footnote" href="#fn-2" name="fnd-2"><sup>2</sup></a> + + <p>The depth sort algorithm merely sorts objects on a key of increasing +z-coordinate, equivalent to decreasing depth. Objects are then +drawn in the sorted sequence so that those at the rear of the scene +are overwritten by those closer to the viewer. Since this is also +how oil painters practice their art, depth sort is sometimes called +“the painter's algorithm.” + + <p>In some cases it is impossible to strictly order polygons according to +depth. Moreover, even if a correct depth ordering exists, the +computation needed to find it may be too complex and slow. In these +cases, <code>sketch</code> splits +<a name="index-splitting_002c-line-and-surface-495"></a>one or more polygons into pieces. The +expectation is that the new, smaller polygons will be simpler to +order. <code>Sketch</code> uses a <acronym title="binary space partition">BSP</acronym> (binary space partition) +<a name="index-binary-space-partition-496"></a><a name="index-BSP_002c-binary-space-partition-497"></a>to handle the splitting operation. + +<ul class="menu"> +<li><a accesskey="1" href="Statistics.html#Statistics">Statistics</a>: Performance numbers on depth sort. +<li><a accesskey="2" href="Bugs-and-anomalies.html#Bugs-and-anomalies">Bugs and anomalies</a>: Imperfections in this implementation. +</ul> + + <div class="footnote"> +<hr> +<h4>Footnotes</h4><p class="footnote"><small>[<a name="fn-1" href="#fnd-1">1</a>]</small> Newell, M.E., R.G. Newell, and T.L. Sancha, A +solution to the hidden surface problem. <i>Proceedings of the ACM +annual conference - Volume 1</i>, page 443–450, ACM Press, 1972.</p> + + <p class="footnote"><small>[<a name="fn-2" href="#fnd-2">2</a>]</small> We +have run <code>sketch</code> on the famous Stanford Bunny, which consists +of nearly 70,000 triangles. Run time was about 6 seconds. +Most of this was spent writing the output file rather than in the +hidden surface algorithm. LaTeX took much longer to process the +resulting <code>PSTricks</code> code. The obvious conclusion is that the +speed of the depth sort algorithm is not a worry.</p> + + <p><hr></div> + + </body></html> + |