Node: Surface Hiding, Previous: Focuses Getstart, Up: Pictures

### Surface Hiding

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.