In [next figure]
, `Circle`

`c` lies in front of `Rectangle`

`r`.
Since `c` is drawn and not filled, `r` is visible behind
`c`.

default_focus.set(1, 3, -5, 0, 3, 5, 10); Point p(0, -2, 5); Rectangle r(p, 3, 4, 90); r.draw(); Point q(2, -2, 3); Circle c(q, 3, 90); c.draw(); current_picture.output();

Fig. 64.

If instead, `c` is filled or filldrawn, only the parts of `r` that are not
covered by `c` should be visible:

r.draw(); c.filldraw();

Fig. 65.

What parts of `r`

are covered depend on the point of view, i.e.,
the position and direction of the `Focus`

used for outputting the
`Picture`

:

default_focus.set(8, 0, -5, 5, 3, 5, 10);

Fig. 66.

Determining what objects cover other objects in a program for 3D graphics is called surface hiding, and is performed by a hidden surface algorithm. 3DLDF currently has a very primitive hidden surface algorithm that only works for the most simple cases.

The hidden surface algorithm used in 3DLDF is a
painter's algorithm, which means that the objects that are
furthest away from the `Focus`

are drawn first, followed by the
objects that are closer, which may thereby cover them. In order to make
this possible, the `Shapes`

on a `Picture`

must be sorted
before they are output. They are sorted according to the z-values in
the `projective_coordinates`

of the `Points`

belonging to the
`Shape`

. This may seem strange, since the
projection is two-dimensional and only the x and y-values from
`projective_coordinates`

are written to `out_stream`

.
However, the perspective transformation also produces a z-coordinate,
which indicates the distance of the `Points`

from the `Focus`

in the z-dimension.

The problem is, that all `Shapes`

, except `Points`

themselves,
consist of multiple `Points`

, that may have different
z-coordinates. 3DLDF currently does not yet have a satisfactory way of
dealing with this situtation. In order to try to cope with it, the user
can specify four different ways of sorting the `Shapes`

: They
can be sorted according to the maximum z-coordinate, the
minimum z-coordinate, the mean of the maximum and minimum z-coordinate
(max + min) / 2,
and not sorted.
In the last case, the `Shapes`

are output in the order of the
drawing and filling commands in the user code.
The z-coordinates referred to are those in
`projective_coordinates`

, and will have been calculated for a
particular `Focus`

.

The function `Picture::output()`

takes a
`const unsigned short`

`sort_value` argument that specifies
which style of sorting
should be used. The namespace `Sorting`

contains the following
constants which should be used for `sort_value`: `MAX_Z`

,
`MIN_Z`

, `MEAN_Z`

, and `NO_SORT`

. The default is
`MAX_Z`

.

3DLDF's primitive hidden surface algorithm *cannot* work for
objects that intersect. The following examples demonstrate why not:

using namespace Sorting; using namespace Colors; using namespace Projections; default_focus.set(5, 3, -10, 3, 1, 1, 10, 180); Rectangle r0(origin, 3, 4, 45); Rectangle r1(origin, 2, 6, -45); r0.draw(); r1.draw(); current_picture.output(default_focus, PERSP, 1, MAX_Z); r0.show("r0:"); -| r0: fill_draw_value == 0 (-1.5, -1.41421, -1.41421) -- (1.5, -1.41421, -1.41421) -- (1.5, 1.41421, 1.41421) -- (-1.5, 1.41421, 1.41421) -- cycle; r0.show("r0:", 'p'); -| r0: fill_draw_value == 0 Perspective coordinates. (-5.05646, -4.59333, -0.040577) -- (-2.10249, -4.86501, -0.102123) -- (-1.18226, -1.33752, 0.156559) -- (-3.51276, -1.2796, 0.193084) -- cycle; r1.show("r1:"); -| r1: fill_draw_value == 0 (-1, 2.12132, -2.12132) -- (1, 2.12132, -2.12132) -- (1, -2.12132, 2.12132) -- (-1, -2.12132, 2.12132) -- cycle; r1.show("r1:", 'p'); -| r1: fill_draw_value == 0 Perspective coordinates. (-5.09222, -0.995681, -0.133156) -- (-2.98342, -1.03775, -0.181037) -- (-1.39791, -4.05125, 0.208945) -- (-2.87319, -3.93975, 0.230717) -- cycle;

Fig. 67.

In [the previous figure]
, the `Rectangles`

r_0 and r_1 intersect along the
x-axis. The z-values of the `world_coordinates`

of r_0 are
-1.41421 and 1.41421 (two `Points`

each), while those of r_1
are 2.12132 and -2.12132. So r_1 has two `Points`

with
z-coordinates greater than the z-coordinate of any `Point`

on r_0, and two `Points`

with z-coordinates less than the
z-coordinate of any `Point`

on r_0. The
`Points`

on r_0 and r_1 all have different z-values in
their `projective_coordinates`

, but r_1 still has a `Point`

with a z-coordinate greater than that of any of the `Points`

on
r_0, and one with a z-coordinate less than that of any of the
`Points`

on r_0.

In [next figure]
, the `Shapes`

on `current_picture`

are sorted
according to the maximum z-values of the `projective_coordinates`

of the `Points`

belonging to the `Shapes`

. r_1 is
filled and drawn first,
because it has the `Point`

with the positive z-coordinate of
greatest magnitude.
When subsequently r_0 is drawn, it covers part of the top of
r_1, which lies in front of r_0, and should be visible:

current_picture.output(default_focus, PERSP, 1, MAX_Z);

Fig. 68.

In [next figure]
, the `Shapes`

on `current_picture`

are sorted
according to the minimum z-values of the `projective_coordinates`

of the `Points`

belonging to the `Shapes`

. `r1`

is drawn
and filled last, because
it has the `Point`

with the negative z-coordinate of greatest
magnitude.
It thereby covers the bottom part of
`r0`

, which lies in front of `r1`

, and should be visible.

current_picture.output(default_focus, PERSP, 1, MIN_Z);

Fig. 69.

Neither sorting by the mean z-value in the
`projective_coordinates`

, nor suppressing sorting does any good.
In each case, one `Rectangle`

is always drawn and filled last,
covering parts of the other that lie in front of the first.

3DLDF's hidden surface algorithm will fail wherever objects intersect, not just where one extends past the other in both the positive and negative z-directions.

Rectangle r(origin, 3, 4, 45); Circle c(origin, 2, -45); r.filldraw(); c.filldraw(black, gray); current_picture.output(default_focus, PERSP, 1, NO_SORT);

Fig. 70.

Even where objects don't intersect, their projections may. In order to
handle these cases properly, it is necessary to break up the
`Shapes`

on a `Picture`

into smaller `Shapes`

, until
there are none that intersect or whose projections intersect. Then, any
of the three methods of sorting described above can be used to sort the
`Shapes`

, and they can be output.

Before this can be done, 3DLDF must be able to find the intersections of
all of the different kinds of `Shapes`

. If 3DLDF converted solids
to polyhedra and curves to sequences of line segments, this would reduce
to the problem of finding the intersections of lines and planes, however
it does not yet do this.

Even if it did, a fully functional hidden surface algorithm must compare
each `Shape`

on a `Picture`

with every other `Shape`

.
Therefore, for n `Shapes`

, there will be
n! / ((n - r)! r!)
(possibly time-consuming) comparisons.

Fig. 71.

Clearly, such a hidden surface algorithm would considerably increase run-time.

Currently, all of the `Shapes`

on a `Picture`

are output, as
long as they lie completely within the boundaries passed as arguments to
`Picture::output()`

.
See Pictures; Outputting. It
would be more efficient to suppress output for them, if they are
completely covered by other objects. This also requires comparisions,
and could be implemented together with a fully-functional hidden surface
algorithm.

Shadows, reflections, highlights and shading are all effects requiring
comparing each `Shape`

with every other `Shape`

, and could
greatly increase run-time.