daojin
- 浏览: 676782 次
- 性别:
- 来自: 西安
-
文章分类
- 全部博客 (440)
- c++学习笔记 (89)
- 如何适应变化 (1)
- VC常见问题 (7)
- Brew开发12月9日至12月26日 (1)
- 软件架构 (3)
- 自己动手写C语言编译器之文档翻译工作 (1)
- 自己动手写C语言编译器 (6)
- 网站资源 (1)
- 郝彬英文教程 (1)
- 45度斜角地图 (0)
- 35.264等角视图 (0)
- 30等角视图 (1)
- 如何搞opengl (1)
- 卷积。 (1)
- Android解析日记 (5)
- Linux基础教学 (9)
- Android游戏框架 (9)
- Android游戏开发之OpenGL之坐标矩阵 (2)
- Android异常处理 (1)
- 资源网站 (1)
- ARM汇编学习 (1)
- game (0)
- 自己动手实现OpenGL（准备开始！后面有空补充） (3)
- 云计算 (1)
- Android面试题目 (17)
- 深度学习 (1)
- OpenGL实践 (1)
- 神经网络学习-翻译 (4)
最新评论
-
3482561：
Android 面试题目之 线程池 -
daojin：
直接布局。
安卓高手之路之图形系统(6)requestLayout的流程 -
hety163：
没明白楼主所说的最后两段。如果一个相对布局中有多个子view， ...
安卓高手之路之图形系统(6)requestLayout的流程 -
jackuhan：
100篇！！！膜拜
安卓高手之路之 图形系统之 图形框架（1） -
ritterliu：
不错，按照流程把关键代码都贴出来了。谢谢分享
Android输入输出系统之TouchEvent流程
#include "stdafx.h"
#include "OpenGL.h"
#include "Map.h"
#include "math.h"
#include "ArrayInterTriangle.h"
#include <iostream.h>
#include <stdio.h>
#include <bitset>
extern unsigned int m_ID;
#include <math.h>
#include<stdexcept>
#include<time.h>
extern bool Lbutdown; // 鼠标左键
extern bool Rbutdown; // 鼠标左键
//////////////////////////////////////////////////////////////////////
extern HWND hWnd;
//定义最近的距离视点最近的鼠标物体：
//定义一个结构来保存所有的物体：
#include<list>
int TreeDepth=0;
#include<vector>
using std::bitset;
using std::list;
using std::vector;
using std::runtime_error;
using std::length_error;
vector<int> TheDividerList;
class Triangle{
public:
float a[3];
float b[3];
float c[3];
};
class TheTreeObect{
int maxlen;
int n;
//定义当前分割平面的索引。
int currentFlip;
Triangle *Triangles;
public:
void SetAsNode(int currentFlip){
Triangle temp=Triangles[currentFlip];
delete [] Triangles;
Triangles=new Triangle(temp);
}
void deleteALL(){
delete[] Triangles;
Triangles=NULL;
n=0;
}
void resetTriangle(Triangle *Triangles,int n){
delete[] this->Triangles;
this->Triangles=Triangles;
this->n=n;
this->maxlen=n;
}
TheTreeObect(){
Triangles= new Triangle[10];
maxlen=10;
n=0;
}
int add(Triangle triangle)
{
if(n==maxlen){
Triangle* temp=Triangles;
Triangles=new Triangle[n+10];
for(int i=0;i<n;i++){
for(int j=0;j<3;j++){
Triangles[i].a[j]=temp[i].a[j];
Triangles[i].b[j]=temp[i].b[j];
Triangles[i].c[j]=temp[i].c[j];
}
}
delete [] temp;
}
for(int j=0;j<3;j++){
Triangles[n].a[j]=triangle.a[j];
Triangles[n].b[j]=triangle.b[j];
Triangles[n].c[j]=triangle.c[j];
}
n++;
return n;
}
int getFlip(){
return currentFlip;
}
int getN(){
return n;
}
Triangle *getTriangles()
{
return Triangles;
}
TheTreeObect(float (*triangle)[3][3],int n1)
{
Triangles= new Triangle[n1];
n=n1;
for(int i=0;i<n;i++){
for(int j=0;j<3;j++){
//第二维表示点的索引，第三维表示，xyz坐标
Triangles[i].a[j]=triangle[i][0][j];
Triangles[i].b[j]=triangle[i][1][j];
Triangles[i].c[j]=triangle[i][2][j];
}
}
}
};
//而叉树节点是一个特殊的物体。。它只有一个平面。
class BSPNode:public TheTreeObect{
public:
BSPNode(){
IsLeaf=true;
}
//是否为分割面。或是是物体，或者是分割面。
bool IsLeaf;
bool IsWithObject;
void setIsWithObject(bool is)
{
IsWithObject=is;
}
BSPNode(TheTreeObect& obj):TheTreeObect(obj){
}
void set(bool Front)
{
IsFront=Front;
}
bool IsNode;
bool IsFront;
TheTreeObect* pBackChild;
TheTreeObect* pFrontChild;
//查看物体的第index个三角形是否与既定面共面。
void outPutSanjiao(Triangle triangle)
{
float *a=triangle.a;
float a0=a[0];
float a1=a[1];
float a2=a[2];
cout<<endl<<a0<<" "<<a1<<" "<<a2<<" "<<endl;
float *b=triangle.b;
float b0=b[0];
float b1=b[1];
float b2=b[2];
cout<<b0<<" "<<b1<<" "<<b2<<" "<<endl;
float *c=triangle.c;
float c0=c[0];
float c1=c[1];
float c2=c[2];
cout<<c0<<" "<<c1<<" "<<c2<<" "<<endl;
}
void outPutSanJiaos(Triangle* pTriangle,int n)
{
for(int i=0;i<n;i++)
{
outPutSanjiao(pTriangle[i]);
}
}
void outPutVector(char *p,float *pf,int n)
{
for(int j=0;p[j]!='\0';p++)
{
cout<<p[j];
}
cout<<":"<<endl;
for(int i=0;i<n;i++)
{
cout<<pf[i]<<endl;
}
}
//函数功能：判断一个三角形来自另外一个三角形所在平面的何方。
//功能描述：如果共面，则same为true，divided为false,方向相同则返回true,否则返回false;
// 如果不共面，则根据在前还是后，还是divided ,进行返回。
bool IsFomFront(TheTreeObect obj,int index,int currentFlip,bool &same,bool &divied){
divied=false;
same=false;
bitset<3> position[3];
float dir[3];
bool Front[3];
bool IsNotInFlat[3];
float point[3];
memcpy(point,obj.getTriangles()[index].a,3*sizeof(float));
//int currentFlip=getFlip();
VectBinus(obj.getTriangles()[currentFlip].a,point,dir);
outPutVector("射线原点",point,3);
outPutVector("射线终点",obj.getTriangles()[currentFlip].a,3);
outPutVector("射线方向",dir,3);
IsNotInFlat[0]=IsIntersectWithTriangle(
point,
dir,
obj.getTriangles()[currentFlip].a,
obj.getTriangles()[currentFlip].b,
obj.getTriangles()[currentFlip].c,
point,
Front[0]
);
cout<<"********************开始射线检测****************************************"<<endl;
cout<<"分割面为"<<endl;
outPutSanjiao(obj.getTriangles()[currentFlip]);
if(!IsNotInFlat[0])cout<<"射线在平面上"<<endl;
else if(Front[0])cout<<"射线从前方穿过"<<endl;
else cout<<"射线从后方穿过"<<endl;
cout<<"********************检测结束****************************************"<<endl;
memcpy(point,obj.getTriangles()[index].b,3*sizeof(float));
VectBinus(obj.getTriangles()[currentFlip].b,point,dir);
IsNotInFlat[1]=IsIntersectWithTriangle(
point,
dir,
obj.getTriangles()[currentFlip].a,
obj.getTriangles()[currentFlip].b,
obj.getTriangles()[currentFlip].c,
point,
Front[1]
);
cout<<"********************开始射线检测****************************************"<<endl;
outPutVector("射线原点",point,3);
outPutVector("射线方向",dir,3);
cout<<"分割面为"<<endl;
outPutSanjiao(obj.getTriangles()[currentFlip]);
if(!IsNotInFlat[1])cout<<"射线在平面上"<<endl;
else if(Front[1])cout<<"射线从前方穿过"<<endl;
else cout<<"射线从后方穿过"<<endl;
cout<<"********************检测结束****************************************"<<endl;
memcpy(point,obj.getTriangles()[index].c,3*sizeof(float));
VectBinus(obj.getTriangles()[currentFlip].c,point,dir);
IsNotInFlat[2]=IsIntersectWithTriangle(
point,
dir,
obj.getTriangles()[currentFlip].a,
obj.getTriangles()[currentFlip].b,
obj.getTriangles()[currentFlip].c,
point,
Front[2]
);
cout<<"********************开始射线检测****************************************"<<endl;
outPutVector("射线原点",point,3);
outPutVector("射线方向",dir,3);
cout<<"分割面为"<<endl;
outPutSanjiao(obj.getTriangles()[currentFlip]);
if(!IsNotInFlat[2])cout<<"射线在平面上"<<endl;
else if(Front[2])cout<<"射线从前方穿过"<<endl;
else cout<<"射线从后方穿过"<<endl;
cout<<"********************检测结束****************************************"<<endl;
for(int i=0;i<3;i++)
{
if(!IsNotInFlat[i])position[i].set(0);else
if(Front[i])position[i].set(1);else
position[i].set(2);
}
for(i=0;i<3;i++)
{
cout<<"i:顶点"<<i<<endl;
cout<<position[i][0];
cout<<position[i][1];
cout<<position[i][2];
}
//每个点的三个状态对应为 position[0],position[1],position[2];
bitset<3> positi=position[0]&position[1]&position[2];
for(i=0;i<3;i++)
{
cout<<"综合：";
cout<<positi[i]<<endl;
}
//查看是否共面
//分析结果为:
cout<<"经过分析，三角形与平面的关系为："<<endl;
if(positi[0])
{ cout<<"这是一个相同的平面"<<endl;
same=true;
//查看方向是否相同
//求得他们的发线：
float flat_3_flip[3];
float flat_3_temp[3];
qiuFaXiangLiang(
getTriangles()[currentFlip].a,
getTriangles()[currentFlip].b,
getTriangles()[currentFlip].c,
flat_3_flip);
qiuFaXiangLiang(
getTriangles()[index].a,
getTriangles()[index].b,
getTriangles()[index].c,
flat_3_temp);
float dotval=DotProduct(flat_3_flip,flat_3_temp);
if(dotval<0){
//点积为负值
return false;
}else
//点积为正值
return true;
}else {
positi=position[0]|position[1]|position[2];
//不共面并且没有在后面的点！！
if(!positi[2])
{
cout<<"前面"<<endl;
return true;
}
//不共面没有前面的点
else if(!positi[1])
{
cout<<"后面"<<endl;
return false;
}else
{
//不共面，既有前面的点，也有后面的点。
cout<<"被分割的面"<<endl;
divied=true;
return false;
}
}
}
//函数功能：从所有的备选三角形列表中找到一个最佳的分割平面。
int getTheBestDivider(vector<int> TheDividerList,bool &found, TheTreeObect obj){
cout<<"×××××××××寻找最佳分割面开始××××××××××××××"<<endl;
cout<<"当前的树深为"<<endl;
cout<<TreeDepth<<endl;
cout<<"要检测的三角集合为："<<endl;
outPutSanJiaos(obj.getTriangles(),obj.getN());
//定义评估数组
int *pingguvalue=new int[TheDividerList.size()];
//是否找到
found=false;
//定义最佳评估值
int theOptimizedValue;
//最佳的评估值对应的三角形编号(对应于theDividerList)
int theOpTriagl;
//评估值是否初始化
bool IsInit=false;
//判断是否为凸空间，默认为凸
bool AllFront=true;
bool AllBack=true;
for(int flip=0;flip<TheDividerList.size();flip++){
cout<<"-------------------第"<<flip<<"个分割面评估值检测开始-------------------"<<endl;
cout<<"第"<<flip<<"个待定分割面为"<<endl;
cout<<"第"<<TheDividerList[flip]<<"个三角形"<<endl;
outPutSanjiao(obj.getTriangles()[TheDividerList[flip]]);
int N_FRONT=0;
int N_BACK=0;
int N_DIVIDE=0;
if(
!IsTriangle(
obj.getTriangles()[TheDividerList[flip]].a,
obj.getTriangles()[TheDividerList[flip]].b,
obj.getTriangles()[TheDividerList[flip]].c
)
)
{
cout<<"它不是一个平面！"<<endl;
continue;
}else
{
cout<<"它是一个平面！"<<endl;
}
for(int index=0;index<obj.getN();index++){
bool front;
bool same;
bool divided;
front=IsFomFront(obj,index,flip,same,divided);
if(divided){
N_DIVIDE++;
AllBack=false;
AllFront=false;
}
else if(front){
AllBack=false;
N_FRONT++;
}else {
N_BACK++;
AllFront=false;
}
}
//不是所有的平面都在后面，也不是都在前面
if(!AllBack&&!AllFront){
cout<<"找到了这样的平面";
found=true;
}
else{
cout<<"没有找到！";
found=false;
}
cout<<"在它前面的三角形个数为"<<N_FRONT<<endl;
cout<<"在它后面的三角形个数为"<<N_BACK<<endl;
cout<<"被它分割的三角形个数为"<<N_DIVIDE<<endl;
//说明需要可以找到这样的分割面
//found=true;
pinggu_value[flip]=fabs(N_FRONT-N_BACK)+N_DIVIDE;
cout<<"评估值为"<<pinggu_value[flip]<<endl;
if(!IsInit){
theOpTriagl=flip;
theOptimizedValue=pinggu_value[flip];
IsInit=true;
}
//没有初始化并且小于目前的评估值
else if(pinggu_value[flip]<theOptimizedValue){
theOpTriagl=flip;
theOptimizedValue=pinggu_value[flip];
}
cout<<"评估结果为："<<endl;
cout<<"树深为"<<endl;
cout<<TreeDepth<<endl;
cout<<"要检测的三角集合为："<<endl;
outPutSanJiaos(obj.getTriangles(),obj.getN());
if(AllBack){
cout<<"它在所有平面的后面"<<endl;
}
else if(AllFront){
cout<<"它在所有平面的前面"<<endl;
}
else cout<<"一些在它前面，一些在它后面"<<endl;
cout<<"当前的最佳评估值为"<<endl;
cout<< theOptimizedValue<<endl;
cout<<"当前的最佳分割面为"<<endl;
cout<<theOpTriagl<<endl;
outPutSanjiao(obj.getTriangles()[TheDividerList[theOpTriagl]]);
cout<<"-------------------第"<<flip<<"个分割面评估值检测结束-------------------"<<endl;
}
Triangle thetri=obj.getTriangles()[theOpTriagl];
glBegin(GL_TRIANGLES);
glColor3f(1.0,0.0,0.0);
glVertex3f(thetri.a[0],thetri.a[1],thetri.a[2]);
glVertex3f(thetri.b[0],thetri.b[1],thetri.b[2]);
glVertex3f(thetri.c[0],thetri.c[1],thetri.c[2]);
glEnd();
return theOpTriagl;
cout<<"×××××××××寻找最佳分割面结束××××××××××××××"<<endl;
}
//参数：triangle：待分割的三角形
//divider: 分割面
//pTri:分割后的三角形
//p_front:前，还是后
//返回：分割后的三角形个数
int divideTriangle(Triangle triangle,Triangle divider,Triangle* &pTri,bool *& p_front){
//定义Bool型变量记录以顶点出发的变是否与平面相交。
bool notdivided[3];
//边
float dingdian[3][3];
//边是向量。从对应的顶点出发的边。
float bian[3][3];
//构造三角形集合：
//记录顶点三角是否有效：
bool valid[3];
//bool front[3];
float dingdiansanjiao[3][3][3];
//对顶点和边向量进行赋值
//平面方程系数
float flat[4];
unsigned char dingdianweizhi[3];
if(!qiuPingMianFangCheng(divider.a,divider.b,divider.c,flat))
return -1;
for(int i=0;i<3;i++)
{
dingdian[0][i]=triangle.a[i];
dingdian[1][i]=triangle.b[i];
dingdian[2][i]=triangle.c[i];
}
for(i=0;i<3;i++)
{
int j=i+1;
if(j==3)j=0;
VectBinus(dingdian[j],dingdian[i],bian[i]);
}
//判断各个顶点与平面的位置关系
const unsigned char QIAN=0;
const unsigned char SHANG=1;
const unsigned char HOU=2;
for(i=0;i<3;i++)
{
float k=
flat[0]*dingdian[i][0]
+flat[1]*dingdian[i][1]
+flat[2]*dingdian[i][2]
+flat[3];
if(k>0.00001)dingdianweizhi[i]=QIAN;
else if(k<-0.00001)dingdianweizhi[i]=HOU;
else dingdianweizhi[i]=SHANG;
}
unsigned char jiaodianweizhi[3];
float jiaodian[3][3];
unsigned char m=0;
pTri =new Triangle[1+2];
p_front=new bool[3];
int n=0;
for(i=0;i<3;i++)
{
if(fabs(dingdianweizhi[i]-dingdianweizhi[i==2?0:i+1])==2)
{
jiaodianweizhi[i]=SHANG;
calInsert(dingdian[i],bian[i],flat,jiaodian[i]);
notdivided[i]=false;
}else
{
//交点退化为顶点
/* for(int j=0;j<3;j++)
{
jiaodian[i][j]=dingdian[i][j];
}
*/
memcpy(jiaodian[i],dingdian[i],sizeof(jiaodian[i]));
jiaodianweizhi[i]=dingdianweizhi[i];
notdivided[i]=true;
}
}
memcpy(pTri[n].a,jiaodian[0],sizeof(jiaodian[0]));
memcpy(pTri[n].b,jiaodian[1],sizeof(jiaodian[1]));
memcpy(pTri[n].c,jiaodian[2],sizeof(jiaodian[2]));
if(jiaodianweizhi[0]==QIAN||jiaodianweizhi[1]==QIAN||jiaodianweizhi[2]==QIAN){
p_front[n]=true;
}else if(jiaodianweizhi[0]==HOU||jiaodianweizhi[1]==HOU||jiaodianweizhi[2]==HOU)
{
p_front[n]=false;
}
n++;
for(i=0;i<3;i++)
{
if(!notdivided[i])
{
valid[i]=true;
int next;
int pre;
next=(i==2?0:i+1);
pre=(i==0?2:i-1);
dingdiansanjiao[i][0][0]=dingdian[i][0];
dingdiansanjiao[i][0][1]=dingdian[i][1];
dingdiansanjiao[i][0][2]=dingdian[i][2];
dingdiansanjiao[i][1][0]=jiaodian[i][0];
dingdiansanjiao[i][1][1]=jiaodian[i][1];
dingdiansanjiao[i][1][2]=jiaodian[i][2];
if(!notdivided[pre]){
dingdiansanjiao[i][2][0]=jiaodian[pre][0];
dingdiansanjiao[i][2][1]=jiaodian[pre][1];
dingdiansanjiao[i][2][2]=jiaodian[pre][2];
}else{
dingdiansanjiao[i][2][0]=dingdian[pre][0];
dingdiansanjiao[i][2][1]=dingdian[pre][1];
dingdiansanjiao[i][2][2]=dingdian[pre][2];
}
memcpy(pTri[n].a,dingdiansanjiao[i][0],sizeof(float [3]));
memcpy(pTri[n].b,dingdiansanjiao[i][1],sizeof(dingdiansanjiao[i][0]));
memcpy(pTri[n].c,dingdiansanjiao[i][2],sizeof(dingdiansanjiao[i][0]));
if(dingdianweizhi[i]==QIAN){
p_front[n]=true;
}else if(dingdianweizhi[i]==HOU)
{
p_front[n]=false;
}
n++;
}
}
cout<<"分解面为："<<endl;
outPutSanjiao(divider);
cout<<"待分解的三角为："<<endl;
outPutSanjiao(triangle);
cout<<"分解后的三角为："<<endl;
outPutSanJiaos(pTri,n);
cout<<"位置关系为"<<endl;
for(int mk=0;mk<n;mk++)
{
if(p_front[mk])cout<<"前！"<<endl;
else cout<<"后"<<endl;
}
return n;
}
//现在根据以上的信息，得到我们的三角形
/*float flat[4];
bool insectFlag[3];
float AB_INSECT[3];
float BC_INSECT[3];
float CA_INSECT[3];
float AB[3],BC[3],CA[3];
for(int i=0;i<3;i++)
{
AB[i]=triangle.b[i]-triangle.a[i];
BC[i]=triangle.c[i]-triangle.b[i];
CA[i]=triangle.a[i]-triangle.c[i];
}
//求得分割面的方程系数,返回-1表示方程不存在
cout<<"*******************求解平面方程开始*******************"<<endl;
outPutVector("A",divider.a,3);
outPutVector("B",divider.b,3);
outPutVector("C",divider.c,3);
if(!qiuPingMianFangCheng(divider.a,divider.b,divider.c,flat))
{
cout<<"没找到平面方程！"<<endl;
return -1;
}
cout<<"**********************求解平面方程结束****************"<<endl;
cout<<"分解面为："<<endl;
outPutSanjiao(divider);
cout<<"待分解的三角为："<<endl;
outPutSanjiao(triangle);
//第一步:求直线与平面的交点
calInsert(triangle.a,AB,flat,AB_INSECT);
//第二部：看这个交点在不在线段内。
float v1[3];
float v2[3];
VectBinus(triangle.a,AB_INSECT,v1);
VectBinus(triangle.b,AB_INSECT,v2);
float dot=DotProduct(v1,v2);
if(dot>0||dot==0)insectFlag[2]=true;
else
{
insectFlag[2]=false;
for(int m=0;m<3;m++)
AB_INSECT[m]=triangle.a[m];
}
cout<<"经过计算发现与AB边的交点为：";
for(i=0;i<3;i++){
cout<<AB_INSECT[i];
}
//第一步:求直线与平面的交点
calInsert(triangle.b,BC,flat,BC_INSECT);
//第二部：看这个交点在不在线段内。
VectBinus(triangle.b,BC_INSECT,v1);
VectBinus(triangle.c,BC_INSECT,v2);
dot=DotProduct(v1,v2);
if(dot>0||dot==0)insectFlag[0]=true;
else
{
insectFlag[0]=false;
for(int m=0;m<3;m++)
BC_INSECT[m]=triangle.b[m];
}
cout<<"经过计算发现与BC边的交点为：";
for(i=0;i<3;i++){
cout<<BC_INSECT[i];
}
//第一步:求直线与平面的交点
calInsert(triangle.c,CA,flat,CA_INSECT);
//第二部：看这个交点在不在线段内。
VectBinus(triangle.c,CA_INSECT,v1);
VectBinus(triangle.a,CA_INSECT,v2);
dot=DotProduct(v1,v2);
if(dot>0||dot==0)
{
insectFlag[1]=true;
}
else
{
insectFlag[1]=false;
for(int m=0;m<3;m++)
CA_INSECT[i]=triangle.c[i];
}
cout<<"经过计算发现与CA边的交点为：";
for(i=0;i<3;i++){
cout<<CA_INSECT[i];
}
//先给这些边编号：
float *jiaodian[3];
jiaodian[0]=BC_INSECT;
jiaodian[1]=CA_INSECT;
jiaodian[2]=AB_INSECT;
float *Bian[3];
Bian[0]=BC;
Bian[1]=CA;
Bian[2]=AB;
float *dingdian[3];
dingdian[0]=triangle.a;
dingdian[1]=triangle.b;
dingdian[2]=triangle.c;
float *sanjiaoxing[3][3];
//分解后的三角形个数
for(int k=0;k<3;k++)
{
sanjiaoxing[k][0]=dingdian[k];
sanjiaoxing[k][1]=jiaodian[(k-1+3)%3];
sanjiaoxing[k][2]=jiaodian[(k+1+3)%3];
}
pTri=new Triangle[4];
//下面遍历这些假三角，有些是不存在的
for(int ki=0;ki<3;ki++)
{
cout<<"三角形"<<ki<<"为："<<endl;
for(k=0;k<3;k++){
cout<<sanjiaoxing[ki][k][0]<<" ";
cout<<sanjiaoxing[ki][k][1]<<" ";
cout<<sanjiaoxing[ki][k][2]<<" ";
}
}
int n=0;
for(i=0;i<3;i++)
{
if(IsTriangle(sanjiaoxing[i][0],sanjiaoxing[i][1],sanjiaoxing[i][2]))
{
for(k=0;k<3;k++){
pTri[n].a[k]=sanjiaoxing[i][0][k];
pTri[n].b[k]=sanjiaoxing[i][1][k];
pTri[n].c[k]=sanjiaoxing[i][2][k];
}
n++;
}
}
outPutSanJiaos(pTri,n);
if(IsTriangle(jiaodian[0],jiaodian[1],jiaodian[2]))
{ n++;
for(k=0;k<3;k++)
{
pTri[n].a[k]=jiaodian[0][k];
pTri[n].b[k]=jiaodian[1][k];
pTri[n].c[k]=jiaodian[2][k];
}
}
Triangle * temp=pTri;
pTri=new Triangle[n];
for(k=0;k<n;k++)
{
pTri[k]=temp[k];
}
delete [] temp;
p_front=new bool[n];
for(k=0;k<n;k++)
{
float dir[3];
float point[3];
bool Front[3];
bool NotInTheFlat[3];
VectBinus(divider.a,pTri[k].a,dir);
NotInTheFlat[0]=IsIntersectWithTriangle(
pTri[k].a,
dir,
divider.a,
divider.b,
divider.c,
point,
Front[0]
);
VectBinus(divider.b,pTri[k].b,dir);
NotInTheFlat[1]=IsIntersectWithTriangle(
pTri[k].b,
dir,
divider.a,
divider.b,
divider.c,
point,
Front[1]
);
VectBinus(divider.c,pTri[k].c,dir);
NotInTheFlat[2]=IsIntersectWithTriangle(
pTri[k].c,
dir,
divider.a,
divider.b,
divider.c,
point,
Front[2]
);
for(i=0;i<3;i++)
{
if(!NotInTheFlat[i])cout<<"上"<<endl;
else if(Front[i])cout<<"前"<<endl;
else cout<<"后"<<endl;
}
for(i=0;i<3;i++)
{
if(NotInTheFlat[i]){
if(Front[i])
{
p_front[k]=true;
cout<<k<<"********************************"<<"前面！"<<endl;
}
else
{
p_front[k]=false;
cout<<k<<"********************************"<<"后面"<<endl;
}
break;
}else
{
cout<<"共面！"<<endl;
}
}
if(p_front[k])cout<<"前！"<<endl;
else cout<<"后"<<endl;
}
for(int mk=0;mk<n;mk++)
{
if(p_front[mk])cout<<"前！"<<endl;
else cout<<"后"<<endl;
}
cout<<"分解后的三角为："<<endl;
outPutSanJiaos(pTri,n);
cout<<"位置关系为"<<endl;
return n;
*/
void addObject(TheTreeObect obj){
TreeDepth++;
// bool same;
bool IsFront;
bool NoUsed=true;
//0表示没找到，其他则返回其索引+1；
int index=0;
//getN是当前的个数
//如果是叶子，那么去构造分割平面列表。
if(IsLeaf){
//构造最初的原始三角形集合
for(int j=0;j<getN();j++)
{
obj.add(getTriangles()[j]);
}
cout<<"初始化的三角形集合为"<<endl;
outPutSanJiaos(obj.getTriangles(),obj.getN());
for(int i=0;i<obj.getN();i++)
{
for(int j=0;j<TheDividerList.size();j++)
{
cout<<"j:"<<j<<endl;
cout<<"三角形集合为"<<endl;
outPutSanJiaos(obj.getTriangles(),obj.getN());
cout<<"********************待检测的数据*************************"<<endl<<endl;
cout<<"待检测的三角形为："<<endl;
outPutSanjiao(obj.getTriangles()[i]);
cout<<endl<<"i的值为："<<i<<" "<<"已经选为分割面的数量为"<<TheDividerList.size()<<endl;
cout<<"分割面为"<<endl;
outPutSanjiao(obj.getTriangles()[TheDividerList[j]]);
cout<<"********************检测数据显示结束*************************"<<endl<<endl;
NoUsed=true;
bool sameFlat=false;
bool divided=false;
IsFront=IsFomFront(obj,i,TheDividerList[j],sameFlat,divided);
cout<<"我们的三角形经过IsFomFront(obj,i,TheDividerList[j],sameFlat,divided)后变为："<<endl;
outPutSanJiaos(obj.getTriangles(),obj.getN());
int m=TheDividerList[j];
cout<<"经过最终确认，他们的位置关系为"<<endl;
if(divided)cout<<"被分割的面"<<endl;
else if(sameFlat)cout<<"相同的平面！！"<<endl;
else if(IsFront)cout<<"在分割面的前面"<<endl;
else
cout<<"在分割面的后面"<<endl;
cout<<"*************确认结束*************"<<endl;
if(sameFlat){
NoUsed=false;
break;
}
}
cout<<"是否为相同的平面的确定结果:"<<endl;
if(NoUsed){
cout<<"不相同的平面！！"<<endl;
//这个面可以作为分割面。
TheDividerList.push_back(i);
}
else
cout<<"相同的平面"<<endl;
cout<<"***************输出结束****************"<<endl;
}
cout<<"查找待定分割面集合之后，OBJ里面的三角形为："<<endl;
outPutSanJiaos(obj.getTriangles(),obj.getN());
}//ifEnd
bool found;
if(IsLeaf)
{
index=getTheBestDivider(TheDividerList,found,obj);
cout<<"查找最佳分割面集合之后，OBJ里面的三角形为："<<endl;
outPutSanJiaos(obj.getTriangles(),obj.getN());
cout<<"*********************搜寻最佳的分割面开始**********************"<<endl<<endl;
if(found){
cout<<"找到了分割面:"<<endl;
outPutSanjiao(obj.getTriangles()[index]);
}
else
{
cout<<"没找到分割面"<<endl;
}
cout<<"×××××××××××结束×××××××"<<endl;
if(!found)
{
resetTriangle(obj.getTriangles(),obj.getN());
return;
}
TheTreeObect* FrontObj=new TheTreeObect();
TheTreeObect* BackObj=new TheTreeObect();
cout<<"×××××××××××三角形集合的前后分类开始×××××××××"<<endl<<endl;
for(int i=0;i<obj.getN();i++){
bool sameFlat=false;
bool divided=false;
IsFront=IsFomFront(obj,i,TheDividerList.at(index),sameFlat,divided);
//如果交叉.
if(divided){
//分解三角形
Triangle* pTri;
bool * p_front;
int number=divideTriangle(obj.getTriangles()[i],obj.getTriangles()[TheDividerList.at(index)],pTri,p_front);
for(i=0;i<number;i++){
if(*p_front++)
{
cout<<"前物---------得到更新"<<endl;
FrontObj->add(*pTri++);
outPutSanJiaos(FrontObj->getTriangles(),FrontObj->getN());
}else
{
cout<<"后物---------得到更新"<<endl;
BackObj->add(*pTri++);
outPutSanJiaos(BackObj->getTriangles(),BackObj->getN());
}
}
}else if(IsFront){
FrontObj->add(obj.getTriangles()[i]);
cout<<"前物---------得到更新"<<endl;
outPutSanJiaos(FrontObj->getTriangles(),FrontObj->getN());
}else{
BackObj->add(obj.getTriangles()[i]);
cout<<"后物---------得到更新"<<endl;
outPutSanJiaos(BackObj->getTriangles(),BackObj->getN());
}
}
cout<<"分类结果为："<<endl;
cout<<"我们的最佳分割平面为："<<endl;
outPutSanjiao(obj.getTriangles()[TheDividerList[index]]);
cout<<"待分类的三角形结合为："<<endl;
outPutSanJiaos(obj.getTriangles(),obj.getN());
cout<<"前向面："<<endl;
outPutSanJiaos(FrontObj->getTriangles(),FrontObj->getN());
cout<<"后向面："<<endl;
outPutSanJiaos(BackObj->getTriangles(),BackObj->getN());
cout<<"×××××××××××三角形集合的前后分类结束×××××××××"<<endl<<endl;
// BSPNode *front=new BSPNode(*FrontObj);
// BSPNode *back=new BSPNode(*BackObj);
//构造叶子节点：
pFrontChild=new BSPNode();
pBackChild=new BSPNode();
((BSPNode*)pFrontChild)->IsLeaf=true;
((BSPNode*)pBackChild)->IsLeaf=true;
((BSPNode*)pFrontChild)->addObject(*FrontObj);
((BSPNode*)pBackChild)->addObject(*BackObj);
delete[] BackObj;
delete[] FrontObj;
//把自己提升为节点
SetAsNode(TheDividerList.at(index));
IsLeaf=false;
}
}
};
class BSPTree{
public:
BSPTree(){
pTree=new BSPNode();
}
BSPNode* pTree;
void addObject(TheTreeObect obj){
pTree->addObject(obj);
}
};
//....
class nearestobject{
private:
bool IsInited;
static nearestobject* const theOnlyOne;
int index;
float nearpoint[3];
float point[3];
float nearestDistance;
nearestobject():IsInited(false),index(0),nearestDistance(0.0){
point[0]=0.0;
point[1]=0.0;
point[2]=0.0;
}
void setLookPoint(float nearpoint[3]){
this->nearpoint[0]=nearpoint[0];
this->nearpoint[1]=nearpoint[1];
this->nearpoint[2]=nearpoint[2];
}
void VectBinus(float a[3],float b[3],float c[3]){
c[0]=a[0]-b[0];
c[1]=a[1]-b[1];
c[2]=a[2]-b[2];
}
//计算模
double calMole(float a[3]){
return sqrt(a[0]*a[0]+a[1]*a[1]+a[2]*a[2]);
}
public:
static nearestobject* GetNearestP(){
return theOnlyOne;
}
//初始化一个近裁剪面点，一个线上的点，以及点对应物体的index;
//返回：是否已经被初始化过
bool Init(float nearpoint[3],float farpoint[3]){
if(!IsInited){
setLookPoint(nearpoint);
for(int i=0;i<3;i++)
{
this->point[i]=point[i];
}
this->index=index;
this->IsInited=true;
float temp[3];
VectBinus(farpoint,nearpoint,temp);
this->nearestDistance=calMole(temp);
return false;
}
return true;
}
int getIndex(){
return index;
}
//返回：以前的物体编号。
int set(int index,float point[3]){
int tempindex;
tempindex=this->index;
double distance;
float temp[3];
VectBinus(point,nearpoint,temp);
distance=calMole(temp);
if((distance-nearestDistance)<-0.000001)
{
nearestDistance=distance;
this->index=index;
}
return tempindex;
}
};
nearestobject* const nearestobject::theOnlyOne=new nearestobject();
//定义射线求交用的变量，这些变量用来进行拾取
float org[3],dir[3],a[3],b[3],c[3],point[3],end[3];
bool IsFromFront;
bool calculateInterWithTriangle(float a[3],float b[3],float c[3]){
return IsIntersectWithTriangle(org,dir,a,b,c,point,IsFromFront);
}
OpenGL::OpenGL()
{
}
OpenGL::~OpenGL()
{ CleanUp();
}
BOOL OpenGL::SetupPixelFormat(HDC hDC0)//检测安装OpenGL
{ int nPixelFormat; // 象素点格式
hDC=hDC0;
PIXELFORMATDESCRIPTOR pfd = {
sizeof(PIXELFORMATDESCRIPTOR), // pfd结构的大小
1, // 版本号
PFD_DRAW_TO_WINDOW | // 支持在窗口中绘图
PFD_SUPPORT_OPENGL | // 支持 OpenGL
PFD_DOUBLEBUFFER, // 双缓存模式
PFD_TYPE_RGBA, // RGBA 颜色模式
16, // 24 位颜色深度
0, 0, 0, 0, 0, 0, // 忽略颜色位
0, // 没有非透明度缓存
0, // 忽略移位位
0, // 无累加缓存
0, 0, 0, 0, // 忽略累加位
16, // 32 位深度缓存
0, // 无模板缓存
0, // 无辅助缓存
PFD_MAIN_PLANE, // 主层
0, // 保留
0, 0, 0 // 忽略层,可见性和损毁掩模
};
if (!(nPixelFormat = ChoosePixelFormat(hDC, &pfd)))
{ MessageBox(NULL,"没找到合适的显示模式","Error",MB_OK|MB_ICONEXCLAMATION);
return FALSE;
}
SetPixelFormat(hDC,nPixelFormat,&pfd);//设置当前设备的像素点格式
//利用hDC创造hRC,这句话使得windows设备句柄转化为opengl支持的设备句柄。
hRC = wglCreateContext(hDC); //获取渲染描述句柄
//得到hRC后，我们激活它，，让它与当前的hDC相关联。
wglMakeCurrent(hDC, hRC); //激活渲染描述句柄
cout<<"Init"<<endl;
// m_baiscobj=new baiscobj();
// m_baiscobj->light0();
return TRUE;
}
extern int k;
void OpenGL::init(int Width, int Height)
{
glViewport(0,0,Width,Height); // 设置OpenGL视口大小。
glMatrixMode(GL_PROJECTION); // 设置当前矩阵为投影矩阵。
glLoadIdentity(); // 重置当前指定的矩阵为单位矩阵
gluPerspective // 设置透视图
( 90.0f, // 透视角设置为 45 度
(GLfloat)Width/(GLfloat)Height, // 窗口的宽与高比
0.1f, // 视野透视深度:近点1.0f
3000.0f // 视野透视深度:始点0.1f远点1000.0f
);
// 这和照象机很类似，第一个参数设置镜头广角度，第二个参数是长宽比，后面是远近剪切。
glMatrixMode(GL_MODELVIEW); // 设置当前矩阵为模型视图矩阵
//glLoadIdentity(); // 重置当前指定的矩阵为单位矩阵
//====================================================
}
struct point3f//定义一个三维变量结构
{double x;
double y;
double z;
};
#define MAP_W 32 // size of map along x-axis 32
#define MAP_SCALE 24.0f // the scale of the terrain map
#define MAP MAP_W*MAP_SCALE/2
point3f n_vector;
// float xyz[3];
float nimh=0,sx,sz; //上一次3D鼠
void picter(float x,float y,float z);
double modelview[16]; // 定义保存视图矩阵数组
double projection[16]; // 定义保存投影矩阵数组
int viewport[4]={0,0,800,600}; // 定义保存屏幕尺寸数组
POINT mouse;
point3f nearPoint;
point3f farPoint;
point3f xyz;
#define FRAND (((float)rand()-(float)rand())/RAND_MAX)
void OpenGL::Render()//OpenGL图形处理
{
GetCursorPos(&mouse);
ScreenToClient(hWnd,&mouse);
//下面对鼠标位置进行编程。
//首先转化为opengl的视口坐标,视口坐标实际上就是窗口坐标，因为前面已经设定。
//下面把屏幕坐标转Opengl坐标：
mouse.x=mouse.x,
mouse.y=Height-mouse.y;
//cout<<mouse.x<<endl;
//cout<<mouse.y;
// cout<<mouse.x<<" "<<mouse.y<<endl;
//下面把屏幕坐标转化为3D坐标
glGetDoublev(GL_MODELVIEW_MATRIX,modelview); // 获取视图矩阵
glGetDoublev(GL_PROJECTION_MATRIX,projection); // 获取投影矩阵
glGetIntegerv(GL_VIEWPORT,viewport); // 获取视口大小
gluUnProject( (double)mouse.x, // 窗口坐标X
(double)mouse.y, // 窗口坐标Y
0.0f, // 获取近裁剪面上的交点
modelview, // 视图矩阵
projection, // 投影矩阵
viewport, // 屏幕视区
&nearPoint.x, // 获得的近点3D坐标值X
&nearPoint.y, // 获得的近点3D坐标值Y
&nearPoint.z // 获得的近点3D坐标值Z
);
gluUnProject( (double)mouse.x, // 窗口坐标X
(double)mouse.y, // 窗口坐标Y
1.0f, // 获取近裁剪面上的交点
modelview, // 视图矩阵
projection, // 投影矩阵
viewport, // 屏幕视区
&farPoint.x, // 获得的近点3D坐标值X
&farPoint.y, // 获得的近点3D坐标值Y
&farPoint.z // 获得的近点3D坐标值Z
);
//Lbutdown=false;
dir[0]=n_vector.x=farPoint.x-nearPoint.x;
dir[1]=n_vector.y=farPoint.y-nearPoint.y;
dir[2]=n_vector.z=farPoint.z-nearPoint.z;
org[0]=nearPoint.x;
org[1]=nearPoint.y;
org[2]=nearPoint.z;
end[0]=farPoint.x;
end[1]=farPoint.y;
end[2]=farPoint.z;
IsFromFront=false;
nearestobject* pNearest=nearestobject::GetNearestP();
pNearest->Init(org,end);
/*
for(int i=0;i<N;i++)
{
int n_triangle;
Triangle* p_nTriangle=object[i].getTriangles(n_triangle);
for(int i=0;i<n_triangle;i++)
Triangle[i].get(a,b,c);
calculateInterWithTriangle(,b,c);
}
*/
glClearColor(0.50f, 0.70f, 0.90f, 1.0f); // 设置刷新背景色
glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT);// 刷新背景
// glLoadIdentity();
// 重置当前的模型观察矩阵
glPushMatrix();//压入堆栈
glEnable(GL_DEPTH_TEST);
glDisable(GL_TEXTURE_2D);
picter(-15,-25,-40);// 更新窗口
glEnable(GL_TEXTURE_2D); //使用纹理
glTranslatef(0,0,-280);
glBindTexture(GL_TEXTURE_2D, m_ID);//
glTexParameterf( GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST );
glTexParameterf( GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST );
glBegin(GL_QUADS);
glTexCoord2f(0.0f, 0.0f); glVertex3f(-Width/2, -Height/2, 0.0f);// 前
glTexCoord2f(1.0f, 0.0f); glVertex3f( Width/2,-Height/2, 0.0f);
glTexCoord2f(1.0f, 1.0f); glVertex3f( Width/2, Height/2, 0.0f);
glTexCoord2f(0.0f, 1.0f); glVertex3f(-Width/2, Height/2, 0.0f);
glEnd();
glPopMatrix();
glFlush();
SwapBuffers(hDC); // 切换缓冲区
}
void OpenGL::CleanUp()
{ wglMakeCurrent(hDC, NULL); //清除OpenGL
wglDeleteContext(hRC); //清除OpenGL
}
float r=0;
void picter(float x,float y,float z)//组合图形
{
glPushAttrib(GL_CURRENT_BIT);//保存现有颜色属实性
glPushMatrix();//平台-==============================
glTranslatef(0,0,-30); //平台的定位
BSPTree* myTree=new BSPTree();
//TheTreeObect(float *triangle[3][3],int n1)
float triangle [2][3][3];
triangle[0][0][0]=0;
triangle[0][0][1]=0;
triangle[0][0][2]=0;
triangle[0][1][0]=0;
triangle[0][1][1]=1;
triangle[0][1][2]=0;
triangle[0][2][0]=0;
triangle[0][2][1]=0;
triangle[0][2][2]=1;
triangle[1][0][0]=1;
triangle[1][0][1]=0;
triangle[1][0][2]=0;
triangle[1][1][0]=0;
triangle[1][1][1]=1;
triangle[1][1][2]=0;
triangle[1][2][0]=-1;
triangle[1][2][1]=0;
triangle[1][2][2]=0;
/* for(int i=0;i<2;i++)
{
triangle[i][0][0]=i+0;
triangle[i][0][1]=i+0;
triangle[i][0][2]=i+0;
triangle[i][1][0]=i+0;
triangle[i][1][1]=i+1;
triangle[i][1][2]=i+0;
triangle[i][2][0]=i+0;
triangle[i][2][1]=i+0;
triangle[i][2][2]=i+1;
}
*/
TheTreeObect* obj=new TheTreeObect(triangle,2);
for(int i=0;i<obj->getN();i++)
{
cout<<obj->getTriangles()[i].a[0]<<" ";
cout<<obj->getTriangles()[i].a[1]<<" ";
cout<<obj->getTriangles()[i].a[2]<<" "<<endl;
cout<<obj->getTriangles()[i].b[0]<<" ";
cout<<obj->getTriangles()[i].b[1]<<" ";
cout<<obj->getTriangles()[i].b[2]<<" "<<endl;
cout<<obj->getTriangles()[i].c[0]<<" ";
cout<<obj->getTriangles()[i].c[1]<<" ";
cout<<obj->getTriangles()[i].c[2]<<" "<<endl;
}
myTree->addObject(*obj);
delete [] obj;
glPopMatrix();
glPushMatrix();//平台-==============================
glTranslatef(x,y+0.5f,z); //平台的定位
glColor3f(0.0f,1.0f,0.2f); //绿色
auxSolidCube(1); //方台(边长)
glTranslatef(0.0f,0.8f,0.0f); //架的位置调整,上升0.8
glColor3f(0.0f,0.0f,1.0f); //蓝色
auxSolidBox(.2f,1.3f,.2f); //长方架(宽、高、长)
glPopMatrix();
glPushMatrix();//雷达==============================
glTranslatef(x,y+2.5f,z); //雷达的定位1
glRotatef(r-90,0.0,1.0,0.0); //雷达旋转2
//=======================================
glColor3f(1.0f,1.0f,1.0f); //白色
glRotatef(45, 1.0, 0.0, 0.0); //盘的角度调整，仰30度
auxWireCone(1.5,0.6f); //线园锥盘(底半径、高)
//=======================================
glRotatef(180, 1.0, 0.0, 0.0); //杆的角度调整,反方向转
glTranslatef(0.0f,0.0f,-0.7f); //杆的位置调整,缩进一点
auxWireCone(0.2f,2.0f); //园锥杆(底半径、高)
glColor3f(FRAND,0,0); //随机红色
glTranslatef(0.0f,0.0f,2.0f); //杆的位置调整,缩进一点
auxSolidSphere(0.1f); //园(半径)
glPopMatrix();
glPushMatrix();//火箭=============================
glTranslatef(x,y+10.0f,z); //火箭的定位
glRotatef(r, 0.0, 1.0, 0.0); //火箭的旋转
glTranslatef(15,0,0); //火箭的定位
//=============================================
glColor3f(1.0f,0.0f,0.0f); //红色
glRotatef(180, 0.0, 1.0, 0.0); //角度调整,与雷达平行，箭头朝前
auxSolidCone(.2,0.6); //园锥(底半径、高)
//=============================================
glColor3f(1.0f,1.0f,1.0f); //白色
glRotatef(90, 1.0, 0.0, 0.0); //角度调整,与火箭头对接
glTranslatef(0.0f,-1.0f,0); //位置调整,与火箭头对接
auxSolidCylinder(.2f,1); //园柱(半径、高)
glRotatef(-270, 1.0, 0.0, 0.0);
glColor3f(FRAND+.6f,0.2f,0.0f); //随机色
glTranslatef(0.0f,-0.0f,-0.2f); //位置调整,缩进一点
auxSolidCone(.2,1.5); //园锥(底半径、高)
glPopMatrix();
glPopAttrib();//恢复前一属性
r+=0.5f;if(r>360) r=0;
}
//定义屏幕拾取要用的变量。
//计算射线与平面交点的函数
/*
bool calInsert(float org[3],float dir[3],float flat[4],float intersection[3]){
float xishu[3][4];
//第一行
//x=nearPoint.x+n_vector.x*(y-nearPoint.y)/(farPoint.y-nearPoint.y);
//z=nearPoint.z+n_vector.z*(y-nearPoint.y)/(farPoint.y-nearPoint.y);
xishu[0][0]=1;
xishu[0][1]=-dir[0]/dir[1];
xishu[0][2]=0;
xishu[0][3]=org[0]-dir[0]*org[1]/dir[1];
//第二行
xishu[1][0]=0;
xishu[1][1]=-dir[2]/dir[1];
xishu[1][2]=1;
xishu[1][3]=org[2]-dir[2]*org[1]/dir[1];
//第三行是一个平面方程。。
//
//假设系数为a,b,c,常量为d
//
//float a ,b ,c, d;
xishu[2][0]=flat[0];
xishu[2][1]=flat[1];
xishu[2][2]=flat[2];
xishu[2][3]=flat[3];
jieXianXingFangCheng(xishu,intersection);
}
//下面的代码判断，平面上，一个点是否在三角形内。
//思路是求面积。面积之和是否与三角形相等。
//要用到求叉积
bool IsInTriangle(float a[3],float b[3],float c[3],float point[3]){
}
*/
算法总结一下：
分割算法：
原来的算法：直接在各个边上假设一个交点，使其变为6个点的6边形。然后从中剔除不构成三角形的顶点序列。
优点：算法只要求4个叉积，就可以得到结果。
缺点：不支持多边形分割。
新的算法： 在各个边上求交点。构成一个顶点的循环序列。（可以用+1取余法得到下一个）
位于序列V1，V2之间的构成一个多边形。从v2到v1构成另外一个多边形。
然后根据多边形的边数，将其分解为三角形，如何将多边形转化为三角形，最简单的莫过于，直接拿其中 一 点 ， 链接各个边。
优点：更快！不过我还没实现这个算法。
原来的算法的改进思路：因为求叉积时间很慢。要算n多乘法：
叉积无非就是用来判断是否在构成三角形。我们现在直接观察。。首先：三个交点肯定能构成三角形，不论移到什么位置。
而对于顶点来说，如果它相邻边上的交点都不存在，也不构成三角形。
因此。。。。行动起来。。。
位置判断算法：
1.如果共面，则判断是否同向。
2.如果不共面，转3
3.如果所有的点都不为FRONT，则在后面。
4.else 如果所有的点都不为BACK,则前面
5。如果上述两项都不成立，则为分割。
#include "stdafx.h"
#include "OpenGL.h"
#include "Map.h"
#include "math.h"
#include "ArrayInterTriangle.h"
#include <iostream.h>
#include <stdio.h>
#include <bitset>
extern unsigned int m_ID;
#include <math.h>
#include<stdexcept>
#include<time.h>
extern bool Lbutdown; // 鼠标左键
extern bool Rbutdown; // 鼠标左键
//////////////////////////////////////////////////////////////////////
extern HWND hWnd;
//定义最近的距离视点最近的鼠标物体：
//定义一个结构来保存所有的物体：
#include<list>
int TreeDepth=0;
#include<vector>
using std::bitset;
using std::list;
using std::vector;
using std::runtime_error;
using std::length_error;
vector<int> TheDividerList;
class Triangle{
public:
float a[3];
float b[3];
float c[3];
};
class TheTreeObect{
int maxlen;
int n;
//定义当前分割平面的索引。
int currentFlip;
Triangle *Triangles;
public:
void SetAsNode(int currentFlip){
Triangle temp=Triangles[currentFlip];
delete [] Triangles;
Triangles=new Triangle(temp);
}
void deleteALL(){
delete[] Triangles;
Triangles=NULL;
n=0;
}
void resetTriangle(Triangle *Triangles,int n){
delete[] this->Triangles;
this->Triangles=Triangles;
this->n=n;
this->maxlen=n;
}
TheTreeObect(){
Triangles= new Triangle[10];
maxlen=10;
n=0;
}
int add(Triangle triangle)
{
if(n==maxlen){
Triangle* temp=Triangles;
Triangles=new Triangle[n+10];
for(int i=0;i<n;i++){
for(int j=0;j<3;j++){
Triangles[i].a[j]=temp[i].a[j];
Triangles[i].b[j]=temp[i].b[j];
Triangles[i].c[j]=temp[i].c[j];
}
}
delete [] temp;
}
for(int j=0;j<3;j++){
Triangles[n].a[j]=triangle.a[j];
Triangles[n].b[j]=triangle.b[j];
Triangles[n].c[j]=triangle.c[j];
}
n++;
return n;
}
int getFlip(){
return currentFlip;
}
int getN(){
return n;
}
Triangle *getTriangles()
{
return Triangles;
}
TheTreeObect(float (*triangle)[3][3],int n1)
{
Triangles= new Triangle[n1];
n=n1;
for(int i=0;i<n;i++){
for(int j=0;j<3;j++){
//第二维表示点的索引，第三维表示，xyz坐标
Triangles[i].a[j]=triangle[i][0][j];
Triangles[i].b[j]=triangle[i][1][j];
Triangles[i].c[j]=triangle[i][2][j];
}
}
}
};
//而叉树节点是一个特殊的物体。。它只有一个平面。
class BSPNode:public TheTreeObect{
public:
BSPNode(){
IsLeaf=true;
}
//是否为分割面。或是是物体，或者是分割面。
bool IsLeaf;
bool IsWithObject;
void setIsWithObject(bool is)
{
IsWithObject=is;
}
BSPNode(TheTreeObect& obj):TheTreeObect(obj){
}
void set(bool Front)
{
IsFront=Front;
}
bool IsNode;
bool IsFront;
TheTreeObect* pBackChild;
TheTreeObect* pFrontChild;
//查看物体的第index个三角形是否与既定面共面。
void outPutSanjiao(Triangle triangle)
{
float *a=triangle.a;
float a0=a[0];
float a1=a[1];
float a2=a[2];
cout<<endl<<a0<<" "<<a1<<" "<<a2<<" "<<endl;
float *b=triangle.b;
float b0=b[0];
float b1=b[1];
float b2=b[2];
cout<<b0<<" "<<b1<<" "<<b2<<" "<<endl;
float *c=triangle.c;
float c0=c[0];
float c1=c[1];
float c2=c[2];
cout<<c0<<" "<<c1<<" "<<c2<<" "<<endl;
}
void outPutSanJiaos(Triangle* pTriangle,int n)
{
for(int i=0;i<n;i++)
{
outPutSanjiao(pTriangle[i]);
}
}
void outPutVector(char *p,float *pf,int n)
{
for(int j=0;p[j]!='\0';p++)
{
cout<<p[j];
}
cout<<":"<<endl;
for(int i=0;i<n;i++)
{
cout<<pf[i]<<endl;
}
}
//函数功能：判断一个三角形来自另外一个三角形所在平面的何方。
//功能描述：如果共面，则same为true，divided为false,方向相同则返回true,否则返回false;
// 如果不共面，则根据在前还是后，还是divided ,进行返回。
bool IsFomFront(TheTreeObect obj,int index,int currentFlip,bool &same,bool &divied){
divied=false;
same=false;
bitset<3> position[3];
float dir[3];
bool Front[3];
bool IsNotInFlat[3];
float point[3];
memcpy(point,obj.getTriangles()[index].a,3*sizeof(float));
//int currentFlip=getFlip();
VectBinus(obj.getTriangles()[currentFlip].a,point,dir);
outPutVector("射线原点",point,3);
outPutVector("射线终点",obj.getTriangles()[currentFlip].a,3);
outPutVector("射线方向",dir,3);
IsNotInFlat[0]=IsIntersectWithTriangle(
point,
dir,
obj.getTriangles()[currentFlip].a,
obj.getTriangles()[currentFlip].b,
obj.getTriangles()[currentFlip].c,
point,
Front[0]
);
cout<<"********************开始射线检测****************************************"<<endl;
cout<<"分割面为"<<endl;
outPutSanjiao(obj.getTriangles()[currentFlip]);
if(!IsNotInFlat[0])cout<<"射线在平面上"<<endl;
else if(Front[0])cout<<"射线从前方穿过"<<endl;
else cout<<"射线从后方穿过"<<endl;
cout<<"********************检测结束****************************************"<<endl;
memcpy(point,obj.getTriangles()[index].b,3*sizeof(float));
VectBinus(obj.getTriangles()[currentFlip].b,point,dir);
IsNotInFlat[1]=IsIntersectWithTriangle(
point,
dir,
obj.getTriangles()[currentFlip].a,
obj.getTriangles()[currentFlip].b,
obj.getTriangles()[currentFlip].c,
point,
Front[1]
);
cout<<"********************开始射线检测****************************************"<<endl;
outPutVector("射线原点",point,3);
outPutVector("射线方向",dir,3);
cout<<"分割面为"<<endl;
outPutSanjiao(obj.getTriangles()[currentFlip]);
if(!IsNotInFlat[1])cout<<"射线在平面上"<<endl;
else if(Front[1])cout<<"射线从前方穿过"<<endl;
else cout<<"射线从后方穿过"<<endl;
cout<<"********************检测结束****************************************"<<endl;
memcpy(point,obj.getTriangles()[index].c,3*sizeof(float));
VectBinus(obj.getTriangles()[currentFlip].c,point,dir);
IsNotInFlat[2]=IsIntersectWithTriangle(
point,
dir,
obj.getTriangles()[currentFlip].a,
obj.getTriangles()[currentFlip].b,
obj.getTriangles()[currentFlip].c,
point,
Front[2]
);
cout<<"********************开始射线检测****************************************"<<endl;
outPutVector("射线原点",point,3);
outPutVector("射线方向",dir,3);
cout<<"分割面为"<<endl;
outPutSanjiao(obj.getTriangles()[currentFlip]);
if(!IsNotInFlat[2])cout<<"射线在平面上"<<endl;
else if(Front[2])cout<<"射线从前方穿过"<<endl;
else cout<<"射线从后方穿过"<<endl;
cout<<"********************检测结束****************************************"<<endl;
for(int i=0;i<3;i++)
{
if(!IsNotInFlat[i])position[i].set(0);else
if(Front[i])position[i].set(1);else
position[i].set(2);
}
for(i=0;i<3;i++)
{
cout<<"i:顶点"<<i<<endl;
cout<<position[i][0];
cout<<position[i][1];
cout<<position[i][2];
}
//每个点的三个状态对应为 position[0],position[1],position[2];
bitset<3> positi=position[0]&position[1]&position[2];
for(i=0;i<3;i++)
{
cout<<"综合：";
cout<<positi[i]<<endl;
}
//查看是否共面
//分析结果为:
cout<<"经过分析，三角形与平面的关系为："<<endl;
if(positi[0])
{ cout<<"这是一个相同的平面"<<endl;
same=true;
//查看方向是否相同
//求得他们的发线：
float flat_3_flip[3];
float flat_3_temp[3];
qiuFaXiangLiang(
getTriangles()[currentFlip].a,
getTriangles()[currentFlip].b,
getTriangles()[currentFlip].c,
flat_3_flip);
qiuFaXiangLiang(
getTriangles()[index].a,
getTriangles()[index].b,
getTriangles()[index].c,
flat_3_temp);
float dotval=DotProduct(flat_3_flip,flat_3_temp);
if(dotval<0){
//点积为负值
return false;
}else
//点积为正值
return true;
}else {
positi=position[0]|position[1]|position[2];
//不共面并且没有在后面的点！！
if(!positi[2])
{
cout<<"前面"<<endl;
return true;
}
//不共面没有前面的点
else if(!positi[1])
{
cout<<"后面"<<endl;
return false;
}else
{
//不共面，既有前面的点，也有后面的点。
cout<<"被分割的面"<<endl;
divied=true;
return false;
}
}
}
//函数功能：从所有的备选三角形列表中找到一个最佳的分割平面。
int getTheBestDivider(vector<int> TheDividerList,bool &found, TheTreeObect obj){
cout<<"×××××××××寻找最佳分割面开始××××××××××××××"<<endl;
cout<<"当前的树深为"<<endl;
cout<<TreeDepth<<endl;
cout<<"要检测的三角集合为："<<endl;
outPutSanJiaos(obj.getTriangles(),obj.getN());
//定义评估数组
int *pingguvalue=new int[TheDividerList.size()];
//是否找到
found=false;
//定义最佳评估值
int theOptimizedValue;
//最佳的评估值对应的三角形编号(对应于theDividerList)
int theOpTriagl;
//评估值是否初始化
bool IsInit=false;
//判断是否为凸空间，默认为凸
bool AllFront=true;
bool AllBack=true;
for(int flip=0;flip<TheDividerList.size();flip++){
cout<<"-------------------第"<<flip<<"个分割面评估值检测开始-------------------"<<endl;
cout<<"第"<<flip<<"个待定分割面为"<<endl;
cout<<"第"<<TheDividerList[flip]<<"个三角形"<<endl;
outPutSanjiao(obj.getTriangles()[TheDividerList[flip]]);
int N_FRONT=0;
int N_BACK=0;
int N_DIVIDE=0;
if(
!IsTriangle(
obj.getTriangles()[TheDividerList[flip]].a,
obj.getTriangles()[TheDividerList[flip]].b,
obj.getTriangles()[TheDividerList[flip]].c
)
)
{
cout<<"它不是一个平面！"<<endl;
continue;
}else
{
cout<<"它是一个平面！"<<endl;
}
for(int index=0;index<obj.getN();index++){
bool front;
bool same;
bool divided;
front=IsFomFront(obj,index,flip,same,divided);
if(divided){
N_DIVIDE++;
AllBack=false;
AllFront=false;
}
else if(front){
AllBack=false;
N_FRONT++;
}else {
N_BACK++;
AllFront=false;
}
}
//不是所有的平面都在后面，也不是都在前面
if(!AllBack&&!AllFront){
cout<<"找到了这样的平面";
found=true;
}
else{
cout<<"没有找到！";
found=false;
}
cout<<"在它前面的三角形个数为"<<N_FRONT<<endl;
cout<<"在它后面的三角形个数为"<<N_BACK<<endl;
cout<<"被它分割的三角形个数为"<<N_DIVIDE<<endl;
//说明需要可以找到这样的分割面
//found=true;
pinggu_value[flip]=fabs(N_FRONT-N_BACK)+N_DIVIDE;
cout<<"评估值为"<<pinggu_value[flip]<<endl;
if(!IsInit){
theOpTriagl=flip;
theOptimizedValue=pinggu_value[flip];
IsInit=true;
}
//没有初始化并且小于目前的评估值
else if(pinggu_value[flip]<theOptimizedValue){
theOpTriagl=flip;
theOptimizedValue=pinggu_value[flip];
}
cout<<"评估结果为："<<endl;
cout<<"树深为"<<endl;
cout<<TreeDepth<<endl;
cout<<"要检测的三角集合为："<<endl;
outPutSanJiaos(obj.getTriangles(),obj.getN());
if(AllBack){
cout<<"它在所有平面的后面"<<endl;
}
else if(AllFront){
cout<<"它在所有平面的前面"<<endl;
}
else cout<<"一些在它前面，一些在它后面"<<endl;
cout<<"当前的最佳评估值为"<<endl;
cout<< theOptimizedValue<<endl;
cout<<"当前的最佳分割面为"<<endl;
cout<<theOpTriagl<<endl;
outPutSanjiao(obj.getTriangles()[TheDividerList[theOpTriagl]]);
cout<<"-------------------第"<<flip<<"个分割面评估值检测结束-------------------"<<endl;
}
Triangle thetri=obj.getTriangles()[theOpTriagl];
glBegin(GL_TRIANGLES);
glColor3f(1.0,0.0,0.0);
glVertex3f(thetri.a[0],thetri.a[1],thetri.a[2]);
glVertex3f(thetri.b[0],thetri.b[1],thetri.b[2]);
glVertex3f(thetri.c[0],thetri.c[1],thetri.c[2]);
glEnd();
return theOpTriagl;
cout<<"×××××××××寻找最佳分割面结束××××××××××××××"<<endl;
}
//参数：triangle：待分割的三角形
//divider: 分割面
//pTri:分割后的三角形
//p_front:前，还是后
//返回：分割后的三角形个数
int divideTriangle(Triangle triangle,Triangle divider,Triangle* &pTri,bool *& p_front){
float flat[4];
bool insectFlag[3];
float AB_INSECT[3];
float BC_INSECT[3];
float CA_INSECT[3];
float AB[3],BC[3],CA[3];
for(int i=0;i<3;i++)
{
AB[i]=triangle.b[i]-triangle.a[i];
BC[i]=triangle.c[i]-triangle.b[i];
CA[i]=triangle.a[i]-triangle.c[i];
}
//求得分割面的方程系数,返回-1表示方程不存在
cout<<"*******************求解平面方程开始*******************"<<endl;
outPutVector("A",divider.a,3);
outPutVector("B",divider.b,3);
outPutVector("C",divider.c,3);
if(!qiuPingMianFangCheng(divider.a,divider.b,divider.c,flat))
{
cout<<"没找到平面方程！"<<endl;
return -1;
}
cout<<"**********************求解平面方程结束****************"<<endl;
cout<<"分解面为："<<endl;
outPutSanjiao(divider);
cout<<"待分解的三角为："<<endl;
outPutSanjiao(triangle);
//第一步:求直线与平面的交点
calInsert(triangle.a,AB,flat,AB_INSECT);
//第二部：看这个交点在不在线段内。
float v1[3];
float v2[3];
VectBinus(triangle.a,AB_INSECT,v1);
VectBinus(triangle.b,AB_INSECT,v2);
float dot=DotProduct(v1,v2);
if(dot>0||dot==0)insectFlag[2]=true;
else
{
insectFlag[2]=false;
for(int m=0;m<3;m++)
AB_INSECT[m]=triangle.a[m];
}
cout<<"经过计算发现与AB边的交点为：";
for(i=0;i<3;i++){
cout<<AB_INSECT[i];
}
//第一步:求直线与平面的交点
calInsert(triangle.b,BC,flat,BC_INSECT);
//第二部：看这个交点在不在线段内。
VectBinus(triangle.b,BC_INSECT,v1);
VectBinus(triangle.c,BC_INSECT,v2);
dot=DotProduct(v1,v2);
if(dot>0||dot==0)insectFlag[0]=true;
else
{
insectFlag[0]=false;
for(int m=0;m<3;m++)
BC_INSECT[m]=triangle.b[m];
}
cout<<"经过计算发现与BC边的交点为：";
for(i=0;i<3;i++){
cout<<BC_INSECT[i];
}
//第一步:求直线与平面的交点
calInsert(triangle.c,CA,flat,CA_INSECT);
//第二部：看这个交点在不在线段内。
VectBinus(triangle.c,CA_INSECT,v1);
VectBinus(triangle.a,CA_INSECT,v2);
dot=DotProduct(v1,v2);
if(dot>0||dot==0)
{
insectFlag[1]=true;
}
else
{
insectFlag[1]=false;
for(int m=0;m<3;m++)
CA_INSECT[i]=triangle.c[i];
}
cout<<"经过计算发现与CA边的交点为：";
for(i=0;i<3;i++){
cout<<CA_INSECT[i];
}
//先给这些边编号：
float *jiaodian[3];
jiaodian[0]=BC_INSECT;
jiaodian[1]=CA_INSECT;
jiaodian[2]=AB_INSECT;
float *Bian[3];
Bian[0]=BC;
Bian[1]=CA;
Bian[2]=AB;
float *dingdian[3];
dingdian[0]=triangle.a;
dingdian[1]=triangle.b;
dingdian[2]=triangle.c;
float *sanjiaoxing[3][3];
//分解后的三角形个数
for(int k=0;k<3;k++)
{
sanjiaoxing[k][0]=dingdian[k];
sanjiaoxing[k][1]=jiaodian[(k-1+3)%3];
sanjiaoxing[k][2]=jiaodian[(k+1+3)%3];
}
pTri=new Triangle[4];
//下面遍历这些假三角，有些是不存在的
for(int ki=0;ki<3;ki++)
{
cout<<"三角形"<<ki<<"为："<<endl;
for(k=0;k<3;k++){
cout<<sanjiaoxing[ki][k][0]<<" ";
cout<<sanjiaoxing[ki][k][1]<<" ";
cout<<sanjiaoxing[ki][k][2]<<" ";
}
}
int n=0;
for(i=0;i<3;i++)
{
if(IsTriangle(sanjiaoxing[i][0],sanjiaoxing[i][1],sanjiaoxing[i][2]))
{
for(k=0;k<3;k++){
pTri[n].a[k]=sanjiaoxing[i][0][k];
pTri[n].b[k]=sanjiaoxing[i][1][k];
pTri[n].
分享到：
发表评论
相关推荐
通过画一个多边形，然后在多边形内外任意位置点一些点，就可以判断点与多边形的位置关系。
判断点在多边形内，射线和多边形算出奇数个交点，在多边形内
本程序主要是判断点与多边形间的关系，在多边形内还是在多边形外。
MFC单文档。程序包括画多边形，多边形的各边不会相交，然后判断选点与多边形的关系。
可以支持所有的多边形情况
判断一个点与多边形的位置关系，这里主要判断内部与外部
写一个C++程序，计算两个多边形的重叠面积 多边形class定义如下： class Polygon { public: Polygon(float* polygon, int vertex) : polygon(polygon), vertex(vertex) {}; private: float* polygon; // 坐标形式...
用射线法判断点是否在多边形中，编译环境VC6.0，鼠标左键实现绘制多边形，右键进行判断。
判断点和多边形的位置，判断点和多边形的位置，判断点和多边形的位置
从而得出了一个简单的点与有向线段之间关系的 判别式 , 并在此基础上根据凸凹点的性质及有向多边形的性质提出了不用解任何方程组也不用计 算三角函数的判定平面多边形的简单性 、 方向及内外点的简单 、 强健而高效...
求解任意两个多边形的并集，交集，差集，要求是简单多边形，可以是凸多边形和凹多边形
判断点在多边形内的函数
点与多边形位置判断程序C#
java 判断点在多边形内 java 判断点在多边形内 java 判断点在多边形内 java 判断点在多边形内 java 判断点在多边形内 Java GIS 多边形 Java点多边形
判断点与多边形的关系，使用扫描线算法实现。图形界面演示测试结果。 实现语言：Python + wxPython
点是否在多边形内判断的C语言代码，有2维及3维两种情况的判断， 请注意:如果你决定使用其中某个函数，请将它拷出来，每个函数都能用，对应于不同的算法，请看说明，最后一个函数为三维情况。
这个函数有两个参数，第三个是可选的。 P1 & P2 包含多边形的几何形状。 P1 & P2 是包含两个字段的结构：x & y 例如： P1.x = rand(1,5)+2; P1.y = rand(1,5); P2.x = rand(1,3); P2.y = rand(1,3); Display_...
文中对比有关参考文献提出的多边形面积分割算法，以文献[1]提出的二分法为基础，补充了算法关键步骤的公式和计算方法。基于AutoCAD的VBA开发环境，从底层的角度实现了算法，弥补了AutoCAD下缺少多边形面积分割功能的...
确定两个任意简单多边形空间关系的算法，超级好的文章