Pixel City Redux #4: I Didn’t Know I Didn’t Know That

By Shamus Posted Tuesday May 1, 2018

Filed under: Programming 58 comments

In the last entry I hacked together a solution that let me draw my scene without using a framebuffer object. But now I’m realizing that even though I got lighting working, I still don’t have the features I need to make this work.

The Loss of Framebuffer Effects

One of my goals at the start of this project was to mess around with goofy color reduction and dithering effects. I don’t know why, really. It was just something I wanted to see in action.

The idea I had for dithering would squash the image down to just 16 colors, which would produce something like this:

I strongly suspect this effect won't do much unless you apply it to a near-photoreal scene, but I still want to run the experiment.
I strongly suspect this effect won't do much unless you apply it to a near-photoreal scene, but I still want to run the experiment.

With lots of colored lighting, stark shadows, and the right surface textures, that might look really interesting. Like pixel art in motion? The other idea was to simply reduce the resolution of the individual color channels to make something like this:

It doesn't look very interesting here, but in on old OpenGL project I got some semi-interesting results out of this.
It doesn't look very interesting here, but in on old OpenGL project I got some semi-interesting results out of this.

Again, there might be some combination of lighting, shadows, bloom FX, and surface textures that would make something unique. (As opposed to just “pixelated”.)

I really enjoy this sort of crazy mixing of technology levels. Like, “What would it look like if you were doing modern-day 3D rendering on the EGA displays of the late 1980s?” Maybe it would yield a distinctive look, or maybe it would just result in something confusing and dull. The only way to be sure would be to do the experiment and see how it looks.

Sadly, I have to abandon this idea. These effects require the use of a framebuffer. You need to be able to render the entire screen into a framebuffer, and then copy it into the viewport using some sort of special effects shader. No framebuffer means no full-screen effects.

This also means no bloom lighting, which is another thing I wanted to experiment with. I wondered what it would look like if you only applied bloom to certain color channels. Like, blue light blooms, but red light doesn’t. It might look something like this:

I know bloom lighting gets a lot of hate, but I think it's a bit like CGI. People only notice it when it's done poorly.
I know bloom lighting gets a lot of hate, but I think it's a bit like CGI. People only notice it when it's done poorly.

I know this is somehow possible in Unity, because Nightdive Studios did something like this in the System Shock Remake demo, and that was written in Unity:

Can we call this... bluem lighting?
Can we call this... bluem lighting?

I’m guessing the “dreamy” look of this image comes from bloom lighting with the blue channel boosted, and I really wanted to try that out on my city.

But to do all this I’d need to figure out how to gain access to framebuffer effects in Unity, and:

1) The documentation on this rendering path is so sketchy it borders on classified.
2) What little I can find out about it indicates it’s built around rendering the scene with normal maps, with the assumption that you’re going for modern-day rendering conventions. So even if I did gather enough information on how to use Unity’s deferred render path, I’d still need to perform extensive modifications to adopt it to my gonzo rendering style. (And it might not even be possible to do so.)

A few days after writing this I found the post-processing effects. It would have allowed me to do all of the stuff above, but none of the search terms I came up with took me to the secret chamber on knowledge I needed to proceed. I found a post-processing effect that does bloom lighting, but it’s a black box and I can’t figure out how to get the source. (I’m sure I’ve got the source SOMEWHERE on my machine in the /Unity install folder, but with no indication of what it’s called or how to set it up, I’d have to re-write and re-implement the entire thing.

It’s a shame, because I’m sure I could do the blue bloom lighting by changing a single line of code, but I can’t get the info on where that one line of code would go.

Using Unity is really odd. Sometimes huge, complex tasks can be automated in just a couple of lines of code, and sometimes seemly-obvious things become unreasonably complex. For the last five days I’ve been saying, “Everything in Unity is either trivial or impossible!” That’s not really true, but it feels true.

Enough whining. Let’s get back to work.

Streets

Bah. Close enough. Ship it.
Bah. Close enough. Ship it.

In previous entries you might have spotted some streets with traffic lines and proper intersections. In this write-up I’m listing features in order and talking about them in isolation because that makes it easier to follow, but the truth is that I bounced around and worked on a lot of different things. If I got stuck on one thing, I’d switch over to another task until I got an idea of how to solve the first problem.

So let’s go back and talk about how I made those streets, because I ran into an amusing situation.

Like I said in part 1, I scribbled some random lines down to use as streets. That would form something like this:

Finally, a nice easy problem for a change.
Finally, a nice easy problem for a change.

Then I just need to see where the lines cross each other. I can split them at those points and insert intersections. That will leave me with something like this:

So simple a child could do it! Sadly, there aren't any kids around at the moment and I'm stumped.
So simple a child could do it! Sadly, there aren't any kids around at the moment and I'm stumped.

Okay, so I just need to take two arbitrary line segments and derive their intersection point. (Assuming they have one.) To do that I’ll need to…

Um.

This Should Be Easy, Right?

Hang on. Why can’t I figure this out? I really expected this would be easy, but now that I’m about to type the code I suddenly realize I have no idea how to do this. And it seems like it should be simple, right? “Where do two lines intersect?” That sounds like a simple operation. It certainly seems simple compared to fancy stuff like surface normals and reflection vectors and transformation matricies.

I mean, it's RIGHT THERE.
I mean, it's RIGHT THERE.

Oh right, I can look at the point and see how far it is from the ends and that will tell me…

No, that will tell me if the point falls within the line, but first I need to find the point.

(Moments of confusion and embarrassment pass. I feel like some kid who’s been asked to write a word on the chalkboard, and it’s not until I’m holding the chalk in my hand that I realize I no longer speak English. Why am I having so much trouble?)

This is silly. I can do this. What if…

Okay, what if I connect two of the endpoints? This will form two of the corners of a triangle. It should be easy to get the inside angles of those two corners, and I can use those to somehow derive…

I worked out a formula to solve this, but it only works on left triangles.
I worked out a formula to solve this, but it only works on left triangles.

Huh. I actually have no idea how to do this. I guess this is the sort of predicament you find yourself in when you’re self-taught. I’m not surprised I have gaps like this in my knowledge, but I am surprised I didn’t know that I didn’t know this until I tried to do it. That’s funny.

Anyway, I search around and I find a code snippet that does the job for me. I have to convert it into C#, but it works:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public bool Intersects (LineSegment other, ref Vector2 intersection_position) 
{
	//First let's try to avoid the heavy math with simple bounding checks.
	Bbox2	box1 = new Bbox2();
	Bbox2   box2 = new Bbox2();
 
	box1.Contain (start);
	box1.Contain (end);
	box2.Contain (other.start);
	box2.Contain (other.end);
	if (!box1.Intersect (box2))
		return false;
 
	float		a1 = end.y - start.y;
	float		b1 = start.x - end.x;
	float		c1 = a1 * start.x + b1 * start.y;
 
	float		a2 = other.end.y - other.start.y;
	float		b2 = other.start.x - other.end.x;
	float		c2 = a2 * other.start.x + b2 * other.start.y;
 
	float det = a1*b2 - a2*b1;
	if (det == 0)
		return false;
	intersection_position.x = (b2*c1 - b1*c2) / det;
	intersection_position.y = (a1 * c2 - a2*c1) / det;
	//The above checks can figure out WHERE the intersection takes place, but that 
	//point might only be reachable by continuing one of the segments.
	//Now make sure this point falls WITHIN the segments.
	float	to_intersection;
	float	my_length = Length ();
	float	other_length = other.Length ();
	to_intersection = (start - intersection_position).magnitude;
	if (to_intersection > my_length)
		return false;
	to_intersection = (end - intersection_position).magnitude;
	if (to_intersection > my_length)
		return false;
	to_intersection = (other.start - intersection_position).magnitude;
	if (to_intersection > other_length)
		return false;
	to_intersection = (other.end - intersection_position).magnitude;
	if (to_intersection > other_length)
		return false;
	//All tests pass. The point must be good.
	return true;
}

It works, so whatever.

Getting Rid of a Bad Idea

Remember in part one I put down all these little “sidewalk marker” objects? At the time, I was envisioning this system where sidewalks would be very organic. Roads would crisscross and form little traffic islands and such. Stuff like this:

These aren't just traffic islands. This is an archipelago.
These aren't just traffic islands. This is an archipelago.

But now that I’m working on this, I’m not really interested in messing around with organically-grown traffic islands. They’re interesting, but they’re not the kind of feature you need. The scene won’t look incomplete without them.

Also, having the program chew through thousands of these stupid sidewalk points is slow to the point of annoyance. If I’m not using them to do anything sophisticated, then there’s no reason to have a sophisticated system.

Highlight code. Press delete.

Now we can build blocks a much simpler way.

We take all our streets, cut them up where they intersect, and put intersection objects at the split location. This intersection will mediate the connections between all the roads that feed into it.

Damn it, THAT'S why I couldn't find the intersection points. They were hiding behind these big black dots!
Damn it, THAT'S why I couldn't find the intersection points. They were hiding behind these big black dots!

Once all the streets are plugged into their respective intersections, we go around and look for hanging dead-end streets. We throw these away.

Great. Ship it.
Great. Ship it.

The block builder will grab one side of the street and just keep making right turns until it gets back to where it started. When it’s done, it’s formed a block.

This is still a very primitive system. I’ll need to add a way to have streets of varying widths, and maybe more variation in the spacing. But I plan on adding a “region” system later where different parts of the city will have different streets / buildings. Until then, I think this is good enough.

 


From The Archives:
 

58 thoughts on “Pixel City Redux #4: I Didn’t Know I Didn’t Know That

  1. default_ex says:

    You may want to bookmark this one: http://paulbourke.net/geometry/. I have had that one sitting in my bookmarks as a reference page whenever I work with geometry. The really nice part is that he doesn’t just show you the answer, he shows how the answer was derived in just enough steps to understand how and why it works.

    1. Ander says:

      That’s wonderful; thank you for the link.

    2. Paul Spooner says:

      Excellent! I had to derive these myself and while it was kinda fun, I’m glad I can just look the solution up next time.

  2. DaMage says:

    Errr, isn’t that problem just calculating the intersection of two lines? You know, figure out the line equation for each (y=mx+c) then putting one into the other to find an intersection point.

    And yep, that exactly, what that function does, calculate the line equation, puts one into the other then checks to make sure the intersection point falls within the line segments you have.

    I’m sure you’ve run into this before at some point, and you’ve just blanked on the solution this time.

    1. 4th Dimension says:

      Yeah. The only issue is that here it involves a bit more math because what Shamus has is bunch of pairs of points (end (x1,y1) beggining (x2,y2)) so:
      – first needs to compute the function of the LINES containing those segments: k1 n1, k2, n2
      – then compute the X and Y that fit both lines
      – and then check if the intersection is part of the line segment.

      1. Guest says:

        That’s exactly what DaMage said though, finding those “LINES” just requires two points, and they have two points, that’s how the lines were defined.

        So y=(y2-y1)(x-x1)/(x2-x1)+y1 for each line, then set them equal to each other. Pretty simple. There’s a minor bit of algebraic rearrangement, but it’s still a linear equation which means it solves pretty simply.

        So for four points defining two lines, x1, y1, x2, y2, x1′, y1′ etc

        Make things easier on yourself and define slopes:
        (This works directly as code:
        m=(y2-y1)(x2-x1)
        m’=(y2′-y1′)(x2′-x1′)

        Then let them equal each other: m(x-x1)+y1=m'(x-x1′)+y1′

        Solving for x: x(m -m’)=y1′-y1+x1m-x1’m’ (Showing for working, the code line is below)

        xintercept=(y1′-y1+x1m-x1’m’)/(m -m’)
        yintercept=m*xintercept-m*x1+y1

        Unless I’ve made some minor algebra mistake (Entirely possible, this was like 3 or 4 minutes of typing into the text box), that’s all you need to calculate the intercept between two defined lines. I’ve used similar code myself dozens of times, it’s high school maths, it’s fairly basic function study stuff. Granted, it does make it quite a pain that you have to leave it generalised, and leaves itself open for lots of typos, but it’s also really easy to see if it works.

        You shouldn’t require a check step to find out if it exists on the lines. It does, by defintion, the process already has had the point substituted into both functions. This is a linear equation, all solutions are real, and non-asymptotic, and lines which are not parallel will only ever have one intercept. If your lines are parallel, then the step where the two slopes are subtracted (m-m’) will return an error due to a divide by zero. Putting a check step in that m!=m’ will fix this. If you run it and have something mark the intersections, that should be enough to confirm you haven’t made any errors in your implementation.

        1. Demolion says:

          The checks are needed because we are looking at line segments, not full lines. Two roads may fail to intersect because one or both are too short.

          As a minor point, the equations you wrote fail if one of the lines is vertical. This is why the code uses lines in the form

          a x + b y = c

          rather than

          y = m x + c

          .

          1. Nimrandir says:

            When I had to do this back in the mists of time, I led with a check for verticality. However, my code was only supposed to produce equationsfor lines, rather than compute an intersection point.

            1. Abnaxis says:

              While this is kinda lazy, the probabilities are pretty vanishingly small for having a vertical line, depending on how many bits your numbers use. You’d have to randomly generate two floating point/double x values with identical values

              1. Droid says:

                For a line pointing in a random direction? Yes. For a grid of mostly north-south-oriented roads? Less so.

              2. Nimrandir says:

                For context, this was for a freshman-level computer science course, and the assignment was to output a linear equation for a given pair of input points. I doubt my professor would have been okay with y = NaN x + foo, and I guarantee he would have tried to make that happen.

        2. 4th Dimension says:

          When I posted this, I didn’t refresh to see if there were more posts in the meanwhile.

    2. Abnaxis says:

      While you’re right, and you can use the high school algrbra of “plug one equation into the other” I wonder if it would be computationally better somehow to use linear algebra to do it?

      It probably wouldn’t even be that much code if you used point-slope form instead of converting equations

      1. Abnaxis says:

        OK, because I’m anal and can’t resist little problems like this, here’s how you solve the problem with a matrix:

        * Pick a point from both lines. Either point, doesn’t matter.
        * Calculate the slopes for each line: (y2-y1)/(x2-x1) = slope
        * Left hand side (LHS) matrix (2 by 2):
        [-slope1, 1]
        [-slope2, 1]
        * Right hand side (RHS) matrix:
        [y1-slope`1*x1];
        [y2-slope`2*x2];

        then [x;y] = inverse(LHS)*RHS. It’s pretty easy to calculate the inverse of a 2 by 2, you can look it up online :)

        I thiiiiiiink this does the same number of operations, but I’m betting it’s a fraction of the lines of code compared to the solution Shamus got.

        1. Droid says:

          The part of his code that you’re discussing is 11 lines long (before that is a bounding-box check that you do not do, and after that is a line SEGMENT check that your code also doesn’t have, but is needed.

          If you want to look at what exactly the code is doing, look up Cramer’s rule.

          1. Abnaxis says:

            I mean, what I’m doing is also Cramer’s rule, except I’m explicitly constructing the matrices.

            You don’t need bounding box or segment checks because of how Shamus has defined his lines (he starts with a bounding box then exclusively has lines that cross the box horizontally or vertically. Every vertical line crosses every horizontal line within the box, and vice-versa).

            Finally, he’s probably got code laying around for solving a linear system that could be reused in my version.

            1. Droid says:

              But explicitly constructing the matrices adds potentially numerically unstable operations that have been simplified in the code above.

              And even if it doesn’t hurt for 2×2 matrices, inverting a matrix is never something you should do on a computer if all you want to do is solve a system of linear equations numerically. Just about every other way of doing it is better numerically, even if it seems like it’s less work algebraically.

              And I understand that you don’t necessarily need the lines of code when applied to these specific line segments, but
              1) Shamus may want to expand the road system in a future article, making the extra checks necessary again.
              2) He also may want to apply the function to line segments other than the roads in this current project in the future.

              The code Shamus got is good in what it does. It simplified the part that you were discussing down to scalar (float) operations that the CPU and FPU can directly process, with as few wrappers around it as convenience and readability allow. They actually improve upon your proposed code wherever you end up dividing and then multiplying by the same value (which generally means a loss of precision, especially if dividend and divisor are of nearly the same size). It, however, does not assume anything about the type of line segments in question, so it is still universally applicable to any two line segments in the same (Euclidean) plane.

              And if you already assume that Shamus has a linear solver that he can just use after your calculations: Why not use the same linear solver to solve the matrix-vector equation in the first place?

              I don’t write this because I want to imply that your work is bad, it’s algebraically fine and, if computation speed and finite precision were not an issue, e.g. when computing things symbolically by hand on a blackboard, would probably yield optimal results. Especially considering how nicely you can write matrices by hand as opposed to on a computer.
              But the ramifications above make your solution measurably inferior in precision and computation speed when compared to the code in the article. If you don’t believe me, any textbook on numerical solvers of linear equations should agree with me on this (especially the “don’t invert the matrix A to solve Ax=b for x” part). If you want, I might dig up one in English as a source.

  3. Droid says:

    Finding the intersection of two line segments is quite tricky, don’t undersell yourself like this!

    You have to:
    – first, find the two lines that continue the respective line segments (so if (x1,y1) is the start and (x2,y2) the end, you would already have to know the two-point formula),
    – then see if they intersect (by solving a system of linear equations, since the point on the intersection is the only one that fulfils both line equations a1*x+b1*y+c1==0 and a2*x+b2*y+c2==0),
    – then see if the intersection point actually lies within the segments of the line that you started with. That requires you to either do two checks per line segment (“is the distance between the intersection point and the starting point of the segment less than the total length of the segment? If yes, is that also true for the intersection point and the end point?”) as done here or mess around with special coordinate systems.

    Of course, it’s not made any easier for you by the code, because the only relevant comment for steps one and two above is the name “det”, which alludes to “I solved this system of linear equations using the line-line intersection formula given two points” (second link above). I guess the names a1, b1, c1, etc. also allude to the line equation of the form ax+by+c=0, but that’s not really all that helpful, because it alludes to what format you used, not what method.

    1. Dan Efran says:

      Yeah, that “det” is frustrating. That function’s author values self-documenting code enough to spell out intersection_position.x, but couldn’t be bothered to write out “determinant”. Thus, what could have been a good clue/search term for those needing an explanation of the algorithm becomes a hint only for those who already understand! Grrr.

      1. Droid says:

        Well, you could argue that “det” is okay because it is the name of the actual mathematical function Det that calculates the determinant of a matrix, as well as the function name of implementations of Det in most programming languages.
        So a Google search would actually make that connection for you. What is missing here is not the connection det -> determinant, but rather determinant -> “solving a system of linear equations using Cramer’s rule” or determinant -> “using a formula derived from projective geometry to solve said system”.

        In either case, it’s a huge step missing, and even if you don’t care for the mathematics involved, it means you’ll have a very hard time if you ever plan to change this code in any way, all just because the coder couldn’t be arsed to write two helpful words, like “Cramer’s rule”.

      2. Shamus says:

        I named the “intersection_position” variable. In the original code it was called “ip” or “isec” or something else less clear.

        The comments are also mine, and so is “to_intersection”.

    2. Decius says:

      Once you find the two lines, just compare the slopes to see if they intersect.
      To find if the point of intersection is within the segment, check to see if the x or y value of the intersection is between the x or y values of the endpoints of the segment.

  4. Geebs says:

    I’ve occasionally wondered whether to try Unity instead of throwing out everything I know about OpenGL and learning Vulkan or Metal or what have you. This business of stuff being either trivially easy or completely impossible sounds utterly maddening.

    1. default_ex says:

      If you choose to learn Vulkan you don’t have to throw out everything you know about OpenGL. A lot of what you learned about OpenGL applies in Vulkan. In my short experience with Vulkan it feels more like someone took OpenGL, removed the specific functionality, replaced it with generalized functions that can be chained together to create the specific functionality and peppered it with configuration structures to ensure your chain of functions behaves the way you want. Most of the paradigms and concepts you learned still apply, even calling conventions are remarkably similar.

      1. Richard says:

        ^ This.

        Vulkan is basically:
        Take OpenGL and a pile of OpenGL drivers. Look at the drivers and rip out almost everything that is almost the same in all the drivers, and let the application do it instead. The application probably knows what it needs better than the driver can guess.

        Of course, problems happen when the application does not know that.

  5. Nick Powell says:

    I come across maths problems like this all the time. The ones where I know I should have the knowledge the solve it and I spend a disproportionate amount of time trying to fix it until I start to wonder if actually I’m just really stupid.

    Programming can be depressing sometimes

    1. Droid says:

      This happens to me a lot, and I’m a maths student. And, as I’m told, not the only one this happens to.
      I’d say it’s a side-effect of mathematics nowadays consisting mostly of retracing the steps previous mathematicians have already taken. This is, of course, a good thing in general, as it allows us to learn much, much more than we ever could find out on our own, in one lifetime.
      But it spawns this thought in many students’ heads that learning new things in mathematics is about being rigorous, or “logical”, about finding the one true path from your premises to your conclusion.

      Much more often, though, learning things in mathematics, especially if you want to teach it to yourself, is similar to trying to find new solutions to new problems, which is ~30% about creativity,~50% about having a lucky ‘eureka’ moment, and only ~20% about being rigorous and logical.

      So if you’re good at rational thought and want to tackle a math problem, you might get stuck when you realize that there are so, SO many possible approaches to a solution, and none of them seem like they’re leading anywhere; to the point that you might think there is no approach at all, because none of the tools at your disposal seem to apply here.
      Solving such a problem usually requires a lot of guesswork, a lot of dead ends and a lot of frustration. And yes, a lot of feeling stupid, when in truth, it’s not your intelligence, especially not your ability to think rationally, that is underperforming, but instead your ability to recall and apply the right “trick”. Of course, a rigorous one, but in the end, nothing more than a trick.

      And to add insult to injury, once you’ve found the solution, of course, everything looks logical and therefore “simple”. It’s very easy to overlook the real hard work that went into this: finding the right idea to start from, the right steps to make progress, the right conditions to be able to tie everything neatly together. And yes, that includes rigorous deduction, but only as a small part of it.

      1. Nimrandir says:

        Have you gotten to complex analysis/function theory yet? It helps when you work through five different proofs of the Fundamental Theorem of Algebra, and they keep getting shorter as you go.

        1. Droid says:

          Yes, I’m already past the BSc courses, and function theory was one of my personal favourites.

          The post above is not to say that I’m struggling in general, I’m ‘getting’ most lectures and exercises sooner or later. It’s just that in the heat of the moment, after trying to tackle a seemingly ‘obvious’ problem and getting horribly stuck, after filling 6 pages with random approaches that all led to nothing, etc.; that can really get to you from time to time.

          So I can totally see where you’re coming from, Nimrandir, and I’m trying to come up with similar connections as much as I can, since, the way I see it, the more connections between different topics and disciplines you can come up with, the better your (comparatively low-level) math framework will support the more difficult/abstract concepts to come.

          All I wanted to say with my miles-long post is that I can very much relate to Nick Powell and that I think it’s too much to expect from yourself to just “get” a completely new concept or approach just because you know you can get there somehow through rigorous logical deduction.
          Especially if you’re just researching a topic on the internet, as opposed to having a professor explain things to you and having the possibility to ask specific questions when you need to.

  6. Viktor says:

    Wait, you homeschool your kids. Do you not have an HS Algebra book lying around? What you’re doing is a lot of steps, but the actual math involved should be relatively east to look up. Or was it just that you were thinking of it as a Unity problem and looking for a Unity solution, not a math problem that needed to be translated to code.

    1. Shamus says:

      This is one of those things that’s easy if you already know what you’re looking for.

      Would it be in Algebra 1, or 2? Or maybe it’s in Geometry? Heck, it could even be in Trigonometry. What am I looking for? It might be called “Line Intersection”, but it might be called something else. Furthermore, there are other concepts that might be filed under “Line Intersection” that have nothing to do with what I’m looking for.

      You can spend a lot of time thumbing through textbooks, or you can type things into a search engine. I did the latter and got the source code, so that worked out. :)

      1. Kathryn says:

        If you should have occasion to look for a more general solution in the future (that is, intersections of higher order polynomials), “Newton-Raphson method” is the search term you need. (it would also work for lines, but with lines, it’s basic algebra)

        1. Droid says:

          Yup, with lines, the Newton-Raphson method is even guaranteed to converge after a single step, no matter how small the allowed tolerance. ;-D

          1. Kathryn says:

            Yep!

            Shamus – another search term for stuff like this is “numerical method”. Numerical methods is the branch of mathematics that deals with approximating answers to problems that either can’t be solved directly or that would be a massive pain to solve directly. This morning, I searched on “numerical method for finding intersections of lines” and got plenty of applicable results (though most were Newton’s method). I did not have time to do a write-up for you, though, and it has been covered by the others now :-)

            I am an engineer, not a mathematician, but if I ever did go back to school/get a Ph.D (extremely unlikely at this point), it would be for math, and I would specialize in numerical methods. It’s a very interesting line of mathematics.

            1. Decius says:

              I can’t think of why there would be a numerical method specific to lines, but applying one that can be used for arbitrary curves to flat curves would work.

            2. DrCapsaicin says:

              I went to grad school for Nuclear Chemistry and had to (self-taught) mess around with some molecular dynamics simulations in C++. I’m a terrible coder, but Numerical Recipes by Press, Teukolsky, Vetterling and Flannery was absolutely invaluable. They have a lot of higher order geometry as well as things like Mersenne Twister pRNG calculations and much much more. If its crazy and the math is funky and you need to put it into code, there is a decent chance they have a snippit of code for it.

              Be careful though: old editions of this book were all in fortran (shudders)

      2. Daemian Lucifer says:

        Not to mention that while these are simple for a human, translating them to code can be very difficult, depending on how the program generated the lines in the first place.

        1. Decius says:

          So long as you are able to pick two different points on the line and get their coordinate values, it doesn’t matter how the line was generated.

      3. Sabrdance (MatthewH) says:

        Not programming, but algebra is officially a key part of my day job, and though I immediately knew to use the formula for lines to calculate if an intersection exists -the modification to check for whether the intersection occurs on the line segment would have required me to look it up -and I don’t have any idea where to look for it, either.

        It’s not obscure, I’m sure, but it probably doesn’t get used much.

        And the Internet is a wonderful thing.

        1. Decius says:

          Is there even a way to check if the intersection of two lines is on a line segment easier than finding the intersection?

          1. Droid says:

            We discussed this in a geometry course a year or so ago, and the answer, I think, is that you can check whether the endpoints of line segment S are “on the same side” of the line through the other segment T (more precisely, on the same half-plane). Then you check the same thing with T and S swapped. If both are false (i.e. both line segments lie “on both sides” of the other line segment), they intersect.

            1. James says:

              Although the particular formula to check if two points are “on the same side” of a line is not obvious to me, I really like how you described this method because I can actually picture how it works. I always grasp math principles a lot better when there’s a visual representation for it. Like, I had a ridiculously hard time in calculus understanding derivatives until one of my professors demonstrated them as graphs of the slopes of the tangent lines of a function (assuming 2 dimensions). Same goes for integrals… I didn’t understand what they “were” for years, until someone demonstrated them as the area under a function over a particular range (assuming 2D again). I’m simplifying those explanations of course, but visualizing calculus in terms of geometry gave me a way to actually grasp what the numbers were “doing”.

              1. Droid says:

                I actually had to look up the formula myself. I remembered it had something to do with determinants, and indeed, if you want to check whether the segment from point R to point S lies “on both sides” of the segment from P to Q, you basically check if the triangles (P, Q, R) and (P, Q, S) have different orientation.
                Geometrically, that means if you make a full loop around the outside of one triangle, then compare it to a loop around the other, as long as you go from P to Q and not in the other direction, one of the loops will be clockwise and the other one counter-clockwise. If the line segments don’t intersect, both loops will be clockwise, or both will be counter-clockwise.
                Intuitively, this means if you look along the line segment PQ, one of the points is gonna be to your left, the other one to your right.
                Finally, the algorithm to check the orientation of the triangle PQR is the determinant of the matrix that has a row filled with 1s, followed by p_1, q_1 and r_1 in the second row, followed by p_2, q_2, r_2 in the third row:
                [ 1, 1, 1;
                p_1,q_1,r_1;
                p_2,q_2,r_2]
                Actually, we only care whether the determinant is positive (point R is on the left), zero (the points are collinear) or negative (R is on the right), so we use the SIGN of the determinant above.

                orient(p,q,r) = sign(p_1 q_2 ? p_2 q_1 ? p_1 r_2 + p_2 r_1 + q_1 r_2 ? q_2 r_1).

                And the line segments PQ and RS intersect if and only if orient(p,q,r) != orient(p,q,s).

                Regarding your math teacher: I’d say I’m surprised, but there’s apparently soo many horrible math teachers out there that this isn’t even all that unusual. We even have a few people here at master’s degree courses in mathematics who hated math (and their math teachers) and only later found out how good they are at it, how great it can be to figure out a math problem and how useful it can be in real life.

                So, yeah, it’s great that you finally found a way to work with these rather abstract concepts! If you feel inclined to tackle some more (with really great visualisations), definitely check out 3Blue1Brown on YouTube. The guy is a wizard when it comes to visual intuition!

                1. Decius says:

                  First that looks like just as much work as determining where the lines intersect and checking if that point is within each segment.
                  Second, that particular algorithm won’t detect intersecting line segments on the same line.

                  1. Droid says:

                    It requires more work to justify but checking the sign of the expression above twice, once for PQR, then for PQS, is just 12 multiplications, 6 additions and a bitwise comparison or two in total (the question marks are supposed to be minus signs by the way).
                    That compares favourably to the four Length() calls alone (with two multiplications each, and, more importantly, the Sqrt() call within it), and is about as much work as the whole part that calculates the intersection point. (which also has 12 multiplications/divisions total)

                    You would need to check for line segments on the same line no matter what, at least none of the algorithms proposed on this page catch that special case (Shamus’ in particular returns False as soon as the determinant is zero, which it is for all parallel lines, including two identical lines).
                    And it’s numerically very unstable to boot, no matter what your algorithm does, because in terms of stability, checking whether 3 points are collinear is an ill-posed problem.
                    Lastly, in that case, what would the intersection point even be if you were to tackle the problem that way?

      4. Decius says:

        Geometry, and what you want is the insight that the intersection of two sets of points is the set of points where the equations describing them intersect, and solving the system of simultaneous equations. There’s probably a math library for that.

        The line described by y=5x+3 intersects the line described by y=-1/5x+100 at the x-coordinate where 5x+3=-1/5x+100.

        The first line intersects the circle around the origin of radius 5 (x^2+y^2=25) at the two points where x^2+y^2=25 and y=5x+3 are both satisfied.
        y=+/- (-x^2+25)^.5=5x+3
        (5x+3)(5x+3)=-x^2+25
        25x^2+30x+9=-x^2+25
        26x^2+30x-16=0
        (apply quadratic formula)
        x = -15/26 +/- sqrt(641)/26

  7. Piflik says:

    You can do image effects in Unity via the OnRenderImage function. Here is an entry point into writing your own PostProcessing effects.

    For common effects, like dithering, bloom, color correction, etc, there is Unity’s “PostProcessing Stack” which you can download for free from the Asset Store (or you can get it from Unity’s GitHub; you can find the most recent stuff there, including experimental; the PostProcessing stack has a V2-branch, haven’t tried it myself, though). You could use it’s Color LUT to very easily reduce the color-resolution, for example.

    1. Echo Tango says:

      Yeah, I was going to say, this should be doable.

  8. time to start over again in the godot engine

    (it’s really nice! and completely open source!)

    1. I have been waiting for godot!

  9. ReticentKaiju says:

    I ran into this same problem with framebuffers in Unity trying to do almost the exact same thing you described (making a “32-bit” style graphics shader with modern lighting and shadow effects). I ended up using a rather stupid hack with multiple cameras pointed at rectangles containing RenderTextures, all because I couldn’t make heads or tails of the Unity documentation on post-processing. I have no idea how well this would be handled by the graphics processing or what kind of performance hit it would take compared to using standard framebuffers, but my game was simple enough that it wasn’t noticeable.

  10. bionicOnion says:

    At the risk of offering unsolicited coding advice, I’m not sure that you need to declare intersection_position with the ‘ref’ keyword in the code sample you gave. It’s my understanding that that keyword is useful when you want to reserve the right to construct a new object to replace the passed-in value (something like ‘intersection_position = new Vector2();’ in the body of that method); since objects are passed by reference in C# by default, I don’t think that the usage of ‘ref’ is gaining you anything here unless I’m missing something.

    At the further risk of offering unsolicited recommendations, this is probably a context where I’d use the ‘out’ keyword. The value of intersection_position is irrelevant when it’s passed in; it’s just there as a placeholder to return the result of the computation in. Using ‘out’ more closely matches those semantics, plus it plays nicely with type deduction, at least in C# 7. In the end, a call to Intersects might look like this:

    if (a.Intersects(b, out var intersection_position))
    {
    // In this block, intersection_position exists and is (presumably) valid, since Intersects returned true
    }
    else
    {
    // Here, intersection_position is out of scope, but that’s probably fine, since it was invalid anyway
    }

    Combining the ‘out’ keyword with a method returning a bool rapidly came to be one of my favorite go-to tools in C#, especially once C# 7 streamlined the syntax a bit.

  11. Aanok says:

    I am almost certain you already know of it Shamus, but you might want to take a look at Return of the Obra Dinn by the guy who made Papers Please.

    It is (a remarkable game and) a 3D project done in Unity, with a fairly detailed development log, that pushes the idea of dithering and pixelation to the extreme of 1 bit rendering. If anything, it’s an interesting read.

  12. Decius says:

    Assuming that the lines are guaranteed to be coplanar and not the same line:
    Put the lines into standard form:
    Pick two different points (Xn,Yn) on a line.
    Check for vertical:If X2=X1, line is of the form x=X1.
    Find the slope: (Y2-Y1)/(X2-X1)->m
    Find the Y-intercept: Y1-X1*m->b
    Repeat for the other line(s).
    If two lines are both vertical, or have the same slope, the lines do not intersect.
    Otherwise, a line of slope m1 and Y-intercept b1 intersects a vertical line x=X2 at (X2, m*X2+b).
    A line of slope m1 and Y-intercept b1 intersects one of slope m2 and Y-intercept b2 at the X-coordinate of ‘(b2-b1)/(m1-m2)’, and the Y-coordinate ‘m1(b2-b1)/(m1-m2)+b1’.

    As an added bonus, you can compare the slopes to determine the angle of the intersection. Arctan(m1-m2) should give the angle between the two; specific use cases might benefit from an absolute value somewhere in there.

  13. Good news! Apparently with the latest update released yesterday (May 2), Unity opened up the render pipeline, and it’s now scriptable. I know you write these ahead of time, and the project might be done with already, but it’s still something to look into.

  14. Shivanshu says:

    You can go to Unity assets Store and download “Post Processing Stack” by Unity. It is free and provided by Unity itself and it seems like the “post processing effects” is dicontinued by Unity in newer Versions.
    Also “Post Processing Stack” is open-source and hosted on the above Git-hub link.
    Also on catlikecoding, In section 2.5, you can see tutorials like bloom, depth of field and other post-processing effects. Maybe you can find it useful.

    1. Shivanshu says:

      Also you should look at the new Unity 2018.1 . It looks like it has a lot of cool features like ProBuilder which you maybe able to use to procedurally generate your city.

  15. After releasing Gleaner Heights on Steam, I got Game Maker Studio 2 and tried to import the game to that version, since it was originally made in 1.4. For starters,
    the ease of converting a project to this new version of the software is a major selling point and is advertised as such by YoYo.

    What baffled me to no end was that, among other problems, in my imported version of the game in Studio 2, when entities moved upwards, their sprites flickered a lot.

    I won’t bother you with pointless technicalities. At some point, due to dumb luck and intuition, I bothered changing a built-in variable of the main character object, depth (since it was related to my problem), in the following way: Instead of

    depth=-y

    I wrote

    depth=y
    depth=-depth

    And the problem disappeared.

    For those of you who are even 1% into programming, you can see the ridiculousness of the thing. These two pieces of code should have the same effect! Except they don’t! For weeks I’ve been testing and fidding with stuff desperately, posting in forums, filing bug reports over at the help desk, being talked down by “experts” in forums who repeated basic stuff I’ve already read and insinuating it’s somehow my fault that I can’t get things to work in this Awesome New Version. What the actual fuck am I supposed to take away from this? What manner of obscure arcana governs these engines?

    So yeah, I can understand Shamus’ frustration. And this little adventure definitely reminded me of that article Shamus wrote about forum communication. I’ll probably have to link to it in my sig in these places lol

    Sorry for any typos, I’m writing this from my phone.

Thanks for joining the discussion. Be nice, don't post angry, and enjoy yourself. This is supposed to be fun. Your email address will not be published. Required fields are marked*

You can enclose spoilers in <strike> tags like so:
<strike>Darth Vader is Luke's father!</strike>

You can make things italics like this:
Can you imagine having Darth Vader as your <i>father</i>?

You can make things bold like this:
I'm <b>very</b> glad Darth Vader isn't my father.

You can make links like this:
I'm reading about <a href="http://en.wikipedia.org/wiki/Darth_Vader">Darth Vader</a> on Wikipedia!

You can quote someone like this:
Darth Vader said <blockquote>Luke, I am your father.</blockquote>

Leave a Reply to Viktor Cancel reply

Your email address will not be published.