home *** CD-ROM | disk | FTP | other *** search
/ DOS/V Power Report 1997 March / VPR9703A.ISO / VPR_DATA / DOGA / SOURCES / POLYEDIT.LZH / MODEL / EDGE.C < prev    next >
C/C++ Source or Header  |  1996-03-26  |  13KB  |  549 lines
  1. /*
  2.  *    エッジ
  3.  *
  4.  *        Copyright T.Kobayashi    1994.7.9
  5.  */
  6.  
  7. #include <stdio.h>
  8. #include <stdlib.h>
  9. #include <string.h>
  10. #include <assert.h>
  11.  
  12. #include "matrix.h"
  13. #include "vector.h"
  14. #include "matclass.h"
  15. #include "strclass.h"
  16. #include "ml.h"
  17.  
  18. #include "poly.h"
  19. #include "view.h"
  20.  
  21. extern    int        EdgeClassID ;
  22.  
  23. #define EDGEALLOCUNIT    256
  24.  
  25. #ifndef __GNUC__
  26. #define inline
  27. #endif
  28.  
  29. static    inline int    EdgeEqual(EdgeData *e1, EdgeData *e2)
  30. {
  31.     return memcmp(e1, e2, sizeof(short)*6) == 0;
  32. }
  33.  
  34. static inline int EdgeCompare(EdgeData *e1, EdgeData *e2)
  35. {
  36.     int *i1, *i2;
  37.     i1 = (int*)e1;
  38.     i2 = (int*)e2;
  39.     if (i1[0] != i2[0])
  40.         return i1[0] - i2[0];
  41.     if (i1[1] != i2[1])
  42.         return i1[1] - i2[1];
  43.     return i1[2] - i2[2];
  44. }
  45.  
  46.  
  47. static    int    EdgeSearchEdge(EdgeClass *edge, EdgeData *ed)
  48. {
  49.     int i, j;
  50.     int begin, end;
  51.     if ((ed->x1 < edge->min[0] && ed->x2 < edge->min[0])
  52.       || (ed->y1 < edge->min[1] && ed->y2 < edge->min[1])
  53.      || (ed->z1 < edge->min[2] && ed->z2 < edge->min[2])
  54.      || (ed->x1 > edge->max[0] && ed->x2 > edge->max[0])
  55.      || (ed->y1 > edge->max[1] && ed->y2 > edge->max[1])
  56.      || (ed->z1 > edge->max[2] && ed->z2 > edge->max[2])) {
  57.         return -1;
  58.     }
  59. #if 0
  60.     for (i = 0; i < edge->edges; ++i) {
  61.         if (EdgeEqual(&edge->edge[i], ed)) {
  62.             return i;
  63.         }
  64.     }
  65. #else
  66.     begin = -1;
  67.     end = edge->edges;
  68.     while (begin < end-1) {
  69.         i = (begin+end)/2;
  70.         j = EdgeCompare(&edge->edge[i], ed);
  71.         if (j == 0) {
  72.             return i;
  73.         } else if (j < 0) {
  74.             end = i;
  75.         } else {
  76.             begin = i;
  77.         }
  78.     }
  79. #endif
  80.     return -1;
  81. }
  82.  
  83. static EdgeClass    *EdgeRealloc(EdgeClass *edge, int size)
  84. {
  85.     int i;
  86.     EdgeClass *newedge;
  87.     newedge = (EdgeClass*)ObjectAlloc(sizeof(EdgeClass) + sizeof(EdgeData) * size, EdgeClassID);
  88.     if (size > edge->allocsize) {
  89.         memcpy(newedge->edge, edge->edge, sizeof(EdgeData) * edge->allocsize);
  90.     } else {
  91.         memcpy(newedge->edge, edge->edge, sizeof(EdgeData) * size);
  92.     }
  93.     for (i = 0; i < 3; ++i) {
  94.         newedge->min[i] = edge->min[i];
  95.         newedge->max[i] = edge->max[i];
  96.     }
  97.     newedge->edges = edge->edges;
  98.     newedge->allocsize = size;
  99.  
  100.     ObjectFree((Object*)edge);
  101.     return newedge;
  102. }
  103.  
  104. static    EdgeClass    *EdgeAppendEdge(EdgeClass *edge, EdgeData *ed)
  105. {
  106.     int pos;
  107.     int j, begin, end;
  108.     if (edge->allocsize <= edge->edges) {
  109.         edge = EdgeRealloc(edge, edge->allocsize + EDGEALLOCUNIT);
  110.     }
  111. #if 0
  112.     pos = edge->edges;
  113. #else
  114. /*
  115. getch();
  116. for (pos = 0; pos < edge->edges; pos++)
  117. printf("\n(%4d,%4d,%4d)-(%4d,%4d,%4d)",
  118.             edge->edge[pos].x1, edge->edge[pos].y1, edge->edge[pos].z1,
  119.             edge->edge[pos].x2, edge->edge[pos].y2, edge->edge[pos].z2);
  120. printf("\nEdgeAppendEdge(%d)(%4d,%4d,%4d)-(%4d,%4d,%4d):",edge->edges,
  121.             ed->x1, ed->y1, ed->z1, ed->x2, ed->y2, ed->z2);
  122. */
  123.     begin = -1;
  124.     pos = end = edge->edges;
  125.     while (begin < end-1) {
  126.         pos = (begin+end)/2;
  127.         j = EdgeCompare(&edge->edge[pos], ed);
  128.         if (j == 0) {
  129.             edge->edge[pos].count++;
  130. /*printf("hit%d\n", pos);*/
  131.             return edge;
  132.         } else if (j < 0) {
  133.             end = pos;
  134.         } else {
  135.             begin = pos;
  136.         }
  137.     }
  138.     pos = end;
  139.     if (pos < edge->edges) {
  140.         memmove(&edge->edge[pos+1], &edge->edge[pos], sizeof(EdgeData) * (edge->edges-pos));
  141.     }
  142. /*printf("add%d", pos);*/
  143. #endif
  144.     edge->edge[pos] = *ed;
  145.  
  146.     if (edge->min[0] > ed->x1) edge->min[0] = ed->x1;
  147.     if (edge->min[0] > ed->x2) edge->min[0] = ed->x2;
  148.     if (edge->min[1] > ed->y1) edge->min[1] = ed->y1;
  149.     if (edge->min[1] > ed->y2) edge->min[1] = ed->y2;
  150.     if (edge->min[2] > ed->z1) edge->min[2] = ed->z1;
  151.     if (edge->min[2] > ed->z2) edge->min[2] = ed->z2;
  152.  
  153.     if (edge->max[0] < ed->x1) edge->max[0] = ed->x1;
  154.     if (edge->max[0] < ed->x2) edge->max[0] = ed->x2;
  155.     if (edge->max[1] < ed->y1) edge->max[1] = ed->y1;
  156.     if (edge->max[1] < ed->y2) edge->max[1] = ed->y2;
  157.     if (edge->max[2] < ed->z1) edge->max[2] = ed->z1;
  158.     if (edge->max[2] < ed->z2) edge->max[2] = ed->z2;
  159.  
  160.     edge->edges++;
  161.     return edge;
  162. }
  163.  
  164. static    EdgeClass    *EdgeDeletePos(EdgeClass *edge, int pos)
  165. {
  166.     if (pos < 0 || edge->edges <= pos) {
  167.         return edge;
  168.     }
  169. #if 0
  170.     if (pos != edge->edges-1) {
  171.         edge->edge[pos] = edge->edge[edge->edges-1];
  172.     }
  173. #else
  174.     if (pos != edge->edges-1) {
  175.         memmove(&edge->edge[pos], &edge->edge[pos+1], sizeof(EdgeData) * (edge->edges-pos-1));
  176.     }
  177. #endif
  178.     edge->edges--;
  179.     return edge;
  180. }
  181.  
  182. static    void    EdgeCreate(EdgeData *ed, Vertex *p1, Vertex *p2)
  183. {
  184.     Vertex *p3;
  185.     if (p1->x > p2->x
  186.      || (p1->x == p2->x && (p1->y > p2->y || (p1->y == p2->y && p1->z > p2->z)))) {
  187.         p3 = p1; p1 = p2; p2 = p3;
  188.     }
  189.     ed->x1 = p1->x;
  190.     ed->y1 = p1->y;
  191.     ed->z1 = p1->z;
  192.     ed->x2 = p2->x;
  193.     ed->y2 = p2->y;
  194.     ed->z2 = p2->z;
  195.     ed->count = 1;
  196. }
  197.  
  198.  
  199. int    EdgeSearch(EdgeClass *edge, Vertex *p1, Vertex *p2)
  200. {
  201.     EdgeData ed;
  202.     EdgeCreate(&ed, p1, p2);
  203.     return EdgeSearchEdge(edge, &ed);
  204. }
  205.  
  206. EdgeClass    *EdgeAppend(EdgeClass *edge, Vertex *p1, Vertex *p2)
  207. {
  208.     EdgeData ed;
  209.     EdgeCreate(&ed, p1, p2);
  210.  
  211. #if 0
  212.     int pos;
  213.     if ((pos = EdgeSearchEdge(edge, &ed)) < 0) {
  214.         edge = EdgeAppendEdge(edge, &ed);
  215.     } else {
  216.         edge->edge[pos].count++;
  217.     }
  218. #else
  219.     edge = EdgeAppendEdge(edge, &ed);
  220. #endif
  221.     return edge;
  222. }
  223.  
  224. EdgeClass    *EdgeDelete(EdgeClass *edge, Vertex *p1, Vertex *p2)
  225. {
  226.     int pos;
  227.  
  228.     if ((pos = EdgeSearch(edge, p1, p2)) >= 0) {
  229.         edge = EdgeDeletePos(edge, pos);
  230.     }
  231.     return edge;
  232. }
  233.  
  234. EdgeClass    *EdgeAlloc(int size)
  235. {
  236.     EdgeClass *edge;
  237.     if (size < EDGEALLOCUNIT) {
  238.         size = EDGEALLOCUNIT;
  239.     } else {
  240.         size = ((size / EDGEALLOCUNIT) + 1) * EDGEALLOCUNIT;
  241.     }
  242.     edge = (EdgeClass*)ObjectAlloc(sizeof(EdgeClass) + sizeof(EdgeData) * size, EdgeClassID);
  243.     edge->allocsize = size;
  244.     edge->edges = 0;
  245.     edge->min[0] = edge->min[1] = edge->min[2] = 32767;
  246.     edge->max[0] = edge->max[1] = edge->max[2] = -32767;
  247.     return edge;
  248. }
  249.  
  250. static    int    EdgeSearchPoly(EdgeClass *edge, Polygon *poly)
  251. {
  252.     int i, j;
  253.     int vers = poly->vers ;
  254. /*printf("EdgeSearchPoly: (%d,%d,%d)-(%d,%d,%d)\n",
  255.         edge->min[0], edge->min[1], edge->min[2],
  256.         edge->max[0], edge->max[1], edge->max[2]);*/
  257.  
  258.     for( i = 0 ; i < vers ; i++ )
  259.     {
  260. /*printf("Check (%d,%d,%d)\n", poly->ver[i].x, poly->ver[i].y, poly->ver[i].z);*/
  261.         if (edge->min[0] <= poly->ver[i].x && poly->ver[i].x <= edge->max[0]
  262.          && edge->min[1] <= poly->ver[i].y && poly->ver[i].y <= edge->max[1]
  263.          && edge->min[2] <= poly->ver[i].z && poly->ver[i].z <= edge->max[2]) {
  264.             int ip = i-1, in = i+1;
  265.             if (i == 0) ip = vers-1;
  266.             if (i == vers-1) in = 0;
  267.             for (j = 0; j < edge->edges; ++j) {
  268.                 if (poly->ver[i].x == edge->edge[j].x1
  269.                  && poly->ver[i].y == edge->edge[j].y1
  270.                  && poly->ver[i].z == edge->edge[j].z1) {
  271.                     if ((poly->ver[ip].x == edge->edge[j].x2
  272.                       && poly->ver[ip].y == edge->edge[j].y2
  273.                       && poly->ver[ip].z == edge->edge[j].z2)
  274.                      || (poly->ver[in].x == edge->edge[j].x2
  275.                       && poly->ver[in].y == edge->edge[j].y2
  276.                       && poly->ver[in].z == edge->edge[j].z2)) {
  277. /*printf("hit\n");*/
  278.                         return TRUE;
  279.                     }
  280.                 }
  281.             }
  282.         }
  283.     }
  284. /*printf("miss\n");*/
  285.     return FALSE;
  286. }
  287.  
  288. EdgeClass    *EdgeSelectVertex(EdgeClass *edge, Vertex *p1)
  289. {
  290.     int i, ni;
  291.     if (p1->x < edge->min[0] || p1->y < edge->min[1] || p1->z < edge->min[2]
  292.      || p1->x > edge->max[0] || p1->y > edge->max[1] || p1->z > edge->max[2]) {
  293.         edge->edges = 0;
  294.         return edge;
  295.     }
  296.     ni = 0;
  297.     for (i = 0; i < edge->edges; ++i) {
  298.         if ((edge->edge[i].x1 == p1->x
  299.           && edge->edge[i].y1 == p1->y
  300.           && edge->edge[i].z1 == p1->z)
  301.          || (edge->edge[i].x2 == p1->x
  302.           && edge->edge[i].y2 == p1->y
  303.           && edge->edge[i].z2 == p1->z)) {
  304.             if (ni != i) {
  305.                 edge->edge[ni] = edge->edge[i];
  306.             }
  307.             ni++;
  308.         }
  309.     }
  310.     edge->edges = ni;
  311.     return edge;
  312. }
  313.  
  314. EdgeClass    *EdgeMulMatrix(EdgeClass *edge, MatrixClass* mat)
  315. {
  316.     int    imat[5][3];
  317.     int i, x, y, z;
  318.     EdgeData *ed;
  319.     MatToInt( imat, mat->mat );
  320.     ed = edge->edge;
  321.     for (i = 0; i < edge->edges; i++) {
  322.         x = (int)ed->x1 * imat[0][0]
  323.           + (int)ed->y1 * imat[1][0]
  324.           + (int)ed->z1 * imat[2][0]
  325.           + imat[4][0] ;
  326.         y = (int)ed->x1 * imat[0][1]
  327.           + (int)ed->y1 * imat[1][1]
  328.           + (int)ed->z1 * imat[2][1]
  329.           + imat[4][1] ;
  330.         z = (int)ed->x1 * imat[0][2]
  331.           + (int)ed->y1 * imat[1][2]
  332.           + (int)ed->z1 * imat[2][2]
  333.           + imat[4][2] ;
  334.         if (x > 0) {
  335.             ed->x1 = imat[3][0] + (short)( ( x + 32767) >> 16 );
  336.         } else {
  337.             ed->x1 = imat[3][0] - (short)( (-x + 32767) >> 16 );
  338.         }
  339.         if (y > 0) {
  340.             ed->y1 = imat[3][1] + (short)( ( y + 32767) >> 16 );
  341.         } else {
  342.             ed->y1 = imat[3][1] - (short)( (-y + 32767) >> 16 );
  343.         }
  344.         if (z > 0) {
  345.             ed->z1 = imat[3][2] + (short)( ( z + 32767) >> 16 );
  346.         } else {
  347.             ed->z1 = imat[3][2] - (short)( (-z + 32767) >> 16 );
  348.         }
  349.  
  350.         x = (int)ed->x2 * imat[0][0]
  351.           + (int)ed->y2 * imat[1][0]
  352.           + (int)ed->z2 * imat[2][0]
  353.           + imat[4][0] ;
  354.         y = (int)ed->x2 * imat[0][1]
  355.           + (int)ed->y2 * imat[1][1]
  356.           + (int)ed->z2 * imat[2][1]
  357.           + imat[4][1] ;
  358.         z = (int)ed->x2 * imat[0][2]
  359.           + (int)ed->y2 * imat[1][2]
  360.           + (int)ed->z2 * imat[2][2]
  361.           + imat[4][2] ;
  362.         if (x > 0) {
  363.             ed->x2 = imat[3][0] + (short)( ( x + 32767) >> 16 );
  364.         } else {
  365.             ed->x2 = imat[3][0] - (short)( (-x + 32767) >> 16 );
  366.         }
  367.         if (y > 0) {
  368.             ed->y2 = imat[3][1] + (short)( ( y + 32767) >> 16 );
  369.         } else {
  370.             ed->y2 = imat[3][1] - (short)( (-y + 32767) >> 16 );
  371.         }
  372.         if (z > 0) {
  373.             ed->z2 = imat[3][2] + (short)( ( z + 32767) >> 16 );
  374.         } else {
  375.             ed->z2 = imat[3][2] - (short)( (-z + 32767) >> 16 );
  376.         }
  377.  
  378.         ed++;
  379.     }
  380.     return edge;
  381. }
  382.  
  383. EdgeClass    *EdgeLogicalOr(EdgeClass *e1, EdgeClass *e2)
  384. {
  385.     int i, pos;
  386.     for (i = 0; i < e2->edges; i++) {
  387.         if ((pos = EdgeSearchEdge(e1, &e2->edge[i])) < 0) {
  388.             e1 = EdgeAppendEdge(e1, &e2->edge[i]);
  389.         } else {
  390.             e1->edge[pos].count += e2->edge[i].count;
  391.         }
  392.     }
  393.     return e1;
  394. }
  395.  
  396. EdgeClass    *EdgeLogicalSub(EdgeClass *e1, EdgeClass *e2)
  397. {
  398.     int i, pos;
  399.     for (i = 0; i < e2->edges; i++) {
  400.         if ((pos = EdgeSearchEdge(e1, &e2->edge[i])) >= 0) {
  401.             e1 = EdgeDeletePos(e1, pos);
  402.         }
  403.     }
  404.     return e1;
  405. }
  406.  
  407. EdgeClass    *EdgeLogicalAnd(EdgeClass *e1, EdgeClass *e2)
  408. {
  409.     int i, pos;
  410.     EdgeClass *edge;
  411.     edge = EdgeAlloc(0);
  412.     for (i = 0; i < e2->edges; i++) {
  413.         if ((pos = EdgeSearchEdge(e1, &e2->edge[i])) >= 0) {
  414.             edge = EdgeAppendEdge(edge, &e1->edge[pos]);
  415.         }
  416.     }
  417.     ObjectFree((Object*)e1);
  418.     return edge;
  419. }
  420.  
  421. EdgeClass    *EdgeLogicalXor(EdgeClass *e1, EdgeClass *e2)
  422. {
  423.     int i, pos;
  424.     for (i = 0; i < e2->edges; i++) {
  425.         if ((pos = EdgeSearchEdge(e1, &e2->edge[i])) >= 0) {
  426.             e1 = EdgeDeletePos(e1, pos);
  427.         } else {
  428.             e1 = EdgeAppendEdge(e1, &e2->edge[i]);
  429.         }
  430.     }
  431.     return e1;
  432. }
  433.  
  434. int    EdgeLogicalEqual(EdgeClass *e1, EdgeClass *e2)
  435. {
  436.     int i;
  437.     for (i = 0; i < e1->edges; i++) {
  438.         if (EdgeSearchEdge(e2, &e1->edge[i]) < 0) {
  439.             return FALSE;
  440.         }
  441.     }
  442.     for (i = 0; i < e2->edges; i++) {
  443.         if (EdgeSearchEdge(e1, &e2->edge[i]) < 0) {
  444.             return FALSE;
  445.         }
  446.     }
  447.     return TRUE;
  448. }
  449.  
  450. EdgeClass    *EdgeSelect(void)
  451. {
  452.     int i;
  453.     EdgeClass *edge;
  454.     Polygon    *poly ;
  455.     edge = EdgeAlloc(0);
  456.     poly = PolyTop();
  457.     while( poly != NULL )
  458.     {
  459.         if ( poly->select == ON ) {
  460.             for( i = 1; i < poly->vers; ++i) {
  461.                 edge = EdgeAppend(edge, &poly->ver[i-1], &poly->ver[i]);
  462.             }
  463.             edge = EdgeAppend(edge, &poly->ver[0], &poly->ver[poly->vers-1]);
  464.         }
  465.         poly = BufferNext( poly );
  466.     }
  467.     return edge;
  468. }
  469.  
  470. EdgeClass    *EdgeSelectCount(EdgeClass *edge, int begin, int end)
  471. {
  472.     int i, ni;
  473.     ni = 0;
  474.     for (i = 0; i < edge->edges; ++i) {
  475.         if (begin <= edge->edge[i].count && edge->edge[i].count <= end) {
  476.             if (ni != i) {
  477.                 edge->edge[ni] = edge->edge[i];
  478.             }
  479.             ni++;
  480.         }
  481.     }
  482.     edge->edges = ni;
  483.     return edge;
  484. }
  485.  
  486. static    void    SelectPoly(Polygon *poly, int sel, int flag, int sw )
  487. /* flag :     ON | OFF    */
  488. /* sw :       UPDATE | AND | OR | XOR    */
  489. {
  490.     if ( poly->mode & MODE_INVISIBLE )
  491.         return ;
  492.  
  493.     if ( ! sel )
  494.         flag = ! flag ;
  495.  
  496.     switch( sw & SELECT_LOG )
  497.     {
  498.         case SELECT_UPDATE:
  499.             poly->select = flag ;
  500.             break ;
  501.         case SELECT_AND:
  502.             poly->select &= flag ;
  503.             break ;
  504.         case SELECT_OR:
  505.             poly->select |= flag ;
  506.             break ;
  507.         case SELECT_XOR:
  508.             poly->select ^= flag ;
  509.             break ;
  510.         default:
  511.             assert( FALSE );
  512.     }
  513.  
  514.     if ( poly->select )
  515.         Selects ++ ;
  516. }
  517.  
  518. void    PolySelectEdge( EdgeClass *edge, int flag, int sw)
  519. {
  520.     Polygon    *poly ;
  521.     PolyPtr = NULL ;
  522.  
  523.     Selects = 0 ;
  524.     poly = PolyTop();
  525.     while( poly != NULL )
  526.     {
  527.         SelectPoly( poly, EdgeSearchPoly(edge, poly), flag, sw );
  528.         poly = BufferNext( poly );
  529.     }
  530. }
  531.  
  532. void    DrawEdge(EdgeClass* edge, int color)
  533. {
  534.     int i;
  535.     Vertex v1, v2;
  536.  
  537.     for (i = 0; i < edge->edges; i++) {
  538.         v1.x = edge->edge[i].x1;
  539.         v1.y = edge->edge[i].y1;
  540.         v1.z = edge->edge[i].z1;
  541.         v2.x = edge->edge[i].x2;
  542.         v2.y = edge->edge[i].y2;
  543.         v2.z = edge->edge[i].z2;
  544.  
  545.         ViewLine3D(&v1, &v2, color);
  546.     }
  547. }
  548.  
  549.