看了何詠的文章（http://www.graphixer.com.cn/ShowWorks.asp?Type=1&ID=28）后，再找到了最原始的那篇論文，也實現了一個，僅僅實現了動態地形優化部分，紋理等其它無關算法的內容沒有加上去。使用OpenGL渲染，即以前做畢業設計時的框架，順便也可以改進一下以前的游戲框架~
這里就不說算法了，讀者可以找找何詠說到的那篇論文，個人覺得主要難點是理解消除裂縫的那部分
首先看效果圖，沒有優化的情況：
啟用算法優化：
不過之前畢業設計的游戲框架做得太爛，很多東西都太死，就不提供出來了，待以后有空好好改進。這里只貼LOD地形類的代碼
.h文件：
1
#pragma once
2
3#include "gmath.h"
4#include "CY_Camera.h"
5
6
7struct lodNode
8
{
9
Index2 Pos;//節點坐標（第x行y列;即對PointArray的索引）
10 int halfRange;//覆蓋半徑
11
12 float BoundRadius; //包圍球半徑
13 float DeltaH; //節點誤差值
14
15 //四個子節點
16 lodNode* LeftUp;
17 lodNode* RightUp;
18 lodNode* LeftDown;
19 lodNode* RightDown;
20
21 //
22 lodNode()
23
{
24 LeftUp=0;
25 RightUp=0;
26 LeftDown=0;
27 RightDown=0;
28
29 halfRange=0;
30 BoundRadius=0;
31
}
32 ~lodNode()
33 {
34 if(LeftUp)delete LeftUp;
35 if(RightUp)delete RightUp;
36 if(LeftDown)delete LeftDown;
37 if(RightDown)delete RightDown;
38 }
39
};
40class LOD
41{
42 float Xuint;//每個單位像素表示的 寬度
43 float Yuint;//每個單位像素表示的 高度
44 float Zuint;//每個單位alpha表示的深度
45 Vector3 *PointArray;//位置矩陣，x對應w，y對應h，z對應d；
46 bool *NeedSplitArray;
47 int Size;//地形圖尺寸
48 int maxLevel;//樹深度
49
50
51 lodNode *Root;
52 void CaculateRadius(lodNode *t);//處理該節點的包圍球半徑、子節點（初始化層次樹中）
53 float CaculateDeltaH(lodNode *t);//處理該節點的誤差值，返回子節點誤差值
54
55 bool isDone;
56
57 Vector3 *GetPoint(int x,int y);//獲取第y行，第x列
58 bool GetPointMark(int x,int y);
59 void SetPoint(int x,int y,float w,float h,float d);
60 void SetPointMark(int x,int y,bool ismark);
61
62 void RenderNode(lodNode *t,int &TrangleNum);//畫該節點
63 void InitMark();//初始化是否細化的標記
64 bool IsNeedMark(lodNode *t);//節點的子節點是否可以標記細分
65public:
66 LOD();
67 ~LOD();
68 void InitPointArray(int size,BYTE *tgaData,float xuint,float yuint,float zuint);//1、初始化數組
69 void InitLOD(); //2、初始化層次樹
70 void FreeData();
71
72
73 void RenderNoLOD();//無優化的渲染
74 void RenderLOD(CY_Camera *cam);
75
76 int trangleNum;//記錄三角形數
77};
.cpp文件：
1#include "LOD.h"
2#include "GLee.h"
3#include "CY_Camera.h"
4#include "Frustum.h"
5#include "list"
6using namespace std;
7
8const float C_Distan=10.0f;
9const float C_Noise=25.0f;
10
11LOD::LOD()
12{
13 Root=0;
14 PointArray=0;
15 NeedSplitArray=0;
16 isDone=false;
17}
18LOD::~LOD()
19{
20 FreeData();
21}
22void LOD::FreeData()
23{
24 if(isDone)
25 isDone=false;
26 if(PointArray)
27 delete []PointArray;
28 if(NeedSplitArray)
29 delete []NeedSplitArray;
30 NeedSplitArray=0;
31 PointArray=0;
32 if(Root)
33 delete Root;
34 Root=0;
35}
36//---------------------------------------------------------------------------------------
37void LOD::InitPointArray(int size,BYTE *tgaData,float xuint,float yuint,float zuint)
38{
39 Xuint=xuint;
40 Yuint=yuint;
41 Zuint=zuint;
42 Size=size;//地形圖尺寸
43
44 PointArray=new Vector3[Size*Size];
45 for(int i=0;i<Size;++i)
46 for(int j=0;j<Size;++j)
47 {
48 SetPoint(i,j,Xuint*i,Yuint*j,Zuint*tgaData[3+4*(j*Size+i)]);
49 }
50 NeedSplitArray=new bool[Size*Size];
51 InitMark();
52}
53//----------------------------------------------------------------------------------------
54void LOD::CaculateRadius(lodNode *t)//處理該節點的包圍球半徑、子節點（初始化層次樹中）
55{
56 int minX,maxX,minY,maxY;
57 float currentR,MaxR=0;
58 Vector3 *temp;
59 Vector3 *target=GetPoint(t->Pos.x,t->Pos.y);
60
61 //---------------計算包圍球半徑---
62 minX=t->Pos.x-t->halfRange;
63 maxX=t->Pos.x+t->halfRange;
64 minY=t->Pos.y-t->halfRange;
65 maxY=t->Pos.y+t->halfRange;
66 for(int i=minX;i<=maxX;++i)
67 {
68 for(int j=minY;j<=maxY;++j)
69 {
70 temp=GetPoint(i,j);
71 currentR=VectorLength(temp->x-target->x,temp->y-target->y,temp->z-target->z);
72 if(currentR>MaxR)
73 MaxR=currentR;
74 }
75 }
76 t->BoundRadius=MaxR;
77 //-------------------------------------
78 //---------------------------------計算子節點---------------
79 if(t->halfRange<=1)return;
80 lodNode *LU_sub,*LD_sub,*RU_sub,*RD_sub;
81 LU_sub=new lodNode();
82 LU_sub->halfRange=t->halfRange/2;
83 LU_sub->Pos.x=t->Pos.x-LU_sub->halfRange;
84 LU_sub->Pos.y=t->Pos.y-LU_sub->halfRange;
85
86 LD_sub=new lodNode();
87 LD_sub->halfRange=t->halfRange/2;
88 LD_sub->Pos.x=t->Pos.x-LD_sub->halfRange;
89 LD_sub->Pos.y=t->Pos.y+LD_sub->halfRange;
90
91 RU_sub=new lodNode();
92 RU_sub->halfRange=t->halfRange/2;
93 RU_sub->Pos.x=t->Pos.x+RU_sub->halfRange;
94 RU_sub->Pos.y=t->Pos.y-RU_sub->halfRange;
95
96 RD_sub=new lodNode();
97 RD_sub->halfRange=t->halfRange/2;
98 RD_sub->Pos.x=t->Pos.x+RD_sub->halfRange;
99 RD_sub->Pos.y=t->Pos.y+RD_sub->halfRange;
100
101 t->LeftUp=LU_sub;
102 t->LeftDown=LD_sub;
103 t->RightUp=RU_sub;
104 t->RightDown=RD_sub;
105
106 CaculateRadius(LU_sub);
107 CaculateRadius(LD_sub);
108 CaculateRadius(RU_sub);
109 CaculateRadius(RD_sub);
110}
111float LOD::CaculateDeltaH(lodNode *t)//處理該節點的誤差值，子節點誤差值
112{
113 int halfRange=t->halfRange;
114 float nDelta1,nDelta2,nDelta3,nDelta4;//4個邊上的誤差值
115 float maxDelta;
116 Vector3 *node1,*node2,*node3,*node4;//點結點
117 Vector3 *edge1,*edge2,*edge3,*edge4;//邊結點
118 Vector3 temp;//
119
120 node1=GetPoint(t->Pos.x-halfRange,t->Pos.y-halfRange);
121 node2=GetPoint(t->Pos.x+halfRange,t->Pos.y-halfRange);
122 node3=GetPoint(t->Pos.x+halfRange,t->Pos.y+halfRange);
123 node4=GetPoint(t->Pos.x-halfRange,t->Pos.y+halfRange);
124 edge1=GetPoint(t->Pos.x,t->Pos.y-halfRange);
125 edge2=GetPoint(t->Pos.x+halfRange,t->Pos.y);
126 edge3=GetPoint(t->Pos.x,t->Pos.y+halfRange);
127 edge4=GetPoint(t->Pos.x-halfRange,t->Pos.y);
128
129 temp=((*node1)+(*node2))*0.5f;
130 nDelta1=VectorLength(temp-(*edge1));
131 maxDelta=nDelta1;
132 temp=((*node3)+(*node2))*0.5f;
133 nDelta2=VectorLength(temp-(*edge2));
134 if(maxDelta<nDelta2)maxDelta=nDelta2;
135 temp=((*node3)+(*node4))*0.5f;
136 nDelta3=VectorLength(temp-(*edge3));
137 if(maxDelta<nDelta3)maxDelta=nDelta3;
138 temp=((*node1)+(*node4))*0.5f;
139 nDelta4=VectorLength(temp-(*edge4));
140 if(maxDelta<nDelta4)maxDelta=nDelta4;
141
142 if(t->halfRange<=1)
143 {
144 t->DeltaH=maxDelta;
145 return maxDelta;
146 }
147 else
148 {
149 float subMax=CaculateDeltaH(t->LeftUp);
150 if(subMax>maxDelta)
151 maxDelta=subMax;
152 subMax=CaculateDeltaH(t->LeftDown);
153 if(subMax>maxDelta)
154 maxDelta=subMax;
155 subMax=CaculateDeltaH(t->RightUp);
156 if(subMax>maxDelta)
157 maxDelta=subMax;
158 subMax=CaculateDeltaH(t->RightDown);
159 if(subMax>maxDelta)
160 maxDelta=subMax;
161
162 t->DeltaH=maxDelta;
163 return maxDelta;
164 }
165}
166void LOD::InitLOD()
167{
168 Root=new lodNode();
169 Root->Pos.x=Size/2;
170 Root->Pos.y=Size/2;
171 Root->halfRange=Size/2;
172 CaculateRadius(Root);
173 CaculateDeltaH(Root);
174
175 maxLevel=0;
176 int i=Size-1;
177 while(i>1)
178 {
179 i/=2;
180 ++maxLevel;
181 }
182 --maxLevel;
183}
184//--------------------------------------------------------------------------------------------
185inline Vector3* LOD::GetPoint(int x,int y)
186{
187 return &(PointArray[y*Size+x]);
188}
189inline void LOD::SetPoint(int x,int y,float w,float h,float d)
190{
191 Vector3 *target=GetPoint(x,y);
192
193 target->x=w;
194 target->y=h;
195 target->z=d;
196}
197inline bool LOD::GetPointMark(int x,int y)
198{
199 return NeedSplitArray[y*Size+x];
200}
201inline void LOD::SetPointMark(int x,int y,bool ismark)
202{
203 NeedSplitArray[y*Size+x]=ismark;
204}
205//------------------------------------------------------------------------------------------
206void LOD::RenderNoLOD()//無優化的渲染
207{
208 if(!PointArray)return;
209 float co=0.004f/Zuint;
210
211 Vector3 *temp1,*temp2,*temp3,*temp4;
212 glDisable(GL_LIGHTING);
213 glBegin(GL_TRIANGLES);
214 for(int i=0;i<Size-1;++i)
215 for(int j=0;j<Size-1;++j)
216 {
217 temp1=GetPoint(i,j);
218 temp2=GetPoint(i+1,j+1);
219 temp3=GetPoint(i,j+1);
220 temp4=GetPoint(i+1,j);
221 glColor3f(1,temp1->z*co,0);
222 glVertex3fv(temp1->V_Array);
223 glColor3f(1,temp3->z*co,0);
224 glVertex3fv(temp3->V_Array);
225 glColor3f(1,temp2->z*co,0);
226 glVertex3fv(temp2->V_Array);
227
228 glColor3f(1,temp1->z*co,0);
229 glVertex3fv(temp1->V_Array);
230 glColor3f(1,temp2->z*co,0);
231 glVertex3fv(temp2->V_Array);
232 glColor3f(1,temp4->z*co,0);
233 glVertex3fv(temp4->V_Array);
234 }
235 glEnd();
236}
237inline bool LOD::IsNeedMark(lodNode *t)//節點的子節點是否可以標記細分
238{
239 int uy,dy,lx,rx;
240 int range=t->halfRange*2;
241 uy=t->Pos.y-range;
242 dy=t->Pos.y+range;
243 lx=t->Pos.x-range;
244 rx=t->Pos.x+range;
245 if(uy>=0 && !GetPointMark(t->Pos.x,uy))
246 return false;
247 if(dy<Size && !GetPointMark(t->Pos.x,dy))
248 return false;
249 if(lx>=0 && !GetPointMark(lx,t->Pos.y))
250 return false;
251 if(rx<Size && !GetPointMark(rx,t->Pos.y))
252 return false;
253 return true;
254}
255inline void LOD::RenderNode(lodNode *t,int &TrangleNum)//畫該節點
256{
257 if(!t)return;
258 TrangleNum+=4;
259 float co=0.004f/Zuint;
260
261 glDisable(GL_LIGHTING);
262 Vector3 *temp;
263
264 int uy,dy,lx,rx;
265 int range=t->halfRange*2;
266 uy=t->Pos.y-range;
267 dy=t->Pos.y+range;
268 lx=t->Pos.x-range;
269 rx=t->Pos.x+range;
270 int itemp=0;
271
272 glBegin(GL_TRIANGLE_FAN);
273 temp=GetPoint(t->Pos.x,t->Pos.y);
274 glColor3f(1,temp->z*co,0);
275 glVertex3fv(temp->V_Array);/**////-----------------中點
276
277 temp=GetPoint(t->Pos.x-t->halfRange,t->Pos.y-t->halfRange);
278 glColor3f(1,temp->z*co,0);
279 glVertex3fv(temp->V_Array);/**////-----------------1
280
281 if(lx<0 || GetPointMark(lx,t->Pos.y))
282 {
283 temp=GetPoint(t->Pos.x-t->halfRange,t->Pos.y);
284 glColor3f(1,temp->z*co,0);
285 glVertex3fv(temp->V_Array);/**////------------2
286 ++TrangleNum;
287 ++itemp;
288 }
289
290 temp=GetPoint(t->Pos.x-t->halfRange,t->Pos.y+t->halfRange);
291 glColor3f(1,temp->z*co,0);
292 glVertex3fv(temp->V_Array);/**////--------------3
293
294 if(dy>=Size || GetPointMark(t->Pos.x,dy))
295 {
296 temp=GetPoint(t->Pos.x,t->Pos.y+t->halfRange);
297 glColor3f(1,temp->z*co,0);
298 glVertex3fv(temp->V_Array);//-------------4
299 ++TrangleNum;
300 ++itemp;
301 }
302
303 temp=GetPoint(t->Pos.x+t->halfRange,t->Pos.y+t->halfRange);
304 glColor3f(1,temp->z*co,0);
305 glVertex3fv(temp->V_Array);//------------------5
306
307 if(rx>=Size || GetPointMark(rx,t->Pos.y))
308 {
309 temp=GetPoint(t->Pos.x+t->halfRange,t->Pos.y);
310 glColor3f(1,temp->z*co,0);
311 glVertex3fv(temp->V_Array);/**////------------6
312 ++TrangleNum;
313 ++itemp;
314 }
315
316 temp=GetPoint(t->Pos.x+t->halfRange,t->Pos.y-t->halfRange);
317 glColor3f(1,temp->z*co,0);
318 glVertex3fv(temp->V_Array);//-----------------7
319
320 if(uy<0 || GetPointMark(t->Pos.x,uy))
321 {
322 temp=GetPoint(t->Pos.x,t->Pos.y-t->halfRange);
323 glColor3f(1,temp->z*co,0);
324 glVertex3fv(temp->V_Array);/**////------------8
325 ++TrangleNum;
326 ++itemp;
327 }
328 temp=GetPoint(t->Pos.x-t->halfRange,t->Pos.y-t->halfRange);
329 glColor3f(1,temp->z*co,0);
330 glVertex3fv(temp->V_Array);/**////-----------------1
331
332 glEnd();
333}
334void LOD::InitMark()
335{
336 int n=Size*Size;
337 for(int i=0;i<n;++i)
338 NeedSplitArray[i]=false;
339}
340void LOD::RenderLOD(CY_Camera *cam)
341{
342 if(!PointArray || !Root)
343 return;
344
345 float modelview[16],projection[16];
346 glGetFloatv(GL_PROJECTION_MATRIX, projection);
347 glGetFloatv(GL_MODELVIEW_MATRIX, modelview);
348 glPushMatrix();
349 glLoadMatrixf(projection);
350 glMultMatrixf(modelview);
351 glGetFloatv(GL_MODELVIEW_MATRIX, modelview);//利用OpenGL計算乘積
352 glPopMatrix();
353 CY_Frustum Frustum;
354 Frustum.Init(modelview,false);
355 //-------------------------------------------------------
356 list<lodNode*>Temp1,Temp2;
357 list<lodNode*> *Current=&Temp1,*Next=&Temp2,*swapTemp;
358 list<lodNode*>::iterator i;
359
360 int level=0;
361 int distance2;//距離
362 Vector3 *point;
363 lodNode* temp;
364
365 trangleNum=0;
366
367 Current->push_back(Root);
368 while(Current->size()>0)
369 {
370 for(i=Current->begin();i!=Current->end();i++)
371 {
372 point=GetPoint((*i)->Pos.x,(*i)->Pos.y);
373 if(!Frustum.SphereInFrustum(*point,(*i)->BoundRadius))
374 {
375 continue;
376 }
377 else if(level==maxLevel)
378 {
379 RenderNode((*i),trangleNum);
380 }
381 else
382 {
383 distance2=VectorLength(cam->GetPosition()-(*point));
384 SetPointMark((*i)->Pos.x,(*i)->Pos.y,true);
385 if(distance2<C_Distan*C_Noise*(*i)->DeltaH && IsNeedMark(*i))
386 {
387 temp=(*i)->LeftUp;
388 SetPointMark(temp->Pos.x,temp->Pos.y,true);
389 Next->push_back(temp);
390
391 temp=(*i)->LeftDown;
392 SetPointMark(temp->Pos.x,temp->Pos.y,true);
393 Next->push_back(temp);
394
395 temp=(*i)->RightUp;
396 SetPointMark(temp->Pos.x,temp->Pos.y,true);
397 Next->push_back(temp);
398
399 temp=(*i)->RightDown;
400 SetPointMark(temp->Pos.x,temp->Pos.y,true);
401 Next->push_back(temp);
402 }
403 else
404 {
405 RenderNode((*i),trangleNum);
406
407 temp=(*i)->LeftUp;
408 SetPointMark(temp->Pos.x,temp->Pos.y,false);
409 temp=(*i)->LeftDown;
410 SetPointMark(temp->Pos.x,temp->Pos.y,false);
411 temp=(*i)->RightUp;
412 SetPointMark(temp->Pos.x,temp->Pos.y,false);
413 temp=(*i)->RightDown;
414 SetPointMark(temp->Pos.x,temp->Pos.y,false);
415 }
416 }
417 }
418 swapTemp=Current;
419 Current=Next;
420 Next=swapTemp;
421 Next->clear();
422 ++level;
423 }
424}
posted on 2009-06-30 12:53
陳昱(CY) 閱讀(3089)
評論(10) 編輯 收藏 引用 所屬分類:
游戲編程 、
圖形學