<p>Incidentally I <a href="https://youtu.be/AZTqTrCrNlw" rel="nofollow noreferrer">implemented something similar</a> for similar hardware some 20 years ago (:</p>

<p>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.</p>

<p>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.</p>

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

<p>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</p>

CC BY-SA 3.0
2017-05-11T14:10:12.003Z
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?
RubyNoob
CC BY-SA 3.0
2017-05-11T14:13:44.383Z
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...
RubyNoob
CC BY-SA 3.0
2017-05-11T14:37:16.127Z
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.
JarkkoL
CC BY-SA 3.0
2017-05-11T17:30:43.553Z
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
RubyNoob
CC BY-SA 3.0
2017-05-11T17:40:07.540Z
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;
JarkkoL
CC BY-SA 3.0
2017-05-11T21:32:38.363Z
Thanks a lot, examining the data closer reveals your equation provides data for whole width of the circle, not just for diameter, correct ? I watched your video again, but I find it hard to see any quantization artifacts there. Did you use full floats or fixed point ? I find it hard to believe that texturing would be integer-only!
RubyNoob
CC BY-SA 3.0
2017-05-12T19:23:22.237Z
Yes, it generates the LUT for full width of a scanline. Can't remember the details, but I'm pretty sure the LUT stored just integer pixel coordinates and I just point sampled it. You could do better with linear interpolation and fixed point.
JarkkoL
CC BY-SA 3.0
2017-05-10T23:20:26.937Z
2017-05-11T00:33:42.320Z
2017-05-11T00:33:42.320Z
JarkkoL
<p>With the correct mapping used for the texture you can avoid a lot of complex math for the sample point. For example the <a href="https://en.wikipedia.org/wiki/Lambert_cylindrical_equal-area_projection" rel="nofollow noreferrer">Lambert cylindrical equal-area projection</a> will let you keep the y coordinate unmodified and the x coordinate only depends on which meridian you are on.</p>

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

CC BY-SA 3.0
2017-05-10T14:15:25.677Z
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.
RubyNoob
CC BY-SA 3.0
2017-05-10T14:18:17.023Z
No I mean changing the source image to minimize coordinate processing
ratchet freak
CC BY-SA 3.0
2017-05-10T14:38:35.893Z
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
RubyNoob
CC BY-SA 3.0
2017-05-10T13:49:43.373Z
2017-05-10T13:49:43.373Z
ratchet freak
<p>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:</p>

<ul>
<li>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)

<ul>
<li>midpoint Bresenham circle algorithm to compute 8 endpoints at each iteration, effectively giving me 4 horizontal scanlines</li>
<li>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</li>
<li>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</li>
</ul></li>
</ul>

<p>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 <em>feel and look</em> like planet rotation, as the perspective/distortion/stretching at the sphere edges (left and right edge of the circle) is obviously missing.</p>

<p>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 ? </p>

<p>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.</p>

CC BY-SA 3.0
2017-05-10T20:10:03.743Z
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.
Olivier
CC BY-SA 3.0
2017-05-10T20:48:52.767Z
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.
RubyNoob
CC BY-SA 3.0
2017-05-10T21:08:05.090Z
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.
Olivier
CC BY-SA 3.0
2017-05-10T21:49:14.470Z
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.
RubyNoob
<texture><uv-mapping>
Fast approximation of spherical texture coordinates
RubyNoob
# Fast approximation of spherical texture coordinates

(Asked by: username_0 on 2017-05-10)

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.

**Tags:** texture, uv-mapping

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: 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.  

---

## 2 answers

### Answer by username_2 on 2017-05-10. Score: 3 | Accepted answer

Incidentally I [implemented something similar](https://youtu.be/AZTqTrCrNlw) 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

> **Comments:**
> **username_0**: 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?  
> **username_0**: 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...  
> **username_2**: 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.  
> **username_0**: 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  
> **username_2**: 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;  
> **username_0**: Thanks a lot, examining the data closer reveals your equation provides data for whole width of the circle, not just for diameter, correct ? I watched your video again, but I find it hard to see any quantization artifacts there. Did you use full floats or fixed point ? I find it hard to believe that texturing would be integer-only!  
> **username_2**: Yes, it generates the LUT for full width of a scanline. Can't remember the details, but I'm pretty sure the LUT stored just integer pixel coordinates and I just point sampled it. You could do better with linear interpolation and fixed point.  

---

### Answer by username_3 on 2017-05-10. Score: 0

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](https://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: 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.  
> **username_3**: No I mean changing the source image to minimize coordinate processing  
> **username_0**: 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  

---

