From IT도서관

효율적인 3D 익스포터 디자인 : 디자이너에게 사랑받는 프로그래머가 되자

원문 정보

• 저자: Gregg Tavares
• 원문보기: Effective 3D Exporter Design: How to Make Artists Love You

소개

There's a common feeling in the game industry that many programmers don't 'get' artists, and visa versa. This often results in artists making fun of programmers for speaking geek, and programmers making tools that force artists to do more work than they should have to.

게임산업계에 존재하는 한가지 공통적인 문제점은 많은 프로그래머들와 그래픽 디자이너들이 서로를 이해하지 못한다는 것입니다. 이 때문에 디자이너들이 프로그래머들을 컴퓨터밖에 모르는 사람 취급을 하게 되거나 프로그래머가 만든 툴이 디자이너의 업무부담을 가중시키는 결과가 나타나곤 하는 것이죠.

This article is about how you can make your 3D graphics exporter tools better, in terms of helping your artists get their job done. If you're lucky, this will get your project better art, which will mean bigger sales, and more money, fame and fortune. Plus, maybe your artists will actually like you for helping them do their best work!

이 글은 여러분의 3D 익스포터가 좀 더 디자이너들의 작업에 도움이 되도록 개선하는 방법에 대해 설명하려고 합니다. 운이 좋다면 여러분 프로젝트의 그래픽이 더 좋아질수 있을것이고, 덕분에 더 많이 팔리고, 더 많은 돈을 벌 수 있을 것이며, 명성과 부를 쌓을 수 있겠죠. 거기다 함께 작업했던 디자이너들이 당신을 좋아하게 될 것입니다!

철학

It may sound namby-pamby, but I think it's a good idea to come up with philosophical guidelines when you are designing your tools, to give you something to judge your choices by. Here are some of mine.

갑자기 왠 철학이냐라고 말할지 모르겠습니다만, 툴을 만드는 중 결정에 도움이 될만한 몇가지 철학적 가이드 라인을 가지는 것은 좋은 생각입니다. 여기 제가 생각하는 몇가지가 있습니다.

- Make your tools "bullet-proof"

- 여러분의 툴을 "방탄 조끼" 로 만드십시오

재벌중(포프)

Obviously, the artists don't try to break your 3D exporter, but if you make them juggle eggs, then the yolk will be on you occasionally. If your tools are designed such that it's easy to make mistakes, people will make mistakes. If it's possible to design them so mistakes are harder or impossible, then you'll save a lot of time in the long run. How many times have you spent hours tracking down a crash bug, only to find was bad data, data you could have prevented from being bad in the first place if your tools checked for it?

당연한 이야기지만 디자이너들이 여러분의 3D 익스포터를 망가뜨리려고 하지는 않습니다만 대충 만들어 넘긴다면 이후에 발생하는 문제들에 여러분이 곤혹을 치루게 될 것입니다. 툴이 실수 하기 쉽도록 만들어져 있다면 당연히 사람들은 실수를 할 수 밖에 없습니다. 반대로 실수를 하는것이 어렵거나 불가능하게 되어있다면 많은 시간을 절약할 수 있을 것입니다. 맨처음 데이터를 읽어올때 체크하기만 했다면 발생하지 않았을 문제 때문에 얼마나 많은 시간을 소모하고 있습니까?

To give you a concrete example, I once received a skinning library and exporter from another team. I immediately made a simple test and tried to run it, and it crashed with no explanation. After asking one of the artists familiar with the exporter, he messed with it for about 2 hours and finally gave up, not able to get it to work. So, it then got passed on to one of the programmers more familiar with the code.

구체적인 예를 들어보도록 하죠. 한번은 다른 팀에서 스키닝 라이브러리와 익스포터를 받은 적이 있습니다. 즉시 간단한 테스트 데이타를 만들어 실행 시켜 보았습니다만 아무런 설명도 없이 프로그램이 죽어버렸스니다. 그 익스포터를 사용하던 디자이너 한명에게 질문해보았지만 그도 2시간동안 괴로워하더니 결국 이유를 알아내지 못하고 포기해버렸습니다. 어쩔수 없이 관련 코드를 알고 있는 프로그래머에게 물어보았습니다.

After an hour or so of passing the files over to him, he told me 'Oh! You need to have 4 or less influences per vertex.' That's fair enough, but why does the tool crash? First, the library could check for too many influences - at least the debug version. Second, the exporter could do a similar job. The exporter might be more useful if it's flexible enough to handle more than 4 influences - maybe it should be designed to take some kind of project-based configuration file, so that you can specify the limits for a particular system, and it can check for them and warn you. I'm sure that the same scenario that I went through happened several times during the project: artist adds new art, game suddenly crashes, hours are spent tracking it down to the problem of too many vertex influences.

한시간 뒤 그는 "각 버텍스에 영향을 미치는 본이 4개 이하여야 합니다" 라고 말해주었습니다. 그래, 그건 좋다. 헌데 왜 프로그램이 죽었을까? 첫째로 영향을 미치는 본의 개수를 체크 하지 않았습니다 - 최소한 디버그 버젼에서라도. 둘째로 익스포터도 그런 작업을 해주지 않았습니다. 물론 버텍스가 4개 이상의 영향을 받을 수 있다면 익스포터는 좀 더 유용해지겠지만, 아마도 이 익스포터는 프로젝트 기반의 설정 파일로 디자인 되었겠죠. 그렇다면 특정 시스템의 한계를 명시하고 체크 해서 경고를 해줘야 했습니다. 프로젝트 진행 도중 이후에도 똑같은 일이 발생할 것이라는 사실을 확신할 수 있습니다. 디자이너가 새로운 데이타를 추가하자 게임은 갑자기 죽어버리고, 그 문제를 찾기 위해 수많은 시간이 소모되겠죠.

In fact, some commercial engines that I've seen can export data that crashes the engine. What were they thinking? The exporter should never export data the engine can't handle. As well as this, the engine or tool, at least in debug mode, should check that the data is correct. Otherwise, you're just asking for hours of debugging.

사실 익스포터가 만든 데이타를 넣자 터져버리는 상용 엔진을 본적도 있습니다. 그들은 무슨 생각을 하고 있는 걸까요? 익스포터는 엔진이 다룰 수 없는 데이타를 뱉어내서는 안됩니다. 그리고 엔진이나 툴에서도 최소한 디버그 모드에서는 데이타가 정상적인지 체크해주는 것이 좋습니다. 그렇지 않다면 여러분은 매번 몇시간씩을 버그를 잡는데 소모하게 될 것입니다.

다시 한번 강조하자면, 여러분의 툴을 방탄 조끼로 만드십시오!

- Don't force your artists to speak to a programmer in order to work out why something doesn't work.

- 디자이너들이 프로그래머에게 "왜 작동하지 않죠?" 라고 묻도록 하지 마십시오.

If your artists have to come to you every time something doesn't work, then you're going to be chasing down issues for your artists all the time.

만약 함께 일하는 디자이너들이 무언가 작동하지 않는 툴 때문에 날마다 여러분에게 찾아온다면 함께 일하는 디자이너들을 위해서라도 명심해 두어야 할 부분입니다.

Anything you can do to design your tools so that artists can figure out the issues on their own means you can work on other things, and everyone can get their work done faster and with less frustration.

문제가 발생했을때 디자이너들이 무엇이 문제인지 즉시 알아 차릴 수 있도록 툴을 만드십시오. 그렇게 함으로써 여러분은 다른 작업에 매진할 수 있을것이고 모든 사람들이 자신의 작업을 아무런 혼란 없이 더 빠르게 끝 마칠수 있을 것입니다.

- Make the tool, not the artist, do the non-artistic work.

- 디자이너들이 그래픽적 업무 외의 일을 하도록 만들지 마십시오.

This is pretty simple. Basically, don't force the artists to do things a trained monkey could do. An extremely simple example would be - don't force them to break up their quads into triangles. If you are passed a quad and you need triangles, then silently make triangles. Of course, you should probably check if it's planar or not and mark it as an error or warning (see below). But the point is - wherever possible, do the obvious thing.

간단합니다. 잘 훈련된 원숭이조차 할 수 있는 일을 디자이너들이 하도록 강요하지 마십시오. 아주 간단한 예를 들어보자면 쿼드를 트라이앵글로 쪼개는 일과 같은 것입니다. 쿼드는 필요 없고 트라이앵글이 필요하다면 그냥 쿼드를 자동으로 트라이앵글로 쪼개십시오. 물론 그것이 계획된 것이던 그렇지 않던 에러나 경고를 표시해 주어야 한다는 것입니다. (후에 다시 설명하겠습니다) 어쨋든 핵심은 가능한 명확히 하라는 것입니다.

- Make it possible for your tools to work as part of a one-step build process.

- 툴에서 이루어지는 작업을 되도록 일괄 작업으로 만드십시오.

You've probably heard about a one-step build being a good idea. The one-step build avoids human error, by eliminating all manual steps in the conversion of human-made creative assets to game-ready data. In particular, this means that artists should not be required to manually re-export their 3D models. They just create the models, textures, level maps, and so on. The build tools will export them as necessary (when they are newer than the game-ready versions of the same data.) An added benefit of the one-step build is that your artists spend most of their time creating art, instead of repeating non-creative tasks that automated systems could do a lot faster and cheaper.

아마도 공정이 일괄적으로 이루어지는 형태가 좋다는건 들어보셨을 겁니다. 디자이너가 작업한 데이타를 게임 데이타로 변환하는데 있어 수동으로 이루어지는 모든 단계를 없애고 일괄 생성 공정으로 만든다면 사람이 저지를수 있는 실수를 피할 수 있을 것입니다. 이것은 디자이너들이 3D 모델을 수작업으로 일일이 다시 뽑지 않아도 된다는 의미 입니다. 디자이너들은 단지 모델과 텍스춰와 맵등을 만들기만 하면 됩니다. 만약에 필요하다면 (현재 게임에서 사용되는 버젼이 변경되었거나 할때) 툴이 알아서 뽑아 주면 됩니다. 덧붙여서 원스텝 공정은 자동화 시킬 경우 좀 더 빠르고 편하게 이루어질 수 있는 비창조적 작업들을 디자이너들이 작업할 시간을 뺏겨가며 하지 않아도 된다는 이득도 있습니다.

- Make your tools to support the way that artists work.

- 디자이너들의 작업을 도울 수 있는 툴을 만드십시오.

There's a point to this piece of philosophy. Never forget that the goal of your tools is to help the artists make great art. You do that by designing your tools to support all the features and techniques that artists typically use. We'll go on to discuss some examples of how this philosophy comes into play.

이 철학의 주요 요지는 툴이 가지고 있는 궁극적인 목표가 "그래퍼들이 좀 더 굉장한 결과물을 만드는 것을 돕는 것" 이란 사실을 절대 잊지 말라는 것입니다. 디자이너들이 일반적으로 사용하는 기능들을 모두 지원하도록 하십시오.

이제부터는 이 철학들이 어떻게 사용되는지 이야기 해보겠습니다.

툴 디자인: 3D 익스포터

It seems like most exporters I come across are designed to export everything in the currently loaded scene in 3D Studio Max, Maya, Lightwave, and so on, but within the limits of the system the programmer designed. If anything in the scene is hidden, they don't export it, and for animation, they export based on the current setting of the time line in the user interface. Alternatively, they export the currently selected items. Some people refer to this export style as WYSIWYG exporting. It sounds like a good idea at first, and it might be great for testing your new engine. But with a little thought, it soon becomes clear that a different design would make things go smoother for everybody involved.

대부분의 익스포터가 그런것 같긴 합니다만 과거에 3D Studio Max, Maya, Lightwave 등의 툴에서 현재 화면 상에 보이는 모든 것을 그대로 뽑아주는 익스포터를 만든적이 있습니다. 만약 어떤 물체가 숨겨져 있다면 뽑지 않고, 애니메이션도 현재 맞춰진 키프레임으로 뽑아내었습니다. 또는 현재 선택된 오브젝트를 익스포트 하기도 했습니다. 보통 이런 것을 WYSIWYG (You See Is What You Get) 라고 부르죠. 언뜻 보기엔 괜찮아 보이기도 하고, 새로운 엔진 테스트에는 훌륭할지도 모릅니다만, 조금만 생각해보시면 모두가 사용하기엔 그다지 좋은 형태가 아니라는 것을 알 수 있을 것입니다.

Let's see what some of the problems are, and the solutions that come up by applying the philosophies above.

무엇이 문제였는지, 그리고 그 문제들에 대한 해결법들에는 어떠한 것들이 있는지 앞서 언급한 철학들과 대조해가며 알아보도록 하지요.

- Make your tools show errors that can be noticed, understood and useful.

- 에러는 알아보기 쉽고, 이해하기 쉬우며, 유용한 형태로 보여주십시오.

Asking an artist to look through ten thousand lines of diagnostic output, in order to find the three warnings that flew by while the data is converted is not useful. Following the "Don't force your artists to speak to a programmer" philosophy, the best way to deal with problems is to show them visually. If certain polygons are obviously wrong, then somehow mark them and show the artist.

디자이너에게 데이타가 컨버팅 되는 동안 단 세줄의 경고를 찾기 위해 수천줄의 메세지를 지켜보고 있으라고 하는 것은 전혀 무의미한 일입니다. "디자이너가 프로그래머에게 질문 하도록 만들지 마십시오" 라는 구절에 따라, 이 문제를 처리하는 가장 효과적인 방법은 시각적으로 보여주는 것입니다. 폴리곤이 잘못 되었다면 디자이너에게 어떻게든 표시하고 보여주십시오.

In my tools, if certain polygons are bad, I'll still output the polygons or the rest of the model, but my file formats have an optional semi-generic error encoding system where I can put in error messages, error lines, error points, and so on. When the 3D objects are loaded up into the viewer or the game, any object that has error information can be displayed or marked in obvious colors such as flashing red.

제 경우 폴리곤이 정상적이지 않더라도 그래도 일단 저장을 하거나 그 부분을 제외한 나머지 부분만이라도 저장을 합니다. 그리고서 에러 메세지나 잘못된 라인 혹은 벡터 번호를 준비해둔 파일의 에러 입력 시스템의 자리에 저장을 해둡니다. 이후 뷰어나 게임에서 3D 오브젝트를 불렀을때 에러 관련 정보가 있다면 반짝거리는 빨간색 처럼 눈에 잘 띄이는 색으로 화면상에 표시합니다.

Those objects can then be selected, and the errors specific to that object can be brought up. If the errors are visually representable, then the polygons associated with that error will also be displayed if the object is selected and a particular error highlighted. For example, an error selected in the debug menu that says "polygon has too many weights" will highlight the polygon in question in the game or previewer.

오브젝트를 선택했을때 오브젝트와 관련된 에러들을 가져와 보여줍니다. 만약 에러가 시각적으로 보여줄 수 있는 형태라면 특정 에러나 그 에러와 연관된 폴리곤을 선택 했을때 출력해주는 것이 좋습니다. 예를들어, 디버그 메뉴에서 "폴리곤에 영향을 미치는 본이 너무 많습니다" 라는 사항을 선택했을때 해당 폴리곤을 표시해주면 됩니다.

Another good idea is to have the programmer that wrote the error message put their name in the message. For example, it could state: "WARNING: <gman> found vertices with more than 4 influences". That way, the artist will immediately know who to talk to if they have a question about the message.

좋은 팁이 한가지 더 있습니다. 에러 메세지를 작성한 사람의 이름을 에러 메세지와 함께 출력해주는 것입니다. 다음과 같은 형태가 되겠죠. "경고: <gman> 4개 이상의 본으로부터 영향을 받고 있는 버텍스가 있습니다." 이렇게 함으로써 아티스트는 관련 질문을 누구에게 해야 하는지 즉시 알아차릴 수 있습니다.

- Never let your tools fail.

- 여러분의 툴이 실패하도록 만들지 마십시오.

I know some of you will disagree with this idea, but hear me out. This is a goal I tried to reach on my last game. No matter what the problem, try to output something into the game or previewer. This goes along with the philosophy of "Don't force your artists to speak to a programmer in order to work out why something doesn't work".

물론 이 생각에 동의하지 않는 분이 계실지도 모르겠습니다만 일단 들어보십시오. 이건 제가 마지막으로 작업했던 게임에서 목표로 삼았던 것입니다. 게임이나 프리뷰에서 무슨 문제가 발생하더라도 무엇이든 일단 출력하려고 했습니다. 이건 "아티스트들이 프로그래머에게 무엇인가 작동되지 않는다고 말하는 상황을 만들지 않도록 하라" 라는 원칙과도 일맥 상통 합니다.

It's very frustrating when you can't build a level because something is broken, and even more so when the problem is unrelated to what you are currently working on. It's best to at least get the object or level working as soon as possible, even with errors or missing items. For example, if a texture path is incorrect and you can't find the source file for the texture, then use a special 'ERROR' texture and still write out the file. This will make it visually clear to the artist what is wrong, and they will most likely know how to fix it immediately, but they will also get to see their model now instead of later.

무엇인가 깨져 있다고 맵 데이타를 부를 수 없다면 매우 곤혹스러울 것입니다. 게다가 현재 작업중인 것과 관련이 없는 문제라면 더더욱 그렇겠죠. 가장 좋은 방법은 오브젝트나 맵을 가능한 곳까지는 불러서 배치 하고 에러나 출력하지 못한 아이템을 표시하는 것입니다. 예를 들어 텍스춰 경로가 잘못 되어 파일을 찾을 수 없다면 "error" 텍스춰를 사용하고 and still write out the file. 이렇게 하면 디자이너들에게 무엇이 잘못되었는지 명확하게 시각적으로 알려줄 수 있으며 대부분 어떻게 고쳐야 하는지 곧바로 알아차릴 수 있을 것입니다. 그리고 일단 작업 결과물을 확인 할 수 있겠죠.

Another example from my level building tools - if one object in the level has errors the level still gets built, but that object is just tagged as bad. There are often thousands of items in a level made by different people. If all it takes is for one of them to be bad to stop your level from loading, you are not going to be getting much work done.

제가 만들었던 툴에서의 또 다른 예를 들어보겠습니다. 데이터를 불러오는 중에 한 오브젝트에 에러가 있다면 그냥 "잘못 되어 있다" 고 체크만 해놓고 넘어갑니다. 데이터에는 여러사람이 만든 수천개의 아이템이 들어가 있습니다. 이중 단 한개의 아이템이 잘못되었다고 데이터를 불러오는 도중 멈춰 버린다면 아마도 여러분의 작업 시간에는 많은 제약이 따를 것입니다.

You can go into more detail still, using both warnings and errors in exported data. A warning means that the data needs to be fixed, but the object should still run. In other words, the game should feel safe to execute the A. I. code for that object without fear of crashing. An error means that the particular object is not in a state the game can use. After loading a level, all objects with warnings would be flashing and all objects with errors will just have a name displayed in their place. At that point, the artist or designer can select objects and find out the specific errors. This is much easier to fix than sifting through hundreds of lines of building diagnostics.

익스포트 데이타에서 경고와 에러 를 사용하십시오. 경고는 데이터가 수정되어야 하지만 일단 동작은 한다는 의미입니다. 다시 말해서 해당 오브젝트를 다루는데 게임이 멈춰 버릴 위험은 없다는 것입니다. 에러는 게임에서 사용 할 수 없음을 의미합니다. 맵을 부른 후에 경고는 깜빡거리며 표시되어야 하고 에러 수준의 오브젝트는 그 오브젝트가 있어야 할 자리에 이름만 표시해 줍니다. 그 시점에 디자이너나 기획자들은 오브젝트를 선택하고 에러를 발견 할 수 있을 것입니다. 맵 로딩중 남은 수천줄의 로그 속에서 문제를 찾아 수정하는 것 보다는 이쪽이 훨씬 쉬울 것 입니다.

However, in some cases it might be appropriate to fail immediately, especially if building a level or object takes a long time. If there are things you can check for quickly that you know will cause a problem, you might want to bring those to the attention of the artist immediately. But if possible, visual evidence is almost always better than just an error message.

하지만 어떤 경우에는 즉시 실패하는 것이 좋을 수도 있습니다. 예를 들어 미리 체크해보고 맵이나 오브젝트가 불러오는데 시간이 너무 오래 걸릴 것 같아 문제가 발생할거 같다면 불러오지 못하도록 함으로써 디자이너들에게 주의를 줄 수 있습니다. 하지만 가능하다면, 몇줄의 에러 메세지 보다는 시각적으로 보여주는 것이 언제나 더 나을 것입니다.

- Don't force your artists to remove helper objects.

- 디자이너들의 Helper 오브젝트를 지우도록 하지 마십시오.

Many exporters require your artists to have the data they need, and only that data, in their 3D editor. Artists are not allowed extra lights, extra models, extra cameras, and so on. But have you ever actually seen how your artists work? They need lights to light their models. They need extra models for constraints, for checking sizes, or for other references. Asking them to have to delete those every time they export is asking for trouble.

많은 익스포터들이 디자이너들에게 3D 에디터에서 필요한 데이타만을 남겨두길 요구하고 있습니다. 디자이너들에겐 광원, 확장 모델, 카메라와 같은 것은 허용되어있지 않죠. 혹시 디자이너들이 어떻게 작업하는지 본적 있습니까? 그들은 모델에 빛을 비춰보기 위해 광원이 필요합니다. 그들은 구속 조건이나 크기를 체크하기 위해서나, 혹은 작업을 위한 더미 모델들이 필요합니다. 그들에게 데이터를 뽑을 때마다 이러한 것들을 지우길 강요한다면 문제가 될 것입니다.

Firstly, you are making artists do this work manually every time they export. They may even have to rebuild all their lights and constraints if they accidentally save after they've deleted them for exporting. Alternatively, they may forget to remove them, export and thereby clutter the game with un-needed items. Even worse, they may accidentally make the game crash and you've got another hour or two as you try to figure out why.

디자이너들에게 수작업으로 데이터를 뽑을 때마다 이러한 작업을 하도록 만들었을때, 그것들을 지우고 데이터를 뽑은 후에 실수로 데이터를 저장 해버렸다면 그들은 다시 여러가지를 재배치 해야만 할 것입니다. 결과적으로 디자이너들이 지우는 것을 잊어버리고 게임 속에는 불필요한 아이템들이 어지럽게 떠다닐 것입니다. 최악의 경우엔 게임이 멈춰버리고 이유를 찾아내기 위해 여러분은 한두시간을 소요하게 될 것입니다.

Following the "make your tools support the way artists work" philosophy, it would be better to find a way to let artists specify what needs to be exported, so that you can ignore all the rest. That way your artists are unlikely to make as many mistakes. They don't need to remember to delete objects. They don't have to worry about accidentally saving after having deleted objects. They can keep all the objects, lights and cameras that make their job easier.

"디자이너들의 작업을 도울 수 있는 툴을 만드십시오" 라는 철학을 기억하십시오. 디자이너들에게 무엇을 뽑을 것인지 명시한 후에 나머지는 무시하게 만들 수 있을 것입니다. 이렇게 한다면 디자이너들의 실수가 줄어들겠죠. 불필요한 오브젝트를 지우는 작업을 할 필요가 없습니다. 데이터를 뽑은후 무심코 저장해버리는 실수를 두려워할 필요가 없어집니다. 디자이너들은 그들의 작업을 더욱 간편하게 해주는 광원이나 카메라와 같은 모든 오브젝트들을 남겨둘 수 있을 것 입니다.

I'd also recommend that the artists should specify what to export, as opposed to specifying what not to export. If you choose the "not" route, then if they add something and forget to mark it to "not" be exported , you're going to end up with stuff you don't want in your data. This is worse than finding something is missing because it was not specified, since once it is specified it will never be missing again. It is usually easier to see what is missing in the game than to notice something extra that isn't supposed to be present.

덧붙여 디자이너들이 무엇을 뽑지 않을 것인지 명시하는 것 보다는 무엇을 뽑을 것인지 명시 해주는 쪽을 추천합니다. 디자이너들이 새로운 오브젝트를 추가하고 익스포트 하지 않겠다는 것을 명시하지 않았을 경우 데이터로 뽑지 않는 것이 좋습니다. 이 경우 뽑히지 않은 데이터를 찾아야 되니 좋지 않을 수도 있습니다만 여러번 실수 하지는 않을 것입니다. 또한 적어도 표시 되지 말아야 할 무언가를 알아차리는 것보다는 무엇인가 출력되고 있지 않다는 것을 확인하는 쪽이 훨씬 쉽겠죠.

- Don't force your artists to check export settings more than once.

- 디자이너들에게 한번 이상 익스포트 셋팅을 설정하도록 강요 하지 마십시오.

Many exports have a gigantic amount of settings. For example, they include elements choosing whether to export vertex colors or animations; whether to save textures as filenames or re-write them; whether to save as an object or a character; what internal name to use for a character, and so on.

여러 익스포터가 끔찍하도록 많은 설정을 가지고 있습니다. 예를 들자면 버텍스 칼라나 버텍스 애니메이션을 포함 시킬 것인지, 텍스춰를 파일 이름만 저장할지 아니면 포함 시킬지, 오브젝트인지 캐릭터인지, 캐릭터를 위해 내부 이름을 사용할 것인지 등이 있습니다.

While these settings might be important, it's asking for trouble to ask your artists to check them every time they export the same file. Following both the "Make the tool, not the artist, do the non-artistic work" and the "make it bulletproof" philosophy, these options should be set once and saved somewhere for exporting that particular file. So, if the camera is not supposed to be exported in this file, then the next time the file is loaded and exported it will automatically not export the camera. If another file is supposed to export animations with a base node called "orcbase", then if it is loaded and exported again, it should automatically export animations as "orcbase".

물론 이러한 설정들은 중요하기 때문에 디자이너들은 같은 파일을 매번 뽑을때 마다 여러분에게 문제점에 관해 문의할 것입니다. "디자이너들이 그래픽적인 일이 아닌 것을 하도록 만들지 마십시오.", "여러분의 툴을 '방탄 조끼' 로 만드십시오" 두가지 철학에 따라 이 옵션은 한번만 설정하도록 하고 설정 내용을 어딘가에 저장해 두십시오. 만약 카메라가 데이터로 뽑히지 않았다면 다음 번에도 자동으로 카메라를 뽑지 않도록 해야 합니다. 또 어떤 파일에서 "orcbase" 라는 이름의 노드를 기반으로 한 애니메이션을 뽑았다면 다음에도 자동으로 "orcbase" 의 애니메이션을 뽑아야 합니다.

Following the "make it bullet proof" rule, the artist should only have to look at settings if he or she needs to change them, and never once they are set. If they have to check them every time they export, odds are some percentage of those times they will miss checking or un-checking an option, and the coder and the artist will lose more time working things out.

"여러분의 툴을 '방탄 조끼' 로 만드십시오" 라는 룰에 따라 디자이너들은 단지 바꾸기 원하는 것만 보면 되며 다시는 그것을 건드릴 필요가 없어야 합니다. 만약 디자이너들이 매번 그것을 확인해야 한다면 그들이 체크해야 되거나 체크해야 되지 말아야할 옵션들을 놓치는 경우가 더욱 많아질 것이며 프로그래머나 디자이너 모두가 작업할 시간을 상당히 잃게 될 것입니다.

- Don't use the time line as an exporter setting.

- Time Line 을 익스포터의 설정으로 사용하지 마십시오.

Lots of exporters export animation by looking at the current time line in the user interface. If it's set from frame 10 to frame 150, then they export 141 frames from frame 10 to frame 150. As above, this is also error-prone. Every time an artist exports, they have to remember to put the editor's UI in a certain state. If they forget to do so, then certain in-game animations will no longer work properly.

많은 익스포터들이 애니메이션을 인터페이스에 지정된 현재 시간을 기준으로 데이터를 뽑곤 합니다. 만약 프레임이 10 부터 150 까지 설정되어있다면 그 사이 141 프레임을 뽑곤 하죠. 이와 같은 경우는 잘못될 확률이 높습니다. 그래픽 데이터를 뽑을때 마다 디자이너들은 올바른 자리에 UI 를 맞춰두어야만 합니다만 만약 그것을 잊어버렸을 경우 게임에서는 제대로 된 애니메이션이 나오지 않겠죠.

Following the "make your tools bullet proof" philosophy, it's better to have a way to specify once which frames to export. That way, artists don't have to remember to reset the time line. They know when they export, no matter what state the UI is in, they are going to get the frames they want.

"여러분의 툴을 '방탄 조끼' 로 만드십시오" 라는 철학에 따르자면 어느 프레임을 뽑을 것인지 명시 할 수 있도록 해두고 한번 설정한 이후에는 다시 설정할 필요가 없도록 만드는 것이 좋습니다. 디자이너들은 데이터를 뽑을때 더이상 UI 를 손댈 필요 없이 자신이 원하는 프레임을 얻을 수 있을 것입니다.

An even better option would be to write a flexible specification system that allows your artists to put more than one animation in the same file. For example, your walk cycle might be frames 10 to 40, and your run cycle might be frames 100 to 130. Some artists find that method of animating much easier than forcing them to do every animation in a separate file. It also means global changes to a character, like adding a gun attachment point to the hand, will be reflected without changes needed to all the other animations.

같은 파일에 하나 이상의 애니메이션을 넣음으로써 좀 더 유용한 시스템을 만들 수 있습니다. 예를 들어 걷는 동작이 10 ~ 40 프레임 사이에 있고 뚜기 동작이 100 ~ 130 프레임 사이에 있다면 각각 파일로 구분해 놓았을때보다 훨씬 더 찾기 쉬울 것입니다. 또한 손에 총 어테치 지점을 붙이는 것처럼 전체에 적용되어야 할 수정을 가할때 여러개의 파일을 일일이 수정해야 될 필요도 없어집니다.

- Don't force your artists to collapse hierarchies.

- 디자이너들에게 상속 구조를 정리하도록 만들지 마십시오.

Another issue I see in lots of exporters is that they export the hierarchy in the 3D tool directly to the game hierarchy. In order to have the best speed in today's hardware, it's important to have as few separate models as possible.

많은 익스포트들 발견할 수 있는 또 하나의 쟁점은 3D 툴에서 사용되는 상속 구조를 그대로 게임에 적용한다는 점입니다. 요즘의 하드웨어에서 최대 속도를 내기 위해서는 가능한한 최소한으로 모델을 구분해두는 것이 좋습니다.

Unfortunately exporters that export the hierarchy directly require the artists to take separated models, and merge them into one model. A simple example might be a static 2-wheeled cart. The artist might build it using 2 tubes for wheels, a cylinder for an axel, 6 cylinders per wheel for the spokes, and then a box minus 2 faces for the cart area. In some exporters, if those objects are not all merged into 1 model, they will be exported as 16 separate models. Most programmers don't give that a second thought; they just assume the artists will merge everything.

불행히도 별다른 가공 없이 상속 구조를 그대로 뽑아내는 익스포터에서는 디자이너가 일일이 모델을 나누고 다시 합치는 작업을 해야만 합니다. 2륜 카트로 간단한 예를 들어보겠습니다. 디자이너는 바퀴를 2개의 튜브로 만들 것이고, 하나의 실린더로 엑셀을, 바퀴마다 6개의 실린더로 스포크를 만들 것이며, 박스로 카트의 몸체를 만들 것입니다. 어떤 익스포터에서는 이것을 하나의 모델로 합치지 않고 16개의 구별된 모델로 익스포트 할 것 입니다. 대부분의 프로그래머는 디자이너들이 모든 것을 합쳐서 작업할 것이라 생각합니다.

Once the artists merge the models, it becomes much more difficult to edit. For example, if an artist wanted to widen the cart, they would want to stretch the axel and the cart, but not the wheels or the spokes. If you forced them to collapse the model they can no longer do that easily.

디자이너들이 한번 모델을 합치면 이후로는 수정 작업이 매우 어려워 집니다. 예를 들어 디자이너가 바퀴와 스포크를 제외하고 카트 몸체와 엑셀만 크기를 늘리고 싶어하는 경우 말입니다. 만약 디자이너들에게 모델을 모두 정리 합치라고 강요한다면 이러한 작업을 더이상 쉽게 할 수 없을 것입니다.

"Making your tools support the way that artists work" means letting the artists leave their models in the state best suited for them to edit it to perfection, not the easiest state for a tools coder to export. If your exporter has a way to specify: "From this node down in the hierarchy, merge all children into one model", you'll allow your artists to leave their art in the best state for editing, and still get optimal models for the game.

"디자이너들의 작업을 도울 수 있는 툴을 만드십시오." 라는 말은 프로그래머들에게 익스포트 하기 쉽게 만들라는 것이 아니라 디자이너들이 작업하는 모델을 쉽게 수정할 수 있는 최고의 상태로 남겨두는 것을 의미 합니다. 여러분의 익스포터가 "이 노드 아래의 모든 노드를 하나의 모델로 합친다" 는 식의 기능을 지원한다면 디자이너들은 수정하기 쉬운 형태의 작업물을 남겨두면서 게임에 최적화된 모델을 얻어 낼 수 있을 것입니다.

- Don't use the hidden or frozen attribute to filter the export.

- 숨김이나 고정 속성을 필터로 사용하지 마십시오.

Going back to "Make your tools bullet proof", your exporter shouldn't care if something is marked as hidden or frozen. That's because your specification says what to export, regardless of whether a particular item is hidden or frozen. Like above, your artists may have hidden something to make the model easier to edit, and then saved the file. The next time the file is exported, the code should still be exporting everything required and not exporting extraneous items. Otherwise, you are going to run into time-consuming debug problems, next time you load up your level.

"여러분의 툴을 "방탄 조끼" 로 만드십시오" 에 따르자면 아이템이 숨겨졌던 고정되어있던 무조건 익스포트 한다고 명세를 통해 알리고 숨기거나 고정해둔 정보를 사용해서는 안됩니다. 디자이너들은 작업을 좀더 쉽게 하기 위해 모델을 감춰둘수도 있으며 그 상태로 파일을 저장할 수도 있습니다. 이후에 그 데이타가 익스포트를 시도할때 코드는 이전과 마찬가지로 필요한걸 익스포트 하고 외부 아이템은 익스포트 하지 않아야 합니다. 그렇지 않다면 문제를 찾기 위해 시간을 소모하게 될 것입니다.

- Don't export function curves!

- 펑션 커브를 익스포트 하지 마십시오!

I've seen many exporters that pull function curves directly out of the 3D package. The documentation for the exporter then goes on to tell the user that, because of this *feature* the artists are only allowed to use certain kinds of animations. Does anybody see a problem here? All the interesting animation functions require features not supported by function curves. Probably the most important one is constraints. Constraints are incompatible with exporting function curves, as are expressions.

3D 데이타에 펑션 커브를 그대로 담아내는 많은 익스포터들을 보았습니다. 때문에 문서를 통해 작업자들에게 특정 애니메이션 기능을 사용하기 위해서는 펑션 커브를 사용해야만 한다고 강요하곤 합니다. 여기서의 문제점이 무엇인지 아시겠습니까? 괜찮은 애니메이션 기능들은 펑션 커브의 지원이 필요 없습니다. 아마 가장 중요한 것은 구속 조건일 것입니다. 구속 조건은 펑션 커브와 같이 익스포트 시에는 표현이 제대로 이루어지지 않습니다.

Following the "Make your tools support the way artists work" philosophy, a much better solution is to sample the output of the package in question. You can then write some curve fitting functions, if you happen to want to use function curves to compress your data. This way, your artists are free to use every tool at their disposal to make great animation, and you'll still be able to compress their results to something reasonable.

"디자이너들의 작업을 도울 수 있는 툴을 만드십시오" 라는 철학에 따라 더 좋은 해결 방법은 결과물의 샘플을 보여주는 것입니다. 이렇게 함으로써 펑션 커브를 데이타를 압축하는데 필요하게 되었을때 활용할 수 있을 것입니다. 이 방법을 통해 작업자들은 애니메이션 작업을 하는데 있어 자유롭게 툴의 모든 기능들을 사용할 수 있을것이며 여러분은 그 결과물을 조금 더 나은 형태로 저장할 수 있게 될 것입니다.

- Don't ever consider editing a middle file format.

- 중간 단계 파일 포맷의 수정은 절대로 고려하지 마십시오.

Middle file formats are a great idea. They allow you to separate your processing tools from your exporters, and also make it possible to use different 3D packages on the same project.

중간 단계 파일 포맷은 훌륭한 아이디어 입니다. 중간 단계 파일 포맷을 통해 여러분은 익스포터에서 작업 단계를 구분하게 할 수 있으며 프로젝트 내에서 다른 형태의 포맷으로 바꿀 수도 있습니다.

However, middle file formats should really be treated just like .obj or .o files in a compiled language. They are files that the build process makes that are temporary files, never to be touched by human hands. The reason? Obviously, if any changes need to be made to the 3D data, it's going to be made by the artists back in the original 3D package. Any changes applied to the middle format are going to be lost when the artist re-exports the new model.

하지만 중간 단계 파일 포맷은 반드시 컴파일 언어에서 .obj 나 .o 파일 처럼 다루어져야만 합니다. 이들 파일은 빌드 공정에서 생기는 임시 파일일뿐 결코 직접 수정되는 일은 없습니다. 이유는 명확합니다. 3D 데이타에 수정이 필요하다면 작업자들이 가지고 있는 원본 3D 데이타에서 이루어져야 합니다. 중간 단계 파일 포맷에서 이루어진 수정 사항은 이후 재차 익스포트시에 없어질 것이기 때문입니다.

This goes back to the goal of your tools being to help your artists make great art. If your processes involve editing the middle file formats, and that editing is lost every time your artists edit an original 3D source file, you are forcing someone to waste time manually re-tweaking the new middle file. You've just given them an incentive to not want to edit things to be better.

작업자들이 굉장한 결과물을 만들 수 있게 만들자는 여러분의 본래 취지로 돌아가도록 하죠. 만약 작업 공정에서 중간 단계 파일 포맷을 수정하는 것이 허용되고 작업자들이 원본 3D 파일을 수정할때마다 수정 사항이 손실 된다면 누군가는 매번 시간을 낭비하게 될 것입니다. 단지 작업자들에게 수정하지 않는게 좋을것 같다고 말하십시오.

- Don't needlessly limit the possible applications of your exporter.

- 여러분의 익스포터에서 가능한 기능을 제한하지 마십시오.

Design your exporter to handle as many cases as possible. To give you a concrete example, I once worked with an exporter that required the artists to manually export a "bind pose" for skinned characters. That one idea removed any possibility of using that exporter to export full real-time 3D cut-scenes, since a cut-scene would never have all the characters in a bind pose state. Instead, the exporter should lookup the bind pose automatically.

여러분의 익스포터가 되도록 많은 경우를 조작할 수 있도록 설계하십시오. 좀 더 구체적인 예를 들어보자면 저는 언젠가 스키닝 캐릭터에서 "bind pose" 만을 수동으로 익스포트 하는 익스포터를 요청을 통해 작업한 적이 있습니다. 이 한가지 아이디어로 인해 모든 캐릭터가 바인드 포즈 상태일리는 없으니 3D 리얼타임 컷씬을 통째로 익스포팅 할 수 있는 가능성이 사라졌습니다.

In Maya at least, there are 2 bind poses. There's one that Maya calls the "bind pose", and the one it actually uses. You want your exporter to use the one Maya actually uses, because the one it calls the "bind pose" is deletable and trust me, your artists will delete it. Why put them through the frustration of having to do their art over? Just make your exporter handle it in the first place.

!!!마야에는 2개의 바인드 포즈가 있습니다. 하나는 "bind pose" 라 부르며 실제로 사용됩니다. "bind pose" 라 불리는 그것은 삭제가 가능하고 디자이너들이 그것을 지울 것이기 때문에 여러분은 마야를 사용하길 원할 수도 있습니다. 왜 디자이너들은 그래픽적인 아닌 일로 괴롭히는 거죠? 그냥 여러분의 익스포터에서 처음에 컨트롤 하도록 하십시오.

Another example of this would be limiting your exporter to only exporting one item at a time. That limit would provent you from exporting multiple characters or multiple animations. If you removed that limit, your artists would be able to make real time cut-scenes with a single click export process, as well as make it easy for artists to animate throws and other multiple-character animations.

또다른 예를 들어보자면 아마 여러분의 익스포터는 한번에 한가지만 익스포트 할 수 있게 되어 있을 것입니다. 이 제약은 동시에 여러 캐릭터나 여러 애니메이션을 익스포트 할 수 없게 됩니다. 만약 이 제약을 제거 한다면 디자이너들은 단순한 익스포터 작업으로 리얼타임 컷씬을 만들수 있게 될 뿐만 아니라 던지는 애니메이션이나 동시에 여러 캐릭터의 모션을 설정할 수 있게 될 것입니다.

- Don't create or load bad data.

- 잘못된 데이타를 생성하거나 부르지 마십시오.

Your exporters should never create bad data, and your engine, previewer and tools should never load bad data. Obviously, if you have bugs in either, you might get bad data, but often there are other issues at play.

익스포터에서는 절대로 잘못된 데이타를 만들지 말고, 엔진과 프리뷰어, 툴에서는 잘못된 데이타를 절대로 불러들이지 마십시오. 만약 어느 한쪽에라도 문제가 있다면 잘못된 데이타가 생성될테고 어디에서든 자주 문제가 발생하게 될 것입니다.

I put version numbers in all my data files to support the idea of making your tools bullet proof. This is done so that the art previewer and game code can check if they understand a certain type of file, and print an error on the screen if the version is out of date. The alternative is that your game loads the data, then crashes without showing a specific error, and you spend hours trying to figure out why.

저는 툴을 방탄 조끼로 만들라는 생각으로 제 모든 데이타 파일에 버젼을 넣어둡니다. 이렇게 함으로써 프리뷰어나 게임 코드상에서 파일의 정확한 형식을 알 수 있게 되며 만약 버젼이 유효하지 않다면 에러를 출력합니다. 무엇보다도 중요한것은 게임에서 데이타를 부를때 프로그램이 죽거나 하지 않고 에러를 보여줘야 한다는 것입니다. 그렇지 않다면 여러분은 이유를 찾기 위해 매번 시간을 낭비하게 될 것입니다.

There are other various ways to handle this issue. For example, at one company I worked at, the version numbers were used as part of the load path. So, for example, a version 2.1 character might come from "\gamedata\2.1\characters", where as code that needed 2.3 version characters would load them from "\gamedata\2.3\characters". Based on their version, all the tools knew where to put their results.

이 문제를 다루기 위한 몇가지 방법들이 있습니다. 예전 제가 일하던 한 회사에서는 버젼을 로딩 경로의 일부로 사용했습니다. 예를들어 2.1 버젼의 캐릭터는 "\gamedata\2.1\characters" 에서 불러오며, 만약 2.3 버젼의 캐릭터가 필요해지면 "\gamedata\2.3\characters" 에서 불러오게 됩니다. 각 데이타의 버젼을 기반으로 해서 모든 툴은 결과물을 어디에 저장해야할지 결정하게 됩니다.

This method had the advantage that people using older versions of the code still had access to data that worked with their version. In turn, people using or working on newer tools and newer versions could safely build new assets, and not worry about breaking everyone. Personally I'd probably use both ideas just to be safe. But, however you do it, a similar approach will save everybody time not tracking down version issues.

이 방법은 사람들이 예전 버젼으로 데이타를 다룰 일이 있거나 할때 매우 유용합니다. 또한 새로운 툴과 새로운 버젼으로 안전하게 새로운 작업을 할 수 있으며 무엇인가 손상될 걱정을 하지 않을 수 있게 됩니다. 개인적으로도 이 두가지 아이디어는 매우 안전하다고 생각합니다. 하지만 만약 여러분이 이 아이디어를 채용한다면

In my version numbers, I have option bits - for example, a bit that says if the file is the kind of file with error information or not. I mentioned above that putting error info in the file is a good idea for development. But in the shipping product, that code and that data is a waste, so I compile it out. But I still have the code check for a version number, and that includes whether the file is a development file or a release file. Otherwise, during final bug testing it's likely that a development file is going to get accidentally used during testing. Without the check and corresponding error, there are going to be hours spent tracking down the cause of the crash.

저는 버젼 정보에 옵션 정보도 포함해 둡니다. 예를들어 정보에 파일에 앞서 좋은 아이디어라고 언급했던 에러 정보가 있는지 그렇지 않은지와 같은 정보를 표시해둡니다. 하지만 발매 버젼에서는 이 코드와 데이타는 낭비가 되므로 제거해버립니다. 그래도 버젼 정보를 확인하는 코드만은 남겨두어 파일이 개발 버젼인지 릴리즈 버젼이던지 간에 확인합니다. 그렇지 않다면 최종 버그 테스트 도중 개발 버젼 파일이 사용되어 아무런 확인이나 에러 출력없이 많은 시간을 낭비하게 될 문제를 일으킬 수 있으니까 말이죠.

- Don't require manual exporting.

- 익스포트시에 수작업을 요구하지 마십시오.

Manual exporting breaks the advice of the one-step build. I can't believe how many teams put up with manually exporting things - it should be possible to type "make", and have all your 3D assets reprocessed from original Max/Maya/Lightwave files into the data for your game.

수작업으로 이루어지는 익스포트는 일괄 빌드 공정에 대한 어드바이스를 무시하는 것입니다. 굉장히 많은 팀들이 수작업으로 익스포팅을 하고 있습니다. - 이것은 반드시 "제작" 으로 간주되어야 하며 모든 3D 데이타들은 원본 Max/Maya/Lightwave 파일로 부터 게임에 사용될 데이타로 재가공되어야 합니다.

What happens when you don't do this? Every time you make a change to your 3D format, your artists have to manually re-export everything. When you start a new platform again, everything will have to be manually re-exported.

이렇게 하지 않으면 무슨일이 발생할까요? 여러분이 3D 포맷을 바꿀때마다 디자이너들은 모든 데이타를 수작업으로 다시 익스포트 해야만 합니다. 만약 여러분이 새로운 플랫폼에서 작업하게 된다면 수작업으로 다시 익스포트 해야만 합니다.

Yes, of course, for a previewer function you'll want a "preview" option that will export the data and pop it into your previewer. But when the data actually exports into the game, you want exporting to happen automatically every time you ask it to rebuild your data.

네 물론 익스포트될 데이타를 여러분의 프리뷰어에 띄워보기 원할수도 있습니다. 하지만 실제로 게임에 사용될 데이타라면 여러분은 데이타를 다시 만들때마다 자동으로 익스포트 되길 바랄 것입니다.

3D 익스포터를 위한 자동 일괄 작업

Following the "Make the tool, not the artist, do the non-artistic work", once you've solved the items above, it should be a relatively simple matter to make automatic exporting part of your build process. For Maya, you can use Mayabatch. You can pass Mayabatch a script that your build process creates to load and export a file. For 3D Studio Max, you can do the same with Maxscript by having your build process create a script to load a file, export it and exit Max.

"디자이너들이 그래픽적 업무 외의 일을 하도록 만들지 마십시오" 에 따라 여러분은 위의 문제를 해결 할 수 있습니다. 여러분의 작업 공정에 자동 익스포트를 과정을 넣는다면 상대적으로 쉬운 문제가 될 것입니다. 마야에서는 Mayabatch 를 사용할 수 있습니다. Mayabatch 스크립트를 사용 함으로써 여러분의 빌드 공정 중에 익스포트 파일을 만들고 불러들일 수 있을 것입니다. 3D Max 에서는 Maxscript 로 파일을 부르고 익스포트하고서 맥스를 종료시키는 똑같은 작업을 할 수 있습니다.

Another added benefit of not requiring manual exporting is that your artists will never wonder which Maya/Max/Lightwave file they need to load up, in order to edit an asset. The file they need to load will be the file that's in the build.

수동 작업이 필요 없어질 경우의 또 다른 장점은 디자이너들이 수정 작업을 위해 Maya/Max/Lightwave 파일을 로드할 필요가 없다는 것입니다. !!!그들이 원하는 파일은 작업 공정에 의해 자동으로 처리 될 것입니다.

However, I'm not suggesting there should be no way to manually export. I'm merely suggesting that your tools should be able to build in one step. Your process should facilitate matters, so that if you need to rebuild something, there are no manual steps required. If you need the ogre model rebuilt, you should be able to say something like "rebuild ogre". The alternative is to hunt down the one artist in your company that worked on the ogre, knows which of 45 files named ogre_23.max, ogre26.max, ogre25b.max, ogre-test3.max, and so on need to be loaded, and then where and how to export it. This is not a very appealing process.

하지만 수동 익스포트가 없어야만 한다는 이야기는 아닙니다. 단지 여러분의 익스포터에서 일괄 빌드도 지원해야 한다고 말하고 있는 것입니다. 여러분의 공정을 간단히 만들어 두면 재작업이 필요할 때에 수작업이 필요치 않게 될 것입니다. 만약 여러분이 오우거 모델의 재작업이 필요할때 여러분은 단지 "오우거 재작업" 이라고 말하기만 하면 됩니다만 ogre_23.max, ogre26.max, ogre25b.max ogre-test3.max 와 같은 이름들의 약 45개의 파일중에서 어떤 것을 로드해야 하고 어떻게 익스포트 해야 하는지 알고 있는 회사의 오우거 담당 디자이너를 궁지로 몰아넣는 일입니다. 이것은 절대 매력적인 작업이 아닙니다.

For example, in a recent project, we used some 3rd party tools that didn't follow this advice. We had a character with eight animations. As I was programming, there were several times I had to ask my artist to add a few nodes to the character's hierarchy. Because the system didn't support a one-time build solution, each time he edited the character, he had to hand export the model, and hand export each of the eight animations. This included editing several exporter settings before each export. If the exporter had been designed better, he might need to only press one button to get all nine files exported, after having done it the first time.

예를 한가지 들자면 근래의 프로젝트에서 저희는 이 충고를 따르지 않는 써드 파티 툴을 사용했습니다. 8개의 모션을 사용하는 캐릭터가 있었고 저는 간혹 프로그래밍을 하면서 디자이너의 뼈대에 몇개의 노드를 추가해달라고 부탁하곤 했습니댜. 시스템 차원에서 일괄 빌드 공정을 지원하지 않았기 때문에 매번 그는 캐릭터를 수정하고서 모델을 익스포트 할때마다 8개의 모션을 일일이 익스포트 해야만 했습니다. 또한 익스포트 할때마다 여러가지 옵션도 수정해야만 했습니다. 만약 익스포터가 좀 더 나은 형태로 되어있었다면 그는 버튼 하나를 누름으로써 9개의 처음 설정했던대로 모든 파일을 한번에 익스포트 할 수 있었을 것입니다.

In this case, the multi-stage export is still not the end of the story. The artist had to then take each of the nine exported files and copy them to the correct places in the build. If the tool truly supported a one-step build, that entire ten minute manual labor error prone process would have been reduced to saving the file and saying "done!".

이런 여러가지를 동시에 익스포트 하는 경우에 대해서 아직 이야기가 남아 있습니다. 디자이너들은 9개의 익스포트된 파일들을 일일이 그 파일들이 있어야 할 장소로 옮겨야 합니다. 만약 툴이 일괄 빌드 공정을 지원한다면 전체 10분 가량의 에러 발생 가능성이 있는 작업을 파일을 저장하고서 "작업이 완료되었습니다!" 라고 말해주는 것으로 대체 할 수 있습니다.

There are levels or stages of one-step building. Sometimes, you want an immediate export-like function to iteratively edit an object being used in the current level. Other times, you want to click one button or type one string, and have a particular object or level and all its updated assets re-exported and reprocessed. Other times, you want all of it re-exported and reprocessed from scratch. Or possibly, you might want to rebuild the entire game. Your tools should support all of the above. If your exporter just supports manual exporting, only the first option is available to you. If your exporter is based initially on automated exporting, all the other options are just simple interface issues.

일괄 빌드 공정으로 레벨이나 스테이지에서도 가능합니다. 간혹 여러분은 현재 레벨에서 사용되는 오브젝트들을 수정하고 다시 익스포트하기를 바랄수도 있습니다. 또 어떤 때에는 한번의 버튼 클릭이나 한 문장으로 특정 오브젝트나 레벨등을 모두 업데이트 하고 다시 익스포트 하길 바랄수도 있을 것입니다. 또는 데이타에 손상이 발생했을때 다시 익스포트 하길 원할수도 있을 것입니다. 혹은 게임 전체를 업데이트 하길 원할 수도 있을 것입니다. 부디 여러분의 툴은 이 모든 것들을 지원하십시오. 만약 여러분의 익스포터가 수작업 만을 지원하고 옵션은 여러분만 사용 가능한 것이 될것지만 만약 익스포터가 자동 작업에 기반하고 있다면 다른 모든 옵션들은 단순한 인터페이스적 차원의 문제가 될것입니다.

명세 정보는 익스포트와 구분해서

Some people will read the above ideas and believe what I'm suggesting is a system that uses a specification file, as opposed to a WYSIWYG system, but please don't make that mistake. In other words, some imagine some ugly non artist-friendly text file that specifies what and how to export stuff, versus the common method of exporting that you currently see in the 3D package. Although the ideas above require a specification, that doesn't mean making the spec couldn't be WYSIWYG.

어떤 분들은 위의 아이디어를 읽고 제가 제안하는 명세 파일 시스템이 WYSIWYG 에 반대 되는 것이라고 생각할 수 있습니다만 그렇게 생각하지 말아주십시오. 무엇을 어떻게 익스포트 해야 하는지에 대한 내용을 디자이너들에게 익숙하지 못한 텍스트 파일로 만드는 것은 보기 안 좋을수도 있지만 일반적인 3D 익스포터들과 비교하여 생각해 보십시오. 비록 명세 정보가 필요하지만 이것은 WYSIWYG 로 만들지 말라는 이야기는 아닙니다.

For example you could make a plug-in for your favorite 3D software that looked at the current scene, what's visible and what's not, and generated a specification file for the exporter system. This would essentially give you the same functionality as a normal no-specification file system, but it would have all the advantages above plus more.

예를들어 여러분이 사용하는 3D 소프트웨어에 무엇이 보이고 무엇이 보이지 않는지 현재의 장면을 볼 수 있는 플러그인을 만들고서 익스포트 시스템을 위한 명세 파일을 만들 수도 있습니다. 이것은 본질적으로 명세 파일을 사용하지 않는 시스템과 똑같습니다만 더 많은 장점들을 가지고 있습니다.

For example, with a specification-centered file system, you can have multiple characters per 3D file, and extract each character separately. That would be useful for genres like fighting games, where there are animations and moves that combine two or more players and complex movies such as throws. The artists would find it hugely beneficial to be able to keep both characters in one file, and animate them together.

이 명세 파일 시스템 에는 한번에 여러개의 캐릭터를 넣을수도 있으며 하나씩 구분해서 넣을 수도 있습니다. 이것은 둘 혹은 그 이상 캐릭터들의 동작이나 움직임을 포함시키거나 영화처럼 섞을 수 있으므로 격투 게임 같은 장르에 매우 유용합니다. 디자이너들은 하나의 파일에 캐릭터들을 유지할 수 있고 함께 애니메이션 시킬 수 됨으로써 굉장한 장점을 얻을 수 있을 것입니다.

Another advantage is that using a specification file reduces the chance for human error in the build. Sure, the artist might forget to add something to the spec file if they add a new object in the scene. But the chance for that mistake happens only once, when they add something new or delete something. With a good preview system that will be known almost instantly.

또 다른 장점은 작업 공정 중 발생할 수 있는 에러를 줄여줍니다. 물론 디자이너들이 오브젝트를 추가했을때 명세 파일에 무엇인가 기입하는 것을 잊어버릴 수도 있습니다만 실수가 발생할 수 있는 경우는 단지 무엇인가를 추가하거나 제거할때 한번 뿐입니다. 좋은 프리뷰 시스템이 있다면 이마저도 금방 찾아낼 수 있을것입니다.

In contrast, relying on a manual exporter system creates an opportunity for error every time a file is saved - i.e. every time an animation is tweaked, a texture remapped, a property edited, etc. So, not only is the spec file system more powerful ( allowing multiple animations, characters and other actions per file), but it drastically reduces the chances for errors. All the while, this doesn't restrict the artist from having other scaffolding in the file to help them do their job.

대조적으로 수작업 익스포트 시스템에 의존하면 파일을 세이브 할때마다 에러가 발생할 기회를 만드는 것이 됩니다 - 예를들어 애니메이션은 매번 틀어질것이며, 텍스춰는 다시 씌워지고, 속성은 수정되어 있겠죠. 그렇기 때문에 명세 파일 시스템이 좋은 것입니다 - 파일마다 다중 캐릭터, 모션을 사용 하는 것이 가능해지죠. 이것을 통해 에러가 발생할 여지를 철저히 줄일 수 있게 될것입니다. 어떤 경우에라도 이것은 디자이너들이 그들에 작업에 사용하는 다른 사항들을 제약하지는 않을 것입니다.

Separating the exporter from the specification file generator also gives you unlimited options regarding how to generate the spec. You could:

명세 파일 생성기는 익스포터와 구별해둔다면 사양을 어떻게 만들 것인지에 대해서는 아무런 제약을 받지 않게 될 것입니다.

• Have a "make a spec from what you can currently see" specification plug-in for your favorite 3D package.
• "현재 보이는 것으로 명세 정보를 만든다" 라는 기능의 플러그인을 3D 툴에 추가합니다.
• Make a spec system that specifies by layer what gets exported. Layer 1 could be background graphics, layer 2 could be A.I nodes, layer 3 could be lights, and so on.
• 명세 시스템은 익스포트 되는 것끼리 레이어로 구분한다. Layer 1 은 배경이 될 수 있을것이며, Layer 2 는 A.I 노드, 레이어 3 은 광원과 같은 것이 될것이다.
• Make a spec system that allows you to specify values for each joint per animation, and say whether or not that joint's animation data should be exported or not. This would make it easy to compress and apply secondary animations.
• 명세 시스템이 각 애니메이션의 연결 시점의 값을 설정할 수 있도록 하고 그것을 구분으로 하여 익스포트할지 안할지 결정할 수 있도록 한다. 이것은 2차 모션을 압축할때 매우 유용하다.

If you make your specifications text or XML-based, you'll have the option to hand-create them when needed, on top of generating them like mentioned above.

만약 명세 정보를 텍스트나 XML 로 작성한다면 앞서 언급한 최초의 생성시 수작업 수정도 가능할 것입니다.

In fact, although it can be a cop out, if you make a good exporters that export based on a specification, you can start with hand written specifications. Then, as your team has time and finds new issues to solve, you can make more and better specification generation and editing tools. Those tools could be any of the spec-making plug-ins mentioned above, or they could be Microsoft Infopath-based XML or a web-based editor with a list of each animation, starting and ending frames, and joints to include or exclude. The sky's the limit.

사실 만약 명세에 기반해 익스포트 하는 좋은 익스포터를 만들고 싶다면 여러분은 일일이 손으로 명세를 작성하는 것에서부터 시작하는 것이 좋습니다. 이렇게 함으로써 팀에서는 해결해야 할 새로운 사항들을 발견하게 되며 여러분은 좀 더 명세 생성 시스템을 개선하고 툴을 개선할 수 있게 될 것입니다. 이 툴은 모션의 시작과 끝 프레임의 리스트를 표시하게 되며 앞서 언급했던 사양 제작 플러그인이 될 수도 있으며 MS 의 Infopath-based XML 또는 웹기반 에디터가 될 수도 있습니다.

There's another advantage in solving all of the above issues - the ability to allow the artist to create 3D cut-scenes completely in their favorite 3D package. There's no more having to edit the camera in-game, or assemble all the parts (characters, backgrounds, camera motion, character animations) separately, They can just make the perfect cut-scene using all the features of the 3D package. Then using a spec, either automatically or hand generated, all the required parts can be automatically exported and run through your tool-chain to get into the game.

디자이너들이 3D 컷씬을 만듦에 있어 또 하나의 장점이 있습니다. 더이상 게임에서 카메라를 수정하거나 각 부분들(캐릭터, 배경, 카메라 움직임, 캐릭터 애니메이션)을 조립할 필요가 없다는 것입니다. 디자이너들은 각 부분에 모든 기능들을 사용하여 완벽한 컷씬을 만들 수 있을것입니다. 그리고 자동으로 혹은 수동으로 작성한 명세 정보를 이용하여 자동으로 익스포트하고 게임에서 돌려볼 수 있게 될 것입니다.

You can even merge specs as well. You could pass the tools multiple specs, and they would load all the items referenced by the various specs, export them, and process them into a single bundle of data for loading. This is a great way to bundle together related data that is best edited separately.

또한 명세 정보를 합치는 것도 가능합니다. 툴에 다중 명세 정보를 넣고 관계된 모든 아이템들을 로드하고 익스포트하여 로딩을 위한 하나의 묶음으로 만들어 둘수도 있습니다. 이것은 연관된 데이타를 각자 수정하고 한꺼번에 묶어둘수 있는 굉장한 아이디어 입니다.

결론 : 행복한 디자이너들이 더 멋진 게임을 만듭니다!

I hope this article has pointed out why it's important to design your tools with a philosophy in mind. My impression is that most tools are designed by a programmer, for a programmer, to supply data for other programmers. Therefore, the work flow of the person who is going to use the tools is not carefully considered. Nor are possible ways to avoid errors. Game library code writers are often some of the worst offenders, not because they are not smart, but because their sole goal in writing an exporter is generally to make some test data for their library. No thought is given to using the tool outside of that one small case. I think most tools would benefit from taking these kinds of ideas and philosophies into consideration during their design.

이 글을 통해 저는 왜 철학을 가지고 툴을 디자인하는 것이 중요한지 전하고 싶었습니다. 저는 대부분의 툴이 프로그래머에 의해, 프로그래머를 위해, 다른 프로그래머를 지원하는 데이타를 만들기 위해 디자인된다고 느꼈습니다. 그로인해 실제로 툴을 이용하는 사람의 작업 과정이 고려되지 않습니다. 뿐만 아니라 에러를 피하는 방법도 고려되지 않습니다. 게임 라이브러리를 작성하는 사람들은 대부분 최악의 제공자들입니다. 그들이 뛰어나지 않아서가 아니라 그들의 목표가 라이브러리의 테스트 데이타를 만들기 위해 익스포터를 만들기 때문입니다. 자신 외의 사람들이 툴을 사용하는 경우에 대한 배려가 없습니다. 툴을 설계하는데 있어서 이와 같은 아이디어와 철학을 고려하면서 설계를 해 나간다면 분명히 많은 도움이 되리라 생각합니다.

While some of these ideas might be more work than the simpler solution you are living with now, it only takes one programmer to implement a better solution. The solution will effect, help and benefit 10 to 150 artists, which will more than pay for itself over the course of the project.

이 아이디어들은 여러분이 사용하고 있는 간단한 작업 방식들 보다는 훨씬 나을 것이며, 단지 한사람의 프로그래머에 의해 구현되는 것입니다만 이 작업 방식이 10명에서 150명의 디자이너들에게 영향을 미치고 편의를 제공한다면 프로젝트 전반에 걸쳐 더 많은 이익을 가져다 줄것입니다.

In the end, the more you help your artists, the better job they will be able to do. That's not only going to mean better art and more sales, but it will mean less stress for you and maybe even some compliments from your fellow artists. What, compliments to a programmer from an artist? I bet you thought it was impossible!

마지막으로, 조금 더 디자이너들을 돕는다면 그들은 더 나은 작업을 해낼수 있을 것입니다. 그것은 단지 조금 더 나은 결과물이나 조금 더 많이 팔리기 위해서만은 아닙니다. 하지만 여러분은 더 적은 스트레스를 받게 될 것이며 디자이너들은 여러분에게 감사해 할 것입니다. 디자이너가 프로그래머에게 감사한다? 저는 여러분이 그게 불가능하다고 생각하고 있으리라는데 걸겠습니다.

감사의 말씀

I wanted to thank all the people that helped me with this article. This includes personnel from Atari, Inxile, Humongous, Naughty Dog, Electronic Arts, Capcom, Sony, and Activision.

이 글과 관련하여 저를 도와준 모든 사람들에게 감사를 전하고 싶습니다. Atari, Inxile, Humongous, Naughty Dog, Eelectronic Arts, Capcom, Sony, 그리고 Activision 의 직원분들께도 감사드립니다.

번역문 정보

• 초벌번역: 김민규
• 재벌번역: 포프 이스
• 감수: 이스

현재상태

• 초벌번역완료 (2005년)
• 재벌번역완료 (2005년 10월 1일)
• 감수완료 (2005년 10월 1일)

Binary Space Partioning Trees and Polygon Removal in Real Time 3D Rendering By Samuel Ranta-Eskola

1장 소개

배경

Binary Space Partioning (BSP)-trees were first described in 1969 by Shumacker et al.1, it was hardly meant to be an algorithm used to develop entertainment products, but since the beginning of the 90’s BSP-trees have been used in the gaming industry to improve performance and make it possible to use more details in the maps2. The first game ever to use the technology is Doom, created by John Carmack and John Romero, two legends in the gaming industry.3 Since then almost all First Person Shooting (FPS4) games have been using that technique.

이진공간분할(BSP)트리는 1969년에 Shumacker 등에 의해서 처음 소개되었습니다. 오락 상품들을 개발하는데 이 알고리즘은 거의 사용되지 않았지만 90년대 초반 이후로 성능 향상과 좀더 세밀한 맵의 표현을 가능하게 하기 위해서 게임 산업에서 사용되었습니다. 이 기술을 사용한 첫번째 게임은 게임계의 전설적 존재인 John Carmack 과 John Romero가 개발한 Doom 입니다. 이 이후로 거의 모든 FPS 게임에서는 이 기술이 사용되어 왔습니다.

문제 기술

Because of the tough competition in the gaming industry a lot of work has been done to improve the original design of the algorithm, but we believe improvements can be done. Our main focus has been on moving costly calculations from run time to pre processing time, thus building a structure that holds a lot of information that can be used during run time. Another thing we wish to do with our work is to find ways to improve and optimize surrounding areas in a gaming engine using the strengths of BSP-trees. As a side effect this report can also be considered as a tutorial on how to develop a gaming engine.

게임산업의 치열한 경쟁으로 인해서 이 알고리즘을 향상 시킨 많은 작업들이 이미 있었지만 아직 개선할 사항들이 있다고 여겨집니다. 우리의 주요한 초점은 런타임에서 하는 비용이 많이 드는 계산들을 사전에 미리 계산하는 방식으로 바꿔서 런타임 동안에 사용되는 많은 정보들을 저장하는 하나의 구조체를 만드는 것입니다. 또한 우리는 BSP-tree의 장점을 사용하고 있는 게임엔진에서 연관된 주변 영역들을 향상시키고 최적화 하는 방법들을 알아내는 것입니다. 부수적인 효과로 저희는 이 문서가 게임 엔진 개발 방법에 대한 튜토리얼이 될수도 있다고 생각합니다.

In this report we are going to show:

이 보고서에서 우리는 아래의 내용들을 설명할 것입니다.

What a BSP-tree is.

How to create a BSP-tree.

Advantages / Disadvantages.

Similar techniques that can be used.

The usability of BSP-trees.

- BSP-tree에 대해서

- BSP-tree를 생성하는 방법

- BSP-tree의 장점과 단점

- 사용할수 있는 유사한 기술들

- BSP-tree의 유용성

- 기존의 방식과 우리 방식의 차이

The research for this thesis has been done at a company called O3games [1], which is a Swedish game developer. The results is used in a product released by Cloop Systems, a sister company. We have implemented a fully working BSP-tree with all the surrounding benefits, i.e. the areas where one can use the strengths of a BSP-tree. To support our discussion we are going to use examples from the code we have written. We will use pseudo-code similar to C++, when it is not clear we will analyze the complexity of the algorithm in order to shed light on where optimizations have been done. Most of our graphical examples are illustrated in 2D, but they would work just as well in 3D. Throughout the report the author will assume that the reader have some knowledge about basic concepts in 3D-math and vector algebra.

이 주제에 대한 연구는 스웨덴의 게임 개발 회사인 O3games 회사(http://www.o3games.com) 에서 수행되었습니다. 연구 결과는 자매회사인 Cloop Systems에서 제품을 개발하는데 사용되었습니다. 우리는 BSP-tree와 관련된 모든 이점을 사용하도록 구현했습니다. 즉, BSP-tree의 이점을 적용할 수 있는 모든 부분에 대해 구현하였다는 말입니다. 논의를 뒷받침하기 위해서 저희가 썼던 코드들을 예제로 사용할 것입니다. C++과 유사한 의사코드를 사용 하였으며 이것이 명확하지 않을 경우 어디서 최적화가 되었는지 명백히 설명하기 위해서 알고리즘의 복잡도(complexity)를 분석할 것입니다. 대부분의 그림 예제들은 2D로 보여졌지만 이 예제들은 3D에서도 똑같이 적용됩니다. 보고서 전체에 걸쳐서 저는 독자분들이 3D수학과 벡터 대수에 대해서 약간의 기본적인 개념에 대한 지식을 가지고 있다고 가정합니다.

2장 BSP-TREES

배경

A Binary Space Partitioning-tree is a structure that, as the name suggests, subdivides the space into smaller sets. These days, given hardware accelerated Z-buffers; the benefit of this is that one has a smaller amount of data to consider given a location in space. But in the beginning of the 90’s the main reason BSP-trees were being used was that they sorted the polygons in the scene so that you always drew back-to-front, meaning that the polygon with the lowest Z-value5 was drawn last. There are other ways to sort the polygons so that the closest polygon is drawn last, for example the Painter’s algorithm6, but few are as cheap as BSP-trees, because the sorting of the polygons is done during the pre-processing7 of the map and not under run- time. The algorithm for generating a BSP-tree is actually an extension of Painter’s algorithm.8 Just as the original design of the BSP algorithm, the Painter’s algorithm works by drawing the polygons in the scene in back-tofront order. However, there are some major drawbacks with Painter’s algorithm:

BSP(Binary Space Partioning) tree는 이름에서 말해 주듯 공간을 작은 집합으로 나누는 것입니다. 오늘날에는 하드웨어 가속 Z-버퍼가 있기 때문에 BSP를 사용함으로써 주는 이점은 공간상에 어떤 위치가 주어졌을떄 고려해야하는 데이터의 양이 점점 더 작아진다는 점입니다. 하지만 90년대 초반에 BSP-tree를 사용하는 이유는 월드상의 폴리곤들을 정렬하기 위해서 인데 이렇게 하여 정렬된 폴리곤을 뒤에서 부터 앞의 순서로 그림으로써 가장 적은 z값을 가지는 폴리곤을 마지막에 그리려고 했기 때문입니다. 이렇게 폴리곤을 정렬해서 가장 가까운 폴리곤을 가장 나중에 그리게 해주는 다른 방법들이 있는데 예를 들자면 Painter's 알고리즘등 입니다. 그러나 BSP-tree 만큼 싸게 실행될 수 없었는데 이유는 맵상의 폴리곤 정렬이 런타임시 계산되는 것이 아니라 미리 계산되기 때문입니다. 사실상 BSP-tree 를 생성하는 알고리즘은 Painter's 알고리즘의 확장입니다. BSP 알고리즘의 원래 설계인 Painter's 알고리즘은 폴리곤을 뒤에서 부터 앞의 순서로 그리도록 작동합니다. 하지만 Painter's 알고리즘에는 몇 가지 주요한 단점이 있습니다.

Polygons will not be drawn correctly if they pass through any other polygon.

It is difficult and computationally expensive to calculate the order that the polygons should be drawn in for each frame.

Painter's 알고리즘은 폴리곤들이 어떤 다른 폴리곤을 통과하게 된다면 이 폴리곤들은 제대로 그려지지 못합니다. 이 알고리즘에서 각 프레임마다 폴리곤들을 어떻게 그릴것인가에 대한 순서를 계산하는 것은 값비싼 비용이 들며 어렵습니다.

<Figure 1. cyclic overlap>

The BSP algorithm BSP 알고리즘

The original idea for the creation of a BSP-tree is that you take a set of polygons that is part of a scene and divide them into smaller sets, where each subset is a convex set of polygons. That is that each polygon in this subset is in front of every other polygon in the same set. Polygon 1 is in front of polygon 2 if each vertex in polygon 1 is on the positive side of the plane polygon 2 defines or in that plane that. A cube made of inward facing polygons is a convex set, whilst a cube made of outwards facing polygons is not.

BSP 트리 생성에 대한 원래 아이디어는 장면의 한 부분을 이루는 폴리곤들의 집합을 취해서 이 폴리곤들의 집합을 더 작은 작은 집합들로 나누는 것입니다. 이때 각 부분 집합들은 폴리곤들의 볼록집합(convex set)입니다. 다시 말해 이 부분집합에서 각 폴리곤들은 같은 집합에서 모든 폴리곤 앞에 놓인다는 것을 의미합니다. 폴리곤1에서 각 정점이 폴리곤 2로 정의되는 평면의 양의 부분에 놓이거나 그 평면에 있다면 폴리곤 1은 폴리곤 2앞에 있습니다. 서로 안쪽으로 마주보고 있는 폴리곤들은 볼록집합이며 반면에 바깥쪽을 향해 있는 면들로 이루어진 상자는 볼록집합이 아닙니다.

Figure 2. The difference between a convex set and a non-convex set. 그림 2. 볼록집합과 오목집합의 차이

The functions needed to determine whether a set of polygons is a convex set would look like this:

폴리곤들의 집합이 볼록집합인지 아닌지를 결정하는 함수는 아래처럼 보일것입니다.

재벌중

POLYGON_INFRONT 함수는 non-symmetric 비교입니다. 이 뜻은 폴리곤2가 폴리곤1의 앞에 있다고 해서 반드시 폴리곤1이 폴리곤2의 앞이 라고 할 수 없다는 것입니다. 다음 그림을 통해서 쉽게 아실수 있습니다.

<Figure 3. The non-symmetric nature of the comparison POLYGON_INFRONT>

POLYGON-INFRONT (Polygon1, Polygon2)1 for each point p in Polygon22 if (CLASSIFY-POINT (Polygon1, p) <> INFRONT)3 then return false4 return true

w IS-CONVEX-SETw Indata: w PolygonSet – The set of polygons to check for convexity w Outdata: w Whether the set is convex or notw Effect: w Checks each polygon against each other polygon, to see if they are w in front of each other, if any two polygons doesn’t fulfill that w criteria the set isn’t convex.

IS-CONVEX-SET (PolygonSet)1 for i f 0 to PolygonSet.Length ()2 for j f 0 to PolygonSet.Length ()3 if(i <> j && not POLYGON-INFRONT(PolygonSet[i], PolygonSet[j]))4 then return false5 return true

The function POLYGON-INFRONT is a non-symmetric comparison, meaning that if Polygon2 is in front of Polygon1 it does not necessarily imply that Polygon1 is in front of Polygon2. This can easily be shown with the following example:

Figure 3. The non-symmetric nature of the comparison POLYGON-INFRONT

In Figure 3 Polygon1 is in front of Polygon2 since both p3 and p4 is on the positive side of Polygon2, but Polygon2 is not in front of Polygon1 since p2 is behind Polygon1.

그림 3에서 폴리곤1은 폴리곤2의 앞에 있습니다. 왜냐하면 p3 과 p4 모두 폴리곤2의 양의 방향에 존재하기 때문입니다. 하지만 폴리곤2는 폴리곤1의 앞에 있지 않습니다. p2가 폴리곤1의 뒤에 있기 때문입니다.

The idea can be slightly modified as the need of convex sets is not as acute when you can use hardware accelerated Z-buffers. Later in this chapter it will be described how this was solved.

볼록집합의 필요에 대한 생각은 약간 수정이 가능한데 이것은 하드웨어 가속 Z 버퍼를 사용할 수 있을 때는 그렇게 민감하지 않기 때문입니다. 이 장의 마지막에 이 문제에 대해 언급하겠습니다.

The structures needed for a BSP-tree can be defined as follows:

BSP-tree 정의에 필요한 구조체들은 다음과 같습니다.

class BSPTree {

BSPTreeNode RootNode w The root node of the tree. }

class BSPTreeNode

{

BSPTree Tree w The tree this node belongs to.

BSPTreePolygon Divider w The polygon that lies in middle

w of the two sub trees.

BSPTreeNode *RightChild w The right sub tree of this node.

BSPTreeNode *LeftChild w The left sub tree of this node.

BSPTreePolygon PolygonSet[] w The set of polygons in this node. }

class BSPTreePolygon

{

3DVector Point1 w Vertex 1 in the polygon.

3DVector Point3 w Vertex 2 in the polygon.

3DVector Point3 w Vertex 3 in the polygon. }

As you can see each polygon is represented by only three points. This is because the hardware in graphic cards is designed to draw triangles. But the algorithm for generating BSP-trees is designed to take care of polygons with any number of points, as long as all points are in the same plane.

위를 보면 알수 있듯이 폴리곤은 단순히 3개의 점으로 구성됩니다. 그 이유는 하드웨어인 그래픽카드가 삼각형을 그리도록 설계 되있기 때문입니다. 그러나 BSP-tree 를 생성하기 위한 알고리즘은 폴리곤이 몇 개의 점을 가지든지 상관없이 점들이 한 평면상에 존재하기만 한다면 적용할 수 있습니다. 

There are several ways to split up the set of polygons into smaller subsets. For example, you can choose an arbitrary plane in space and divide the polygons by putting the ones on the positive side of the plane in the right sub tree and the polygons on the negative side in the left sub tree. The problem with this approach is that it is very difficult to find a plane that divides the polygons into two approximately equally sized sets, since there are an infinite set of planes in space. So the most common way to do this is by taking one of the polygons in the scene and dividing the polygons according to the plane that polygon defines.

폴리곤 집합을 작은 부분 집합으로 나누는 방법은 여러가지가 있습니다. 예를 들어, 공간에 임의의 한 평면을 정의하여 이 평면에 양의 방향에 있는 폴리곤 집합을 오른쪽 트리로 넣고 음의 방향에 있는 폴리곤 집합을 왼쪽 트리로 넣을 수 있습니다. 문제는 이런 접급 방식으로는 왼쪽,오른쪽 트리의 사이즈를 거의 같게 나누는 평면을 찾기가 매우 힘듭니다. 왜냐면 공간에는 무한의 평면 집합이 존재하기 때문입니다. 따라서 일반적으로 쓰이는 방법은 공간에 있는 폴리곤중에 하나를 선택하여 이 폴리곤으로 정의 되는 면을 기준으로 폴리곤들을 나누는 것입니다.

We have defined an algorithm, POLYGON-INFRONT, which can classify whether a polygon is on the positive side of another polygon. Now we need to modify that algorithm to be able to also determine whether the polygon is spanning the plane defined by the other polygon. The algorithm is defined as follows:

우리는 한 폴리곤이 다른 폴리곤의 앞에 있는지를 구별해주는 POLYGON_INFRONT 알고리즘을 정의했습니다. 이제는 한 폴리곤이 다른 폴리곤으로 정의되는 면을 분할하는지(spanning)의 여부도 판단할 수 있도록 이 알고리즘을 수정할 필요가 있습니다. 알고리즘은 다음과 같이 정의 될 수 있습니다.

w CALCULATE-SIDE w Indata : w Polygon1 – The polygon to classify the other polygon against w Polygon2 – The polygon to classify w Outdata : w Which side of polygon1 polygon 2 is located on. w Effect: w Classifies each point in the second polygon versus the w first polygon. If there are points on the positive side but no w points on the negative side, Polygon2 is considered to be in front w of Polygon1. If there are points on the negative side but no w points on the positive side, Polygon2 is considered to be behind w Polygon1. If all points are coinciding polygon2 is considered to w be coinciding with Polygon1. The last possible case is that there w are points on both the positive and the negative side, then w polygon2 is considered to be spanning Polygon1.

CALCULATE-SIDE (Polygon1, Polygon2)1 NumPositive f 0, NumNegative f 0 2 for each point p in Polygon23 if (CLASSIFY-POINT (Polygon1, p) = INFRONT)4 then NumPositive = NumPositive + 1 5 if (CLASSIFY-POINT (Polygon1, p) = BEHIND)6 then NumNegative = NumNegative + 17 if (NumPositive > 0 && NumNegative = 0)8 then return INFRONT 9 else if(NumPositive = 0 && NumNegative > 0)10 then return BEHIND 11 else if(NumPositive = 0 && NumNegative = 0)12 then return COINCIDING 13 else return SPANNING

This gives us a problem when it comes to determining which subset a polygon that is spanning the plane should be placed in. The algorithm deals with this by splitting such a polygon into two polygons. This also solves two of the problems in Painter’s algorithm, namely cyclic overlap and intersecting polygons. Below is example of how a polygon is splitted:

여기서 문제가 하나 생기는데 면을 분할하는 폴리곤일 경우 어떤 부분집합에 들어가야 하는지 선택해야 합니다. BSP-tree 알고리즘은 이럴 경우 폴리곤을 분할하여 두 개로 만들어 처리합니다. 이렇게 함으로써 Painter's 알고리즘이 가지고 있는 두 가지 문제점, 순환해서 겹쳐진 폴리곤 문제와 서로 교차하는 폴리곤 문제를 해결하게 됩니다. 다음 예제는 어떻게 폴리곤을 분할하는지 보여줍니다.

Figure 4. Splitting a polygon

In the figure above Polygon1 is the classifying polygon and Polygon2 is the polygon that is classified. Since Polygon2 is spanning the plane defined by Polygon1 it has to be splitted. The result is the picture to the right. Polygon2 is now completely in front of Polygon1 and Polygon3 is completely behind. The glitch between Polygon2 and Polygon3 is just there to illustrate that it is two separate polygons, after a split the two resulting polygons will be adjacent to each other.

위의 그림에서 폴리곤1을 기준이 되는 폴리곤이며 폴리곤2를 분류대상이 되는 폴리곤입니다. 폴리곤2가 폴리곤1로 정의되는 면을 분할하므로 폴리곤2는 분할될 필요가 있습니다. 그 결과가 오른쪽 그림입니다. 이제 폴리곤2는 완전하게 폴리곤1에 앞에 있으며 폴리곤3은 완전하게 뒤에 있습니다. 폴리곤2와 폴리곤3의 미세한 여백은 단지 그림에서 두 폴리곤을 구분하기 위해 표시한 것입니다. 실제로 나누어진 후의 두 폴리곤은 맞닿아 있습니다.

When a BSP-tree is created, one has to decide whether the need is of a balanced tree, meaning that there should not be too big a difference in depth between the left and the right sub tree of each node, or try to limit the number of splits, since each split creates new polygons. If too many new polygons is created during the BSP-tree creation the graphic card will have a hard time rendering the map, thus reducing the frame rate, while a unbalanced tree will require more expensive traversal of the tree. We decided to accept a certain number of splits in order to get a more balanced tree. But the main concern was reducing the number of new polygons created. Below is our loop for choosing the best dividing polygon from a set of polygons:

BSP-tree를 생성할 때 트리의 균형성과 폴리곤 분할 횟수 제한, 이 두가지 중에 어느 것에 중점을 둘지 결정해야 합니다. 트리의 균형성이란 왼쪽 트리의 노드 깊이와 오른쪽 트리의 노드 깊이의 차이가 많지 않아야 함을 의미합니다. (balanced tree) 폴리곤 분할 횟수 제한은 폴리곤 분할로 새롭게 생성되는 폴리곤의 수를 제한한다는 의미입니다. 만약에 BSP-tree 생성중에 너무 많은 수의 폴리곤이 생성된다면 맵을 렌더링하기 위해 그래픽카드는 힘든 시간을 가질 것이며 프레임율은 떨어질 것입니다. 또한 BSP-tree가 비균형적으로 생성되면 탐색할 때 비싼 비용을 요구하게 됩니다. 우리는 보다 균형적인 트리를 얻기 위해서 약간의 폴리곤 분할을 감수하기로 결정했습니다. 하지만 주된 관심사는 폴리곤 분할로 생성되는 새로운 폴리곤의 수를 줄이는데 있습니다. 아래 의사코드는 폴리곤 집합중에 가장 좋은 기준이 되는 폴리곤을 선택하는 방식을 나타냅니다.

w CHOOSE-DIVIDING-POLYGONw Indata: w PolygonSet – The set of polygons to search for the best dividing w polygon.w Outdata: w The best dividing polygonw Effect: w Searches through the set of polygons and returns the polygons that w splits the set into the two best resulting sets. If the set is w convex no polygon can be returned.

CHOOSE-DIVIDING-POLYGON (PolygonSet)1 if (IS-CONVEX-SET (PolygonSet))2 then return NOPOLYGON3 MinRelation f MINIMUMRELATION4 BestPolygon f NOPOLYGON5 LeastSplits f INFINITY6 BestRelation f 0

w Loop to find the polygon that best divides the set.

7 while(BestPolygon = NOPOLYGON)8 for each polygon P1 in PolygonSet9 if (Polygon P1 has not been used as divider previously

during the creation of the tree)

w Count the number of polygons on the positive side, negative side w of and spanning the plane defined by the current polygon. 10 NumPositive f 0, NumNegative f 0, NumSpanning f 0 11 for each polygon P2 in PolygonSet except P1

12 Value = CALCULATE-SIDE(P1, P2)13 if(Value = INFRONT)14 NumPositive = NumPositive + 115 else if(Value = BEHIND)16 NumNegative = NumNegative + 117 else if(Value = SPANNING)18 NumSpanning = NumSpanning + 1

w Calculate the relation between the number of polygons in the two w sets divided by the current polygon.

19 if (NumPositive < NumNegative)20 Relation = NumPositive / NumNegative21 else22 Relation = NumNegative / NumPositive

w Compare the results given by the current polygon to the best this w far. If the this polygon splits fewer polygons and the relation w between the resulting sets is acceptable this is the new candidate w polygon. If the current polygon splits the same amount of polygons w as the best polygon this far and the relation between the two w resulting sets is better -> this polygon is the new candidate w polygon.

23 if (Relation > MinRelation &&

(NumSpanning < LeastSplits ||

(NumSpanning = LeastSplits &&

Relation > BestRelation))24 BestPolygon f P1 25 LeastSplits f NumSpanning26 BestRelation f Relation

w Decrease the number least acceptable relation by dividing it with w a predefined constant. 27 MinRelation f MinRelation / MINRELATIONSCALE 28 return BestPolygon

Complexity analysis: Because of the while loop it is very hard to find a bound to this function. Depending of the structure of the scene the while loop might loop for a very long time. The MINRELATIONSCALE is what decides how much the acceptable relation decreases per iteration, thus how long it will take before the minimum relation will be small enough to accept the best possible solution. The worst case is that we have a set consisting of n polygons that is not a convex set and the best possible solution is a dividing polygon that splits the set into one part consisting of n-1 polygons and another set consisting of 1 polygon. This solution will only be acceptable when the minimal acceptable relation is less than 1/(n-1) (see line 19-23 in the algorithm). Meaning that MinRelation / MINRELATIONSCALEi < 1/(n-1) where i is the number of iterations in the loop, this is due the division by MINRELATIONSCALE at line 27 in the algorithm. Let’s assume that the initial value for MinRelation is 1, which is the highest possible value since the relation is always between 0 and 1 (see lines 19-22 in the algorithm). We have:

while 루프 때문에 이 함수의 실행 범위를 찾는 것은 매우 어렵습니다. 씬의 구조에 따라서 while 루프가 많은 시간을 돌아갈지도 모릅니다. MINRELATIONSCALE 값은 수용할 수 있는 최소 상대치(MinRelation)가 한번의 반복마다 얼만큼 줄어드는지를 뜻하며, 따라서 최소 상대치가 최적의 답을 찾을수 있을 정도로 줄어드는데 어느 정도의 시간이 걸리는지 나타냅니다. // 여기서 상대치라는 표현은 트리의 균형성을 말합니다. 0부터 1사이의 값으로 1에 가까울 수록 보다 균형적이라는 뜻입니다. MINRELATIONSCALE 값이 크면 최소로 요구되는 균형성이 빨리 적어지므로 기준이되는 폴리곤을 보다 빨리 찾게 될 것입니다. //

최악의 경우는 n개의 폴리곤 집합이 볼록집합이 아니면서 최적의 나눔이 한쪽은 1개의 폴리곤을 가지고 다른 한쪽은 n-1개의 폴리곤을 가지게 되는 경우입니다. 이런 경우는 최소 수용 가능 상대치가 1/(n-1) 보다 작을때 가능합니다. 이것은 의사코드의 27번째 라인에서 볼수 있듯이 i를 루프가 반복된 횟수라고 했을때 MinRelation/MINRELATIONSCALE^i < 1/(n-1)인 경우를 의미합니다. 만약에 최초의 MinRelation 값을 1이라고 했다면 (1은 균형성이 가장 좋은 값으로 MinRelation이 가질수 있는 최대값) 

1 / MINRELATIONSCALEi < 1/(n-1) 1 < MINRELATIONSCALEi/(n-1) (n-1) < MINRELATIONSCALEi

logMINRELATIONSCALE (n-1) < i This is no upper bound for i, but since i will be very close to logMINRELATIONSCALE (n-1) we will, for simplicity assume they are equal. Another practical assumption to make is that MINRELATIONSCALE always should be greater than or equal to 2. Thus giving us:

여기서 i(루프 반복 횟수)의 최대값은 없습니다. 하지만 i의 값이 최소값에 매우 가까울 것이기 때문에 단순화하여 그 두 값이 같다고 생각할 수 있습니다. 또한 실제적으로 MINRELATIONSCALE값이 항상 2보다 크거나 같다고 가정하게 되면 다음과 같이 됩니다.

logMINRELATIONSCALE (n-1) = i MINRELATIONSCALE >= 2 i = logMINRELATIONSCALE (n-1) < lg(n-1) = O(lg n)

Inside the while loop, there are two iterations over the set of polygons. Giving us that the worst case behavior of this algorithm is of order O(n2 lg n), but the typical behavior is almost always closer to O(n2) as there tend to exist a polygon that will fulfill the requirements in the first iteration.

while 루프안에서 폴리곤 집합에 대해 두 개의 반복문이 존재합니다. 이것으로 최악의 경우를 따져본다면 O(N^2 LogN)이지만 전형적으로 대부분의 경우 첫번째 반복에서 조건에 맞는 폴리곤이 발견되는 O(N^2)에 가깝습니다.

The loop in CHOOSE-DIVIDING-POLYGON might look as if there are cases where it will not terminate, but this is not true since if the set of polygons is a non-convex set there is always one polygon that can divide the polygons into two sets. CHOOSE-DIVIDINGPOLYGON selects the polygon that splits the least number of polygons. To prevent from choosing polygons that would not divide the set, the relation between the sizes of the two resulting sets must be better than a threshold value. To better illustrate this we show an example where choosing the polygon that splits the fewest amount of polygons would render in an infinite loop:

CHOOSE_DIVIDING_POYGON에 있는 루프가 끝나지 않을 경우가 있을것 처럼 보일지도 모르겠습니다. 하지만 이것은 사실이 아닙니다. 왜냐하면 폴리곤 집합이 볼록집합이 아닐 경우에 두 가지 집합으로 나눌수 있는 폴리곤이 항상 한 개는 존재하기 때문입니다. CHOOSE_DIVIDING_POYGON은 폴리곤 분할 횟수가 가정 적은 폴리곤을 선택합니다. 여기서 집합을 전혀 나누지 않는 폴리곤 선택을 피하기 위해 나누어진 양쪽 트리 크기의 균형성을 나타내는 상대치(Relation) 값이 미리 정의된 최소 상대치(MinRelation) 값보다 반드시 커야만 하는 조건이 있습니다. 이것을 보다 잘 설명하기 위해서 가장 적은 수의 폴리곤 분할을 하는 기준 폴리곤을 선택하는데 무한 루프를 돌거 같은 예제를 들겠습니다.

Figure 5. Problems when choosing dividing polygon.

In the above example choosing either polygon 1,6,7 or 8 would not render in the split of any polygon, but on the other hand each of the polygons in the set is on the positive side of those polygons, so in the next loop the same polygon would be chosen again, rendering in a infinite loop. As a matter of fact 1,2,3 and 4 is on the border of the least convex hull that can hold the polygon set, polygons for which this is true cannot be used as a dividing polygon since all other polygons in the set is on the positive side of them. Choosing polygon 2,3,4 or 5 would each cause one split but it would also divide the set into two smaller sets.

위의 예제에서 1,6,7,8폴리곤을 기준 폴리곤으로 선택하게 되면 어떤 폴리곤 분할도 하지 않습니다. 반면에 이 기준 폴리곤 이외의 모든 폴리곤들은 기준 폴리곤의 앞에 존재 하게 되며 다음 루프로 넘어가게 됩니다. 하지만 다음 루프에서 역시 1,6,7,8 폴리곤이 다시 선택되게 되어 무한 루프가 발생할 것 처럼 보일 수 있습니다. 사실 1,6,7,8 // 원래 1,2,3,4 인데 오타 같습니다. //폴리곤은 전체 폴리곤 집합을 가질 수 있는 최소볼록집합(convex hull)의 경계선 위에 있습니다. 이 폴리곤들은 기준 폴리곤이 될 수 없는데 왜냐하면 다른 모든 폴리곤들이 양의 방향쪽으로만 있기 때문입니다. 2,3,4,5 폴리곤들중에 기준 폴리곤을 선택하게 되면 한번의 폴리곤 분할이 일어나게 되지만 두 개의 보다 작은 집합들로 나눠지게 됩니다.

Another reason why a it is not always good to choose the polygon that splits the fewest polygons is that in most cases that heuristic will render in a unbalanced set. A balanced tree will perform better during runtime than an unbalanced one.

또한 폴리곤 분할이 최소로 일어나는 폴리곤을 기준으로 잡는 것이 항상 좋은 선택이 될수 없는 이유는 대부분의 경우 비균형적인 트리를 만들기 때문입니다. 균형적인 트리가 비균형적인 것보다 런타임에서 보다 좋은 성능을 낼 것입니다.

When the best polygon has been chosen the rest of the polygons is divided according to that polygon. There are two ways to do deal with the dividing polygon:

최적의 기준 폴리곤이 선택되면 남은 폴리곤들의 집합은 기준 폴리곤에 의하여 부분 집합으로 나누어지게 됩니다. 그리고 이 기준 폴리곤을 다루는 법은 두 가지가 있습니다.

A leafy tree can be created, meaning that all polygons are put into the leaf nodes, thus the dividing polygons have to be categorized to be on one of the sides. In our example we count the polygons in the same plane as the dividing polygon as being on the positive side of the plane.

1. 리프가 많은 트리가 생성될 수 있습니다. 이것이 의미하는 바는 모든 폴리곤들을 리프 노드들에 넣는 것으로 기준 폴리곤 역시 두 개의 트리중 한 쪽에 포함되게 합니다. 우리 예제에서는 기준 폴리곤을 양의 방향쪽에 있다고 정하여 양의 방향 트리에 포함 시킵니다.

The other way is to store the dividing polygons in the internal nodes. This process is repeated for each sub tree until each leaf contains a convex set of polygons.

2. 다른 방법으로 노드들의 내부에 기준 폴리곤을 저장합니다. 이 방식은 각각의 부분 집합에 대해서 볼록집합(convex set)이 될때까지 반복됩니다.

The algorithm for generating a leafy BSP-tree looks like this:

BSP-tree 를 생성하는 알고리즘은 다음과 같습니다.

w GENERATE-BSP-TREE w Indata: w Node – The sub tree to build of the type BSPTreeNode.w PolygonSet – The set of polygons to create a BSP-tree from. w Outdata: w A BSP-tree stored in the incoming node.w Effect: w Generates a BSP-tree out of a set of polygons.

GENERATE-BSP-TREE (Node, PolygonSet)1 if (IS-CONVEX-SET (PolygonSet))2 Tree f BSPTreeNode (PolygonSet)3 Divider f CHOOSE-DIVIDING-POLYGON (PolygonSet)4 PositiveSet f {}5 NegativeSet f {}

6 for each polygon P1 in PolygonSet

7 Value f CALCULATE-SIDE (Divider, P1)8 if(Value = INFRONT)9 PositiveSet f PositiveSet U P1 10 else if (Value = BEHIND)11 NegativeSet f NegativeSet U P1 12 else if (Value = SPANNING)

13 Split_Polygon10 (P1, Divider, Front, Back)14 PositiveSet f PositiveSet U Front 15 NegativeSet f NegativeSet U Back 16 GENERATE-BSP-TREE (Tree.RightChild, PositiveSet) 17 GENERATE-BSP-TREE (Tree.LeftChild, NegativeSet)

Complexity analysis:The call to CHOOSE-DIVIDING-POLYGON is of order O(n2 lg n), which dominates the rest of the function except for the recursive calls. If we assume that the division of the polygon set is fairly even we can formulate the following function to calculate the bounds of GENERATE-BSP-TREE:T(n) = 2T(n/2) + O(n2 lg n)

CHOOSE_DIVIDING_POLYGON을 호출하는 것은 O(N^2 LogN) 정도의 Complexity를 가지게 되며, 이것이 재귀함수 호출 부분을 뺀 나머지 함수 부분을 좌우하게 됩니다. 만약에 우리가 폴리곤 집합을 나누는 것이 명확히 짝으로 떨어진다고 가정한다면 GENERATE_BSP_TREE 범위를 다음 같이 계산하여 식을 세울수 있게 됩니다.

T(n) = 2T(N/2) + O(N^2 LogN)

Using Masters Theorem11 we get that the order of complexity is Q (n2 lg n), where n is the number of polygons in the incoming set.

Master's Theorem 을 사용하면 O(N^2 logN)을 얻을 수 있습니다. 여기서 N 은 폴리곤 집합 안에 있는 폴리곤들의 개수를 의미합니다.

10 [Silicon Graphics. BSP Tree Frequently Asked Questions (FAQ)]

Following there is an example of how a BSP-tree is generated. The structure below is the original set of polygons, we have numbered them to make the example easier to follow. This set of polygons is going to be divided into a BSP-tree.

이어지는 예제는 BSP-tree가 어떻게 생성되는지 보여줍니다. 밑에 구조는 원래의 폴리곤 집합을 보여주며 예제 설명을 쉽게 하기 위해 각각의 폴리곤에 넘버링을 하였습니다. 이 폴리곤 집합이 분할되어 BSP-tree가 되는 것입니다.

Figure 6. Example structure

To be able to run the algorithm we must choose a couple of constants, namely: MINIMUMRELATION and MINRELATIONSCALE. We found that choosing MINIMUMRELATION = 0.8 and MINRELATIONSCALE = 2 will give quite good result, but one can experiment we those numbers. The higher the MINIMUMRELATION is the better balanced the tree will be, but the number of splitted polygons will probably increase too.

알고리즘을 실행하기 위해서는 MINIMUMRELATION 과 MINRELATIONSCALE 상수들을 먼저 정해주어야 합니다. 우리는 이것을 각각 0.8과 2로 잡는 것이 매우 좋은 결과를 낳는 것을 발견했습니다. 그러나 다른 숫자들로 실험할 수도 있습니다. MINIMUMRELATION 값이 클수록 보다 좋은 균형의 트리가 생성되지만 폴리곤 분할 횟수가 증가하게 될 것 입니다.

The starting set of polygons is obviously not a convex set, so a dividing polygon will be chosen. After a quick glance at the structure we can see that polygons {1,2,6,22,28} cannot be used as dividing polygons since they define convex hull that contains the whole set of polygons. But all the other polygons are candidates for being dividing polygon. The polygons that split the fewest number of polygons and give the best relation between the sizes of the two resulting sets are 16 and 17, they lie on the same line and do not split any other polygon. The two resulting sets is almost equally sized namely |negative|= 15 and |positive| = 13 polygons in each of the resulting sets. Let us choose polygon 16 as the divider. The result will look as follows:

최초로 주어진 폴리곤 집합은 명확히 볼록집합이 아님을 알수 있고, 따라서 기준 폴리곤을 선택할 수 있습니다. 일단 훑어보게 되면 {1,2,6,22,28} 폴리곤들은 분할 기준이 될수 없음을 알 수 있습니다. 왜냐하면 최소볼록집합�