THE FASTEST EVER 3D / 2D FLOOD FILL SCANLINE CODE, IS ALSO THE EASIEST!!! 

Do you want to achieve a 9 million pixels/second floodfill on a single core of i7 7700? using less memory than a generic list? Read on!

Here is a video with a simple graphic illustration:
https://www.youtube.com/watch?v=Xddws-50Igs&feature=youtu.be

If you don't believe me, here is a video filling 4.7 million pixels per second on a 2011 AMD FX: 

https://www.youtube.com/watch?v=4hQ1wA4Sl4c&feature=youtu.be

I started this quest by researching tutorials, codes, and implementations of floodfill, to understand the methods, logics, tricks, tips. Scanlines, recursive, generic lists...

Most algorithms are very long!!! they use too many instructions, excessively complex neighbor-search logic, scans, scanlines, and processes, and they use stack-disorganized memory or generic lists.

I'll explain the 9 million pixel per second method for a 2D image flood fill. Read attentively:

TRANSFORM THE EQUATION: 

Recursively Found Flood Spaces = 4^(Xpixel*Ypixel) (billions of duplicate finds)

to

Recursively Found Flood Spaces = (Xpixel*Ypixel) 

(deduplicate the recursively found pixels, by overwriting their previous found status, in an XY array address, that you use instead of system memory, to schedule the next recursion. The XY array can execute a maximum ONE recursion per pixel.. the 4^XY instructions become XY instructions)

My code is the same as a recursion, and for 100x100 canvas, it uses 100,00*28 instructions.

A recursion code uses 4^(100,000)*28 instructions, so I am saving many orders of magnitude of instructions being computed on the processor, compared to the original recursion.

1. Start by writing 12 lines, a four neighbor recursive floodfill code that will cause a stack overflow.
2. Encapsulate the 12 line recursion in a loop and optimize the resulting program's data flow with some 2D arrays. 
3. Decide to keep the recursion simplicity and it's tidy compact instruction set, and record it's read and write progress in some orderly 2D arrays, and encapsulate the recursion in a 2D loop, which will work the same as a scan-square rather than a scan-line, forcing the recursions to write lines and squares. (2D arrays are read with 2-3 processor instruction. i.e. "if (FoundNeighborPixel2D[ x , y ] = empty) RecurseOn ( x , y ) ;   
4. Add 12 lines of code into the recursion, that assign recursion execute commands, to schedule themselves, by write/read their schedule status in an orderly Xpixel*Ypixel 2D array. Encapsulate the recursion in forX; forY; {{ loop, so that the recursion proceeds like a combine harvester in a field, it checks the left square, fills it, checks the left square, fills it, for every loop iteration, and moves up and does the row above, like a very simple scan line.

The PC most naturally progresses through 2D arrays and squares, so that is how we keep the RAM addresses for all stages for the square of the canvas.

Thus you economize a lot of code and a lot of processor executions: encapsulate the 12 line recursion in a loop and optimize the resulting program's data flow with some 2D arrays. 

Using 2x 2D arrays, is like a nuclear submarine where two admiral captains have a key to launching an atomic ballistic missile. Both captains have to supply their key to schedule a missile/recursion. A pixels must be marked as a found neighbor to be processed at all, in the XY loop, and it must be marked checked but not filled, in order to run the recursive function which fills and checks neighbors and marks them in the neighbors array.

So, the 2D arrays are overwriting the found neighbors from the recursion tree when they are found, overwriting into the same 2D array addres for every duplicate found-neighbor. A subsequent recursion for that found neighbor always happens exactly once, marched forwards by the loop iteration... the loop uses 1-2 instructions to check if the current space is uncharted, and 12 lines if is a found neighbor, and then the loop repeats N times until found neighbors = zero, the flood is complete.

( 12 lines means that found neighbours are 1/FILLED AND 2/THEIR NEIGHBORS SEARCHED).

You only have to write duplicates from the tree into two memory arrays: "FoundNeighborPixel" and "FilledNeighborPixel".

Normally, you should have been able to understand the program by now. You can go code your 9 million pixels per second program now! Perhaps more information will confuse the topic? still I have written a different approach:

ORGANIZED RECURSION MEMORY MAP OF A GRID SPACE:

Your recursive loop, proceeding, explodes image data into a tree, 1, 4, 16, 64... branches of neighbor pixels. If we can pack the tree branches back into the image pixel positions, from which they came, i.e. the pixel source of the data, the XY image graph, then we would have a tree with X*Y branches / memory useage. We do that in 12 lines, implementing some 2D arrays to organize the recursion memory.

You place the recursive function into a nested x - y loop, to contain it and give it structure.

for x = 1... the first iteration:

The recursive function finds 4 empty neighbors, it records them for later.

You write those 4 empty neighbors to a 2D array called "FoundNeighborPixel", Do not write them to system memory, else you will explode the neighbors into a tree.

You also prepare a 2D array called "FilledNeighborPixel", Because once you have detected an empty neighbor, you will fill it, and check it's neighbors.

for x = 2... the second iteration:

the recursive function checks pixel number 2, it reads it's status in the "FoundNeighborPixel" Array. 1 instruction returns the value "neighbor marked for checking, check if it is filled and check if it's neighbors are filled/empty/borders" ( If it was not marked for checking, it would have been a border pixel, and we would have break; for that pixel).

If the pixel marked for checking, we will maybe have to fill it. We have an empty 2D array called "FilledNeighborPixel" We check if the pixel is filled in the "FilledNeighborPixel" (which starts off all blank). If no filled, we floodfill that pixel in the "filled" array (and we color that pixel in the original image).
If it IS filled in the fill array, then it has already been fully processed, and it's neighbors will have already have been checked so we break, and save 20 checkneighbor instructions.

The "filled" array will eventually represent the entirety of your floodfill as an XY graph. It is empty at the beginning, so you fill it iteration by iteration, on spaces marked true in  "FoundNeighborPixel" where  "FilledNeighborPixel" is false, and you mark it's 4 neighbors in the "check neighbors" array, otherwise you abort the next 20 instructions of the function and do the next pixel in the loop.

...
...

The loop proceeds like dominoes, the X and Y row gets filled one iteration after then next.

If you click a blank canvas, you can fill a million pixels |(1024x1024) using 20million instructions, that's a bout 0.1 seconds for a Gigaflop processor core like an i7.

When you figure out the above, you will have 9million pixels per second on an i7 processor.

DIFFICULTY OF CODING:
The recursion function code is a 10 line function.
You place it in an XY nested loop, that's 4 lines.
You add 2 break conditions, that's 2 lines.
The 2d-array writing lines slipstreamed into the recursion are another 10 lines of code.
Overall, the entire floodfill code is about 40 lines.

 (perhaps it is not a recursion any more, I am no computing student)

COMPUTATIONAL EXPENSE: 
Individual pixels of the XY loop will use 20 instructions for every floodfill operation, or 2 instructions for every "pixel already found/filled" result.

For a 1024x1024 images, you are using 20 million instructions, about .1 seconds on an i7.

The search loop runs again and again, until it finds zero new Fill operations, then your floodfill space is complete. So it will consume 15 million instructions on the first pass and 2 million on the second pass for example.

To turbo charge the process, you can read the pixels once forwards, once backwards, once forwards, so that the "scanlines" produced by this simple code scan forwards and up for X+ Y+ space on one loop, and fill backwards and down for every second run of the XY nested loop.

Think of your tree branches as your sword, and the image grid as your six pack. may the force be with you.

MEMORY USE:
I processed datasets of 2 billion voxels, using a desktop PC.

2D is the same logic as 3D, it just uses 2D arrays instead of 3D, 2D images instead of minecraft cubes.

for UXGA images, you will need about 10-20 MB of ram.

... THE REST OF THIS PAGE IS WHERE I TRY TO EXPLAIN THE CONCEPT LIKE A CONFUSED TEACHER: THERE IS JS CODE AT THE END. THE REST OF THIS PAGE IS SUPERFLUOUS, IT'S LIKE A CRASH COURSE BY A HIPPY STONED TEACHER:

Flood requires only a search and fill of neighbor cell, if empty, and cells share common neighbors. Instruction duplicates can occur in an exponential tree fashion. That's why people resort to line-scans, rather than using one memory address for every cell, which can deduplicate and overwrite duplicates, and thus lets you use recursion or any search routine you want!!!

For every next search instruction, using small arrays to store the 2-3 steps of your recursion logic/ IF/OR/ comparison your number of instructions by millions of times, resulting in a simple and fast recursive process. The recursion is only 7 lines of code, so why not just write arrays to manage it's comparison results in a duplicate of the original image? Max 3 copies of the image!

My PC was previously crawling on canvases of billion voxels using optimized generic lists and scan lines. 

I found a workaround which employs 2 system arrays vars that both have 6 lines of logic code to read and write, the arrays are addressed using spacial coordinates, i.e. your DIYstack array address is pixel(X, Y) if you use 2D, and it fast keeps track of your recursive progress, for what has been checked, and what to check next.

So you simply recurse through neighbor cells and you memorize your previous checks in an array with as many pixels as there are cells in your canvas/voxel.
The wonder of that, is that you recurse a neighbor pixel search-tree which has trillions of potential duplicate checks/revisited pixels, and any double checks to be performed are written to the same memory coordiante for that pixel X.Y, and then next run of the loop checks those memory coordinates ONCE! and logs it's neighbors for checking again, without duplicates. It finishes as soon as you press the start button.

The recursive floodfill code is 12 lines and another 12 lines of memory array code, to avoid using stacks / generic lists / scanlines.

It's called the SCANBOX ALGORYTHM, because it can iteratively even fill cubes in 3D rather than lines. 

• 2 million voxels filled per second. AMD single core 3.2Ghz.
• 2 MB memory/stack used for 1000 x 1000 pixels
• 2 GB memory for a 1 BILLION voxel space (other people's generic list stack version i tested jammed the PC after 12GB in ram due to excessive branching, Their default run-time stack codes jammed after 10mn voxels)

copyright information is at the end of page, it's a shareware for use in commercial programs.

Instead of the linear memory stack which addresses randomly and automatically, used by default in the computer to record 2D progress. You would use a 2D array to store 2D pixel maps. It's completley logical, but no one did it before!!! it's a recursion IFS type floodfill with a near zero memory/progress impact. weird right?

The virtual RAM block is a boolean array of the same size as the voxels/pixels. 10*10*10 3D voxel canvas is accessed/addressed using z*10*10 + y*10 +x ... 10*10 pixel 2d address is 10*y+x.  It has a spacial memory adressing system, representing your space, any duplicate checks in the check queue are written to the same memory bit.
No duplicate checks can happen in your process, it's perfect organized floodfill memory.

Why is it so optimized compared to other algorythms? The search logic checks neighbor pixels without any pattern or method or scanline, it's rapid! but it can't double check a pixel  for neighbors, and waste time, because pixels marked to check only have one possible array address marked as true/false, in a spatial array.

• The "neighbor pixels to be checked" overwrite each other if they are detected from different neighbor pixels in your hand built RAM space/stack if on the same space, no recursions are checked twice... it's computationally super efficient for spacial trees. It flood fills by marching in straight lines in every direction.

Using the address: z*10*10 + y*10 +x for every time you read a memory position, i.e. 2% of total computing load of a floodfill iteration.

In 2D you can fill all empty pixels above and to the left of the start pixel in a first iteration through every pixel, and you can fill all the pixels underneath and to the right of every previously filled pixel on the second iteration. It means that if you you are filling 1000x1000 pixels with a picture of an rabbit in the middle, the floodfill will complete in 1.5 or 2 seconds, using only as much memory as 1000x1000 pixels with zero memory redundancy. (max 1mn ram true-false spaces)

In 3D it fills all pixels forward up and left of start point on the first pass, and fills every pixel reverse down and right on the reverse pass, and it can fill space of 1000x1000x1000 pixels with a rabbit in the middle in 2 minutes using 1bn ram array.

Here is code summary of the process:

There are two arrays of true false values. 

One of them is a voxel presence/absence array. A sphere in there will be represented by a sphere of true values in the center.  The array could hold voxels and it could be an image in 2D, marking colors and other qualitative information.

Another equal size array is our magic floodfill memory array, which marks voxels to be checked as true. it's more structured, sequenced and low ram than a stack, using 2d/3d array logic (otpionally a 2d/3d type array), 

You write the corner pixel for example 1.1.1 as your first flood fill point. The recursive function marks that pixel as true in the presence/absence ram block... and it ALSO writes 6 neighbors of pixel 1.1.1 in the neighbor checking array... The pixel in front of it, to the left and up of it, which it finds and fills at end of line and row. 

The condition to do a fill a void voxel and check neighbors via a recursion function is if the check on that position is true and the pixel presence is false, it writes the empty as true and checks the six neighbors.

This creates a scanline which sweeps through the entire space, checking forwards as it goes, and floodfills it instantly, as fast as is virtually possible, using almost no ram, with maximum efficiency, and minimal coding. 

(please paypal me at

thank you!!! ;})

here is the code, it's 40 lines of code, 10 lines of brackets, and most of it is comments. On 64bit single core AMD at 3.4GHz it finds 5 million voxels per second at while cube filling and completes a complex 1 billion voxel fill in well under 10 minutes without optimizing as suggested at end.

THIS IS UNITY3D JS CODE, YOU CAN READ IT IN A JS COLORED CODE EDITING PROGRAM:

mesher.supernormous is the voxel positional array.
var sn2 : boolean[]; is a blank copy of the above

function chk(  ) //floodfill pseudo-recursion algo  

{

var last = 0;//count filled voxels since end of a previous loop used to break

for( var i = 0 ; i <99999 ; i++ )

{ //a very complex fill typically takes 20-25 loops to complete

//if(i%2==0)//recommended!!! use flip-flop condition to alternate between forwards tr++ scan and backwards tr-- of memory block, to fill 3 axes both ways.

for( var tr = 0 ; tr < sn2.Length ; tr++ ) //scan forwards through check ram

{

if(tr%10000000==0)

{print(bcnt+ "   --2runin----     " +

(Time.realtimeSinceStartup-tt)+" -=-=-== " + i+"  "+tr);yield WaitForFixedUpdate(); }//make it yield every 1-10mn checks, which will limit the runtime stack at 1 million function calls for example. the entire loop will end up making 500mn function calls total.

if ( sn2[tr]==true &&  mesher.supernormous[tr]==false ) 

{//the check ram block is called sn2

var z = tr/bsizexy ;//convert linear 3D array to 3d xyz positons

var y = (tr%bsizexy)/bsizex ;

var x = (tr - z*bsizexy - y*bsizex) ; 

boundary2( x,y,z  );

}

}

            

if (last == bcnt){print("The program has run"); break;}

last=bcnt;//if written voxel count doesnt increase in last loop, all points found... if did the tr loop forwards and backwards in my version.

               }

// one note about the above function... It does 500mn voxels in 2-3 minutes, but it has maximum efficiency for complex spaces if you repeat the loop in all 3 axes, in both directions. every time you linearly loop through the check memory, it does scanlines on only 3 axes directions, for example x forward makes scanlines in X, Y, Z, and -x backwards scan throuch checkmemory does -X -Y -Z, so, you can duplicates the tr++ loop 6 times on 3 axes both ways, i believe that you could floodfill a menger sponge from the center outwards in as many sweeps as it has recursions. 

function boundary2(  x : int , y : int , z : int ) //recursive floodfill algo  

{

if ( x < 0 || x >= bsizex || y < 0 || y >= bsizey || z < 0 || z >= bsizez )return;

//{

// print( " x "+ x +" y "+y +" z "+ z +" "++""++""++ )};

if (wst( x , y , z ) == false)

{

wsf(x,y, z,  true) ;

csf(x+1,y,z, true);

csf(x-1,y,z, true);

csf(x,y+1,z, true);

csf(x,y-1,z, true);

csf(x,y,z+1, true);

csf(x,y,z-1, true);

}                         

}

csf = write check memory array as XYZ values

wsf= write voxel presence array as XYZ values

wst= read voxel presence array as XYZ values

function csf( x:int , y:int , z:int,val : boolean) //used for writing

{

var tally : int = z * bsizexy + y * bsizex + x;

if ( x < 0 || x >= bsizex || y < 0 || y >= bsizey || z < 0 || z >= bsizez )return;

else

sn2[ tally ] = val;

}

function wst( x:int , y:int , z:int ) : boolean//true if null

{

var tally : int = z * bsizexy + y * bsizex + x;

if( tally >=0 && tally < cubic )

return mesher.supernormous[ tally ];  //the voxel presence array is called supernormous

else return true;

}

function wsf( x:int , y:int , z:int,val : boolean) //used for writing

{

var tally : int = z * bsizexy + y * bsizex + x;

if( tally >=0 && tally < cubic ){  

mesher.supernormous[ tally ] = val; bcnt+=1;}// count written flood voxels

}

You can use the ultimate scanline trick synergetically with other algorythms if you want. It is the best at managing huge spaces in small RAM requirements and filling them very fast. Afterwards it is slower for the last 1% of spaces which could be hidden in cones in a complex surface. so the most optimal is probably to fill the first 99 percent of pixels using the trick, and then copy the last pixels/voxels to be checked to Vector3 position array in a stack function which can do the last 1 million in less time, this would be faster by 10-20 percent than using only boolean spacial memory process. it works fastest with 6 neighbors, you can use N neighbors, 8, 12, so forth.

Please comment if you find any further optimizations for the boolean memory checking scanbox algorythm and for any feedback. Please feel free to perform some measurements to find if scanbox is faster than all other scanline tricks? 1billion voxels in a complex boundary in 10 minutes is a considerable challenge.

COPYRIGHT INFORMATION: 

This is difficult and proprietary research. It is SHAREWARE;), Definitely give me a payment if you have more than 3 employees.
(All rights are retained by the author of the 2d/3d/Nd data flood fill computation technique/algorythm using a check marker array for spacial flood/floodfill processing with spacial check information stored as array indices).  If i have saved you 4-7 days of research and work and superboosted your program, it would please be fair that you send me a paypal payment of 10-50 usd to my given addy:

 

EDIT- It's a good idea to start the entire project using bitwise encode and decode of bit arrays rahter than boolean, it's fast and it can hold 4 times more data for the same amount of memory than boolean and standard fp arrays. i hit the limit of 2.4bn bools per array in 32bit.

META-Arg-searchwords: void c# .net github stackoverflow python picture image 2D 3D volume PNG medical isosurface scan minecraft image stack fiji 

Marching Cubes project newbie development experience conclusion:

Marching Cubes project newbie development experience:

It's been a year since i finished the marching cubes script for U3d, its efficient and useable, but other people have done more editable (diggable) versions and i stuggled to polish all the features and make it user friendly.

The extra 4-5 weeks of effort it took to polish the engine when i was already bored, meant that i overworked the same idea and i bacame allergic to the notion of it. As coders many of us probably struggle with staying on one idea for too long, because fascination comes from always working on unknown and new enigmas and dreams.

All in all, even with multicore, the graphics card would have struggled to make a truly expansive bunch of mesh and there would have been memory leak after playing 5 minutes freefalling through complex meshes. say there was a memory bug after making 5000 meters of mesh, the erase resource command didnt even work. in future i will also research SETMATERIALPROPERTYBLOCK, which i useful for dynamic updated efficient mesh worlds. anyone working on MC now should totally do it in DX11. 100x faster mesh 0_0. ill be doing that soon myself.

Phyllotaxis spiral formulas and codes

Phyllotaxis Spirals,`Sunflower Seed Spirals: 

interesting comparison of 2 similar codes to make Phyllotaxis Spirals, both tests use 200 points. which is most regular?
if you want to use the 2nd code, it's not finished, it writes 2 superimposed sunflowers, the second winds back in;)
same with 400 dots:

TAGS: plot equally spaced dots points on a spiral

Nice Links with PHI related mathematitians that do amazing things:

http://linuxgazette.net/133/luana.html

this guys page.
http://richsunproductions.info/vsfx705/modelingsuite.html
HOLY COW!!!

nice maths pics of phi toruses
https://www.google.fr/search?q=phi+spiral+on+different+shapes&espv=210&es_sm=93&source=lnms&tbm=isch&sa=X&ei=WmbDUuvACKG47Aa4wIGoCg&ved=0CAkQ_AUoAQ&biw=855&bih=547&dpr=2#es_sm=93&espv=210&q=phi+spiral+on+torus&tbm=isch

code for making geodesic domes and mesh
http://www.opengl.org.ru/docs/pg/0208.html
GTS triangulated surface GNU library:
http://gts.sourceforge.net/

Marching Cubes tricks-semi-advanced Info

Some speed optimisation and accuracy considerations for marching cubes:

it's amazing how brief and effective a simple implementation of marching cubes is. only about 100 lines apart from the tables, so easy to read! It just calculates an equation on points, checks the values between points, for all edges of a cube, and the data table returns what triangles that corresponds to. it's literally 2 or 3 loops and some lists of points and lines and a data table.

If you have a basic implementation of marching cubes, you will find that each triangle is separate from each other and has its own vertices, so any mesh with 10,000 triangles will represent 30,000 vertices. a slightly optimised code would produce about 11,000 vertices instead.

Another consideration is that the simple versions calculate 12 edges for each cube, and when you add all the cubes together, it's about 4 times more edges than you really need to process.

So- to divide that part of the code processing by a factor of 4, you should use only the 3 edges of the cube on the front lower left corner, March through all the cubes and store all their values in an array, and then you will have all the edges by doing only 3 edges  instead of 12.

to read edges from the new array, every time you have the cube and need to send 12 of them to the triangles data table,you simply get the right array values for the cubes adjacent.

to calculate the points in the 1st place, from which the edge-ISOsurface intersection values are assessed, most marching cubes just walk through all the points and put them in an array.

Some marching cubes also do octree segmentation divisions of the space and only check the points and edges inside quadrants of the space which clearly contain the surface., and areas that are far from the ISO level are thrown out.

You can also just not bother to do any edges and cubes and marching, for any cubes of which 1 point is really far from the ISO value. get the 1st cube corner, check it's value, and leave it out if it's far away from the surface. you can even rewrite all the points , as they are calculated at 1st, that are far from the ISO, to a specific value so that all the cubes to be left out have that specific value on any of their points.


Here's a little trick about snapping very small triangles and throwing them out. At the linear interpolation stage of the edges, just make points are very close to cube corners equals to keep corners like as explained in the Snap MC implementation-this literally took 2 lines to change the triangles, and another 3 lines to omit triangles that are flattened.

Another consideration is

Mesh generators, videos, etc

Here's a page for different kinds of mesh generators similar to marching cubes.

here's an awesome video, original morphologies:


This one is pretty good it does some biped / quadruped meshes with bone structure stuff. if there was a neural net code for U3D they could make things that adapt to their environment.


speaking of neural net evolving artificial organisms, this is one of the cooler ones


some complete game systems of this kind will appear once all the tools are around to put them together fast. having studied animal biomechanics from centipedes to birds, its fair to say that nature doesnt waste time evolving entire patterns of movement from random jerks, it adds together toolsets of preprogrammed neural behaviour like sinusoidal leg movement that exist as dormant dna since the pre cambrian times of the trilobites etc.  funny to think that your skull is an old fish head that has been extended for other purposes. oh dam... going on divergeant topic... back to mesh

mesh gen of liquid mechanics... amazing work
theres alot of info about delauney mesh gens but i thought that delauney mesh are abit chaotic, it seems wiser to find ways to make points and triangulate them by your own experiments than copy stuff like delauney algorythms.

Trilateration of Normals for IsoSurface 3D meshes

Edit-
So I have managed a nice fast script that makes perfect normals, based on the shape formula rather than the mesh.

it can update a 6500 vertex mesh 58 times per second, pretty fast, if you need the code im around.

The rest of the posts just goes through the total puzzlement I went through to figure out the above solution, and in the end of the following solutions were kind of nonsense.

I figured that Trilateration , same as they use with GPS, would be good for surmising the exact normal position. apart from the fact we are missing the exact iso value that should exist at the normal point, as well as position. if you're really hard in maths, you can try that, it's a simple formula but it needs to be derived properly. Trying to think of triangles on and within spheres screws with your head!

Afterwards, I decided to draw  3 points very close to the vertex, measure the difference in between iso levels at the 3 points, and seeing as we can measure the precise iso level that exists at the vertex made by the marching cubes, we can prolong the 3 points as 2 segments in a straight line up to where they would meet the exact iso level of the vertex , and have the exact plane of the iso in close proximity to the vertex.

I coded it fine except it's buggy I don't know how to finish the code.
Here is a picture to show the general idea, it's basically sending out 3 points as feelers close to the vertex and prolonging the points relative to each other's value so that they equals the vertex value. that will give you 2 points coplanar to the vertex on the same iso that you make a normal from.

Its taking too long to program these things, forget both of those methods for now, I am going to do a simple solution, Which involves sampling 3 points on a small sphere surrounding vertex, taking the highest ISO value, then sampling 3 more points next to it , in a smaller radius, and then 3 more in a smaller radius, which should narrow it down to about 1/10000 in about 20 cycles, I will see if I can use a RotateAround method for it. After some thinking the best tools for that would be quaternion.aroundaxis (something) and vector3.slerp, in case one day you find yourself doing a spherical point scanner for something!

Here is a brief code for highlighting normals in unity, you have to switch to scene view to see them :
highlight normals:


#pragma strict

function Update () {

    var mesh : Mesh = GetComponent(MeshFilter).mesh;
    var vertices : Vector3[]  = mesh.vertices;
var normals : Vector3[]  = mesh.normals;

    for (var i = 0 ; i < vertices.length; i++){

vertices[i] =  transform.TransformPoint(vertices[i] );

    Debug.DrawLine (vertices[i], vertices[i] + (normals[i] * 0.1), Color.red);
}

}

box projection of textures on procedural tunnels

So the last 3 days I did box projection texture mapping on some curvaceous abstract procedural shapes made with marching cubes.

Perlin noise tunnels with box projection UVs

at the start I had 3 lines of code that puts the 3 planes of the box X/Y/Z onto any rounded surface and that was easy, the tricky thing was finding how to calculate the joining triangles in between the planes

moral of the story is to definitely make pictures of the triangles that you are editing and not just launch off into some formula, and to have some good mesh troubleshooting tools so you can see within unity the triangles stats by clicking on each triangle.

Wiki says that there are algorithms for making cubic projection seamless but you will be hard pressed to find some papers and posts on that topic.

Buy the UV cubic remapping code for $5 if you want! it is in actionscript/JS and it is pretty straightforwards so you can adapt it to C etc. You will have to have some mesh to apply it to!

Unity actually can return the 3 corners of the triangle that you click on and all the information about them which is extremely useful and handy code here it is, adapt it for your purpose.

       

//#pragma strict
var cubicobject : GameObject;
// Attach this script to a camera and it will
// draw a debug line triangle triangle
// at the triangle where you place the mouse.
function Update () {
    // Only if we hit something, do we continue
    var hit : RaycastHit;
    if (Physics.Raycast (camera.ScreenPointToRay(Input.mousePosition), hit)&&Input.GetMouseButtonDown(0)){

 //var cubicscript = cubicobject.GetComponent(otherscript);
 //var facing :int[] = cubicscript.aspect;//use this to get any information is from other scripts
 
    // Just in case, also make sure the collider also has a renderer
    // material and texture
  var meshCollider = hit.collider as MeshCollider;
  if (meshCollider == null || meshCollider.sharedMesh == null)
   return;

  var mesh : Mesh = meshCollider.sharedMesh;
  var vertices = mesh.vertices;
  var triangles = mesh.triangles;
  var uvs = mesh.uv;
  
  var t0 = hit.triangleIndex * 3 + 0;
  var t1 = hit.triangleIndex * 3 + 1;    
  var t2 = hit.triangleIndex * 3 + 2;   
  
  // Extract local space vertices that were hit
  var p0 = vertices[triangles[t0]];
  var p1 = vertices[triangles[t1]];    
  var p2 = vertices[triangles[t2]];   
  
  var u0 = uvs[triangles[t0]];
  var u1 = uvs[triangles[t1]];    
  var u2 = uvs[triangles[t2]];  
   
  Debug.Log(   " IND1   "+ triangles[t0] + " IND2   "+ triangles[t1] +" IND3   "+ triangles[t2]  );  
  Debug.Log(   " HIT1   "+ p0*100000 + " HIT2   "+ p1* 100000 +" HIT3   "+ p2*100000  );
  Debug.Log(   " UVS1   "+ u0*100000 + " UVS2   "+ u1*100000 +" UVS3   "+ u2*100000  );
    
  // Transform local space vertices to world space
  var hitTransform : Transform = hit.collider.transform;
  p0 = hitTransform.TransformPoint(p0);
  p1 = hitTransform.TransformPoint(p1);
  p2 = hitTransform.TransformPoint(p2);

  // Display with Debug.DrawLine
  Debug.DrawLine(p0, p1,Color.green, 2, false);
  Debug.DrawLine(p1, p2,Color.green, 2, false);
  Debug.DrawLine(p2, p0,Color.green, 2, false);
  
  
 }
}

       
 

The final step with these tunnels is figure out how to calculate normals relative to each of vertex, based not on the mesh itself, but the curvy Perlin noise formula underlying it.

In case you ever wondered, This is what the normals look like that are generated from vertex positions in the program:

Obviously, some normals that are close together point against each other creating shadow boundaries.(This is a blocky cave using triangles over 3 m long which doesn't look very natural!)

The nicest way to make normals from this kind of blob shape,would be to create an equivalent blog slightly larger, for example with the boundary equals to 1.01, and then find the closest point from a vertex to the theoretical surface. For that I figure you would distribute 50 points onto a quadrant of the surface closest to the vertex and take the closest one. that's the mathematically nicest way to do it.

Perhaps I will try less head scratching methods, for example just taking the vertex and normal arrays, and averaging out the normals that are close to each other, with a median or a weighted average.

here's the code that will show you the normals-(in the scene view only)-using debug.line


for(i=0;i<vertex_number;i++) {                                                                                                              
Debug.DrawLine (object_size*vertices[i],object_size*vertices[i]+normals[i], Color.red);}                      

the funny thing is-I don't know why I am making these tunnels, it wasn't the plan at all. They are pretty and I wanted to make them nice, sure, but originally my mission was to make a shape generator that does literally millions of colourful caricature shapes and patterns, so I can generate intriguing, jolly, and pretty meshes to put in my games by the bucket load and make infinite landscapes full of things to explore. but if I can just figure these normals out so I can make smooth tunnels, then I will have a truly awesome tunnel generator for myself and others.