Demo or Die #01 28 февраля 1999

Программирование

Demo-Building - an algorithm to PROCESSING visibility of surfaces 3D-figup.

__________________________________________


   (C) by Wolf of Etc group / Scene

Processing algorithms face visibility

                3D-shapes.


   1. The method of the first (for the convex faces).


   Face is convex if
interior angle at each vertex is not
more than 180 degrees.

   In this algorithm, the object must
be defined as an array of face [len1]
numbered points that are connected
edges. The following array of points [len2]
should contain the coordinates of the points
which are numbered in the previous array
face [len1].


   Example:


     Array of points:

     points [] = {

                x1, y1, z1,

                x2, y2, z2,

                ...

                x12, y12, z12

              }


     An array of faces:

     face [] = {

                1,2,6,4,

   ; Number of points constituting 4 coal

   ; Face

                2,3,4,7,

                ...


            }


   The order of traversal points that describes
face is very important. When it is selected
must adhere to the following
principles:

   Fringe is described towards
clockwise or counterclockwise, in order
that-be in passing along the edge of one
point P1 to P2 face has always been
left to the direction of the vector
transition (the truth is inconvenient?).

   But she had hidden processing of faces
based on the fact that for a convex
object from any point of view of each facet
or seen, or not completely visible.

   Decision about the visibility of faces taken
Based on analysis of the plane in which
is bound (analytical methods
geometry). To do this, take the first three
point of the array that describes the brink
(Which must be checked for
visibility). Their coordinates have to be already
two-dimensional (as translated in 2D, please read
Article 3D-> 2D).

   Let the coordinates are as follows:

   (X1, y1), (x2, y2), (x3, y3).

   Then, if the determinative
(Determinant) of this matrix:


            x3-x1 x2-x1

      D =

            y3-y1 y2-y1


   is negative, then the face
is visible.

   For those who do not know how to be considered
determinative, here's a formula for
the previous matrix:


   D = (x3-x1) * (y2-y1) - (x2-x1) * (y3-y1);


   2. The method of the second (sort of faces).


   This method is based on sorting
faces of three-dimensional object.

   This method is a simple but
At the same time one of the most ill in
some cases.

   The method is based on the fact that when drawing
on-screen object to be sorted
his face from the mean value
coordinate Z. From this it follows that if
object consists of a triangular faces, then
average value should be considered as
(Z1 + Z2 + Z3) / 3, where Z1, Z2, Z3 - Z coordinate
angles of the face. The axis Z, must be
directed into the screen. When the face
will be sorted, you must withdraw
verge of three-dimensional object from the most
distant relative coordinate Z. So
that all the faces will come to conclusions without
regardless of whether it is completely invisible
or only part of it.


   3. METHODS third (Z-buffer).


   This method is the simplest and
most importantly correct, but since
No nothing in the world ideal, this method
is also the most inhibitory.

   The method is that we
necessary to calculate the Z coordinate for
each point of the face. Ie if you do
texture mapped, it must also
interpolate and coordinate Z.

   So, we distinguish two arrays: an array of
(Z-buffer) and an array of color pixels
(Buffer), whose dimensions should
match the size of the screen to be
drawn three-dimensional objects and zabem
array Z-buffer in some large number.
For each point of view drawn in
Z-coordinate and verify its value with
value in the z-buffer'e if it is more
do not draw this point, and if less,
Draw in the buffer and a Z-set buffer'e
Z-coordinate of this point. And so for all
faces. And then we deduce from buffer'a on
screen.

   That's it. As you can see a big
Brake: (


   ps: In the next issue of demo or
die # 2, I will tell you about
Some of the accelerated algorithms
sort that will help you
Sort your face three-dimensional
objects.
__________________________________________