I am still working on my "javascript 3d engine" (link inside stackoverflow). at First, all my polygons were faces of cubes, so sorting them by average Z was working fine. but now I've "evolved" and I want to draw my polygons (which may contain more than 4 vertices) in the right order, namely, those who are close to the camera will be drawn last.

basically, I know how to rotate them and "perspective"-ize them into 2D, but don't know how to draw them in the right order.

just to clarify:

//my 3d shape = array of polygons
//polygon = array of vertices
//vertex = point with x,y,z
//rotation is around (0,0,0) and my view point is (0,0,something) I guess.

can anyone help?

p.s: some "catch phrases" I came up with, looking for the solution: z-buffering, ray casting (?!), plane equations, view vector, and so on - guess I need a simple to understand answer so that's why I asked this one. thanks.

p.s2: i don't mind too much about overlapping or intersecting polygons... so maybe the painter's algorthm indeed might be good. but: what is it exactly? how do I decide the distance of a polygon?? a polygon has many points.

I am still working on my "javascript 3d engine" (link inside stackoverflow). at First, all my polygons were faces of cubes, so sorting them by average Z was working fine. but now I've "evolved" and I want to draw my polygons (which may contain more than 4 vertices) in the right order, namely, those who are close to the camera will be drawn last.

basically, I know how to rotate them and "perspective"-ize them into 2D, but don't know how to draw them in the right order.

just to clarify:

//my 3d shape = array of polygons
//polygon = array of vertices
//vertex = point with x,y,z
//rotation is around (0,0,0) and my view point is (0,0,something) I guess.

can anyone help?

p.s: some "catch phrases" I came up with, looking for the solution: z-buffering, ray casting (?!), plane equations, view vector, and so on - guess I need a simple to understand answer so that's why I asked this one. thanks.

p.s2: i don't mind too much about overlapping or intersecting polygons... so maybe the painter's algorthm indeed might be good. but: what is it exactly? how do I decide the distance of a polygon?? a polygon has many points.

• javascript
• 3d
• polygons

• Interestingly, I think you'll get better performance drawing the polygons nearest to the screen first IF all the polygons are opaque. This is due to the remaining (hidden) polygons failing the depth test and not being rendered. If they are transparent your suggested order is required. – Jackson Pope Commented Jan 18, 2011 at 15:19
• en.wikipedia/wiki/Painter%27s_algorithm – asawyer Commented Jan 18, 2011 at 15:24

3 Answers 3

The approach of sorting polygons and then drawing them bottom-to-top is called the "Painter's algorithm". Unfortunately the sorting step is in general an unsolvable problem, because it's possible for 3 polygons to overlap each other:

Thus there is not necessarily any polygon that is "on top". Alternate approaches such as using a Z buffer or BSP tree (which involves splitting polygons) don't suffer from this problem.

how do I decide the distance of a polygon?? a polygon has many points.

Painter's algorithm is the simplest to implement, but it works only in very simple cases because it assumes that there is only a single "distance" or z-value for each polygon (which you could approximate to be the average of z-values of all points in the polygon). Of course, this will produce wrong results if two polygons intersect each other.

In reality, there isn't a single distance value for a polygon -- each point on the surface of a polygon can be at a different distance from the viewer, so each point has its own "distance" or depth.

You already mentioned Z-buffering, and that is one way of doing this. I don't think you can implement this efficiently on a HTML canvas, but here's the general idea:

1. You need to maintain an additional canvas, the "z-buffer", where each pixel's colour represents the z-depth of the corresponding pixel on the main canvas.

2. To draw a polygon, you go through each point on its surface and draw only those points which are closer to the viewer than any previous objects, as indicated by the z-buffer.

I think you will have some ideas by investigating BSP tree ( binary spaces partition tree ), even if the algo will require to split some of your polygon in two. Some example could be find here http://www.devmaster/articles/bsp-trees/ or by google for BSP tree. Posting some code as a reply is, in my opinion, not serious since is a plex topic.