Artifact cb1f95041dcc9c2e500f6187e9bf06f1daef19b22ad2c0099d8bedff103a7393:
- Executable file
r37/lisp/csl/cslbase/c_render.cpp
— part of check-in
[f2fda60abd]
at
2011-09-02 18:13:33
on branch master
— Some historical releases purely for archival purposes
git-svn-id: https://svn.code.sf.net/p/reduce-algebra/code/trunk/historical@1375 2bfe0521-f11c-4a00-b80e-6202646ff360 (user: arthurcnorman@users.sourceforge.net, size: 23896) [annotate] [blame] [check-ins using] [more...]
// c_render.cpp // Drawing code for the graphics window // Copyright (C)/©/¸ Codemist Ltd, 1995-2001 /* Signature: 66b0240a 08-Apr-2002 */ /* * This code may be used and modified, and redistributed in binary * or source form, subject to the "CCL Public License", which should * accompany it. This license is a variant on the BSD license, and thus * permits use of code derived from this in either open and commercial * projects: but it does require that updates to this code be made * available back to the originators of the package. * Before merging other code in with this or linking this code * with other packages or libraries please check that the license terms * of the other material are compatible with those of this. */ #ifdef GRAPHICS_WINDOW #include "cwin.hpp" // I have two serious concerns here. The first is the amount of space needed // to store descriptions of objects that I might draw. The second is the // potential performance-bottleneck of floating point arithmetic on many // PCs. To try to alleviate these difficulties I will do much of my work // using fixed point arithmetic and with data packed into 16-bit fields // in structures. // I will store 3D points (after rotation and so on) with X and Y // coordinates in the range 0 to 64K, and I will translate & clip this // so that objects at (0x8000, 0x8000) appear in the middle of my screen. // But I will leave myself a full range of integers for the Z coordinate // so that I do not have to worry so much about fine-tuning the // transformations I use in that respect. // The odd-looking range for X and Y is so I can use unsigned bitfield // components in the following structure. // If I want to do Phong shading at some stage (that puts nice highlights // onto rendered surfaces) I should extend the representation of an // XYZPoint to include a surface normal. It should be enough to use 10 // bits for each of the three direction cosines, since I do not have // that many bits of discrimination in my control over display brightness. // I put the field in now so that using it later on will be easy, but // will probably not fill in the values to start with. Note that the // direction cosines need to be signed fields, so I should normalise them // to the range -511 to +511 (nb NOT 512). The typedef is in my main // header file but is replicated here to make it easier to read this code. //-- typedef struct tagXYZPoint //-- { //-- unsigned int x:16; //-- unsigned int y:16; //-- int z; //-- signed int nx:10, ny:10, nz:10; //-- unsigned int red:8, green:8, blue:8, spare:8; //-- } XYZPoint; // I will build up images out of triangles. When I need a rectangle or // bigger polygon I will just split it into triangles. I will assume that // all the vertices I will ever use have been stored in a linear array // of type XYZPoint[]. // A triangle is then represented as a triple of XYZPoints each denoted // by their index values in the array, say v1, v2, v3. // The vertices should be listed in clockwise when viewed from the "outside" // of the object, and if pairs of triangles are used to form rectangles // then the diagonal of the rectangle should be given as the first pair of // vertices. // When a triangle is drawn some or all of its edges can be drawn in with // a pen that will often have a contrasting colour to that used for the // interior of the cell. The need to have only SOME edges drawn in this // way arises when larger polygons have been split into multiple triangles // for processing - the edges of the original polygon may need drawing but // synthetic interior joins do not. The three flag bits edge1, edge2 and // edge3 are used to control which (if any) edges get drawn. All edges // in an entire figure will end up drawn in the same colour: no provision is // made for giving all the edges their own separate colours. //***** What follows has not been implemented yet ***** // So that axes and other line-art can be included there is special support // for straight line "triangles". These have the flag "lineflag" set and then // do not need to use vertex3, which should be set equal to vertex2. // A record with lineflag set represents a straight line segment from vertex1 // to vertex2. If edge1 is set it is drawn in the outline colour (as used for // edges of proper triangles) while otherwise it uses its own R-G-B colour. // If vertex1 is equal to vertex2 when lineflag is set then the record would // appear to represent a point (and vertex3 will be equal to vertex1 and // vertex2). I am inclined to believe that I do not want to draw individual // points. typedef struct tagTriangle { // Observe that each line packs to just 16 bits. // At present I leave 15 bits spare! I used to keep a colour in // that slot but now I keep colous with vertices not faces, so do // not need that space. unsigned int lineflag:1, moved:1, spare:14; unsigned int edge1:1, vertex1:15; unsigned int edge2:1, vertex2:15; unsigned int edge3:1, vertex3:15; } Triangle; // The above layout has several uncomfortable limitations. Perhaps the // most obvious is that it can only handle 32K points. This represents // a grid 180 by 180. A brief experiment with "gnuplot" suggests that it // runs out of space well before that, and many plots I have seen demonstrated // use a grid that is more like 20 by 20, The examples in the Jenks and // Sutor book on Axiom have their most impressive pictures using under // 25K vertices (a bit tight....) and I think that only their fractal // images (eg Antoine's Necklace) would defeat the structure I have here. // I could keep my triangle records the same size but allow for up to // about 1000000 vertices by packing vertex numbers in a way that would // cross word boundaries. I will consider that possibility later on. // I will do a somewhat crude job clipping triangles that do not intersect // the part of the screen that is being re-drawn. // I will also assume that triangles never intersect, so a version // of the painter's algorithm will do for rendering. XYZPoint *points; Triangle *triangles; int triangleCount = 0; #define x_steps 27 #define y_steps 29 XYZPoint vertices[(x_steps+1)*(y_steps+1)]; Triangle faces[x_steps*y_steps*2]; // I will want to colour faces based on their Z coordinate or some other // parameter. The following function maps an integer into a colour in // such a way that increasing the integer leads to a sequence of colours // that cycles through the rainbow and then back from blue to red via // magenta. void selectColour(int z, int &red, int &green, int &blue) { while (z < 0) z += (6*255)*0x00100000; z = z % (6*255); switch (z / 255) { case 0: red = 255; green = z % 255; blue = 0; return; case 1: red = 255 - z % 255; green = 255; blue = 0; return; case 2: red = 0; green = 255; blue = z % 255; return; case 3: red = 0; green = 255 - z % 255; blue = 255; return; case 4: red = z % 255; green = 0; blue = 255; return; case 5: red = 255; green = 0; blue = 255 - z % 255; return; } } // The "raw data" section of this code is really for debugging purposes only // and will need to be replaced by something that can accept surface // specifications from some external source. typedef struct tagRealPoint { double x, y, z; } RealPoint; RealPoint rawData[x_steps+1][y_steps+1]; CBrush thirtyTwoBrushes[32]; void initRawData() { int x, y; for (x=0; x<=x_steps; x++) { double rx = (6.0*(double)x)/(double)x_steps - 3.0; for (y=0; y<=y_steps; y++) { int n = x+(x_steps+1)*y; double ry = (6.0*(double)y)/(double)y_steps - 3.0; double rz = 3.0*cos(3.0*sqrt(rx*rx+ry*ry)); rawData[x][y].x = rx; rawData[x][y].y = ry; rawData[x][y].z = rz; } } for (int i=0; i<32; i++) { int red, green, blue; selectColour((255*6*i)/32, red, green, blue); thirtyTwoBrushes[i].CreateSolidBrush(RGB(red, green, blue)); } } static doneInit = 0; // I truncate at 2^30 because that is slightly easier than using the // whole of the integer range, and the cases where it makes a difference // will not arise very often. #define IntegerRange 1073741824.0 // 2^30 void CGraphicsWindow::initSurface() { if (doneInit == 0) { initRawData(); doneInit = 1; } int x, y, sx, sy; points = vertices; for (x=0; x<=x_steps; x++) { for (y=0; y<=y_steps; y++) { int n = x+(x_steps+1)*y; double rx = rawData[x][y].x; double ry = rawData[x][y].y; double rz = rawData[x][y].z; double aw = xform[3][3]; double ax = (xform[0][0]*rx+xform[1][0]*ry+xform[2][0]*rz+xform[3][0])/aw; double ay = (xform[0][1]*rx+xform[1][1]*ry+xform[2][1]*rz+xform[3][1])/aw; double az = (xform[0][2]*rx+xform[1][2]*ry+xform[2][2]*rz+xform[3][2])/aw; double rw = perspecDistance/(perspecDistance - az); ax *= rw; ay *= rw; if (ax < -IntegerRange) sx = 0; else if (ax > IntegerRange) sx = 0xffff; else sx = 0x8000+(int)ax; if (sx < 0) sx = 0; else if (sx > 0xffff) sx = 0xffff; points[n].x = sx; if (ay < -IntegerRange) sy = 0; else if (ay > IntegerRange) sy = 0xffff; else sy = 0x8000+(int)ay; if (sy < 0) sy = 0; else if (sy > 0xffff) sy = 0xffff; points[n].y = sy; if (az < -IntegerRange) az = -IntegerRange; else if (az > IntegerRange) az = IntegerRange; points[n].z = (int)az; int red, green, blue; selectColour((int)(400.0*rz), red, green, blue); points[n].red = red; points[n].green = green; points[n].blue = blue; points[n].spare = 0xff & (int)(100*rz); } } triangles = faces; triangleCount = 0; for (x=0; x<x_steps; x++) { for (y=0; y<y_steps; y++) { int n = x+(x_steps+1)*y; // I set things up here so that edges 1 and 2 of each triangle are the // ones that form the diagonal of the rectangle that is being divided. I // do this so that it is at least partially reasonable to select a colour // for the whole of a triangle by averaging these... triangles[triangleCount].lineflag = 0; triangles[triangleCount].edge1 = 0; triangles[triangleCount].edge2 = 1; triangles[triangleCount].edge3 = 1; triangles[triangleCount+1].lineflag = 0; triangles[triangleCount+1].edge1 = 0; triangles[triangleCount+1].edge2 = 1; triangles[triangleCount+1].edge3 = 1; // Note I make the triangles clockwise here int x1 = points[n].x, y1 = points[n].y, z1 = points[n].z; int x2 = points[n+1].x, y2 = points[n+1].y, z2 = points[n+1].z; int x3 = points[n+x_steps+1].x, y3 = points[n+x_steps+1].y, z3 = points[n+x_steps+1].z; int x4 = points[n+x_steps+2].x, y4 = points[n+x_steps+2].y, z4 = points[n+x_steps+2].z; int d1 = x4-x1, d2 = y4-y1, d3 = z4-z1; int d4 = x3-x2, d5 = y3-y2, d6 = z3-z2; if (d1*d1+d2*d2+d3*d3 >= d4*d4+d5*d5+d6*d6) { triangles[triangleCount].vertex1 = n + x_steps + 1; triangles[triangleCount].vertex2 = n + 1; triangles[triangleCount].vertex3 = n; triangles[triangleCount+1].vertex1 = n + 1; triangles[triangleCount+1].vertex2 = n + x_steps + 1; triangles[triangleCount+1].vertex3 = n + x_steps + 2; } else { triangles[triangleCount].vertex1 = n + x_steps + 2; triangles[triangleCount].vertex2 = n; triangles[triangleCount].vertex3 = n + x_steps + 1; triangles[triangleCount+1].vertex1 = n; triangles[triangleCount+1].vertex2 = n + x_steps + 2; triangles[triangleCount+1].vertex3 = n + 1; } triangleCount += 2; } } sortTriangles(); } int triangleLeft(const Triangle *a) { int w, r; r = points[a->vertex1].x; if ((w = points[a->vertex2].x) < r) r = w; if ((w = points[a->vertex3].x) < r) r = w; return r; } int triangleRight(const Triangle *a) { int w, r; r = points[a->vertex1].x; if ((w = points[a->vertex2].x) > r) r = w; if ((w = points[a->vertex3].x) > r) r = w; return r; } int triangleBottom(const Triangle *a) { int w, r; r = points[a->vertex1].y; if ((w = points[a->vertex2].y) < r) r = w; if ((w = points[a->vertex3].y) < r) r = w; return r; } int triangleTop(const Triangle *a) { int w, r; r = points[a->vertex1].y; if ((w = points[a->vertex2].y) > r) r = w; if ((w = points[a->vertex3].y) > r) r = w; return r; } int triangleFar(const Triangle *a) { int w, r; r = points[a->vertex1].z; if ((w = points[a->vertex2].z) < r) r = w; if ((w = points[a->vertex3].z) < r) r = w; return r; } int triangleNear(const Triangle *a) { int w, r; r = points[a->vertex1].z; if ((w = points[a->vertex2].z) > r) r = w; if ((w = points[a->vertex3].z) > r) r = w; return r; } int orderTriangles(const void *va, const void *vb) { int za = triangleFar((const Triangle *)va); int zb = triangleFar((const Triangle *)vb); if (za < zb) return -1; else if (za > zb) return 1; else return 0; } // The next function returns 1 is the line (a1-a2) lies above (and thus // obscures) the line (b1-b2), or -1 if there is an obscuring that goes // the other way. int linesCross(XYZPoint *a1, XYZPoint *a2, XYZPoint *b1, XYZPoint *b2) { // Firstly I will discard all cases where the line segments are not incident. int l1 = a1->y-a2->y, m1 = a2->x-a1->x, n1 = a1->x*a2->y-a2->x*a1->y; int u1 = l1*b1->x+m1*b1->y+n1, u2 = l1*b2->x+m1*b2->y+n1; if (u1 >= 0 && u2 >= 0) return 0; if (u1 <= 0 && u2 <= 0) return 0; int l2 = b1->y-b2->y, m2 = b2->x-b1->x, n2 = b1->x*b2->y-b2->x*b1->y; int v1 = l2*a1->x+m2*a1->y+n2, v2 = l2*a2->x+m2*a2->y+n2; if (v1 >= 0 && v2 >= 0) return 0; if (v1 <= 0 && v2 <= 0) return 0; // Now I know that the line segments cross in their XY projections, so I // compute the Z coordinates of the intersection. double z1 = ((double)v1*(double)a2->z-(double)v2*(double)a1->z)/ (double)(v1-v2); double z2 = ((double)u1*(double)b2->z-(double)u2*(double)b1->z)/ (double)(u1-u2); if (z1 > z2) return 1; if (z1 < z2) return -1; // The position here is possibly nasty - the two triangles DO overlap, but // at the point where the edges cross they have the same distance. I should // do something more here, but that can come later on. return 0; } int insideTriangle(XYZPoint *a, XYZPoint *b1, XYZPoint *b2, XYZPoint *b3) { // place-holder return 0; } int triangleObscures(Triangle *a, Triangle *b) { XYZPoint *a1 = &points[a->vertex1], *a2 = &points[a->vertex2], *a3 = &points[a->vertex3]; XYZPoint *b1 = &points[b->vertex1], *b2 = &points[b->vertex2], *b3 = &points[b->vertex3]; int v; if ((v = linesCross(a1, a2, b1, b2)) != 0) return (v > 0); if ((v = linesCross(a1, a2, b2, b3)) != 0) return (v > 0); if ((v = linesCross(a1, a2, b3, b1)) != 0) return (v > 0); if ((v = linesCross(a2, a3, b1, b2)) != 0) return (v > 0); if ((v = linesCross(a2, a3, b2, b3)) != 0) return (v > 0); if ((v = linesCross(a2, a3, b3, b1)) != 0) return (v > 0); if ((v = linesCross(a3, a1, b1, b2)) != 0) return (v > 0); if ((v = linesCross(a3, a1, b2, b3)) != 0) return (v > 0); if ((v = linesCross(a3, a1, b3, b1)) != 0) return (v > 0); if ((v = insideTriangle(a1, b1, b2, b3)) != 0) return v; if ((v = insideTriangle(a2, b1, b2, b3)) != 0) return v; if ((v = insideTriangle(a3, b1, b2, b3)) != 0) return v; if ((v = insideTriangle(b1, a1, a2, a3)) != 0) return v; if ((v = insideTriangle(b2, a1, a2, a3)) != 0) return v; if ((v = insideTriangle(b3, a1, a2, a3)) != 0) return v; return 0; } // After setting up the list of triangles (which must be re-done each time // I rotate or re-scale) I must call the following to Z-sort the data void CGraphicsWindow::sortTriangles() { // First I do a simple and direct sort based on the lowest point in each // triangle. qsort(triangles, triangleCount, sizeof(Triangle), orderTriangles); // Now the ordering I am left with is NOT guaranteed adequate, since I might // have a tall triangle whose lowest point is very low but where some // other triangle that starts higher up is in fact underneath it where they // happen to cross. I will do something more like an insertion sort // now to try to fix up such cases. int i; for (i=0; i<triangleCount; i++) triangles[i].moved = 0; i = 0; while (i<triangleCount-1) { int l = triangleLeft(&triangles[i]), r = triangleRight(&triangles[i]), t = triangleTop(&triangles[i]), b = triangleBottom(&triangles[i]), n = triangleNear(&triangles[i]); for (int j=i+1;j<triangleCount;j++) { if (triangleFar(&triangles[j]) >= n) break; if (triangleLeft(&triangles[j]) >= r) continue; if (triangleRight(&triangles[j]) <= l) continue; if (triangleBottom(&triangles[j]) >= t) continue; if (triangleTop(&triangles[j]) <= b) continue; if (triangleObscures(&triangles[i], &triangles[j])) { if (triangles[j].moved) continue; triangles[i].moved = 1; Triangle w = triangles[j]; for (int k=j-1; k>=i; k--) triangles[k+1] = triangles[k]; triangles[i] = w; i--; break; } } i++; } } // Supposing that the triangles have been sorted so that the bottom-most // one is at the front of the vector, I can just paint all the data... void CGraphicsWindow::paintTriangles(CDC *dc, RECT *clip, int width, int height) { // TESTING CODE HERE initSurface(); // END OF TESTING CODE Triangle *p = triangles; int i; for (i=0; i<triangleCount; i++, p++) { BOOL lineflag = p->lineflag; XYZPoint *v1 = &points[p->vertex1], *v2 = &points[p->vertex2], *v3 = &points[p->vertex3]; int xscale = (65536*width)/10000, yscale = (65536*height)/10000; int xoff = width/2, yoff = height/2; int x1 = xoff + ((((int)v1->x-32768)*xscale)>>16), y1 = yoff - ((((int)v1->y-32768)*yscale)>>16); int x2 = xoff + ((((int)v2->x-32768)*xscale)>>16), y2 = yoff - ((((int)v2->y-32768)*yscale)>>16); int x3 = xoff + ((((int)v3->x-32768)*xscale)>>16), y3 = yoff - ((((int)v3->y-32768)*yscale)>>16); if (clip != NULL) { int left = clip->left, top = clip->top, right = clip->right, bottom = clip->bottom; if (x1 < left && x2 < left && x3 < left) continue; if (x1 > right && x2 > right && x3 > right) continue; if (y1 < top && y2 < top && y3 < top) continue; if (y1 > bottom && y2 > bottom && y3 > bottom) continue; } int red1 = v1->red, green1 = v1->green, blue1 = v1->blue; int red2 = v2->red, green2 = v2->green, blue2 = v2->blue; int red3 = v3->red, green3 = v3->green, blue3 = v3->blue; BOOL e1 = p->edge1, e2 = p->edge2, e3 = p->edge3; if (fullRender || !wirePreview || !viewpointShown) { if (!drawWire && drawSurface != IDM_NOSURFACE) e1 = e2 = e3 = 0; switch (drawSurface) { case IDM_NOSURFACE: break; case IDM_SURFACE: { CBrush *b = &thirtyTwoBrushes[v1->spare & 0x1f]; POINT tri[3]; tri[0].x = x1; tri[0].y = y1; tri[1].x = x2; tri[1].y = y2; tri[2].x = x3; tri[2].y = y3; dc->SelectObject(b); dc->SelectStockObject(NULL_PEN); dc->Polygon(tri, 3); dc->SelectStockObject(BLACK_BRUSH); break; } case IDM_SQUARES: { CBrush b(RGB((red1+red2)/2, (green1+green2)/2, (blue1+blue2)/2)); POINT tri[3]; tri[0].x = x1; tri[0].y = y1; tri[1].x = x2; tri[1].y = y2; tri[2].x = x3; tri[2].y = y3; dc->SelectObject(&b); dc->SelectStockObject(NULL_PEN); dc->Polygon(tri, 3); dc->SelectStockObject(BLACK_BRUSH); break; } case IDM_TRIANGLES: { CBrush b(RGB((red1+red2+red3)/3, (green1+green2+green3)/3, (blue1+blue2+blue3)/3)); POINT tri[3]; tri[0].x = x1; tri[0].y = y1; tri[1].x = x2; tri[1].y = y2; tri[2].x = x3; tri[2].y = y3; dc->SelectObject(&b); dc->SelectStockObject(NULL_PEN); dc->Polygon(tri, 3); dc->SelectStockObject(BLACK_BRUSH); break; } case IDM_SMOOTH: dc->SelectStockObject(NULL_PEN); SubTriangle(dc, x1, y1, red1, green1, blue1, x2, y2, red2, green2, blue2, x3, y3, red3, green3, blue3, 2); break; case IDM_HISMOOTH: dc->SelectStockObject(NULL_PEN); SubTriangle(dc, x1, y1, red1, green1, blue1, x2, y2, red2, green2, blue2, x3, y3, red3, green3, blue3, 4); break; } } if (e1 && e3) { dc->SelectStockObject(BLACK_PEN); dc->MoveTo(x3, y3); dc->LineTo(x1, y1); dc->LineTo(x2, y2); if (e2) dc->LineTo(x3, y3); } else if (e1) { dc->SelectStockObject(BLACK_PEN); dc->MoveTo(x1, y1); dc->LineTo(x2, y2); if (e2) dc->LineTo(x3, y3); } else if (e2) { dc->SelectStockObject(BLACK_PEN); dc->MoveTo(x2, y2); dc->LineTo(x3, y3); if (e3) dc->LineTo(x1, y1); } else if (e3) { dc->SelectStockObject(BLACK_PEN); dc->MoveTo(x3, y3); dc->LineTo(x1, y1); } } if (!GetUpdateRect(NULL, FALSE)) { fullyRendered = fullRender; fullRender = 0; } } #endif // end of c_render.cpp