Streaking the Stars
After the location and size for each star streak polygon has been computed, the next thing that has to be done is to actually draw each star streak on the HI. This is accomplished for each star by drawing one anti-aliased line shaped polygon that begins at the star's startling location on the HI and ends at the edge of the HI.
Remember, all the discussion below must be repeated for each line segment that must be drawn on the HI. Before the drawing of a variable thickness anti-aliased line segment on the HI can begin, the HGP must first determine on which pixels of the HI the polygon is going to be drawn on. The approach I'm going to use is actually based on my own custom raster polygon scan conversion algorithm.
Scan Converting the Star Streak Polygons
Polygon scan conversion, i.e. PSC, is a technique that's normally used to do things like paint texture mapped polygons onto a display screen during the playing of a polygonal based computer game. I however, am going to use this technique to identify the pixels on the HI that need to be considered for polygonal anti-aliasing. Then for each pixel identified by PSC, the hyerspace polygon will then be clipped against the pixel's area on the screen. When the hyerspace polygon is clipped against this pixel, what results from this process is another polygon which is completely contained within the pixel's square boundaries. We then figure out what percentage of area this new polygon overlaps the pixel's unit area. This 0-100 percentage is then scaled into a pixel intensity value from 0-255. It is 0-255 pixel intensity that is then assigned for this pixels screen intensity.
For example, if the polygon completely overlaps the pixel, then the pixel's color on the HI will be set to completely white, i.e. 255. If the pixel only overlaps the polygon, say 50%, then the corresponding pixel on the HI will be set to a medium gray, i.e. 128. By continuing this process for every identified pixel of every hyperspace polygon in the image, I will be able to build up the final anti-aliased hyperspace image.
The procedure to scan convert a star streak polygon basically works by finding pairs of polygon edges within that overlap each other along the Y axis. Any edge can overlap up to two other edges in the polygon. When the program finds two edges that overlap, the program records which two edges overlap along with the region of the Y axis overlap between them. See the below example.
Image
Once the program has identified all mutually exclusive overlap regions within a polygon, in the above example there are three, the program then evaluates each of the overlap regions separately. For each overlap region, the program starts at the highest scanline in the region and proceeds down each scanline until the bottom of the overlap region is reached. At each scanline, the program shoots two horizontal lines, one across the top of the scanline and one across the bottom of the scanline. Where these two lines intersect the two polygon edges defining the overlap region, we get four X coordinate values. We then find the minimum and maximum X coordinates out of these four values. The Y scanline coordinate along with the min and max X coordinates define a range of pixels on the HI that will then be feed into the anti-aliasing algorithm one pixel at a time. See the below picture.
Image
Now in actuality, after the first scanline in each overlap region has been processed, only the bottom horizontal line needs to be fired at the overlap edges of later scanlines since the X coordinates of the bottom horizontal line of the previous scanline can be used as the top horizontal line X coordinates of the next scanline. Doing this cuts out unnecessary computations. As you can see from above, sorting of the two edges within an overlap region is unnecessary since we are only interested in the min and max X coordinates of the four intersections.
Last Updated: April 25, 2000
HTML URL: http://geocities.datacellar.net/~special_effect/hyperspace_ss.html
E-Mail: special_effect@geocities.com or click here