4
$\begingroup$

I'm working on a Software Rasterizer on a sub-30 MHz RISC CPU My current focus is on zooming-in on a slowly rotating planet. For maximum quality, no 3D polygons are involved with the planet - the planet texturing is purely image-based. This is what I have:

  • the planet rotates only around Y axis and is always viewed straight on with camera at the equator (so you can't see poles, hence the default pole distortion artifact is not an issue here at all)
    • midpoint Bresenham circle algorithm to compute 8 endpoints at each iteration, effectively giving me 4 horizontal scanlines
    • simple linear remapping between texture row and planet's scanline - e.g. if the planet is 64 pixels tall on screen and texture is 128 pixels tall, I simply skip every other row
    • same linear remapping within each scanline - e.g. if the current scanline is 64 pixels wide, and texture is 128 pixels wide, I simply skip every other texel in current texture row

The above works and is great as a first working and reasonably fast prototype. However, when the planet rotates, despite the low screen resolution, due to the simple linear remapping (within each scanline), it does not feel and look like planet rotation, as the perspective/distortion/stretching at the sphere edges (left and right edge of the circle) is obviously missing.

What is the equation that can give me the exact texture coordinate, for a current texture row, of each on-screen pixel of that circle's scanline ?

Please note that I can't afford to compute sin/cos (or use precomputed tables). Division is expensive, but I could perhaps hide its latency via interleaving with other instructions (while division is being computed). So, ideally, I could compute it just via add/sub/mul/bitshift. Obviously, due to symmetry, that computed coordinate will be reused for 3 other points, so we're in reality computing that for only 25% points of the circle.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ What kind of CPU/system can hold useful 2D textures but not a short lookup table for an asin() approximation? A dozen entries + linear interpolation should be good enough for your application. $\endgroup$
    – Olivier
    May 10, 2017 at 20:10
  • 1
    $\begingroup$ It's not about lack of main RAM but about slowing down the RISC chip which gets effectively locked till a read from RAM is finished. Transferring texels is about the extent of RAM access that is doable in 30+ fps. The local cache is only 4 KB for both code and data. Problem is, it's 32-bit internally for read/write which either wastes a lot of precious cache or performance when you unpack single bytes from 32 bits. You mention dozen values for asin. Can you elaborate? 90 degrees/12 =~7 degree step, if I get you right. $\endgroup$
    – RubyNoob
    May 10, 2017 at 20:48
  • 2
    $\begingroup$ Yes, that's what I meant, with 12 being a rough guess. You would still have some distortion compared to the real asin() but probably not that much. Can your CPU do multiplications in reasonable time? If so, a cubic spline would be an even better approximation (more quality for the same table size). I think this can be done with integer math but float would be easier, if you have it. $\endgroup$
    – Olivier
    May 10, 2017 at 21:08
  • 1
    $\begingroup$ Conversion from float to int is usually last step, when I confirm in excel that the numbers work- but is necessary as floats are not supported and I try to avoid fixed point as much as possible. The multiplication takes just 3 cycles like add or sub or bitshift. Cubic spline is a great idea. I completely forgot about those! So far I managed to avoid tables, but if there's no other way I could sacrifice , say , 100 bytes for 25 values of asin , at 4 degree resolution. Or more- it's easy to tweak table size when hunting for acceptable level of distortion. $\endgroup$
    – RubyNoob
    May 10, 2017 at 21:49

2 Answers 2

Reset to default
3
$\begingroup$

Incidentally I implemented something similar for similar hardware some 20 years ago (:

IIRC, I calculated 1D look-up-table using acos for parallel projection of a cylinder and just scaled it for each scanline to reduce computation cost. The LUT just gives you x-coordinate offset to the texture and you add constant offset for each scanline for the rotation.

For y-axis the input texture can be preprocessed to have proper spherical distortion applied and you can just linearly scale the texture vertically. Though it's not that much extra computation to do it run-time either.

This doesn't give you proper perspective projection but might be enough for your purposes.

Edit: Didn't notice you said you can't afford LUT. You could do the table look-up every N pixels and linearly interpolate inbetween. This was a common method in the past to do affordable perspective correct texture mapping for software rasterizers to avoid div/pixel

Improve this answer
$\endgroup$
7
  • $\begingroup$ Nice demo! That is exactly what I'm doing right now ! I noticed you kept the radius small to keep the framerate high ;) Yes, I'm very often experimenting with how far I can push the division vs interpolation, often times I end up adjusting the dataset so I can replace division with bitshift. Since we can mirror the right half of planet, we need to cover just 90 degrees with the LUT. But, is the AngleStep per on-screen pixel, constant for those 90 degrees?So, if for current camera,equator takes up 180 pixels, e.g. half takes 90 pixels,then each pixel would correspond to 90/90 =1 degree step? $\endgroup$
    – RubyNoob
    May 11, 2017 at 14:10
  • $\begingroup$ I think I just realized what I need to do: Create a sphere in 3D, place camera right in front of it, transform each point on equator, and note the X coordinate. That will give me the exact distribution that I need for the LUT creation. I'm not sure why I thought initially I could get away without doing that - I was hoping there would be some simple math trick,as it's a sphere. Actually, I can do it in excel, as I have a tab that I used for testing the integer version of the 3D transformations... $\endgroup$
    – RubyNoob
    May 11, 2017 at 14:13
  • 1
    $\begingroup$ I noticed you mentioned 4KB code/data cache & memory latency issues in your target platform in comments. This is very cache friendly way of rasterizing the sphere so small LUT should remain in the cache of that size, and each entry in the LUT could be stored in 1 or 2 bytes. You also don't need 1 degree precision so the LUT can be smaller (linearly interpolate between the LUT entries), so the entire LUT could fit in just ~100 bytes or less. You can calculate the LUT easily with acos(), which maps horizontal position to the surface of the cylinder for the "rounded" texture mapping effect. $\endgroup$
    – JarkkoL
    May 11, 2017 at 14:37
  • $\begingroup$ Thanks, I'm still trying to wrap my head around the arccos, though. I get that its numerical distribution of values is nonlinear, and that's exactly what we need to cheat. I guess, when I implement it,it'll be obvious,but to get the index to the table, I can only remap it [from the horizontal position on the screen] linearly (e.g. a point that is horizontally in the middle between the left edge and circle center would have value of 0.5, arccos of which is 60 degrees, and that corresponds to texel at position of 0.66 x TextureSegmentWidth).It may not matter,as the end result is nonlinear,anyway $\endgroup$
    – RubyNoob
    May 11, 2017 at 17:30
  • 1
    $\begingroup$ You map the x-coordinate linearly to the table and fetch the u-coordinate you use to fetch from the texture. This is essentially: for(unsigned i=0; i<lut_suze; ++i) lut[i]=acos(1.0f-2.0f*float(i)/lut_size) / pi * 0.5f * tex_width; $\endgroup$
    – JarkkoL
    May 11, 2017 at 17:40
0
$\begingroup$

With the correct mapping used for the texture you can avoid a lot of complex math for the sample point. For example the Lambert cylindrical equal-area projection will let you keep the y coordinate unmodified and the x coordinate only depends on which meridian you are on.

Then you could use bresenham's ellipse algorithm to draw every visible meridian on the planet.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Not sure if I'm reading this right ? Are you proposing I switch from image-based texturing to polygonal mesh of the sphere and use perspective texturing rather ? The computational complexity (and related visual artifacts alone ) disqualify this approach altogether. Right now, until planet is close, I can stay around 60 fps. No chance with perspective texturing. That link looks like it allows to move the point of distortion up and down, so not sure how it can be used to remap the sphere points into the texture. Doesn't look like it. $\endgroup$
    – RubyNoob
    May 10, 2017 at 14:15
  • $\begingroup$ No I mean changing the source image to minimize coordinate processing $\endgroup$
    – ratchet freak
    May 10, 2017 at 14:18
  • $\begingroup$ But that would only help with the distortion around poles (which I'm not showing, deliberately). The 3-D perspective (most visible on left/right edge) is a real-time effect - it's essentially some nonlinear function (most probably it has a kind-of quadratic falloff, I'm guessing). Essentially, for each 2D point (x,y) on a known scanline y, we want to know the 3D point (x,y,z) - which I can easily linearly remap to the texture coordinates $\endgroup$
    – RubyNoob
    May 10, 2017 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.