This week I was a little busy, unfortunately, with moving in and working on another project for another class, COMP 491 - Teaching in Computer Science. I attented the first of RUSP's weekly meetings and touched bases again with Dr. Warren.

We agreed that the techniques I had experimented with during the summer of 2002 were not adequate to generate high level geometry. Instead, the geometry could possibly created as a tree of some kind of building blocks. The algorithms borrowed from texture synthesis could then be used to fill in detail by converting the building blocks into some discrete representation, like isosurfaces.

I have started thinking about how such a graph could be constructed. There should be different classes of building blocks, such as boxes, cylinders, perhaps extruded curves, and of course, pre-made polygonal geometry. The user should have the possibility to enable or disable these blocks by category and to select options for connectivity, minimum and maximum distance to other existing building blocks, for example, or alignment options. The latter would, for example, make sure that the floors of all blocks are only a few inches apart, making it navigatable by foot, if desired. Transformations such as scaling and rotation should also be controllable.

Building blocks are then randomly picked according to the user's options, and the algorithm verifies that the location picked is valid. If it is not, another location is selected.

I can see how this general algorithm can create levels for a computer game, but I would also like to create architecture that makes sense in our world, and I have problems seeing how an actual house could be generated. Maybe there could be soft boundaries to represent the general shape of the house, and then rooms could be placed in a best-fit fashion.

top of page

My COMP 491 project is hopefully nearing completion, so it will not be in the way as much anymore. I started setting up this website for RUSP and will make weekly reports, references, images and downloads available here.

I will also maintain a glossary on this website to make it easier for strangers to the field to understand my research. If you find anything on this website that needs further explanation, please email me at mgricken at rice dot edu.

The topic of this week's class is effective communication. I am looking forward to this class, since on Friday I will be lecturing COMP 212 all by myself for the first time ever. I know I have problems using the projector effectively.

I have still been working with Dr. Nguyen on my COMP 491 project a lot. The paper submission deadline for SIGCSE is next Friday, so I will probably be a little preoccupied for another week, unfortunately.

I have continued laying down requirements for the high-level generation of the geometry, though. The user should be able to pick several primitives to make up the geometry, such as boxes, cylinders, and pre-fabricated polygonal shapes. This allows the user to force the algorithm into adhering to a certain style.

These primitives can be scaled, rotated, and translated by the algorithm, but only according to rules specified by the user. There have to be parameters to put minimum and maximum limits on all values, to make them proportional to each other, and to make them granular. Granularity could then, for example, be used to create separate floors: All floors have to start at a Z coordinate which is a multiple of 100.

Placement seems complicated at this point. It should be possible to create minimum distances to objects that have already been placed. This would allow us to generate walls of arbitrary thickness between the objects. On the other hand, however, the user might not want to have too much space inbetween objects, so a maximum distance is necessary, too. Overlap between objects should generally be allowed. The overall geometry gets generated by the union of all objects, so overlap is inconsequential.

Connecting two objects in a realistic fashion is something that will also take a lot of thought. In existing architecture, rooms are often connected by doors or passages, which are geometrically very small boxes. This could be enforced by alternating between large and small objects and forcing them to connect, i.e. making the maximum distance between them 0. On the other hand, we do not want this to happen all the time. There are probably criteria for this that I have not yet understood.

An algorithm to do this could abstractly look like this:

1. Place a root object
2. Pick an existing parent object P
3. Pick a new object N. If P is large, make N small, and vice versa.
4. Place N as a child of P with correct parameters (scaling, rotation, etc.) so that it does not overlap with any other objects except for possibly P
5. Go to 2 and repeat

This algorithm creates perfect mazes, i.e. there is one and only one way from each node to each other. This is probably not desirable in most cases: In most houses, there are multiple ways from one room to another. These situations can be created by inserting additional passages between objects, as described by step 4a below:

4a. If N is large, check if N is close enough to other large objects L_i that already exist; if they are close enough, there is a probability P_connect that governs whether N and L_i should be connected by another small object.

A post-processing step might be helpful, too, which can shrink or enlarge existing objects to enforce minimum and maximum distances between objects.

I am not sure how to pick locations for new objects, though. There often are infinitely many locations that are acceptable and just as many that do not work. Random placement and subsequent checking of the location is acceptable thus seems impractical.

Dr. Warren suggested I randomly lay out points first and, depending on the distance between them, connect them with edges. This graph should then be used for the placement of the objects. This seems like a good plan, since it also gives the user more control at a very early stage of the generation: Points could be moved around if desired, or the graph could entirely be created by hand. The main benefit, however, is a deterministic run-time. Random runtimes are generally bad :)

top of page

Tonight, the paper for SIGCSE will have to be submitted, so I can finally concentrate on my RUSP project. While I have spent most of this week working on the paper, I have also experimented with different graphics libraries to use.

I would like to use Java rather than C++, just because it is easier for me to rapidly prototype in Java, and it is faster and more convenient to generate user interfaces with it. I consider a good user interface critical, since most likely I will have a wide array of parameters that need to be controlled.

On the other hand, the results of the algorithms will need to be displayed in 3D, and so far I have only used OpenGL and C++ to do that. Therefore, I began looking into OpenGL libraries for Java. Unfortunately, I have not found one that is truly to my liking. The 3D library that Sun offers, Java3D, might be promising, though. Internally it may use OpenGL, so it offers fast and flexible displays, but the interface is not like OpenGL at all, which means I will have to learn how to use the library almost from scratch.

Next week I will make the decision about what to use, and hopefully the first rough implementation of the tree generation mentioned last week.

top of page

This week, I have tried to work with GL4Java to get OpenGL access in Java. For some reason, I do not get it compiled properly on Windows. While it should work on Windows machines too and while I think I have all the tools required to build it, my software does not seem to be configured properly. If I can't sort this out quickly, I might have to settle for a different solution.

Most of this week, unfortunately, went for homework assignments in other classes that I had neglected because of the SIGCSE paper. I have determined there is too much friction, I lose too much time because I am trying to do too many things at once. I think I will drop a class I do not need for my degree and hope that 14 hours will make it easier to focus one something.

Overall, this was a disappointing week.

top of page

I was sick and did not even make it to any of my classes.

top of page

Most of the last two weeks, I have been sick unfortunately. In fact, in week 5 I did not even make it to class. I feel much better already since I got antibiotics on Monday.

I did not get much done when it comes to implementation; I have started writing my proposal though and am progressing well. Just writing down exactly what I want to accomplish helps a lot, as does reviewing previous work again, and attempting to explain my research goals to someone not immediately familiar with the topic.

It has become more and more clear that the multi-layered approach seems more promising: In my previous work in geometry synthesis, the algorithms were able to duplicate interesting detail, but failed at creating an intelligent overall structure. I still believe texture synthesis can be applied to geometry, but the algorithms need some guidance.

By allowing the user to control the results at two levels before the synthesis by analogy algorithms are applied, it becomes much more likely that meaningful structures are created. The creation process also becomes much more flexible, since automatic and manual generation can be mixed.

Unfortunately, I am also becoming aware of how wide of a topic the automatic generation of architecture is. The human factor is very important in how we design, and I am not sure how well my heuristics can describe this. There is certainly much more that can be done; however, I think I will focus more on the synthesis by analogy part.

I am looking forward to presenting the first draft of my proposal on Tuesday.

top of page

I spent the end of week 6 and a large portion of week 7 working on the first draft of my proposal. Just having to write down what goals I am trying to accomplish, why I want to reach them, how I will go about doing so, and how my work relates to previous work was very worthwhile. When I worked on the section about work done before, for example, I noticed I have read a lot of research for the second part, synthesis by analogy, but hardly anything on the first part, the parametric generation of geometry. So I searched for some more work and noticed that there really is a niche. I couldn't find any scientific work at all in this area. That is wonderful, but also makes for a rough start. I did find some papers in relating areas, though, and some ad-hoc techniques that will come in handy.

Exactly spelling out what I want to do and when has given me a great sense of direction. There is definitely less confusion. Since I will submit a final draft of the proposal, it really feels like this first draft was written for me, not for the instructors or someone else.

One of my favorite sections, though, must have been the one on future research that could be done as a result of my studies: Showing an explicit link between textures and geometry would blow the door open for so many techniques that have been used only for textures so far. While this is a result of the similarity that I assume exists between textures and geometry, different research could be done because of the differences that remain: It might be possible to greatly optimize geometry synthesis by using a different representation of geometry, one that does not lend itself to textures that easily. This section just gives me even more reasons to pursue my project.

After writing the proposal, I also have more of an idea what I can talk about in the presentation.

top of page

Unfortunately, I got sick again this week. I guess I went back to work too quickly. This semester seems a little cursed with respect to that.

I went over my proposal many times again, and noticed a lot of mistakes. I never mentioned where the conference will be held, for example, or when the exact deadline for the poster is. Scott Schaefer also had the kindness to read my proposal and gave me many good ideas on how to improve it. Many thanks to him.

This week, I also found another interesting paper. It does not deal with geometry synthesis, but with "content synthesis" for computer games. It does not precisely spell out the shape of the level, but rather how it is connected, that means it generates a level's topology in form of a connected graph of nodes, not its geometry. The author, however, provides some interesting insight on how to make graph-based content interesting. I will see if I can modify the approach outlined in my proposal to incorporate some of these new ideas.

I have also found another way to work with Java and OpenGL, which should make working with my project a lot more comfortable, both for me and for its users.

I'm sad that I got sick again, but the last two weeks were quite productive nonetheless, which makes me happy.

top of page

This week, I began implementing some of the core technology for the synthesis application. As stated in the week before, I decided to split the application into a Java and a C++ part. The Java part, from my current point of view, will be dealing with the general algorithm and the graphical user interface; the C++ part will take care of the 3D display. If necessary, this layout should give me the flexibility to speed synthesis up by moving those parts into the C++ part as well.

It seems like software engineering is not an exact science, though. The link between C++ and Java, JNI, is poorly documented, and I have to do a lot of guesswork, which bogs me down. After many hours of generalizing the example that I had and the celebration once I managed to do that, I noticed that the C++ display would just overdraw the Java GUI, and menus would appear behind it. This was a problem with Z ordering and Java's two GUI libraries. The slower, older one should work, but the newer one I was using would not.

I tried to switch to the older GUI system, even though I would lose some of the niceties I had been accustomed to. Whenever I did this, I would get an exception in the link between C++ and Java. Strangely enough, this error would occur before my code ever executed. I am sure it is, in the root, my fault that this happens, but with my current means I just cannot figure out what I am doing wrong.

To continue working, I redesigned the GUI to avoid the Z ordering issues. I do have a version that allows me to continue now, but I follow a narrow path, and making little changes causes my program to crash in undocumented ways.

I am still excited, though. I am finally getting things on the screen.

top of page

In the 10th week this semester, I continued to work with the GUI. I have a solid connection between the Java interface and the C++ drawing code now, so all is good here. I still have to decide how much work is actually done in the C++ part. Ideally, I want to keep it to a minimum, as I find Java easier to handle, but if the application becomes too slow, I will have to make C++ do it.

I have also started to edit my proposal again. Scott Schaefer's feedback was very valuable, and I think it is beginning to change the way I write. Dr. Johnson recommended I use passive voice less often, so I still have at least another edit cycle to go. I'm sure that's going to change my perspective on technical writing again. I will also have to make the "Future Work" section part of the introduction so that the future possibilities work as motivating factor.

The presentation is a little over a week away. I have spent some thought on how to lay it out, but haven't done much work.

Today I also talked to Dr. Warren and Scott again. We're not yet quite sure how we are going to convert the graph-based maze to polygons, so we decided to go ahead with just a 3-dimensional graph for now and decide the geometry generation later.

I'm almost back to my old strength. It feels good to be healthy again and to be working.

top of page

This was a great week for me, though not necessarily because of my work for RUSP. The SIGCSE 2004 paper notifications came in, and the paper that Dr. Nguyen, Dr. Wong and I wrote at the beginning of this semester has been accepted. I will go to SIGCSE 2004 in early March 2004 and present. I believe I can now say all the work we put into the project has paid off, and I hope I will be forgiven for not having spent as much time with my RUSP project during the first few weeks. I am incredibly happy. While just writing the paper was a good and valuable experience already, getting the paper accepted is just so much sweeter.

On Tuesday, I submitted the final version of my proposal. I changed a lot of the wording, replacing passive with active voice. Dr. Johnson and Scott Schaefer were correct: Active voice is so much more accurate. Passive voice still slips in very easily, so I have to make writing a very conscious activity. Among the changes I made, listing the SIGCSE publication in my resume was my favorite one; I'm sure that's understandable.

I continued working on the graph-based approach for the parametric synthesis this week. Unfortunately, I won't be able to include it in my presentation next Tuesday. There is just too much work that I need to do to get the abstract representation into something visual.

My presentation is coming along well, too. It is difficult to write for non-specialists and to convey all the information in so little time, only 20 minutes, but I think I can do it. I am using a lot of animation to explain a few select algorithms, so I hope no one will be confused by jargon or special terms. I am also splitting the slides in two, a main section and extra slides. The extra slides explain some more details, I doubt I will get to them, though.

The animation worries me a little, though. I definitely need PowerPoint XP or PowerPoint 2003 for the animation; the older versions do not provide the ability to show and hide elements the way I need for my algorithm explanations. I am looking forward to meeting with Dr. Pomerantz tomorrow morning to make sure my slides will display correctly. If not, I will hopefully be able to borrow a laptop from a friend.

top of page

It was definitely a good idea to see Dr. Pomerantz today and test my presentation on his laptop. Because of all the animation features I was using, my presentation did not run on the version of PowerPoint he had installed. Fortunately, Ryan Aippersbach let me borrow his tablet PC for the presentation.

The presentation went well, I think. I was the last presenter and glad about it. Otherwise, I would have been more worried about running out of time and getting someone else in trouble. There were a few things that did not go as I had planned it, though.

First of all, I forgot to mention the second of my hypotheses, namely that texture synthesis techniques can be applied to geometry, and that I will get good results, provided the surfaces are local and stationary. I also wanted to mention the pyramid scheme as an optimization and did not.

In the reviews, I was told to move around a little more. Whoever noticed that was right. Looking back at my presentation, I stood in the same spot as if my feet had been glued to the ground. Probably not a good thing. I was told I had good hand gestures though. I'm happy about that, because I have a hard time figuring out when to use gestures and how.

I was also told I should have focused on practical applications a little more. I'm afraid my project came across as toy project, while I am sure it isn't. It has practical implications, and especially in simulation and training, these could lead to important improvements. The theoretical side that links textures and geometry is also very exciting, at least from my point of view.

Another thing that went wrong is something for which I feel rather bad. Everyone had an Acknowledgements slide except for me. Of course, I cannot do this project alone and I greatly value the help of many others. Please let me thank you here for all your support.

I was also informed that my budget request has been fully approved. Thank you RUSP!

I haven't been able to do very much after my presentation. For some reason, my computer started acting up. I could not get an internet connection and get data off my computer at home. The project data, especially information from the previous project, fills about a CD-ROM, and most computers on campus don't have a CD-ROM writer. I also do not have administrator rights on any computers, and working on my project without all my tools installed turns out to be very hard. I have to get my computer fixed. I'm just glad these problems started to occur after I was done making my presentation.

top of page

I was still working on getting my PC fixed. On Wednesday, my second PC got access to the web back, so I could at least get my emails from my room. I was tired of going to the computer lab just for that.

On Friday, finally, I was able to repair everything. It's a strange story. My second PC had a worm, and I have no idea how it got there, because everything that goes on that computer passes through my primary one, which was not infected. Because of that worm, IT shut down my network port, blocking both PCs. I got access back, but for some reason the firewall on my primary computer had gone insane, still blocking all communication. I had to manually remove it; just switching it off was not sufficient.

Now that I have access to all the papers and the Java API reference again, I should be able to get some work done.

top of page

Most of my time this week was unfortunately sucked up by grad school applications. I should have started earlier, and I didn't, despite all the warnings in RUSP.

A lot of the parametric model can easily be extended to 3D and no grid. I am having some problems with distances, though. They were specified on a per-field basis, and now we do not have fields anymore. I will have to dig out my statistics books again to find the right distribution for continuous representations.

top of page

I studied some distributions again. At first, it seemed like an exponential distribution would do exactly what I want. I would specify the mean, and it would become more and more likely that a corridor would branch after that.

I'm not sure this is really what a user would want to specify. Maybe the user wants to specify a distribution that says, " it's most likely that the corridor will be this long before it branches. It is less likey to branch before that and less likely to branch after that". In that case, a gamma or normal distribution seem more useful.

I think I will just postpone this decision and provide the user with a selection of distributions to choose from. At least from a programming perspective, abstracting this notion out is simple. I just have to watch out that I won't get too many parameters again. That proved to be a problem two summers ago.

The semester is almost over now. I have one project to finish, two finals to take, and some grading to do. My research, however, does not end. I will take it home and hopefully complete the parametric stage. I will therefore continue to post weekly reports.

top of page