Mrz00m
Fractal Lover
Posts: 204
|
 |
« Reply #9 on: October 13, 2017, 11:52:17 AM » |
|
Awesome Thragor! very impressive. I'm going to hyjack your thread a bit with some technical information about point clouds.
I know quite a lot about efficiency and precision for point clouds algorithms that would be good in MB3D... So here is some programming advice for the MB3D superheroes to make faster, smaller, anti-aliased clouds:
it's good to keep all surface corner points with normals like (1,1,-1) throw out all flat points that are facing X-Y-Z normals (1,0,0) and perhaps even edges (1,1,0) normals, to throw out the aliased flat points, i.e. that are held within a plane of your resolution grid, especially for round objects...
Why is that awesome?
It compresses your point clouds size by 97 percent, from 30,000,000 points to 1,000,000 points
the point cloud is fast to mesh, and the file is 3MB rather than 500MB
the resulting cloud is less aliased, no flat zones and staircases
it's very easy to program
here is one way to do that:
March through all the voxels (resolution grid), x, y, z, and for every solid threshold point which is worth a cloud point, measure the 6 points neighboring it on -x+x, -y+Y, -Z+z, and average those neighbor points, if the space is empty or not, to know which way the point is facing, and delete points which average to zero normals, they are rare noise points, and also disgard all the inside-volume samples which don't have empty space in one of their 6 neighbours.
That's efficient because you only do one read loop through the space in x, y,z, and check the space in all directions from every inside sample in order to obtain the surface edge and the normals in one go, and it's easy to program, about 30 lines. and in the read loop, for every cloud point, you sample the neighbours and find out if it's aliased, if it's flat, if it's a true corner point with a normal of (1,1,1) or a lesser, ridge corner facing towards (1,1,0) for example. I tend to keep only the (1,1,1) points. I have code for this process so i can provide that for you to check out if you want.
So, in one march, you have discovered all the points which lie on the outside of the structure, and you also have precise normals for them, and it less aliased because you have thrown out all the flat zones and only kept the points with the most information.
For anti-aliasing, I also did another algorythm second pass when i had all these corner cloud points without the flat zones: search the nearest point on the voxel layer of x-1 and x+1, where every point in sandwitched in between, and find out what the slope is to one or both of them... this gave me very precise normals when make for nearly perfect anti-aliased round objects from low res point clouds.
To do the anti aliasing and precise normals for all corner points that I kept, i ordered all the points in X, Y, ans Z sequentially, which takes about 1-2 seconds of processing time, and i kept an array to say how many points were on every layer x=1 to x=999, and where every layer starts from so 3 arrays in total: order the point cloud by x, say how many points are on every x layer, and third array to say where x layers start from in the giant point cloud array, so a big array of 1 million points, and two small arrays of 999 points, where value X,20 = 45means there are 45 point sin x layer, and value X,20 starts from big array point 432234, so you start reading point cloud at value 432234, read only 45 points from it, and you have anti-aliase it ... So if we are refining all point in x=20 and that face forwards, we simply read all array data starting points in x=19 and x=20, and find the nearest point on the layer below or above, and use it to construct the anti-aliased normal.
That's one way of doing it within MB3D, and there is a better way:
The above level is for a voxel grid, and within MB3D you have a lot more freedom with access to the formula results. So if i were to do clouds within mandelbulber, i wouldn't use a voxel system to do anti-aliasing and to keep the points with the most information. i would use 3x precision ray-tracing... So, every time you have found an edge voxel with an empty space in one of the 6 neighbors, you sub-raytrace within that small cube to devide that cube again by 100, or you average the exact ISO value of the neighbors to find the points precise position wihtout even raytracing, using just the neighbor point iso values, that avoids all aliasing to begin with, it's much better. for all surface points with >1 empty neighbors, you keep and compare the neighbor ISO values, a surface point of ISOval 0,1023, with -x 0,4041 and +x of -0,1044, you can move that point position on X to exactly (0,1023+0,1044)/2, anti-aliasing allpoints fairly fast on the fly, and exporting true point clouds with decimal points, and not voxel type point clouds, very nice!
So, i'd march through the grid space, check the neighbors of every solid point, throw out all the empty points and the points with 6 neighbors which are not boundaries, and sub-sample the MB3d formula, to get the color and the normal values... for example, you can use true marching cubes type logic within every edge point that you have detected, which has neighbors on 0 and on 1 and definitely contains an edge... you measure the exact position of the ISOsurface on X, Y and Z, and then average the neighbor ISO values to have a very precise position and normal value.
That still leaves the question of how to simplify the resulting giant clouds of marched, because all the points will be fairly precise interpolated, resulting in precise point maps. it would be good throw out a lot of the flat spaces whilst simultaneously keeping all the points of details in the intricate zones, non flat zones... Here is the trick:
Compare every point in the point cloud with the 20 closest points and throw out 10 neighbor points if they have very similar normal values: they are all in a flat zone coding the same information in duplicates. you can use M-nearest neighbor algorithm for that, or by putting the points into layers based on X, Y , Z integer value,(even if the points at that stage have decimal precision), and searching in the layer above and below, for all points in a given distance with the same normal. If they are on the layer above and they all point upwards, you know you have lots of flat zone points and you can eventually get very precise point clouds from MB3D with only 5 percent of the data that is currently used, using very fast algorythms that should only take 5 minutes for 3000x3000x3000 array, and can also subsample all the edge points to get 100x more precise point positions without aliasing.
|
October 19, 2006, 08:42:52 PM
Dilber MC Theme by HarzeM