Sketchup Exports Bad 3D Models - but only in some formats


#21

I’m sorry, but that makes no sense to me. It is computationally trivial to split up a mesh if that’s what you want. It doesn’t even require a search, you just do it. It is not computationally trivial to find a nearest neighbor, which is what you need to do in order to weld vertices. That is why I don’t want to impose this burden on my own software when it already has to deal with large models, e.g. 24 million triangles is typical - in the SketchUp universe that would be 72 million vertices to search for nearest neighbors. Even if my algorithm is O(n log n) that’s still a significant overhead.

And it is certainly a bug: if you export to OBJ the vertices are shared, if you export to FBX or 3DS then the vertices are unshared, connectivity information is lost. All of these formats have similar capabilities in the current context (i.e. the can all encode connectivity without relying on infinite floating point precision). They can’t all be an optimal representation of the same model.


#22

Sorry, I meant 0(n). In this case you are not searching for a nearest neighbor in the normal sense where two points are considered equal if they are within a specific tolerance, you are looking for vertices with identical coordinates (by virtue of stemming from the very same vertex in Sketchup) which means that you can omit sorting or space hashing and instead use a normal hash.

For example, a vertex with coordinates (10.3, 15.1, 8.7) is inserted in a hash with key (string) “10.3,15.1,8.7” and data is the new common vertex for all vertices with these coordinates. The cost of bunching together 10 vertices with identical coordinates is 10 lookups in a hash. The welding can be performed with a single pass through all vertices.

Whether the exporter exhibits a bug or not, well, we really don’t know. Maybe it’s because of laziness, but as I see it, there may be a legitimate reason for duplicate vertices. However, I personally agree that an FBX export should reflect the connectivity of the Sketchup model and the format by itself does permit it. It would be interesting with a comment from the Sketchup team.


#23

Sorry, that is not correct. Even if you only test for equality (which would be unreliable with floating point), it’s still comparing every vertex with every other vertex, which is O(n^2). In the example model given earlier, that is (72,000,000 * 72,000,000 * 3) floating point comparisons just for this function.

That is actually worse than the O(n log n) full algorithm I had in mind, i.e. keep the vertices in sorted order of X say, and only compare against the other vertices which fall into the required range. Or use a hash table to eliminate the need to sort.


#24

The fact that we are looking at identities makes the problem similar to counting the number of occurrences of specific letters in the array [“a”, “b”, “b”, “b”, “a”, “c”, “c”]. You iterate the array once and fill a hash on the fly. In ruby it would be something like:

hash = ["a", "b", "b", "b", "a", "c", "c"].inject({}) { |hash, char|  
	hash[char] = hash.has_key?(char) ? hash[char] + 1 : 1
	hash
}
puts hash.to_s 

And the result is:

{"a"=>2, "b"=>3, "c"=>2}

So, you make one iteration through your list of vertices O(n) and make a hash lookup for every vertex O(1) (ideally…).

Now, can we treat floating point numbers as strings? Well, in this case the answer is probably yes since the numbers come from the same source. They are not processed through different transformations and so on. I would give this welding scheme a shot at least.


#25

@DonMilne

Be aware that I have taken your recommendations and I have entered them into our system for the improvement of our exporters.

Cheers
CD


#26

@ChrisDizon: thank you very much for that good news.