strange artifacts of csgUnion on Two Spheres

[דור ריבלין‎]

Hi There,

Im testing out the csgUnion operation between two grids/spheres.

the psudo - procedure I was trying to perfom is the following:

Given : grid gA

(1)

 , grid gB

(2)

{

gC = gA Union gB /* gA + gB

(3)

gD = gC   \   gA /* which also is equivlent to gB - gA

(4)

gE = gC   \   gD /* gC - gD = gA + gB - (gB - gA) = gA + gB - gB + gA = gA

(5)

return gE

}

expecting to end up with sphere A as a result , yet I've ended up with some artifacts on the final grid. 

I looked into the SDF of the final grid :

(6)

and as one can tell , I think the reason for the artifact is redundant positive values on the right hand side.

now present the code and maybe anyone could help me and point out where i got it wrong :

openvdb::Vec3f Center(0.0f, 0.0f, 0.0f);
float radius = 7.0f;

float shift = 2 * radius / 3;

openvdb::Vec3f sCenter(Center.x() + shift, Center.y(), Center.z());

auto a = openvdb::tools::createLevelSetSphere<openvdb::Grid<openvdb::FloatTree>>(radius, Center, 0.1);

openvdb::tools::pruneLevelSet(a->tree());

auto b = openvdb::tools::createLevelSetSphere<openvdb::Grid<openvdb::FloatTree>>(radius, sCenter, 0.1);

openvdb::tools::pruneLevelSet(b->tree());

openvdb::FloatGrid::Ptr CenterSphere = a->deepCopy();

CenterSphere->setName("Center Sphere");

openvdb::FloatGrid::Ptr ShiftedSphere = b->deepCopy();

ShiftedSphere->setName("Shifted Sphere");

openvdb::FloatGrid::Ptr Union = openvdb::tools::csgUnionCopy<openvdb::Grid<openvdb::FloatTree>>(*a, *b);

Union->setName("Union");

openvdb::FloatGrid::Ptr iDelta = openvdb::tools::csgDifferenceCopy<openvdb::Grid<openvdb::FloatTree>>(*Union, *a);

iDelta->setName("Initial Delta");

(7)

openvdb::FloatGrid::Ptr fDelta = openvdb::tools::csgIntersectionCopy<openvdb::Grid<openvdb::FloatTree>>(*iDelta, *b);

fDelta->setName("final Delta");

(8)

openvdb::FloatGrid::Ptr pfDelta = fDelta->deepCopy();

openvdb::tools::pruneLevelSet(pfDelta->tree());

pfDelta->setName("pruned final Delta");

(9)

openvdb::FloatGrid::Ptr iUndoUnion = openvdb::tools::csgDifferenceCopy<openvdb::Grid<openvdb::FloatTree>>(*Union, *pfDelta);

iUndoUnion->setName("Undo Union");

 I've added images of the SDF and the Voxels Tree for each step of the process  showing why i've added the steps to the my psudo algorithm 
with the final result the as shown above in (6). 

any thoughts or suggestions ?

Thanks in advance.

[Ken Museth]

I haven't studied your example in detail but I'm fairly certain I know that's going on. Basically you're performing a sequence of CSG operations and a classic mistake is to forget that most such CSG operations on level sets (i.e narrow band signed distance fields, SDF) actually destroy the very nature of a level set (i.e it's no longer a SDF!). This is not an artifact of VDB, but a consequence of the fact that CSG operations on level sets are typically implemented as simple min/max voxel-level operations that totally ignore the changing topology (I can explain this in more detail if you want). So long story short the result of performing a CSG operation on two level sets is not (necessarily) a level set. So when you proceed to perform additional CSG operations you can get artifacts like the ones you're observing. The fix is pretty simple, after each CSG call openvdb::tools::levelSetRebuild which does two things - it updates the narrow-band topology as well as the signed distance values (both from the new zero-crossing produced by the CSG operation).

Cheers,

Ken

[דור ריבלין‎]

Hi Ken,

I've took out openvdb::tools::LevelSetRebuild method for a spin, it had good result, also modifing my psudo algo as follows:
{

gU* =  gA <Union> gB 

(a)

gD = gU \ gA

(b)

gU = gA <Union> gD

(c)

gE = gU \ gD

(d)

}

when I added the openvdb::tools::LevelSetRebuild  along the stages the final result is

(e)

while the result is much better its not there yet .

In addition the process of performing levelSetRebuild is expansive time-wise and memory-wise at each CSG stage,also depending on the grid dimensions , complexity and most important voxel ratio to the real world, here 0.1.

Is there a different approach handling the situation , that is better recommended.

I've looked into the topology and compMin ,compSum directions but i think i'm missing it.

adding my updated code below :

openvdb::Vec3f Center(0.0f, 0.0f, 0.0f);

float radius = 7.0f;

float shift = 2 * radius / 3;

openvdb::Vec3f sCenter(Center.x() + shift, Center.y(), Center.z());

auto a = openvdb::tools::createLevelSetSphere<openvdb::Grid<openvdb::FloatTree>>(radius, Center, 0.1);

openvdb::tools::pruneLevelSet(a->tree());

auto b = openvdb::tools::createLevelSetSphere<openvdb::Grid<openvdb::FloatTree>>(radius, sCenter, 0.1);

openvdb::tools::pruneLevelSet(b->tree());

openvdb::FloatGrid::Ptr CenterSphere = a->deepCopy();
CenterSphere->setName("Center Sphere");

openvdb::FloatGrid::Ptr ShiftedSphere = b->deepCopy();

ShiftedSphere->setName("Shifted Sphere");

openvdb::FloatGrid::Ptr tmpU = openvdb::tools::csgUnionCopy<openvdb::Grid<openvdb::FloatTree>>(*a, *b);

tmpU->setName("U'");

openvdb::FloatGrid::Ptr rtmpU = openvdb::tools::levelSetRebuild(*tmpU);

rtmpU->setName("rebuilt U'"); /* I've ditched this stage */

openvdb::FloatGrid::Ptr delta = openvdb::tools::csgDifferenceCopy<openvdb::Grid<openvdb::FloatTree>>(*tmpU, *a);

delta->setName("Delta");

openvdb::FloatGrid::Ptr rDelta = openvdb::tools::levelSetRebuild(*delta);

rDelta->setName("rebuilt Delta");

openvdb::FloatGrid::Ptr U = openvdb::tools::csgUnionCopy<openvdb::Grid<openvdb::FloatTree>>(*a, *rDelta);

U->setName("U");

openvdb::FloatGrid::Ptr Undo = openvdb::tools::csgDifferenceCopy<openvdb::Grid<openvdb::FloatTree>>(*U, *rDelta);

Undo->setName("Undo");

openvdb::FloatGrid::Ptr rUndo = openvdb::tools::levelSetRebuild(*Undo);

rUndo->setName("rebuilt Undo");

also i would not mind more elaborate explanation regarding SDF , Narrow - Bend and CSG or a reference to  good material.

thanks,
Dor

[qu...@iue.tuwien.ac.at]

also i would not mind more elaborate explanation regarding SDF , Narrow - Bend and CSG or a reference to  good material.

I would also be interested in this

regards, 

michael