Dear DDJ,
It was great reading about the CPU detection algorithms in Dr. Dobb's ("Processor Detection schemes," DDJ, June 1993). It's nice to see that magazines such as yours are willing to publish information about this topic.
Incidentally, we've had to deal with the same problem of identifying CPU's. It turns out that there is an incredible amount of information to be gained from CPU's made by other manufacturers like Cyrix, IBM, and Chips&Technologies.
For example, CPU's IBM documentation already includes information for new products up to the up-and-coming 486DX3 99 MHz chip! IBM's documentation is the only one to lay out the undocumented information returned by the CPUID command. Cyrix has started including an identification register that is I/O-memory mapped and absolutely the easiest to use...far better than a CPUID command since it does not generate an exception if the CPU doesn't support CPUID. Chips&Technologies had some really great ideas about power management, but most of their key accounts fell through and they killed off the chip.
A slight omission from your article was the op-code for the CPUID command on the Pentium. No problem for those who have a 586-ready assembler or possess the data sheets, but unfortunate for those who don't. Next time, include the op-code!
Aki Korhonen
Emeryville, California
Dear DDJ,
Yes, "true 3-D is easier than it looks" ("Algorithms for Stereoscopic Imaging," DDJ, April 1993), but I think it is even easier than the impression that some readers may have been left with after reading the article.
In the first place, you don't need a machine like a Silicon Graphics workstation. Low-quality stereo has been available for years on the Atari and Amiga computers. Medium- and low-quality stereo systems can be set up on PCs using VGA and other graphics displays and equipment from the companies mentioned in the article, Stereographics and Tektronix. Another source of low-cost stereo glasses that should be mentioned id the 3-D TV Corporation (San Rafael, California).
Secondly, the algorithms themselves can be much simpler. By way of example, an alternative approach to the key projection computation makes use of inherent symmetries and the stereo geometry. The resulting computation is much more efficient than the authors'. A function using this technique is called RealToStereo, it converts a real 3-D point to two pixel values, one for the left image and one for the right. I'd also like to share something I've learned about "jaggies" in stereoscopic graphics.
In this approach, we view the monitor screen as the image plane of a camera (double meaning intended!) and define two 3-D frames of reference: the Camera frame and the Object frame. The Object frame is anything you want it to be; it is defined by the objects to be viewed. The Camera frame, on the other hand, is defined to have its origin located at the focal point (FP) of the "camera" and its Z-axis lie on the line of sight (LOS) of the camera. The image plane is normal to the LOS and a distance f from the FP (f for focal "distance"). In a real camera, the image plane lies behind FP, but it is easier to visualize the plane as being in front: rays of light from an object point pass through the image plane before they converge at FP. The point where the LOS crosses the image plane is called the "principal point" (PP). For a further discussion of the camera model, see The Manual of Photogrammetry published by the American Society of Photogrammetry, Falls Church, Virginia.
Let's first consider a standard, monoscopic camera. To find out where a ray from an object point will intercept the image plane, the Object coordinates of the point (x,y,z) are transformed to Camera coordinates (X,Y,Z); the Camera coordinates are projected onto the image plane; and finally the image plane coordinates are scaled up or down into pixels.
For efficiency, use 3x3 matrices instead of 4x4 matrices in 3-D coordinate platforms. The basic transformation from Object space to Camera space is C=T+M*O, where C, T, and O are 3-vectors and M is a 3x3 matrix. T defines translation and M defines rotation (it is composed of the angle cosines between the various axes). This computation consists of nine multiplies and nine additions. Duvanenko et al. used the Foley and van Dam formulation that requires 4-vectors and a 4x4 matrix and significantly more computations: 16 multiplies and 12 additions, as they pointed out. Terms get calculated even though they are identically 0. So, if you don't have dedicated hardware to carry out 4-D calculations, as on the Silicon Graphics machines, and you're concerned about computational efficiency, stay in the 3-D world.
In Camera coordinates, the transformation to the image plane is a simple application of the projective, or perspective, transformation; see Example 1(a).
The resulting 2-vector I is the position of the ray on the image plane relative to the PP. This is readily scaled into pixels. Thus, the entire conversion from a 3-D point to a 2-D pixel (for a single view) requires only one 3-vector-matrix multiply, a 3-vector addition, two scalar divisions, and two scalar multiplies (pixel scaling factors can be combined with f).
Now, what is a stereoscopic camera? It has two focal points, but the same image plane. The focal points are separated by a distance S in the X direction. It simplifies things at this stage to think about three different Camera frames (no, really!): one defined by the left FP, one defined by the right FP, and one that would be defined by a focal point at the center of the line joining the two actual focal points. In other words, the left Camera frame is simply displaced from the center frame by a distance (-S/2) along the X axis, and the right frame, by (+S/2).
The above form of the transformation equation is also (very!) convenient because it separates the translation terms from the rotation terms. To project an object point through the left FP, say, requires only a shift in the X direction, in other words, CL=C+S, CR=C-S, where S=(S/2, 0, 0), CL and CR are 3-D positions in left and right Camera frames, respectively, and C is calculated above. Now the projective transform is performed for each focal point essentially as above, but is further simplified because only the x component is different; see Example 1(b).
The image plane points are then scaled to pixels, and so forth. The result is a pair of pixel locations, each relative to their respective principal points. (At this point, you may want to change origins or shift the pixels relative to each other, see the notes in the code listing.)
The point is, of course, that if you are concerned about speed of computation, significant saving can be made by calculating both rays at the same time, rather than by simply applying the single focal point projection (via whatever method you use) twice. In particular, note that the vector-matrix multiply need be done only once.
This has two other important advantages. First, only one rotation matrix is used. Therefore, when you want to rotate Object space with respect to Camera space, only one 3x3 (or, 4x4, if you insist) matrix multiply is needed--again saving much computational time. Second, separating out the "separation term" in the formula in Example 1(b) leads to a good way to deal with a very subtle problem that can arise in stereoscopic graphics.
Suppose you're drawing a line in 3-D space on a plane that is parallel to the image plane and located some distance from it in the Z direction, and suppose this line is tilted, say, five or ten degrees from the Y (or y) axis. On the monitor screen, the pixel representation of the line is two lines, one for each focal point. These lines must be exactly parallel; if they are not, any disparity in the x location of the pixels that make up the lines will look to the viewer like a displacement in the Z direction; that is, in or out of the screen.
This is particularly noticeable where there are jaggies, the line breaks that must occur when drawing diagonal lines on a pixel-based screen. If the line breaks do not occur at precisely the same positions along the two lines, alternate segments appear to jump in and out of the screen, when you are wearing stereoscopic glasses. This will occur if the lines start and stop at x locations that are not shifted by exactly the same amount. Of course, another requirement is that the y locations of the end points be exactly equal; this is guaranteed by the formula in Example 1(b).
The 3-D coordinate transform is usually done in floating point, but, at some stage, the quantities are reduced to integers for the pixel representation. If you aren't careful about truncation or round-off effects when converting floating-point numbers to integers, the shift in x position at the top and bottom of the two lines can be slightly different. Suppose, for example, the top end of the line is located at an x coordinate of 6.4 and the bottom end is at 4.1, and suppose the separation distance between focal points is 2.4. The transformation for left and right pixel locations involves the sum and the difference of the same term, (S/2). The numerical results are something like 6.4+1.2=7.6 and 6.4-1.2=5.2 at the top, and 4.1+1.2=5.3 and 4.1--1.2=2.9 at the bottom. When these values are converted, by truncation (as in a type cast in C) or by rounding, the pixel difference at the top will be 2 (or 3) and the difference at the bottom will be 3 (or 2). The lines will not actually be parallel on the screen.
The solution is to add and subtract the separation term after conversion to integers. This method is used in the listings; and it speed up the calculation by a little bit also.
M.A. Weissman
Federal Way, Washington
Dear DDJ,
Reading David Smead's letter ("Letters," DDJ, May 1993), written in response to Scott Guthreys "A Curmudgery on Programming-language Trends," I found it interesting that he applied the usual double standard when comparing C to assembler and then C++ to C. When comparing C with assembler, he stated that "writing in C is faster than writing in assembler," which is true, largely because C supports the concept of structure. However, when comparing C with C++, he stated that "everything you need already exists in C," which is misleading.
I would observe that, using his own arguments, "everything you need already exists in machine code, so do we need C?" and "writing object-oriented programs is faster in C++ than in C."
The reason I use C++, rather than C, to write OO programs is because C++ supports object orientation. It enables the technology, and I would certainly dispute, in the context of OO, that "C is more than powerful enough to program in." It isn't, as it provides no support for classes, objects, inheritance, or polymorphism.
Edward Kenworthy
Cannock Staffs, England
Dear DDJ,
"C Snippet #37" of December 1992 looks to me too cumbersome. My idea of doing it in C is presented like this:
#include <ctype.h>
#include <string.h>
char * rmlead (char *str)
{
char *obuf = str;
for ( ;
*obuf &&
!isspace(*obuf);
) ;
return obuf;
}No caveat about the original, no destroying the input, no unnecessary copying, no two-level logic, no avoidable break. And much shorter.
Jony Rosenne
Tel Aviv, Israel
Dear DDJ,
In "Swaine's Flames" (July 1993), Michael almost states the point of his essay. Taking some license here, his point that the term "Artificial Intelligence" only applies to things we don't understand. As we develop the algorithms and processes to mimic human intelligence, the demystification provides more specific and exact terminology--just as two hundred years ago everything from refraction to weather, flight to the stars, and procreation to electricity were all bundled under the term "magic."
Because of this, like magic, Artificial Intelligence will never be achieved. In the next generation, when desktop thinking machines are controlling our aircraft, reading to our children, and chatting with us at the check-out lines, we will doubtless call them simply "Cognitive Expression Processors."
Matthew Strebe
San Diego, California
(a) lx= f * Cx / Cz, ly = f * Cy / Cz (b) ILx = (Cx+ S) * f / Cz, ILy = f * Cy / Cz IRx = (Cx - S) * f / Cz, IRy = ILy
Copyright © 1993, Dr. Dobb's Journal