simple intersection

[alexas]

I am not sure if it is really a programming question, but I am a little desperate so maybe someone will see some obvious mistake and help me. I am generating the cuboids, and checking their intersection as if they were spheres.

So I have the following functions that were tested and give the correct results of the center of the the all cubes including the newly generated cube. My condition is the following:

  if ((mrad + irad)*(mrad + irad) > (rx * rx + ry * ry + rz * rz)) return true;

where mrad, irad are the radius of the cuboid(as spheres), rx,ry,rz - the difference in the distance between their center points. So it should be fairly obvious : if the distance between previous and newly generated cuboid centers is greater than the sum of their radius's, they must not intersect, and vice versa. However, it works only sometimes - I have no idea why. 7 out of 10 times it gets in the infinity loop, meaning that no possible cuboid can be generated which would not intersect with previous - which is nonsense. If it is needed, I can upload all the code, yet as I said, the functions which give the coordinates are checked and works ok. So I suspect that I am missing something in the condition itself.

[Ganado]

The line of code you posted, without more context, looks correct, if 'true' means "not intersecting" (edit: Right, my mistake, I meant intersecting, as the radii are bigger than the centers, you're right). The problem most likely is outside of that particular logic.

What I would do is make a copy of your current source code, and remove the parts of the code that aren't directly related to your current problem. Try to produce the smallest program that still demonstrates the issue you're having. Often, just by doing this, you'll start to understand the issue, but if not at least you'll have something small enough that you can simply post to the forum.

For example, figure out exactly which configuration of spheres/centers causes an issue, and write a program that just uses those problem spheres instead of some randomized loop or what-not.
Or perhaps it boils down to, "Given two existing spheres, can a third sphere be placed at a particular location without intersection?"

If you keep trying to pack spheres of some bounded, non-zero size into a constrained volume, eventually there won't be room to fit another sphere.

[jonnin]

are you sure it is an infinite loop?
or are you doing an advanced version of the unique random number mistake? That is, say you want 100 values, 0-99 but only one copy of each. The 100th one has to roll over and over until it gets a value never before seen if you try to randomly generate each one.. every time you add a cube, the next one has to randomly land in unused space which is constantly shrinking ... at some point there are places it can land a new cube, but randomly finding them may take {hours, days, years?} depending on what is going on?

[alexas]

"True" should mean that it is possibly intersecting. If the sum of the radius's is bigger than the actual distance between the centers of the cuboids(spheres), it should mean that the cuboids(spheres) possibly can intersect.

Ok so there is a code:

First, the function of the class of the cuboids which gives the radiuss:

std::tuple<float, float, float>
Rectangle3D::getGeometricalCenter() const
{
   return std::make_tuple(0.5 * _cuboid_length, 0.5*_cuboid_width, 0.5 * _cuboid_height);
}

float
Rectangle3D::getSphereRadius() const
{
    const auto ccords = Rectangle3D::getGeometricalCenter();
    const auto rx = std::get<0>(ccords);
    const auto ry = std::get<1>(ccords);
    const auto rz = std::get<2>(ccords);
    return std::sqrt(rx * rx + ry * ry + rz * rz);
}

Position calculation:

std::tuple<float, float, float>
Polymer::position(const int32_t index) const
{
    Quaternion<float> fpos(0.0f, 0.5f + _origin_x, 0.5f + _origin_y, _origin_z);
        if (index > 0)
    {
        for (int32_t i = 0; i < index; i++)
        {
            Quaternion<float> qpos(0.0f, 0.0f, 0.0f, _monomers[i].height());
                        fpos += _rotations[i] * qpos * conj(_rotations[i]);
        };
    }
     return std::make_tuple(fpos.b(), fpos.c(), fpos.d());
}

Intersection calculation:

bool
Polymer::intersecting(const Monomer& monomer, const Quaternion<float>& rotation, const int32_t index) const
{
   if (number_of_monomers() == 0) return false;
   const auto mrad = monomer.getSphereRadius();
   const auto irad = _monomers[index].getSphereRadius();
   auto mpos = position(number_of_monomers());
   Quaternion<float> qmon (0.0f, 0.0f, 0.0f, 0.5f * monomer.height());
   const auto fpos = rotation * qmon * conj(rotation);
   auto rx = std::get<0>(mpos) + fpos.b();
   auto ry = std::get<1>(mpos) + fpos.c();
   auto rz = std::get<2>(mpos) + fpos.d();
   Quaternion<float> imon (0.0f, 0.0f, 0.0f, 0.5f * _monomers[index].height());
   const auto rotpos = _rotations[index] * imon * conj(_rotations[index]);
   const auto ipos = position (index);
   rx -= rotpos.b(); ry -= rotpos.c(); rz -= rotpos.d();
   rx -= std::get<0>(ipos); ry -= std::get<1>(ipos); rz -= std::get<2>(ipos);
   if ((mrad + irad)*(mrad + irad) > (rx * rx + ry * ry + rz * rz)) return true;
   return false;
}

Adding:

void
Polymer::add(const Monomer &monomer, const Quaternion<float> &rotation)
{
    for (int32_t i = 0; i < (number_of_monomers()-1); i++)
    {
        if (intersecting(monomer,rotation, i)) return;
    }

    _monomers.push_back(monomer);
    _rotations.push_back(rotation);
}

Random generation of quaterions are really ok. If it is stuck in the infinity loop, usually it happens already after first two cuboids are generated. What it means is that first two cuboids are rotated in such positions, that it is impossible to find another position that would satisfy that condition of radius' > distance. If is not stuck, it successfully generates as much as I need, i.e. several hundred. However, some of the cuboids in the chain are sometimes still intersecting each other - which implies that intersection condition is violated

[Ganado]

The whole quaternion mathematics might be out of my league, so maybe other more knowledgeable people can reply. But I think my previous advice still applies: Create a program where two known cuboids are already generated, and the third cuboid generated is one where you think it shouldn't be intersecting, but your program thinks it is intersecting (or vice-versa) -- so that the program produces the same results every single time. Then, you can debug the logic happening there in isolation to see where expectation starts to diverge from reality.

My question as a layman is why is the discrepancy between cuboids and spheres needed? If I'm reading the code correctly, the sphere will always encompass the cuboid, right? So that means you will get "false positives" for detecting intersection (the spheres intersect but the cuboids themselves don't), if I'm understanding this correctly.

[alexas]

That the idea - it is kinda conservative approach. For me it is ok to be on the safe side. And it is because it is much easier at least theoretically calculate that. I was trying to check the possible algorithms for the cuboids specifically, but it is too hard for me to comprehend , plus it would be possible more slowly. I need to do it fast, and it is ok for me false positives(it is even better that my cuboids will be at least away from each other if they were spheres).

I tried to replicate the error and found the cases, which clearly can be seen as not intersecting cuboids , far away from each other, while the intersection function gives the wrong output. I checked the positions and it seems that values are not correct. Will keep searching

[ne555]

this is what I understood of your scenario
you have one polymer which is composed by monomers
a monomer is a rectangular prism, it knows its dimensions {length, width, height}, ¿does it know its position {x,yz}? (of the mass center)

you one to add another monomer to the polymer so you create a random rotation (¿no translation?)
if it intersects the polymer, the insertion fails, so you generate another rotation.


now, your code
in `Polymer::position()' you have Quaternion<float> fpos(0.0f, 0.5f + _origin_x, 0.5f + _origin_y, _origin_z)
¿why the 0.5 offset? ¿why only on x and y and not in z?

it seems that this calculates the position of each monomer in the polymer
you move m[i].h in direction d[i] ¿does this give you the center of the monomer?
but then the distance between m[i].center and m[i-1].center will only be m[i].h, ¿shouldn't be (m[i].h + m[i-1].h)/2?


in `Polymer::intersecting()' there are a lot of things happening, I'll suggest you to explode that function
first, you get the position of the last monomer on the chain, and you add the new candidate but here you move only m.h/2, ¿why only half?
(you do this exact same computation for each iteration of the loop)

then you calculate the position of m[i], and move it according to its rotation ipos+rpos (¿?)
don't understand, ¿position() don't give you the position? ¿you need another offset?

//let's say that each monomer knows the position of its center
bool
intersecting(const Monomer& a, const Monomer& b){ //note, no mention of polymer
	auto distance = a.center - b.center;
	return norm2(distance) < a.getSphereRadius()+b.getSphereRadius();
}

bool
Polymer::add(Monomer monomer, const Quaternion<float> &rotation)
{
	double d = (monomer.height() + _monomers.back().height()) / 2;
	vector offset = rotation*d*conj(rotation);
	monomer.center = _monomers.back().center + offset;

    for (int32_t i = 0; i < (number_of_monomers()-1); i++)
    {
        if (intersecting(monomer, _monomers[i])) return false; //failure
    }

    _monomers.push_back(monomer);
    _rotations.push_back(rotation);
	return true;
}

for testing, make all the monomers cubes of the same size
paint different the last inserted and candidate
and perhaps limit to the plane {x,y} (no movement on z)


> it gets in the infinity loop, meaning that no possible cuboid can be
> generated which would not intersect with previous - which is nonsense
¿why is nonsense? if the chain folded on itself (like a spiral) you may have no space to continue

[alexas]

Yes, now I see some inherent limits when treating cuboids as spheres..it seems that there exists such combination of two previous cuboids, that it is impossible to find the third cuboid rotation in which it would not intersect both of the previous cuboids.