The problem is that I cannot differentiate between a line that is completely outside of the view and a line that is partially inside the view reliably. Therefore, some lines which were completely outside get clipped to the view (so you end up with 0-length walls on the x=y/x=-y boundaries, or walls end up being flipped backwards behind the camera).
A related issue was checking if x1 > y1 (clip) else if x1 < -y1 (clip), as it's possible for a point to be both > y1 and < -y1 (if it's behind the camera). Most of it's fixed, I still have the odd zero-length wall issue.
Detecting if a line is completely outside the view before clipping it would be useful, and I can't work out how to do it, basically.
Progress thread for original version (2006)
Moderator: benryves
Determining if a line is totally invisible or visible:
Current status: Only got lines to clip left, because the line inbetween points 1 and 2 must go through either the x=y or x=-y camera fov boundaries. The rest is just a lot of boring cases, which I'll leave to you Ben 
[/code]
Code: Select all
// Totally behind camera?
if (y1 < 0 && y2 < 0) return INVISIBLE;
// Left side of the x=-y camera boundary?
if (x1 < -y1 && x2 < -y2) return INVISIBLE;
// Right side of x=y?
if (x1 > y1 && x2 > y2) return INVISIBLE;
// Totally inside camera view?
if (x1 > -y1 && x1 < y1 && x2 > -y2 && x2 < y2) return VISIBLE;
Ah, didn't see that one coming. Both boundaries must be crossed though, the two middle if-statements will sort out lines that only cross one of the boundaries behind the camera.
One way to skip divisions, although still having two multiplications, is to look at the line to be processed as a vector, create another vector from the origin to one point of the current line and do a dot-product. Examine the sign to see on if the clipped line would go behind the camera or in the fov.
Would work perfectly well on a computer
One way to skip divisions, although still having two multiplications, is to look at the line to be processed as a vector, create another vector from the origin to one point of the current line and do a dot-product. Examine the sign to see on if the clipped line would go behind the camera or in the fov.
Would work perfectly well on a computer
-
benryves
- Maxcoderz Staff
- Posts: 3087
- Joined: Thu 16 Dec, 2004 10:06 pm
- Location: Croydon, England
- Contact:
I believe Emmanuel D's method was to use a cross product-ish sort of technique.
I have a mockup (prototype, if you will) of the function in QuickBasic which works pretty much perfectly (I haven't put in the code for the simple cases y1=y2, x1=x2, m=1 or m=-1) but has a lot of what I would hope is redundant checking.
My description was rather poor, I was referring to this case:
a->b would be in view, c->d would be completely out of view, yet both lines start/end in the same zones. (Assuming the camera is looking down the screen).
I have a mockup (prototype, if you will) of the function in QuickBasic which works pretty much perfectly (I haven't put in the code for the simple cases y1=y2, x1=x2, m=1 or m=-1) but has a lot of what I would hope is redundant checking.
My description was rather poor, I was referring to this case:
Code: Select all
\ /
\ /c
\ /
\ /
\ / a
_____\/_____
d /\
/ \
/ \
/ \
b/ \
/ \/ \If you use Emmanuel's method (or mine, they were pretty similar but he derived his with a tinsy bit of maths, I just jotted down some generic geometry stuff 
), you will see the difference between the lines a-b and c-d (both methods are based on checking on what side of the origin the line would go). Two muls aren't that bad, but maybe you've already solved that in your routine
), you will see the difference between the lines a-b and c-d (both methods are based on checking on what side of the origin the line would go). Two muls aren't that bad, but maybe you've already solved that in your routine I haven't exactly read through all these posts, but I figured I'd offer my input anyways. So there's a clipping method called Liang-Barsky which might be useful to you. So I'm sure you know lines can be expressed in parametric form as:
p(a) = (1 - a) * p1 + a * p2 0 <= a <= 1
You can compute the intersection with a plane by this equation:
a = (n . (p0 - p1)) / (n . (p2 - p1))
where p0 is on the current plane
which takes 6 multiplications and 1 division. But (I'm gonna go out on a limb and assume you're using the usual divide by z straight up projection stuff) if you instead look at projection as a shearing of the data and then an orthographic projection, the calculation actually reduces a lot. So basically instead of a general parallelpiped you'd have a right parallelpiped which is axis aligned. Now assuming you've already sheared the x and y coordinates with however you're projecting...
ie left viewing plane (correct me if I'm wrong):
a = ((1,0,0) . (p0 - p1)) / ((1,0,0) . (p1 - p2))
Notice how quickly things simplify with the orthogonal clipping planes? For each plane you do two subtractions and a division. I hope this was helpful because like I said, I didn't go searching through the last several pages of posts to find out what was said, but I wanted to help as best as I could.
Oh and for detection you can use what's called the Cohen-Sutherland algorithm. I don't exactly have the time to explain exactly how it works but you should look it up. It allows you to easily minimize computations with the use of quick bitwise and's. It's a pretty straight forward algorithm.
p(a) = (1 - a) * p1 + a * p2 0 <= a <= 1
You can compute the intersection with a plane by this equation:
a = (n . (p0 - p1)) / (n . (p2 - p1))
where p0 is on the current plane
which takes 6 multiplications and 1 division. But (I'm gonna go out on a limb and assume you're using the usual divide by z straight up projection stuff) if you instead look at projection as a shearing of the data and then an orthographic projection, the calculation actually reduces a lot. So basically instead of a general parallelpiped you'd have a right parallelpiped which is axis aligned. Now assuming you've already sheared the x and y coordinates with however you're projecting...
ie left viewing plane (correct me if I'm wrong):
a = ((1,0,0) . (p0 - p1)) / ((1,0,0) . (p1 - p2))
Notice how quickly things simplify with the orthogonal clipping planes? For each plane you do two subtractions and a division. I hope this was helpful because like I said, I didn't go searching through the last several pages of posts to find out what was said, but I wanted to help as best as I could.
Oh and for detection you can use what's called the Cohen-Sutherland algorithm. I don't exactly have the time to explain exactly how it works but you should look it up. It allows you to easily minimize computations with the use of quick bitwise and's. It's a pretty straight forward algorithm.
-
benryves
- Maxcoderz Staff
- Posts: 3087
- Joined: Thu 16 Dec, 2004 10:06 pm
- Location: Croydon, England
- Contact:
I've been fiddling about with the engine recently - not a lot has been changed, though I've started organising the engine a lot more neatly (for example, "ld ix,Level \ call Nostromo.Level.Load" will allocate the memory required and set up the engine to use the particular level you pointed it at). The worst offenders were the wall handing code and the movement code, so I rewrote both from scratch.
The wall code isn't too different, but changes the projection somewhat so that a level doesn't need to be 32,000 units wide to represent a room 2m wide The flags have also been changed, and you can now specify whether the left, right, top or bottom wall edge lines are drawn:
(Yes, I need a new level design!)
I've been back onto the clipping problem, and have actually done some work on it. As far as my rather shaky grasp of algebra goes, the following maths should work to snap the end of a line onto the y=x boundary:
The wall code isn't too different, but changes the projection somewhat so that a level doesn't need to be 32,000 units wide to represent a room 2m wide
The flags have also been changed, and you can now specify whether the left, right, top or bottom wall edge lines are drawn:(Yes, I need a new level design!)
I've been back onto the clipping problem, and have actually done some work on it. As far as my rather shaky grasp of algebra goes, the following maths should work to snap the end of a line onto the y=x boundary:
Code: Select all
# For clipping to y = x:
# δY/δX are Y1-Y0 and X1-X0 respectively (naturally).
if (|δY| > |δX|) {
m = δY ÷ δX
Clip = (Y0 - m Ãâ€â€And of course, as things get 3Dish, I jump in... Typical, eh?
What's excessive about the solutions proposed earlier in the thread? First a couple of comparisons and then two mults.
A little silly venture:
Express a line in parametric form, "p = u0 + u*t". Figuring out t for the two clipping planes is pretty easy (set "p.x = p.y" and "p.x = -p.y") and you get expressions similar to "t = (x0 - y0) / (y - x)". Compare t to the interval I = [0, 1]. Simple bound-checks and you can determine where the line. If t is in I, then you have to clip (just "p = u0 + u*t" ).
Whether this is practical on the calc, I dunno, I got enough programming problems myself :p The number of operations seem to get worse with this though, I'd suggest you benchmark the first solution to see if it really is too intensive.
What's excessive about the solutions proposed earlier in the thread? First a couple of comparisons and then two mults.
A little silly venture:
Express a line in parametric form, "p = u0 + u*t". Figuring out t for the two clipping planes is pretty easy (set "p.x = p.y" and "p.x = -p.y") and you get expressions similar to "t = (x0 - y0) / (y - x)". Compare t to the interval I = [0, 1]. Simple bound-checks and you can determine where the line. If t is in I, then you have to clip (just "p = u0 + u*t"
).Whether this is practical on the calc, I dunno, I got enough programming problems myself :p The number of operations seem to get worse with this though, I'd suggest you benchmark the first solution to see if it really is too intensive.
-
benryves
- Maxcoderz Staff
- Posts: 3087
- Joined: Thu 16 Dec, 2004 10:06 pm
- Location: Croydon, England
- Contact:
I guess I could (at least, for the moment) get away with snapping points to the boundaries if I'm unsure as to whether it's valid or not - if it's invalid, it'll (probably) just end up flipping the wall backwards behind the camera anyway (and checking for y < 0 is a simple operation). Think about optimisation later
I had a look at this old engine I was familiar with, and they seem to do it using the parametric method.
I had a look at this old engine I was familiar with, and they seem to do it using the parametric method.
you could try making it appear blue on the calculator.benryves wrote: (Added an adjustment layer in Photoshop to transform neutral colours to bright red, on the calc it's a grey - sadly I have not found out how do draw red pixels on the LCD)
The engine looks pretty good. Have you made any progress on making walls so they obstruct object behind them?
In Memory of the Maxcoderz Trophy 
-
benryves
- Maxcoderz Staff
- Posts: 3087
- Joined: Thu 16 Dec, 2004 10:06 pm
- Location: Croydon, England
- Contact:
I'm using the equations above (*points*) - it seems that the best way to fix this is to make sure that you clip to Y = 0 first, as that stops points being snapped to the wrong side. It feels a bit idiotic using fixed-point to represent a gradient (range: 0 to infinity), but it seems to work - sign errors permitting.
All is good until I walk onto the far side of the wall, and then it all goes mental. Seems to be a sign error (the way that the wall flips - turns into an X - seems to indicate that the depth of the clipped point is shunted behind the camera, which swaps the top and bottom).
All is good until I walk onto the far side of the wall, and then it all goes mental. Seems to be a sign error (the way that the wall flips - turns into an X - seems to indicate that the depth of the clipped point is shunted behind the camera, which swaps the top and bottom).