Random placement in an area

Kevin D.
2012-07-02
2013-06-05
  • Kevin D.
    Kevin D.
    2012-07-02

    Currently there are some scripts that allow me to distribute object 1 over the surface of object 2.  Is there a way to randomly place many copies of object 1 inside the area of object 2 rather than than the surface?

     
  • Peter Eastman
    Peter Eastman
    2012-07-03

    Do you want this for an arbitrary mesh, or a simpler shape (like a sphere or box)?

    Meshes are essentially defined by their surfaces.  That makes it much easier to distribute objects over their surfaces than over their volumes.  That doesn't mean it can't be done, though.  Could you describe what you want to do?

    Peter

     
  • Kevin D.
    Kevin D.
    2012-07-03

    I am working on a scifi video game, and I have been tasked with making a spaceship junkyard.  It's an old school vertical shooter, so the artwork only has to be viewed from above.  I have made a bunch of spaceship models and I have broken them down into pieces of junk.  Now I have to randomly place copies inside an arbitrary shape in order to create piles of junk.  Since the view is only top down, I can just use the surface of a flat shape to distribute over, but placing them inside the object would look a little better I think. 

    OK, I just tried using the surface of a flat mesh and it turned out pretty good.  I'm still curious about using the area of the shape instead, even if it is just a cube or sphere.  That is some thing I can see myself using a lot in this project.

     
  • Luke S
    Luke S
    2012-07-03

    A sphere would actually be the simplest. Generate a random location, and if its distance from the center of the sphere is greater than the radius of the sphere, throw the location away. otherwise you are good.

    A cube would be almost as simple. In fact, if the cube is arranged flat in the scene, you just have to make sure that your locations are inside the bounding box. Rotated cubes would not be that much harder.

    Cylinder too.

    As Peter said, an arbitrary mesh object would be the trickiest, but I think it can be done. Generate a location, and then draw a line from it to the edge of the bounding box. Count how many faces you pass through. If the number is odd, you are 'inside' the object. If it is even, you are outside. This method should work for meshes with stretched around, 'tenatacle-ish' shapes, and for any that have 'empty bubbles' inside. - you could get some really complex debris fields going on here, though if you are using this in a 2d game, I don't know if you can use all of it.

    I have not coded this out - might do it just as practice even if you don't need all that capability.

    Question: does all of your junk need to be completely inside the mesh, or can parts stick out a little?

    Sounds interesting to me.

    LJSAILS

     
  • Kevin D.
    Kevin D.
    2012-07-03

    Parts of the debris can definitely stick out of the mesh.  I certainly do not want things to look neat and organized.  I am also wanting the debris to be more dense in the center of the object.  Currently I am using this mesh as my surface:

    http://www.proceduraltextures.com/notblogstuff/densemesh.PNG

    This causes the density to fall off from the center.  This better simulates a pile of junk rather than some loose debris.

     
  • Luke S
    Luke S
    2012-07-04

    Ahh…. So this is more like a big pile of junk sitting on a planet surface? I was imagining a floating 'ship graveyard' - maybe this just says stuff about the kind of scifi I read.

    If so, then

    more dense in the center

    - means the pile is higher here, and things are overlapping more?

    Should be pretty simple - I might have a basic version tomorrow. (no guarantees)

    OTOH, I'm not sure that the results will really be that much better than what you are doing - Is there anything about your current approach that gives you results that you don't like?

    ljsails

     
  • Kevin D.
    Kevin D.
    2012-07-04

    I want things to overlap like crazy in the center.  This is my result using my flat mesh:
    http://www.proceduraltextures.com/zorksox/wp-content/uploads/2012/07/junkyard.png

    It looks exactly like I want it to….from above.  At any other angle you start to notice that the junk pile is flat.  On the other hand, if those junk piles were deep like actual piles, there would be more objects in the scene and it would look the same.  So maybe I am doing it the right way for this project.

    Don't get me wrong.  I would make much use of the script you are writing, I just may not use it for this.

     
  • Peter Eastman
    Peter Eastman
    2012-07-04

    That looks really cool.  I want to see this game when it's done!

    Peter

     
  • Kevin D.
    Kevin D.
    2012-07-04

    Sure thing.  You'll only have to wait a year or so :)

     
  • Luke S
    Luke S
    2012-07-22

    Ok, sorry this is so late.

    Here is a (somewhat) working volume distribute script.

    Limits: only primitives(cube, sphere, cylinder)  work properly. Trimesh has bugs. (it runs - slowly - but items get placed outside the mesh.)

    I think that the basic idea behind the Trimesh algorithm is sound, but there is a flaw or two in my implementation. If I missed something obvious, please point it out.

    Any other thoughts/feedback are also welcomed.

    /*
    <?xml version='1.0' standalone='yes' ?>
    <!--  xml header for scripts and plugin manager --> 
    <script>
        <name>Volume Distribute</name>
        <author>ljsails (ljsails@users.sourceforge.net)</author>
        <version>0.1</version>
        <date>07/06/2012</date>
    <description>
    This script produces a series of copies of a selected object and distributes them randomly throughout the volume of another object.
    If the object is not a primitive solid, or cannot be transformed into a (closed) triangle mesh object, the script returns without doing anything.
    </description>
    <comments>
    </comments>
    </script>
    */
    theScene = window.getScene();
    numObjects = theScene.getNumObjects();
    containerChoices = new BList();
    distribChoices = new BList();
    randomGen = new Random(0);
    //Pick a random position within the object's bounding box
    Vec3 randomPosition(BoundingBox box){
        xRange = box.maxx - box.minx;
        yRange = box.maxy - box.miny;
        zRange = box.maxz - box.minz;
        x = randomGen.nextDouble() * xRange + box.minx;
        y = randomGen.nextDouble() * yRange + box.miny;
        z = randomGen.nextDouble() * zRange + box.minz;
        return new Vec3(x, y, z); 
    }
    //choose a random rotation. Vec3 used to carry data. (Is there a better way? OTOH, Sphere does the same thing!)
    Vec3 randomRotation(double range){
        x = randomGen.nextDouble() * range * 360;
        y = randomGen.nextDouble() * range * 360;
        z = randomGen.nextDouble() * range * 360;
        return new Vec3(x, y, z);
    }
    //is the pos on the same side of the line ab as third? Failure point! this does not work!
    boolean sameSide(Vec3 pos, Vec3 third, Vec3 a, Vec3 b){
        cp1 = b.minus(a).cross(pos.minus(a));
        cp2 = b.minus(a).cross(third.minus(a));
        result = (cp1.dot(cp2) >= 0);
        return result;
    }
    //is the point in the 2d triangle abc?
    boolean inTriangle(Vec3 pos, Vec3 a, Vec3 b, Vec3 c){
        //return (sameSide(pos, a, b, c) && sameSide(pos , b, a, c) && sameSide(pos, c, a, b));
        //above method buggy, alternative used below.
        v0 = c.minus(a);
        v1 = b.minus(a);
        v2 = pos.minus(a);
        
        // Compute dot products
        dot00 = v0.dot(v0);
        dot01 = v0.dot(v1);
        dot02 = v0.dot(v2);
        dot11 = v1.dot(v1);
        dot12 = v1.dot(v2);
        
        // Compute barycentric coordinates
        invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
        u = (dot11 * dot02 - dot01 * dot12) * invDenom;
        v = (dot00 * dot12 - dot01 * dot02) * invDenom;
        
        // Check if point is in triangle
        return (u >= 0) && (v >= 0) && (u + v < 1);
    }
    //returns how far pos is in front of the facet v1,v2,v3.
    double relativePlaneNormal(Vec3 pos, Vec3 v1, Vec3 v2, Vec3 v3){
        s1 = v2.minus(v1); s1.normalize();
        s2 = v3.minus(v1); s2.normalize();
        normal = s1.cross(s2);
      if (normal.z < 0.0) normal.scale(-1.0);
        return pos.dot(normal);
    }
    //first pass to disqualify most triangles - any triangles that are
    //completely behind or to one side of the test position are discarded.
    boolean isInBlockingRange(Vec3 pos, Vec3 v1, Vec3 v2, Vec3 v3){
        xAxis = ( (v1.x > pos.x && v2.x > pos.x && v3.x > pos.x) || (v1.x < pos.x && v2.x < pos.x && v3.x < pos.x) );
        yAxis = ( (v1.y > pos.y && v2.y > pos.y && v3.y > pos.y) || (v1.y < pos.y && v2.y < pos.y && v3.y < pos.y) );
        zAxis = (v1.z < pos.z && v2.z < pos.z && v3.z < pos.z);
        return !(xAxis || yAxis || zAxis);
    }
            
    //is the given position inside a Sphere?
    boolean isSphereLegal(Vec3 pos, Object3D obj){
        rad = obj.getRadii();
        aSq = rad.x * rad.x; bSq = rad.y * rad.y; cSq = rad.z * rad.z;
        xSq = pos.x * pos.x; ySq = pos.y * pos.y; zSq = pos.z * pos.z;
        res = (xSq / aSq) + (ySq / bSq) + (zSq / cSq);
        if (res <= 1.0) {
            return true;
        } else {
            return false;
        }
    }
    //is the given position inside a Cylinder?
    boolean isCylinderLegal(Vec3 pos, Object3D obj){
        hRat = (pos.y + (obj.getPropertyValue(3) / 2)) / obj.getPropertyValue(3);
        a = (obj.getPropertyValue(0) * (1 - hRat)) + (obj.getPropertyValue(0) * obj.getPropertyValue(2) * hRat);
        b = (obj.getPropertyValue(1) * (1 - hRat)) + (obj.getPropertyValue(1) * obj.getPropertyValue(2) * hRat);
        xSq = pos.x * pos.x; zSq = pos.z * pos.z;
        aSq = a*a; bSq = b*b;
        res = (xSq / aSq) + (zSq / bSq);
        if (res <= 1.0) {
            return true;
        } else {
            return false;
        }
    }
    //is given position inside an arbitrary trimesh object?
    boolean isTriLegal(Vec3 pos, Object3D obj){
        tris = obj.getFaces();
        verts = obj.getVertexPositions();
    
        count = 0;
    
        for (int i = 0; i < tris.length; i++) {
            v1 = verts[tris[i].v1]; v2 = verts[tris[i].v2]; v3 = verts[tris[i].v3];
            //I'm counting on shortcut evaluation here. 
            if (isInBlockingRange(pos, v1, v2, v3) && inTriangle(pos, v1, v2, v3) && relativePlaneNormal(pos, v1, v2, v3) > 0) count++;     
        }
    
          //if you must pass through an odd number of faces, you are inside the object.
        return (count%2 == 1);
    }
    //generally, is a random position within bounds?
    boolean isLegal(Vec3 pos, int type, Object3D obj){
        switch (type) {
            case 1: return true; // if the bounding object is a cube, all generated positions are valid
            case 2: return isSphereLegal(pos, obj);
            case 3: return isCylinderLegal(pos, obj);
            case 4: return isTriLegal(pos, obj);
        }
    }
    //Main Script Body///
    //fill widgets with object choices from the scene. TODO: block cameras and lights
    for (i = 0; i < numObjects; i++){
        containerChoices.add(theScene.getObject(i).name);
        distribChoices.add(theScene.getObject(i).name);
        }
    //other input fields, and create the dialog.    
    numCopies = new ValueField(10, ValueField.POSITIVE+ValueField.INTEGER);
    rotationRange = new ValueField(1.0,ValueField.NONNEGATIVE);
    dlg = new ComponentsDialog(window, "Select Parameters",
         new Widget [] {new BScrollPane(containerChoices, BScrollPane.SCROLLBAR_AS_NEEDED, BScrollPane.SCROLLBAR_AS_NEEDED), 
         new BScrollPane(distribChoices, BScrollPane.SCROLLBAR_AS_NEEDED, BScrollPane.SCROLLBAR_AS_NEEDED), numCopies, rotationRange},
          new String [] {"Volume","Fill With","Number of Copies", "Rotation Variation"});
          
    if (!dlg.clickedOk()) return;
    if (containerChoices.getSelectedIndex() == distribChoices.getSelectedIndex()) {
        new MessageDialog(window, "The object cannot be distributed through its own volume!");
        return;
    }
    copies = (int)numCopies.getValue();
    rotation = rotationRange.getValue();
    container = theScene.getObject(containerChoices.getSelectedIndex());
    distributable = theScene.getObject(distribChoices.getSelectedIndex());
    obj = container.getObject();
    dist = distributable.getObject();
    type = 0;
    if (obj instanceof Cube) {
        type = 1;
    } else if (obj instanceof Sphere) {
        type = 2;
    } else if (obj instanceof Cylinder) {
        type = 3;
    } else if (obj instanceof TriangleMesh && obj.isClosed()) {
        type = 4; //Don't run conversion on something that is already a trimesh.
    } else if (obj.canConvertToTriangleMesh() != Object3d.CANT_CONVERT){
        obj = obj.convertToTriangleMesh(theScene.getInteractiveSurfaceArea());
        if (obj.isClosed()) {
            type = 4;
        }
    } 
    if (type == 0) return; //script crashes if we can't process the container - better than running the main loop with no effect.
    
    while (copies > 0) {
        pos = randomPosition(obj.getBounds());
        if (isLegal(pos, type, obj)) {
            rot = randomRotation(rotation);
            distCopy = new ObjectInfo(dist, new CoordinateSystem(container.coords.fromLocal().times(pos), rot.x, rot.y, rot.z), "Duplicate of " + distributable.name);
            container.addChild(distCopy, 0);
            window.addObject(distCopy, null);
            copies --;
        }
    }
    window.rebuildItemList();
    

    ljsails

     
  • Kevin D.
    Kevin D.
    2012-07-29

    If I copy and paste this into notepad or the script editor, there are no line breaks.

    Like so:

    /* <?xml version='1.0' standalone='yes' ?> <!- xml header for scripts and plugin manager -> <script> <name>Volume Distribute</name> <author>ljsails (ljsails@users.sourceforge.net)</author> <version>0.1</version> <date>07/06/2012</date> <description> This script produces a series of copies of a selected object and distributes them randomly throughout the volume of another object. If the object is not a primitive solid, or cannot be transformed into a (closed) triangle mesh object, the script returns without doing anything. </description> <comments> </comments> </script> */ theScene = window.getScene(); numObjects = theScene.getNumObjects(); containerChoices = new BList(); distribChoices = new BList(); randomGen = new Random(0); //Pick a random position within the object's bounding box Vec3 randomPosition(BoundingBox box){ xRange = box.maxx - box.minx; yRange = box.maxy - box.miny; zRange = box.maxz - box.minz; x = randomGen.nextDouble() * xRange + box.minx; y = randomGen.nextDouble() * yRange + box.miny; z = randomGen.nextDouble() * zRange + box.minz; return new Vec3(x, y, z); } //choose a random rotation. Vec3 used to carry data. (Is there a better way? OTOH, Sphere does the same thing!) Vec3 randomRotation(double range){ x = randomGen.nextDouble() * range * 360; y = randomGen.nextDouble() * range * 360; z = randomGen.nextDouble() * range * 360; return new Vec3(x, y, z); } //is the pos on the same side of the line ab as third? Failure point! this does not work! boolean sameSide(Vec3 pos, Vec3 third, Vec3 a, Vec3 b){ cp1 = b.minus(a).cross(pos.minus(a)); cp2 = b.minus(a).cross(third.minus(a)); result = (cp1.dot(cp2) >= 0); return result; } //is the point in the 2d triangle abc? boolean inTriangle(Vec3 pos, Vec3 a, Vec3 b, Vec3 c){ //return (sameSide(pos, a, b, c) && sameSide(pos , b, a, c) && sameSide(pos, c, a, b)); //above method buggy, alternative used below. v0 = c.minus(a); v1 = b.minus(a); v2 = pos.minus(a); // Compute dot products dot00 = v0.dot(v0); dot01 = v0.dot(v1); dot02 = v0.dot(v2); dot11 = v1.dot(v1); dot12 = v1.dot(v2); // Compute barycentric coordinates invDenom = 1 / (dot00 * dot11 - dot01 * dot01); u = (dot11 * dot02 - dot01 * dot12) * invDenom; v = (dot00 * dot12 - dot01 * dot02) * invDenom; // Check if point is in triangle return (u >= 0) && (v >= 0) && (u + v < 1); } //returns how far pos is in front of the facet v1,v2,v3. double relativePlaneNormal(Vec3 pos, Vec3 v1, Vec3 v2, Vec3 v3){ s1 = v2.minus(v1); s1.normalize(); s2 = v3.minus(v1); s2.normalize(); normal = s1.cross(s2); if (normal.z < 0.0) normal.scale(-1.0); return pos.dot(normal); } //first pass to disqualify most triangles - any triangles that are //completely behind or to one side of the test position are discarded. boolean isInBlockingRange(Vec3 pos, Vec3 v1, Vec3 v2, Vec3 v3){ xAxis = ( (v1.x > pos.x && v2.x > pos.x && v3.x > pos.x) || (v1.x < pos.x && v2.x < pos.x && v3.x < pos.x) ); yAxis = ( (v1.y > pos.y && v2.y > pos.y && v3.y > pos.y) || (v1.y < pos.y && v2.y < pos.y && v3.y < pos.y) ); zAxis = (v1.z < pos.z && v2.z < pos.z && v3.z < pos.z); return !(xAxis || yAxis || zAxis); } //is the given position inside a Sphere? boolean isSphereLegal(Vec3 pos, Object3D obj){ rad = obj.getRadii(); aSq = rad.x * rad.x; bSq = rad.y * rad.y; cSq = rad.z * rad.z; xSq = pos.x * pos.x; ySq = pos.y * pos.y; zSq = pos.z * pos.z; res = (xSq / aSq) + (ySq / bSq) + (zSq / cSq); if (res <= 1.0) { return true; } else { return false; } } //is the given position inside a Cylinder? boolean isCylinderLegal(Vec3 pos, Object3D obj){ hRat = (pos.y + (obj.getPropertyValue(3) / 2)) / obj.getPropertyValue(3); a = (obj.getPropertyValue(0) * (1 - hRat)) + (obj.getPropertyValue(0) * obj.getPropertyValue(2) * hRat); b = (obj.getPropertyValue(1) * (1 - hRat)) + (obj.getPropertyValue(1) * obj.getPropertyValue(2) * hRat); xSq = pos.x * pos.x; zSq = pos.z * pos.z; aSq = a*a; bSq = b*b; res = (xSq / aSq) + (zSq / bSq); if (res <= 1.0) { return true; } else { return false; } } //is given position inside an arbitrary trimesh object? boolean isTriLegal(Vec3 pos, Object3D obj){ tris = obj.getFaces(); verts = obj.getVertexPositions(); count = 0; for (int i = 0; i < tris.length; i++) { v1 = verts; v2 = verts; v3 = verts; //I'm counting on shortcut evaluation here. if (isInBlockingRange(pos, v1, v2, v3) && inTriangle(pos, v1, v2, v3) && relativePlaneNormal(pos, v1, v2, v3) > 0) count++; } //if you must pass through an odd number of faces, you are inside the object. return (count%2 == 1); } //generally, is a random position within bounds? boolean isLegal(Vec3 pos, int type, Object3D obj){ switch (type) { case 1: return true; // if the bounding object is a cube, all generated positions are valid case 2: return isSphereLegal(pos, obj); case 3: return isCylinderLegal(pos, obj); case 4: return isTriLegal(pos, obj); } } //Main Script Body/// //fill widgets with object choices from the scene. TODO: block cameras and lights for (i = 0; i < numObjects; i++){ containerChoices.add(theScene.getObject(i).name); distribChoices.add(theScene.getObject(i).name); } //other input fields, and create the dialog. numCopies = new ValueField(10, ValueField.POSITIVE+ValueField.INTEGER); rotationRange = new ValueField(1.0,ValueField.NONNEGATIVE); dlg = new ComponentsDialog(window, "Select Parameters", new Widget  {new BScrollPane(containerChoices, BScrollPane.SCROLLBAR_AS_NEEDED, BScrollPane.SCROLLBAR_AS_NEEDED), new BScrollPane(distribChoices, BScrollPane.SCROLLBAR_AS_NEEDED, BScrollPane.SCROLLBAR_AS_NEEDED), numCopies, rotationRange}, new String  {"Volume","Fill With","Number of Copies", "Rotation Variation"}); if (!dlg.clickedOk()) return; if (containerChoices.getSelectedIndex() == distribChoices.getSelectedIndex()) { new MessageDialog(window, "The object cannot be distributed through its own volume!"); return; } copies = (int)numCopies.getValue(); rotation = rotationRange.getValue(); container = theScene.getObject(containerChoices.getSelectedIndex()); distributable = theScene.getObject(distribChoices.getSelectedIndex()); obj = container.getObject(); dist = distributable.getObject(); type = 0; if (obj instanceof Cube) { type = 1; } else if (obj instanceof Sphere) { type = 2; } else if (obj instanceof Cylinder) { type = 3; } else if (obj instanceof TriangleMesh && obj.isClosed()) { type = 4; //Don't run conversion on something that is already a trimesh. } else if (obj.canConvertToTriangleMesh() != Object3d.CANT_CONVERT){ obj = obj.convertToTriangleMesh(theScene.getInteractiveSurfaceArea()); if (obj.isClosed()) { type = 4; } } if (type == 0) return; //script crashes if we can't process the container - better than running the main loop with no effect. while (copies > 0) { pos = randomPosition(obj.getBounds()); if (isLegal(pos, type, obj)) { rot = randomRotation(rotation); distCopy = new ObjectInfo(dist, new CoordinateSystem(container.coords.fromLocal().times(pos), rot.x, rot.y, rot.z), "Duplicate of " + distributable.name); container.addChild(distCopy, 0); window.addObject(distCopy, null); copies -; } } window.rebuildItemList();

    Any chance you could put this in a text file an upload it somewhere?