🚀 go-pugleaf

Long commentary!  Rather than reply strictly point-by-point, I'll try to
answer some of Chris's major questions with an example.  The example
and the hardware discussion accompanying it will necessarily be much
simplified, but I hope it will be obvious that they can be generalized.

Chris asked how the OpenGL API allows immediate-mode graphics data to be
extracted without reformatting.  By "reformatting" in this context I mean
copying information from an application-specific data structure to an
API-specific data structure for the sole purpose of making the information
interpretable to the API.  (An analogous definition can be made with
"wire-protocol packets" substituted for "API-specific data structures.")

Suppose we're writing an application that defines a 3D mesh of points,
performs a calculation modifying them in some way (e.g. computing the
deflection of a beam under load) and then wants to draw some subset
of them (like the outer surface of the beam) as a bunch of quadrilaterals.
The mesh might look like this:

	struct {float location[3]; double someData;} Mesh[10][10][10];

Now with A Typical Graphics Interface (ATGI), we draw the quadrilaterals
this way:

	typedef struct {float x, y, z;} ATGIVertex;
	ATGIVertex quad[4];

	for (i = 0; ...)
		for (j = 0; ...)
			for (k = 0; ...)
				{
				quad[0].x = Mesh[i][j][k].location[0];
				quad[0].y = Mesh[i][j][k].location[1];
				quad[0].z = Mesh[i][j][k].location[2];
				quad[1].x = Mesh[i+1][j][k].location[0];
				quad[1].y = Mesh[i+1][j][k].location[1];
				quad[1].z = Mesh[i+1][j][k].location[2];
				/*
				 * Similarly for Mesh[i+1][j+1][k]
				 *   and Mesh[i][j+1][k] ...
				 */
				ATGIDrawPolygon(4, quad);
				}

The process of converting the data from the form used by the
application (in Mesh) to the form recognized by the API (in quad) is an
example of "reformatting." Note that the original application data
structure could not be passed directly to the graphics API, because of
the presence of extra fields (someData) and because the data is not
available in the correct order (Mesh[i]... followed by Mesh[i+1]...,
rather than Mesh...[k] followed by Mesh...[k+1]).

Real-world databases are typically too large to be cache-resident, so
this data reformatting process generates bus traffic to read
information from Mesh and possibly to store it in quad (if the cache is
write-through or if the data structure being written is larger than the
cache).  From quad it still must be transferred to the graphics engine
in some way (DMA or programmed-I/O).  For illustration, let's say the
cache is write-back and the cache line and bus transaction width are
both equal to the size of one floating-point value.  We'll assume the
cache will be large compared to quad.  Furthermore we'll send data to
the graphics engine via programmed I/O.  That gives us the following
(simplified) sequence of bus transactions:

	Read from Mesh[i][j][k].location[0]
	/* store to quad[0].x -- no transaction due to write-back cache */
	Read from Mesh[i][j][k].location[1]
	/* store to quad[0].y -- no transaction due to write-back cache */
	...
	/* Total of 12 bus transactions for reading elements of Mesh */

	/* Read from quad[0].x -- no transaction because data is in cache */
	Transfer quad[0].x to graphics engine via programmed I/O
	/* Read from quad[0].y -- no transaction because data is in cache */
	Transfer quad[0].y to graphics engine via programmed I/O
	...
	/* Total of 12 bus transactions for writing elements of quad */

The grand total is 24 bus transactions per quadrilateral.  (This covers
the graphics data only; in a real system there would be additional
overhead of some kind -- e.g. primitive type, number of vertices, etc.
This overhead can be ignored for our analysis.)

Now with the OpenGL API, we might draw the quadrilaterals this way:

	
	for (i = 0; ...)
		for (j = 0; ...)
			for (k = 0; ...)
				{
				glBegin(GL_POLYGON);
				glVertex3fv(Mesh[i][j][k].location);
				glVertex3fv(Mesh[i+1][j][k].location);
				glVertex3fv(Mesh[i+1][j+1][k].location);
				glVertex3fv(Mesh[i][j+1][k].location);
				glEnd();
				}

The glBegin() call indicates the beginning of data for a polygon.
Each glVertex3fv() call indicates the location of an array of three
floating-point values defining a vertex.  (As you might guess from the
structure of the name, there are analogs of glVertex3fv() for other
data types and orderings.)  The glEnd() call marks the end of the
data for the polygon.

You could implement glVertex3fv() as a simple read-write loop that
reads vertex data and writes it to the graphics engine by programmed
I/O.  That would always generate a number of bus transactions less than
or equal to the scenario given above (depending on caching policy,
size of data structures involved, etc.).  But you can do better.

WARNING:  I need to delve into hardware and system design for a
moment.  This will be an *extremely* simplified outline of a possible
design, so simplified that astute readers will spot a number of
features that I'm sure they will find objectionable.  Please don't
flame this particular design; I'm trying to provide a basic
understanding of how a problem might be solved, not a detailed proposal
for a real-world solution.  Realistic solutions can be implemented and
have been implemented in a number of different, clever (and much
better!) ways by several manufacturers.

Suppose you add a small piece of logic to your graphics engine so that
it "snoops" bus transactions.  Whenever a "read" transaction appears
with a certain high address bit set, the graphics engine grabs the
resulting data and processes it.  The main memory system simply ignores
the address bit, so it doesn't affect the actual address used for the
fetch.  No extra bus transactions are generated.

Now you can implement glVertex3fv() something like this:

	void glVertex3fv(float* vertex)
		{
		register float junk;

		junk = *((vertex    ) | MAGIC_ADDRESS_BIT);
		junk = *((vertex + 1) | MAGIC_ADDRESS_BIT);
		junk = *((vertex + 2) | MAGIC_ADDRESS_BIT);
		}

A small fudge in the operating system sets up address mapping so that
the appropriate physical addresses are generated from these virtual
addresses.  No extra address-translation overhead is incurred.

The result is that the bus transaction history now looks something
like this:

	Read from Mesh[i][j][k].location[0] -- also snooped by graphics engine
	Read from Mesh[i][j][k].location[1] -- also snooped by graphics engine
	...
	/* Total of 12 bus transactions */

So, even granting generous terms to the ATGI approach, the OpenGL API
has allowed us to save 50% of our bus accesses.  It cost us just a few
gates and a small amount of system software.  And the resulting
application code is certainly no more complicated; it may even be
simpler, according to some tastes.

Why couldn't you use the same technique to speed up the ATGI
interface?  Because the reformatting of data from "Mesh" to "quad" is
mandated by the API.  Without it, the ATGI API has no way to interpret
the data.  The OpenGL API works because it treats graphics data at a
very fine granularity, so fine that the data can be extracted from the
application's native data structures without reformatting.

You could raise the objection that the application could store its data
in precisely the same format required by the ATGI API.  I've commented
on this in previous postings, and this one is already way too long, so
I'll skip it for now.  Suffice to say that some applications don't have
this option, and even the ones that do may pay a cost in terms of
increased real memory requirements for duplicated data.

You might also object that the OpenGL approach requires more procedure
calls.  True.  But on present-day and expected workstations and newer
PCs, leaf procedure calls are cheaper than memory references, so the
OpenGL approach still wins.  Check out the numbers on your favorite
system.

And finally, to reemphasize two points:  (1) The OpenGL API allows
implementations that (I believe) are always at least as efficient as
those of typical APIs on current and planned hardware, even if special
graphics assistance is not available.  (2) I've given only a very
sketchy system design here.  Better approaches are available, and
they're still cheap to implement.



For a few specific questions:

| >               ... for example, if you want to show the deflection of
| >the beam under load, then all of the beam's geometry will change and
| >you'll have to regenerate the PHIGS, PEXlib, or PEX representation for
| >every frame.  
| 
| Well, no. Having reformatted the data, to show a dynamic bending under
| load you just edit the structure store and change some positions. The
| details of which element connects to which are constant. 

OK, I admit I used a loaded example.  (Pun intended.)  When the beam
bends, *all* the vertices change position.  That means you have to
reformat *all* the data from your original database, replace *all* the
vertex data in the structure store, and re-render *all* the
primitives.  The cost of this will always be at least as great as
re-rendering the beam in immediate mode, and on all the systems with
which I'm familiar the cost is significantly greater.  This is an
example of an application for which immediate mode is superior to
structure mode, even for a remote display.



| Well, there is only a massive drop in performance from local to remote
| if you use an immediate mode API. With server side structure storage
| and traversal, performance is much the same in either case. There is a
| little drop because local displays can use shared memory transport,
| but that is just a little optimisation; it does not affect the
| generality of the network transparency approach.

See above.  The tradeoff between immediate mode and structure mode is
very much application-dependent, and unfortunately also dependent on
locality of the display.

As mentioned elsewhere, one reason you wouldn't want to use structure
store on a local display is that the data in your application's private
database usually has to be duplicated in the structure store.  I've
seen too many angry customers complaining that their 20MB database
caused their 32MB system to thrash -- all because the database is
present once in the application, and once again in PEX structure store.

| It may be your belief that running displays on a local machine is far
| more common; that is not my experience. For example, I am sitting at a
| VAXstation 4000 and running programs on a Sun SPARC 2, an HP 9000/750,
| a VAXstation 3100 and a Meiko Computing Surface in addition to my
| local machine.

I certainly use remote displays, but typically not for applications
where graphics performance is important to me.  Software vendors tell
me that the local display case is the usual one for their customers,
too.

| It is my belief that this distributed model will fast become the norm,
| and if as you state GL does not address it without huge performance
| penalty, then that is a significant failing of GL.

Please allow me to correct that misunderstanding!  I didn't say (and
didn't mean to imply) that OpenGL is an inferior solution in a
distributed graphics environment.  OpenGL does have an associated X11
extension protocol (GLX), analogous to the PEX protocol.  Not only does
OpenGL have the ability to support immediate mode graphics with lower
overhead, but in structure mode OpenGL supports finer granularity
structure modification than PEX.  In general, I believe OpenGL should
perform quite well in a distributed environment.

Allen