home *** CD-ROM | disk | FTP | other *** search
/ DOS/V Power Report 1997 March / VPR9703A.ISO / VPR_DATA / DOGA / SOURCES / PASM.LZH / POLYLINE.CPP < prev    next >
C/C++ Source or Header  |  1996-07-10  |  10KB  |  338 lines
  1. #include <math.h>
  2. #include <string.h>
  3. #include "polyline.h"
  4. #include "suflib.h"
  5.  
  6. #include "log.h"
  7.  
  8. PointID PolyData::AddPoint(int x, int y, int z)
  9. {
  10.     if (allocpoints <= points) {
  11.         PolyPoint *np = new PolyPoint[allocpoints + POLYALLOCUNIT];
  12.         memcpy(np, point, sizeof(PolyPoint) * allocpoints);
  13.         delete [] point;
  14.         point = np;
  15.         allocpoints += POLYALLOCUNIT;
  16.     }
  17.     point[points].x = x;
  18.     point[points].y = y;
  19.     point[points].z = z;
  20.     return points++;
  21. }
  22.  
  23. void PolyData::RemovePoint(PointID pid)
  24. {
  25.     if (pid >= 0 && pid == points-1) {
  26.         points--;
  27.     }
  28. }
  29.  
  30. void PolyData::AddLine(PointID p1, PointID p2, void *id)
  31. {
  32.     int i;
  33.     if (p1 > p2) {i = p1; p1 = p2; p2 = i;}
  34.  
  35.     if (point[p1].z <= 0
  36.      || point[p2].z <= 0
  37.      || (point[p1].x == point[p2].x  && point[p1].y == point[p2].y)
  38.      || (point[p1].x < 0             && point[p2].x < 0)
  39.      || (point[p1].x >= ScreenWidth  && point[p2].x >= ScreenWidth)
  40.      || (point[p1].y < 0             && point[p2].y < 0)
  41.      || (point[p1].y >= ScreenHeight && point[p2].y >= ScreenHeight)) {
  42.         return;
  43.     }
  44.     for (i = 0; i < lines; ++i) {
  45.         if (line[i].p1 == p1 && line[i].p2 == p2) {
  46.             return;
  47.         }
  48.     }
  49.     if (alloclines <= lines) {
  50.         PolyLine *nl = new PolyLine[alloclines+ POLYALLOCUNIT];
  51.         memcpy(nl, line, sizeof(PolyLine) * alloclines);
  52.         delete [] line;
  53.         line = nl;
  54.         alloclines += POLYALLOCUNIT;
  55.     }
  56.     line[lines].p1 = p1;
  57.     line[lines].p2 = p2;
  58.     line[lines].id = id;
  59.     lines++;
  60. }
  61.  
  62. int PolyData::AddPolyClip(int *ps, int offset)
  63. {
  64.     int flag;
  65.     flag = 0;
  66.     if (ScreenWidth <= 0 || ScreenHeight <= 0) {
  67.         return TRUE;
  68.     }
  69.     for (int i = 0; ps[i] != POLY_SEPARATER; ++i) {
  70.         if (point[ps[i]+offset].z <= 0)return FALSE;
  71.         if (point[ps[i]+offset].x >= 0)             flag |= 1;
  72.         if (point[ps[i]+offset].x < ScreenWidth)    flag |= 2;
  73.         if (point[ps[i]+offset].y >= 0)             flag |= 4;
  74.         if (point[ps[i]+offset].y < ScreenHeight)   flag |= 8;
  75. //        if (point[ps[i]+offset].z > 0)              flag |= 16;
  76.     }
  77.     if (flag != 15) {
  78.         return FALSE;
  79.     }
  80.     return TRUE;
  81. }
  82.  
  83. void PolyData::AddPoly(int *ps, int offset, void *id)
  84. {
  85.     if (AddPolyClip(ps, offset) == FALSE) {
  86.         return;
  87.     }
  88.     poly[polys].point = pointbuf + pointbufs;
  89.     poly[polys].minx = poly[polys].maxx = point[ps[0]+offset].x;
  90.     poly[polys].miny = poly[polys].maxy = point[ps[0]+offset].y;
  91.     poly[polys].minz = poly[polys].maxz = point[ps[0]+offset].z;
  92.     for (int i = 0; ps[i] != POLY_SEPARATER; ++i) {
  93.         if (poly[polys].maxx < point[ps[i]+offset].x) poly[polys].maxx = point[ps[i]+offset].x;
  94.         if (poly[polys].minx > point[ps[i]+offset].x) poly[polys].minx = point[ps[i]+offset].x;
  95.         if (poly[polys].maxy < point[ps[i]+offset].y) poly[polys].maxy = point[ps[i]+offset].y;
  96.         if (poly[polys].miny > point[ps[i]+offset].y) poly[polys].miny = point[ps[i]+offset].y;
  97.         if (poly[polys].maxz < point[ps[i]+offset].z) poly[polys].maxz = point[ps[i]+offset].z;
  98.         if (poly[polys].minz > point[ps[i]+offset].z) poly[polys].minz = point[ps[i]+offset].z;
  99.         poly[polys].point[i] = ps[i] + offset;
  100.     }
  101.     poly[polys].points = i;
  102.     poly[polys].id = id;
  103.     pointbufs += i;
  104.     polys++;
  105. }
  106.  
  107. void PolyData::AddPolyInv(int *ps, int offset, void *id)
  108. {
  109.     if (AddPolyClip(ps, offset) == FALSE) {
  110.         return;
  111.     }
  112.     poly[polys].point = pointbuf + pointbufs;
  113.     poly[polys].minx = poly[polys].maxx = point[ps[0]+offset].x;
  114.     poly[polys].miny = poly[polys].maxy = point[ps[0]+offset].y;
  115.     poly[polys].minz = poly[polys].maxz = point[ps[0]+offset].z;
  116.     for (int i = 0; ps[i] != POLY_SEPARATER; ++i)
  117.         ;
  118.     i--;
  119.     for (int j = 0; i >= 0; --i, ++j) {
  120.         if (poly[polys].maxx < point[ps[i]+offset].x) poly[polys].maxx = point[ps[i]+offset].x;
  121.         if (poly[polys].minx > point[ps[i]+offset].x) poly[polys].minx = point[ps[i]+offset].x;
  122.         if (poly[polys].maxy < point[ps[i]+offset].y) poly[polys].maxy = point[ps[i]+offset].y;
  123.         if (poly[polys].miny > point[ps[i]+offset].y) poly[polys].miny = point[ps[i]+offset].y;
  124.         if (poly[polys].maxz < point[ps[i]+offset].z) poly[polys].maxz = point[ps[i]+offset].z;
  125.         if (poly[polys].minz > point[ps[i]+offset].z) poly[polys].minz = point[ps[i]+offset].z;
  126.         poly[polys].point[j] = ps[i] + offset;
  127.     }
  128.     poly[polys].points = j;
  129.     poly[polys].id = id;
  130.     pointbufs += j;
  131.     polys++;
  132. }
  133.  
  134. void PolyData::ConvertLines(void)
  135. {
  136.     for (int p = 0; p < polys; ++p) {
  137.         Poly *np = poly + p;
  138.         for (int i = 0; i < np->points-1; ++i) {
  139.             AddLine(np->point[i], np->point[i+1], np->id);
  140.         }
  141.         AddLine(np->point[i], np->point[0], np->id);
  142.     }
  143.     for (int i = 0; i < polys; ++i) {
  144.         Poly *np = poly + i;
  145.         ConvertLine(np);
  146.     }
  147. }
  148.  
  149. int PolyData::IsOutside(PointID p, PointID p1, PointID p2)
  150. {
  151. //    PolyPoint *p1 = &point[pid[0]+offp];
  152. //    PolyPoint *p2 = &point[pid[1]+offp];
  153. //    PolyPoint *p3 = &point[pid[2]+offp];
  154. //    long m = (p1->x-p2->x)*(p3->y-p2->y) - (p1->y-p2->y)*(p3->x-p2->x);
  155.     if (p < 0) {
  156.         return TRUE;
  157.     }
  158.     if ((long)(point[p1].x-point[p2].x) * (long)(point[p].y-point[p2].y)
  159.       - (long)(point[p1].y-point[p2].y) * (long)(point[p].x-point[p2].x) > 0) {
  160.         return FALSE;
  161.     }
  162.     return TRUE;
  163. }
  164.  
  165. double PolyData::TriangleCrossRate(PointID l1, PointID l2, PointID p1, PointID p2, PointID p3)
  166. {
  167.     double delta;
  168.     double v1x, v1y, v1z, v2x, v2y, v2z, ux, uy, uz;
  169.     v1x = point[p1].x - point[p2].x;
  170.     v1y = point[p1].y - point[p2].y;
  171.     v1z = point[p1].z - point[p2].z;
  172.     v2x = point[p3].x - point[p2].x;
  173.     v2y = point[p3].y - point[p2].y;
  174.     v2z = point[p3].z - point[p2].z;
  175.     ux = point[l2].x - point[l1].x;
  176.     uy = point[l2].y - point[l1].y;
  177.     uz = point[l2].z - point[l1].z;
  178.  
  179.     delta = v1x * v2y * uz + v1y * v2z * ux + v1z * v2x * uy
  180.           - v1x * v2z * uy - v1y * v2x * uz - v1z * v2y * ux;
  181.     if (-1 <= delta && delta <= 1) {
  182.         return 1.0;
  183.     }
  184.     double m;
  185.     m = (v1y * v2z - v1z * v2y) * (point[l1].x - point[p2].x)
  186.       - (v1x * v2z - v1z * v2x) * (point[l1].y - point[p2].y)
  187.       + (v1x * v2y - v1y * v2x) * (point[l1].z - point[p2].z);
  188.     m = - m / delta;
  189.     return m;
  190. }
  191.  
  192. int PolyData::TriangleIsFront(PointID p, PointID p1, PointID p2, PointID p3)
  193. {
  194.     long delta;
  195.     long v1x, v1y, v1z, v2x, v2y, v2z, dx, dy;
  196.     v1x = point[p1].x - point[p2].x;
  197.     v1y = point[p1].y - point[p2].y;
  198.     v1z = point[p1].z - point[p2].z;
  199.     v2x = point[p3].x - point[p2].x;
  200.     v2y = point[p3].y - point[p2].y;
  201.     v2z = point[p3].z - point[p2].z;
  202.     dx  = point[p].x - point[p2].x;
  203.     dy  = point[p].y - point[p2].y;
  204.  
  205.     delta = v1x * v2y - v1y * v2x;
  206.     if (delta == 0) {
  207.         return TRUE;
  208.     }
  209.  
  210.     double k, l;
  211.     k = (double)( v2y * dx - v2x * dy) / (double)delta;
  212.     l = (double)(-v1y * dx + v1x * dy) / (double)delta;
  213.  
  214.     double z = point[p2].z + k * v1z + l * v2z;
  215.  
  216.     if (z - 1.0 <= (double)point[p].z) {
  217.         return TRUE;
  218.     }
  219.     return FALSE;
  220. }
  221.  
  222. double PolyData::CrossRate(PointID l1, PointID l2, PointID p1, PointID p2)
  223. {
  224.     long dx, dy, lx, ly, lz, px, py, pz;
  225.     lx = point[l2].x - point[l1].x;
  226.     ly = point[l2].y - point[l1].y;
  227.     lz = point[l2].z - point[l1].z;
  228.     px = point[p2].x - point[p1].x;
  229.     py = point[p2].y - point[p1].y;
  230.     pz = point[p2].z - point[p1].z;
  231.     dx = point[p1].x - point[l1].x;
  232.     dy = point[p1].y - point[l1].y;
  233.  
  234.     long delta = lx*py - ly * px;
  235.  
  236.     if (delta == 0) return -1.0;
  237.     double k, l;
  238.     k = (double)(py * dx - px * dy) / (double)delta;
  239.     l = (double)(ly * dx - lx * dy) / (double)delta;
  240.     if (l <= 0 || l >= 1.0) {
  241.         return -1;
  242.     }
  243.     if (point[l1].z + k * lz >= point[p1].z + l * pz) {
  244.         return -1;
  245.     }
  246.     return k;
  247. }
  248.  
  249. void PolyData::ConvertLine(Poly *np)
  250. {
  251.     int maxlines;
  252.     maxlines = lines;
  253.     for (int i = 0; i < maxlines; ++i) {
  254.         int p1outside, p2outside, p3outside;
  255.         PointID p1 = line[i].p1;
  256.         PointID p2 = line[i].p2;
  257.         PointID p3 = -1;
  258.         if (p1 < 0 || p2 < 0
  259.          || (np->maxz < point[p1].z && np->maxz < point[p2].z)
  260.          || (np->minx > point[p1].x && np->minx > point[p2].x)
  261.          || (np->maxx < point[p1].x && np->maxx < point[p2].x)
  262.          || (np->miny > point[p1].y && np->miny > point[p2].y)
  263.          || (np->maxy < point[p1].y && np->maxy < point[p2].y)) {
  264.             continue;
  265.         }
  266.         p1outside = TriangleIsFront(p1, np->point[0], np->point[1], np->point[2]);
  267.         p2outside = TriangleIsFront(p2, np->point[0], np->point[1], np->point[2]);
  268.         if (p1outside && p2outside) {
  269.             continue;
  270.         }
  271.         int xd = point[p2].x - point[p1].x;
  272.         int yd = point[p2].y - point[p1].y;
  273.         int zd = point[p2].z - point[p1].z;
  274.         double rate = TriangleCrossRate(p1, p2, np->point[0], np->point[1], np->point[2]);
  275.         if (0.0 < rate && rate < 1.0) {
  276.             p3 = AddPoint(point[p1].x + xd * rate, point[p1].y + yd * rate, point[p1].z + zd * rate);
  277.         }
  278.         p1outside |= IsOutside(p1, np->point[np->points-1], np->point[0]);
  279.         p2outside |= IsOutside(p2, np->point[np->points-1], np->point[0]);
  280.         p3outside = IsOutside(p3, np->point[np->points-1], np->point[0]);
  281.         double r1 = -1.0, r2 = -1.0;
  282.         double k;
  283.         k = CrossRate(p1, p2, np->point[np->points-1], np->point[0]);
  284.         if (0 < k && k < 1) {
  285.             r1 = k;
  286.         }
  287.         for (int j = 0; j < np->points-1; ++j) {
  288.             p1outside |= IsOutside(p1, np->point[j], np->point[j+1]);
  289.             p2outside |= IsOutside(p2, np->point[j], np->point[j+1]);
  290.             p3outside |= IsOutside(p3, np->point[j], np->point[j+1]);
  291.             k = CrossRate(p1, p2, np->point[j], np->point[j+1]);
  292.             if (0 < k && k < 1) {
  293.                 if (r1 < 0 || k < r1) {
  294.                     r2 = r1;
  295.                     r1 = k;
  296.                 } else if (r2 < 0 || k < r2) {
  297.                     r2 = k;
  298.                 }
  299.             }
  300.         }
  301.         PointID pa = -1, pb = -1;
  302.         if (p3outside == FALSE) {
  303.             if (r1 < 0 || rate < r1) {
  304.                 r2 = r1;
  305.                 r1 = rate;
  306.                 pa = p3;
  307.             } else if (r2 < 0 || rate < r2) {
  308.                 r2 = rate;
  309.                 pb = p3;
  310.             } else {
  311.                 RemovePoint(p3);
  312.             }
  313.         } else if (p3 >= 0) {
  314.             RemovePoint(p3);
  315.         }
  316.         if (r1 >= 0 && pa < 0) {
  317.             pa = AddPoint(point[p1].x + xd * r1, point[p1].y + yd * r1, point[p1].z + zd * r1);
  318.         }
  319.         if (r2 >= 0 && pb < 0) {
  320.             pb = AddPoint(point[p1].x + xd * r2, point[p1].y + yd * r2, point[p1].z + zd * r2);
  321.         }
  322.         if (pb >= 0) {
  323.             line[i].p2 = pa;
  324.             AddLine(pb, p2, line[i].id);
  325.         } else if (!p1outside && !p2outside) {
  326.             line[i].p1 = line[i].p2 = -1;
  327.         } else if (pa >= 0) {
  328.             if (!p1outside && p2outside) {
  329.                 line[i].p1 = pa;
  330.             } else if (p1outside && !p2outside) {
  331.                 line[i].p2 = pa;
  332.             }
  333.         }
  334.     }
  335. }
  336.  
  337.  
  338.