home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2006 March / Gamestar_82_2006-03_dvd.iso / DVDStar / Editace / quake4_sdkv10.exe / source / idlib / geometry / Winding.cpp < prev    next >
C/C++ Source or Header  |  2005-11-14  |  34KB  |  1,625 lines
  1.  
  2. #include "../precompiled.h"
  3. #pragma hdrstop
  4.  
  5.  
  6. //===============================================================
  7. //
  8. //    idWinding
  9. //
  10. //===============================================================
  11.  
  12. /*
  13. =============
  14. idWinding::ReAllocate
  15. =============
  16. */
  17. bool idWinding::ReAllocate( int n, bool keep ) {
  18.     idVec5 *oldP;
  19.  
  20. // RAVEN BEGIN
  21. // mwhitlock: Dynamic memory consolidation
  22.     RV_PUSH_HEAP_MEM_AUTO(p0,this);
  23. // RAVEN END
  24.  
  25.     oldP = p;
  26.     n = (n+3) & ~3;    // align up to multiple of four
  27.     p = new idVec5[n];
  28.     if ( oldP ) {
  29.         if ( keep ) {
  30.             memcpy( p, oldP, numPoints * sizeof(p[0]) );
  31.         }
  32.         delete[] oldP;
  33.     }
  34.     allocedSize = n;
  35.  
  36.     return true;
  37. }
  38.  
  39. /*
  40. =============
  41. idWinding::BaseForPlane
  42. =============
  43. */
  44. void idWinding::BaseForPlane( const idVec3 &normal, const float dist ) {
  45.     idVec3 org, vright, vup;
  46.  
  47.     org = normal * dist;
  48.  
  49.     normal.NormalVectors( vup, vright );
  50.     vup *= MAX_WORLD_SIZE;
  51.     vright *= MAX_WORLD_SIZE;
  52.  
  53.     EnsureAlloced( 4 );
  54.     numPoints = 4;
  55.     p[0].ToVec3() = org - vright + vup;
  56.     p[0].s = p[0].t = 0.0f;
  57.     p[1].ToVec3() = org + vright + vup;
  58.     p[1].s = p[1].t = 0.0f;
  59.     p[2].ToVec3() = org + vright - vup;
  60.     p[2].s = p[2].t = 0.0f;
  61.     p[3].ToVec3() = org - vright - vup;
  62.     p[3].s = p[3].t = 0.0f;
  63. }
  64.  
  65. /*
  66. =============
  67. idWinding::Split
  68. =============
  69. */
  70. int idWinding::Split( const idPlane &plane, const float epsilon, idWinding **front, idWinding **back ) const {
  71.     float *            dists;
  72.     byte *            sides;
  73.     int                counts[3];
  74.     float            dot;
  75.     int                i, j;
  76.     const idVec5 *    p1, *p2;
  77.     idVec5            mid;
  78.     idWinding *        f, *b;
  79.     int                maxpts;
  80.  
  81.     assert( this );
  82.  
  83.     dists = (float *) _alloca( (numPoints+4) * sizeof( float ) );
  84.     sides = (byte *) _alloca( (numPoints+4) * sizeof( byte ) );
  85.  
  86.     counts[0] = counts[1] = counts[2] = 0;
  87.  
  88.     // determine sides for each point
  89.     for ( i = 0; i < numPoints; i++ ) {
  90.         dists[i] = dot = plane.Distance( p[i].ToVec3() );
  91.         if ( dot > epsilon ) {
  92.             sides[i] = SIDE_FRONT;
  93.         } else if ( dot < -epsilon ) {
  94.             sides[i] = SIDE_BACK;
  95.         } else {
  96.             sides[i] = SIDE_ON;
  97.         }
  98.         counts[sides[i]]++;
  99.     }
  100.     sides[i] = sides[0];
  101.     dists[i] = dists[0];
  102.     
  103.     *front = *back = NULL;
  104.  
  105.     // if coplanar, put on the front side if the normals match
  106.     if ( !counts[SIDE_FRONT] && !counts[SIDE_BACK] ) {
  107.         idPlane windingPlane;
  108.  
  109.         GetPlane( windingPlane );
  110.         if ( windingPlane.Normal() * plane.Normal() > 0.0f ) {
  111.             *front = Copy();
  112.             return SIDE_FRONT;
  113.         } else {
  114.             *back = Copy();
  115.             return SIDE_BACK;
  116.         }
  117.     }
  118.     // if nothing at the front of the clipping plane
  119.     if ( !counts[SIDE_FRONT] ) {
  120.         *back = Copy();
  121.         return SIDE_BACK;
  122.     }
  123.     // if nothing at the back of the clipping plane
  124.     if ( !counts[SIDE_BACK] ) {
  125.         *front = Copy();
  126.         return SIDE_FRONT;
  127.     }
  128.  
  129.     maxpts = numPoints+4;    // cant use counts[0]+2 because of fp grouping errors
  130.  
  131. // RAVEN BEGIN
  132. // mwhitlock: Dynamic memory consolidation
  133.     RV_PUSH_HEAP_MEM_AUTO(p0,this);
  134. // RAVEN END
  135.  
  136.     *front = f = new idWinding(maxpts);
  137.     *back = b = new idWinding(maxpts);
  138.         
  139.     for (i = 0; i < numPoints; i++) {
  140.         p1 = &p[i];
  141.         
  142.         if ( sides[i] == SIDE_ON ) {
  143.             f->p[f->numPoints] = *p1;
  144.             f->numPoints++;
  145.             b->p[b->numPoints] = *p1;
  146.             b->numPoints++;
  147.             continue;
  148.         }
  149.     
  150.         if ( sides[i] == SIDE_FRONT ) {
  151.             f->p[f->numPoints] = *p1;
  152.             f->numPoints++;
  153.         }
  154.  
  155.         if ( sides[i] == SIDE_BACK ) {
  156.             b->p[b->numPoints] = *p1;
  157.             b->numPoints++;
  158.         }
  159.  
  160.         if ( sides[i+1] == SIDE_ON || sides[i+1] == sides[i] ) {
  161.             continue;
  162.         }
  163.             
  164.         // generate a split point
  165.         p2 = &p[(i+1)%numPoints];
  166.         
  167.         // always calculate the split going from the same side
  168.         // or minor epsilon issues can happen
  169.         if ( sides[i] == SIDE_FRONT ) {
  170.             dot = dists[i] / ( dists[i] - dists[i+1] );
  171.             for ( j = 0; j < 3; j++ ) {
  172.                 // avoid round off error when possible
  173.                 if ( plane.Normal()[j] == 1.0f ) {
  174.                     mid[j] = plane.Dist();
  175.                 } else if ( plane.Normal()[j] == -1.0f ) {
  176.                     mid[j] = -plane.Dist();
  177.                 } else {
  178.                     mid[j] = (*p1)[j] + dot * ( (*p2)[j] - (*p1)[j] );
  179.                 }
  180.             }
  181.             mid.s = p1->s + dot * ( p2->s - p1->s );
  182.             mid.t = p1->t + dot * ( p2->t - p1->t );
  183.         } else {
  184.             dot = dists[i+1] / ( dists[i+1] - dists[i] );
  185.             for ( j = 0; j < 3; j++ ) {    
  186.                 // avoid round off error when possible
  187.                 if ( plane.Normal()[j] == 1.0f ) {
  188.                     mid[j] = plane.Dist();
  189.                 } else if ( plane.Normal()[j] == -1.0f ) {
  190.                     mid[j] = -plane.Dist();
  191.                 } else {
  192.                     mid[j] = (*p2)[j] + dot * ( (*p1)[j] - (*p2)[j] );
  193.                 }
  194.             }
  195.             mid.s = p2->s + dot * ( p1->s - p2->s );
  196.             mid.t = p2->t + dot * ( p1->t - p2->t );
  197.         }
  198.  
  199.         f->p[f->numPoints] = mid;
  200.         f->numPoints++;
  201.         b->p[b->numPoints] = mid;
  202.         b->numPoints++;
  203.     }
  204.     
  205.     if ( f->numPoints > maxpts || b->numPoints > maxpts ) {
  206.         idLib::common->FatalError( "idWinding::Split: points exceeded estimate." );
  207.     }
  208.  
  209.     return SIDE_CROSS;
  210. }
  211.  
  212. /*
  213. =============
  214. idWinding::Clip
  215. =============
  216. */
  217. idWinding *idWinding::Clip( const idPlane &plane, const float epsilon, const bool keepOn ) {
  218.     float *        dists;
  219.     byte *        sides;
  220.     idVec5 *    newPoints;
  221.     int            newNumPoints;
  222.     int            counts[3];
  223.     float        dot;
  224.     int            i, j;
  225.     idVec5 *    p1, *p2;
  226.     idVec5        mid;
  227.     int            maxpts;
  228.  
  229.     assert( this );
  230.  
  231.     dists = (float *) _alloca( (numPoints+4) * sizeof( float ) );
  232.     sides = (byte *) _alloca( (numPoints+4) * sizeof( byte ) );
  233.  
  234.     counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
  235.  
  236.     // determine sides for each point
  237.     for ( i = 0; i < numPoints; i++ ) {
  238.         dists[i] = dot = plane.Distance( p[i].ToVec3() );
  239.         if ( dot > epsilon ) {
  240.             sides[i] = SIDE_FRONT;
  241.         } else if ( dot < -epsilon ) {
  242.             sides[i] = SIDE_BACK;
  243.         } else {
  244.             sides[i] = SIDE_ON;
  245.         }
  246.         counts[sides[i]]++;
  247.     }
  248.     sides[i] = sides[0];
  249.     dists[i] = dists[0];
  250.  
  251.     // if the winding is on the plane and we should keep it
  252.     if ( keepOn && !counts[SIDE_FRONT] && !counts[SIDE_BACK] ) {
  253.         return this;
  254.     }
  255.     // if nothing at the front of the clipping plane
  256.     if ( !counts[SIDE_FRONT] ) {
  257.         delete this;
  258.         return NULL;
  259.     }
  260.     // if nothing at the back of the clipping plane
  261.     if ( !counts[SIDE_BACK] ) {
  262.         return this;
  263.     }
  264.  
  265.     maxpts = numPoints + 4;        // cant use counts[0]+2 because of fp grouping errors
  266.  
  267.     newPoints = (idVec5 *) _alloca16( maxpts * sizeof( idVec5 ) );
  268.     newNumPoints = 0;
  269.         
  270.     for ( i = 0; i < numPoints; i++ ) {
  271.         p1 = &p[i];
  272.  
  273.         if ( newNumPoints+1 > maxpts ) {
  274.             return this;        // can't split -- fall back to original
  275.         }
  276.  
  277.         if ( sides[i] == SIDE_ON ) {
  278.             newPoints[newNumPoints] = *p1;
  279.             newNumPoints++;
  280.             continue;
  281.         }
  282.  
  283.         if ( sides[i] == SIDE_FRONT ) {
  284.             newPoints[newNumPoints] = *p1;
  285.             newNumPoints++;
  286.         }
  287.  
  288.         if ( sides[i+1] == SIDE_ON || sides[i+1] == sides[i] ) {
  289.             continue;
  290.         }
  291.  
  292.         if ( newNumPoints+1 > maxpts ) {
  293.             return this;        // can't split -- fall back to original
  294.         }
  295.  
  296.         // generate a split point
  297.         p2 = &p[(i+1)%numPoints];
  298.  
  299.         dot = dists[i] / (dists[i] - dists[i+1]);
  300.         for ( j = 0; j < 3; j++ ) {
  301.             // avoid round off error when possible
  302.             if ( plane.Normal()[j] == 1.0f ) {
  303.                 mid[j] = plane.Dist();
  304.             } else if ( plane.Normal()[j] == -1.0f ) {
  305.                 mid[j] = -plane.Dist();
  306.             } else {
  307.                 mid[j] = (*p1)[j] + dot * ( (*p2)[j] - (*p1)[j] );
  308.             }
  309.         }
  310.         mid.s = p1->s + dot * ( p2->s - p1->s );
  311.         mid.t = p1->t + dot * ( p2->t - p1->t );
  312.  
  313.         newPoints[newNumPoints] = mid;
  314.         newNumPoints++;
  315.     }
  316.     
  317.     if ( !EnsureAlloced( newNumPoints, false ) ) {
  318.         return this;
  319.     }
  320.  
  321.     numPoints = newNumPoints;
  322.     memcpy( p, newPoints, newNumPoints * sizeof(idVec5) );
  323.  
  324.     return this;
  325. }
  326.  
  327. /*
  328. =============
  329. idWinding::ClipInPlace
  330. =============
  331. */
  332. bool idWinding::ClipInPlace( const idPlane &plane, const float epsilon, const bool keepOn ) {
  333.     float*        dists;
  334.     byte *        sides;
  335.     idVec5 *    newPoints;
  336.     int            newNumPoints;
  337.     int            counts[3];
  338.     float        dot;
  339.     int            i, j;
  340.     idVec5 *    p1, *p2;
  341.     idVec5        mid;
  342.     int            maxpts;
  343.  
  344.     assert( this );
  345.  
  346.     dists = (float *) _alloca( (numPoints+4) * sizeof( float ) );
  347.     sides = (byte *) _alloca( (numPoints+4) * sizeof( byte ) );
  348.  
  349.     counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
  350.  
  351.     // determine sides for each point
  352.     for ( i = 0; i < numPoints; i++ ) {
  353.         dists[i] = dot = plane.Distance( p[i].ToVec3() );
  354.         if ( dot > epsilon ) {
  355.             sides[i] = SIDE_FRONT;
  356.         } else if ( dot < -epsilon ) {
  357.             sides[i] = SIDE_BACK;
  358.         } else {
  359.             sides[i] = SIDE_ON;
  360.         }
  361.         counts[sides[i]]++;
  362.     }
  363.     sides[i] = sides[0];
  364.     dists[i] = dists[0];
  365.     
  366.     // if the winding is on the plane and we should keep it
  367.     if ( keepOn && !counts[SIDE_FRONT] && !counts[SIDE_BACK] ) {
  368.         return true;
  369.     }
  370.     // if nothing at the front of the clipping plane
  371.     if ( !counts[SIDE_FRONT] ) {
  372.         numPoints = 0;
  373.         return false;
  374.     }
  375.     // if nothing at the back of the clipping plane
  376.     if ( !counts[SIDE_BACK] ) {
  377.         return true;
  378.     }
  379.  
  380.     maxpts = numPoints + 4;        // cant use counts[0]+2 because of fp grouping errors
  381.  
  382.     newPoints = (idVec5 *) _alloca16( maxpts * sizeof( idVec5 ) );
  383.     newNumPoints = 0;
  384.  
  385.     for ( i = 0; i < numPoints; i++ ) {
  386.         p1 = &p[i];
  387.  
  388.         if ( newNumPoints+1 > maxpts ) {
  389.             return true;        // can't split -- fall back to original
  390.         }
  391.         
  392.         if ( sides[i] == SIDE_ON ) {
  393.             newPoints[newNumPoints] = *p1;
  394.             newNumPoints++;
  395.             continue;
  396.         }
  397.     
  398.         if ( sides[i] == SIDE_FRONT ) {
  399.             newPoints[newNumPoints] = *p1;
  400.             newNumPoints++;
  401.         }
  402.  
  403.         if ( sides[i+1] == SIDE_ON || sides[i+1] == sides[i] ) {
  404.             continue;
  405.         }
  406.             
  407.         if ( newNumPoints+1 > maxpts ) {
  408.             return true;        // can't split -- fall back to original
  409.         }
  410.  
  411.         // generate a split point
  412.         p2 = &p[(i+1)%numPoints];
  413.         
  414.         dot = dists[i] / (dists[i] - dists[i+1]);
  415.         for ( j = 0; j < 3; j++ ) {
  416.             // avoid round off error when possible
  417.             if ( plane.Normal()[j] == 1.0f ) {
  418.                 mid[j] = plane.Dist();
  419.             } else if ( plane.Normal()[j] == -1.0f ) {
  420.                 mid[j] = -plane.Dist();
  421.             } else {
  422.                 mid[j] = (*p1)[j] + dot * ( (*p2)[j] - (*p1)[j] );
  423.             }
  424.         }
  425.         mid.s = p1->s + dot * ( p2->s - p1->s );
  426.         mid.t = p1->t + dot * ( p2->t - p1->t );
  427.             
  428.         newPoints[newNumPoints] = mid;
  429.         newNumPoints++;
  430.     }
  431.  
  432.     if ( !EnsureAlloced( newNumPoints, false ) ) {
  433.         return true;
  434.     }
  435.  
  436.     numPoints = newNumPoints;
  437.     memcpy( p, newPoints, newNumPoints * sizeof(idVec5) );
  438.  
  439.     return true;
  440. }
  441.  
  442. /*
  443. =============
  444. idWinding::Copy
  445. =============
  446. */
  447. idWinding *idWinding::Copy( void ) const {
  448.     idWinding *w;
  449.  
  450. // RAVEN BEGIN
  451. // mwhitlock: Dynamic memory consolidation
  452.     RV_PUSH_HEAP_MEM_AUTO(p0,this);
  453. // RAVEN END
  454.  
  455.     w = new idWinding( numPoints );
  456.     w->numPoints = numPoints;
  457.     memcpy( w->p, p, numPoints * sizeof(p[0]) );
  458.     return w;
  459. }
  460.  
  461. /*
  462. =============
  463. idWinding::Reverse
  464. =============
  465. */
  466. idWinding *idWinding::Reverse( void ) const {
  467.     idWinding *w;
  468.     int i;
  469.  
  470. // RAVEN BEGIN
  471. // mwhitlock: Dynamic memory consolidation
  472.     RV_PUSH_HEAP_MEM_AUTO(p0,this);
  473. // RAVEN END
  474.  
  475.     w = new idWinding( numPoints );
  476.     w->numPoints = numPoints;
  477.     for ( i = 0; i < numPoints; i++ ) {
  478.         w->p[ numPoints - i - 1 ] = p[i];
  479.     }
  480.     return w;
  481. }
  482.  
  483. /*
  484. =============
  485. idWinding::ReverseSelf
  486. =============
  487. */
  488. void idWinding::ReverseSelf( void ) {
  489.     idVec5 v;
  490.     int i;
  491.  
  492.     for ( i = 0; i < (numPoints>>1); i++ ) {
  493.         v = p[i];
  494.         p[i] = p[numPoints - i - 1];
  495.         p[numPoints - i - 1] = v;
  496.     }
  497. }
  498.  
  499. /*
  500. =============
  501. idWinding::Check
  502. =============
  503. */
  504. bool idWinding::Check( bool print ) const {
  505.     int                i, j;
  506.     float            d, edgedist;
  507.     idVec3            dir, edgenormal;
  508.     float            area;
  509.     idPlane            plane;
  510.  
  511.     if ( numPoints < 3 ) {
  512.         if ( print ) {
  513.             idLib::common->Printf( "idWinding::Check: only %i points.", numPoints );
  514.         }
  515.         return false;
  516.     }
  517.     
  518.     area = GetArea();
  519.     if ( area < 1.0f ) {
  520.         if ( print ) {
  521.             idLib::common->Printf( "idWinding::Check: tiny area: %f", area );
  522.         }
  523.         return false;
  524.     }
  525.  
  526.     GetPlane( plane );
  527.     
  528.     for ( i = 0; i < numPoints; i++ ) {
  529.         const idVec3 &p1 = p[i].ToVec3();
  530.  
  531.         // check if the winding is huge
  532.         for ( j = 0; j < 3; j++ ) {
  533.             if ( p1[j] >= MAX_WORLD_COORD || p1[j] <= MIN_WORLD_COORD ) {
  534.                 if ( print ) {
  535.                     idLib::common->Printf( "idWinding::Check: point %d outside world %c-axis: %f", i, 'X'+j, p1[j] );
  536.                 }
  537.                 return false;
  538.             }
  539.         }
  540.  
  541.         j = i + 1 == numPoints ? 0 : i + 1;
  542.         
  543.         // check if the point is on the face plane
  544.         d = p1 * plane.Normal() + plane[3];
  545.         if ( d < -ON_EPSILON || d > ON_EPSILON ) {
  546.             if ( print ) {
  547.                 idLib::common->Printf( "idWinding::Check: point %d off plane.", i );
  548.             }
  549.             return false;
  550.         }
  551.     
  552.         // check if the edge isn't degenerate
  553.         const idVec3 &p2 = p[j].ToVec3();
  554.         dir = p2 - p1;
  555.         
  556.         if ( dir.Length() < ON_EPSILON) {
  557.             if ( print ) {
  558.                 idLib::common->Printf( "idWinding::Check: edge %d is degenerate.", i );
  559.             }
  560.             return false;
  561.         }
  562.  
  563.         // check if the winding is convex
  564.         edgenormal = plane.Normal().Cross( dir );
  565.         edgenormal.Normalize();
  566.         edgedist = p1 * edgenormal;
  567.         edgedist += ON_EPSILON;
  568.         
  569.         // all other points must be on front side
  570.         for ( j = 0; j < numPoints; j++ ) {
  571.             if ( j == i ) {
  572.                 continue;
  573.             }
  574.             d = p[j].ToVec3() * edgenormal;
  575.             if ( d > edgedist ) {
  576.                 if ( print ) {
  577.                     idLib::common->Printf( "idWinding::Check: non-convex." );
  578.                 }
  579.                 return false;
  580.             }
  581.         }
  582.     }
  583.     return true;
  584. }
  585.  
  586. /*
  587. =============
  588. idWinding::GetArea
  589. =============
  590. */
  591. float idWinding::GetArea( void ) const {
  592.     int i;
  593.     idVec3 d1, d2, cross;
  594.     float total;
  595.  
  596.     total = 0.0f;
  597.     for ( i = 2; i < numPoints; i++ ) {
  598.         d1 = p[i-1].ToVec3() - p[0].ToVec3();
  599.         d2 = p[i].ToVec3() - p[0].ToVec3();
  600.         cross = d1.Cross( d2 );
  601.         total += cross.Length();
  602.     }
  603.     return total * 0.5f;
  604. }
  605.  
  606. /*
  607. =============
  608. idWinding::GetRadius
  609. =============
  610. */
  611. float idWinding::GetRadius( const idVec3 ¢er ) const {
  612.     int i;
  613.     float radius, r;
  614.     idVec3 dir;
  615.  
  616.     radius = 0.0f;
  617.     for ( i = 0; i < numPoints; i++ ) {
  618.         dir = p[i].ToVec3() - center;
  619.         r = dir * dir;
  620.         if ( r > radius ) {
  621.             radius = r;
  622.         }
  623.     }
  624.     return idMath::Sqrt( radius );
  625. }
  626.  
  627. /*
  628. =============
  629. idWinding::GetCenter
  630. =============
  631. */
  632. idVec3 idWinding::GetCenter( void ) const {
  633.     int i;
  634.     idVec3 center;
  635.  
  636.     center.Zero();
  637.     for ( i = 0; i < numPoints; i++ ) {
  638.         center += p[i].ToVec3();
  639.     }
  640.     center *= ( 1.0f / numPoints );
  641.     return center;
  642. }
  643.  
  644. // RAVEN BEGIN
  645. // scork: Splash Damage's light-resize code
  646. /*
  647. =============
  648. idWinding::GetNormal
  649. =============
  650. */
  651. idVec3 idWinding::GetNormal( void ) const {
  652.     idVec3 v1, v2, center, normal;
  653.  
  654.     if ( numPoints < 3 ) {
  655.         normal.Zero();
  656.         return normal;
  657.     }
  658.  
  659.     center = GetCenter();
  660.     v1 = p[0].ToVec3() - center;
  661.     v2 = p[1].ToVec3() - center;
  662.     normal = v2.Cross( v1 );
  663.     normal.Normalize();
  664.     return normal;
  665. }
  666. // RAVEN END
  667.  
  668. /*
  669. =============
  670. idWinding::GetPlane
  671. =============
  672. */
  673. void idWinding::GetPlane( idVec3 &normal, float &dist ) const {
  674.     idVec3 v1, v2, center;
  675.  
  676.     if ( numPoints < 3 ) {
  677.         normal.Zero();
  678.         dist = 0.0f;
  679.         return;
  680.     }
  681.  
  682.     center = GetCenter();
  683.     v1 = p[0].ToVec3() - center;
  684.     v2 = p[1].ToVec3() - center;
  685.     normal = v2.Cross( v1 );
  686.     normal.Normalize();
  687.     dist = p[0].ToVec3() * normal;
  688. }
  689.  
  690. /*
  691. =============
  692. idWinding::GetPlane
  693. =============
  694. */
  695. void idWinding::GetPlane( idPlane &plane ) const {
  696.     idVec3 v1, v2;
  697.     idVec3 center;
  698.  
  699.     if ( numPoints < 3 ) {
  700.         plane.Zero();
  701.         return;
  702.     }
  703.  
  704.     center = GetCenter();
  705.     v1 = p[0].ToVec3() - center;
  706.     v2 = p[1].ToVec3() - center;
  707.     plane.SetNormal( v2.Cross( v1 ) );
  708.     plane.Normalize();
  709.     plane.FitThroughPoint( p[0].ToVec3() );
  710. }
  711.  
  712. /*
  713. =============
  714. idWinding::GetBounds
  715. =============
  716. */
  717. void idWinding::GetBounds( idBounds &bounds ) const {
  718.     int i;
  719.  
  720.     if ( !numPoints ) {
  721.         bounds.Clear();
  722.         return;
  723.     }
  724.  
  725.     bounds[0] = bounds[1] = p[0].ToVec3();
  726.     for ( i = 1; i < numPoints; i++ ) {
  727.         if ( p[i].x < bounds[0].x ) {
  728.             bounds[0].x = p[i].x;
  729.         } else if ( p[i].x > bounds[1].x ) {
  730.             bounds[1].x = p[i].x;
  731.         }
  732.         if ( p[i].y < bounds[0].y ) {
  733.             bounds[0].y = p[i].y;
  734.         } else if ( p[i].y > bounds[1].y ) {
  735.             bounds[1].y = p[i].y;
  736.         }
  737.         if ( p[i].z < bounds[0].z ) {
  738.             bounds[0].z = p[i].z;
  739.         } else if ( p[i].z > bounds[1].z ) {
  740.             bounds[1].z = p[i].z;
  741.         }
  742.     }
  743. }
  744.  
  745. /*
  746. =============
  747. idWinding::RemoveEqualPoints
  748. =============
  749. */
  750. void idWinding::RemoveEqualPoints( const float epsilon ) {
  751.     int i, j;
  752.  
  753.     for ( i = 0; i < numPoints; i++ ) {
  754.         if ( (p[i].ToVec3() - p[(i+numPoints-1)%numPoints].ToVec3()).LengthSqr() >= Square( epsilon ) ) {
  755.             continue;
  756.         }
  757.         numPoints--;
  758.         for ( j = i; j < numPoints; j++ ) {
  759.             p[j] = p[j+1];
  760.         }
  761.         i--;
  762.     }
  763. }
  764.  
  765. /*
  766. =============
  767. idWinding::RemoveColinearPoints
  768. =============
  769. */
  770. void idWinding::RemoveColinearPoints( const idVec3 &normal, const float epsilon ) {
  771.     int i, j;
  772.     idVec3 edgeNormal;
  773.     float dist;
  774.  
  775.     if ( numPoints <= 3 ) {
  776.         return;
  777.     }
  778.  
  779.     for ( i = 0; i < numPoints; i++ ) {
  780.  
  781.         // create plane through edge orthogonal to winding plane
  782.         edgeNormal = (p[i].ToVec3() - p[(i+numPoints-1)%numPoints].ToVec3()).Cross( normal );
  783.         edgeNormal.Normalize();
  784.         dist = edgeNormal * p[i].ToVec3();
  785.  
  786.         if ( idMath::Fabs( edgeNormal * p[(i+1)%numPoints].ToVec3() - dist ) > epsilon ) {
  787.             continue;
  788.         }
  789.  
  790.         numPoints--;
  791.         for ( j = i; j < numPoints; j++ ) {
  792.             p[j] = p[j+1];
  793.         }
  794.         i--;
  795.     }
  796. }
  797.  
  798. /*
  799. =============
  800. idWinding::AddToConvexHull
  801.  
  802.   Adds the given winding to the convex hull.
  803.   Assumes the current winding already is a convex hull with three or more points.
  804. =============
  805. */
  806. void idWinding::AddToConvexHull( const idWinding *winding, const idVec3 &normal, const float epsilon ) {
  807.     int                i, j, k;
  808.     idVec3            dir;
  809.     float            d;
  810.     int                maxPts;
  811.     idVec3 *        hullDirs;
  812.     bool *            hullSide;
  813.     bool            outside;
  814.     int                numNewHullPoints;
  815.     idVec5 *        newHullPoints;
  816.  
  817.     if ( !winding ) {
  818.         return;
  819.     }
  820.  
  821.     maxPts = this->numPoints + winding->numPoints;
  822.  
  823.     if ( !this->EnsureAlloced( maxPts, true ) ) {
  824.         return;
  825.     }
  826.  
  827.     newHullPoints = (idVec5 *) _alloca( maxPts * sizeof( idVec5 ) );
  828.     hullDirs = (idVec3 *) _alloca( maxPts * sizeof( idVec3 ) );
  829.     hullSide = (bool *) _alloca( maxPts * sizeof( bool ) );
  830.  
  831.     for ( i = 0; i < winding->numPoints; i++ ) {
  832.         const idVec5 &p1 = winding->p[i];
  833.  
  834.         // calculate hull edge vectors
  835.         for ( j = 0; j < this->numPoints; j++ ) {
  836.             dir = this->p[ (j + 1) % this->numPoints ].ToVec3() - this->p[ j ].ToVec3();
  837.             dir.Normalize();
  838.             hullDirs[j] = normal.Cross( dir );
  839.         }
  840.  
  841.         // calculate side for each hull edge
  842.         outside = false;
  843.         for ( j = 0; j < this->numPoints; j++ ) {
  844.             dir = p1.ToVec3() - this->p[j].ToVec3();
  845.             d = dir * hullDirs[j];
  846.             if ( d >= epsilon ) {
  847.                 outside = true;
  848.             }
  849.             if ( d >= -epsilon ) {
  850.                 hullSide[j] = true;
  851.             } else {
  852.                 hullSide[j] = false;
  853.             }
  854.         }
  855.  
  856.         // if the point is effectively inside, do nothing
  857.         if ( !outside ) {
  858.             continue;
  859.         }
  860.  
  861.         // find the back side to front side transition
  862.         for ( j = 0; j < this->numPoints; j++ ) {
  863.             if ( !hullSide[ j ] && hullSide[ (j + 1) % this->numPoints ] ) {
  864.                 break;
  865.             }
  866.         }
  867.         if ( j >= this->numPoints ) {
  868.             continue;
  869.         }
  870.  
  871.         // insert the point here
  872.         newHullPoints[0] = p1;
  873.         numNewHullPoints = 1;
  874.  
  875.         // copy over all points that aren't double fronts
  876.         j = (j+1) % this->numPoints;
  877.         for ( k = 0; k < this->numPoints; k++ ) {
  878.             if ( hullSide[ (j+k) % this->numPoints ] && hullSide[ (j+k+1) % this->numPoints ] ) {
  879.                 continue;
  880.             }
  881.             newHullPoints[numNewHullPoints] = this->p[ (j+k+1) % this->numPoints ];
  882.             numNewHullPoints++;
  883.         }
  884.  
  885.         this->numPoints = numNewHullPoints;
  886.         memcpy( this->p, newHullPoints, numNewHullPoints * sizeof(idVec5) );
  887.     }
  888. }
  889.  
  890. /*
  891. =============
  892. idWinding::AddToConvexHull
  893.  
  894.   Add a point to the convex hull.
  895.   The current winding must be convex but may be degenerate and can have less than three points.
  896. =============
  897. */
  898. void idWinding::AddToConvexHull( const idVec3 &point, const idVec3 &normal, const float epsilon ) {
  899.     int                j, k, numHullPoints;
  900.     idVec3            dir;
  901.     float            d;
  902.     idVec3 *        hullDirs;
  903.     bool *            hullSide;
  904.     idVec5 *        hullPoints;
  905.     bool            outside;
  906.  
  907.     switch( numPoints ) {
  908.         case 0: {
  909.             p[0] = point;
  910.             numPoints++;
  911.             return;
  912.         }
  913.         case 1: {
  914.             // don't add the same point second
  915.             if ( p[0].ToVec3().Compare( point, epsilon ) ) {
  916.                 return;
  917.             }
  918.             p[1].ToVec3() = point;
  919.             numPoints++;
  920.             return;
  921.         }
  922.         case 2: {
  923.             // don't add a point if it already exists
  924.             if ( p[0].ToVec3().Compare( point, epsilon ) || p[1].ToVec3().Compare( point, epsilon ) ) {
  925.                 return;
  926.             }
  927.             // if only two points make sure we have the right ordering according to the normal
  928.             dir = point - p[0].ToVec3();
  929.             dir = dir.Cross( p[1].ToVec3() - p[0].ToVec3() );
  930.             if ( dir[0] == 0.0f && dir[1] == 0.0f && dir[2] == 0.0f ) {
  931.                 // points don't make a plane
  932.                 return;
  933.             }
  934.             if ( dir * normal > 0.0f ) {
  935.                 p[2].ToVec3() = point;
  936.             }
  937.             else {
  938.                 p[2] = p[1];
  939.                 p[1].ToVec3() = point;
  940.             }
  941.             numPoints++;
  942.             return;
  943.         }
  944.     }
  945.  
  946.     hullDirs = (idVec3 *) _alloca( numPoints * sizeof( idVec3 ) );
  947.     hullSide = (bool *) _alloca( numPoints * sizeof( bool ) );
  948.  
  949.     // calculate hull edge vectors
  950.     for ( j = 0; j < numPoints; j++ ) {
  951.         dir = p[(j + 1) % numPoints].ToVec3() - p[j].ToVec3();
  952.         hullDirs[j] = normal.Cross( dir );
  953.     }
  954.  
  955.     // calculate side for each hull edge
  956.     outside = false;
  957.     for ( j = 0; j < numPoints; j++ ) {
  958.         dir = point - p[j].ToVec3();
  959.         d = dir * hullDirs[j];
  960.         if ( d >= epsilon ) {
  961.             outside = true;
  962.         }
  963.         if ( d >= -epsilon ) {
  964.             hullSide[j] = true;
  965.         } else {
  966.             hullSide[j] = false;
  967.         }
  968.     }
  969.  
  970.     // if the point is effectively inside, do nothing
  971.     if ( !outside ) {
  972.         return;
  973.     }
  974.  
  975.     // find the back side to front side transition
  976.     for ( j = 0; j < numPoints; j++ ) {
  977.         if ( !hullSide[ j ] && hullSide[ (j + 1) % numPoints ] ) {
  978.             break;
  979.         }
  980.     }
  981.     if ( j >= numPoints ) {
  982.         return;
  983.     }
  984.  
  985.     hullPoints = (idVec5 *) _alloca( (numPoints+1) * sizeof( idVec5 ) );
  986.  
  987.     // insert the point here
  988.     hullPoints[0] = point;
  989.     numHullPoints = 1;
  990.  
  991.     // copy over all points that aren't double fronts
  992.     j = (j+1) % numPoints;
  993.     for ( k = 0; k < numPoints; k++ ) {
  994.         if ( hullSide[ (j+k) % numPoints ] && hullSide[ (j+k+1) % numPoints ] ) {
  995.             continue;
  996.         }
  997.         hullPoints[numHullPoints] = p[ (j+k+1) % numPoints ];
  998.         numHullPoints++;
  999.     }
  1000.  
  1001.     if ( !EnsureAlloced( numHullPoints, false ) ) {
  1002.         return;
  1003.     }
  1004.     numPoints = numHullPoints;
  1005.     memcpy( p, hullPoints, numHullPoints * sizeof(idVec5) );
  1006. }
  1007.  
  1008. /*
  1009. =============
  1010. idWinding::TryMerge
  1011. =============
  1012. */
  1013. #define    CONTINUOUS_EPSILON    0.005f
  1014.  
  1015. idWinding *idWinding::TryMerge( const idWinding &w, const idVec3 &planenormal, int keep ) const {
  1016.     idVec3            *p1, *p2, *p3, *p4, *back;
  1017.     idWinding        *newf;
  1018.     const idWinding    *f1, *f2;
  1019.     int                i, j, k, l;
  1020.     idVec3            normal, delta;
  1021.     float            dot;
  1022.     bool            keep1, keep2;
  1023.  
  1024.     f1 = this;
  1025.     f2 = &w;
  1026.     //
  1027.     // find a idLib::common edge
  1028.     //    
  1029.     p1 = p2 = NULL;    // stop compiler warning
  1030.     j = 0;
  1031.     
  1032.     for ( i = 0; i < f1->numPoints; i++ ) {
  1033.         p1 = &f1->p[i].ToVec3();
  1034.         p2 = &f1->p[(i+1) % f1->numPoints].ToVec3();
  1035.         for ( j = 0; j < f2->numPoints; j++ ) {
  1036.             p3 = &f2->p[j].ToVec3();
  1037.             p4 = &f2->p[(j+1) % f2->numPoints].ToVec3();
  1038.             for (k = 0; k < 3; k++ ) {
  1039.                 if ( idMath::Fabs((*p1)[k] - (*p4)[k]) > 0.1f ) {
  1040.                     break;
  1041.                 }
  1042.                 if ( idMath::Fabs((*p2)[k] - (*p3)[k]) > 0.1f ) {
  1043.                     break;
  1044.                 }
  1045.             }
  1046.             if ( k == 3 ) {
  1047.                 break;
  1048.             }
  1049.         }
  1050.         if ( j < f2->numPoints ) {
  1051.             break;
  1052.         }
  1053.     }
  1054.     
  1055.     if ( i == f1->numPoints ) {
  1056.         return NULL;            // no matching edges
  1057.     }
  1058.  
  1059.     //
  1060.     // check slope of connected lines
  1061.     // if the slopes are colinear, the point can be removed
  1062.     //
  1063.     back = &f1->p[(i+f1->numPoints-1)%f1->numPoints].ToVec3();
  1064.     delta = (*p1) - (*back);
  1065.     normal = planenormal.Cross(delta);
  1066.     normal.Normalize();
  1067.     
  1068.     back = &f2->p[(j+2)%f2->numPoints].ToVec3();
  1069.     delta = (*back) - (*p1);
  1070.     dot = delta * normal;
  1071.     if ( dot > CONTINUOUS_EPSILON ) {
  1072.         return NULL;            // not a convex polygon
  1073.     }
  1074.  
  1075.     keep1 = (bool)(dot < -CONTINUOUS_EPSILON);
  1076.     
  1077.     back = &f1->p[(i+2)%f1->numPoints].ToVec3();
  1078.     delta = (*back) - (*p2);
  1079.     normal = planenormal.Cross( delta );
  1080.     normal.Normalize();
  1081.  
  1082.     back = &f2->p[(j+f2->numPoints-1)%f2->numPoints].ToVec3();
  1083.     delta = (*back) - (*p2);
  1084.     dot = delta * normal;
  1085.     if ( dot > CONTINUOUS_EPSILON ) {
  1086.         return NULL;            // not a convex polygon
  1087.     }
  1088.  
  1089.     keep2 = (bool)(dot < -CONTINUOUS_EPSILON);
  1090.  
  1091.     //
  1092.     // build the new polygon
  1093.     //
  1094.  
  1095. // RAVEN BEGIN
  1096. // mwhitlock: Dynamic memory consolidation
  1097.     RV_PUSH_HEAP_MEM_AUTO(p0,this);
  1098. // RAVEN END
  1099.  
  1100.     newf = new idWinding( f1->numPoints + f2->numPoints );
  1101.     
  1102.     // copy first polygon
  1103.     for ( k = (i+1) % f1->numPoints; k != i; k = (k+1) % f1->numPoints ) {
  1104.         if ( !keep && k == (i+1) % f1->numPoints && !keep2 ) {
  1105.             continue;
  1106.         }
  1107.         
  1108.         newf->p[newf->numPoints] = f1->p[k];
  1109.         newf->numPoints++;
  1110.     }
  1111.     
  1112.     // copy second polygon
  1113.     for ( l = (j+1) % f2->numPoints; l != j; l = (l+1) % f2->numPoints ) {
  1114.         if ( !keep && l == (j+1) % f2->numPoints && !keep1 ) {
  1115.             continue;
  1116.         }
  1117.         newf->p[newf->numPoints] = f2->p[l];
  1118.         newf->numPoints++;
  1119.     }
  1120.  
  1121.     return newf;
  1122. }
  1123.  
  1124. /*
  1125. =============
  1126. idWinding::RemovePoint
  1127. =============
  1128. */
  1129. void idWinding::RemovePoint( int point ) {
  1130.     if ( point < 0 || point >= numPoints ) {
  1131.         idLib::common->FatalError( "idWinding::removePoint: point out of range" );
  1132.     }
  1133.     if ( point < numPoints - 1) {
  1134.         memmove(&p[point], &p[point+1], (numPoints - point - 1) * sizeof(p[0]) );
  1135.     }
  1136.     numPoints--;
  1137. }
  1138.  
  1139. /*
  1140. =============
  1141. idWinding::InsertPoint
  1142. =============
  1143. */
  1144. void idWinding::InsertPoint( const idVec3 &point, int spot ) {
  1145.     int i;
  1146.  
  1147.     if ( spot > numPoints ) {
  1148.         idLib::common->FatalError( "idWinding::insertPoint: spot > numPoints" );
  1149.     }
  1150.  
  1151.     if ( spot < 0 ) {
  1152.         idLib::common->FatalError( "idWinding::insertPoint: spot < 0" );
  1153.     }
  1154.  
  1155.     EnsureAlloced( numPoints+1, true );
  1156.     for ( i = numPoints; i > spot; i-- ) {
  1157.         p[i] = p[i-1];
  1158.     }
  1159.     p[spot] = point;
  1160.     numPoints++;
  1161. }
  1162.  
  1163. /*
  1164. =============
  1165. idWinding::InsertPointIfOnEdge
  1166. =============
  1167. */
  1168. bool idWinding::InsertPointIfOnEdge( const idVec3 &point, const idPlane &plane, const float epsilon ) {
  1169.     int i;
  1170.     float dist, dot;
  1171.     idVec3 normal;
  1172.  
  1173.     // point may not be too far from the winding plane
  1174.     if ( idMath::Fabs( plane.Distance( point ) ) > epsilon ) {
  1175.         return false;
  1176.     }
  1177.  
  1178.     for ( i = 0; i < numPoints; i++ ) {
  1179.  
  1180.         // create plane through edge orthogonal to winding plane
  1181.         normal = (p[(i+1)%numPoints].ToVec3() - p[i].ToVec3()).Cross( plane.Normal() );
  1182.         normal.Normalize();
  1183.         dist = normal * p[i].ToVec3();
  1184.  
  1185.         if ( idMath::Fabs( normal * point - dist ) > epsilon ) {
  1186.             continue;
  1187.         }
  1188.  
  1189.         normal = plane.Normal().Cross( normal );
  1190.         dot = normal * point;
  1191.  
  1192.         dist = dot - normal * p[i].ToVec3();
  1193.  
  1194.         if ( dist < epsilon ) {
  1195.             // if the winding already has the point
  1196.             if ( dist > -epsilon ) {
  1197.                 return false;
  1198.             }
  1199.             continue;
  1200.         }
  1201.  
  1202.         dist = dot - normal * p[(i+1)%numPoints].ToVec3();
  1203.  
  1204.         if ( dist > -epsilon ) {
  1205.             // if the winding already has the point
  1206.             if ( dist < epsilon ) {
  1207.                 return false;
  1208.             }
  1209.             continue;
  1210.         }
  1211.  
  1212.         InsertPoint( point, i+1 );
  1213.         return true;
  1214.     }
  1215.     return false;
  1216. }
  1217.  
  1218. /*
  1219. =============
  1220. idWinding::IsTiny
  1221. =============
  1222. */
  1223. #define    EDGE_LENGTH        0.2f
  1224.  
  1225. bool idWinding::IsTiny( void ) const {
  1226.     int        i;
  1227.     float    len;
  1228.     idVec3    delta;
  1229.     int        edges;
  1230.  
  1231.     edges = 0;
  1232.     for ( i = 0; i < numPoints; i++ ) {
  1233.         delta = p[(i+1)%numPoints].ToVec3() - p[i].ToVec3();
  1234.         len = delta.Length();
  1235.         if ( len > EDGE_LENGTH ) {
  1236.             if ( ++edges == 3 ) {
  1237.                 return false;
  1238.             }
  1239.         }
  1240.     }
  1241.     return true;
  1242. }
  1243.  
  1244. /*
  1245. =============
  1246. idWinding::IsHuge
  1247. =============
  1248. */
  1249. bool idWinding::IsHuge( void ) const {
  1250.     int i, j;
  1251.  
  1252.     for ( i = 0; i < numPoints; i++ ) {
  1253.         for ( j = 0; j < 3; j++ ) {
  1254.             if ( p[i][j] <= MIN_WORLD_COORD || p[i][j] >= MAX_WORLD_COORD ) {
  1255.                 return true;
  1256.             }
  1257.         }
  1258.     }
  1259.     return false;
  1260. }
  1261.  
  1262. /*
  1263. =============
  1264. idWinding::Print
  1265. =============
  1266. */
  1267. void idWinding::Print( void ) const {
  1268.     int i;
  1269.  
  1270.     for ( i = 0; i < numPoints; i++ ) {
  1271.         idLib::common->Printf( "(%5.1f, %5.1f, %5.1f)\n", p[i][0], p[i][1], p[i][2] );
  1272.     }
  1273. }
  1274.  
  1275. /*
  1276. =============
  1277. idWinding::PlaneDistance
  1278. =============
  1279. */
  1280. float idWinding::PlaneDistance( const idPlane &plane ) const {
  1281.     int        i;
  1282.     float    d, min, max;
  1283.  
  1284.     min = idMath::INFINITY;
  1285.     max = -min;
  1286.     for ( i = 0; i < numPoints; i++ ) {
  1287.         d = plane.Distance( p[i].ToVec3() );
  1288.         if ( d < min ) {
  1289.             min = d;
  1290.             if ( FLOATSIGNBITSET( min ) & FLOATSIGNBITNOTSET( max ) ) {
  1291.                 return 0.0f;
  1292.             }
  1293.         }
  1294.         if ( d > max ) {
  1295.             max = d;
  1296.             if ( FLOATSIGNBITSET( min ) & FLOATSIGNBITNOTSET( max ) ) {
  1297.                 return 0.0f;
  1298.             }
  1299.         }
  1300.     }
  1301.     if ( FLOATSIGNBITNOTSET( min ) ) {
  1302.         return min;
  1303.     }
  1304.     if ( FLOATSIGNBITSET( max ) ) {
  1305.         return max;
  1306.     }
  1307.     return 0.0f;
  1308. }
  1309.  
  1310. /*
  1311. =============
  1312. idWinding::PlaneSide
  1313. =============
  1314. */
  1315. int idWinding::PlaneSide( const idPlane &plane, const float epsilon ) const {
  1316.     bool    front, back;
  1317.     int        i;
  1318.     float    d;
  1319.  
  1320.     front = false;
  1321.     back = false;
  1322.     for ( i = 0; i < numPoints; i++ ) {
  1323.         d = plane.Distance( p[i].ToVec3() );
  1324.         if ( d < -epsilon ) {
  1325.             if ( front ) {
  1326.                 return SIDE_CROSS;
  1327.             }
  1328.             back = true;
  1329.             continue;
  1330.         }
  1331.         else if ( d > epsilon ) {
  1332.             if ( back ) {
  1333.                 return SIDE_CROSS;
  1334.             }
  1335.             front = true;
  1336.             continue;
  1337.         }
  1338.     }
  1339.  
  1340.     if ( back ) {
  1341.         return SIDE_BACK;
  1342.     }
  1343.     if ( front ) {
  1344.         return SIDE_FRONT;
  1345.     }
  1346.     return SIDE_ON;
  1347. }
  1348.  
  1349. /*
  1350. =============
  1351. idWinding::PlanesConcave
  1352. =============
  1353. */
  1354. #define WCONVEX_EPSILON        0.2f
  1355.  
  1356. bool idWinding::PlanesConcave( const idWinding &w2, const idVec3 &normal1, const idVec3 &normal2, float dist1, float dist2 ) const {
  1357.     int i;
  1358.  
  1359.     // check if one of the points of winding 1 is at the back of the plane of winding 2
  1360.     for ( i = 0; i < numPoints; i++ ) {
  1361.         if ( normal2 * p[i].ToVec3() - dist2 > WCONVEX_EPSILON ) {
  1362.             return true;
  1363.         }
  1364.     }
  1365.     // check if one of the points of winding 2 is at the back of the plane of winding 1
  1366.     for ( i = 0; i < w2.numPoints; i++ ) {
  1367.         if ( normal1 * w2.p[i].ToVec3() - dist1 > WCONVEX_EPSILON ) {
  1368.             return true;
  1369.         }
  1370.     }
  1371.  
  1372.     return false;
  1373. }
  1374.  
  1375. /*
  1376. =============
  1377. idWinding::PointInside
  1378. =============
  1379. */
  1380. bool idWinding::PointInside( const idVec3 &normal, const idVec3 &point, const float epsilon ) const {
  1381.     int i;
  1382.     idVec3 dir, n, pointvec;
  1383.  
  1384.     for ( i = 0; i < numPoints; i++ ) {
  1385.         dir = p[(i+1) % numPoints].ToVec3() - p[i].ToVec3();
  1386.         pointvec = point - p[i].ToVec3();
  1387.  
  1388.         n = dir.Cross( normal );
  1389.  
  1390.         if ( pointvec * n < -epsilon ) {
  1391.             return false;
  1392.         }
  1393.     }
  1394.     return true;
  1395. }
  1396.  
  1397. /*
  1398. =============
  1399. idWinding::LineIntersection
  1400. =============
  1401. */
  1402. bool idWinding::LineIntersection( const idPlane &windingPlane, const idVec3 &start, const idVec3 &end, bool backFaceCull ) const {
  1403.     float front, back, frac;
  1404.     idVec3 mid;
  1405.  
  1406.     front = windingPlane.Distance( start );
  1407.     back = windingPlane.Distance( end );
  1408.  
  1409.     // if both points at the same side of the plane
  1410.     if ( front < 0.0f && back < 0.0f ) {
  1411.         return false;
  1412.     }
  1413.  
  1414.     if ( front > 0.0f && back > 0.0f ) {
  1415.         return false;
  1416.     }
  1417.  
  1418.     // if back face culled
  1419.     if ( backFaceCull && front < 0.0f ) {
  1420.         return false;
  1421.     }
  1422.  
  1423.     // get point of intersection with winding plane
  1424.     if ( idMath::Fabs(front - back) < 0.0001f ) {
  1425.         mid = end;
  1426.     }
  1427.     else {
  1428.         frac = front / (front - back);
  1429.         mid[0] = start[0] + (end[0] - start[0]) * frac;
  1430.         mid[1] = start[1] + (end[1] - start[1]) * frac;
  1431.         mid[2] = start[2] + (end[2] - start[2]) * frac;
  1432.     }
  1433.  
  1434.     return PointInside( windingPlane.Normal(), mid, 0.0f );
  1435. }
  1436.  
  1437. /*
  1438. =============
  1439. idWinding::RayIntersection
  1440. =============
  1441. */
  1442. bool idWinding::RayIntersection( const idPlane &windingPlane, const idVec3 &start, const idVec3 &dir, float &scale, bool backFaceCull ) const {
  1443.     int i;
  1444.     bool side, lastside = false;
  1445.     idPluecker pl1, pl2;
  1446.  
  1447.     scale = 0.0f;
  1448.     pl1.FromRay( start, dir );
  1449.     for ( i = 0; i < numPoints; i++ ) {
  1450.         pl2.FromLine( p[i].ToVec3(), p[(i+1)%numPoints].ToVec3() );
  1451.         side = pl1.PermutedInnerProduct( pl2 ) > 0.0f;
  1452.         if ( i && side != lastside ) {
  1453.             return false;
  1454.         }
  1455.         lastside = side;
  1456.     }
  1457.     if ( !backFaceCull || lastside ) {
  1458.         windingPlane.RayIntersection( start, dir, scale );
  1459.         return true;
  1460.     }
  1461.     return false;
  1462. }
  1463.  
  1464. /*
  1465. =================
  1466. idWinding::TriangleArea
  1467. =================
  1468. */
  1469. float idWinding::TriangleArea( const idVec3 &a, const idVec3 &b, const idVec3 &c ) {
  1470.     idVec3    v1, v2;
  1471.     idVec3    cross;
  1472.  
  1473.     v1 = b - a;
  1474.     v2 = c - a;
  1475.     cross = v1.Cross( v2 );
  1476.     return 0.5f * cross.Length();
  1477. }
  1478.  
  1479.  
  1480. //===============================================================
  1481. //
  1482. //    idFixedWinding
  1483. //
  1484. //===============================================================
  1485.  
  1486. /*
  1487. =============
  1488. idFixedWinding::ReAllocate
  1489. =============
  1490. */
  1491. bool idFixedWinding::ReAllocate( int n, bool keep ) {
  1492.  
  1493.     assert( n <= MAX_POINTS_ON_WINDING );
  1494.  
  1495.     if ( n > MAX_POINTS_ON_WINDING ) {
  1496.         idLib::common->Printf("WARNING: idFixedWinding -> MAX_POINTS_ON_WINDING overflowed\n");
  1497.         return false;
  1498.     }
  1499.     return true;
  1500. }
  1501.  
  1502. /*
  1503. =============
  1504. idFixedWinding::Split
  1505. =============
  1506. */
  1507. int idFixedWinding::Split( idFixedWinding *back, const idPlane &plane, const float epsilon ) {
  1508.     int        counts[3];
  1509.     float    dists[MAX_POINTS_ON_WINDING+4];
  1510.     byte    sides[MAX_POINTS_ON_WINDING+4];
  1511.     float    dot;
  1512.     int        i, j;
  1513.     idVec5 *p1, *p2;
  1514.     idVec5    mid;
  1515.     idFixedWinding out;
  1516.  
  1517.     counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
  1518.  
  1519.     // determine sides for each point
  1520.     for ( i = 0; i < numPoints; i++ ) {
  1521.         dists[i] = dot = plane.Distance( p[i].ToVec3() );
  1522.         if ( dot > epsilon ) {
  1523.             sides[i] = SIDE_FRONT;
  1524.         } else if ( dot < -epsilon ) {
  1525.             sides[i] = SIDE_BACK;
  1526.         } else {
  1527.             sides[i] = SIDE_ON;
  1528.         }
  1529.         counts[sides[i]]++;
  1530.     }
  1531.  
  1532.     if ( !counts[SIDE_BACK] ) {
  1533.         if ( !counts[SIDE_FRONT] ) {
  1534.             return SIDE_ON;
  1535.         }
  1536.         else {
  1537.             return SIDE_FRONT;
  1538.         }
  1539.     }
  1540.     
  1541.     if ( !counts[SIDE_FRONT] ) {
  1542.         return SIDE_BACK;
  1543.     }
  1544.  
  1545.     sides[i] = sides[0];
  1546.     dists[i] = dists[0];
  1547.     
  1548.     out.numPoints = 0;
  1549.     back->numPoints = 0;
  1550.  
  1551.     for ( i = 0; i < numPoints; i++ ) {
  1552.         p1 = &p[i];
  1553.  
  1554.         if ( !out.EnsureAlloced( out.numPoints+1, true ) ) {
  1555.             return SIDE_FRONT;        // can't split -- fall back to original
  1556.         }
  1557.         if ( !back->EnsureAlloced( back->numPoints+1, true ) ) {
  1558.             return SIDE_FRONT;        // can't split -- fall back to original
  1559.         }
  1560.  
  1561.         if ( sides[i] == SIDE_ON ) {
  1562.             out.p[out.numPoints] = *p1;
  1563.             out.numPoints++;
  1564.             back->p[back->numPoints] = *p1;
  1565.             back->numPoints++;
  1566.             continue;
  1567.         }
  1568.     
  1569.         if ( sides[i] == SIDE_FRONT ) {
  1570.             out.p[out.numPoints] = *p1;
  1571.             out.numPoints++;
  1572.         }
  1573.         if ( sides[i] == SIDE_BACK ) {
  1574.             back->p[back->numPoints] = *p1;
  1575.             back->numPoints++;
  1576.         }
  1577.         
  1578.         if ( sides[i+1] == SIDE_ON || sides[i+1] == sides[i] ) {
  1579.             continue;
  1580.         }
  1581.             
  1582.         if ( !out.EnsureAlloced( out.numPoints+1, true ) ) {
  1583.             return SIDE_FRONT;        // can't split -- fall back to original
  1584.         }
  1585.  
  1586.         if ( !back->EnsureAlloced( back->numPoints+1, true ) ) {
  1587.             return SIDE_FRONT;        // can't split -- fall back to original
  1588.         }
  1589.  
  1590.         // generate a split point
  1591.         j = i + 1;
  1592.         if ( j >= numPoints ) {
  1593.             p2 = &p[0];
  1594.         }
  1595.         else {
  1596.             p2 = &p[j];
  1597.         }
  1598.  
  1599.         dot = dists[i] / (dists[i] - dists[i+1]);
  1600.         for ( j = 0; j < 3; j++ ) {
  1601.             // avoid round off error when possible
  1602.             if ( plane.Normal()[j] == 1.0f ) {
  1603.                 mid[j] = plane.Dist();
  1604.             } else if ( plane.Normal()[j] == -1.0f ) {
  1605.                 mid[j] = -plane.Dist();
  1606.             } else {
  1607.                 mid[j] = (*p1)[j] + dot * ( (*p2)[j] - (*p1)[j] );
  1608.             }
  1609.         }
  1610.         mid.s = p1->s + dot * ( p2->s - p1->s );
  1611.         mid.t = p1->t + dot * ( p2->t - p1->t );
  1612.             
  1613.         out.p[out.numPoints] = mid;
  1614.         out.numPoints++;
  1615.         back->p[back->numPoints] = mid;
  1616.         back->numPoints++;
  1617.     }
  1618.     for ( i = 0; i < out.numPoints; i++ ) {
  1619.         p[i] = out.p[i];
  1620.     }
  1621.     numPoints = out.numPoints;
  1622.  
  1623.     return SIDE_CROSS;
  1624. }
  1625.