data/qcsrc/client/winding.qc

   1 entity entdup(entity e)
   2 {
   3         entity e2;
   4         e2 = spawn();
   5         copyentity(e, e2);
   6         return e2;
   7 }
   8
   9 entity AllocWinding(entity base)
  10 {
  11         entity e;
  12         e = spawn();
  13         e.classname = "winding";
  14         e.sort_next = e;
  15         e.sort_prev = e;
  16         e.owner = e;
  17         if(base)
  18                 e.winding_point_interpolate = base.winding_point_interpolate;
  19         return e;
  20 }
  21
  22 void InsertIntoWinding(entity w, entity e)
  23 {
  24         e.sort_next = w;
  25         e.sort_prev = w.sort_prev;
  26         e.sort_prev.sort_next = e;
  27         e.sort_next.sort_prev = e;
  28         e.owner = w.owner;
  29 }
  30
  31 void DeleteFromWinding(entity p)
  32 {
  33         p.sort_next.sort_prev = p.sort_prev;
  34         p.sort_prev.sort_next = p.sort_next;
  35         remove(p);
  36 }
  37
  38 entity AllocPoint(entity w, vector o)
  39 {
  40         entity e;
  41         e = spawn();
  42         e.classname = "winding_point";
  43         e.origin = o;
  44         e.owner = w;
  45         return e;
  46 }
  47
  48 void ClearWinding(entity w)
  49 {
  50         entity e;
  51         for(e = w.sort_next; e != w; )
  52         {
  53                 e = e.sort_next;
  54                 remove(e.sort_prev);
  55         }
  56         // now only w is left
  57         w.sort_next = w.sort_prev = w;
  58 }
  59
  60 void FreeWinding(entity w)
  61 {
  62         ClearWinding(w);
  63         remove(w);
  64 }
  65
  66 entity CopyWinding(entity w)
  67 {
  68         entity e, en, wn, pn;
  69         wn = entdup(w);
  70         pn = wn;
  71         for(e = w.sort_next; e != w; e = e.sort_next)
  72         {
  73                 en = entdup(e);
  74                 en.owner = wn;
  75                 en.sort_prev = pn;
  76                 pn = en;
  77         }
  78         wn.sort_prev = pn;
  79         wn.sort_prev.sort_next = wn;
  80         for(en = wn.sort_prev; en != wn; en = en.sort_prev)
  81                 en.sort_prev.sort_next = en;
  82         return wn;
  83 }
  84
  85 void ClipWindingEpsilon(entity w, vector norm, float dist, float epsilon, float want_sides)
  86 {
  87         // algorithm from q3map2
  88         float counts_f, counts_b;
  89         entity p, p2, pnew;
  90         float i;
  91         float dot, d, d2;
  92         vector mid;
  93
  94         for(i = 0, p = w.sort_next; p != w; ++i, p = p.sort_next)
  95         {
  96                 dot = p.origin * norm - dist;
  97                 if(dot > epsilon)
  98                         ++counts_f;
  99                 else if(dot < -epsilon)
 100                         ++counts_b;
 101         }
 102
 103         if not(counts_f)
 104         {
 105                 if(want_sides >= 0)
 106                         clipwinding_front = AllocWinding(w);
 107                 if(want_sides <= 0)
 108                         clipwinding_back = CopyWinding(w);
 109                 return;
 110         }
 111         if not(counts_b)
 112         {
 113                 if(want_sides >= 0)
 114                         clipwinding_front = CopyWinding(w);
 115                 if(want_sides <= 0)
 116                         clipwinding_back = AllocWinding(w);
 117                 return;
 118         }
 119
 120         clipwinding_front = AllocWinding(w);
 121         clipwinding_back = AllocWinding(w);
 122
 123         for(i = 0, p = w.sort_next; p != w; ++i, p = p.sort_next)
 124         {
 125                 p2 = p.sort_next;
 126                 if(p2 == w)
 127                         p2 = p2.sort_next;
 128                 d = p.origin * norm - dist;
 129                 d2 = p2.origin * norm - dist;
 130                 if(d > epsilon) // front
 131                 {
 132                         if(want_sides >= 0)
 133                                 InsertIntoWinding(clipwinding_front, entdup(p));
 134                         if not(d2 < -epsilon) // only if switching side
 135                                 continue;
 136                 }
 137                 else if(d < -epsilon) // back
 138                 {
 139                         if(want_sides <= 0)
 140                                 InsertIntoWinding(clipwinding_back, entdup(p));
 141                         if not(d2 > epsilon) // only if switching side
 142                                 continue;
 143                 }
 144                 else // on
 145                 {
 146                         // point is for both windings
 147                         if(want_sides >= 0)
 148                                 InsertIntoWinding(clipwinding_front, entdup(p));
 149                         if(want_sides <= 0)
 150                                 InsertIntoWinding(clipwinding_back, entdup(p));
 151                         continue;
 152                 }
 153                 // must... make... split... point
 154                 dot = d / (d - d2);
 155                 mid = (1 - dot) * p.origin + dot * p2.origin;
 156                 pnew = AllocPoint(w, mid);
 157                 pnew.winding_cutpoint = 1;
 158                 if(w.winding_point_interpolate)
 159                         w.winding_point_interpolate(w, pnew, p, p2, dot);
 160
 161                 if(want_sides >= 0)
 162                         InsertIntoWinding(clipwinding_front, pnew);
 163                 if(want_sides <= 0)
 164                 {
 165                         if(want_sides >= 0)
 166                                 pnew = entdup(pnew);
 167                         InsertIntoWinding(clipwinding_back, pnew);
 168                 }
 169         }
 170 }