Logo by Maya - Contribute your own Logo!

END OF AN ERA, FRACTALFORUMS.COM IS CONTINUED ON FRACTALFORUMS.ORG

it was a great time but no longer maintainable by c.Kleinhuis contact him for any data retrieval,
thanks and see you perhaps in 10 years again

this forum will stay online for reference
News: Visit us on facebook
 
*
Welcome, Guest. Please login or register. March 28, 2024, 02:31:46 PM


Login with username, password and session length


The All New FractalForums is now in Public Beta Testing! Visit FractalForums.org and check it out!


Pages: [1]   Go Down
  Print  
Share this topic on DiggShare this topic on FacebookShare this topic on GoogleShare this topic on RedditShare this topic on StumbleUponShare this topic on Twitter
Author Topic: Convert a Distance Estimate to a Mesh  (Read 7861 times)
Description: Software to turn any distance estimate into a complete mesh of triangles ;)
0 Members and 1 Guest are viewing this topic.
eiffie
Guest
« on: October 04, 2011, 05:32:39 PM »

I had a need to create a simple mandelbulb mesh so I made an app to shoot rays from a bounding box to the origin and deform the box to the shape of the mandelbulb. It worked "ok" so I added user scripting so any distance estimation function could be used. Attached is the .NET executable and project source (only 65k!) This certainly isn't an optimal mesh and lots of geometry is missed (occluded from the ray cast) but it served the purpose I had. If anyone has ideas on an algorithm to fully capture a fractal as a mesh I'd love to hear it!
 UPDATE - Thanks Fractower for the algorithm! The attachment now converts the full geometry.
 UPDATE 2 - Now with texture creation and .obj export.


* FractalMesh2.jpg (193.8 KB, 800x800 - viewed 660 times.)
* FractalMesh1_0_0_2.zip (68.76 KB - downloaded 289 times.)
« Last Edit: October 13, 2011, 11:38:19 PM by eiffie, Reason: updating attachments » Logged
DarkBeam
Global Moderator
Fractal Senior
******
Posts: 2512


Fragments of the fractal -like the tip of it


« Reply #1 on: October 04, 2011, 06:16:30 PM »

Thanks a lot for sharing. A Beer Cup A Beer Cup A Beer Cup A Beer Cup cheesy kiss angel
Logged

No sweat, guardian of wisdom!
fractower
Iterator
*
Posts: 173


« Reply #2 on: October 04, 2011, 06:59:40 PM »

I have used the marching cube algorithm to triangulate the surface of a bulb. It solves the undercut and hole problem. I was lazy so I populated a 3D array with escape times then did the surface extraction. This was very slow and limited me to relative a low res grid. It might be nice to use your method to produce seed points then use a 3D paint algorithm to extract the values needed to do the triangulation. This would eliminate the need for the scaler array and address isolated part problem associated with the 3D paint algorithm.
Logged
eiffie
Guest
« Reply #3 on: October 04, 2011, 07:47:29 PM »

Thanks for the ideas fractower. I will learn more about these methods.
Logged
fractower
Iterator
*
Posts: 173


« Reply #4 on: October 04, 2011, 07:55:00 PM »

Don't learn. Just steal. I used Cory Gene Bloyd's code posted below.

http://paulbourke.net/geometry/polygonise/
Logged
eiffie
Guest
« Reply #5 on: October 08, 2011, 05:41:52 PM »

Thanks fractower, just what I was looking for. I avoided the memory issue by just scanning 2 planes of data at a time for the calculations but now I need a machine that can display 10s of millions of polys sad Still a pretty fun toy. The original post has been updated with a new attachment.
Logged
fractower
Iterator
*
Posts: 173


« Reply #6 on: October 09, 2011, 12:18:43 AM »

That was fast. Good idea about using 2 planes.

One problem with this implementation of marching cube is that it uses  linear interpolation to decide where to put the vertices of a triangle. For most applications this is fine, but the boundary of a fractal is very non-linear. I have not graphed it my self, but I suspect looks like 1/r. This pushes the vertices closer to the lower side which cause shading operations that use normals to look funny (specular flare etc). If you notice this and it bothers you, it can be solved by replacing the linear step with a better sampling algorithm.

The 10s millions of t
Logged
fractower
Iterator
*
Posts: 173


« Reply #7 on: October 10, 2011, 08:33:14 AM »

Let me try that again.

The 10s millions of polys is a problem. Short of waiting a couple of years for technology to catch up, you might consider starting with a low res mesh and use feature extraction for the interesting parts. A lot of work has been done in the medical imaging field on this problem. A simple and direct approach is a 3D paint algorithm. The 3D paint algorithm will automatically grab only connected regions. This would work well for the Mandelbox with its many isolated parts. The other application could be patch enhancement. Imagine pointing at a patch you would like to see in better detail. The paint algorithm could be used to grab 100K smaller triangles centered on that spot.

3D paint is not to complicated. It consists three main parts: a painter function, an ordered to_do_list, and a bit per cube to indicate scheduled_or_done. Since the walking cube algorithm operates on cubes of 8 mesh points, it is useful to think in terms of cubes.

The painter starts in a cube that is cut by the iso-surface. The painter calculates (paints) the triangles. The painter then looks at his 6 neighbors. Any neighbor who shares a triangle edge and has not been scheduled_or_done gets added to the to_do_list and marked as scheduled_or_done. He then either clones himself to work on the to_do_list or he does it himself.

This is an ideal application for recursion because the to_do_list and scheduled_or_done is handled on the stack by the magic of the stack programming model. Unfortunately recursion uses a LIFO to_do_list. This tends to paint the furthermost cubes first which does not work for patch extraction. A FIFO (First in first out) to_do_list will then to paint closest points first.  The following pseudo code captures the basic algorithm.

Code:
// add the starting point to the to_do_list and mark scheduled_or_done.
to_do_list.add(start_cube);
scheduled_or_done.add(start_cube);

// Do the painting job. Add the triangles to the mesh.
cube.paint();

// The Painter lives here.
while(cube = to_do_list.next()) {
    for(n =0; n < 6; n++){
        if( (cube.shares_edge[n])  && (scheduled_or_done.val[cube.neighbor[n]]){
            to_do_list.add(cube.neighbor[n]);
            scheduled_or_done.add(cube.neighbor[n]);
        }
    }
}
   

The to_do_list object is a FIFO with add and next functions. The next function returns void when it is empty. It only needs to include the growing boundary of cubes so it will be limited to a few thousand at most.

The scheduled_or_done is more complex since in general it needs a bit per possible cube (mesh point). A hash of some kind is likely a better idea. The entries of a simple hash will be on the order of the number of triangles. With a little more storage it is possible to remove painted cubes which can no longer be scheduled (for geometric reasons). When all the children cubes that a parent cube added to the to_do_list are done, then no cube that it shares a wall with will be evaluated again. This list will be about twice the size of the to_do_list.

The patch will tend to grow in such a way to minimize the taxi cab distance from the start_cube.

Fractower

« Last Edit: October 10, 2011, 08:37:39 AM by fractower » Logged
lycium
Fractal Supremo
*****
Posts: 1158



WWW
« Reply #8 on: October 10, 2011, 06:48:01 PM »

10s of millions of polygons are no problem at all if you pre-process your mesh and use occlusion culling or ray tracing.
Logged

eiffie
Guest
« Reply #9 on: October 11, 2011, 05:22:34 PM »

Great info! I was already debating reducing the mesh during or after creation.

Update - I downloaded MeshLab (free) and seeing how many face and vertex reduction functions they have I realize there is nothing I'm going to add to that.  Instead I added texture generation with a little built-in raytracer.
« Last Edit: October 13, 2011, 11:44:00 PM by eiffie » Logged
Pages: [1]   Go Down
  Print  
 
Jump to:  

Related Topics
Subject Started by Replies Views Last post
A Mandelbox distance estimate formula 3D Fractal Generation « 1 2 3 » JosLeys 32 79387 Last post September 07, 2011, 02:38:02 PM
by knighty
Need help to convert (ABS( 1.0 - SQRT(1-(4*c)) ) to C Programming ker2x 9 850 Last post September 20, 2010, 05:31:16 PM
by Rrrola
Using the Jacobian to estimate distance Programming TruthSerum 7 6981 Last post July 06, 2014, 02:39:12 AM
by David Makin
spotty interior distance estimate for Julia sets Mandelbrot & Julia Set claude 5 4061 Last post February 21, 2015, 05:50:58 PM
by Adam Majewski
Easier to convert to .obj feature request cyseal 11 3078 Last post December 10, 2015, 12:06:16 AM
by thargor6

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines

Valid XHTML 1.0! Valid CSS! Dilber MC Theme by HarzeM
Page created in 0.252 seconds with 27 queries. (Pretty URLs adds 0.034s, 2q)