Comments on Plain spheres
Post
Plain spheres
Given a list of spheres, output an image.
Produce a greyscale orthographic (parallel projection - no perspective) ray caster, that renders only plain grey spheres with no lighting.
Input
- A list of spheres, each consisting of:
- The coordinates of its centre $(x,y,z)$.
- Its radius $r$.
- Its greyscale value $g$, an integer from $0$ to $255$ (both inclusive).
- Only the greyscale value will be restricted to integer values. The coordinates and radius may have fractional values.
Output
- An image $1024$ by $1024$ pixels with greyscale values from $0$ to $255$.
- The image covers x and y values from $-1$ to $1$.
- A sphere's greyscale value is applied to every visible part of it. There is no variation over the surface of the sphere, so it appears flat like a disk.
- You may output whatever image format is convenient, including simple text formats such as PGM or a list of pixel greyscale values. If you want to include an example of your output as an image in your answer, the image formats that Codidact supports are PNG, JPEG, and GIF. You could output PGM and then convert to PNG to upload to your answer. If you output just the greyscale values as a list of numbers from $0$ to $255$, I've made a
[ TODO page to convert these to greyscale PNG]
. - You are free to output an image reflected or rotated by a multiple of 90 degrees. However, the z axis is required to be increasing in the forwards direction (into the image) otherwise some of the test cases will look incorrect.
- You may assume that all ray intersection points (not just nearest intersections) will have a $z$ value greater than zero, and less than $1024$.
TODO: Adjust test cases to fit within this specified z range
Calculating a pixel value
Imagine a ray passing into the image through a pixel, perpendicular to the image plane. If it hits a sphere, it shows the greyscale value of the first sphere it hits. Otherwise, it shows a value of zero (black).
For example, for each pixel:
- The pixel $x,y$ coordinates will each be from $0$ to $1023$. Scale these to the range $-1$ to $1$ (for example, divide by $512$ and subtract $1$).
- If these scaled $x,y$ coordinates are within the radius $r$ of the $x,y$ coordinates of a sphere's centre, the ray intersects that sphere (the $z$ coordinate is not relevant to this test because the image is an orthographic projection - the rays are all parallel to the $z$ axis). The distance $a$ of the ray from the sphere's centre can be calculated as follows:
CONSIDER A DIAGRAM HERE
- For each sphere that the ray intersects, find the $z$ coordinate of the nearest intersection (there will often be $2$ per sphere, $1$ on the front of the sphere and $1$ on the back of the sphere, as the ray passes through - only the nearest is relevant). This can be calculated as follows:
- The distance $d$ to the nearest intersection point can be calculated from the $z$ coordinate of the sphere's centre, the radius $r$, and the distance $a$ from the $x,y$ coordinates of the sphere's centre to the scaled $x,y$ coordinates of the pixel:
CONSIDER A DIAGRAM HERE
- Of all the spheres that the ray intersects, the sphere with the intersection point with the smallest $z$ coordinate $d$ is the one to display. Set the pixel to the greyscale value of this sphere.
- If $2$ or more spheres have an intersection point with the smallest $z$ coordinate $d$ then you may set the pixel to the greyscale value of any of these spheres.
TODO: generate output images for each test case
both ways to confirm that this makes less than
a pixel's width difference.
- If the ray did not intersect any spheres, set the pixel to zero (black).
Example implementations
These are ungolfed code to supplement understanding of the requirements. You are free to golf these or implement your own approach that matches the test cases up to reflection & rotation.
The Python implementation uses 64 bit floating point. The Rust implementation uses 32 bit floating point to show the difference in output. I've tried to optimise the test cases for compatibility with 32 bit floating point, so the differences are restricted to being a pixel out in some places.
Python
The function grey_values
would be sufficient as an entry to this challenge. The rest of the code saves the output as a PNG file. The function itself has no dependence on the import png
so it would not be required in an entry.
Instructions for installing the png
package can be found on its project page on PyPI.
def grey_values(spheres):
values = []
for y_pixel in range(1024):
for x_pixel in range(1024):
x_ray, y_ray = x_pixel / 512 - 1, y_pixel / 512 - 1
min_distance, hit_grey_value = None, 0
for sphere in spheres:
x_sphere, y_sphere, z_sphere, radius, grey = sphere
a = (
(x_ray - x_sphere) ** 2 + (y_ray - y_sphere) ** 2
) ** 0.5
if a < radius:
distance = z_sphere - (radius ** 2 - a ** 2) ** 0.5
if min_distance is None or distance < min_distance:
min_distance = distance
hit_grey_value = grey
values.append(hit_grey_value)
return values
import png
test_case = [
[0, 0, 1000, 2, 192],
[-2, 2, 100, 3, 98],
[2, 2, 100, 3, 98],
[0.5, -0.5, 500, 0.2, 255],
[-0.349469, -0.1, 20.000279, 0.6, 64],
[-0.349775, -0.100273, 20.000485, 0.6, 85],
[-0.350214, -0.100386, 20.000407, 0.6, 106],
[-0.350527, -0.100273, 20.000091, 0.6, 127],
[-0.350531, -0.1, 19.999721, 0.6, 148],
[-0.350225, -0.099727, 19.999515, 0.6, 169],
[-0.349786, -0.099614, 19.999593, 0.6, 190],
[-0.349473, -0.099727, 19.999909, 0.6, 211],
[0.20032, 0.349824, 15.000456, 0.3, 0],
[0.20032, 0.349517, 14.999924, 0.3, 0],
[0.19968, 0.350483, 15.000076, 0.3, 0],
[0.19968, 0.350176, 14.999544, 0.3, 0],
[0.200578, 0.350073, 14.999958, 0.3, 0],
[0.199817, 0.349519, 15.000277, 0.3, 0],
[0.200183, 0.350481, 14.999723, 0.3, 0],
[0.199422, 0.349927, 15.000042, 0.3, 0],
[0.200235, 0.35042, 15.000332, 0.3, 0],
[0.199765, 0.350078, 15.000529, 0.3, 0],
[0.200235, 0.349922, 14.999471, 0.3, 0],
[0.199765, 0.34958, 14.999668, 0.3, 0],
[0.200429, 0.350419, 15.000005, 0.3, 255],
[0.199571, 0.349795, 15.000366, 0.3, 255],
[0.200429, 0.350205, 14.999634, 0.3, 255],
[0.199571, 0.349581, 14.999995, 0.3, 255],
[0.200524, 0.349747, 15.000146, 0.3, 255],
[0.200196, 0.349509, 15.000283, 0.3, 255],
[0.199804, 0.350491, 14.999717, 0.3, 255],
[0.199476, 0.350253, 14.999854, 0.3, 255],
[0.200138, 0.349578, 14.999597, 0.3, 255],
[0.200138, 0.350138, 15.000567, 0.3, 255],
[0.199862, 0.349862, 14.999433, 0.3, 255],
[0.199862, 0.350422, 15.000403, 0.3, 255],
[0.200488, 0.350136, 15.000321, 0.3, 255],
[0.199957, 0.349751, 15.000544, 0.3, 255],
[0.200488, 0.34979, 14.999721, 0.3, 255],
[0.199957, 0.349404, 14.999944, 0.3, 255],
[0.200043, 0.350596, 15.000056, 0.3, 255],
[0.199512, 0.35021, 15.000279, 0.3, 255],
[0.200043, 0.350249, 14.999456, 0.3, 255],
[0.199512, 0.349864, 14.999679, 0.3, 255],
[-0.5, 0.500442, 10.000442, 0.2, 0],
[-0.5, 0.5, 10, 0.1995, 255],
[-0.499966, 0.49971, 9.999563, 0.199, 0],
[-0.500034, 0.499563, 9.99971, 0.199, 0],
[-0.499934, 0.499432, 9.999144, 0.1985, 255],
[-0.500066, 0.499144, 9.999432, 0.1985, 255],
[0.6, 0.5, 10, 0.25, 210],
[0.600122, 0.4999, 10.000122, 0.25, 210],
[0.600061, 0.49995, 10.000061, 0.25003, 50],
[0.595856, 0.505256, 9.991271, 0.24, 100],
[0.597973, 0.507461, 9.992175, 0.24, 210],
[0.595362, 0.507926, 9.993945, 0.24, 100],
[0.594618, 0.509055, 9.996832, 0.24, 210],
[0.592382, 0.506906, 9.996092, 0.24, 100],
[0.590438, 0.504882, 9.997604, 0.24, 210],
[0.591035, 0.503605, 9.994744, 0.24, 100],
[0.59121, 0.500708, 9.993425, 0.24, 210],
[0.593181, 0.502585, 9.991764, 0.24, 100],
[0.595867, 0.502302, 9.990069, 0.24, 210],
]
values = grey_values(test_case)
rows = [values[row * 1024:row * 1024 + 1024] for row in range(1024)]
with open('combination_scene.png', 'wb') as file:
w = png.Writer(1024, 1024, greyscale=True)
w.write(file, rows)
Rust
The function grey_values
would be sufficient as an entry to this challenge. The rest of the code saves the output as a PNG file.
The png
crate can be installed using cargo add png
. The png
crate is not required for the grey_values
function, only for saving as a PNG file.
fn grey_values(spheres: &Vec<[f32; 5]>) -> Vec<u8> {
let mut values = vec![];
for y_pixel in 0..1024 {
for x_pixel in 0..1024 {
let x_ray = x_pixel as f32 / 512.0 - 1.0;
let y_ray = y_pixel as f32 / 512.0 - 1.0;
let mut min_distance = f32::INFINITY;
let mut hit_grey_value = 0;
for sphere in spheres {
let [
x_sphere, y_sphere, z_sphere, radius, grey
] = *sphere;
let a = (
(x_ray - x_sphere).powf(2.0)
+ (y_ray - y_sphere).powf(2.0)
).sqrt();
if a < radius {
let distance = z_sphere - (
radius.powf(2.0) - a.powf(2.0)
).sqrt();
if distance < min_distance {
min_distance = distance;
hit_grey_value = grey as u8;
}
}
}
values.push(hit_grey_value);
}
}
values
}
fn main() {
let test_case: Vec<[f32; 5]> = vec![
[0.0, 0.0, 1000.0, 2.0, 192.0],
[-2.0, 2.0, 100.0, 3.0, 98.0],
[2.0, 2.0, 100.0, 3.0, 98.0],
[0.5, -0.5, 500.0, 0.2, 255.0],
[-0.349469, -0.1, 20.000279, 0.6, 64.0],
[-0.349775, -0.100273, 20.000485, 0.6, 85.0],
[-0.350214, -0.100386, 20.000407, 0.6, 106.0],
[-0.350527, -0.100273, 20.000091, 0.6, 127.0],
[-0.350531, -0.1, 19.999721, 0.6, 148.0],
[-0.350225, -0.099727, 19.999515, 0.6, 169.0],
[-0.349786, -0.099614, 19.999593, 0.6, 190.0],
[-0.349473, -0.099727, 19.999909, 0.6, 211.0],
[0.20032, 0.349824, 15.000456, 0.3, 0.0],
[0.20032, 0.349517, 14.999924, 0.3, 0.0],
[0.19968, 0.350483, 15.000076, 0.3, 0.0],
[0.19968, 0.350176, 14.999544, 0.3, 0.0],
[0.200578, 0.350073, 14.999958, 0.3, 0.0],
[0.199817, 0.349519, 15.000277, 0.3, 0.0],
[0.200183, 0.350481, 14.999723, 0.3, 0.0],
[0.199422, 0.349927, 15.000042, 0.3, 0.0],
[0.200235, 0.35042, 15.000332, 0.3, 0.0],
[0.199765, 0.350078, 15.000529, 0.3, 0.0],
[0.200235, 0.349922, 14.999471, 0.3, 0.0],
[0.199765, 0.34958, 14.999668, 0.3, 0.0],
[0.200429, 0.350419, 15.000005, 0.3, 255.0],
[0.199571, 0.349795, 15.000366, 0.3, 255.0],
[0.200429, 0.350205, 14.999634, 0.3, 255.0],
[0.199571, 0.349581, 14.999995, 0.3, 255.0],
[0.200524, 0.349747, 15.000146, 0.3, 255.0],
[0.200196, 0.349509, 15.000283, 0.3, 255.0],
[0.199804, 0.350491, 14.999717, 0.3, 255.0],
[0.199476, 0.350253, 14.999854, 0.3, 255.0],
[0.200138, 0.349578, 14.999597, 0.3, 255.0],
[0.200138, 0.350138, 15.000567, 0.3, 255.0],
[0.199862, 0.349862, 14.999433, 0.3, 255.0],
[0.199862, 0.350422, 15.000403, 0.3, 255.0],
[0.200488, 0.350136, 15.000321, 0.3, 255.0],
[0.199957, 0.349751, 15.000544, 0.3, 255.0],
[0.200488, 0.34979, 14.999721, 0.3, 255.0],
[0.199957, 0.349404, 14.999944, 0.3, 255.0],
[0.200043, 0.350596, 15.000056, 0.3, 255.0],
[0.199512, 0.35021, 15.000279, 0.3, 255.0],
[0.200043, 0.350249, 14.999456, 0.3, 255.0],
[0.199512, 0.349864, 14.999679, 0.3, 255.0],
[-0.5, 0.500442, 10.000442, 0.2, 0.0],
[-0.5, 0.5, 10.0, 0.1995, 255.0],
[-0.499966, 0.49971, 9.999563, 0.199, 0.0],
[-0.500034, 0.499563, 9.99971, 0.199, 0.0],
[-0.499934, 0.499432, 9.999144, 0.1985, 255.0],
[-0.500066, 0.499144, 9.999432, 0.1985, 255.0],
[0.6, 0.5, 10.0, 0.25, 210.0],
[0.600122, 0.4999, 10.000122, 0.25, 210.0],
[0.600061, 0.49995, 10.000061, 0.25003, 50.0],
[0.595856, 0.505256, 9.991271, 0.24, 100.0],
[0.597973, 0.507461, 9.992175, 0.24, 210.0],
[0.595362, 0.507926, 9.993945, 0.24, 100.0],
[0.594618, 0.509055, 9.996832, 0.24, 210.0],
[0.592382, 0.506906, 9.996092, 0.24, 100.0],
[0.590438, 0.504882, 9.997604, 0.24, 210.0],
[0.591035, 0.503605, 9.994744, 0.24, 100.0],
[0.59121, 0.500708, 9.993425, 0.24, 210.0],
[0.593181, 0.502585, 9.991764, 0.24, 100.0],
[0.595867, 0.502302, 9.990069, 0.24, 210.0],
];
let values = grey_values(&test_case);
let path = std::path::Path::new("combination_scene.png");
let file = std::fs::File::create(path).unwrap();
let w = &mut std::io::BufWriter::new(file);
let mut encoder = png::Encoder::new(w, 1024, 1024);
encoder.set_color(png::ColorType::Grayscale);
encoder.set_depth(png::BitDepth::Eight);
let mut writer = encoder.write_header().unwrap();
writer.write_image_data(&values).unwrap();
}
Test cases
The output images may be scaled down to fit this page. Click on any image to open it full size.
Single sphere
Input:
[
[0, 0, 0, 1, 128],
]
Two separated spheres
Input:
[
[0, -0.55, 0, 0.4, 100],
[0, 0.55, 0, 0.4, 200],
]
Ring of spheres
Input:
[
[0.75, 0, 0, 0.25, 64],
[0.53033, 0.375, -0.375, 0.25, 185],
[0, 0.53033, -0.53033, 0.25, 64],
[-0.53033, 0.375, -0.375, 0.25, 185],
[-0.75, 0, 0, 0.25, 64],
[-0.53033, -0.375, 0.375, 0.25, 185],
[0, -0.53033, 0.53033, 0.25, 64],
[0.53033, -0.375, 0.375, 0.25, 185],
]
Beach ball
Input:
[
[0.001, 0, 0, 1, 64],
[0.000707, 0.000707, 0, 1, 85],
[0, 0.001, 0, 1, 106],
[-0.000707, 0.000707, 0, 1, 127],
[-0.001, 0, 0, 1, 148],
[-0.000707, -0.000707, 0, 1, 169],
[0, -0.001, 0, 1, 190],
[0.000707, -0.000707, 0, 1, 211],
]
Football
Input:
[
[0, 0.000058, 0.001947, 1, 0],
[0, -0.001715, 0.000923, 1, 0],
[0, 0.001715, -0.000923, 1, 0],
[0, -0.000058, -0.001947, 1, 0],
[0.001657, -0.000512, 0.000887, 1, 0],
[-0.001657, -0.000512, 0.000887, 1, 0],
[0.001657, 0.000512, -0.000887, 1, 0],
[-0.001657, 0.000512, -0.000887, 1, 0],
[0.001024, 0.001435, 0.000829, 1, 0],
[-0.001024, 0.001435, 0.000829, 1, 0],
[0.001024, -0.001435, -0.000829, 1, 0],
[-0.001024, -0.001435, -0.000829, 1, 0],
[0.001868, 0.000618, 0.000357, 1, 255],
[-0.001868, 0.000618, 0.000357, 1, 255],
[0.001868, -0.000618, -0.000357, 1, 255],
[-0.001868, -0.000618, -0.000357, 1, 255],
[0.000714, -0.000934, 0.001618, 1, 255],
[-0.000714, -0.000934, 0.001618, 1, 255],
[0.000714, 0.000934, -0.001618, 1, 255],
[-0.000714, 0.000934, -0.001618, 1, 255],
[0, -0.001975, -0.000316, 1, 255],
[0, 0.001261, 0.001552, 1, 255],
[0, -0.001261, -0.001552, 1, 255],
[0, 0.001975, 0.000316, 1, 255],
[0.001155, 0.000423, 0.001577, 1, 255],
[-0.001155, 0.000423, 0.001577, 1, 255],
[0.001155, -0.001577, 0.000423, 1, 255],
[-0.001155, -0.001577, 0.000423, 1, 255],
[0.001155, 0.001577, -0.000423, 1, 255],
[-0.001155, 0.001577, -0.000423, 1, 255],
[0.001155, -0.000423, -0.001577, 1, 255],
[-0.001155, -0.000423, -0.001577, 1, 255],
]
Eight ball
Input:
[
[0, 0, 1000, 2, 128],
[0, 0, 0.003125, 1, 0],
[0, 0, 0, 0.9975, 255],
[0, 0.000547, -0.002573, 0.995, 0],
[0, -0.000547, -0.002573, 0.995, 0],
[0, 0.001071, -0.005037, 0.9925, 255],
[0, -0.001071, -0.005037, 0.9925, 255],
]
Star ball
Input:
[
[0, 0, 0, 1, 210],
[0, 0, 0.0008, 1, 210],
[0, 0, 0.0004, 1.00012, 50],
[0.012969, 0, -0.042045, 0.96, 100],
[0.016397, 0.011913, -0.039054, 0.96, 210],
[0.004008, 0.012334, -0.042045, 0.96, 100],
[-0.006263, 0.019276, -0.039054, 0.96, 210],
[-0.010492, 0.007623, -0.042045, 0.96, 100],
[-0.020268, 0, -0.039054, 0.96, 210],
[-0.010492, -0.007623, -0.042045, 0.96, 100],
[-0.006263, -0.019276, -0.039054, 0.96, 210],
[0.004008, -0.012334, -0.042045, 0.96, 100],
[0.016397, -0.011913, -0.039054, 0.96, 210],
]
Combination scene
Input:
[
[0, 0, 1000, 2, 192],
[-2, 2, 100, 3, 98],
[2, 2, 100, 3, 98],
[0.5, -0.5, 500, 0.2, 255],
[-0.349469, -0.1, 20.000279, 0.6, 64],
[-0.349775, -0.100273, 20.000485, 0.6, 85],
[-0.350214, -0.100386, 20.000407, 0.6, 106],
[-0.350527, -0.100273, 20.000091, 0.6, 127],
[-0.350531, -0.1, 19.999721, 0.6, 148],
[-0.350225, -0.099727, 19.999515, 0.6, 169],
[-0.349786, -0.099614, 19.999593, 0.6, 190],
[-0.349473, -0.099727, 19.999909, 0.6, 211],
[0.20032, 0.349824, 15.000456, 0.3, 0],
[0.20032, 0.349517, 14.999924, 0.3, 0],
[0.19968, 0.350483, 15.000076, 0.3, 0],
[0.19968, 0.350176, 14.999544, 0.3, 0],
[0.200578, 0.350073, 14.999958, 0.3, 0],
[0.199817, 0.349519, 15.000277, 0.3, 0],
[0.200183, 0.350481, 14.999723, 0.3, 0],
[0.199422, 0.349927, 15.000042, 0.3, 0],
[0.200235, 0.35042, 15.000332, 0.3, 0],
[0.199765, 0.350078, 15.000529, 0.3, 0],
[0.200235, 0.349922, 14.999471, 0.3, 0],
[0.199765, 0.34958, 14.999668, 0.3, 0],
[0.200429, 0.350419, 15.000005, 0.3, 255],
[0.199571, 0.349795, 15.000366, 0.3, 255],
[0.200429, 0.350205, 14.999634, 0.3, 255],
[0.199571, 0.349581, 14.999995, 0.3, 255],
[0.200524, 0.349747, 15.000146, 0.3, 255],
[0.200196, 0.349509, 15.000283, 0.3, 255],
[0.199804, 0.350491, 14.999717, 0.3, 255],
[0.199476, 0.350253, 14.999854, 0.3, 255],
[0.200138, 0.349578, 14.999597, 0.3, 255],
[0.200138, 0.350138, 15.000567, 0.3, 255],
[0.199862, 0.349862, 14.999433, 0.3, 255],
[0.199862, 0.350422, 15.000403, 0.3, 255],
[0.200488, 0.350136, 15.000321, 0.3, 255],
[0.199957, 0.349751, 15.000544, 0.3, 255],
[0.200488, 0.34979, 14.999721, 0.3, 255],
[0.199957, 0.349404, 14.999944, 0.3, 255],
[0.200043, 0.350596, 15.000056, 0.3, 255],
[0.199512, 0.35021, 15.000279, 0.3, 255],
[0.200043, 0.350249, 14.999456, 0.3, 255],
[0.199512, 0.349864, 14.999679, 0.3, 255],
[-0.5, 0.500442, 10.000442, 0.2, 0],
[-0.5, 0.5, 10, 0.1995, 255],
[-0.499966, 0.49971, 9.999563, 0.199, 0],
[-0.500034, 0.499563, 9.99971, 0.199, 0],
[-0.499934, 0.499432, 9.999144, 0.1985, 255],
[-0.500066, 0.499144, 9.999432, 0.1985, 255],
[0.6, 0.5, 10, 0.25, 210],
[0.600122, 0.4999, 10.000122, 0.25, 210],
[0.600061, 0.49995, 10.000061, 0.25003, 50],
[0.595856, 0.505256, 9.991271, 0.24, 100],
[0.597973, 0.507461, 9.992175, 0.24, 210],
[0.595362, 0.507926, 9.993945, 0.24, 100],
[0.594618, 0.509055, 9.996832, 0.24, 210],
[0.592382, 0.506906, 9.996092, 0.24, 100],
[0.590438, 0.504882, 9.997604, 0.24, 210],
[0.591035, 0.503605, 9.994744, 0.24, 100],
[0.59121, 0.500708, 9.993425, 0.24, 210],
[0.593181, 0.502585, 9.991764, 0.24, 100],
[0.595867, 0.502302, 9.990069, 0.24, 210],
]
Accuracy
The outputs for the test cases were generated using 64 bit floating point numbers. The following is the last test case using 32 bit floating point rather than 64 bit floating point:
The inaccuracies in the 32 bit floating point version are subtle. You may need to click on the image to open it full size to see the occasional inaccurate pixel. For example, around the inside of the holes in the 8 on the eightball. These occasional inaccurate pixels are acceptable in your output (allowing languages which only support 32 bit floating point to compete).
More widespread speckling as in the following image would not be valid, so you may need to be careful if changing the order of calculations during golfing:
This exaggerated inaccuracy was achieved by adding 1000 to and then subtracting 1000 from the distance calculation, exceeding the available precision of 32 bit floating point and causing some distances to appear in the wrong order. Note that this same approach causes no inaccuracy with 64 bit floating point, so if your language supports both you may have more leeway for rearranging calculations if you use 64 bit floating point.
Explanatory animations
The example images were produced from plain grey spheres with no surface pattern or texture. The following animations show how they break down into their component plain spheres.
Animations
TODO
Scoring
This is a code golf challenge. Your score is the number of bytes in your code. Lowest score for each language wins.
Explanations are optional, but I'm more likely to upvote answers that have one.
5 comment threads