News: Check out the originating "3d Mandelbulb" thread here
 
*
Welcome, Guest. Please login or register. November 20, 2014, 11:39:13 PM


Login with username, password and session length



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 3243 times)
Description: Software to turn any distance estimate into a complete mesh of triangles ;)
0 Members and 1 Guest are viewing this topic.
eiffie
Global Moderator
Fractal Bachius
******
Posts: 507


« 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 165 times.)
* FractalMesh1_0_0_2.zip (68.76 KB - downloaded 99 times.)
« Last Edit: October 13, 2011, 11:38:19 PM by eiffie, Reason: updating attachments » Logged
DarkBeam
Global Moderator
Fractal Senior
******
Posts: 1666


The spaghetti formula coder


« 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

Formulas are never too much (?)

fractower
Iterator
*
Posts: 169


« 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
Global Moderator
Fractal Bachius
******
Posts: 507


« 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: 169


« 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
Global Moderator
Fractal Bachius
******
Posts: 507


« 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: 169


« 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: 169


« 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
eiffie
Global Moderator
Fractal Bachius
******
Posts: 507


« Reply #8 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
Better DE estimate using orbit traps Mandelbulb Implementation « 1 2 3 » knighty 44 6386 Last post February 16, 2010, 02:29:32 PM
by hobold
A Mandelbox distance estimate formula 3D Fractal Generation « 1 2 3 » JosLeys 32 16219 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 582 Last post September 20, 2010, 05:31:16 PM
by Rrrola
How do I convert a Mandelbrot to a Mandelbulb? 3D Fractal Generation Bottleneck 4 809 Last post December 03, 2011, 10:01:13 PM
by huminado
Using the Jacobian to estimate distance Programming TruthSerum 7 420 Last post July 06, 2014, 02:39:12 AM
by David Makin

Powered by MySQL Powered by PHP Powered by SMF 1.1.20 | SMF © 2013, Simple Machines

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