MENTAL
 Main Menu
 Applications
 Computer Science
 Abstract Graphics

Abstract Graphics
 ABSTRACT
GRAPHICS

"Pictorial representation is essential for discovery and rapid understanding" (John L. Synge).


Digital Geometry

Digital geometry −a field within discrete geometry− handles sets of digitized discrete points representing two- or three-dimensional graphs in Euclidean space. These graphs can be:
Graphics languages

In Computer Graphics a lot of effort has been put into creating graphics standards, with different criteria. However, these standards constitute isolated languages, not connected to a general or universal language.

Graphics languages are specialized languages (such as markup languages, database management languages, etc.), based on specific graphical primitives (line, circle, etc.). There are vector, raster or both. There are static and dynamic graphics. And there are also software interface oriented languages: API (Application Program Interface). The most important ones are:
The Bresenham algorithm

The Bresenham algorithm is used to convert a vector into a set of raster points. It determines the cells of a two-dimensional grid that must be marked (drawn) to form an approximation to a straight line between two given points. It was developed by Jack Bresenham in 1962, at IBM, and published in 1965 in the IBM Systems Journal [Bresenham, 1965].

A raster vector example

Bresenham's algorithm was one of the first to be developed in the field of computer graphics because of its simplicity and effectiveness. It uses only addition and subtraction of integers and bit shifting, simple operations that all processors have. However, it is included in the processors (as hardware or firmware) of modern graphics cards.

This algorithm is commonly used to draw lines on a computer screen. The screen consists of a two-dimensional array of pixels addressable by their coordinates (x, y). It is also used in other matrix devices, such as plotters, printers, etc.


The algorithm in pseudocode

This algorithm draws a series of pixels between the points (x1, y1) y (x2, y2). Function line(x1, y1, x2, y2)
   dx = x2−x1
   dy = y2−y1
   error = 0 // incremental error
   p = dy/dx // slope of the line
   y = y1
   For x = x1 To x2
      draw(x, y) // draw pixel in (x, y)
      error = error + p
      If abs(error) ≥ 0.5 Then
        y = y+1
        error = error−1
      End If
   End For
End Function

The function draw(x, y) places a numeric value in the cell (x, y), value that can be simply 1 (interpreted as "black") or an integer associated to a color (combination of some basic colors) or to a grayscale. The following is the generalized one-line drawing function, which takes into account the possible values of dx and dy:

Function lineag(x1, y1, x2, y2)
   dx = x2−x1
   dy = y2−y1
   Case dx = 0 Then
      For y = y1 To y2
        draw(x1, y) // pixel in (x, y)
        End For
   Case dy = 0 Then
      For x = x1 To x2
        draw(x, y1) // pixel in (x, y)
      End For
   Case dx ≥ dy Then.
      line(x1, y1, x2, y2)
   Case dx < dy Then.
      line(x2, y2, x1, y1)
   End Cases
End Function


Version in C

void MidpointLine(int x1,y1,x2,y2)
   {int dx = x2−x1;
   int dy = y2−y1;
   int d = 2*dy−dx;
   int increE = 2*dy;
   int incrNE = 2*(dy−dx);
   x = x1;
   y = y1;
   WritePixel(x, y);
   while (x < x2)
      {if (d<= 0)
        {d+ = incrE;
        x++}
      else
        {d+=incrNE;
        x++;
        y++;}
      WritePixel(x, y);}
      }


Variants and extensions of the Bresenham algorithm

The label "Bresenham" is used on a whole family of algorithms that extend or modify the original Bresenham algorithm. For example:
MENTAL as Graphics Language

MENTAL is not only able to formalize geometric structures. It is also capable of drawing over a region of abstract space, so that, with a physical device, such space can be visualized.


Bresenham's algorithm in MENTAL

( line(x1 y1 x2 y2) =
   ( (d = x2−x1)
   (dy = y2−y1)
   (d = 2*dy - dx)
   (increE = 2*dy)
   (incrNE = 2*(dy−dx))
   (x = x1)
   (y = y1)
   draw(x y)
   ⟨(x < x2) →
      (((d = d+incrNE)
      (x = x+1)
      (y = y+1)) ←'
      (d ≤ 0) →
      ((d = d+incrE)
      (x = x+1)))
      draw(x y)⟩ )


The advantages of MENTAL as a graphic language

MENTAL can be used as a graphical language by using a region within abstract space. The fact that the graph is independent of the representation matrix device justifies that MENTAL can be called an "abstract graphical language". The use of a unified language such as MENTAL to create graphics provides great advantages, advantages derived from the possibilities of the language, with no other limit than that of the imagination. Flexibility, clarity, simplicity and creativity are maximum and go beyond graphic standards. For example: With MENTAL you can create specialized languages for architecture, GIS (geographic information systems), mechanical design, etc.


Some examples
  1. Suppose we want a certain group of points to be visible or invisible, depending on the value of a variable. To those points we assign the value ⟨k⟩ (a generic expression):

      ( D\2 = ⟨k⟩ )
      ( D\6\9 = ⟨k⟩ ) ...

    By making k=0, all those points would be invisible. And by making k>0, all would be visible. In general, k could be an integer indicating a color.

  2. Location of a graphic object in a variable graphic space (array):

      ( ⟨E⟩= v )
      ( ⟨E⟩\6\9 = v ) ...

    By making (E = D), the object is located in D space.

  3. Location of the points of an object referred to a given point in 2D space (i0, j0):

      ( ⟨D0 = v⟩ )
      ( ⟨D\(i0+1)\(j0+2) = v⟩ )

    Making (i0=7 j0=9) the object moves according to this reference position.

Addenda

Computational Geometry

Computational Geometry is a branch of computer science devoted to the study of algorithms that can be stated in terms of geometry. The main impetus in the development of computational geometry as a discipline was the progress in computer-generated graphics (Computer Graphics) and in applications such as CAD/CAM (computer-aided design and manufacturing), GIS (geographic information systems), CAE (computer-aided engineering) and integrated circuit design.

The two main branches of computational geometry are:
  1. Combinatorial computational geometry, also called algorithmic geometry, which treats geometric objects as discrete entities [Preparata & Shamos, 1988].

  2. Numerical computational geometry, also called machine geometry, computer-aided geometric design (CAGD) or geometric modeling, which deals mainly with the representation of real-world objects in forms treatable by CAD/CAM systems. This branch can be considered a further development of descriptive geometry and is often considered a branch of computer graphics or CAD [Forrest, 1971].

Bibliography