enikesha
/
old


			
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456
							<!--
	demo.design 3D programming FAQ

	Idea, texts, screenshots:
		Andrew A. Aksyonoff,
		shodan@chat.ru

	Web-design, illustrations:
		Andrey Samoilov,
		asy@sense.simbirsk.su
-->

<html>
<head>
<title>demo.design 3D programming FAQ. Удаление невидимых частей. Отсечение.</title>
<link rel=stylesheet href="../style.css" type="text/css">
</head>

<script language="javascript">
<!--//
browser = navigator.appName;
version = parseFloat(navigator.appVersion);
if (browser == "Netscape" && version >= 3.0) { jsenabled = 1; } else
if (browser == "Microsoft Internet Explorer" && version >= 3.0) { jsenabled = 1; } else { jsenabled = 0; }

function swap(img,ref) { if (jsenabled) {document.images[img].src = ref;} }
function loadtocache(img,ref) { cache[img] = new Image(); cache[img].src = ref; }

if (jsenabled) {
cache = new Array();
loadtocache(0,"../img/xdl.gif");
loadtocache(1,"../img/xfaq.gif");
loadtocache(2,"../img/xlinks.gif");
loadtocache(3,"../img/xauthor.gif");
loadtocache(4,"../img/xe.gif");
loadtocache(5,"../img/xprev.gif");
loadtocache(6,"../img/xnext.gif");}
//-->
</script>

<body bgcolor=white><center>

<!-- Title -->

<img src="../img/b.gif" width=500 height=1 alt=""><br>
<img src="../img/t.gif" width=500 height=1 alt=""><br>
<img src="../img/b.gif" width=500 height=1 alt=""><br>
<img src="../img/t.gif" width=500 height=2 alt=""><br>
<table width=500 cellpadding=0 cellspacing=0 border=0>
<td><img src="../img/t.gif" width=5 height=1 alt=""><a href="../main.htm" onmouseover="swap('logo','../img/xe.gif');" onmouseout="swap('logo','../img/e.gif');"><img src="../img/e.gif" name=logo width=60 height=50 hspace=10 border=0 alt=" в самое начало "></a></td>
<td><p class=pagetitle><img src="../img/t.gif" width=265 height=1 alt=""><br>demo.design<br>3D programming FAQ</td>
<td align=center><p class=navy><a href="../download.htm" onmouseover="swap('dl','../img/xdl.gif');" onmouseout="swap('dl','../img/dl.gif');"><img src="../img/dl.gif" name=dl width=40 height=40 border=0 hspace=5 alt=" download "></a><br>download</td>
<td align=center><p class=navy><a href="../links.htm" onmouseover="swap('links','../img/xlinks.gif');" onmouseout="swap('links','../img/links.gif');"><img src="../img/links.gif" name=links width=40 height=40 border=0 hspace=5 alt=" коллекция линков "></a><br>links</td>
<td align=center><p class=navy><a href="../author.htm"  onmouseover="swap('author','../img/xauthor.gif');" onmouseout="swap('author','../img/author.gif');"><img src="../img/author.gif" name=author width=40 height=40 border=0 hspace=5 alt=" автора! "></a><br>author</td>
</table>
<img src="../img/t.gif" width=500 height=4 alt=""><br><img src="../img/b.gif" width=500 height=1 alt=""><br>

<!-- Head -->

<table width=500 cellpadding=0 cellspacing=10 border=0><td><div align=justify>

<p class=title>
<img src="../img/b3.gif" width=70 height=70 align=left hspace=0 alt="">
<img src="../img/t.gif" width=5 height=70 align=left hspace=0 alt="">
УДАЛЕНИЕ НЕВИДИМЫХ ЧАСТЕЙ<br>3.6. Отсечение

<!-- Article -->

<p>В процессе отрисовки граней мы почти сразу столкнемся со следующей неприятной
ситуацией: проекция грани лежит в плоскости экрана, но она вовсе не обязана
точно попадать в прямоугольник-экран. Поэтому эту самую проекцию желательно
корректно обрезать по границе экрана (можно, конечно, выводить все на экран
через свою функцию putpixel() и проверять в ней x, y на попадание в экран,
но это извращение и вдобавок очень медленно). Операцией обрезания как раз и
занимаются разные алгоритмы отсечения (clipping).

<a name="361"></a>
<p class=title><img src="../img/b3.gif" width=70 height=70 align=left hspace=0 alt=""><img src="../img/t.gif" width=5 height=70 align=left hspace=0 alt="">3.6.1. Отсечение при растеризации

<p>Это, пожалуй, самый простой, довольно быстрый и наиболее часто используемый
метод отсечения. Идея, как обычно, проста. При растеризации треугольника мы
в конечном итоге рисуем набор горизонтальных отрезков. Так и будем обрезать
по границам экрана именно отрезки. Пусть мы рисуем отрезок от start_x до
end_x по строке с y = current_sy. Возможны следующие случаи:

<p class=expression><ul>
<li>(current_sy < 0), или (current_sy >= YSIZE), или (start_x >= XSIZE),
или (end_x <= 0). Тогда отрезок вообще не виден и мы его не рисуем.
Причем если (current_sy >= YSIZE), то отрисовку грани прекращаем.

<li>(start_x < 0). В этом случае нам надо пропустить первые (-start_x)
пикселов, так что сдвигаем все интерполируемые по отрезку величины
на (-start_x) пикселов и делаем start_x равным нулю. Например, для
аффинного текстурирования надо сдвинуть u и v:

<pre class=source>
u += (-start_x) * du;
v += (-start_x) * dv;
start_x = 0;
</pre>

<li>(end_x >= XSIZE). Здесь совсем просто. Так как интерполируем мы, начиная
с начала отрезка, достаточно просто сделать end_x = XSIZE - 1.
</ul>

<p>Таким образом, все отсечение делается несколькими строками кода:

<pre class=source>
// ...
if (current_sy >= YSIZE) return;
if ((current_sy < 0) ||
    (start_x >= XSIZE) ||
    (end_x <= 0))
  break;
if (start_x < 0) {
  u -= start_x * du; // пример для аффиного текстурирования
  v -= start_x * dv;
}
if (end_x >= XSIZE) end_x = XSIZE - 1;
// ...
</pre>

<p>Самое приятное заключается в том, что два умножения, которые получаются в
случае (start_x < 0), можно легко совместить с теми двумя, что нужны для
субтексельной точности (см.<a href="72.htm">п.7.2</a>). А несколько сравнений и присваивание на
одну линию делаются достаточно быстро. Получаем отсечение, практически не
замедляющее скорость работы.

<a name="362"></a>
<p class=title><img src="../img/b3.gif" width=70 height=70 align=left hspace=0 alt=""><img src="../img/t.gif" width=5 height=70 align=left hspace=0 alt="">3.6.2. Алгоритм Сазерленда-Ходжмана

<p>Этот алгоритм (Sutherland-Hodgman algorithm) предназначен, на самом деле,
для отсечения произвольного полигона (даже не обязательно выпуклого, хотя
использовать невыпуклые полигоны довольно, на мой взгляд, нерационально)
в полуплоскость, или, для 3D случая, в полупространство; другими словами,
отсечения полигона прямой или плоскостью. Применяя алгоритм несколько раз,
получаем методы отсечения в выпуклый полигон (например, прямоугольник,
которым является экран) или выпуклый объем (например, ту часть пространства,
которую видно из камеры).

<p>Итак, пусть у нас есть полигон с N вершинами, заданными в каком-то порядке,
то есть, по часовой стрелке или против; в каком именно, алгоритму все равно.
Занумеруем их от 0 до N-1. Теперь последовательно обходим все ребра полигона:
ребро от вершины 0 до вершины 1, от 1 до 2, ..., от N-2 до N-1, от N-1 до 0.
Вершины, являющиеся началом и концом ребра, могут лежать в области отсечения,
(область отсечения - либо полуплоскость для 2D случая, либо полупространство
для 3D случая) могут и не лежать; возможны следующие случаи:

<p class=expression><ul>
<li>начало лежит в области отсечения, конец - тоже. Тогда просто добавляем
начало к вершинам полигона-результата.

<li>начало лежит в области отсечения, конец не лежит. В этом случае считаем
точку пересечения ребра и границы области отсечения, добавляем в список
вершин результата начало ребра и вслед за ним точку пересечения.

<li>начало не лежит в области отсечения, конец лежит. Тоже считаем точку
пересечения, и добавляем только ее.

<li>начало не лежит в области отсечения, конец тоже. Переходим к следующему
ребру, никак не изменяя результат.
</ul>

<p>Рассмотрим простенький пример работы алгоритма в 2D случае, а именно отсечем
2D треугольник прямой. Она делит плоскость на две полуплоскости, две области,
нужную и ненужную.

<p><center><img src="illu/illu36a.gif" width=180 height=180 alt="рисунок (illu/illu36a.gif)"></center>

<p class=expression><ul>
<li>шаг 1, ребро 0-1: вершина 0 не лежит в нужной области, вершина 1 лежит.
Ищем точку пересечения, находим точку A, добавляем ее в список вершин
результата. Теперь этот список состоит из одной вершины A.

<li>шаг 2, ребро 1-2: обе вершины лежат в области, добавляем вершину 1.
Результат теперь являет собой список A, 1.

<li>шаг 3, ребро 2-0: 2 лежит в области, 0 не лежит. Добавляем вершину 2 и
точку пересечения B. После последнего шага, таким образом, получили
корректный результат отсечения - полигон с вершинами A, 1, 2, B.
</ul>

<p>В случае, когда надо сделать отсечение в экран, последовательно применяем
алгоритм, отсекая полигон прямыми sx=0, sx=XSIZE, sy=0, sy=YSIZE. Из-за
такого простого вида уравнений прямых соответственно упрощается код для
выяснения принадлежности вершины нужной области и поиска точки пересечния.
Вот, например, кусок кода для отсечения полигона прямой sx=0 (оставляющий
область sx > 0).

<pre class=source>
// dst - массив для сохранения вершин результата
// src - массив вершин исходного полигона
//   n - число вершин исходного полигона
// функция возвращает число вершин результата
int clipLeft(vertex *dst, vertex *src, int n) {
  int i, r;
  vertex p1, p2;
  float k;

  r = 0;
  for (i = 0; i < n; i++) {
    p1 = src[i];
    p2 = src[(i + 1) % n];

    // если начало лежит в области
    if (p1.sx >= 0) {
      // если конец лежит в области
      if (p2.sx >= 0) {
        // добавляем начало
        dst[r++] = p1;
      } else { // если конец не лежит в области
        // добавляем начало
        dst[r++] = p1;

        // добавляем точку пересечения
        k = -p1.sx / (p2.sx - p1.sx);
        dst[r].sx = 0;
        dst[r].sy = p1.sy + k * (p2.sy - p1.sy);
        dst[r].u = p1.u + k * (p2.u - p1.u);
        dst[r].v = p1.v + k * (p2.v - p1.v);
        r++;
      }
    } else { // если начало не лежит в области
      // если конец лежит в области
      if (p2.sx >= 0) {
        // добавляем точку пересечения
        k = -p1.sx / (p2.sx - p1.sx);
        dst[r].sx = 0;
        dst[r].sy = p1.sy + k * (p2.sy - p1.sy);
        dst[r].u = p1.u + k * (p2.u - p1.u);
        dst[r].v = p1.v + k * (p2.v - p1.v);
        r++;
      }
    }
  }
  return r;
}
</pre>

<p>Видно, что можно чуточку перемешать код обработки разных случаев, изменить
порядок действий алгоритма и тем самым подсократить исходник, да и сделать
алгоритм проще и понятнее:

<pre class=source>
// dst - массив для сохранения вершин результата
// src - массив вершин исходного полигона
//   n - число вершин исходного полигона
// функция возвращает число вершин результата
int clipLeft(vertex *dst, vertex *src, int n) {
  int i, r;
  vertex p1, p2;
  float k;

  r = 0;
  for (i = 0; i < n; i++) {
    p1 = src[i];
    p2 = src[(i + 1) % n];
    if (p1.sx >= 0) { // если начало лежит в области
      dst[r++] = p1;  // добавляем начало
    }
    // если ребро пересекает границу
    // добавляем точку пересечения
    if (((p1.sx >  0) && (p2.sx < 0)) ||
        ((p2.sx >= 0) && (p1.sx < 0)))
    {
      k = -p1.sx / (p2.sx - p1.sx);
      dst[r].sx = 0;
      dst[r].sy = p1.sy + k * (p2.sy - p1.sy);
      dst[r].u = p1.u + k * (p2.u - p1.u);
      dst[r].v = p1.v + k * (p2.v - p1.v);
      r++;
    }
  }
  return r;
}
</pre>

<p>Написав аналогичные куски кода для остальных трех сторон экрана, получим
функцию отсечения в экран по алгоритму Сазерленда-Ходжмана.

<a name="363"></a>
<p class=title><img src="../img/b3.gif" width=70 height=70 align=left hspace=0 alt=""><img src="../img/t.gif" width=5 height=70 align=left hspace=0 alt="">3.6.3. 3D-отсечение

<p>В пунктах <a href="#361">3.6.1</a> и <a href="#362">3.6.2</a> делался упор на 2D-отсечение, т.е. отсечение экраном
уже спроецированного полигона. Еще один метод - это 3D-отсечение, когда все
полигоны отсекаются областью зрения камеры. В этом случае после проецирования
полигон заведомо попадает в экран и дальнейшее отсечение уже не требуется.
Кстати, z-отсечение при 3D-отсечение делается почти автоматически, очень
хорошо вписываясь в общую схему, при использовании же 2D-отсечения придется
делать еще и его.

<p>Рассмотрим стандартную камеру. Ее область зрения задается "пирамидой",
ограниченной пятью плоскостями со следующими уравнениями (откуда взялось
smallvalue и что это такое, написано в <a href="35.htm">п.3.5</a>):

<p class=expression>
z = -dist + smallvalue<br>
y =  (z + dist) * ySize / (2 * dist)<br>
y = -(z + dist) * ySize / (2 * dist)<br>
x =  (z + dist) * xSize / (2 * dist)<br>
x = -(z + dist) * xSize / (2 * dist)<br>

<p>Вот рисунок (вид сбоку), на котором видно первые три из этих плоскостей.

<p><center><img src="illu/illu36b.gif" width=180 height=180 alt="рисунок (illu/illu36b.gif)"></center>

<p>Отсекаем полигон каждой из этих плоскостей по тому же самому алгоритму
Сазерленда-Ходжмана, получаем 3D-отсечение.

<p>Теперь выясним, как это самое отсечение сделать относительно универсально
(а не только для стандартной камеры), быстро и просто. Зададим наши пять
плоскостей не в форме какого-то уравнения, а в форме

<p class=expression>plane = [o, n],

<p>где o - какая-то точка, принадлежащая плоскости; n - нормаль, смотрящая в
то полупространство, которое мы хотим оставить. Например, для стандартной
камеры в этом случае плоскости запишутся так:

<p class=expression><table align=center cellspacing=0 cellpadding=0 border=0>
<tr><td>n = (0, 0, 1),           </td><td> o = (0, 0, -dist + smallvalue)</td></tr>
<tr><td>n = (0, -dist, ySize/2), </td><td> o = (0, 0, -dist)</td></tr>
<tr><td>n = (0,  dist, ySize/2), </td><td> o = (0, 0, -dist)</td></tr>
<tr><td>n = (-dist, 0, xSize/2), </td><td> o = (0, 0, -dist)</td></tr>
<tr><td>n = ( dist, 0, xSize/2), </td><td> o = (0, 0, -dist)</td></tr>
</table>

<p>При такой форме задания плоскости критерий принадлежности произвольной точки
p нужному нам полупространству выглядит очень просто:

<p class=expression>(p - o) * n >= 0.

<p>Не менее просто выглядит и процедура поиска пересечения отрезка от точки p1
до точки p2 с плоскостью. Для любой точки p внутри отрезка имеем

<p class=expression>p = p1 + k * (p2 - p1), 0 <= k <= 1,

<p>но так как p лежит в плоскости, p * n = 0; отсюда имеем

<p class=expression>(p1 * n) + (k * (p2 - p1) * n) = 0,<br>
k = -((p2 - p1) * n) / (p1 * n) = (p1 * n - p2 * n) / (p1 * n) = 1 - (p2 * n) / (p1 * n).<br>

<p>и моментально находим точку пересечения. Все 3D-отсечение, таким образом,
сводится к последовательному применению одной универсальной процедуры
отсечения плоскостью. Кроме того, видно, что можно посчитать матрицу перевода
стандартной камеры в произвольную, применить ее к выписанным точкам o и
нормалям n для плоскостей, задающих "стандартную" область зрения (к нормалям,
естественно, надо применить только "поворотную" часть матрицы) и получить,
таким образом, уравнения плоскостей уже для *любой* камеры. Тогда 3D-отсечение
можно сделать вообще до всяческих преобразований сцены, минимизировав, таким
образом, количество поворотов и проецирований вершин - не попавшие в область
зрения вершины поворачивать и проецировать, очевидно, не надо. Проецирования
невидимых вершин, впрочем, можно избежать и другим образом: сделав поворот
сцены, а потом 3D-отсечение "стандартной" областью зрения камеры.

<p>Рассмотрим это более подробно. Пусть у нас есть какая-то камера; пусть есть
матрица, которая переводит стандартную камеру в эту камеру. Она как бы состоит
из двух частей: матрицы T (обозначения здесь использутся те же самые, что в
<a href="25.htm">п.2.5</a>) и матрицы параллельного переноса, совмещающей Ss и s (обозначим ее
буквой M). Причем сначала применяется матрица M, потом матрица T. Так вот,
для перевода какой-то плоскости-ограничителя области зрения стандартной
камеры, заданной в форме plane = [o,n], надо всего лишь сделать пару
матричных умножений (поскольку M - матрица переноса, и ее применение на деле
сводится к трем сложениям, матричных умножений будет ровно два):

<p class=expression>new_o = T * M * std_o<br>
new_n = T * std_n<br>

<p>Что лучше и быстрее, как обычно, не ясно. При отсечении до преобразований
тест на попадание точки в область зрения стоит от 3 до 15 умножений
(относительно дешевые операции типа сложений не считаем), плюс 11 умножений
и 2 деления на поворот и проецирование после отсечения, зато поворачиваются
и проецируются только видимые точки. При отсечении после преобразований
тест стоит 8 умножений (так как в координатах нормалей шесть нулей и одна
единица), зато для всех точек придется сделать 9 умножений для поворота;
проецироваться же по-прежнему будут только видимые точки. Так что наиболее
подходящий метод выбирайте сами.

<p>В завершение осталось только привести процедуру для отсечения полигона
произвольной плоскостью:

<pre class=source>
// вычитание векторов
float vecsub(vertex *result, vertex a, vertex b) {
  result->x = a.x - b.x;
  result->y = a.y - b.y;
  result->z = a.z - b.z;
}

// скалярное умножение векторов
float vecmul(vertex a, vertex b) {
  return a.x * b.x + a.y * b.y + a.z * c.z;
}

// dst - массив для сохранения вершин результата
// src - массив вершин исходного полигона
// num - число вершин исходного полигона
//   n - нормаль к плоскости
//   o - точка, лежащая в плоскости
// функция возвращает число вершин результата
int clipPlane(vertex *dst, vertex *src, int num,
  vertex n, vertex o)
{
  int i, r;
  vertex p1, p2, tmp;
  float t1, t2;
  float k;

  r = 0;
  for (i = 0; i < num; i++) {
    p1 = src[i];
    p2 = src[(i + 1) % num];
    vecsub(&tmp, p1, o); t1 = vecmul(tmp, n);
    vecsub(&tmp, p2, o); t2 = vecmul(tmp, n);
    if (t1 >= 0) {   // если начало лежит в области
      dst[r++] = p1; // добавляем начало
    }
    // если ребро пересекает границу
    // добавляем точку пересечения
    if (((t1 >  0) && (t2 < 0)) ||
        ((t2 >= 0) && (t1 < 0)))
    {
      k = 1 - vecmul(p1, n) / vecmul(p2, n);
      dst[r].x = p1.x + k * (p2.x - p1.x);
      dst[r].y = p1.y + k * (p2.y - p1.y);
      dst[r].z = p1.z + k * (p2.z - p1.z);
      dst[r].u = p1.u + k * (p2.u - p1.u);
      dst[r].v = p1.v + k * (p2.v - p1.v);
      r++;
    }
  }
  return r;
}
</pre>

</div>
</td></table>

<!-- Bottom Navigation -->

<img src="../img/b.gif" width=500 height=1 alt=""><br><img src="../img/t.gif" width=500 height=2 alt=""><br>
<table width=500 cellpadding=0 cellspacing=0 border=0>
<td><img src="../img/t.gif" width=5 height=1 alt=""><a href="../main.htm" onmouseover="swap('logo2','../img/xe.gif');" onmouseout="swap('logo2','../img/e.gif');"><img src="../img/e.gif" name=logo2 width=60 height=50 hspace=10 border=0 alt=" в самое начало "></a></td>
<td><p class=pagetitle><img src="../img/t.gif" width=265 height=1 alt=""><br>demo.design<br>3D programming FAQ</td>
<td align=center><p class=navy><a href="35.htm" onmouseover="swap('prev','../img/xprev.gif');" onmouseout="swap('prev','../img/prev.gif');"><img src="../img/prev.gif" name=prev width=40 height=40 border=0 hspace=5 alt=" предыдущая статья "></a><br>previous</td>
<td align=center><p class=navy><a href="../content.htm" onmouseover="swap('faq','../img/xfaq.gif');" onmouseout="swap('faq','../img/faq.gif');"><img src="../img/faq.gif" name=faq width=40 height=40 border=0 hspace=5 alt=" содержание "></a><br>content</td>
<td align=center><p class=navy><a href="41.htm" onmouseover="swap('next','../img/xnext.gif');" onmouseout="swap('next','../img/next.gif');"><img src="../img/next.gif" name=next width=40 height=40 border=0 hspace=5 alt=" следующая статья "></a><br>next</td>
</table>
<img src="../img/t.gif" width=500 height=4 alt=""><br>
<img src="../img/b.gif" width=500 height=1 alt=""><br>
<img src="../img/t.gif" width=500 height=1 alt=""><br>
<img src="../img/b.gif" width=500 height=1 alt=""><br>


</center></body>
</html>