fast 'ball' pixel-rasterization routine with shading

Question

I need some simple "ball" rasterization routine in C.

I cooked myself something based on midpoint-Bresenham algorithm (to see in wikipedia) where I first calculate circle points in x-y screen plane

// XXX
// XXXXX
// XXXXXX
// XXXXXXX
// XXXXXXXX
// XXXXXXXX
// XXXXXXXXX
// XXXXXXXXX
// XXXXXXXXX

then for each scanline I go with the 'second' midpoint, this time in x-z plane and update depth buffer z values.

It seems to work though it has some troubles to it. For example,

Perspective transformation as far as I know does not cast balls to circles but probably ellipses so that my algorithm of rasterizing it as circles is not quite correct.
For small circles there is a jump between one point balls that look like
```
//  #
```
then when getting closer it jumps immediately to something like
```
//  #
//#####
//#####
//  #
```
or
```
//  ##
//######
//######
//  ##
```

I'm not sure if this is consequence of midpoint algorithm or I'm making something wrong.

Other question is when I get this algorithm, then I would like a shading version of it. I need for example to know normal for each of pixels of my rasterized balls (to use it for dot with light ray). Could someone provide some formula for this normal for pixel?

Maybe there is some faster way of shading it?

In short I need some advice to improve the thing I have, especially I want shaded version of it (more important to work than be perfect but some improvements on exactness would be right too).

If you want "balls" use `glutSolidSphere(radius)` and if you have been using perspective projection then how could you expect that your ball should be sphere? — Venkatesh, Nov 15 '14 at 19:23
When you render a moving object in perfect detail, it won't look as good as when you render a "suggestion" of the object. As for ellipses, a ball is projected as a circle in 2D unless the axes have unequal scales, but an ellipse pointing in the direction of travel could help with the illusion of motion. — Weather Vane, Nov 15 '14 at 19:28
@wv dont think so that ball will be a circle, i got some raytracing code (that gives perfect projection i thing) and quite visible balls are deformed there, esp if view has some wide angle set, but this x angle and y angle of wiev are proportional to viewporrt window sizes — user2214913, Nov 15 '14 at 19:49
especially need an equation for normal for this bal (ball is defined by Radius, say has origin in 0,0) whad would look like normal for point x,y where x is from -R to R same for Y - what is normal vector for given x,y...tnx — user2214913, Nov 15 '14 at 19:51
The only time a spherical ball is elliptical is on widescreen TV sports. In graphics projection it should not matter what view angle or perspective you are using, all points on the circumference of the ball's silhouette are the same distance from the eye / camera, and the nearest point of the ball is the centre. — Weather Vane, Nov 15 '14 at 20:21
"x angle and y angle of view are proportional to viewport window sizes" but should be taking aspect ratio into account, not just a pixel scale. — Weather Vane, Nov 15 '14 at 20:23
they are same distance to the eye point but when doing projection in raytracer i think i counted not eye to ball-point distance but ball-point to screen distance when screen is sone rectangle - im not sure never 100% understood that — user2214913, Nov 15 '14 at 20:37
I mean each dx and dy in pixel on screen was the same id 3d space so ratio was proportional x/y=1 — user2214913, Nov 15 '14 at 20:38

score 1 · Accepted Answer · edited May 23 '17 at 12:27

Normal vector

on sphere the normal for any point (x,y,z)
is (x-x0,y-y0,z-z0)
where (x0,y0,z0) is the sphere center
so you need the Z coordinate too ...
should normalize it by dividing the final dot product by radius...

Rasterization

to compute Z axis you need sqrt
for small radiuses you can use lookup table for SQRT (and still be fast)
so the rasterization looks like this:
1. do 2 nested fors per x,y (center +/- radius square area)
2. ignore pixels out of range x*x+y*y>r*r
3. compute z via sphere equation
  - x*x+y*y+z*z=r*r
  - z=sqrt(r*r-x*x-y*y)
  - compute the normal_vector
4. apply perspective transform
  - (x,y,z) only leave the normal as is
5. compute shaded color and output the pixel
  - pixel_color=ball_color*(ambient_light_intensity+directional_light_intensity*dot(normal_vector,light_direction_vector));

Also look here: Drawing 3D sphere in C/C++ (voxel space surface only rendering) just use only XY plane projection

The size jump

may be your Bresenhams implementation stops 1 iteration too early or too late
the dot is visual radius 0 and the next size is visual radius 2
if you still want to stay on bresenham then check what radius you actually use and repair the for loop (add +/- 1 or change <=/>= to </> or viceversa)

fast 'ball' pixel-rasterization routine with shading

1 Answers1