椭球与直线求交 算法或者数学求解也可以

Question

请问,有没有什么好的算法,关于椭球与直线求交,因为我做的是裁减问题.
我用的是OpenGL环境开发
顺带的,关于椭球方程x*x/a*a+y*y/b*b+z*z/c*c=1
中的a,b,c是指轴长,还是指从中心点到面的距离,我数学很菜.

Answer 1

看这个吧
 http://community.csdn.net/Expert/topic/3767/3767461.xml?temp=.3111383

Answer 2

已经试了一个下午,可是,Happy兄的那个好像不对,可能我哪里计算错误了,交点没有求到.
而且,那个页面是一个点在内,一个在外的.是不是可以这样,如果第一个点在内的,就如那个算法,如果第一个点是外点的话,则,在T小于0的时候,才是正解吧.我明天要回去参加一个考试,所以,这个事情要耽搁几天.谢谢大家帮忙.
顺便想问问,有好的,效率高的算法吗?这个毕竟运算量太大,谢谢
也非常感谢Happy兄的鼎立支持:)

Answer 3

那个例子特殊
但是对于直线和椭球求交点的情况也是适用的原来算法当中的那个在内的点，可以定义为你的直线上的任意一点
直线和椭球计算结果最多是两个点，一个点对应是一个t数值
但是t数值在这里是没有范围限制的，正也好，负也好都是有效的数据了关键是否有又有的t数值，如果计算t的时候的sqrt里面的内容是负数表示无解，直线和椭球没有交点
否则就是有交点，具体的就是按照算法求就是了。直接用公式计算是最快的方法了，不可能更快了。

Answer 4

void ClipsEllipSimple(GLfloat AAxis,GLfloat BAxis,GLfloat CAxis, //椭圆的三个轴长
   GLfloat x1,GLfloat y1,GLfloat z1, //直线的一个端点
   GLfloat x2,GLfloat y2,GLfloat z2) //直线的另一个端点
{
GLfloat Px1,Py1,Pz1,Px2,Py2,Pz2; //裁剪后的新的两个线段点
double T,t1,t2,ta,tb,tc; //参数方程的参数
double delt; //判断一元二次方程是否有根,求交用
double ASquare,BSquare,CSquare; //分别代表椭球三轴的平方
ASquare=AAxis*AAxis;
BSquare=BAxis*BAxis;
CSquare=CAxis*CAxis; //double dx,dy,dz; //记录x,y,z的两点差值
int flag=0; //记录直线与椭球的交点情况
bool P1flag=FALSE,P2flag=FALSE; //用于记录哪个点是否被记下来
if(((x1*x1)/ASquare+(y1*y1)/BSquare+(z1*z1)/CSquare)<1)//代入椭球方程,判断是否在椭球内
{
flag++;
P1flag=TRUE; //第一点被记录
Px1=x1; Py1=y1; Pz1=z1; //第一点被保存
}
if(((x2*x2)/(AAxis*AAxis)+(y2*y2)/(BAxis*BAxis)+(z2*z2)/CSquare)<1)
{
flag++;
P2flag=TRUE;
Px2=x2; Py2=y2; Pz2=z2;
}
switch(flag)
{
case 0:
break;
case 1://与椭球有一个交点
//关于参数T的一元二次方程的三个系数
 ta=(x2-x1)*(x2-x1)*BSquare*CSquare+(y2-y1)*(y2-y1)*ASquare*CSquare+(z2-z1)*(z2-z1)*ASquare*BSquare;
 tb=2.0*((x2-x1)*BSquare*CSquare+(y2-y1)*ASquare*CSquare+(z2-z1)*ASquare*BSquare);
 tc=x1*BSquare*CSquare+y1*ASquare*CSquare+z1*ASquare*BSquare-ASquare*BSquare*CSquare;
//根判别式
delt = tb*tb - 4*ta*tc;
if(delt<0) break;
else
{
t1=(-tb+sqrt(delt))/(2*ta);
t2=(-tb-sqrt(delt))/(2*ta);
}
if(P1flag)
{
T=t1>0?t1:t2;
Px2=T*(x2-x1)+x1;
Py2=T*(y2-y1)+y1;
Pz2=T*(z2-z1)+z1;
}
if(P2flag)
{
T=t1<0?t1:t2;
Px1=T*(x2-x1)+x1;
Py1=T*(y2-y1)+y1;
Pz1=T*(z2-z1)+z1;
}
break;
case 2://完全在椭球内
break; }
}

Answer 5

#include "stdafx.h"
#include <math.h>
#include <stdio.h>
#include <stdlib.h>double a = 0.3f; 
double b = 0.5f;
double c = 0.3f;
double x00 = 0;
double y00 = 0;
double z00 = 0;
double x10 = 0.0517955f;
double y10 = -0.207970f;
double z10 = 0.499058f;
double x20 = 0.0521549f;
double y20 = -0.206991f;
double z20 = 0.499062f;double a1 = ((x20-x10)*(x20-x10)*b*b*c*c + (y20-y10)*(y20-y10)*a*a*c*c + (z20-z10)*(z20-z10)*a*a*b*b);
double b1 = 2.0*((x20-x10)*(x10-x00)*b*b*c*c + (y20-y10)*(y10-y00)*a*a*c*c + (z20-z10)*(z10-z00)*a*a*b*b);
double c1 = (x10-x00)*(x10-x00)*b*b*c*c + (y10-y00)*(y10-y00)*a*a*c*c + (z10-z00)*(z10-z00)*a*a*b*b- a*a*b*b*c*c;
double  p = b1*b1 - 4*a1*c1;
double t1 = (-b1 + sqrt(p) )/a1 * 0.5;
double t2 = (-b1 - sqrt(p) )/a1 * 0.5;
return 0;
}

Answer 6

这个就是当时测试的函数源码
其中 a，b，c就是椭球的三个轴
(x00,y00,z00) 表示椭球的中心，在你的例子当中，他们就是(0, 0, 0);
(x10, y10, z10) (x20, y20, z20)就是直线上的任意两个点
带入看看计算结果是否相符吧。

Answer 7

sorry，copy的时候，少了两行，
漏了
include <>
int main()
{只要p不小于0，就是有解的
没有给出实际的位置，根据那个文章的描述，你可以计算位置的
毕竟这个测试，当时做的也只是为了验证那个楼主的疑问而已

Answer 8

高  薪  诚  聘  V  C  +  +  精  英  软  媒  (  深  圳  )  成 立 于 二 零 零 二 年 五 月 。由 新 加 坡 私人 投 资 基 金 注 资 。软  媒  的  业  务  ，专  注  于  软  件  的“现  场 开 发 工 具”，持 续 的 挖 掘 用 户 使 用 软 件 的 核 心 利 益 。软 媒 堪 称 深 圳 第 一 大 软 件 军 团，集 结 了 一 大 批 专 兼 职V C + + 软 件 业 界 精 英 。软 媒 对 于 核 心 技 术 人 员 ，采 取 “ 四 高 ” 的 管 理 政 策 。（ 一 ） 高 薪
“ 永 远 让 薪 水 跑 在 能 力 前 面 ” 是 软 媒 的 座 右 铭 。（ 二 ） 高 技 术
软 媒 公 司 内 部 针 工 具 型 软 件 研 发 ，形 成 自 主 产 权 的 系列 软 件 架 构 。
 
（ 三 ） 高 手 军 团
软 媒 的 每 个 高 级 工 程 师 ， 都 是 身 手 不 凡 的 业 界 精 英 ， 形 成 了 浓 厚 的 高 科 技 氛 围 。（ 四 ） 高 素 质 用 户 群
“ 一 个 软 件 离 开 了 它 的 用 户 就 是 垃 圾” 并 不 过 分 ，软 媒 提 供 了 7 * 2 4 小 时 的 在 线 用 户 群 引 导 软 件 的 需 求 。
    产 品 介 绍    <  系 列 软 件 研 发 工 具  >
让 九 亿 农  民 兄 弟 都 能 开 发 出 自 己 喜 爱 的 软 件 。  提 示 ： 凡 符 合 本 职 位 要 求 者  ， 可 以 直 接 来 面 试 无 须 投 放 简 历 。 要 求 ： 精 通 标 准 C \ C + + 结 构 化 程 序 设 计 。
 1 、 要 求 有 V C + + 软 件 开 发 经 验 。
 2 、 精 通 W i n d o w s 界 面 开 发 ， 熟 练 使 用 C D C 绘 图 类 。
 3 、 具 有 良 好 的 独 立 开 发 能 力 和 自 主 开 发 能 力 。
 4 、 有 工 具 型 软 件 开 发 经 验 者 优 先 。 工 作 职 责 ：
 1 、 开 发 工 具 软 件 及 其 构 件 。
 2 、 独 立 自 主 设 计 工 具 使 用 流 程 。
 3 、 一 切 设 计 都 基 于 用 户 需 求 。
 4 、 不 需 要 团 队 开 发 经 验 。
 5 、 要 求 有 良 好 的 用 户 需 求 实 现 能 力 。 基 本 工 资 ：
 1 、 高 级 软 件 工 程 师 ： 9 , 0 0 0 元 / 月 联 系 方 式 ：  R i c h m a i n @ d u o s o f t . c nhttp://www.jobsdb.com.cn/main/jobseeker/JobTemplates/Default/CN/JobDetail.asp?CompanyID=109434&JobPostID=3178881&FromFlag=&Language=CN&Page=1 & T e m p l a t e I D = D e f a u l t

Answer 9

谢谢,我已经可以搞定了,谢谢:)
我推导函数出问题了,呵呵
关于T是否小于0的问题,我记得是这个参数函数是模拟向量,所以,是否大于0代表的是是在椭球内部还是外部,具体的,我会去仔细查阅的,这些资料我有.对亏了Happy兄,真的很感谢:)