Decreasing poly count on models

[Nicola]

Ok i have this question: suppose that i want to make a low poly version of a model (made of N parts), suitable for real time graphics for example in a videogame, how could i substantially reduce the amount of vertex and polygons while keeping as much details as possible? I'm not interested in keeping internal structure, just to obtain a lowpoly model.

One thing that came to mind was to remove all studs from the parts (they're relatively small in a model, expecially when seen from apart, and take up a lots of vertex/poly), and it would be easily done by removing all stud*.dat primitives. Also removing all greeble on the bottom of bricks would help a lot (but it's harder as, afaik, they're not primitives?).
Another thing could be to remove all internal, non visible parts, but how to do it algorithmically is bejond me.

So can anyone point to some algorithm or want to share some idea ?

[Travis Cobbs]

Actually, the tubes on the bottom of parts (like the generic 2x4 brick and 2x4 plate) use stud primitives also (stud4.dat for that diameter tube). Unless you're viewing the model from a long way away, though, it's not going to look at all like LEGO if all the studs have been removed.

[Roland Melkert]

You could play around with bump mapping or tessellation to replace the studs. Biggest problem would be to generate the needed textures.

[Tim Gould]

Yes removing studs doesn't look great (you can do it easily in POVray). Even at a long distance your brain just finds it off. I build pretty studless models, but leaving off the few that remains ruins the LEGO effect.

But... I reckon replacing studs by cleverly chosen textures _might_ work alright at a distance.

Tim

[Nicola]

yeah maybe using some ad-hoc shader to simulate studs would do, but it's not that easy..
and what about removing inner bricks? anyone has ideas?

[Michael Horvath]

The LDBoxer tool might help you remove some more polys.

http://home.swipnet.se/simlego/ldraw/ldb...dboxer.htm

[Vincent Majorczyk]

I'm working to solve this problem (reduce faces number).
I have an idea which need to be improved.

first, you merge all files which are used by your model.
second, you display your model with an unique color (example: white; no light effet).
trird, you display a closed mesh which represents all possible points of view (another color: blue).
next you place your point of view at the position of the tested face (normal to the face) with an angular vision of 180° (don't display the tested face).

So, if there are blue pixel, the face is visible from the mesh of possible points of view.

[Nicola]

That's an interesting algorithm, i tried to come up with something similar..
So if i understood correctly, basically you sit on every face of the model, and look up the normal. if you see any "blue", that means the face is also visible from the "blue" (so must be kept), otherwise if you see only white, you can conclude you're an inner face and can be removed.
One thing that came in mind is how you compute the "point of view" mesh. In the simplest case, it could be a sphere enclosing the whole mesh, am i right? But i feel that it's more complex than that. If you have a convex model, there can be points that are never visible from the "outside sphere", but are still on the surface, and you could possibly see it "navigating inside" the model.

The only other problem is performances (it should render a frame for each face in the model), but of course the whole algorithm can be precomputed beforehand so not really a big deal.

Have you implemented anything yet ?

[Tim Gould]

One thing that came in mind is how you compute the "point of view" mesh. In the simplest case, it could be a sphere enclosing the whole mesh, am i right? But i feel that it's more complex than that. If you have a convex model, there can be points that are never visible from the "outside sphere", but are still on the surface, and you could possibly see it "navigating inside" the model.

Although I can't prove it, I'm fairly certain that any external face must have an even (including zero) number of faces between it and the viewer. So your convex face can be found by counting intersections.

I'd like, one day, to make a program that can "auto BFC" a part by this method by tracing a ray and flipping surfaces as needed. But it's slow and thus not a routine you'd like to do every load. Do it once and prepackage a BFCd library.

Tim

[Ben Supnik]

Hi Y'all,

This topic may be of interest to LDraw viewers too since it's easy to get geometry bound.

This might be a silly idea, but for some parts you could calculate its axis aligned bounding box and then rendering an ortho view of the part (projected onto the bounding box) to a texture that becomes a normal map; then draw the bounding box with the normal map in-game. The idea is that you'd be "baking" studs, greebles and other small detail into a texture, which is something the game engine may be prepared to cope with.

(Commercial games use this technique in real production - you model a low polygon final object, then add 3-d detail, then 'bake' the 3-d detail back onto the low detail.)

One of the wins here is quality: when studs get very small you get a ton of aliasing due to tiny triangles - even 16x FSAA doesn't go that far. But geometry faked with a texture is subject to mipmapping, giving you good down-sampling to small sizes.

In BrickSmith I am experimenting with replacing primitives with their bounding box based on the size of the part in screen space in real-time - so it's a dynamic LOD scheme, not a net reduction. But in the case with a large number of parts, it's a win: zoomed in, parts are culled off-screen, and zoomed out, many small parts are reduced to bounding boxes, while the big parts are preserved. But the results are medium-quality at best...it's done for performance reasons.

cheers
Ben

[Nicola]

I'd like, one day, to make a program that can "auto BFC" a part by this method by tracing a ray and flipping surfaces as needed. But it's slow and thus not a routine you'd like to do every load. Do it once and prepackage a BFCd library.

Tim

I think it would be much better to have normals included directly in the quad/tri data, precalculated by the part author, just like any 3d format. All that stuff about BFC, invertnetx, matrix flipping etc is insane, i've never seen in any 3d framework, and i've seen some

[Tim Gould]

With ldraw 'better' depends a lot on perspective. The file format and large parts library maintains backwards compatibility to the 90s. It's also hand editable. It's also highly portable.

Where it does fall over in matching with modern 3D standards. But to change that in the way you'd like we'd need to alter the entire parts library, all the techniques and technology written for part design, and entirely break backwards compatibility.

Or to put it another way, what is good for a renderer is not necessarily good for any of the other tasks of the file format.

Tim

[Nicola]

With ldraw 'better' depends a lot on perspective. The file format and large parts library maintains backwards compatibility to the 90s. It's also hand editable. It's also highly portable.

Where it does fall over in matching with modern 3D standards. But to change that in the way you'd like we'd need to alter the entire parts library, all the techniques and technology written for part design, and entirely break backwards compatibility.

Or to put it another way, what is good for a renderer is not necessarily good for any of the other tasks of the file format.

Tim

Yes i understand the motivations. Still i think something should be made in that direction. It doesn't have to break compatibility, just like BFC extension didn't. A good normal support extension would make many ldraw quirks obsolete and solve many current "bugs" such as mismatching half curves, weird minifig heads and such.

Btw, while backward compatibility is important, there is a moment when you have to draw a line and drop all 20 years old legacy that holds back, all softwares do that. I'm not suggesting to do that now, after all i'm just the last arrived here, i don't want to look arrogant

Also we are going off topic, eventually we can discuss this on another thread

[Ben Supnik]

Hi Nicola,

I had a very similar reaction when I first looked at the LDraw file format - coming from a 3-d rendering background, my immediate reaction was "why isn't texturing UV-mapped? Why aren't normals per vertex?" Allen gave me some background into the LDraw format, process, etc. that was helpful.

I think you have to view LDraw as a _source_ format, not a _rendering_ format. X-Plane's objects have per vertex normals and UV-mapped textures, but our artists don't use that format to create things. They use a 3-d program with all sorts of complex, tweaky stuff - automatic subdivision, NURBs, deformers, etc. The 3-d program and an export script then 'bake' the work down into the simple, boring, basically fully-precomputed format the renderer wants.

You could totally define an "LDraw processed" part format that was designed for ease-of-render, and not at all meant for editing. You could have UV maps (instead of projections from the tex spec) and per vertex normals (instead of crazy algorithms to 'guess' normals), you could subdivide all quads into tris, you could pre-compute vertex sharing, you could even pre-compute LOD info.

The advantage of such a format would be that usage of it would be trivial for rendering programs - a lot of the hard work of drawing LDraw is in getting from raw LDraw to that "pile of triangles" state the hardware wants. With a pre-baked format, the analysis code could be written once and saved to disk to be used by everyone.

But that doesn't imply that the needs of a 'baked' format necessarily apply to the source format. I would even say that one of the nice things about pre-processing is that you can afford to do algorithmic transformations that would be too expensive/complicated to put in the renderer itself.

I think it would still be useful to have some idea of a long term road map for .ldr files -- as a source format. This is one reason why I've been skeptical of proposed normals to fix normal smoothing issues: I think we should have an idea of what a comprehensive solution looks like before we accept parts of the solution into the library.

Cheers
Ben

PS, I agree that BFC is really quite complicated. :-) But I think the -derived- results of a 'baked' part with BFC are pretty tame - a pile of CCW quads with some marked as two-sided (or doubled to form the back faces).

[Paul Griffin]

BFC is easy...well, compared to bowtied quads. I could not believe how many ways you could bowtie a quad.

Now if only there was a simple algo for conditional lines...

[Nicola]

i finally got around and tested this thing, with a slightly different algorithm.
I tested it on one of my models (this one) and the results are that i was able to go from 71k triangles to 32k. While this is substantial (more than 50% off), i was expecting something better. Stacking parts should hide both top studs and bottom "female studs" cylinders and internal boxes, greatly reducing face count. But probably rounded parts and wheels (that have a lot of insets) still make a huge face count.
Performances were quite slow, requiring tens of minutes to get around a model (of course it was a completely un-optimized test).

[Ben Supnik]

Hrm - are you saying that your model was slope in the rendering engine with 32k triangles? If so, can the engine be made faster? Pretty much any desktop hardware you run on should be able to plow through that sized mesh.

(It might be easier to make the rendering faster than to further remove detail...)

cheres
Ben

[Nicola]

no no the rendering was fast, it was the preprocessing that took ages

[Michael Horvath]

Any progress? I am very interested in this as well.

[Antonio Cortés Carrillo]

A very very long time ago (2004), i implemented a similiar algorithm that detects and removes the inner parts of the model.

If you are interesting, can find it here:

http://buf3d.cimplus.es/download/pfedit2.zip

Is not the buf3d, is much older and for that reason:
* Does not properly read all 3D Ldraw models.
* Do not use GPU (but works very fast ... )
* Well .... sure there are many bugs that buf3d already solved

For use, these are the steps to follow:
- Import->Ldraw Model (I will ask the library directory)
- Optimize-> Select Objects Ocludded
- They will leave many options without touching it will be fine (9/16 iterations)
- After the process, the internals parts appear selected
- Selected-> Show Selection Only (Optional)
- Selected-> Remove Selected

Removes over 50% triangles, easily

[Michael Heidemann]

Very interesting and a good point to start or add to already existing techniques. Thanks for sharing.

[Steffen]

I thought always that such an algorithm was used inside windz.exe
which can auto-BFC a part.
Am I wrong?

[Michael Heidemann]

I think yes, but as we do not have the source code for windz we do not know.

[Philippe Hurbain]

Here is a quick description by Ildefonso, when we discussed about issues that Windz has with open (eg. subparts) structures:

The ray tracing algorithm casts rays randomly. It counts the number of hits that were done by both sides of the triangles/quads and if this difference is bigger than 70% it assumes that this is the outside of the triangle. Once it finds the outside of one triangle, it finds its triangles/quads neighbors and set the same orientation for them.
My idea was to remove this randomness letting the user to set the direction that the rays will follow. So, one could choose if all the rays would be cast from top to bottom, from right to left and so on. I think that even with this algorithm, we will have some cases that it will not work, but this should help in simple cases like flat parts.

[Michael Heidemann]

Thanks for that.
His suggestion for flat parts works, I have already coded the same but throw it away because only some parts are really flat and those can be easily corrected nowadays with MLCad (swap).

[Michael Horvath]

A very very long time ago (2004), i implemented a similiar algorithm that detects and removes the inner parts of the model.

If you are interesting, can find it here:

http://buf3d.cimplus.es/download/pfedit2.zip

Is not the buf3d, is much older and for that reason:
* Does not properly read all 3D Ldraw models.
* Do not use GPU (but works very fast ... )
* Well .... sure there are many bugs that buf3d already solved

For use, these are the steps to follow:
- Import->Ldraw Model (I will ask the library directory)
- Optimize-> Select Objects Ocludded
- They will leave many options without touching it will be fine (9/16 iterations)
- After the process, the internals parts appear selected
- Selected-> Show Selection Only (Optional)
- Selected-> Remove Selected

Removes over 50% triangles, easily

Bump. Does this tool output to the ldraw format too? Or something else?