# csp256

Member

9

1. ## Intersection of half-plane and square

Thank you for your responses! Unfortunately using an external library is not an option because this project is a part of me teaching someone else how to program by guiding them through solving their problem (instead of just doing it myself).   I am very interested in the Sutherland-Hodgman algorithm (and computational geometry in general) but it is overkill for the moment. I have solved my problem using the method I outlined above, plus ordering the points. I accomplished this by taking arctangent of their relative vectors around their centroid: as I said, it did not need to be fast. I need to check approximately a million such intersections only once.   The line to line segment intersection had a particularly nice solution since x or y was a constant, and the line was already in normal (parametric) form, so I could find the intersection by x = r - tan(theta) * y   or by  y = r - cot(theta) * x as needed.   I am treating theta=0,pi/2,pi,3pi/2 as special cases because it was important this individual function be no more complicated than necessary for pedagogical reasons.   Do you have any cool computational geometry resources for me (I know very little on the subject), outside the bounds of this project? I will soon check the appropriate forums/stickies.
2. ## Intersection of half-plane and square

I have a (non tilted) square bounded by the points (x, y) and (x+h, y+h). I would like to know the percentage (or area; doesn't matter) that intersects with a half plane. Performance is not a priority.   When I say half-plane, I mean the set of all points further away from (or closer to) the origin than a line of infinite extent. This line is internally specified by an angle theta, and a minimum distance S from the origin. (and a further boolean specifying if we include points "closer to origin" or "further away from origin")   How do I solve this problem?   First thought is to check for a line to line segment intersection for each edge of the square. Take the union of the square's vertices with all points returned from the previous check. This will give 4 to 6 vertices. I then throw away all vertices which fail the closer/further test. I am then left with a minimal set of convex bounding points (thus solving the problem in principle).   I am comfortable performing special case checks for theta = 0, pi/2, pi, and 3pi/2 radians to catch the special case where the line segment lies on the half plane border.   Is there a better way to do this? I feel like I am missing something obvious.
3. ## Cellular automata for hydraulic erosion?

I like toying around with World Machine and other procedural terrain generation tools. I'm also trying to learn more about general-purpose GPU programming, so I thought I would see if I could recreate one of my favorite parts of World Machine on the GPU: hydraulic erosion.   World Machine's hydraulic erosion function simulates the effect of precipitation on a heightmap, and has four outputs: an eroded heightmap, a water-flow map, a soil-deposition map, and a wear map (that shows where the erosion occurred). It does a pretty good job, and is relatively fast. The starter map you get on start up can be eroded with default settings in ~10 seconds.    I intend to replicate this basic functionality, but with an increase in speed. This is not meant to be boasting or impressive, just a consequence of using the GPU on a parallelizable problem. However I would like to improve upon it with a new feature: meanders and oxbow lakes. http://en.wikipedia.org/wiki/Meander Meanders are when rivers curve significantly, due to increased water flow and erosive force on the exterior of a bend in the river. Excessive curves may cause the river to erode an extra connection to itself, cutting off part of the river from a water source. This results in horse-shoe shaped lakes next to rivers (which may or may not dry up).   I would like to see if I can get this to happen as an emergent behavior from a properly constructed cellular automata. In order to see this sort of behavior I would need a model that allowed (1) water flowing next to a cell (which is higher than the water) to cause erosion in that cell, (2) water to flow faster on the outside of a bend, (3) faster moving water to be more erosive, (4) slower water to deposit more soil. I'm not entirely sure how to achieve that. Locally computing the gradient of water altitudes to determine flow rate each time step is the simplest method, but it also fails to achieve #2, which is an important property.    Does anyone have any ideas? I feel like I am too close to the problem and am overlooking something simple.    PS: I understand that what I am talking about is, strictly speaking, a finite element method instead of a proper CA. However, I have repeatedly seen this referred to as a CA elsewhere, so I do so here as well.
4. ## Cellular automata for hydraulic erosion?

I should have been more specific! Yes I know about the memory architecture and how that causes this problem to be just "parallelizable" instead of "embarrassingly parallel".   http://www.olcf.ornl.gov/tutorials/cuda-game-of-life/   I was intended to use the second method shown there (the one using __syncthreads() & shared memory) as a rough template, and then maybe play around with texture memory or OpenCL later.   What I need help on was the CA design, not the programming.    I frankly don't have the expertise to recreate that webGL interface. I also wonder how quickly it actually simulates erosion. Just waiting for precipitation causes very slow erosion, while adding water quickly saturates the landscape and results in smooth landscapes.    http://www.world-machine.com/about.php?page=latest   Compare that to the images at the above page. The first one has a fairly obvious straight channel running diagonally from top left to bottom right. These result when your initial heightmap is smooth in that area. This means that taking a hand-made heightmap with a rough outline of your terrain and then eroding it can cause nasty artifacts. I consider that a nasty limitation of the extant techniques, as it removes much of the benefit of procedural generation.   While the webGL implementation and the second image in the WM link both have curvy river-like flow patterns, they are curvy because they simply followed the gradient of the input heightmap. They weren't caused by any interesting fluid/erosion dynamics. That is what I'd like to change, and that involves crafting the cells' update rules appropriately.   This involves simulating the flow gradient of the water in a persistent, non-stochastic way. What I am really asking for direction on is how to do that.    PS: While the online demo is spiffy, non-real-time techniques are still useful. Because the erosion step dominates most terrain generation pipelines, if you can significantly reduce its duration then you open yourself to being able to completely procedurally generate large numbers of terrains. If you have some evaluation metric to compare them against, then you can select the best N of them to show to the artist, who can further tweak their parameters. These tweaked parameters can then be what is sent to the player, who generates the terrain on demand. This means that the amount of data which you ship to your end user to handle terrain is orders of magnitude smaller than it used to be, but still looks high quality because it has been hand-tweaked by an artist.
5. ## I'm tutoring a promising student who is about to make a big mistake

I used to teach video game programming to kids (as an excuse to teach programming to kids). Recently I've begun tutoring one of my former students, who is now 17 and a year from graduating high school. I'm doing it as something of a hobby/distraction from my own degree program, and because I empathize with him (he had a severe, traumatic life-event recently). Thankfully he has an enviable mix of talent and ambition, and above average discipline (though it is admittedly where he needs the most work; don't we all?). He has strong analytic and creative aptitude.   Unfortunately I think he is about to make a mistake. He wants to work on video games. Specifically he intends to apply this fall to DigiPen for a BA in Game Design. His back up plan is to use his degree for technical writing. His parents are problematically of the “follow your dreams” school of thought and are encouraging him. I am more pragmatic, and the parents might listen to me if I talk to them.   I think his school of choice is not regionally accredited (unable to be accepted for entrance into a master's program elsewhere; may not be recognized by employers outside of the industry [such as government contracts, which are prevalent here]). I think that his intended degree program is not an entry level position and has almost no application outside of the video game industry (which is notoriously volatile job market).   I think he is choosing the BA of Game Design because of fear of failure. I think he has this fear of failure because he is smart and has never really had to try very hard (until recently; which was traumatic). I think he sees the hard metrics of success and failure in computer science and digital art with fear. I think he is instead focusing on an abstract approach instead of the making-and-doing of video games in an attempt to do what he wants without the risk.   Ostensibly he knows that no one needs or wants an idea guy. He says he knows that even his own “big game idea” is worthless [as it is the thousand small details that make or break a game]. He says he knows that in order to learn to code video games, you should first learn to code [or, that to master digital art you must first master art]. However I think he is only halfway there. I don't think he has a firm appreciation of the ramifications of those statements.   I *do* think he has what it takes to be a successful game developer (if he spends a few years working really hard), but I think he is going about it in a tragically bad way. I want to guide him towards either a computer science or digital art degree program at an accredited university. Unfortunately he has already toured DigiPen and fallen in love.   I would like advice on how to help steer him in a better direction (or a correction if I am the one off-base here). I meet with him tomorrow. I am focusing teaching him math right now as prep for the ACT, but have a litany of ideas of ways to grow his portfolio for after he takes the test. I am hoping he will naturally develop an interest in one of the aspects of game development, but think it more likely that I will have to try other methods to convince him that there are better paths to realize his dreams.   "Too long; didn't read" summary: 17 year old student of mine wants a BA in Game Design from DigiPen, potentially for the wrong reasons at that. Parents are encouraging him (but do value my input).
6. ## I'm tutoring a promising student who is about to make a big mistake

You are teaching him programming and math (great!), he wants to get into game design, so you want him to major in art? That doesn't sound quite correct to me... but I'm not in the industry. How'd art even get into the picture? Has he already shown interest (and natural skill) in art? If he has skill for programming, wouldn't a computer science degree be more appropriate?   He was looking at design for the wrong reason. It was because he was afraid of failure (and in art/coding it is very clear when you don't know what you're doing). He saw game design as a less intimidating alternative because of the murkier metrics of individual skill. I openly accused him of this Friday and he said "wow, you really hit the nail on the head!"   I still want him to achieve his desire to be a game designer. I do not think that going to school for game design is a good way to achieve that (I am not in industry either, just repeating what I've distilled from what I've read). I think that having a strong marketable skill, a useful trade which allows you to get your foot in the door / prove yourself, and then branching into a more executive role is the way to do it. And the best way to do digital art, is to know how to do art. The actual tools you use are fairly easy to pick up; they are not the limiting factor. For example, many people ask "how do I learn to program video games", and I tell them "learn to program". I understand the same goes for "how do i learn to make digital art" (learn to make art). I would even go so far as saying that this principle extends to design. "how do i learn to design video games" becomes "how do i learn to design", but design is inherently not a fundamental skill. It is built on top of a foundation of skills. Without that foundation, your attempts at design are as doomed as the kid who tries to make an MMO without knowing what TCP/IP is.   His math and programming skills have atrophied significantly. I'm going to work on repairing them. His experiences have given him a uniquely common reason for not having developed a baseline of skill in either art or coding. I'm sorry for being vague, but I am trying to preserve his anonymity. Just trust me on this.
7. ## I'm tutoring a promising student who is about to make a big mistake

I had a lengthy, frank discussion with him. He was exceptionally mature about it and was processing what I was saying. I am used to dealing with kids being a lot more difficult. You tell the average 17 year old that and they don't even hear you.   He is definitely leaning much more towards art.   I basically presented it as "I want you to achieve your goals. I do not think that major is the best way to do that, despite it having the same name as your desired job title. I think the best way to do that is to get a classical art degree, and use your electives/club/personal projects to build digital art / video games", but I worked up to it by expressing all the reasons first without comment about their implication.   He considered SCAD, for example, when I explained to him that he has his heart set on DigiPen for the wrong (but understandable) reasons. I think that you can do a hell of a lot worse than SCAD, but I may be biased (my sister is an alumnus).
8. ## I'm tutoring a promising student who is about to make a big mistake

In this post I am going to talk about how I intend to guide my young student's education towards having a good foundation. Ya know, calling him that is odd. Let's call him Steve (obviously not his real name).   Steve is unfocused. This is not unexpected in a 17 year old who hasn't been exposed to most of the aspects of his industry. My intended solution is to give him a broad base, and then have him focus on something. I'm going to post my rough outline of how I want to direct his study. Could someone please be so kind as to give me criticism on my intended pedagogical approach?   First, I have to break down what I want to expose him to. List of fundamental skills I intend to cover with him (with general programming intentionally excluded): terrain, organic modeling, artificial (non-organic) modeling, texturing, rigging, animation, lighting, materials (shaders), particles, post process (Photoshop, Blender's compositor), UDK's Kismet. Please let me know how that list is incomplete. (I would not know how to begin teaching audio, much less audio engineering) After those fundamentals have been mastered (more on that in a bit) we can talk about environment and level design. I am postponing those because I think they are inherently higher level discussions that are more abstract and reliant upon a strong foundation. Hopefully, once we get there he will begin to understand why attempting to jump straight to game design is (in my opinion) foolish.    My approach is broken broadly into three stages.   1: Initial exposure and conceptual framework. Steve will basically follow an online tutorial. I actually have a specific tutorial in mind for each one of the fundamentals I listed. There may be supplemental reading (I remember the resources which elucidated me)   2: Very small scale project. Self directed, but with guidance (or even veto) from me. This will be at, or only very slightly outside, the scope of the first stage, but without a direct tutorial.   3: Modest portfolio project emphasizing that skill. (this is a portfolio for getting into a school, so modest is a good adjective).    I intend to take each one of those skills up there to stage 1. Maybe half or a third of them to stage 2, and one to stage 3 (at that point we can re-evaluate what needs to be done). Level and environment design will not be discussed until after multiple skills are at stage 2. He alone will decide which ones to pursue further, and I will urge him to do so solely off of which seemed interesting, not those that he was naturally good at, or found easy. Obviously if he doesn't develop an interest in any of those, I may come to suspect that maybe the video game industry isn't for him (but I think he will take to it).   My major talking points will be aimed towards making him a successful self-directed learner:   1: Fail at something every day. Hell, I want a shirt that says that. I will stress that it is important that you fail early, often, and quickly. This is so you can learn early, often, and quickly. The blank canvas is not your enemy, it is an opportunity. Making a wrong stroke in a painting is not a mistake, it is a lesson.   2: To be creative and productive give yourself design constraints. A glut of choice is crippling. Design constraints, even arbitrary ones, cause adaptation which causes personal and professional growth.   3: Use of the 60 60 30 time management method (or similar method). Breaks are an important part of successful design, but they are not as important as *starting* the project. Always, always, always finish what you start.   4: Have clear goals. Murky goals result in non-existent results. Write down your intentions, do something else, then return and double the length and detail of your notes. Make lots of lists. Nothing is prettier than a completed checklist.    Therefor I will give him, from the very start, tight deadlines for each project. I will work with him to develop constraints for stage 2. At stage 3 I expect him to be prepared to write his own constraints with little to no oversight. Documentation was not listed as a fundamental skill above, but it does not necessarily fall directly into the same "stages" breakdown. However, I will have him do some implementation documentation at stage 2. Stage 3 will be very well documented throughout. (hey, if he wants to be a technical writer I will capitalize on that)   A complicating factor is that I have no formal training in game development. I am not a good artist and do not have any art training. I do however have a good technical (not necessarily practical) grasp of color theory from my self-study of computer vision and image processing. I particularly enjoyed modifying UDK materials, and find level/environment design fascinating. I have a pet fascination with technical artists and what they do.   Since I know that he is certain to "waste" some of his time playing video games I am going to direct what he plays and how. I'm thinking that having him write a page about each L4D2 level would be an exceptional case study. Ultimately I'd like to expose him to early-generation games, but that'll come much later.   On the math side I am going to reinforce his Trig knowledge and get him through Calculus A with a strong grasp of vectors and parametric representation. Coding wise he will implement binary search, merge sort (recursive then non-recursive), Conway's game of life (and/or Langton's ant), TicTacToe, some other board game, A* search, and Monte-Carlo tree search (a very simple/elegant/effective AI technique. It is well suited to turn based games). I will encourage him to use Python, Processing, and C# (in Unity) to achieve this. That is the baseline of programming background I intend to give him, even if he does not chose to go further in programming. I will evaluate how to direct his studies if does chose a computer oriented path, but I believe it more likely he will move towards digital art.   The above is intended to represent a year of study. I think those goals are achievable, practical, but admirable in scope for a talented person still in high school. Also, I think that building confidence under directed self study could potentially be instrumental in his recovery.   So, burst my bubble! Where and how am I wrong? What would you change?
9. ## I'm tutoring a promising student who is about to make a big mistake

Thanks frob. :) Of course I'm going to talk to him! I just need to figure out how. Obviously charging in like a bull and saying "you need to go to SCAD or USC" will not work. And honestly, it took me writing that post and talking about it to my girlfriend to really think the situation through. I know that they may not head my advice. I know they may tell me to not come back, even though I am effectively tutoring him pro-bono. But, that same fact gives me security to attempt to effect change.   Thanks for the link. What a card! But, I am thankful Sloper has compiled a body of work like that. That makes it harder to dismiss and, while rough around the edges, his message is very clear and pragmatic.   For the time being I am teaching my young student math. That is my focus for the next couple weeks. But I will talk to him (not his parents) about design not being an entry level position. If I can get him to imagine himself in a skill-oriented, content-creation-focused discipline (say, BFA in Game Art) instead of a more administrative role, I think I've won the hard battle. That would entail him being interested in obtaining a skill set, confronting his fear of failure, and provide a clear way for me to train him to develop better work/self-study habits. After that, convincing him that a traditional art foundation is the superior path is almost a foregone conclusion. Thankfully I have half a year to do this, not weeks or days.   I'm also concerned about the drop out rate at DigiPen. I've heard numbers of 50% first year, and an additional 50% the second. While he is ostensibly recovering well, it has been my experience that people who go through a traumatic experience take several years longer to heal from it than they think they do. Several times I've seen people who, one to two years after their recovery (whatever that entails for them), have their lives fall apart. It happened to me, and my girlfriend*. I'm really concerned about him moving away to any college, especially to an accelerated degree program that has a huge attrition rate, right at that dangerous spot in your recovery (where you let your guard down).    * Please make sure your friends and family know that you want to donate "specific organs and tissues", not whole body, in case of your death. Checking the box on the driver's license form isn't enough. With a 1 minute conversation you can save lives. My girlfriend's hyperacute liver failure would have been fatal if it weren't for a young man who told his parents he wanted to donate if he died. That conversation saved three people's lives.