My attempt would look something like this:


Code:



if we're concerned about coverage, we can change it thusly:

Code:

But I don't have a good enough intuition for barycentric coordinates to know which of those we prefer without drawing it out better.

It seemed to me (intuitively) that if we iterate over each edge paired with each other edge, drawing perpendicular rays from each edge, then finding the intersection of the two rays, we would cover every point in the triangle (voxel-wise) at least once. Of course, many of those points would lie outside the triangle, but the barycentric coordinates can easily tell us that.

Edit: I'm inclined to try using the first set of code and seeing what coverage looks like for the fine details of moderately complex models.

This should do the same thing without explicitly having to cast the rays.

Let me know what coverage looks like on a decent model

I'm implementing the code. self.geom_makecart() is simply return tri[0]*bary[0]+tri[1]*bary[1]+tri[2]*bary[2], while for def castraythroughvoxels(self,origin,direction,radius=1) I'm using the 1987 paper referenced here. The code dies for a certain triangle with ./kmz2mc.py:79: RuntimeWarning: invalid value encountered in divide: snorm = snorm/np.linalg.norm(snorm); at that point, snorm is [ 0. -0. 0.]. That means that e[1] and e[0] are parallel or antiparallel, right?

Yes. We should probably do something before that like

Code:

My solution was as follows, but I guess it's the same thing. Anyway, this works unbelievably well based on the in-world models (and I'm not even using the voxel-casting properly yet!

Code:
I'm going to try to implement coloring and texturing before I implement the proper percentage-based voxel filling. Here's a demo screenshot of a view I showed from my previous engine:

Edit: Pushed changes to repo.

I see a distinct lack of holes in that model Want to run it on the skyscraper model as well?

Same complete success! I remain sad that the spire on the top of this building refuses to generate under any algorithm, though.

Is it complaining about the spire, or failing silently? What does the geometry look like if you load it Sketchup?

I can pull it off; it's almost as if it's a separate model. Let me dig into the model format and see if that's a thing it can do.

oh, it's probably a separate mesh! I'm quite certain Collada supports that

Yeah, I'm already grabbing information from the 17 different geometries in this particular model (which I just verified by dumping out the geometry information while I converted it), but I must be missing something. I'll edit this post when I figure it out.

Edit: I think the thing that ends up in the basement of the building is the spire; it must have some offset information that I'm missing. Plan of action:

1) Return a list of voxels from the castray...() method
2) Texture everything. Then I can tell what exactly is going on.
3) Based on this, figure out where the spire (and other odd meshes) are going
4) Figure out how to do the volume-based voxel selection.
5) See if it's necessary to re-index points as per PyCollada documentation.
5) Handle poly and line primitives. Way to segment polys into tris?

Does your model have named objects by any chance? That can make debugging a lot easier!


You need to ask the mesh how the triangles are stored. tri-strips and tri-fans are both reasonably common in some places, and probably would need to be reindexed. or you'll get garbage. It's also good to check if the mesh declares a winding order (CW or CCW) and negate our face normals if it's CW.


Quads -> tris are super easy (link 0->1->2 and 2->3->0). Everything else, it's probably easy to convert to a tri-fan first and then reindex.

It looks like instead of just throwing all of the geometries down, I need to recurse down and down through model.scenes, which contains transforms and geometry references.

Edit: Here's the New York Life Building once more, fully-textured and with no holes. I even taught it to understand transparencies in textures, which seems to be working well (and I might make it use the glass block for translucent areas, although I suspect that not many 3D Warehouse models have proper windows. I wanted to use the textures to find the levels of floors, add glass windows, and fill in the floors, but I might have to leave that to you, elfprince13. I'd love any inspiration you can offer on how that might be feasible based on your current Fourier/Eigen exploration.

The first item on my agenda with this tomorrow will be to fix the iteration through the geometry, applying transforms as necessary. The second item will be thinning the surfaces created as necessary.



Edit: I implemented all the fun recursion and everything, and it seems to mostly work. However, when I actually go ahead convert the model, the spire's transformation matrix is very, very not applied properly:

Have you double checked that the matrices are being stored correctly? OpenGL prefers column-major indexing, but most programmers prefer row-major indexing. If the model format is storing it in column-major order to save processing time, and you're loading it in row-major order, bad things will happen.

In general, languages/frameworks designed for matrix math prefer column-major order because columns are vectors, and programmers who don't do linear algebra on a regular basis prefer row-major order because it's how we type it.

[edit]
If you check that, and it's definitely not the problem, also make sure you're multiplying in the correct order as you proceed downwards. Matrix multiplication is not, in general, commutative, and applying transformations in reversed order is another common mistake.

That's an excellent point. However, I dumped out a few of the transformation matrices, and they looked like this:
Code:
The [0,0,0,1] in the bottom row makes me think this is indeed a proper row-major matrix; it helps that PyCollada takes care of all of the XML -> numpy array conversion.

Edit: It occurs to me that transformation matrices in meters are not transformation matrices in model units (usually inches, sometimes centimeters).

Sadly, that could just as easily be from the opposite convention. In homogeneous coordinates, it's just as valid to have the last column be [[0],[0],[0],[1]] and put the translational coordinates in the bottom row, but such a transposition would muck about with your rotations.

If PyCollada -> numpy stuff is tested library code and not your code, the multiplication order seems like the more likely suspect.

But try both

By the way, here's one instance of where the matrix multiplication issues I was asking about in SAX come in handy. The triangle vertices are stored in an x-row, 3-column matrix, and the transformation matrix is 4x4. I was transposing the vertices, multiplying transform * vertices (in that order), then re-transposing the vertices, like so:

Code:
There's actually two sets of transformations: once for vertices as a set to find model extents, and again when I actually convert triangles. The model extents transformations seem to come out ok, the triangle conversion does not. I'll look again at that code:
Code:

The big question is how are you producing your transform? It's the downward recursion, where, I'm assuming, each sub-transformation needs to be composed with it's predecessors, that I was concerned about.

It certainly does, and here's how I do that:
Code:
See any issues? I can also check in this code. The fact that it's computing proper model extents makes me think only the transform right before geom_tri2voxel(tri) is bad.

Edit: Here's a debug-printed example of the applied transformation.

Code:

Edit #1 and #2: More debug output revealed that the first tv.resize() isn't doing what it's meant to. It's doing something closer to reshape().

Edit #3: It seems the distinction between a = numpy.resize(a,shape) and a.resize(shape) is one that's confusing me a lot. I'll have to re-read the numpy documentation, because I didn't expect a.resize(shape) to act like a.reshape(shape).