pouët.net

Dearest lazy-pouet,

Given the coordinates of one pixel inside the blob how do you compute a boulding box around the blob?

Uh, can you define slightly more precisely what you mean by "blob"? Are you talking about a 2D isosurface?

Flood fill from the pixel and find min and max x, y ? =)

In case of vertices it´s just what sol suggested...find the min&max of all triangle-positions, center bounding box ...minX + (maxX-minX)/2 for x and the same for y, and size of box is just (maxX-minX)/2 again...in case of a static blob (not changing any vertices this only has to be done once as an initialization-step, else every frame of course.)
In case of raymarched geometry you would need to sample at different heights for x and widths for y, then doing the same as above...if it´s a blob that changes its geometry every frame, this could get quite costy...but as you are asking for boxes already you don´t seem to need the accuracy -> i would, atleast for a demo, just use a static bounding box, covering all sizes the blob could grow to...which could be not what you need right now, but you weren´t specific enough in your question i guess...

I used bounding boxes for my textmode raymarcher, there I just defined it for each object. Like sphere with 4 units radius, please use a bounding box of 5 units.

What I'm trying to say, is that if you can define it manually with some constant values, or define it as a function of another variable (radius), you will end up with better results than trying to find it using sampling. You have more control over it, you can fine tune it and it will always be faster.

Assuming you mean the classic 1/d² metaballs… you can get a pretty rough idea even before triangulation. What's “inside” is defined by sum(1/d_i²) <= C where d_i is the distance to metaball i and C is some positive constant (in marching cubes, you search for the point where this equation reaches equality).

Now look at each metaball i in turn. What's the farthest away you could have “inside” from this point? Well, if there was only this metaball in the world, obviously you'd have a perfect sphere where d_i² = 1/C, or distance d_i = 1/sqrt(C). But there's influence from others, too. The farthest you could make that single point extend would be if all the other metaballs were exactly on top of it, so that for N metacalls, you'd have exactly N times the potential: N/d_i² <= C: This yields distance d_i = 1/sqrt(NC).

So go through each point, extend the bounding box 1/sqrt(NC) units in each direction from the center, and take the bounding box of the resulting bounding boxes. The potential function is convex, so as far as I can tell, you can't go outside this.

mu6k: Indeed. You can even have multiple, increasing precision bounds, depending on the needs. If you're doing culling for rendering-purposes, you might want to perform a cheap, very conservative check (is anything in this set of blobs potentially visible at all?), and then if that passes, you have more accurate check (what blobs in the set can affect anything on-screen). But I'd always go with the less accurate check first, and only add the more accurate if profiling data shows that more complexity is justified.

Sesse: Isn't the largest surface made not from placing all on top of each other, but rather putting the second ball on any poiny on the first points surface, and the next one on the furthest away point in the restulting surface and so on?

Sesse: Thinking at it again, that doesn't matter; as the bounding boxes for the successive points would pick that effect up. So yeah, your approach seems valid.

kusma: Yeah, I think it's right. It might be overly conservative in practice, though. E.g., if you have 640 metaballs, you'll extend the bounding box to sqrt(640) radii from each point, e.g. about 25 times. It's unlikely to be that far away.

Don't know if this helps:

http://www.angelcode.com/dev/metaballs/metaballs.html
http://www.angelcode.com/dev/metaballs/

Seems like he is working outwards from the ball center...

Take 4 pieces of paper, and push them, one from each direction, until they just touch the edge of the blob. You can now wipe the blob up with a sponge.

Thinking about it, if you want a tighter but more expensive bound, you can do quite well with something like an axis-aligned raymarch (or something like Newton's method) from each center point. (As soon as you have a bound from one box, the bound point is likely to get rejected super-fast for all the other centers, so you'll get by with rather few samples.)

@Sesse: I'm pretty sure that whatever clever trick we come up with here, Blueberry is going to come in and whip us with some clever parabola intersection trick ;)

kusma: Why do you think I started off by assuming 1/d² and not a polynomial ;-)

:)

The trick that Kusma mentions (used in Rapo Diablo and Rapo Diablo 5000) goes like this:

Use a blob shape formula of max(0, a-bd²)², where d is the distance to the blob's center and a and b are parameters defining each blob's size and strength. This gives a nice, bell-shaped potential with maximum reach of sqrt(a/b).

For a particular ray, substitute the ray equation into the blob equation to get a formula in the ray's parameter, t. It will have the form max(0, At²+Bt+C)² with A < 0.

If the inner quadratic equation never crosses zero (i.e. if B²-4AC < 0), the blob is definitely not hit by the ray, so this can be used as a quick bounding sphere intersection test. Perform this test for all blobs.

If only one blob is potentially hit by the ray, the equation for the actual intersection is (At²+Bt+C)² = P, where P is the potential threshold defining the isosurface. Move it around a bit and it becomes At²+Bt+C-sqrt(P) = 0. Solve this quadratic equation to get the exact intersection points.

If more than one blob is hit by the ray, resort to raymarching, summing the values for each potentially intersected blob at each step.

Hmmm, if this is for rendering marching cubes stuff, you could ask Google for Gernot Ziegler and HistoPyramids.

edge tracing, 2 word, from the absolute king.

.