← Back to branch summary

~ubuntu-branches/ubuntu/hardy/sauerbraten/hardy-backports

« back to all changes in this revision

Viewing changes to engine/spheretree.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Bruno "Fuddl" Kleinert, Bruno "Fuddl" Kleinert, Cyril Brulebois
  • Date: 2007-08-26 17:45:25 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20070826174525-uiv5yjjk092m95cl
Tags: 0.0.20070819.dfsg-1
http://bugs.debian.org/426691
[ Bruno "Fuddl" Kleinert ]
* Update the Debian menu file to the latest menu structure
* Remove 10_save_and_load_maps_from_home_directory.dpatch (Upstream solved
  this in this release) (Closes: #426691)
* Remove 10_search_home_for_config.dpatch (Upstream solved this in this
  release)
* Add 10_fix_clean_target.dpatch to avoid calling autotools in clean target
* Add NEWS.Debian

[ Cyril Brulebois ]
* Added XS-Vcs-Svn and XS-Vcs-Browser fields in the control file.

Show diffs side-by-side

added added

removed removed

Lines of Context:
engine/spheretree.cpp
1
 
#include "pch.h"
2
 
#include "engine.h"
3
 
 
4
 
struct SphereBranch : SphereTree
5
 
{
6
 
    SphereTree *child1, *child2;
7
 
 
8
 
    SphereBranch(SphereTree *c1, SphereTree *c2) : child1(c1), child2(c2)
9
 
    {
10
 
        vec n(child2->center);
11
 
        n.sub(child1->center);
12
 
        float dist = n.magnitude();
13
 
 
14
 
        radius = (child1->radius + child2->radius + dist) / 2;
15
 
 
16
 
        center = child1->center;
17
 
        if(dist)
18
 
        {
19
 
            n.mul((radius - child1->radius) / dist);
20
 
            center.add(n);
21
 
        }
22
 
    }
23
 
 
24
 
    ~SphereBranch()
25
 
    {
26
 
        DELETEP(child1);
27
 
        DELETEP(child2);
28
 
    }
29
 
 
30
 
    bool childintersect(const vec &o, const vec &ray, float maxdist, float &dist, int mode) const
31
 
    {
32
 
        return child1->intersect(o, ray, maxdist, dist, mode) ||
33
 
               child2->intersect(o, ray, maxdist, dist, mode);
34
 
    }
35
 
};  
36
 
 
37
 
struct SphereLeaf : SphereTree
38
 
{
39
 
    tri tri;
40
 
 
41
 
    SphereLeaf(const SphereTree::tri &t) : tri(t)
42
 
    {
43
 
        center = t.a;
44
 
        center.add(t.b);
45
 
        center.add(t.c);
46
 
        center.div(3);
47
 
        float r1 = center.dist(t.a), 
48
 
              r2 = center.dist(t.b), 
49
 
              r3 = center.dist(t.c);
50
 
        radius = max(r1, max(r2, r3));
51
 
    }
52
 
    
53
 
    bool childintersect(const vec &o, const vec &ray, float maxdist, float &dist, int mode) const
54
 
    {
55
 
        vec edge1(tri.b), edge2(tri.c);
56
 
        edge1.sub(tri.a); 
57
 
        edge2.sub(tri.a);
58
 
        vec p;
59
 
        p.cross(ray, edge2);
60
 
        float det = edge1.dot(p);
61
 
        if(det == 0) return false;
62
 
        vec r(o); 
63
 
        r.sub(tri.a);
64
 
        float u = r.dot(p) / det;
65
 
        if(u < 0 || u > 1) return false;
66
 
        vec q; 
67
 
        q.cross(r, edge1);
68
 
        float v = ray.dot(q) / det;
69
 
        if(v < 0 || u + v > 1) return false;
70
 
        float f = edge2.dot(q) / det;
71
 
        if(f < 0 || f > maxdist) return false;
72
 
        if(tri.tex && (mode&RAY_ALPHAPOLY)==RAY_ALPHAPOLY)
73
 
        {
74
 
            if(!tri.tex->alphamask)
75
 
            {
76
 
                loadalphamask(tri.tex);
77
 
                if(!tri.tex->alphamask) { dist = f; return true; }
78
 
            }
79
 
            float s = tri.tc[0] + u*(tri.tc[2] - tri.tc[0]) + v*(tri.tc[4] - tri.tc[0]),
80
 
                  t = tri.tc[1] + u*(tri.tc[3] - tri.tc[1]) + v*(tri.tc[5] - tri.tc[1]);
81
 
            int si = int(s*tri.tex->w), ti = int(t*tri.tex->h);
82
 
            if(!(tri.tex->alphamask[ti*((tri.tex->w+7)/8) + si/8] & (1<<(si%8)))) return false;
83
 
        }
84
 
        dist = f;
85
 
        return true;
86
 
    }
87
 
 
88
 
    bool isleaf() { return true; }
89
 
};
90
 
 
91
 
SphereTree *buildspheretree(int numtris, const SphereTree::tri *tris)
92
 
{
93
 
    if(numtris<=0) return NULL;
94
 
 
95
 
    SphereTree **spheres = new SphereTree *[numtris];
96
 
    loopi(numtris) spheres[i] = new SphereLeaf(tris[i]);
97
 
 
98
 
    vec center = vec(0, 0, 0);
99
 
    loopi(numtris) center.add(spheres[i]->center);
100
 
    center.div(numtris);
101
 
 
102
 
    int numspheres = numtris;
103
 
    while(numspheres>1)
104
 
    {
105
 
        int farthest = -1;
106
 
        float dist = -1e16f;
107
 
        loopi(numspheres)
108
 
        {
109
 
            float d = center.dist(spheres[i]->center) - spheres[i]->radius;
110
 
            if(d>dist)
111
 
            {
112
 
                farthest = i;
113
 
                dist = d;
114
 
            }
115
 
        } 
116
 
        SphereTree *child1 = spheres[farthest];
117
 
        int closest = -1;
118
 
        float radius = 1e16f;
119
 
        loopi(numspheres)
120
 
        {
121
 
            if(i==farthest) continue;
122
 
            SphereTree *child2 = spheres[i];
123
 
            float xyradius = (child1->radius + child2->radius + child1->center.dist(child2->center)) / 2;
124
 
            if(!xyradius && child1->isleaf() && child2->isleaf() && ((SphereLeaf *)child1)->tri == ((SphereLeaf *)child2)->tri)
125
 
            {
126
 
                spheres[i] = spheres[--numspheres];
127
 
                if(farthest==numspheres) farthest = i;
128
 
                else i--;
129
 
                continue;
130
 
            }    
131
 
            else if(xyradius < radius)
132
 
            {
133
 
                closest = i;
134
 
                radius = xyradius;
135
 
            }
136
 
        }
137
 
        if(closest>=0)
138
 
        {
139
 
            spheres[farthest] = new SphereBranch(spheres[farthest], spheres[closest]);
140
 
            spheres[closest] = spheres[--numspheres];
141
 
        }
142
 
    }
143
 
    
144
 
    SphereTree *root = spheres[0];
145
 
    delete[] spheres;
146
 
    return root;
147
 
}
148
 
 
149
 
static inline void yawray(vec &o, vec &ray, float angle)
150
 
{
151
 
    angle *= RAD;
152
 
    float c = cosf(angle), s = sinf(angle),
153
 
          ox = o.x, oy = o.y,
154
 
          rx = ox+ray.x, ry = oy+ray.y;
155
 
    o.x = ox*c - oy*s;
156
 
    o.y = oy*c + ox*s;
157
 
    ray.x = rx*c - ry*s - o.x;
158
 
    ray.y = ry*c + rx*s - o.y;
159
 
    ray.normalize();
160
 
}
161
 
 
162
 
bool mmintersect(const extentity &e, const vec &o, const vec &ray, float maxdist, int mode, float &dist)
163
 
{
164
 
    model *m = loadmodel(NULL, e.attr2);
165
 
    if(!m) return false;
166
 
    if(mode&RAY_SHADOW)
167
 
    {
168
 
        if(!m->shadow || checktriggertype(e.attr3, TRIG_COLLIDE|TRIG_DISAPPEAR)) return false;
169
 
    }
170
 
    else if((mode&RAY_ENTS)!=RAY_ENTS && !m->collide) return false;
171
 
    if(!m->spheretree && !m->setspheretree()) return false;
172
 
    if(!maxdist) maxdist = 1e16f;
173
 
    vec yo(o);
174
 
    yo.sub(e.o);
175
 
    if(!m->spheretree->shellintersect(yo, ray, maxdist)) return false;
176
 
    float yaw = -180.0f-(float)((e.attr1+7)-(e.attr1+7)%15);
177
 
    vec yray(ray);
178
 
    if(yaw != 0) yawray(yo, yray, yaw);
179
 
    return m->spheretree->childintersect(yo, yray, maxdist, dist, mode);
180
 
}
181