Last changed: 31 Mar 1995 Random notes.... In this file we explain how and why certain things are done, and point out where work remains... Rasterization ------------- There are two schemes used for rasterization: pixel spans and pixel arrays. Pixel Spans are horizontal runs of pixels generated by polygon rasterization and glDrawPixel operations. As seen in span.c, horizontal runs of pixels are passed to each enabled raster operation (blending, depth-buffering, stencil, etc). At many of these stages, pixels may be discarded due to failing the depth test, stippling, etc. The boolean mask array indicates which pixels to draw and which to discard. Spans are good because many pixels can be processed per function call. Also, we're taking advantage of spatial coherence. Pixel arrays are used in the rasterization of points, lines, and bitmaps. The pixel array (or pixel buffer) scheme is very similar to the pixel span method. The only difference is that the pixels can be at random locations. Despite the care I've put into rasterization, it's still the bottleneck in Mesa. The OpenGL rasterization pipeline imposes a certain structure which is difficult to implement at maximum speed. I'm still working on it though... Polygons -------- The vertices of a polygons (and triangles and quads, etc) are stored in VB.Eye[], etc. The vlist[] array is an list of indexes into the vertex arrays, defining the vertices of the polygon. This scheme is was prompted by how clipping is done. Remember that clipping a polygon may result in an unchanged polygon or a radically different one. In the former case, we don't want to copy vertex data from an input list to a clipped list. In the later case, we don't want to shift vertex data to insert new vertices. The solution was to use a level of indirection (the vlist array). This also worked out well for the TRIANGLE_STRIP, TRIANGLE_FAN, QUAD_STRIP, etc. primitives. The only disadvantage is the extra cycles needed to lookup indexes via vlist when doing vertex transformations. Maybe copying and shifting data in the clippers is OK if you don't mind a big speed hit for clipping. The polygon rasterizing functions in polygons.c will handle any n-sided simple polygon. Would it have been better to break down n-sided poly- gons into triangles and do triangle rasterization only (which we could optimize?) Maybe, but interpolation of colors across quadrilaterals looks better when they're treated as 4-sided polygons instead of 2 tri- angles. Clipping -------- Clipping points is trivial. Line clipping is done with the usual bit-mask line clipping algorithm. Polygon clipping is based on the edge-by-edge method of Sutherland-Hodgman. Yes, I went crazy with macros! It was a good way to avoid writing nearly the same code over and over and is faster than a bunch of function calls. Be ready for a debugging nightmare if you want to change this code! This code is pretty fast as is. Transformations --------------- The functions in xform.c for rotate, scale, translate all construct 4x4 matrices then do matrix multiplies. This should be optimized! However, always making a 4x4 matrix is simple for display lists. Also, some of the functions (gl_transform_point,etc) should be rewritten as macros and put in xform.h. Point, line, polygon rendering ------------------------------ In points.c, lines.c and polygons.c there are a number of rasterization functions for each primitive. The one to use is determined by looking at the current context. If you have a special combination of rendering operations which isn't as fast as it could be, it should be easy to add it in like the others. Dithering --------- The spec says dithering should initially be enabled. Testing this using SGI's library and demo programs, glIsEnabled says dithering is enabled yet there is no visual evidence of dithering. It seems to me that dithering should initially be off especially for CI visuals. Suppose you're drawing a flat-shaded polygon with index 5 which is mapped to red. You don't want dithering to produce pixels with value 4 because who knows what color is loaded at position 4 in the colormap. Currently, dithering is initially disabled in this implementation. GLU library ----------- The GLU library is very much incomplete. Only the most frequently used functions are done. Others are half-hearted attempts. Someone who knows splines has to write the NURBS code. All the GLU functions should be written in terms of GL calls. The GLU library could be written by someone entirely independent of the main library. Tk and aux libraries -------------------- These libraries are based on SGI code. They shouldn't be used for real applications. Go directly to the X/Mesa interface, use the pseudo-GLX functions, or use GLUT instead. Demo programs ------------- Look at the source for the demo programs to learn what keyboard functions are available. New demos should be written since these are mostly SGI's. glDrawPixels, glReadPixels, glBitmap ------------------------------------ These functions are complicated because of the vast number of options possible. I haven't put much effort into speeding them up. The glPixelZoom operation isn't supported yet. I'm not sure of the best way to integrate it. C notes ------- When writing new code, use the strictest compiler flags available. This helps to catch subtle bugs and increases portability. Also, use lint once in a while. There shouldn't be any compilation warnings, except when the compiler is at fault. Look at assembly language output when not sure how to efficiently write something. Use the right data types. Use unsigned types instead of signed types when possible since some compilers can generate better code with them. Be aware of how type conversions are done. On SGI systems for example, float/int conversion is much more efficient than float/unsigned int conversion. Write straightforward code: compilers often can do better optimizations on simple code than complicated code. It's also easier for others to understand. USE COMMENTS! Compiler problems ----------------- The DEC ultrix C compiler doesn't recognize the 'const' qualifier! OSF/1 hasn't been tested. The Sun ANSI C compiler doesn't have correct prototypes for memcpy(), etc in its header files. Also, it complains about mixed-type expressions much more than other compilers. The Amiga DCC compiler, at least the version I have, can't compile Mesa because it's just too big. Also it doesn't like the F floating point constant suffix. SGI's IRIX 4.0.5 C compiler produces *many* warnings when -fullwarn is specified, unlike IRIX 5.2 C compiler. SGI's IRIX 6.0.1 C compiler produces many detailed warnings, use the -woff option to control them. There appear to be some fatal bugs in Mesa when compiled on IRIX 6.0 systems. Try the demos/wave program for example... Known Bugs ---------- Under IRIX 6.0 in 64-bit mode, cones are drawn incorrectly. Namely, depth buffering is incorrect for quadrilateral which share a common vertex. The problem is either in the computation of the equation of the quad's plane or in the computation/interpolation of Z values. Under IRIX 6.0 in 64-bit mode, the wave demo doesn't work. dbx reports the crash inside an Xlib call... Linux systems are more sensitive to floating point exceptions. At the time of writing this, all known FP exceptions have been fixed. Summary of the source code in src/ ---------------------------------- Here is a summary of the source files which implement the core library. See the top of each file for details. accum.[ch] - accumulation buffer alpha.[ch] - alpha test amesa.[ch] - Amiga interface attrib.[ch] - attribute stack bitmap.[ch] - glBitmap blend.[ch] - pixel blending bresenham.[ch] - implementation of Bresenham's line algorithm clip.[ch] - functions for clipping points, lines, and polygons against the view volume and user-defined clipping planes Check out this code! It makes liberal use of the cpp! config.h - tunable configuration parameters context.[ch] - definition of the library context and functions for creating, setting, deleting contexts. copypixels.[ch] - glCopyPixels dd.h - device driver function prototypes. These functions must must be implemented by xmesa.c, amesa.c, etc. to perform low-level rendering. depth.[ch] - depth buffer functions dither.[ch] - dithering functions draw.[ch] - point, line, and polygon rendering drawpixels.[ch] - glDrawPixels enable.c - the glEnable and glDisable functions eval.[ch] - evaluators feedback.[ch] - feedback and selection facilities fog.c - fog functions get.c - glGet* functions glx.c - pseudo-GLX functions interp.[ch] - interpolation functions light.[ch] - lighting, material, and shading functions lines.[ch] - line segment rendering list.[ch] - display lists logic.[ch] - pixel logic ops macros.h - useful macros used in many files misc.c - simple, miscellaneous functions pb.c - pixel buffer (pixel array) functions pixel.[ch] - glPixelStore, glPixelTransfer, etc. points.[ch] - point rendering polygons.[ch] - polygon rendering quickpoly.[ch] - quick and dirty polygon rendering readpixels.c - glReadPixels scissor.[ch] - scissor box span.[ch] - pixel span processing stencil.[ch] - stencil operations texture.[ch] - texture mapping vb.[ch] - vertex buffer data structure vertex.c - the glVertex*, glNormal*, glIndex* and glColor* functions xform.[ch] - matrix transformation functions xmesa.c - the X/Mesa interface If you want to familiarize yourself with the source code, the place to start is in context.h. This file defines the structures which make up the global rendering context. There's only 3 global variables in the whole library: CC, PB and VB. CC (Current Context) and is a structure which contains the entire current rendering context. With the functions in context.c we can setup multiple contexts and switch between them to support rendering in multiple windows (almost) simultaneously. PB is the pixel buffer structure. VB is the vertex buffer structure. Why isn't CC a pointer to a context structure? CC is referenced a *lot* and we don't want to dereference a pointer every time we access it. As a trade-off, I deemed it acceptable to do memcpy's of the structure when switching current contexts. Probably the second thing to look at is draw.c which implements the glBegin/glVertex/glEnd stuff. The VB variable is a structure which holds arrays of vertices, colors, texture coordinates, etc. A polygon is defined by an array of indexes into the VB arrays. This was needed because clipping can delete and add vertices to a polygon. Maintaining a list of indexes is faster than doing memcpy's to shift vertex data when vertices are added and deleted. Also, this system works well for primitives which share vertices (triangle and quad strips). Line segment vertices are indexed similarly. Beyond that, the source code is divided up into relatively independent modules with simple names. It should be easy to find all the code related to any particular library feature. On naming conventions: functions which are defined in one file and used from other files have the suffix gl_. Also, such functions are proto- typed in the corresponding .h file. Functions which are only called in the file in which they are defined are declared as static without the gl_ prefix. I always like the Modula-2 way of doing things! As long as the application writer doesn't name his/her functions with a leading gl_ and doesn't use a variable named CC, there should be no symbol conflicts. Perhaps CC should be renamed... Organization ------------ +-----------------------------------------------------+ | | | Client Programs | | | +-----------------------------------------------------+ +-----------+ +------------+------------+ +---------+ | | | aux | | | | | GLU | +------------+ tk | | GLUT | | | | | | | +-----------+ +-------------------------+ +---------+ +----------------------------+------------------------+ | | | | Mesa | | | | | +----------------------------+ xmesa/amesa/glx, etc | | dd.h | | +----------------------------+ | | | | | +-----------------------------------------------------+ | Hardware/OS/Window System | +-----------------------------------------------------+ Key: Hardware/OS/Window System - Putting images onto the display screen is done by calling whatever graphics rendering functions are made available by the system's hardware, operating system or window system. For example: Unix/X Xlib calls Amiga Intuition/graphics library calls PC Windows calls or direct writing to hardware xmesa, amesa, etc - Each computer system will probably require a different 'interface library' to provide the connection between the core library and the underlying hardware/os/window system. Typically, there will, be functions to create rendering contexts, attach them to windows or screens, etc. Also, the functions described in dd.h must be implemented as the core library uses these functions to produce output. dd.h - device driver function prototypes. These functions must be imple- mented in order to produce output. Examples are functions to set the current color, draw pixels, lines, polygons, write spans of pixels, and swap buffers. Mesa - this is the core library. It should be completely portable as all system-dependent features are accessed through the device driver functions. GLU - This utility library is completely implemented in terms of GL calls. tk - A simple window system independent toolkit. aux - A simple library build on tk. Client Programs - Graphics programs will use the core functions and either the aux/tk library or a xmesa, amesa, etc. interface program. More on the device drivers ========================== See the file src/dd.h for the list of functions which compose a device driver. Each of the functions must be implemented on your system/hardware for the library to function. Additionally, you must provide some functions for establishing rendering contexts, swapping buffers, etc. in a manner similar to the GLX library. There are basically three catagories of functions in the device driver: 1. simple primitive functions 2. span-based functions 3. miscellaneous functions Simple primitive functions are used to write individual pixels, line segments, or polygons to the output device. These functions are used when advanced features such as depth-buffering, stenciling, and smooth shading are disabled. If your system supports line or polygons rendering in hardware or in the OS, you should use those facilities. Span-based functions are used to render primitives which require depth- buffering, smooth shading, etc. The span functions write a horizontal sequence of pixels to the frame buffer with a per-pixel binary mask. Pixels may be masked from writing when they fail the depth test, stencil test, stippling, etc. Among the miscellaneous functions are functions for clearing the output buffer, specifying the reading and drawing buffers The X/Mesa device driver ------------------------ The X/Mesa driver is the interface between GL and the X11 window system. All GL rendering is performed by making X11 library calls. This isn't the fastest method, but it's the most portable and 'networkable'. The X/Mesa interface was loosely modeled on the GLX interface. See the file include/GL/xmesa.h for the programmer's view. The file src/xmesa.c is the implementation of the xmesa and device driver functions. Of interest is the implementation of the back buffer used when double buffering is enabled. The last argument to XMesaCreateContext() is a flag which specifies whether an off-screen pixmap (on the server) or an Ximage (on the host) is used as the back buffer. It's probably best to use a pixmap when your rendering low-complexity scenes and to use an Ximage when rendering high-complexity scenes or displaying remotely. Try both to determine which is faster for your application. There is support for the X Shared Memory extension. To enable it, add the flag -DSHM to the src/Makefile CFLAGS line and be sure to link your applica- tion with -lXext. When enabled, the Shared Memory extension will be utilized when using an XImage for the back buffer in double buffer mode. The net result is the "swap" operation will be faster (especially for larger windows). Also, note that alpha blending usually only works when rendering into an Ximage. This is because the X server usually discards extra bits in the argument passed to XSetForeground while XPutPixel will not discard the extra alpha bits. While a 24-bit (or 12-bit) TrueColor or DirectColor visual is recommended for rendering in RGB mode, 8-bit (or 1-bit!) PseudoColor or StaticColor visuals are supported. When simulating RGB mode on an 8-bit or 1-bit display, dithering is used to increase the number of perceived colors. Thanks to Bob Mercier for the wonderful new 8-bit dithering code. GLX --- Real OpenGL uses the GLX X extension to tie into the X window system. Mesa's GLX is _not_ an implementation of the real GLX protocol. It only tries to act like it. If you're going to use the GLX functions you should scan src/glx.c to see its deficiencies. Porting to new systems ====================== Porting Mesa to new systems should require very few changes to the core code in src/. The most effort will be in implementing the device driver functions described in "dd.h". Those functions, plus more system-specific functions such as those in xmesa.c and amesa.c are the interface between the Mesa library and the OS/hardware. Ideas for porting to MS Windows: 1. Call the interface "wmesa" (Windows/Mesa interface) 2. Design a "wmesa.h" file which describes how users must setup/ destory a Windows/Mesa context, etc. 3. Implement the functions in "dd.h" and "wmesa.h" in terms of MS Windows functions in "wmesa.c" 4. Create a makefile which compiles all the core files and wmesa.c and makes a library in lib/. 5. Update the top-level Makefile. 6. Implement the tk libarary in terms of the core and wmesa.c functions. Ideas for porting to Apple MacIntosh: 1. Call the interface "mmesa" (Mac/Mesa interface) 2. Design a "mmesa.h" file which describes how users must setup/ destroy a Mac/Mesa context, etc. 3. Implement the functions in "dd.h" and "mmesa.h" in terms of Mac OS/QuickDraw functions in "mmesa.c" 4. Create a makefile which compiles all the Mesa core files and mmesa.c and makes a library in lib/. 5. Update the top-level Makefile. 6. Implement the tk libarary in terms of the core and mmesa.c functions. Ideas for porting to more Unix/X workstations. 1. Edit the Make-config to add appropriate entries for your system. 2. If your compiler detects errors or warnings, try to correct them in a portable fashion. Also: 1. You may want to adjust some of the parameters in config.h 2. If the GL datatypes in GL/gl.h need to be defined in terms of some C types other than what's currently seen, you may have to insert some #ifdef directives. Mesa programming notes ---------------------- Per-vertex fog is used by default when possible, use glHint( GL_FOG_HINT, GL_NICEST ) to enable per-pixel fog. Linear texture coordinate interpolation is used by default. To enable perspective-corrected interpolation use glHint( GL_PERSPECTIVE_CORRECTION_HINT, GL_NICEST ). Coordinate transformation order: -------------------------------- glVertex() object coords xform by ModelView matrix eye coords clip to user clip planes eye coords xform by Projection matrix clip coords clip to view volume clip coords divide by W ndc coords map to window by viewport window coords Checklist of library status --------------------------- function status & notes ------------ -------------------------------- glAccum Done glAlphaFunc Done glBegin Done glBitmap Done, but not thoroughly tested glBlendFunc Done glCallList Done glCallLists Done glClear done (except for scissor box) glClearAccum Done glClearColor Done glClearDepth Done glClearIndex done? glClearStencil done? glClipPlane done? glColor* Done glColorMask done, but no effect in drivers glColorMaterial done? glCopyPixels glCullFace Done glDeleteLists Done glDepthFunc Done glDepthMask Done glDepthRange Done glDisable Done glDrawBuffer Done, but behavior depends on the Mesa driver glDrawPixels Done, but not thoroughly tested glEdgeFlag Done glEdgeFlagv Done glEnable Done glEnd Done glEndList Done glEvalCoord1* done glEvalCoord2* done glEvalMesh1 done glEvalMesh2 done glEvalPoint1 done glEvalPoint2 done glFeedbackBuffer done? glFinish done glFlush done glFog* done glFrontFace done glFrustum done glGenLists done glGetBooleanv mostly done glGetClipPlane done glGetDoublev mostly done glGetError done glGetFloatv mostly done glGetIntegerv mostly done glGetLightfv done glGetLightiv glGetMapdv done glGetMapfv done glGetMapiv done glGetMaterialfv glGetMaterialiv glGetPixelMapfv glGetPixelMapuiv glGetPixelMapusv glGetPolygonStipple mostly done glGetString done glGetTexEnvfv glGetTexEnviv glGetTexGendv glGetTexGenfv glGetTexGeniv glGetTexImage glGetTexLevelParameterfv glGetTexLevelParameteriv glGetTexParameterfv glGetTexParameteriv glHint done, but no effect in some cases glIndexMask done, no effect in drivers? glIndex* done glInitNames done? glIsEnabled done glIsList done glLightModel* done glLight* done glLineStipple done glLineWidth done glListBase done glLoadIdentity done glLoadMatrixd done glLoadMatrixf done glLoadName done glLogicOp done glMap[12]* done glMapGrid[12]* done glMaterial* done glMatrixMode done glMultMatrixd done glMultMatrixf done glNewList done glNormal* done glOrtho done glPassThrough done glPixelMap* done except for display list compile glPixelStore* done glPixelTransfer* done glPixelZoom not even started! glPointSize done glPolygonMode done glPolygonStipple almost done glPopAttrib done glPopMatrix done glPopName done glPushAttrib done glPushMatrix done glPushName done glRasterPos* done glReadBuffer done glReadPixels Done, but not thoroughly tested glRect* done glRenderMode done glRotated done glRotatef done glScaled done glScalef done glScissor done glSelectBuffer done glShadeModel done glStencilFunc done glStencilMask done glStencilOp done glTexCoord* done glTexEnvf glTexEnvfv glTexEnvi glTexEnviv glTexGend glTexGendv glTexGenf glTexGenfv glTexGeni glTexGeniv glTexImage1D glTexImage2D partially works glTexParameterf glTexParameterfv glTexParameteri glTexParameteriv glTranslated done glTranslatef done glVertex* done glViewport done To Do ----- (grep for TODO in *.[ch] for details) make sure all argument checking is delayed until display list execution time. a few functions still don't get compiled into display lists many GLU functions need to be written, including NURBS glPixelZoom many texture mapping functions texture mapped lines, points glGetTex* calls Recent changes -------------- 11 Feb 95 Better makefile support for Suns 11 Feb 95 Changed NDC coordinate scheme (no more Vndc array) 12 Feb 95 Perspective-corrected texture coordinate interpolated added. 12 Feb 95 Per-pixel fog implemented 13 Feb 95 Added X Shared Memory support ... 23 Mar 95 Introduced vertex buffer (VB) stuff 27 Mar 95 Reimplemented xmesa.c using function pointers to the pixel writing functions