• 원본 : http://www.flipcode.com/tutorials/tut_octrees.shtml
  
  

Hidden surface removal is among the biggest problems when writing a 3D engine. 은면제거는 3D엔진을 제작하는데 있어 가장 큰 문제중 하나라고 할수 있다.

I struggled with it since the very beginning of writing 3D engines and still have no satisfactory solution to it. 나는 3D 엔진을 제작하는 아주 초창기에 은면제거부분을 가지고 고군분투했고 아직까지도 그것을 만족시킬만한 해결책을 가지고 있지 않다.

The ideal visibility detection scheme would allow unlimited data, extremely dynamic worlds and would have zero overdraw. 이상적인 visibility detection 체계는 무한한 데이타와 극히 동적인 세계를 다루어야 하고, 겹쳐서 그려지는 것이 전혀 없어야만 한다.

The first 3d engine which implements these three demands still has to be written. 이 3가지 요구를 구현했던 첫번째 3D 엔진은 아직 작성될 예정에 있다.

The Z buffer for example allows dynamical worlds and even crossing faces, but it suffers from immense overdraw. 예를 들어 Z 버퍼는 면들이 겹쳐있는 상태에서도 동적인 세계를 표현하는 것이 가능하다. 그러나 막대한 오버드로우가 발생하는 것이 단점이다.

The BSP-tree on the other hand, if well implemented, has no overdraw at all but needs that much pre-processing that dynamical worlds are a definite nono. 반면에 잘 구현되어있는 BSP 트리는 오버드로우가 전혀 없지만, 많은 전처리가 수반된다. (게다가 동적으로 변하는 세계를 구축하는 것은 금기에 가깝다.)

It wasn't until recently i first heard of the octree, and I must admit i was struck by it's simplicity. 최근에 내가 처음 옥트리에 대해 듣게 되었고 나는 그 단순함때문에 바로 받아들였다.(?...-_-;)

I never actually implemented this structure and therefore I will present no pseudo code at all. 직접 이 구조에 대해서 설명하지 않을 것이므로 pseudo code도 없을 것이다.

This explanation is merely an attempt to make it more clear to people who have never heard of it. 이 글은 거의 옥트리에 대해 전혀 들어보지 못한 사람들에게 보다 명확한 설명을 하려는 시도에 가깝다.

Besides, if you really understand the structure, then implementation is a piece of cake. 반면에, 만약 이 구조에 대해 정말로 이해하고 있다면 또다른 팁같은 것으로 생각해라. (...)

Our virtual world or level is actually nothing more then a soup of polygons. 우리의 가상세계 또는 레벨(?)은 실제로 폴리곤 집합에 지나지 않는다.

Some of you people might have thrown in a couple of curves and voxels but most of it will be polygons. Here it is: 여러분중 몇몇은 곡선이나 복셀들안에 던져질수도 있지만 그것들도 대부분은 폴리곤들이다. 여기에 예제가 있다. :

http://www.flipcode.com/tutorials/octree00.jpg

Fig 1. 우리의 작은 레벨

In the picture I just built a simple level containing no more than 250 polys. 그림안의 레벨은 약 250개의 폴리곤을 담고 있다. Now imagine a cube surrounding the world like in the next image: 이제 다음 그림을 보면서 레벨전체를 담고 있는 정육면체를 상상해봐라.

http://www.flipcode.com/tutorials/octree01.jpg

Fig. 2. 정육면체에 담겨있는 레벨.

Now it isn't hard to see that this cube can be divided into eight smaller cubes, hence the name octree. 이제 이 정육면체를 더작은 8개의 정육면체들로 나누는 것은 그렇게 어렵지 않다. (이렇기 때문에 옥트리라는 이름이 붙었다.) Take a look at this picture: 이 그림을 봐라. :

http://www.flipcode.com/tutorials/octree02.jpg

Fig 3. 분할되어있는 가상 정육면체가 지정된 우리의 작은 레벨.(-_-)

Call the larger cube the parent and the smaller cubes the children. 큰 부분의 정육면체부분을 '부모'라고 칭하고 그보다 작은 부속된 정육면체들을 '자식'이라고 부르기로 한다.

On their turn subdivide each children into eight smaller cubes, and you will notice we are creating a tree where each node has eight children.

There is still one little problem left. When should we stop dividing cubes into smaller ones? There are two possible solutions. The first one is to stop when a cube has some size smaller then a fixed number. The second one is more common. You might have noticed that every child has less polygons then it's parent. The trick is to stop subdividing when the number of polygons in a cube is smaller then some fixed number.

Trees are recursion, recursion is trees. It is as simple as that. If you have a correct definition of you cubeNode it is very easy to create an octree recursively. First of all you check all polygons against the boundarys of the cube. This is very simple cause these boundaries are all axis aligned. This means that the cube has six plane equations, which are:

1. X = Q.X
2. Y = Q.Y
3. Z = Q.Z
   
   
4. X = Q.X + cubeSize
5. Y = Q.Y + cubeSize
6. Z = Q.Z + cubeSize
   
   

Where Q is the position of one corner of the cube. This are very easy equations and the all parent polygons can very easily be checked against them.

It could occur that a polygon crosses a cube boundary. Again two possible solution are at hand. First of all we could clip the polygon against the cube, which is simple, because of the axis aligned boundarys. On the other hand we could put the polygon in all cubes it is in. This means that some cubes can contain the same polygons. In order to prevent us from drawing one poly more than one time we should have a flag on each polygon which will be set if the poly is drawn for the first time.

The implementation of an octree is very straight forward. I haven't done it myself yet, but I will soon. It is all matter of recursion. In order to construct a tree, the first thing you should think of is recursion. Whether we are talking about binary trees, quad trees or octrees, it doesnt matter, just build the darn thing recursively. So have a class definition of one cubeNode and put the creation of the tree in it's constructor. In this constructor you will call the constructor itself for smaller cubes.

An octree is actually nothing more then a data structure. It can be used for very different things. It is not only handy for visibility detection but also for collision detection, realtime shadows and many more things. The most important thing to understand about octrees is that if a parent is not important then it's children aren't either. Let's makes this a little bit more clear with an example.

We will do this in 2d, which therefore resembles a quadtree, but with some imagination it can very easily be extended to 3d. Here we test the cubes (squares) against the viewing frustrum. Take a look at the next picture:

http://www.flipcode.com/tutorials/octree04.jpg

Fig 4. An octree from the top and a viewing frustrum.

In this picture a colored square that has one color was dumped without checking it뭩 children. As you can see some squares had to be checked all the way to the final node, but some large squares could be dumped at once. The colored squares are the ones that are outside the viewing frustrum and the greyscale ones are the one inside the viewing frustrum. As you can see this is actually a worst case scenario because the viewing frustrum crosses the middle of the surrounding square and therefore all the four children have to be checked.

You could also apply the octree to many other things. Collision detection for example. Just check in which cube your bounding sphere or box is and you will only have to check against those faces. There are many more examples.

There is already a lot written about octrees. 옥트리에 대한 내용은 이미 많이 나와있다.

I tried to give my view on them in the hope somebody might read this. 나는 옥트리에 대한 내 견해를 이 글을 읽는 사람에게 주려고 하는 것이다. (직역...-_-;)

As you can see octrees are way easier to implement than BSP-trees (although some disagree) while offering a better structure. 여러분이 보다시피 옥트리는 더 괜찮은 구조를 제공한다면 BSP 트리보다 더 구현하기 쉽다. (물론 찬성하지 않을 수도 있을 것이다.)

The main point about an octrees is that when a parent is discarded so are it's children. Actually that is all there is to it. 옥트리의 요점은 부모노드가 버려질때 그것이 바로 자식노드가 된다는 것이다. (????) 실제로 그것이 전부이다.

Code clean, play Goldeneye and go vegetarian. Jaap Suter a.k.a .........