Bounding box for implicit surface

In general this is hard, but you may still want to create boxes that only loosely fit (i.e. they are too large).
For the ones which have a limited range, you can guarantee that the surface fits inside the bounding box of the control points extended by the range in each direction.
For a more general case, it seems to me there may be a method of repeatedly approximating two control points with 1 point, which has an effect value such that you can guarantee it has more influence than the two did put together. By picking which points to merge, you may be to reduce it to one point with a reasonably small number.
Investigating this a bit further, it seems to be quite dificult to get a useful approximation for two control points in terms of one. It is useful for points that are close to each other compared with the surface, but that is not likely.

I''m using the basic 1/r^2 function because i need it to extend to infinity (i''m using the field values also to manage gravity in my game). So that won''t work unfortunatly .

Also i''m not just using control points, i''m also using lines, torus'' and spheres (this creates 2 surfaces a large sphere outside and a smaller sphere inside). So merging them together won''t really be feasible.

Thanks for the reply though.

Are you sure that you need 1/r2 functions ? I plan to study a new blob algo in a near future (take a look at the metaball thread). 3rd or 4th degree polynomial approximations could replace squared hyperboles with the slight difference that the field becomes exactly null beyond a certain radius of influence :

r<=R => f(r)=Polynomial(r)
r>R => f(r)=0
Also warrant that f(R)=f''(R)=0.

f(r) makes a "smooth hat shape" like _/\_ but smoothed . The resulting blob should not be very different from a blob defined with 1/r2 metaballs.

I would call them cut multivariate polynomials (CMPs) in x,y,z. You can add them since the polynomials constitute a mathematical field.

If you use CMPs. I suppose you can easilly compute the exact bounding box. First a space partition can order the spheres for instance an octree. When you evaluate the blob field at any point P={x,y,z} you first have to select only the metaballs whose spheres of influence contain P.

So here are the guidelines of my proposed algorithm :

Make a binary search for each of the 6 planes of the AABox you want to compute. Just enlist all the spheres that can collide with plane P (for instance x=x0). Compute the max field value on this plane. Try to see what in means in details. The sign of the max field value is s. Then move your plane in the direction of s or -s (depending if you seek a min or max coordinate of the box). Once it''s 0 you have your plane position (and thus for instance Box.xmin).

Now OK if you don''t want my CMPs. Since I suspect CMP or 1/r2 based blobs are very similar, if a maximum error emax between the two shapes can be evaluated, just compute the AABox of the CMP based blob and then expand it by emax.

quote:

---

Original post by Charles B
Are you sure that you need 1/r2 functions ? I plan to study a new blob algo in a near future (take a look at the metaball thread).

---

I have tried changing the field function to the "Soft Objects" field to see what happened. Its pretty similar but i ran into some problems due to the fact that i don''t only use the field for rendering the surfaces. I''m also using the field in my game to act as gravity and determine which direction is the UP direction for my camera. And as soon as i jump off away from one of the balls, i will reach a point in space where the field is 0 (which means that i float off to infinity). So i decided to stick with 1/r^2 for the time being.

I''ve just gone with the option of finding the bounding box of the individual entities, expanding them and then adding them all together. It means i end up with a bounding box that is too big in many cases, in rare cases when the entities are packed close together it may end up being too small. But its acceptable until i find something better

Could you explain a bit more in details what these fields actually mean in your code (game?) ?

Else I have tested something very interesting in the past. I found a formula to sum the forces of a 1/r2 field on a triangle. With this routine I could define a kind of collision model that works very well. Fields => smooth collisions. Maybe this could be interesting for you. The force per triangle and punctual source field costs roughly 100 cycles. I made a race demo with this single technique. However solid collisions are also required to avoid object traversal bugs.

Else if you are unsatisfied by your current solution I have two suggestions :

- once again you could alternate between the 1/r2 and Polynomial models for physics and rendering.

- else with polynomials only you could maybe add a contant gravity. It analoguous to using an ambient light for lighting equations. If G(P) is local gravity this would be continuous in space.

CPMs would be much better for performances : you don''t need to sum all the sources thanks to the radius of influence. You can cache sums of polynomials and evaluate the blob field anywhere in constant since polynomial coefficients can be added. With 1/r2 you are obliged to compute reciprocicals for each source. So if you have many sources (metaballs) ...