Is there a DDA-style algorithm for rasterizing a 2D circle on 3D plane?

418 views Asked by At

I'm basically curious about a corollary of Bresenham's circle drawing but in 3D perspective where the end result is a flat circle on the Y (vertical) plane. Is there a magic DDA-type algorithm out there for this sort of thing?

NOTE that by DDA I mean using mostly integers and avoiding as many multiplications and divides as possible since the main bottleneck is the perspective Z divide.

What I've come up with so far is to loop through 360 degrees by some increment and draw a line between the projected coordinate and the next one based on the increment. The image below is a test using a 23 degree increment (I'd use 22.5 but this works from an integer lookup with only whole degree accuracy):

circle drawn using lines with a 23 degree increment

Pseudo code for this would be something like:

for (degree = 0; degree < 360; degree += degree_inc) {
    z1 = z + radius * cos(degree)
    x1 = x + radius * sin(degree)
    y1 = y

    next_degree = degree + degree_inc
    if (next_degree >= 360) {
        next_degree = 0;
    }
    z2 = z + radius * cos(next_degree)
    x2 = x + radius * sin(next_degree)
    y2 = y

    line(project_x(x1,z1), project_y(y1,z1),
         project_x(x2,z2), project_y(y2,z2))
}

Obviously there are a lot of little optimizations to the real code (lookup tables and pre-calculated amounts) but this is the essence of it.

Cheers!

0

There are 0 answers