After lots of hard work, I finally submitted the approval form for my thesis this morning.
Actually, I'm not technically done yet. First of all, the form is submitted but there's still an electronic thesis deposit process I have to go through. Also, my advisor still thought that some of the citations weren't adequate, so I agreed not to do the electronic thesis deposit until after I had fixed those issues. Also, I have to make sure that all the documentation for the software is updated. But I can easily do all that from Colorado, and I have plenty of time between now and when my job starts.
Anyway, I'm off to GenCon now, and then on to Colorado! I'll make sure to keep you updated.
Showing posts with label Research. Show all posts
Showing posts with label Research. Show all posts
Wednesday, August 3, 2011
Wednesday, September 22, 2010
Some more news
1. The Lego robotics thing won't be starting until the 4th week in October, and will only be once a month on the 4th Sunday of each month. So there will be no more news about that until then.
2. I will be presenting my work at the CS Grad Expo on October 4. I will try to get some sort of picture up then.
3. We just submitted our annual report to the National Science Foundation. If you want to see it I can try to put it up here soon.
4. I have gone to several Magic card tournaments in the past few weeks. I have started to get better at the tournaments and I actually got in first place in one of tham (out of about 12 people or so). The only problem is that now whenever I play multiplayer (that is, games with more than 2 people) everyone gangs up on me because they assume that I will beat them if they don't. It is impossible to convince them otherwise even if there is a situation where, say, I have no creatures with any useful powers on the board but the person across from me is just one turn away from using his power that will make all his creatures indestructible for the rest of the game.
5. At Belegarth, I have identified several things that I need to get better at, and I have devised a plan for doing so, as follows. These plans have not been implemented yet but I will post again as I see how they come out.
PROBLEM: Sometimes I can't remember who is on my team. Asking the target is rarely useful because it simply alerts them that I am about to shoot them. Not asking is problematic because it sometimes results in me shooting people on my own team.
SOLUTION: Take photos of as many players as possible. Write a computer program that will do the following: (1) display a random selection of these images, each labeled as "red" or "blue", then (2) display images one after another and ask me to identify which is on which "team." This way I can practice team identification.
PROBLEM: I am supposed to only "half draw" the bow back when shooting from under 15 feet. However I sometimes have a hard time determining whether it is 15 feet.
SOLUTION: Tape a piece of tape near the side of my glasses, with two tick marks on it. The distance between the tick marks will be calibrated such that the apparent distance between the tick marks is equal to the apparent height of an average-height target at 15 feet. (The principle is similar to the principle described here, except that I don't need to know the exact range, just know whether it is more or less than 15 feet.)
PROBLEM: Different people have given me conflicting answers as to what exactly "half draw" means. Basically, the "draw length" is the distance between the nock (the place where the arrow is attached to the bowstring) and the front of the handle of the bow when you draw it. The maximum allowable draw length for full draw is 28 inches. The question is that even if you just put the arrow on the bow in the "neutral position" and don't draw it at all, the "draw length" is not zero; it is about 7 inches or so (because the bow is curved.) So does "half draw" mean 14 inches (halfway between 0 and 28) or 17.5 inches (halfway between 7 and 28). I have gotten both answers from different players, and sometimes they tell me one thing but when I have them demonstrate and measure it, it's clearly something else.
SOLUTION: Bring a tape measure to practice. Have as many archers as possible demosntrate where they think "half draw" is, and measure it. Take the average of all these measurements, then put a "half-draw mark" on the arrow at that location. Get the half-draw mark checked by a herald (that's like a referee). Additionally, in case I am playing and there is a different herald who disagrees with the first herald on where half-draw is, bring replacement tape so I can re-mark the arrows if necessary.
2. I will be presenting my work at the CS Grad Expo on October 4. I will try to get some sort of picture up then.
3. We just submitted our annual report to the National Science Foundation. If you want to see it I can try to put it up here soon.
4. I have gone to several Magic card tournaments in the past few weeks. I have started to get better at the tournaments and I actually got in first place in one of tham (out of about 12 people or so). The only problem is that now whenever I play multiplayer (that is, games with more than 2 people) everyone gangs up on me because they assume that I will beat them if they don't. It is impossible to convince them otherwise even if there is a situation where, say, I have no creatures with any useful powers on the board but the person across from me is just one turn away from using his power that will make all his creatures indestructible for the rest of the game.
5. At Belegarth, I have identified several things that I need to get better at, and I have devised a plan for doing so, as follows. These plans have not been implemented yet but I will post again as I see how they come out.
PROBLEM: Sometimes I can't remember who is on my team. Asking the target is rarely useful because it simply alerts them that I am about to shoot them. Not asking is problematic because it sometimes results in me shooting people on my own team.
SOLUTION: Take photos of as many players as possible. Write a computer program that will do the following: (1) display a random selection of these images, each labeled as "red" or "blue", then (2) display images one after another and ask me to identify which is on which "team." This way I can practice team identification.
PROBLEM: I am supposed to only "half draw" the bow back when shooting from under 15 feet. However I sometimes have a hard time determining whether it is 15 feet.
SOLUTION: Tape a piece of tape near the side of my glasses, with two tick marks on it. The distance between the tick marks will be calibrated such that the apparent distance between the tick marks is equal to the apparent height of an average-height target at 15 feet. (The principle is similar to the principle described here, except that I don't need to know the exact range, just know whether it is more or less than 15 feet.)
PROBLEM: Different people have given me conflicting answers as to what exactly "half draw" means. Basically, the "draw length" is the distance between the nock (the place where the arrow is attached to the bowstring) and the front of the handle of the bow when you draw it. The maximum allowable draw length for full draw is 28 inches. The question is that even if you just put the arrow on the bow in the "neutral position" and don't draw it at all, the "draw length" is not zero; it is about 7 inches or so (because the bow is curved.) So does "half draw" mean 14 inches (halfway between 0 and 28) or 17.5 inches (halfway between 7 and 28). I have gotten both answers from different players, and sometimes they tell me one thing but when I have them demonstrate and measure it, it's clearly something else.
SOLUTION: Bring a tape measure to practice. Have as many archers as possible demosntrate where they think "half draw" is, and measure it. Take the average of all these measurements, then put a "half-draw mark" on the arrow at that location. Get the half-draw mark checked by a herald (that's like a referee). Additionally, in case I am playing and there is a different herald who disagrees with the first herald on where half-draw is, bring replacement tape so I can re-mark the arrows if necessary.
Thursday, September 2, 2010
A new semester
So a new semester just started. A few cool things have been going on:
1. I signed up for two classes: "Adaptive + Multigrid Methods" with Luke Olson and "Finite Element Analysis" with Dan Tortorelli.
The class on Iterative+Multigrid Methods is about techniques for solving large systems of linear equations. Large systems of linear equations arise a lot from approximating a partial differential equation by a separate linear equation at each point on the mesh. "Iterative" means that you solve the equation by coming up with an approximate "guess" and then repeatedly improving the "guess" until you get close enough to the solution. "Multigrid" means that rather than just using one mesh, you have several different meshes of different sizes, and you use the solution to the coarser mesh (which can be computed faster) in order to get a better guess for the solution of the finer mesh.
The Finite Element Analysis class is in the mechanical engineering department, so most of the students are mechanical engineering students. It is interesting to learn more about how the mathematical techniques I am learning about are actually used to model physical systems, although one problem (from my perspective) is that since most of the students are not computer science students a lot of time is spent going over basic programming concepts that I've already seen over and over. For example today the professor spent most of the class just explaining how to write a program that reads input from a data file and puts it into a matrix.
2. As for my research, we have gotten to the point where we can produce reasonably good looking visualizations of the meshing process. Once I finish that part (probably in the next few weeks) I am planning on making a web page where I can put them up so you can look at them.
3. In Belegarth, last week there was the Numenor "Opener" to mark the start of the semester, where lots of people come, including some from other groups, and they do lots of different battles. One of the battles was a "Unit Battle," where the different "units" (units are groups of people that fight together and often have distinctive uniforms) all fight. For that battle I temporarily joined a unit called House Valdemar. During that battle the leader of that unit (who is also the owner of one of the game stores I play Magic at) was so impressed with my archery skills he asked me to join the unit. The way it works is that now I am a "petitioner", and after a couple months the members vote on whether to keep me in as a full fledged member. So I guess it's kind of like a fraternity (not that I would know).
4. I have volunteered to be an instuctor for a 4-H club activity that teaches kids how to build robots using Lego Mindstorms toys. The way this happened was that one of my classes is in the engineering building, so when I was getting out of class I saw a flyer up on the wall advertising this, and it sounded really cool. It's going to be an hour once a week for 6 weeks, and it probably going to start in a couple weeks or so (they haven't set up the schedule yet). I did check to make sure it will end before December so it won't interfere with our vacation plans.
1. I signed up for two classes: "Adaptive + Multigrid Methods" with Luke Olson and "Finite Element Analysis" with Dan Tortorelli.
The class on Iterative+Multigrid Methods is about techniques for solving large systems of linear equations. Large systems of linear equations arise a lot from approximating a partial differential equation by a separate linear equation at each point on the mesh. "Iterative" means that you solve the equation by coming up with an approximate "guess" and then repeatedly improving the "guess" until you get close enough to the solution. "Multigrid" means that rather than just using one mesh, you have several different meshes of different sizes, and you use the solution to the coarser mesh (which can be computed faster) in order to get a better guess for the solution of the finer mesh.
The Finite Element Analysis class is in the mechanical engineering department, so most of the students are mechanical engineering students. It is interesting to learn more about how the mathematical techniques I am learning about are actually used to model physical systems, although one problem (from my perspective) is that since most of the students are not computer science students a lot of time is spent going over basic programming concepts that I've already seen over and over. For example today the professor spent most of the class just explaining how to write a program that reads input from a data file and puts it into a matrix.
2. As for my research, we have gotten to the point where we can produce reasonably good looking visualizations of the meshing process. Once I finish that part (probably in the next few weeks) I am planning on making a web page where I can put them up so you can look at them.
3. In Belegarth, last week there was the Numenor "Opener" to mark the start of the semester, where lots of people come, including some from other groups, and they do lots of different battles. One of the battles was a "Unit Battle," where the different "units" (units are groups of people that fight together and often have distinctive uniforms) all fight. For that battle I temporarily joined a unit called House Valdemar. During that battle the leader of that unit (who is also the owner of one of the game stores I play Magic at) was so impressed with my archery skills he asked me to join the unit. The way it works is that now I am a "petitioner", and after a couple months the members vote on whether to keep me in as a full fledged member. So I guess it's kind of like a fraternity (not that I would know).
4. I have volunteered to be an instuctor for a 4-H club activity that teaches kids how to build robots using Lego Mindstorms toys. The way this happened was that one of my classes is in the engineering building, so when I was getting out of class I saw a flyer up on the wall advertising this, and it sounded really cool. It's going to be an hour once a week for 6 weeks, and it probably going to start in a couple weeks or so (they haven't set up the schedule yet). I did check to make sure it will end before December so it won't interfere with our vacation plans.
Thursday, March 18, 2010
Blog Experiment Conclusion
SPOILER ALERT: Do not read this post until you have read the three posts before this one (the two about the superhero role-playing game and the one titled "Being a Superhero in the Real World"). Then scroll down to see the rest.
...
...
...
...
...
...
...
...
...
...
...
The post titled "Being a Superhero in the Real World" was a demonstration of several scientifically proven persuasion techniques.
The superhero theme of the post, as well as its placement immediately following two posts about superhero role-playing games, is intended to take advantage of the real scientific result that getting subjects to think about superheroes makes them more likely to volunteer for charity.
The post itself was a demonstration of the "SPICE model" of persuasion, described in a recent article in Scientific American. SPICE stands for Simplicity, Perceived Self-Interest, Incongruity, Confidence, and Empathy. The four bullet points under "but wait, there's more" appeal to simplicity, self-interest, confidence, and empathy respectively. The overall tone of the post, mixing serious real-life issues with mimicry of TV salespersons and discussions of superheroes, is an example of incongruity.
(But seriously, you should definitely read Peter Singer's stuff. Even if you don't agree with all of it, the issues he raises are definitely thought-provoking.)
...
...
...
...
...
...
...
...
...
...
...
The post titled "Being a Superhero in the Real World" was a demonstration of several scientifically proven persuasion techniques.
The superhero theme of the post, as well as its placement immediately following two posts about superhero role-playing games, is intended to take advantage of the real scientific result that getting subjects to think about superheroes makes them more likely to volunteer for charity.
The post itself was a demonstration of the "SPICE model" of persuasion, described in a recent article in Scientific American. SPICE stands for Simplicity, Perceived Self-Interest, Incongruity, Confidence, and Empathy. The four bullet points under "but wait, there's more" appeal to simplicity, self-interest, confidence, and empathy respectively. The overall tone of the post, mixing serious real-life issues with mimicry of TV salespersons and discussions of superheroes, is an example of incongruity.
(But seriously, you should definitely read Peter Singer's stuff. Even if you don't agree with all of it, the issues he raises are definitely thought-provoking.)
Being a Superhero in the Real World
In comics, movies, and (as you've seen before) role-playing games, brave superheroes can make the world a better place by fighting evil. Even though superpowers don't exist in real life (as far as we know), a recent book argues that it's easier than you think to be a superhero in your own way. The book "The Life You Can Save" by philosopher Peter Singer argues that by giving just a small fraction of our income to charities working to help the poor in developing countries, we can save the lives of others at little cost to ourselves. But wait, there's more:
- It's simple. In order to be a superhero the "regular way," first you have to figure out how to actually get superpowers, then you have to worry about being sued if your powers malfunction, like in the session report below. But with giving money, all you have to do is pick an organization from the list and reach for your checkbook!
- It helps you, too. Learning to live on a little less money will help you in case there is an economic downturn, so why not start now?
- I am so confident in my message that I've taken the pledge myself. Why don't you do the same?
- I'm writing this blog post because Ihave your best interest at heart. You wouldn't want to go through life not thinking that you've done what you could to help, would you?
----------
So what are you waiting for? Operators are standing by! Act now! Sign up today!Don't make me keep mimicking cheesy TV informercials!
- It's simple. In order to be a superhero the "regular way," first you have to figure out how to actually get superpowers, then you have to worry about being sued if your powers malfunction, like in the session report below. But with giving money, all you have to do is pick an organization from the list and reach for your checkbook!
- It helps you, too. Learning to live on a little less money will help you in case there is an economic downturn, so why not start now?
- I am so confident in my message that I've taken the pledge myself. Why don't you do the same?
- I'm writing this blog post because Ihave your best interest at heart. You wouldn't want to go through life not thinking that you've done what you could to help, would you?
----------
So what are you waiting for? Operators are standing by! Act now! Sign up today!Don't make me keep mimicking cheesy TV informercials!
Friday, March 12, 2010
Blog Experiment
This week, I will be conducting an experiment using this blog in order to investigate a real scientific finding. The experiment will be conducted over one or more blog posts, starting today and ending a week from today. At that time I will make a post explaining what the experiment was.
So as not to introduce bias, I will not state here what the experiment is. That will be up to you to figure out! (Feel free to guess, that's part of the fun!)
NOTE: I meant to make this post earlier in the day, before I made my previous post about Illinois government. So that post could be part of the experiment. Or maybe not.
So as not to introduce bias, I will not state here what the experiment is. That will be up to you to figure out! (Feel free to guess, that's part of the fun!)
NOTE: I meant to make this post earlier in the day, before I made my previous post about Illinois government. So that post could be part of the experiment. Or maybe not.
Saturday, September 5, 2009
Independent Study
This semester I have decided to do an independent study with Professor Jeff Erickson.
The project we are working on (like several of the projects I have worked on in the past) involves numerical simulations of physical systems. Consider a function F(x,t) which represents the value of a particular physical variable at a particular point in space (x) at a given time (t). For example, in an application modeling heat transfer, F could represent the temperature at a given point in the material. The function F is defined by a set of initial conditions (at t=0) and then a set of differential equations that define how the value of F at each point x changes over time. The goal is to calculate (or at least estimate) the values of F over time.
Of course there are an infinite number of different values of X, and so an infinite number of variables to track. In order to solve this problem it is necessary to divide the region of interest up into a large number of smaller "cells," and keep track of one value at each cell. The pattern of cells is referred to as a "mesh". In a one dimensional case the "mesh" is trivial, but in a two dimensional problem there are lots of different mesh patterns, such as a square grid or a triangular grid. (I worked on a project with exactly this theme several years ago.)
One way of understanding the point of the "mesh" is by analogy to wargames like Dungeons + Dragons. In a real battle, movement is continuous, but in the game it is necessary to approximate that continuous movement by a discrete grid. And the shape of that grid (square in D+D, hexagonal in many other war games) is like the "mesh", and each point in that mesh is dealt with separately.
Of course in real life time is also continuous, so there are an infinite number of points in time. So just like with space, it is necessary to approximate the continuous time interval with a set of discrete points in time.The standard way of solving these problems doing this is to choose a "time step" dt - so for example if dt=6 seconds, you calculate the values of F at t=6 based on the values at t=0, then repreat the process to get the values at t=12 from t=6, and so on. (To continue with the D+D analogy, in a real life battle things are happening continuously in real-time, but the game divides up the time into a series of discrete "combat rounds".)
Now we come to the main part of our project. The part of our project that is different is to, rather than choose a mesh once and do a series of iterations where the time increases by dt each time, you keep track of a separate value of t for each vertex in the mesh, and increase the t value one vertex at a time. The advantage of doing this is that in many applications, there's a known maximum speed at which effects can propagate, and you can use this to limit the number of simultaneous equations that it is necessary to solve. Suppose that the equations are modeling sound waves, and the speed of sound in the material in question is 1000 meters per second, and suppose that the cells are spaced 1 meter apart. Then if, you use a dt of 0.001 seconds, then in one time step effects can propagate at most one mesh cell, so at each step rather than having to solve simultaneous equations for all the cells in the mesh, you only have to do so for one cell and its nearest neighbors, because those are the only cells that can affect the given vertex. This can significantly speed up the algorithm, and it also allows you to take better advantage of multiple processors, because different processors can be working on different parts of the mesh.
As for the D+D analogy for that, this is more of a stretch but here goes. Let's say you have a gigantic battle with 100 different characters arranged in a 10x10 array, and let's say each character only has powers that can affect other characters adjacent to him, and none of them can move.* Of course this battle is going to be slow going because once one person declares his actions he has to wait for 99 other characters to declare their actions before they can go do them and start theire next round. But as it turns out you don't need to keep everyone in sync like that - you can have some players start their second and subsequent rounds even before everyone finishes their first round. This is possible for the slow speed of interaction - since it will take nine rounds for anything happening in, say, the top left corner of the board to affect the character in he bottom right corner, one of those corners can be up to nine rounds "ahead" of the other and the game will still work just as normal. Basically, let's say that the guy in the top left corner just finished his 10th round while the guy in the bottom right corner is still deciding on his action for the 5th round. This will still work because the bottom right guy's 5th round action won't affect the first guy until at least the 14th round (it has to get through nine intervening spaces at one space per round), so he doesn't need to know about it yet. The condition that the "time difference" between two cells is no greater than the time it takes for information to move between them is known as the "causality" constraint.
However, there is an important complication. It is possible in certain circumstances, depending on how the mesh is laid out, to get "stuck" - i.e. there is no way to progress any vertex without violating a causality constraint.** If this happens then you have to (at least temporarily) go back to the original method of pushing up all the vertices at once*** (this is analogous to having everyone take their turns in sync, in the previous analogy). The problem is how to progress in such a way that you avoid getting stuck. There are also lots of other complications, like it you want to refine (i.e. make denser) a part of the mesh in the middle of the program execution, etc.
There is already a program that does this, and a paper about it, for the case of two dimensional meshes. The part that remains to be done is doing this for three dimensional meshes. Some of the algorithm design work is already done so a lot of the work is just coding it up (but after that we'll get to the other parts where the algorithms that are needed are not known yet).
In Erickson's words, "most computer science Ph.D. students can't program their way out of a wet paper bag, and that applies to most computer science professors as well.****" Since I am not one of those "most computer science Ph.D. students" he thought it would be a good idea for me to work for him.
---
* This analogy is technically inaccurate because in D+D, each player's turn happens sequentially, so A can do something to affect B, then that affects what B does, which affects C, so C chooses an action which affects D, and so on, all in the space of one round. For this analogy to work you have to assume that all turns happen simultaneously so that each link in the chain requires another round.
** It might appear that it is never possible to get stuck - if you increment the t value on the vertex that currently has the lowest t value, then you're not increasing any gaps. The explanation is that my description is significantly simplified - in reality it's not actually about the difference between the t values of the vertices, it has to do with the slopes of the sides of the "cells" in the n+1 dimensional space consisting of the n space dimensions plus the time dimension. But I couldn't figure out how to explain that part concisely and this post is long enough as it is.
***I'm actually not 100% sure how this part works. I just talked to Erickson yesterday and haven't read the papers yet.
****Erickson is not the first of my professors to express a similar sentiment. University of Maryland professor Samir Khuller said that when people find out that he is a computer science professor, sometimes that ask him to help fix their computer, and he says that "I can't even fix my own computer, how can I fix yours?" Michelle Hugue even once said that she "hates computers."
The project we are working on (like several of the projects I have worked on in the past) involves numerical simulations of physical systems. Consider a function F(x,t) which represents the value of a particular physical variable at a particular point in space (x) at a given time (t). For example, in an application modeling heat transfer, F could represent the temperature at a given point in the material. The function F is defined by a set of initial conditions (at t=0) and then a set of differential equations that define how the value of F at each point x changes over time. The goal is to calculate (or at least estimate) the values of F over time.
Of course there are an infinite number of different values of X, and so an infinite number of variables to track. In order to solve this problem it is necessary to divide the region of interest up into a large number of smaller "cells," and keep track of one value at each cell. The pattern of cells is referred to as a "mesh". In a one dimensional case the "mesh" is trivial, but in a two dimensional problem there are lots of different mesh patterns, such as a square grid or a triangular grid. (I worked on a project with exactly this theme several years ago.)
One way of understanding the point of the "mesh" is by analogy to wargames like Dungeons + Dragons. In a real battle, movement is continuous, but in the game it is necessary to approximate that continuous movement by a discrete grid. And the shape of that grid (square in D+D, hexagonal in many other war games) is like the "mesh", and each point in that mesh is dealt with separately.
Of course in real life time is also continuous, so there are an infinite number of points in time. So just like with space, it is necessary to approximate the continuous time interval with a set of discrete points in time.The standard way of solving these problems doing this is to choose a "time step" dt - so for example if dt=6 seconds, you calculate the values of F at t=6 based on the values at t=0, then repreat the process to get the values at t=12 from t=6, and so on. (To continue with the D+D analogy, in a real life battle things are happening continuously in real-time, but the game divides up the time into a series of discrete "combat rounds".)
Now we come to the main part of our project. The part of our project that is different is to, rather than choose a mesh once and do a series of iterations where the time increases by dt each time, you keep track of a separate value of t for each vertex in the mesh, and increase the t value one vertex at a time. The advantage of doing this is that in many applications, there's a known maximum speed at which effects can propagate, and you can use this to limit the number of simultaneous equations that it is necessary to solve. Suppose that the equations are modeling sound waves, and the speed of sound in the material in question is 1000 meters per second, and suppose that the cells are spaced 1 meter apart. Then if, you use a dt of 0.001 seconds, then in one time step effects can propagate at most one mesh cell, so at each step rather than having to solve simultaneous equations for all the cells in the mesh, you only have to do so for one cell and its nearest neighbors, because those are the only cells that can affect the given vertex. This can significantly speed up the algorithm, and it also allows you to take better advantage of multiple processors, because different processors can be working on different parts of the mesh.
As for the D+D analogy for that, this is more of a stretch but here goes. Let's say you have a gigantic battle with 100 different characters arranged in a 10x10 array, and let's say each character only has powers that can affect other characters adjacent to him, and none of them can move.* Of course this battle is going to be slow going because once one person declares his actions he has to wait for 99 other characters to declare their actions before they can go do them and start theire next round. But as it turns out you don't need to keep everyone in sync like that - you can have some players start their second and subsequent rounds even before everyone finishes their first round. This is possible for the slow speed of interaction - since it will take nine rounds for anything happening in, say, the top left corner of the board to affect the character in he bottom right corner, one of those corners can be up to nine rounds "ahead" of the other and the game will still work just as normal. Basically, let's say that the guy in the top left corner just finished his 10th round while the guy in the bottom right corner is still deciding on his action for the 5th round. This will still work because the bottom right guy's 5th round action won't affect the first guy until at least the 14th round (it has to get through nine intervening spaces at one space per round), so he doesn't need to know about it yet. The condition that the "time difference" between two cells is no greater than the time it takes for information to move between them is known as the "causality" constraint.
However, there is an important complication. It is possible in certain circumstances, depending on how the mesh is laid out, to get "stuck" - i.e. there is no way to progress any vertex without violating a causality constraint.** If this happens then you have to (at least temporarily) go back to the original method of pushing up all the vertices at once*** (this is analogous to having everyone take their turns in sync, in the previous analogy). The problem is how to progress in such a way that you avoid getting stuck. There are also lots of other complications, like it you want to refine (i.e. make denser) a part of the mesh in the middle of the program execution, etc.
There is already a program that does this, and a paper about it, for the case of two dimensional meshes. The part that remains to be done is doing this for three dimensional meshes. Some of the algorithm design work is already done so a lot of the work is just coding it up (but after that we'll get to the other parts where the algorithms that are needed are not known yet).
In Erickson's words, "most computer science Ph.D. students can't program their way out of a wet paper bag, and that applies to most computer science professors as well.****" Since I am not one of those "most computer science Ph.D. students" he thought it would be a good idea for me to work for him.
---
* This analogy is technically inaccurate because in D+D, each player's turn happens sequentially, so A can do something to affect B, then that affects what B does, which affects C, so C chooses an action which affects D, and so on, all in the space of one round. For this analogy to work you have to assume that all turns happen simultaneously so that each link in the chain requires another round.
** It might appear that it is never possible to get stuck - if you increment the t value on the vertex that currently has the lowest t value, then you're not increasing any gaps. The explanation is that my description is significantly simplified - in reality it's not actually about the difference between the t values of the vertices, it has to do with the slopes of the sides of the "cells" in the n+1 dimensional space consisting of the n space dimensions plus the time dimension. But I couldn't figure out how to explain that part concisely and this post is long enough as it is.
***I'm actually not 100% sure how this part works. I just talked to Erickson yesterday and haven't read the papers yet.
****Erickson is not the first of my professors to express a similar sentiment. University of Maryland professor Samir Khuller said that when people find out that he is a computer science professor, sometimes that ask him to help fix their computer, and he says that "I can't even fix my own computer, how can I fix yours?" Michelle Hugue even once said that she "hates computers."
Subscribe to:
Posts (Atom)