#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].
