Abstract:
Accurate display of line stipple in line segments, situated off the vertical or horizontal planes, is achieved by employing a calculated constant as a slope correction factor. The calculated constant, termed line style count, is determined utilizing the absolute length of the line segment, a ratio implementing the absolute length of the line segment, the major axis component of the line segment and fraction bits in the line counter. For each step along the major axis on a data processing system display, a constant value of 1.0 and the calculated constant, line style count, is added to a line style pointer to slope correct line stipple. A pre-computed square-root table is stored in texture memory and accessed for pre-calculated values to assist in reducing the time required to calculate accurate line style pointers. A standard Bresenham line steps the line counter for every step along the major axis, so that the corrected line style count equals the ratio of the true line length and the rasterized (major axis) length.

Description:
BACKGROUND OF THE INVENTION 
     1. Technical Field 
     The present invention relates in general to CAD/CAM applications in data processing systems and in particular to methods and systems for display of CAD/CAM drawings. Still more particularly, the present invention relates to a method and system for correction of stippled lines utilized in CAD/CAM drawings and display accuracy of the line. 
     2. Description of the Related Art 
     Data processing Systems that are primarily employed for graphics processes are used in many different areas of industry, business, education, home and government. Graphics applications for these systems are growing rapidly and include interactive planning, office automation, electronic publishing, animation and computer-aided design. The applications are developed utilizing various software “tools” that best work with the available data processing system hardware. 
     Computer Aided Design/Computer Aided Manufacturing (“CAD/CAM”) is utilized to assist in preparing drawings to assist in design and building models of potential products. CAD/CAM plays a great part in providing drawings and assisting in manufacturing components of electrical, mechanical and electromechanical items such as automobile engines, draw works, oil well drilling rigs, high rise buildings, micro-processor devices and including airplanes, ships and space vehicles. Often the designs are implemented via drafting or blueprints. However, the designs are often utilized, interactively on a computer display, to determine possible physical properties of design elements by subjecting an on-line display model to various virtual stresses. By simulating actual conditions through virtual testing on a computer terminal, a design may be pre-tested without having to actually build the final product. It is important that the CAD design be accurate and rendered in sufficient detail to provide reliable results of the on-line testing. 
     CAD/CAM applications and draftspersons use stippled (“styled”) lines to indicate specific drawing details. Stippled lines are lines comprised of different combinations of dashes and dots where each combination illustrates a particular type of view in a drawing. For example, in a drawing, one dashed line may indicate a hidden edge within a solid. Another dashed line may indicate a centerline of the same object. If the dashes are distorted, the lines may be confused. Therefore, it is important that the line stipple (“style”) be easily distinguishable from other line styles. 
     On computer graphics systems, a line style is typically defined by a sequence of ones and zeroes. The line style is displayed on a video screen as a pattern of light (“on”) and dark (“off”) pixels in a rectangular array (“raster display”) and identified by the number of on and off pixels (for example, 24 pixels on, 8 pixels off). Line rasterization is performed utilizing a Bresenham (developer of the technique) line drawing technique in which the line is rasterized with respect to its major axis (the axis in which the distance between its endpoints is largest). For each step along the major axis, a pixel is rendered (light, dark and sometimes shaded) and the line style pointer (a marker indicating the current position within the line style pattern) is incremented to point to the next entry in the line style pattern. The rendered pixel is drawn (“on” or shaded) if the current line style pointer points to a one in the pattern and not drawn (“off”) if it points to a zero. 
     Since sequencing is done with respect to the major axis (either X or Y), lines drawn on the diagonal (dX=dY) result in a line style that appears to be 41% longer than the same line drawn horizontal or vertical. Any deviation from true horizontal or true vertical results in a line depicted with increased stipple length. 
     Current industry standard graphics APIs like OpenGL™, a graphics application interface of Silicon Graphics, Inc. of San Jose, Calif., are specified such that anti-aliased, stippled lines should be slope corrected. A stippled line on a display is considered to be a sequence of contiguous rectangles. Each rectangle is a size, in width and length, which is equal to one pixel and each rectangle is centered on the line segment. The rectangles referred to are pixels. To date, most vendors have not implemented slope correction of nominal width lines because of the expense in doing so. 
     In the past, several techniques have been utilized to slope correct a stippled line. One method of slope correction of the line style considered the line style pointer to be a fixed point number with one fractional bit. 
     FIG. 5, a flow diagram illustrating a method for slope correcting line stipples, illustrates this method. 
     The process begins at step  500 , which depicts the application determining the originating and terminating vertex of the line to be slope corrected. The process proceeds to step  502 , which illustrates determining the major and minor axis of the stipple segments within the line, where major axis is the axis with the largest change. The process then passes to step  504 , which depicts the application beginning the procedure to slope correct the line. The process passes next to step  506 , which illustrates adding 1.0 to the line style pointer at the first stipple segment in the line. For every step along the major axis, 1.0 is added to the line style pointer. The process continues to step  508 , which depicts adding 0.5 to the style pointer and for every step along the minor axis, 0.5 is added to a line style counter. The line style count is utilized to step through the line style pattern as stippled lines are rasterized. The process next passes to step  510 , which illustrates repeating the two preceding steps,  506  and  508 , until the terminating vertex of the line is reached. 
     If this procedure is not applied to a line, the length of the individual stipples will appear longer than the true length. This correction technique, albeit very simple to implement, results in line stipples that can still be in error by over 10%. 
     Another known method uses line style assist logic that consists of a count down counter and a shrink/expand control bit. For every step along the major axis, the line style counter is incremented and the count down counter decremented. If the count down counter reaches zero, the counter is reloaded and the line style counter is incremented if shrink control is selected or decremented if expand control is selected. The accurate line style assist logic suffers from significant accuracy problems because not enough precision exists where it is needed the most (when the count down counter is small). 
     It would be desirable, therefore, to provide a method that would utilize presently existing hardware to provide accurate displays of line stipple in lines off the vertical or horizontal planes. 
     SUMMARY OF THE INVENTION 
     It is therefore one object of the present invention to provide a method and system to slope correct line stipples. 
     It is another object of the present invention to provide a method and system of slope correction that utilizes currently available hardware. 
     It is a further object of the present invention to provide a method and system of slope correction that produces displays of line styles that are accurate. 
     The foregoing objects are achieved as is now described. Accurate display of line stipple in line segments, situated off the vertical or horizontal planes, is achieved by employing a calculated constant as a slope correction factor. The calculated constant, termed line style count, is determined utilizing the absolute length of the line segment, a ratio implementing the absolute length of the line segment, the major axis component of the line segment and fraction bits in the line counter. For each step along the major axis on a data processing system display, a constant value of 1.0 and the calculated constant, line style count, is added to a line style pointer to slope correct line stipple. A pre-computed square-root table is stored in texture memory and accessed for pre-calculated values to assist in reducing the time required to calculate accurate line style pointers. A standard Bresenham line steps the line counter for every step along the major axis, so that the corrected line style count equals the ratio of the true line length and the rasterized (major axis) length. 
     The above, as well as additional objects, features, and advantages of the present invention will become apparent in the following detailed written description. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself however, as well as a preferred mode of use, further objects and advantages thereof, will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein: 
     FIG. 1 depicts a high level block diagram of a graphics application architecture stack and related portions of a data processing system, in which a preferred embodiment of the present invention may be implemented; 
     FIGS. 2A-2C are illustrations of display patterns with different degrees and methods of slope correction, where FIG. 2A depicts a resultant display generated by a preferred embodiment of the present invention; 
     FIG. 3 depicts a high level logic flow diagram for slope correcting line stipples in accordance with the method of the present invention; 
     FIG. 4 depicts a second embodiment wherein a correction look-up table is substituted for the dynamic calculations in accordance with the method of the present invention; and 
     FIG. 5 is a flow diagram illustrating a prior art method for slope correcting line stipples. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     With reference now to the figures, and in particular with reference to FIG. 1, a high level block diagram of a graphics application architecture stack and related portions of a data processing system, in which a preferred embodiment of the present invention may be implemented, are depicted. Graphics application architecture stack  100  is a typical example of application hierarchy in graphics focused data processing systems. Hardware  102  includes, among other elements, a system bus, graphics card, processor, video processor, main memory and a display (all not shown). Application  104  and the related software modules usually reside on the data processing system disk drive (not shown) or network hard drive (not shown). 
     Application  104  is a program that is typically utilized to perform a specialized task. Examples include CAD programs, animation programs and space planning programs. API is an acronym that stands for Application Programming Interface and includes subroutines, functions and methods that are available to application  104 . High-level API  106  is an API that performs very high functions and often market specific tasks (large model visualization software, for example). Toolkits  108  are graphics utility libraries designed to perform common tasks that are regularly required in the application, such as drawing a block or a sphere. A low-level API is an API that performs rudimentary graphics requests such as drawing a line or drawing a polygon. Low-level API is generally architected into Low-level device independent  110  and Low-level device dependent  112  components. The Low-level device dependent  112  component directly interfaces with graphics hardware  102 . A CAD program, as indicated above, is an example application utilizing graphics application architecture stack  100 . Line drawings are common with CAD programs and generally stippled lines that are displayed are inaccurate and require correction if these lines are not displayed in an orthogonal axis. 
     Turning now to FIGS. 2A-2C, patterns with different degrees and methods of slope correction are illustrated, where FIG. 2A depicts a resultant display generated by a preferred embodiment of the present invention. FIG. 2A is a 360 degree circular pattern of 180 stippled lines. There are two vertical lines (Y axis) and two horizontal lines (X axis). The stipple segments of the lines displayed on the X and Y axes are true length. Additionally, the lines displayed in all the other positions are true length. A circular pattern is an indication that all stipple segments displayed are the same length. 
     Referring now to FIG. 2B, a pattern generated by the prior art method, as described in FIG. 5, is illustrated. As discussed previously the prior art method adds fixed values to the X and Y axes of each stipple segment to arrive at a corrected length. The irregular segment length, although approaching a circular pattern, falls visibly short. The irregularity of the line segments is an indication of unequal stipple segment lengths. 
     Turning to FIG. 2C, a non-slope corrected line pattern of 180 stippled lines is displayed. The two vertical lines (Y axis) and the two horizontal (X axis) lines are of a true length having stipple segments of equal length. Lines displayed that are at an angle to both the horizontal and vertical axes have the same total line length, but the stipple segments are of different lengths. The square pattern generated by the stipple segments is an indicator of a non-slope corrected line. 
     Turning now to FIG. 3, a high level logic flow diagram which depicts a method for slope correcting line stipples in accordance with the method and system of the present invention, is depicted. The process begins with step  300 , which depicts the application determining the originating and terminating vertices for the stippled line segment to be corrected. The process continues with step  302 , which illustrates determination of a value of the line segment length (dx) along the X axis utilizing the equation 
     
       
           dx=abo (v 1 [ x ]−v 2   [   x] ). 
       
     
     In the equation, v 1 [x] is the originating vertex and v 2 [x] is the terminating vertex that defines the segment along the x axis. The process then passes to step  304 , which depicts determination of the value of the stipple segment length (dy) along the Y axis utilizing the equation 
     
       
           dy=abs (v 1 [ y ]−v 2 [ y ]). 
       
     
     In this equation, v 1 [y] is the originating vertex and v 2 [y] is the vertex that defines the segment along the y axis. 
     After the values are determined, the process next passes to step  306 , which illustrates comparison of the values of dx and dy. If dx is greater than dy, the process then proceeds to step  308 , which depicts assignment of the segment dx to dmajor, where dmajor is the major axis component of the line segment along the axis (horizontal or vertical) in which the line has the greatest change. The line segment dy is assigned to dminor, which is the minor axis component of the line segment along axis (horizontal or vertical) of smallest change. The process then passes to step  312 , which illustrates calculation of the absolute length of the line segment, len, utilizing the equation 
     
       
           len=sqrt ( dx   2   +dy ), 
       
     
     where sqrt is the mathematical square root. The process then continues to step  314 , which depicts the calculation of the line style count utilizing the equation 
     
       
         line_style_count=(1&lt;&lt;COUNT_BITS)*(( len −dmajor)/dmajor)+0.5), 
       
     
     where COUNT_BITS is the number of fraction bits in the line style counter. The process then passes to step  316 , which depicts the addition of 1.0 and the calculated line style count to the line style pointer to arrive at a consistent stipple length regardless of the orientation. 
     Referring back to step  306 , if dx is not greater than dy, then the process proceeds instead to step  310 , which illustrates the axis component dy assigned to dmajor and axis component dx assigned to dminor. The process next passes to step  312 , which illustrates the calculation of the absolute length of the line segment (len) utilizing the equation 
     
       
           len=sqrt ( dx   2   +dy   2 ), 
       
     
     where sqrt is the mathematical square root. The process then continues to step  314 , which depicts the calculation of the line style count utilizing the equation 
     
       
         line_style_count=(1&lt;&lt;COUNT_BITS)*(( len −dmajor)/dmajor)+0.5), 
       
     
     where COUNT_BITS is the number of fraction bits in the line style counter. The process then passes to step  316 , which depicts the addition of 1.0 and the calculated line style count to the line style pointer to arrive at a consistent stipple length regardless of the orientation. Computations to determine the line style count are indicated below: 
     
       
           dx=abs (v 1 [ x ]−v 2 [ x];   (1) 
       
     
     
       
           dy=abs [v 1 [ y ]−v 2 [ y];   (2) 
       
     
     
       
         if( dx&gt;dy ) dmajor= dx ; dminor= dy;   (3) 
       
     
     
       
         else dmajor= dy;  dminor= dx;   (4) 
       
     
     
       
           len=sqrt ( dx   2   +dy   2 );  (5) 
       
     
      line_style_count=(1&lt;&lt;COUNT_BITS)*(( len−dmajor/dminor)− 0.5  ( 6 ) 
     A diagonal line that is non-slope corrected would display stipple segments that would appear up to 41% longer than the horizontal or vertical display of that line. The present invention defines the process of accurately slope correcting the line stipple utilizing currently available hardware and software. It provides a major reduction in the distortion of the visual length of the stipple segments; from 41% to less than 0.2%. 
     Referring now to FIG. 4, a second embodiment wherein a correction look-up table is substituted for the dynamic calculations, described above, in accordance with the present invention, is depicted. The correction look-up table is static and contains pre-computed values that replace calculations of the embodiment of FIG.  3 . The correction look-up table is pre-computed by the following equations for every segment&#39;s slope that may be displayed (i is a loop counter and TABLE_SIZE is the number of entries in the line style count table): 
     
       
         for ( i= 0;  i &lt;=TABLE_SIZE;  i ++) {  (a) 
       
     
     
       
         slope=(float)( i )/TABLE_SIZE;  (b) 
       
     
     
       
           len=sqrt (1.0+slope*slope);  (c) 
       
     
     
       
         lineStyleCountTable[ i ]=( I &lt;&lt;COUNT_BITS)*(length−1.0)+0.5;  (d) 
       
     
     
       
         }  (e) 
       
     
     An index for the table is determined utilizing existing perspective correction logic. The index is determined by the following calculation and entered into the correction look-up table: 
     
       
         index=(TABLE_SIZE*(dminor/dmajor))+0.5 
       
     
     and 
      line_style_count=lineStyleCountTable[index] 
     (pre-computed values correlating to the index). 
     The process for computing values (line_style_count) for entry into the table begins with step  400 , which depicts the determination of the originating and terminating vertices of the line segment to be corrected. The process continues with step  402 , which illustrates the determination of the value of the line segment length (dx) along the X axis utilizing the equation 
     
       
           dx=abs (v 1 [ x ]−v 2 [ x ]). 
       
     
     In the equation, v 1 [x] is the originating vertex and v 2 [x] is the terminating vertex that defines the line segment along the X axis. The process then passes to step  404 , which depicts the determination of the value of the line segment length (dy) along the Y axis utilizing the equation 
     
       
           dy=abs (v 1 [ y ]−v 2 [ y ]). 
       
     
     In the equation, v 1 [y] is the originating vertex and v 2 [y] is the terminating vertex that defines the line segment along the y axis. 
     After the values are determined, the process next passes to step  406 , which illustrates the comparison of the values of dx and dy. If dx is greater than dy, the process proceeds to step  408 , which depicts the assignment of dx to dmajor and dy to dminor. The process then passes to step  412 , which illustrates the acquisition of a pre-computed value corresponding to the relative length of the pre-computed line segment in the correction look-up table stored in texture memory. 
     The process then passes to step  414 , which depicts the addition of 1.0 and the calculated line style count to the line style pointer to arrive at a consistent stipple length regardless of the orientation. 
     Referring back to step  406 , if dx is not greater than dy, the process proceeds instead to step  410 , which illustrates the assignment of dy to dmajor and dx to dminor. 
     The process then passes to step  412 , which illustrates the acquisition of a pre-computed value in the correction look-up table as determined by the coordinates of the vertices determined by step  404  through step  410 . The correction look-up table is a static table stored in texture memory and is pre-computed, by equations discussed above, for line segment slopes that may be displayed. Further, line segment slopes not in the correction table are determined by linear interpolation between table entries, wherein interpolation increases the accuracy of the correction table or allows for a reduced table size. 
     The process then passes to step  414 , which depicts the addition of 1.0 and the calculated line style count to the line style pointer to arrive at a consistent stipple length regardless of the orientation. 
     The correction look-up table embodiment provides additional advantages to the present invention. Looking up a value in the correction look-up table requires less time than calculating the same value. Additionally, the table is available in texture memory and eliminates the need to add processing hardware. Accuracy can be improved from 41% error to an error of less than 0.2% utilizing only 8 bits. 
     Calculations for dmajor and dminor are performed by all current line rasterization hardware. Length and line_style_count calculations are implemented utilizing texture mapping hardware and perspective logic. The correction look-up table is stored as a one dimension texture map. The texture map&#39;s width is TABLE_SIZE and vertices texture coordinates are sourced from internally computed values where S(texture coordinate s/w)=dminor and Q(texture coordinate q/w)=dmajor. 
     It is important to note that while the present invention has been described in the context of a fully functional data processing system, those skilled in the art will appreciate that the mechanism of the present invention is capable of being distributed in the form of a computer readable medium of instructions in a variety of forms, and that the present invention applies equally regardless of the particular type of signal bearing media utilized to actually carry out the distribution. Examples of computer readable media include: nonvolatile, hard-coded type media such as read only memories (ROMs) or erasable, electrically programmable read only memories (EEPROMs), recordable type media such as floppy disks, hard disk drives and CD-ROMs, and transmission type media such as digital and analog communication links. 
     While the invention has been particularly shown and described with reference to a preferred embodiment, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the invention.