root/OpenSceneGraph/trunk/src/osg/LineSegment.cpp @ 13041

Revision 13041, 10.2 kB (checked in by robert, 3 years ago)

Ran script to remove trailing spaces and tabs

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
Line 
1/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield
2 *
3 * This library is open source and may be redistributed and/or modified under
4 * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or
5 * (at your option) any later version.  The full license is in LICENSE file
6 * included with this distribution, and on the openscenegraph.org website.
7 *
8 * This library is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11 * OpenSceneGraph Public License for more details.
12*/
13#include <osg/LineSegment>
14
15using namespace osg;
16
17LineSegment::~LineSegment()
18{
19}
20
21bool LineSegment::intersectAndClip(vec_type& s,vec_type& e,const BoundingBox& bb)
22{
23    // compate s and e against the xMin to xMax range of bb.
24    if (s.x()<=e.x())
25    {
26
27        // trivial reject of segment wholely outside.
28        if (e.x()<bb.xMin()) return false;
29        if (s.x()>bb.xMax()) return false;
30
31        if (s.x()<bb.xMin())
32        {
33            // clip s to xMin.
34            s = s+(e-s)*(bb.xMin()-s.x())/(e.x()-s.x());
35        }
36
37        if (e.x()>bb.xMax())
38        {
39            // clip e to xMax.
40            e = s+(e-s)*(bb.xMax()-s.x())/(e.x()-s.x());
41        }
42    }
43    else
44    {
45        if (s.x()<bb.xMin()) return false;
46        if (e.x()>bb.xMax()) return false;
47
48        if (e.x()<bb.xMin())
49        {
50            // clip s to xMin.
51            e = s+(e-s)*(bb.xMin()-s.x())/(e.x()-s.x());
52        }
53
54        if (s.x()>bb.xMax())
55        {
56            // clip e to xMax.
57            s = s+(e-s)*(bb.xMax()-s.x())/(e.x()-s.x());
58        }
59    }
60
61    // compate s and e against the yMin to yMax range of bb.
62    if (s.y()<=e.y())
63    {
64
65        // trivial reject of segment wholely outside.
66        if (e.y()<bb.yMin()) return false;
67        if (s.y()>bb.yMax()) return false;
68
69        if (s.y()<bb.yMin())
70        {
71            // clip s to yMin.
72            s = s+(e-s)*(bb.yMin()-s.y())/(e.y()-s.y());
73        }
74
75        if (e.y()>bb.yMax())
76        {
77            // clip e to yMax.
78            e = s+(e-s)*(bb.yMax()-s.y())/(e.y()-s.y());
79        }
80    }
81    else
82    {
83        if (s.y()<bb.yMin()) return false;
84        if (e.y()>bb.yMax()) return false;
85
86        if (e.y()<bb.yMin())
87        {
88            // clip s to yMin.
89            e = s+(e-s)*(bb.yMin()-s.y())/(e.y()-s.y());
90        }
91
92        if (s.y()>bb.yMax())
93        {
94            // clip e to yMax.
95            s = s+(e-s)*(bb.yMax()-s.y())/(e.y()-s.y());
96        }
97    }
98
99    // compate s and e against the zMin to zMax range of bb.
100    if (s.z()<=e.z())
101    {
102
103        // trivial reject of segment wholely outside.
104        if (e.z()<bb.zMin()) return false;
105        if (s.z()>bb.zMax()) return false;
106
107        if (s.z()<bb.zMin())
108        {
109            // clip s to zMin.
110            s = s+(e-s)*(bb.zMin()-s.z())/(e.z()-s.z());
111        }
112
113        if (e.z()>bb.zMax())
114        {
115            // clip e to zMax.
116            e = s+(e-s)*(bb.zMax()-s.z())/(e.z()-s.z());
117        }
118    }
119    else
120    {
121        if (s.z()<bb.zMin()) return false;
122        if (e.z()>bb.zMax()) return false;
123
124        if (e.z()<bb.zMin())
125        {
126            // clip s to zMin.
127            e = s+(e-s)*(bb.zMin()-s.z())/(e.z()-s.z());
128        }
129
130        if (s.z()>bb.zMax())
131        {
132            // clip e to zMax.
133            s = s+(e-s)*(bb.zMax()-s.z())/(e.z()-s.z());
134        }
135    }
136
137    return true;
138}
139
140
141bool LineSegment::intersect(const BoundingBox& bb) const
142{
143    if (!bb.valid()) return false;
144
145    vec_type s=_s,e=_e;
146    return intersectAndClip(s,e,bb);
147}
148
149
150bool LineSegment::intersect(const BoundingBox& bb,float& r1,float& r2) const
151{
152    if (!bb.valid()) return false;
153
154    vec_type s=_s,e=_e;
155    bool result = intersectAndClip(s,e,bb);
156    if (result)
157    {
158        value_type len = (_e-_s).length();
159        if (len>0.0f)
160        {
161            value_type inv_len = 1.0f/len;
162            r1 = (float)((s-_s).length()*inv_len);
163            r2 = (float)((e-_e).length()*inv_len);
164        }
165        else
166        {
167            r1 = 0.0f;
168            r2 = 0.0f;
169        }
170    }
171    return result;
172}
173
174bool LineSegment::intersect(const BoundingBox& bb,double& r1,double& r2) const
175{
176    if (!bb.valid()) return false;
177
178    vec_type s=_s,e=_e;
179    bool result = intersectAndClip(s,e,bb);
180    if (result)
181    {
182        double len = (_e-_s).length();
183        if (len>0.0)
184        {
185            double inv_len = 1.0/len;
186            r1 = ((s-_s).length()*inv_len);
187            r2 = ((e-_e).length()*inv_len);
188        }
189        else
190        {
191            r1 = 0.0;
192            r2 = 0.0;
193        }
194    }
195    return result;
196}
197
198
199bool LineSegment::intersect(const BoundingSphere& bs,float& r1,float& r2) const
200{
201    vec_type sm = _s-bs._center;
202    value_type c = sm.length2()-bs._radius*bs._radius;
203
204    vec_type se = _e-_s;
205    value_type a = se.length2();
206
207
208    // check for zero length segment.
209    if (a==0.0)
210    {
211        // check if start point outside sphere radius
212        if (c>0.0) return false;
213
214        // length segment within radius of bounding sphere but zero length
215        // so return true, and set the ratio so the start point is the one
216        // to be used.
217        r1 = 1.0f;
218        r2 = 0.0f;
219        return true;
220    }
221
222    value_type b = sm*se*2.0f;
223
224    value_type d = b*b-4.0f*a*c;
225
226    if (d<0.0f) return false;
227
228    d = (value_type)sqrt(d);
229
230
231    value_type div = 1.0f/(2.0f*a);
232
233    r1 = (float)((-b-d)*div);
234    r2 = (float)((-b+d)*div);
235
236    if (r1<=0.0f && r2<=0.0f) return false;
237
238    if (r1>=1.0f && r2>=1.0f) return false;
239
240    return true;
241}
242
243
244
245bool LineSegment::intersect(const BoundingSphere& bs,double& r1,double& r2) const
246{
247    vec_type sm = _s-bs._center;
248    value_type c = sm.length2()-bs._radius*bs._radius;
249
250    vec_type se = _e-_s;
251    value_type a = se.length2();
252
253
254    // check for zero length segment.
255    if (a==0.0)
256    {
257        // check if start point outside sphere radius
258        if (c>0.0) return false;
259
260        // length segment within radius of bounding sphere but zero length
261        // so return true, and set the ratio so the start point is the one
262        // to be used.
263        r1 = 1.0f;
264        r2 = 0.0f;
265        return true;
266    }
267
268    value_type b = sm*se*2.0;
269
270    value_type d = b*b-4.0f*a*c;
271
272    if (d<0.0f) return false;
273
274    d = (value_type)sqrt(d);
275
276
277    value_type div = 1.0f/(2.0*a);
278
279    r1 = ((-b-d)*div);
280    r2 = ((-b+d)*div);
281
282    if (r1<=0.0 && r2<=0.0) return false;
283
284    if (r1>=1.0 && r2>=1.0) return false;
285
286    return true;
287}
288
289
290bool LineSegment::intersect(const BoundingSphere& bs) const
291{
292    vec_type sm = _s-bs._center;
293    value_type c = sm.length2()-bs._radius*bs._radius;
294    if (c<0.0f) return true;
295
296    vec_type se = _e-_s;
297    value_type a = se.length2();
298
299    value_type b = (sm*se)*2.0f;
300
301    value_type d = b*b-4.0f*a*c;
302
303    if (d<0.0f) return false;
304
305    d = (value_type) sqrt(d);
306
307    value_type div = 1.0f/(2.0f*a);
308
309    value_type r1 = (-b-d)*div;
310    value_type r2 = (-b+d)*div;
311
312    if (r1<=0.0f && r2<=0.0f) return false;
313
314    if (r1>=1.0f && r2>=1.0f) return false;
315
316    return true;
317}
318
319
320bool LineSegment::intersect(const Vec3f& v1,const Vec3f& v2,const Vec3f& v3,float& r)
321{
322    if (v1==v2 || v2==v3 || v1==v3) return false;
323
324    vec_type vse = _e-_s;
325
326    vec_type v12 = v2-v1;
327    vec_type n12 = v12^vse;
328    value_type ds12 = (_s-v1)*n12;
329    value_type d312 = (v3-v1)*n12;
330    if (d312>=0.0)
331    {
332        if (ds12<0.0) return false;
333        if (ds12>d312) return false;
334    }
335    else                         // d312 < 0
336    {
337        if (ds12>0.0) return false;
338        if (ds12<d312) return false;
339    }
340
341    vec_type v23 = v3-v2;
342    vec_type n23 = v23^vse;
343    value_type ds23 = (_s-v2)*n23;
344    value_type d123 = (v1-v2)*n23;
345    if (d123>=0.0)
346    {
347        if (ds23<0.0) return false;
348        if (ds23>d123) return false;
349    }
350    else                         // d123 < 0
351    {
352        if (ds23>0.0) return false;
353        if (ds23<d123) return false;
354    }
355
356    vec_type v31 = v1-v3;
357    vec_type n31 = v31^vse;
358    value_type ds31 = (_s-v3)*n31;
359    value_type d231 = (v2-v3)*n31;
360    if (d231>=0.0)
361    {
362        if (ds31<0.0) return false;
363        if (ds31>d231) return false;
364    }
365    else                         // d231 < 0
366    {
367        if (ds31>0.0) return false;
368        if (ds31<d231) return false;
369    }
370
371    value_type r3 = ds12/d312;
372    value_type r1 = ds23/d123;
373    value_type r2 = ds31/d231;
374
375    //    value_type rt = r1+r2+r3;
376
377    vec_type in = v1*r1+v2*r2+v3*r3;
378
379    value_type length = vse.length();
380    vse /= length;
381    value_type d = (in-_s)*vse;
382
383    if (d<0.0) return false;
384    if (d>length) return false;
385
386    r = (float) d/length;
387
388    return true;
389}
390
391bool LineSegment::intersect(const Vec3d& v1,const Vec3d& v2,const Vec3d& v3,double& r)
392{
393    if (v1==v2 || v2==v3 || v1==v3) return false;
394
395    vec_type vse = _e-_s;
396
397    vec_type v12 = v2-v1;
398    vec_type n12 = v12^vse;
399    value_type ds12 = (_s-v1)*n12;
400    value_type d312 = (v3-v1)*n12;
401    if (d312>=0.0)
402    {
403        if (ds12<0.0) return false;
404        if (ds12>d312) return false;
405    }
406    else                         // d312 < 0
407    {
408        if (ds12>0.0) return false;
409        if (ds12<d312) return false;
410    }
411
412    vec_type v23 = v3-v2;
413    vec_type n23 = v23^vse;
414    value_type ds23 = (_s-v2)*n23;
415    value_type d123 = (v1-v2)*n23;
416    if (d123>=0.0)
417    {
418        if (ds23<0.0) return false;
419        if (ds23>d123) return false;
420    }
421    else                         // d123 < 0
422    {
423        if (ds23>0.0) return false;
424        if (ds23<d123) return false;
425    }
426
427    vec_type v31 = v1-v3;
428    vec_type n31 = v31^vse;
429    value_type ds31 = (_s-v3)*n31;
430    value_type d231 = (v2-v3)*n31;
431    if (d231>=0.0)
432    {
433        if (ds31<0.0) return false;
434        if (ds31>d231) return false;
435    }
436    else                         // d231 < 0
437    {
438        if (ds31>0.0) return false;
439        if (ds31<d231) return false;
440    }
441
442    value_type r3 = ds12/d312;
443    value_type r1 = ds23/d123;
444    value_type r2 = ds31/d231;
445
446    //    value_type rt = r1+r2+r3;
447
448    vec_type in = v1*r1+v2*r2+v3*r3;
449
450    value_type length = vse.length();
451    vse /= length;
452    value_type d = (in-_s)*vse;
453
454    if (d<0.0) return false;
455    if (d>length) return false;
456
457    r = d/length;
458
459    return true;
460}
Note: See TracBrowser for help on using the browser.