tag:blogger.com,1999:blog-2715968472735546962.post5967674301910642877..comments2024-05-21T07:09:03.959+02:00Comments on Bannalia: trivial notes on themes diverse: Filmation mathJoaquín M López Muñozhttp://www.blogger.com/profile/08579853272674211100noreply@blogger.comBlogger62125tag:blogger.com,1999:blog-2715968472735546962.post-90968767239476433922023-12-01T11:32:08.989+01:002023-12-01T11:32:08.989+01:00I am completely fascinated! This post of yours is ...I am completely fascinated! This post of yours is awesome! I thought that I understood the principles of Filmation technique when I learned 5 weeks ago the concepts of partial order, total order, and topological sorting, but... your figure with prisms A,B,C has blown out my mind! It is true: "be behind" does not have the transitive property that every partial ordering must have.<br /><br />Yesterday I had to check it, in the computer game I am programing in ZX Spectrum Z80 assembler: I prepared 3 sprites in my 3D environment as in your figure, and the program jumped to a piece of code to return to Basic with an informative error message. I was so confident that this code would never execute that I commented the source with something as "in this point we have not found a minimal element, which should be impossible" (ouch!). <br /><br />Thus, thank you so much!<br /><br />PS: I am thankful to you also for your post "The isometric room" (Feb 28, 2008), because your trick "if(!new_pivot)++pivot;" allows me to solve the "no-minimal-element-found" situation with your "use-the-first-unsorted-element" solution.Conrado Badenashttps://www.blogger.com/profile/15776089433326147618noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-90662651096303680642020-07-18T08:58:33.811+02:002020-07-18T08:58:33.811+02:00Great article Joaquín, I wrote something along the...Great article Joaquín, I wrote something along the same lines years ago after trying to convince some folks on forums that a drawing order alone is not the answer to isometric projection. http://www.servo7.co.uk/iso/Anonymoushttps://www.blogger.com/profile/10171802810341060779noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-50680831240098942552017-03-02T03:35:40.082+01:002017-03-02T03:35:40.082+01:00So I guess John Ritman (Head Over Heels) outsmarte...So I guess John Ritman (Head Over Heels) outsmarted us all by stating (in God's voice) "If you have a tall sprite, like the main character, better divide it vertically in two or you will definitely have problems..."Anonymoushttps://www.blogger.com/profile/09834830662977459378noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-19533836526090517012016-08-24T20:01:50.820+02:002016-08-24T20:01:50.820+02:00Cool :-)Cool :-)Joaquín M López Muñozhttps://www.blogger.com/profile/08579853272674211100noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-48357505609200987742016-08-24T19:50:27.371+02:002016-08-24T19:50:27.371+02:00Here it is :)
https://arthursantana.github.io/pos...Here it is :)<br /><br />https://arthursantana.github.io/posts/iso/roxhttps://www.blogger.com/profile/07204669572707780537noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-40286114714672900702016-08-23T17:12:12.783+02:002016-08-23T17:12:12.783+02:00I'll be happy to read it when you publish that...I'll be happy to read it when you publish that!Joaquín M López Muñozhttps://www.blogger.com/profile/08579853272674211100noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-14390029374690481912016-08-23T17:00:20.119+02:002016-08-23T17:00:20.119+02:00You are right about that. P is 3x3, but after we c...You are right about that. P is 3x3, but after we change basis with B we can discard the component that is orthogonal to the plane and end up with a 2x3 modified B*P matrix (in fact you can choose B to be 2x3 already and things work out automagically).<br /><br />If you are interested, I'm considering writing down the derivation on a blog post (I only have it on paper).roxhttps://www.blogger.com/profile/07204669572707780537noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-66590263322257396892016-08-23T16:52:19.810+02:002016-08-23T16:52:19.810+02:00I have to admit that I couldn't follow you --f...I have to admit that I couldn't follow you --for one, B*P looks like a 3x3 matrix (you don't state the dimensions of P, but you say it has a diagonal, so I assume is 3x3) where a 3D->2D projection would use a 2x3 matrix.<br /><br />Anyway, I'm glad your own calculations solved the problem for you :-)Joaquín M López Muñozhttps://www.blogger.com/profile/08579853272674211100noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-28753412366834811642016-08-23T16:40:22.829+02:002016-08-23T16:40:22.829+02:00I played a little more with the problem, and found...I played a little more with the problem, and found that if I scale your transformation matrix by sqrt(2)/2 and further scale the screen-y vector by 3/2, I get exactly the transformation matrix I had calculated earlier.<br /><br />That's clearly caused by the normalization of the screen basis vectors, so that's where we diverge.<br /><br />Incidentally, something interesting came up: the projection matrix turned out to be unnecessary! When I changed the basis to the screen vectors, all that I needed to project was to zero the z component, since it was made orthogonal to the screen plane.<br /><br />Another thing to note if you or anybody else wants to follow the proof (attempt) is that you can invert an orthogonal matrix simply by transposing it. Forgetting that the screen basis was orthonormal made me waste a lot of time computing Gauss-Jordan by hand.roxhttps://www.blogger.com/profile/07204669572707780537noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-83459755058132930702016-08-23T13:05:30.978+02:002016-08-23T13:05:30.978+02:00Hi Joaquín,
Sorry for that, I changed the variabl...Hi Joaquín,<br /><br />Sorry for that, I changed the variable names while editing and changed it wrong :)<br /><br />I meant B*P. What I did was project into the plane with basis [1 -1 0]' and [1 0 -1]', then express the projection in terms of the basis [-1 1 0]',[-1 -1 2], [1 1 1]' (after normalizing it). If I made some mistake, it was probably on the choice of these vectors. Also I inverted the 3D axes x and y because I wanted a right handed system.<br /><br />When I started, I expected to get the same result as your first formula, but something way uglier came up (although I can see that is only a relative scaling x/y, the transformation matrix has 0's on the right places).roxhttps://www.blogger.com/profile/07204669572707780537noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-57428892163739747372016-08-23T09:39:45.503+02:002016-08-23T09:39:45.503+02:00Hi Rox,
I must admit I'm not fully getting yo...Hi Rox,<br /><br />I must admit I'm not fully getting your formulas since you mention an M (in B*M) that is not defined before. For what it's worth, in the article the following transformation is given<br /><br />(x,y,z) → (x0 + √3 x/2 − √3 y/2, y0 − x/2 − y/2 + z)<br /><br />that is usually approximated (maybe this is what you are referring?) by<br /><br />(x,y,z) → (x0 + x − y, y0 − x/2 − y/2 + z)<br /><br />which is simpler to handle from a pixelization point of view.<br /><br />Joaquín M López Muñozhttps://www.blogger.com/profile/08579853272674211100noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-20228346236689143562016-08-23T00:25:10.841+02:002016-08-23T00:25:10.841+02:00Hi Joaquín,
Thanks for the post, very interesting...Hi Joaquín,<br /><br />Thanks for the post, very interesting.<br /><br />I believe that your projection formula distorts the image a little, since your x and y vectors have different norms, ain't that the case?<br /><br />I tried the little linear algebra that I know and ended up with these transformation matrices, using an orthonormal basis for the screen (x,y):<br />Projection matrix P = 2/3 on the diagonal, -1/3 elsewhere;<br /><br />Change of basis matrix B = [-sqrt(2)/2 sqrt(2)/2 0; -sqrt(6)/6 -sqrt(6)/6 sqrt(6)/3; sqrt(3)/3 sqrt(3)/3 sqrt(3)/3].<br /><br />If I haven't got anything wrong, B*M should be the linear transformation that takes the 3D vector and gives back the normalized coordinates on the screen (you still need to add the origin point).roxhttps://www.blogger.com/profile/07204669572707780537noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-56563050172586372292016-05-27T17:02:19.231+02:002016-05-27T17:02:19.231+02:00Okay yes it makes sense, thanks very much for the ...Okay yes it makes sense, thanks very much for the discussion! tdhttps://www.blogger.com/profile/18361166031404139480noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-16607422800881717072016-05-27T12:07:23.126+02:002016-05-27T12:07:23.126+02:00The equations depend on the particular coefficient...The equations depend on the particular coefficients for the projection formula we are using<br /><br />(x,y,z) → (x0 + x − y, y0 − x/2 − y/2 + z),<br /><br />that is, (1,-1,0) for x, (-1/2,-1/2,1) for y. With other cofficients th resulting equations would be different. For instance, if you consider the image were the two prisms labeled A and B are depicted and try to imagine how it would change as you rotate the 3D scene around the z axis, it's easy to see that at some point the projections would not overlap --hence the equations are not "universal" for any orthogonal projection, but specific to its particular coefficients.Joaquín M López Muñozhttps://www.blogger.com/profile/08579853272674211100noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-82801088996583277852016-05-27T11:27:03.850+02:002016-05-27T11:27:03.850+02:00Thanks a lot for the clarification! Im still tryin...Thanks a lot for the clarification! Im still trying to get my head around it a little; do equations 1,2,3 in the article work just the same for skewed projections? I dont quite understand whether the rules [e.g. (x-y',x'-y)] are general rules which you apply to the projected points of the prism, or if it includes projecting the prisms to hexagons with the approximation you give also?<br /><br />For example, if I have a camera that could be projecting from any angle, can I use the same rule by applying 1/2/3 to my 2 vertices after the projection is done?tdhttps://www.blogger.com/profile/18361166031404139480noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-47121251796820628282016-05-26T20:22:43.032+02:002016-05-26T20:22:43.032+02:00Given a prism there are two and only two vertices ...Given a prism there are two <i>and only two</i> vertices (x1,y1,z1) and (x2,y2,z2) such that x1<x2, y1<y2, z1<z2. This has nothing to do with the fact that these two vertices coincide in their 2D projection --in fact, this could fail to be the case if the projection is skewed, as you point out.<br /><br />As for a proof of eqs. 1-3, it can be derived from the following. simple observation: label the six edges of an hexagon (or, rather, the lines they extend to) as a, b, c, d, e, f, starting from the top vertix and going clockwise. Do similarly with the second hexagon to get A, B, C, D, E, F. Then, it should be obvious that the hexagons overlap if and only if the followin three conditions are met:<br /><br /> 1. line A lies between a and d, or else line a lies between A and D.<br /> 2. line B lies between b and e, or else line b lies between B and E.<br /> 3. line C lies between c and f, or else line c lines between C and F.<br /><br />And 1, 2, 3 directly imply the overlapping conditions presented in the article.Joaquín M López Muñozhttps://www.blogger.com/profile/08579853272674211100noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-1489181896965845242016-05-26T13:35:39.265+02:002016-05-26T13:35:39.265+02:00Hi Joaquin
Great article thanks!
I'm a littl...Hi Joaquin<br /><br />Great article thanks!<br /><br />I'm a little confused how you pick the opposing vertices. The rule is that x1 < x2, y1 < y2, z1 < z2, and I see in another post you say the two picked for this are the front and back vertices in the center of the hexagon. <br /><br />If you rotated the camera slightly, you would have that x1 == x2 for those points, and the rule doesnt fit... what do you do in this case? Can we simply pick any two opposing vertices that fit the x1 < x2, y1 < y2, z1 < z2 rule?<br /><br />It would be brilliant if you could provide a proof for equations 1-3 also!tdhttps://www.blogger.com/profile/18361166031404139480noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-61224221873894020612016-01-30T14:47:29.291+01:002016-01-30T14:47:29.291+01:00I just want to add here that its important that yo...I just want to add here that its important that your collision geometry and sprite prism consider penetration errors. Generally collision solving (specially if physics based) have some amount of penetration (floating errors, cant solve everything in one frame, etc.) So you can have sorting errors(maybe for a few frames) if you use the exact same size for collision and your sprite prism. Its better to leave some room (geometry a lil bit bigger than the sprite prism)Suminskyhttps://www.blogger.com/profile/00327398494394075000noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-42970364655168116892016-01-16T13:28:34.497+01:002016-01-16T13:28:34.497+01:00A quick note to let you know that I've just st...A quick note to let you know that I've just started on the Z-order algorithm tonight (everything else is complete), and will hopefully have nutted it out within a few days, depending on spare time.tcdevhttps://www.blogger.com/profile/17906878237742487968noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-7892665020130843902015-12-14T04:08:17.217+01:002015-12-14T04:08:17.217+01:00A note on that "bug" I found. Turns out ...A note on that "bug" I found. Turns out it isn't, I somehow missed a JP despite checking it several times. I was thrown because of the somewhat inconsistent implementation of the same algorithm in the same routine on the two different axes - and a completely unnecessary JP.tcdevhttps://www.blogger.com/profile/17906878237742487968noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-42569229204707139162015-12-14T00:22:33.102+01:002015-12-14T00:22:33.102+01:00I'll be releasing everything at some point. My...I'll be releasing everything at some point. My immediate goal is to finish commenting the Spectrum disassembly and the C port on the PC simultaneously. Then I want to port it to one or perhaps two retro platforms, and then I'll probably release all the source code with it. My final goal is to port it to the 6809-based Coco3.<br /><br />But I'd be happy to share the Z-order stuff with you once it's complete, since I'll be taking advantage of your work shortly. I'll let you know when I get it done.tcdevhttps://www.blogger.com/profile/17906878237742487968noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-67165284196723464272015-12-13T14:06:31.038+01:002015-12-13T14:06:31.038+01:00I'm afraid to say I didn't reverse-enginee...I'm afraid to say I didn't reverse-engineere the code at all: the Z-order stuff is basically self-evident, and the fact that Knight Lore shows a transitivity glitch as predicted by theory confirms that Ultimate guys followed the approach I describe in my blog entry.<br /><br />BTW, your project looks extremely interesting. I'd be delighted to have a look at the Z-order section once you crack it (and maybe post an addendum to my blog). Are you making your code available somewhere?Joaquín M López Muñozhttps://www.blogger.com/profile/08579853272674211100noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-15903124793591792422015-12-13T12:13:50.632+01:002015-12-13T12:13:50.632+01:00I just stumbled across your blog entry tonight! Th...I just stumbled across your blog entry tonight! Thanks for the insight, it'll come in very useful in the next few weeks, I'm sure, as I'm currently reverse-engineering Knight Lore to port it to a number of retro platforms. Whilst I'm commenting the original code, I'm also porting it to generic C code, preserving as much of the original Z80 code and data structure as possible.<br /><br />Check out my Retro Ports blog (which I assume you can access from my id) right here on blogspot.com.au.<br /><br />I've worked my way through most of the code (I can render rooms and have objects moving around) and am now getting down to the nitty gritty, such as the display order sorting and the wiping algorithm. Just now I've found what I believe is a bug in the wiping code, and so started searching for reports of a graphics glitch in Knight Lore (which led me here). It's obviously not a serious bug, but if I'm not mistaken, it doesn't calculate the correct number of lines to wipe a moving object in all cases.<br /><br />I'd be interested to hear how much (if any) reverse-engineering you did on the original code and whether you'd be willing to share your notes, as the display order is one of the remaining areas I've left until the end! ;)<br /><br />tcdevhttps://www.blogger.com/profile/17906878237742487968noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-33398744259823382632015-10-19T19:41:52.359+02:002015-10-19T19:41:52.359+02:00> [...] if they do overlap, we can apply the fo...> [...] if they do overlap, we can apply the following easily provable properties [...] Since the prisms A and B do not overlap (in 3D)[...]<br /><br />I think it would be better here to use "intersect in 3D" rather than overlap. This was pretty confusing for me. And it would be great if you could mention what [x,y,z] and [x',y',z'] refers to. Took me a while to figure it out in the comments.<br /><br />Anyways thanks for this article, it helped a lot!Anonymoushttps://www.blogger.com/profile/03521077128828980471noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-50888680709786323582015-10-19T18:11:13.617+02:002015-10-19T18:11:13.617+02:00As you correctly point out, the projections of the...As you correctly point out, the projections of these two blocks overlap yet none of the conditions 1...6 apply. The reason is that the blocks intersect <b>in 3D</b> (for instance, the point [0.75,0.75,0.75] is inside both A and B), and isBehind requires that this is not the case:<br /><br /><i>As objects are assumed to be convex and they do not overlap (i.e. A∩B = ∅)...</i>Joaquín M López Muñozhttps://www.blogger.com/profile/08579853272674211100noreply@blogger.com