little_helpers/tikz/sketch-0.2.161/Doc/sketch/Hidden-surface-removal.html

   1 <html lang="en">
   2 <head>
   3 <title>Hidden surface removal - Sketch</title>
   4 <meta http-equiv="Content-Type" content="text/html">
   5 <meta name="description" content="Sketch">
   6 <meta name="generator" content="makeinfo 4.7">
   7 <link title="Top" rel="start" href="index.html#Top">
   8 <link rel="up" href="Caveats.html#Caveats" title="Caveats">
   9 <link rel="prev" href="Clipping.html#Clipping" title="Clipping">
  10 <link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
  11 <!--
  12 Copyright (C) 2005, 2006, 2007, 2008 Eugene K. Ressler.
  13
  14 This manual is for `sketch', version 0.2 (build 161),
  15 Tuesday, September 08, 2009, a program that converts descriptions of simple
  16 three-dimensional scenes into static drawings. This version generates
  17 `PSTricks' or `PGF/TikZ' code suitable for use with the
  18 TeX document processing system.
  19
  20 `Sketch' is free software; you can redistribute it and/or modify
  21 it under the terms of the GNU General Public License as published by
  22 the Free Software Foundation; either version 3, or (at your option)
  23 any later version.
  24
  25 Sketch is distributed in the hope that it will be useful,
  26 but WITHOUT ANY WARRANTY; without even the implied warranty of
  27 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  28 GNU General Public License for more details.
  29
  30 You should have received a copy of the GNU General Public License
  31 along with `sketch'; see the file COPYING.txt.  If not, see
  32 http://www.gnu.org/copyleft.-->
  33 <meta http-equiv="Content-Style-Type" content="text/css">
  34 <style type="text/css"><!--
  35   pre.display { font-family:inherit }
  36   pre.format  { font-family:inherit }
  37   pre.smalldisplay { font-family:inherit; font-size:smaller }
  38   pre.smallformat  { font-family:inherit; font-size:smaller }
  39   pre.smallexample { font-size:smaller }
  40   pre.smalllisp    { font-size:smaller }
  41   span.sc { font-variant:small-caps }
  42   span.roman { font-family: serif; font-weight: normal; }
  43 --></style>
  44 </head>
  45 <body>
  46 <div class="node">
  47 <p>
  48 <a name="Hidden-surface-removal"></a>Previous:&nbsp;<a rel="previous" accesskey="p" href="Clipping.html#Clipping">Clipping</a>,
  49 Up:&nbsp;<a rel="up" accesskey="u" href="Caveats.html#Caveats">Caveats</a>
  50 <hr><br>
  51 </div>
  52
  53 <!-- node-name,  next,  previous,  up -->
  54 <h4 class="subsection">4.4.3 Hidden surface removal and polygon splitting</h4>
  55
  56 <p><code>Sketch</code> uses the <dfn>depth sort algorithm</dfn>
  57 <a name="index-depth-sort-498"></a><a name="index-hidden-surface-algorithm-499"></a>for hidden surface removal.  This is a very old technique due to
  58 Newell.<a rel="footnote" href="#fn-1" name="fnd-1"><sup>1</sup></a>  It is
  59 generally regarded as too slow for real time graphics, but it is
  60 ideal for our purpose where speed is not very important.<a rel="footnote" href="#fn-2" name="fnd-2"><sup>2</sup></a>
  61
  62    <p>The depth sort algorithm merely sorts objects on a key of increasing
  63 z-coordinate, equivalent to decreasing depth.  Objects are then
  64 drawn in the sorted sequence so that those at the rear of the scene
  65 are overwritten by those closer to the viewer. Since this is also
  66 how oil painters practice their art, depth sort is sometimes called
  67 &ldquo;the painter's algorithm.&rdquo;
  68
  69    <p>In some cases it is impossible to strictly order polygons according to
  70 depth.  Moreover, even if a correct depth ordering exists, the
  71 computation needed to find it may be too complex and slow.  In these
  72 cases, <code>sketch</code> splits
  73 <a name="index-splitting_002c-line-and-surface-500"></a>one or more polygons into pieces.  The
  74 expectation is that the new, smaller polygons will be simpler to
  75 order.  <code>Sketch</code> uses a <acronym title="binary space partition">BSP</acronym> (binary space partition)
  76 <a name="index-binary-space-partition-501"></a><a name="index-BSP_002c-binary-space-partition-502"></a>to handle the splitting operation.
  77
  78 <ul class="menu">
  79 <li><a accesskey="1" href="Statistics.html#Statistics">Statistics</a>:                   Performance numbers on depth sort.
  80 <li><a accesskey="2" href="Bugs-and-anomalies.html#Bugs-and-anomalies">Bugs and anomalies</a>:           Imperfections in this implementation.
  81 </ul>
  82
  83    <div class="footnote">
  84 <hr>
  85 <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
  86 solution to the hidden surface problem. <i>Proceedings of the ACM
  87 annual conference - Volume 1</i>, page 443&ndash;450, ACM Press, 1972.</p>
  88
  89    <p class="footnote"><small>[<a name="fn-2" href="#fnd-2">2</a>]</small> We
  90 have run <code>sketch</code> on the famous Stanford Bunny, which consists
  91 of nearly 70,000 triangles.  Run time was about 6 seconds.
  92 Most of this was spent writing the output file rather than in the
  93 hidden surface algorithm.  LaTeX took much longer to process the
  94 resulting <code>PSTricks</code> code.  The obvious conclusion is that the
  95 speed of the depth sort algorithm is not a worry.</p>
  96
  97    <p><hr></div>
  98
  99    </body></html>
 100