1 /********************************************************************************
2 * *
3 * S i n g l e - P r e c i s i o n S p h e r e C l a s s *
4 * *
5 *********************************************************************************
6 * Copyright (C) 2004,2005 by Jeroen van der Zijp. All Rights Reserved. *
7 *********************************************************************************
8 * This library is free software; you can redistribute it and/or *
9 * modify it under the terms of the GNU Lesser General Public *
10 * License as published by the Free Software Foundation; either *
11 * version 2.1 of the License, or (at your option) any later version. *
12 * *
13 * This library is distributed in the hope that it will be useful, *
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
16 * Lesser General Public License for more details. *
17 * *
18 * You should have received a copy of the GNU Lesser General Public *
19 * License along with this library; if not, write to the Free Software *
20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. *
21 *********************************************************************************
22 * $Id: FXSphered.cpp,v 1.11.2.1 2006/04/05 22:09:48 fox Exp $ *
23 ********************************************************************************/
24 #include "xincs.h"
25 #include "fxver.h"
26 #include "fxdefs.h"
27 #include "FXHash.h"
28 #include "FXStream.h"
29 #include "FXVec2d.h"
30 #include "FXVec3d.h"
31 #include "FXVec4d.h"
32 #include "FXSphered.h"
33 #include "FXRanged.h"
34
35 /*
36 Notes:
37 - Negative radius represents empty bounding sphere.
38 */
39
40
41 using namespace FX;
42
43 /************************** S p h e r e C l a s s *************************/
44
45 namespace FX {
46
47
sqr(FXdouble x)48 inline FXdouble sqr(FXdouble x){ return x*x; }
49
50
51 // Initialize from bounding box
FXSphered(const FXRanged & bounds)52 FXSphered::FXSphered(const FXRanged& bounds):center(bounds.center()),radius(bounds.diameter()*0.5){
53 }
54
55
56
57 // Test if sphere contains point x,y,z
contains(FXdouble x,FXdouble y,FXdouble z) const58 FXbool FXSphered::contains(FXdouble x,FXdouble y,FXdouble z) const {
59 return 0.0<=radius && sqr(center.x-x)+sqr(center.y-y)+sqr(center.z-z)<=sqr(radius);
60 }
61
62
63 // Test if sphere contains point p
contains(const FXVec3d & p) const64 FXbool FXSphered::contains(const FXVec3d& p) const {
65 return contains(p.x,p.y,p.z);
66 }
67
68
69 // Test if sphere contains another box
contains(const FXRanged & box) const70 FXbool FXSphered::contains(const FXRanged& box) const {
71 return contains(box.corner(0)) &&
72 contains(box.corner(1)) &&
73 contains(box.corner(2)) &&
74 contains(box.corner(3)) &&
75 contains(box.corner(4)) &&
76 contains(box.corner(5)) &&
77 contains(box.corner(6)) &&
78 contains(box.corner(7));
79 }
80
81
82 // Test if sphere properly contains another sphere
contains(const FXSphered & sphere) const83 FXbool FXSphered::contains(const FXSphered& sphere) const {
84 if(0.0<=sphere.radius && sphere.radius<=radius){
85 register FXdouble dx=center.x-sphere.center.x;
86 register FXdouble dy=center.y-sphere.center.y;
87 register FXdouble dz=center.z-sphere.center.z;
88 return sphere.radius+sqrt(dx*dx+dy*dy+dz*dz)<=radius;
89 }
90 return FALSE;
91 }
92
93
94 // Include point
include(FXdouble x,FXdouble y,FXdouble z)95 FXSphered& FXSphered::include(FXdouble x,FXdouble y,FXdouble z){
96 register FXdouble dx,dy,dz,dist,delta,newradius;
97 if(0.0<=radius){
98 dx=x-center.x;
99 dy=y-center.y;
100 dz=z-center.z;
101 dist=sqrt(dx*dx+dy*dy+dz*dz);
102 if(radius<dist){
103 newradius=0.5*(radius+dist);
104 delta=(newradius-radius);
105 center.x+=delta*dx/dist;
106 center.y+=delta*dy/dist;
107 center.z+=delta*dz/dist;
108 radius=newradius;
109 }
110 return *this;
111 }
112 center.x=x;
113 center.y=y;
114 center.z=z;
115 radius=0.0;
116 return *this;
117 }
118
119
120 // Include point
include(const FXVec3d & p)121 FXSphered& FXSphered::include(const FXVec3d& p){
122 return include(p.x,p.y,p.z);
123 }
124
125
126 // Include given range into this one
include(const FXRanged & box)127 FXSphered& FXSphered::include(const FXRanged& box){
128 include(box.corner(0));
129 include(box.corner(1));
130 include(box.corner(2));
131 include(box.corner(3));
132 include(box.corner(4));
133 include(box.corner(5));
134 include(box.corner(6));
135 include(box.corner(7));
136 return *this;
137 }
138
139
140 // Include given sphere into this one
include(const FXSphered & sphere)141 FXSphered& FXSphered::include(const FXSphered& sphere){
142 register FXdouble dx,dy,dz,dist,delta,newradius;
143 if(0.0<=sphere.radius){
144 if(0.0<=radius){
145 dx=sphere.center.x-center.x;
146 dy=sphere.center.y-center.y;
147 dz=sphere.center.z-center.z;
148 dist=sqrt(dx*dx+dy*dy+dz*dz);
149 if(sphere.radius<dist+radius){
150 if(radius<dist+sphere.radius){
151 newradius=0.5*(radius+dist+sphere.radius);
152 delta=(newradius-radius);
153 center.x+=delta*dx/dist;
154 center.y+=delta*dy/dist;
155 center.z+=delta*dz/dist;
156 radius=newradius;
157 }
158 return *this;
159 }
160 }
161 center=sphere.center;
162 radius=sphere.radius;
163 }
164 return *this;
165 }
166
167
168
169 // Intersect sphere with normalized plane ax+by+cz+w; returns -1,0,+1
intersect(const FXVec4d & plane) const170 FXint FXSphered::intersect(const FXVec4d& plane) const {
171 register FXdouble dist=distance(plane,center);
172
173 // Lower point on positive side of plane
174 if(dist>=radius) return 1;
175
176 // Upper point on negative side of plane
177 if(dist<=-radius) return -1;
178
179 // Overlap
180 return 0;
181 }
182
183
184 // Intersect sphere with ray u-v
intersect(const FXVec3d & u,const FXVec3d & v) const185 FXbool FXSphered::intersect(const FXVec3d& u,const FXVec3d& v) const {
186 if(0.0<=radius){
187 FXdouble rr=radius*radius;
188 FXVec3d uc=center-u; // Vector from u to center
189 FXdouble dd=len2(uc);
190 if(dd>rr){ // Ray start point outside sphere
191 FXVec3d uv=v-u; // Vector from u to v
192 FXdouble hh=uc*uv; // If hh<0, uv points away from center
193 if(0.0<=hh){ // Not away from sphere
194 FXdouble kk=len2(uv);
195 FXdouble disc=hh*hh-kk*(dd-rr); // FIXME this needs to be checked again!
196 if(disc<=0.0) return FALSE;
197 return TRUE;
198 }
199 return FALSE;
200 }
201 return TRUE;
202 }
203 return FALSE;
204 }
205
206
207 // Test if sphere overlaps with box
overlap(const FXSphered & a,const FXRanged & b)208 FXbool overlap(const FXSphered& a,const FXRanged& b){
209 if(0.0<=a.radius){
210 register FXdouble dd=0.0;
211
212 if(a.center.x<b.lower.x)
213 dd+=sqr(a.center.x-b.lower.x);
214 else if(a.center.x>b.upper.x)
215 dd+=sqr(a.center.x-b.upper.x);
216
217 if(a.center.y<b.lower.y)
218 dd+=sqr(a.center.y-b.lower.y);
219 else if(a.center.y>b.upper.y)
220 dd+=sqr(a.center.y-b.upper.y);
221
222 if(a.center.z<b.lower.z)
223 dd+=sqr(a.center.z-b.lower.z);
224 else if(a.center.z>b.upper.z)
225 dd+=sqr(a.center.z-b.upper.z);
226
227 return dd<=a.radius*a.radius;
228 }
229 return FALSE;
230 }
231
232
233 // Test if box overlaps with sphere; algorithm due to Arvo (GEMS I)
overlap(const FXRanged & a,const FXSphered & b)234 FXbool overlap(const FXRanged& a,const FXSphered& b){
235 return overlap(b,a);
236 }
237
238
239 // Test if spheres overlap
overlap(const FXSphered & a,const FXSphered & b)240 FXbool overlap(const FXSphered& a,const FXSphered& b){
241 if(0.0<=a.radius && 0.0<=b.radius){
242 register FXdouble dx=a.center.x-b.center.x;
243 register FXdouble dy=a.center.y-b.center.y;
244 register FXdouble dz=a.center.z-b.center.z;
245 return sqrt(dx*dx+dy*dy+dz*dz)<(a.radius+b.radius);
246 }
247 return FALSE;
248 }
249
250
251 // Saving
operator <<(FXStream & store,const FXSphered & sphere)252 FXStream& operator<<(FXStream& store,const FXSphered& sphere){
253 store << sphere.center << sphere.radius;
254 return store;
255 }
256
257
258 // Loading
operator >>(FXStream & store,FXSphered & sphere)259 FXStream& operator>>(FXStream& store,FXSphered& sphere){
260 store >> sphere.center >> sphere.radius;
261 return store;
262 }
263
264 }
265