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.