Towards a Potentially Visible Set

Like explained in the previous post, some sort of occlusion culling is needed to decrease the number of triangles drawn. A potentially visible set (PVS) would be ideal for runtime performance but computing one is pretty tricky.

I’ve been racking my brain trying to come up with a simple brute force solution to precompute a PVS for an arbitrary triangle mesh, for a polygon soup. I haven’t been successful so far, even though I found an open source library that supposedly does that. This post tells you about difficulties related to it.

Two polygons see each other. Proved by a raycast shown in the image as a line.

But let me first explain the angle I’m taking with this project. A modern PC is a supercomputer by 1996 standards; my Nvidia GTX 1060 would’ve easily been #1 in TOP 500 list in June 1996 with its speed of 4 TFLOPS. It’s hard to convey how incredibly pathetic computers were back then.

We’ve also had 26 years to advance algorithms since then, so we should be able to do amazing things both on PC and the N64 itself. That’s what I’m after: Something that truly was impossible back then. Very accurate precomputed visibility could be a part of that but I can’t just get it to work!

Exact visibility

In 3D rendering we usually care for conservative visibility, i.e. never cull away too much so that the rendered picture becomes incorrect. For example in a view cell of a PVS, say one room in a level, there is a list all objects that can be seen from anywhere from that room. It’s conservative.

However, we could use a method that computes exact visibility to come up with that conservative object list. Like a function bool can_see(triangle1, triangle2). Unfortunately exact 3D visibility a difficult problem. Fortunately there’s an open source library for that!

It’s visilib

Denis Haumont’s visilib is

an efficient and robust library for exact visibility computation in 3D

YES! It was there all that time and I just didn’t know which words to type into Google search box. OK so now we have a method to check if two polygons in an arbitrary polygon soup can see each other. Time to sketch a plan.

A plan for a PVS

1. Export the whole static game level as an Wavefront OBJ file.
2. Split its volume into grid cells, say 1x1x1 m in size.
3. Use visilib to compute every polygon seen from each grid cell.
4. Save those per-cell lists to a file.
5. Compress the file.
6. Load the file on the N64.
7. At runtime, find the grid cell the camera is in and read a list of polygons to draw.

Mission accomplished: overdraw eliminated! At least in theory…

The reality of using someone else’s C++ code

When you see something cool online you don’t usually see all the mistakes and false starts that went into making it. To a fan it doesn’t really matter but to a peer they could’ve been fascinating. They could learn from their techniques and mistakes. That’s why I’m showing you all the steps I had to do to get started with this experiment.

So the setup. There’s a triangle mesh that acts as an occluder. Then there are two convex polygons, the source and receiver, whose visibility we are interested in. In this case the source is a side of a view cell box and the receiver is one triangle of the mesh.

The code compiled just fine on my Ubuntu. CMake works much better on Linux than on Windows :)

A dependency had disappeared. A proprietary “Leda” library was used for robust arithmetic but isn’t freely available anymore. Luckily libvisi also works with just floats.

Included sample runs but crashes on some test models. I had to increase maximum recursion depth limit of the library from 200 to 2000 to avoid this crash.

Had to fix one math function that caused a crash.

Included OBJ loader code couldn’t handle quads. Even though it accepted them so I had to patch that in.

No documentation on expected winding order of triangles. It’s counter-clockwise order. I had to create a simple test scene with different normal orientations to check this.

My winding order test scene.

If the two polygons aren’t facing other the code prints “Clipping failure” and returns an error code. This case can be considered “not visible”. I wrote a backface culling check as well: check signed distance of each vertex of both polys against others plane. If both have a vertex with a positive distance, polygons can see each other. Maybe there’s an easier way.

Triangle occludes itself. Receiver triangle has to be removed from the occluder set because otherwise it can get front of itself. Tried to do this by zeroing vertex indices of the receiver triangle so that it becomes degenerate. I’m not sure if it works.

I want to be clear: This library is awesome. It’s cutting edge-research so it’s expected to be rough around the edges. My aim here is to show the practical difficulties that always come up when working with new code. Sometimes easy things turn out to be the hardest.

Does it work?

Not yet. For some reason even some very simple cases fail and produce “not visible” result, like the one below.

The blue triangle on the left is not reported seeing the quad on the right. And I just can’t figure out why. I even moved that triangle out of the mesh surface to avoid precision issues.

I hope to have a new post ready for you soon where I reveal the dumb mistake that was causing all this. :)

Unsolicited debugging advice

I’m not that great at debugging, as demonstrated by above, but I’ll share my technique anyway. First of all, it’s important to listen to good music to keep the mood up. Then you write down the problem

PROBLEM: my polys cant see each other,

and then observations, this is important to avoid jumping to conclusions (I do it anyway):

observation: reversing tri winding causes a failure to reported
observation: tri has to be moved pretty far from surface to be visible
observation: removing the tri completely from occluder set has no effect,

so now I can generate a new thing to check:

TODO: visualize the set of occluding polygons

Even if I have no grand theory for this bug yet, at least I’ll gain more evidence. Also it’s easier to get back on track after a pause.

Thanks for coming to my rubber duck debugging talk.