Close

Hidden Surface Elimination

A project log for Supercon Badge Surface Plotter

Firmware hack for real-time animated 3D surfaces

ted-yapoTed Yapo 11/07/2018 at 21:102 Comments

This is a technique straight out of the 1980s.  I read about it in BYTE Magazine, and remember writing quick versions of it in BASIC whenever I was bored somewhere there was a computer - like in a store or during a college physics lab.

EDIT: I found it! Read the original article here: BYTE Magazine, Vol 03, No 05, May 1978, pp.50-58. I love the freakin' Interwebs.

I created this example in python using matplotlib to illustrate the method.  Lines are drawn parallel to the x-axis from front to back, and the screen y-coordinate is calculated from the surface height and the surface's y-parameter using a simple orthographic projection (described below). For each column, a minimum and maximum drawn y-value is stored.  This represents the bounds of the previously drawn surface.  Any parts of new lines which fall within these bounds are hidden (i.e. behind the surface already drawn) and are discarded.  When new points are drawn, the minimum and maximum values are updated.  Note that the terms minimum and maximum here refer to pixel coordinates, so the y value increases as you move down on the figure.

This method also identifies the top and bottom sides of the surface - points drawn below the maximum y-value are on the underside of the surface (colored magenta), while points drawn above the minimum y-value are on the top side of the surface (colored green).

Although drawing the whole line at a time works well for illustrating the method, the badge code draws the image left-to right, calculating all the pixels in the first column before moving on to the second, etc.  This has several benefits - first, during animations, complete columns of the new frame quickly replace those of the previous one, reducing annoying visual tearing.  Second, by storing the previous locations that were plotted at each column, only those pixels previously drawn on a column need to be cleared.  This eliminates the need to clear 240 pixels when only perhaps 30 have been drawn.  More about this in a future log.

Orthographic Projection

The projection from 3D (x, y, z) to 2D (col, row) is a simple orthographic view.  This kind of projection doesn't show perspective, but is dead-simple to generate.  This is illustrated in the following figure:

Here, three lines on the surface are shown in 3-space (gray lines).  The x-y surface has been tilted by rotating around the x-axis slightly.  The resulting points are then projected onto the screen by simply dropping the 3D y-coordinate and using the rotated z-coordinate as the vertical pixel coordinate (what we think of as the y- or row coordinate).  It may be easier to visualize in this view:

From the side, you can see how the 3D surface has been tilted slightly towards the screen, and the projection is simply along lines parallel to the 3D y-axis.

In a previous log, I showed the code for setting the projection angle:

#define ang 10.
int16_t cs_ang = FP(0.98481); //FP(cos(ang*3.141592653/180.));
int16_t sn_ang = FP(0.17365); //FP(sin(ang*3.141592653/180.));

The values for sin() and cos() of the 10-degree angle were pre-calculated and pasted into the C-code.  These values are then used to project the y- and z-coordinate values of surface points into rows of the badge display:

uint16_t row = 120 - (((((int32_t)y * sn_ang)>>S)+
                       (((int32_t)z * cs_ang)>>S))>>3);
 

The constant 120 centers the surface on the 240-pixel high screen, and the value is negated because the screen row coordinates increase as you move down (opposite from mathematical coordinate convention).  This equation simply tilts the 3D x-y plane as shown in the diagrams above.  The divide-by-8 (>>3) just scales the function to fit the display properly.

Discussions

Yann Guidon / YGDES wrote 11/08/2018 at 00:01 point

Damnit.... I start to understand !

  Are you sure? yes | no

Ted Yapo wrote 11/08/2018 at 01:38 point

I get that feeling sometimes ... it usually passes quickly :-)

  Are you sure? yes | no