CGA Graphics Programming: General Ellipses (Part 1)

Рет қаралды 674

Ай бұрын

We begin to make a plan for implementing general ellipses on an IBM PC/XT in 8088 assembly language for the CGA graphics card.
We discuss some of the choices we have and the pros and cons.

Пікірлер: 16

@koteth4505 Ай бұрын

I think it would also be possible (or at least interesting) to explore Feynman's construction. Feynman uses it for Kepler's orbits. This method allows the construction of ellipses and hyperbolas. Square and compass construction uses a reference circle and lines. The tools required are straight lines and the ability to draw an orthogonal line from the centre of another line. It sounds complex, but there may be arithmetic and algorithmic shortcuts. en.wikipedia.org/wiki/Feynman%27s_Lost_Lecture

@pcretroprogrammer2656 Ай бұрын

That's certainly an interesting one. I don't know if this could be done without square roots, but it would definitely be an interesting one to look at. Of course, back in the time of Kepler, everything was done the way the ancient Greeks did it, with a few additional tricks that were developed subsequently.

@JimLeonard Ай бұрын

You may want to fire up DeluxePaint II for the PC to see Dan Silva's solution to this. In that program, you first draw the standard ellipse, then hold down a mouse button to rotate it to the number of degrees you want. This implies that the algorithm is 1. calc regular ellipse, then 2. rotate all previously generated points around the ellipses' center point. This seems pretty fast to do since the rotations are only one axis. For ensuring there are no gaps in the rotated points when drawn, you draw lines between the points rather than the points themselves.

@pcretroprogrammer2656 Ай бұрын

It's really a surprising coincidence that the person who designed the general ellipse algorithm I used was Dilip Da Silva and the person who wrote Deluxe Paint was Dan Silva. They are definitely not the same person and it seems doubtful they are related. Really fun coincidence. Anyway, I will definitely take a close look at the ellipse rotation in Deluxe Paint II. It will be interesting to see how the pixel gap problem was solved, if at all.

@andrewdunbar828 Ай бұрын

A filled general ellipse is much harder than a one-pixel outline general ellipse. You convert the rotated ellipse formula to a sheered circle and then you can go through getting the left and right extend for every Y value. You can get any ellipse this way. for ellipses that are very skinny you often have to worry about precision artefacts so you'll want some logic to decide whether to do horizontal or vertical scanlines. I seem to remember that when you get to a certain point that general conics come into play. My maths skills fail me at this point. I never had an intuitive understanding for parabolae and hyperbolae that I had for ellipses either, which doesn't help.

@pcretroprogrammer2656 Ай бұрын

I may end up doing things this way too for comparison. I'm pretty convinced of the benefits of both methods at this point. I hope we'll get to parabolae and hyperbolae. But on this early hardware, there are no guarantees.

@andrewdunbar828 Ай бұрын

@@pcretroprogrammer2656 I was also thinking, if you're going to go to the trouble of implementing floating point, would implementing fixed point bignums be another alternative?

@pcretroprogrammer2656 Ай бұрын

@@andrewdunbar828 I think arbitrary precision is too general here and would be too expensive. You lose the benefits of fixed point. Of course, bignums might be a possibility for the corner cases. I think it sounds like a lot of work though. At least for floating point you could start with some routines used by a C compiler, e.g. TASM and just improve their code (if possible; more likely you would just adapt it to the specific requirements you actually need).

@andrewdunbar828 Ай бұрын

If you were to use square roots, what would be the input range? Would it depend on the screen resolution? If so, a lookup table is an option.

@pcretroprogrammer2656 Ай бұрын

Unfortunately the square roots would be of rational values, not integers, so lookup is probably not practical. But maybe there is a way to make it work somehow. Definitely worth thinking about.

@andrewdunbar828 Ай бұрын

@@pcretroprogrammer2656 There might be a version of the Carmack fast square root trick that will work?

@pcretroprogrammer2656 Ай бұрын

@@andrewdunbar828 For floating point, certainly.

@tehdasi Ай бұрын

The problem is that he's trying to do this on limited memory, and a lookup table with small enough error to be useful would prolly be too large to fit int he limited memory of an XT. Then again if he does get this working, I reckon at some point he's going to have to introduce error that he'd rather not have, so it might be a case of which method has the better trade off between speed and error. Anyways, we'll see.

@benjamindeharo314 Ай бұрын

Do you plan to make a tutorial about coding an emulator for an 8 bit pc like the zx spectrum someday ?

@pcretroprogrammer2656 Ай бұрын

I don't have plans for that as there are very good emulators already. I don't think I could improve on them.

@benjamindeharo314 Ай бұрын

@@pcretroprogrammer2656 Oh I didn't mean for you to do something nobody has ever done. There's only 1 tutorial about how to make a zx spectrum on youtube, and I find it hard to follow. So it could be useful for educational purpose, on top of just being a fun exercise.