Jump to content


Member Since 16 May 2013
Offline Last Active Feb 15 2015 07:46 AM

Topics I've Started

Intersection of half-plane and square

01 February 2015 - 10:46 AM

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.

Cellular automata for hydraulic erosion?

23 May 2013 - 10:54 PM

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.

I'm tutoring a promising student who is about to make a big mistake

16 May 2013 - 08:36 PM

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).