Computer Generated Lego Landscapes

[SylvainLS]

Little updates on both ldraw_cliff and ldraw_landscape:

• for both, it’s mainly about how parameters and their default values are handled (easier to edit),
• for ldraw_landscape, I added explanations and fields for the size of the uploaded image (which I can’t access from the html) to avoid loosing information when scaling.

I made heightfields for the relief baseplates but I’m not very happy with the resulting landscapes: the baseplates become quickly unrecognisable with randomness , so I fear it’d only actually be usefull to make scaled brick (or rather plates) versions of the baseplates (using a slope of 0).

[SylvainLS]

Hey people,

I see my last post generated a few views, so I’m guessing I’m not talking in my head 

I have a puzzle for someone who knows their stuff about voxelization.

I implemented (or copied and translated to be more precise) 3 voxelization methods and “devised” my own:

• method 0 is Schwarz-Seidel (implementation Rama Hoetzlein),
• method 1 is Voorhies’ cube-triangle intersection (Graphics Gems III),
• method 2 is Tomas Akenine-Möller’s AABB-triangle overlap (his code),
• the first three methods go through the whole voxel space for each triangle to search for the voxels that intersect with said triangle, in O(number of triangles x voxel space size),
• method 3 is mine: I use Bresenham to draw the edges and fill them, I simply draw the filled triangle in the integer voxel space, in O(sum of triangles’ surfaces).

The results on the 3947 crater plate (hey it’s LEGO! still on topic!), 5656 triangles (no studs!), with a voxel space of 100x100x16 (yes, it’s small, you need to zoom): 

As for results and the main puzzle:

• 0 shows “flares” (and a nasty one at that), I guess it’s floating point calculations errors with small vertical triangles (?), but I’m really surprised the implementation doesn’t care,
• 1 shows (you need to look closely) large “empty” triangles (their content is black, it should be gray-1), I guess/hope it’s a rounding error but it’s disappointing for flat triangles,
• 2 is perfect (AFAICT),
• 3 has some little troubles (corner cases, pun intended), and doesn’t find the same results (rounding issue? too simple).

As for running on my PC (run with 4 threads, first time is real time, second time is user time (aka time it would take with one thread)):

• 0 takes 19s/76s,
• 1 takes 10s/39s, (better, as expected),
• 2 takes 4s/16s, (even better, as expected),
• and 3 takes 0.04s !! 

And that’s my second puzzle: I haven’t found anyone using a similar method out there, why?

(Why 4 methods?  As usal: I started with mine, thought someone necessarily did better before, found Hoetzlein’s code and method, found that his own method is flawed, used his code for Schwarz-Seidel’s, found the flares, found Voorhies’, had a problem because of a stupid copy-paste of mine but thought it was the code that had the problem, found Akenine-Möller’s, still had the bug, found the bug was mine, ran all three, thought, hey, why not finish mine to see if could work?)

So if someone is interested in discussing this or could point me to someone who’d be….

[supertruper1988]

I know some of these words

I would love to learn about these things but for now my only question is, how much trouble is caused in the corner cases and do you mean edge cases of variables or literal corners?

[SylvainLS]

34 minutes ago, supertruper1988 said:

how much trouble is caused in the corner cases and do you mean edge cases of variables or literal corners?

Both, that was the intended pun 

My method seems to have problems in the corners of the image (they are white, they should be Batmanesque (black or very very dark gray)), and as those are where there are tiny vertical triangles (the sides of the rounded corners of the baseplate), I think it’s a problem with too tiny measures.  I haven’t investigated yet.

(Hmm, simply eliminating too small triangles (making them one point or a line) could solve the issue without my having to think about it too much…. )

And don’t be too overwhelmed by the big words and the name dropping.  It’s just for people who want to know or search the names themselves.  I only knew about Bresenham because I used it in the 90’s, the rest I found in the last couple of days.

[Philo]

11 hours ago, SylvainLS said:

I haven’t found anyone using a similar method out there, why?

Let's face it, maybe you're a genius ;) More seriously you are is a  favorable case as you are sure there is only one sheet in vertical direction, that helps...

[SylvainLS]

4 hours ago, Philo said:

Let's face it, maybe you're a genius ;)

I think I should feel insulted by the “maybe” 

 

4 hours ago, Philo said:

More seriously you are is a  favorable case as you are sure there is only one sheet in vertical direction, that helps...

Actually, it does not because I don’t use that property in my method: it really draws all the triangles (and fill them) in the voxel space.  It doesn’t eliminate lower voxels before they are all found/painted.

With the other methods, which go through the whole space for each triangle (loop on all x, all y, all z), I can optimize in two ways: 1. the simplest, do the innest loop in descending z, stop it at the first encountered voxel by the current triangle, 2. memorize the current uppest z for each x,y (so, for all the previous triangles), only look between that and maxz for the next ones.  I only implemented the first one not to mess to much with the algorithms while still debugging the rest.

Anyway, I found the corner bug: just me being stupid again   (rotating only half what should have been rotated).

I also thought a bit more (ouch), and realized the other algorithms have their 0,0,0 voxel centered on 0,0,0 (corners at ±0.5).  Mine works more like it’s centered on 0.5,0.5,0.5 (corners at 0 & 1).  Once corrected, the results are still different but closer.

My method doesn’t paint voxels that should be painted.  That’s what Bresenham does after all: it draws a line with a minimum of pixels, it does not find all the pixels crossed by the line.

So, if I look at all the voxels found (not only the upper ones), I get fewer voxels than the other methods.  But it’s not a subset: I find some voxels that shouldn’t be there.  Drawing “degenerate” triangles (with a tiny edge) with only one line helps a bit with those supernumenary voxels but not all.

Well, so it might explain why it’s not the preferred voxelization method but it doesn’t explain why I didn’t find anyone talking about it.  I think it’s a very very fast near-enough method.

I’m going to voxelize simpler but more general parts (maybe a minifig head) to better compare the results….

[SylvainLS]

Okay, green images are the “correct” voxelization, turquoise images are “mine.”

 

That’s supposed to be a 3626c head (a bit stretched).

You’ll notice the “correct” voxelization algorithm have problems with the sides, it looks like an apple core 

I highlighted in red the major problems with my method: the horizontal triangles that form the flat circles go further than the vertical ones for the cylinders.  We can also see inside because the last horizontal slice is missing (simple limit issue, it also happens with the “correct” method but is less noticeable as there’s no side).

Because the “correct” result was missing the sides, I tried with an even simpler model: 3005.dat.

 

As you see, both are still missing the last slice.  Still a couple red voxels for my method, but the “correct” one is also missing the inside box!

[SylvainLS]

Just for completeness (black is method 0, blue is method 1, red voxels are obvious errors):

   

So, nobody’s perfect, though 0 doesn’t have any voxel missing (not even the last slice).  1 has less problems on the outside but is missing part of the inside!

 

[Calabar]

On 4/12/2020 at 4:09 PM, SylvainLS said:

Okay, so here it is.
It’s a simple diamong-square/“plasma” algorithm. 
You can feed it a heightfield image and it will “alter” the results.

Does it means we could expect ready-to-use lightmaps for all existing raised baseplates?

The topic is becoming more and more interesting. Do you think to take methods 0-2 as example to refine your method or do you think to provide a multiple solution, wth the better one as default?

Edited April 24, 2020 by Calabar

[SylvainLS]

7 hours ago, Calabar said:

Does it means we could expect ready-to-use lightmaps for all existing raised baseplates?

I’m still considering what’s best and simplest (or the most “good-&-simple”).

On the one hand, providing ready-made maps would be the simplest.  But size matters: a wrong scale, a too small or too large image or not enough shades of grey or too many, and you risk loosing details when you apply it.  That’s why I’d rather people do their own maps.

On the other hand, providing a simple way to make a heightmap from a .dat file isn’t easy.  The program needs to parse the LDraw library, which can’t be done in a simple HTML page.  I could dump my program’s sources somewhere and let people use them but then, that greatly reduces the number of people who could use them (need to compile the C++, have to make everything OS-agnostic…).

So, now that I have written that down , I’m leaning toward a middle ground: provide the triangles files for the baseplates along with a simple triangles-to-image HTML page.

 

7 hours ago, Calabar said:

Do you think to take methods 0-2 as example to refine your method or do you think to provide a multiple solution, wth the better one as default?

I can give the choice.  They all more or less give the same results, especially for heightmaps, and in about the same times, once optimized.  (Plus, optimizing with bounding boxes remove spurious voxels in methods 0 to 2.)

As for my method, I think using another algorithm than Bresenham to draw lines should give better results… but I need to find or devise it first  

[SylvainLS]

Okay, so after a few days trying to find out why there were holes with so-called “conservative” voxelization methods, I give up trying to get always perfect results.

Indeed, I found a complete implentation (not just theoretical or copy-pasted snippets) and it doesn’t seem to care about holes (this one, it provides input examples files too (so it’s not my input that’s broken)).

 

So, here’s a simple web page to convert a triangle file (text file, one triangle per line, 9 space-separated coordinates per triangle) into a heightfield PNG usable in ldraw_landscape.

I put triangle files for all(?) relief baseplates too.  Don’t forget to set the size to the size of your landscape (preferably 2^n+1 (65, 129…)) and beware of non square baseplates.

And try the different methods and different sizes if you don’t like the results.

[Philo]

57 minutes ago, SylvainLS said:

So, here’s a simple web page to convert a triangle file (text file, one triangle per line, 9 space-separated coordinates per triangle) into a heightfield PNG usable in ldraw_landscape.

What's the best way to restart the voxelizer after changing parameters? so far it seems I need to change input file (to a different one!)

[SylvainLS]

23 minutes ago, Philo said:

What's the best way to restart the voxelizer after changing parameters? so far it seems I need to change input file (to a different one!)

Ah, yes, oopsy, the heightfield is indeed computed each time you upload a file, I hadn’t tested Chromium: in Firefox, you can choose the same file repeatedly.

I’ll see what can be done….

[SylvainLS]

Ok, done, new version (I only changed the html).

[Philo]

11 hours ago, SylvainLS said:

Ok, done, new version (I only changed the html).

Thanks! I also increased smallcanvas size to 128x128 to get a better direct preview of the result...

[SylvainLS]

Ah yes good idea.  The canvas is a necessity to make a PNG the simplest way, its functionning as a real preview is just a bonus I hadn’t really thought of  

It’s about the same in ldraw_landscape: I need a (visible) canvas to read the pixels in the heightfield image, and it serves as an indication the image loaded successfully (which sometimes doesn’t happen, the joys of JavaScript).

[supertruper1988]

Why the odd number for field size?

 

[SylvainLS]

It’s because the heightfield should be the size of the landscape and because the diamond-square algorithm used by ldraw_landscape is recursive and cuts dimensions in 2.

It works in 2D but, explained in 1D, it works this way:  take a segment, that’s 2 points (2 = 2⁰+1), cut it in 2, compute the middle point, you now have two segments, 3 points (3 = 2¹+1), cut them in two, you now have 4 segments, 5 points (5 = 2²+1), …, at iteration n, you have 2^n segments, 2^n+1 points.  (Keywords: Von Koch line (and snowflake), fractal mountains.)  On a square, it’s a two time algorithm (the diamond-square algorithm): you start with a square, compute the 4 middle points (diamond), then the center, you now have 4 squares, rince and repeat.

But, well, it’s not that important for the end results because:

• First, I implemented it to act as if the previous iteration was done, so, if you ask for a 7x8 landscape, it acts as if 9x9 was done and computes the four 5x5 landscapes, 3 of which are truncated.
  But that means the missing points are at 0, not driven by the slope parameter.
• Second, the heightfield is multiplied with the random landscape, so it doesn’t change the way the random landscape is computed.
  But I’m not sure I won’t find a better way than a multiplication.

 

[supertruper1988]

So how does this apply if I want to have something in even baseplate sizes like 32, 64, 96 etc?

 

Then back to your triangle program, do you know if I can make an STL into a TRI file? If I recall, STL's are already triangles. I would not be doing intricate shapes but rather cuts and fills in some hills. Thanks for the education BTW it has prompted me to get into to some JS courses. 

 

 

[SylvainLS]

6 hours ago, supertruper1988 said:

So how does this apply if I want to have something in even baseplate sizes like 32, 64, 96 etc?

Just use 32, 64, 96, etc.

 

6 hours ago, supertruper1988 said:

Then back to your triangle program, do you know if I can make an STL into a TRI file? If I recall, STL's are already triangles.

Precision: I used the .tri extension but I’m not the only one to have used this extension (meaningful TLA are in a limited number after all).  Mine are just plain text files with coordinates, easy to get from LDraw .dat files.

I could have taken .dat files directly but then you need flattened (= all subfiles included) files, and it would have added a conversion layer for those who want to make their own files.  The same can be said for OFF, STL, or other triangle files: choose one and someone would have wanted another one.

As for STL files, indeed, they are just (and already) triangles.  You’ll need make a script to convert them to .tri: just ditch anything but the vertices coordinates and put them all on a line, separated with a space.  The coordinates are read with the JavaScript parseFloat function, which means it’s the standard C representation (“123.4” or “1.234E2”, etc.).

Edit: IIRC, you have a Mac, so awk is readily available (otherwise install it). This should do the trick with STL text files:

awk '/vertex/ {t=t $2 " " $3 " " $4 " "} /endloop/ {print t; t=""}' file.stl > file.tri

 

Edited April 28, 2020 by SylvainLS
awk example

[Legonaut]

On 10/3/2019 at 4:51 PM, SylvainLS said:

Nice.

Your post reminded me of a script I made a few years ago that generated cliff landscapes like this one:

(higher resolution)

I translated it in Javascript (for portability) and it’s available here (licence GPL 3+).

I downloaded it but what do I have to do now? Sorry but I'm not that good with this kind of stuff, altough I would love to use this generator!

[SylvainLS]

19 minutes ago, Legonaut said:

I downloaded it but what do I have to do now? Sorry but I'm not that good with this kind of stuff, altough I would love to use this generator!

If you downloaded the zipfile, unzip it.

If you downloaded the files, be sure you have ldraw_cliff.html and ldraw_cliff.js together.

Now open ldraw_cliff.html in your browser (Ctrl-O should open a file dialog on about every browser).

Fill the form and click the button at the bottom.  Once the file is ready the link next to the button becomes clickable and you can “download” (save to disk from memory) the LDraw file.

[Legonaut]

It worked but I'm confused with the Colour numbers, on what are these based off? Is there a list for them?

What I already got as results was reeeally good!

[SylvainLS]

7 hours ago, Legonaut said:

It worked but I'm confused with the Colour numbers, on what are these based off? Is there a list for them?

LDraw colour codes (we’re making an LDraw file here).  See http://ryanhowerter.net/colors.php for an extensive table with LEGO, BrickLink and LDraw colours names and codes.