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:

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:

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 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:

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

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:

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:

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.

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…

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:

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.

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

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.
Steam Summer Blues

This mess of dross, confusion, and terrible UI design is the storefront the big publishers couldn't beat? Amazing.
Autoblography

The story of me. If you're looking for a picture of what it was like growing up in the seventies, then this is for you.
The Witch Watch

My first REAL published book, about a guy who comes back from the dead due to a misunderstanding.
My Music

Do you like electronic music? Do you like free stuff? Are you okay with amateur music from someone who's learning? Yes? Because that's what this is.
Good Robot Dev Blog

An ongoing series where I work on making a 2D action game from scratch.
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.
That’s wonderful; thank you for the link.
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.
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.
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.
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.
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
rather than
.
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.
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
For a line pointing in a random direction? Yes. For a grid of mostly north-south-oriented roads? Less so.
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.
When I posted this, I didn’t refresh to see if there were more posts in the meanwhile.
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
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.
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.
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.
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.
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.
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.
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”.
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”.
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.
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.
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.
^ 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.
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
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.
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.
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.
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.
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. :)
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)
Yup, with lines, the Newton-Raphson method is even guaranteed to converge after a single step, no matter how small the allowed tolerance. ;-D
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.
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.
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)
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.
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.
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.
Is there even a way to check if the intersection of two lines is on a line segment easier than finding the intersection?
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.
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”.
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!
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.
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?
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
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.
Yeah, I was going to say, this should be doable.
time to start over again in the godot engine
(it’s really nice! and completely open source!)
I have been waiting for godot!
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.
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.
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.
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.
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.
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.
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.
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.