# back-face (back-line) culling without winding order

In fooling around with my own 3D display engine I've been able to get a few modest features working, and I've come close with this latest one - line culling - but I fear in order to do it correctly I'll need to backpedal a little bit and start establishing more attributes in my basic wireframe objects. I'd like to avoid that if possible because I legitimately haven't needed it until now (maybe).

The basic '3d object' class is essentially just lists of lines, points, an RGB value for color, and a few self-transforming methods for basic movement and rotation.

class MyObject(object):
def __init__(self, points, lines, color):
self.points = points
self.lines = lines
self.color = color
# insert methods for rotation/translation/etc


No vertex order, no collection of 'faces' or 'sides' or anything, just points and lines and a color.

I've tried to introduce a culling method into my view object that uses all the possible triangles that each line could be an edge with, and then checks the dot product of that triangle's outward-facing normal against the imaginary line from the camera to the shared point in the triangle (v0, pt_a, etc).

def line_cull(self, shape):
"""Determine which lines should be drawn by comparing them against
the triangles they could be a part of. If the triangle faces away from the
camera, don't draw that line.
"""
to_draw = []
for line in shape.lines:
a, b = line
# get a list of the other lines that point a exists in
other_lines = [m for m in shape.lines if a in m and m is not one]
# treat point a as "vertex 0" and get the line from a to the camera
a_to_cam = minus(a, self.camera)
for line2 in other_lines:
# get the correct point c
if not a == line2[0]:
line2 = line2[::-1]
c = line2[-1]
# get the vector of ab and ac for a cross product
ab = minus(b, a)
ac = minus(c, a)
# find the middle of the triangle
mid = [x / 3.0 for x in plus(a, plus(b, c))]
# outwards is the direction vector from the shape's center
# to the middle of the triangle. for whatever reason this
# has been working better at orienting the normal than just
# using the dot product to the center of the object
outwards = minus(mid, shape.center)
norm = cross(ab, ac)
if dot(norm, outwards) < 0:
norm = cross(ac, ab)
if dot(norm, a_to_cam) < 0:
if line not in to_draw:
to_draw.append(line)


This works for certain shapes a lot better than others. Sticking to platonic solids for now - tetrahedrons and cubes are perfectly drawn, whereas octahedrons (especially rotating ones) have flickering back-end lines.

I did try to include a line about confirming the existence of line BC -- that is, the imaginary 'third line' in the triangle -- and all of a sudden, all my cubes disappeared! Because there would never be a third line in its series of right-angles, and so there was nothing to render anymore.

My question is -- do I have to establish faces/sides/etc in order for this to "just work", or is there a way to suss out which pairings should not be considered, without just excluding certain shapes from being rendered at all?

My question is -- do I have to establish faces/sides/etc in order for this to "just work", or is there a way to suss out which pairings should not be considered, without just excluding certain shapes from being rendered at all?

Yes. The problem is that its completely ambiguous what a face even is in your formulation. Right now, you're implicitly assuming all points and lines are on the border of a solid object, and that they have a consistent "outside" and "inside".

However, without information about normals or the volumetric properties of the shape, you have no means of determining the correct orientation of each face. You're left trying to guess the normal from the fact that the shapes you are drawing just happen to be convex. This is a losing battle, in my opinion.

Why not introduce the concept of triangles and winding order? There's a reason graphics libraries do this, and you just rediscovered it. It's not that difficult to implement either. Just reinterpret every three points as a triangle and assume a winding order. Then the code doesn't have to do any checks to try to compute a face normal -- the work goes into properly modeling the shapes instead.

• Well I'm not not determining normals, I'm just doing it on the fly, which is probably a good sign that I'm doing it weird. I didn't want to introduce data I didn't absolutely need into the base class of the wireframe objects but it would appear that it is unavoidable. No matter, you're not wrong of course, it's easily implemented. This is, ultimately, just a learning experience for me, and so as you've stated I've indeed "rediscovered" issues that were probably long-since tackled by smarter people than me. Thanks for the feedback. – Stick Feb 11 '15 at 16:59
• This really does make things much simpler, thanks a lot – Stick Feb 11 '15 at 21:04

I would prefer to make this as a comment, but I don't have the rep yet.

While what you have isn't the easiest or most recommended way to go about that, it theoretically could work. You probably have a bug, my guess is that the cross product is trying to cross a line with itself on your more complicated shapes and returning a normal of length 0.

Also, if your normals point the wrong direction, you don't need to recross them, you can simply just negate all the values (manually, or multiply the normal by -1.0) and you'll have a normal pointing the opposite direction. And, cross products aren't guaranteed return normalized vectors, so you'll probably want to normalize the vectors you get out of them before you use them.

• I hope that I need to normalize anything, just get the normal vectors to each plane, but if I go with the above statement about just establishing faces and winding order then I only ever need to do this one time anyway. – Stick Feb 11 '15 at 19:14