I was doing some R&D for a project with my BROS<\/em> <\/strong>Frank & David when I came across a problem I had thought\u00a0of for a while but never tackled for real. the\u00a0idea is to distribute (scatter) a set of random 3D points inside a volume, preferably an\u00a0arbitrary mesh.<\/p>\n

distributing \u00a0random points in geometric volumes is quite straight forward. if you know the formula of\u00a0a sphere, a cube, a cylinder or any shape, you can create a\u00a0point inside the said shape. also, and much like Constructive Solid Geometry, it’s fairly easy to use boolean operations (union, subtraction, intersection & XOR) between the shapes and obtain\u00a0a broad variety\u00a0of complex shapes.<\/p>\n

if this approach is elegant, probably fast and efficient, it has a big downside ; arbitrary meshes are hard –\u00a0if not impossible\u00a0– to model with equations. it is therefore often limited to simple use cases like procedural or fractals shapes.<\/p>\n

being a long time 3DS max user, I\u00a0often used the “Scatter” modifier\u00a0to distribute point on or inside a mesh. when\u00a0I used a non-manifold<\/em>\u00a0polyhedron – a “broken” mesh, with holes, no inside<\/em> or outside<\/em>\u00a0– the modifier failed or 3DS crashed. that’s when\u00a0I decided to try\u00a0to code something.<\/p>\n

the algorithm goes as follow:<\/p>\n

\n
1. pick a random point on the bounding volume of the mesh\u00a0and a random direction<\/li>\n
2. shoot a ray at the\u00a0mesh from that origin, in that direction<\/li>\n
3. evaluate the result to keep or discard the intersection points<\/li>\n<\/ol>\n

   it implies shooting many rays at a mesh\u00a0so\u00a0depending on the mesh’s complexity, it can take a lot of time\u00a0and anyway it’s more suited as a mesh “pre-processor” than as a\u00a0real time modifier.<\/p>\n

   step 1 is trivial, for\u00a0step 2,\u00a0THREE.js has a built-in raycaster\u00a0and\u00a0for step 3, we’ll mostly need to determine if we’re ‘inside’ or\u00a0‘outside’ the mesh.<\/p>\n

   to determine\u00a0if a point is inside or outside a polyhedron, assuming the mesh is a manifold<\/em>\u00a0(it has an ‘inside’ and an ‘outside’), we\u00a0can shoot a ray from that point in any direction and count how many times the ray intersects the polyhedron.<\/p>\n

   if the number is even, your\u00a0point is outside, if it’s odd, it’s inside. a visual explanation:<\/p>\n

   <\/p>\n

   I\u00a0think it also works with actual octopuses\u00a0but I would recommend not<\/strong> to try.<\/p>\n

   essentially, we’ll\u00a0use the number of times a\u00a0ray intersects the mesh to determine wether we’re inside or outside. here’s\u00a0my implementation:<\/p>\n

   var raycaster;\/\/THREE.raycaster: used to shoot rays at the mesh\r\nvar o;\/\/ray origin\r\nvar d;\/\/ray direction\r\nvar intersections;\/\/stores the result of the raycasting\r\nvar a;\/\/DOM element tag to download the result ( see particlesToString )\r\n\r\nfunction distribute( mesh, count ) {\r\n\r\n    \/\/this will store the results\r\n    var coords = [];\r\n    var dests = [];\r\n    \/\/temporary vars to store the position and destination\r\n    var p0, p1;\r\n\r\n    \/\/this has an influence as to how the raycasting is performed\r\n    var side = mesh.material.side;\r\n    mesh.material.side = THREE.DoubleSide;\r\n\r\n    \/\/we'll need normals (it's probably done implicitly when we raycast though)\r\n    mesh.geometry.computeFaceNormals();\r\n\r\n    \/\/this is used to distributte the origins of the rays\r\n    mesh.geometry.computeBoundingBox();\r\n    var bbox = mesh.geometry.boundingBox;\r\n\r\n    \/\/ 'inflates' the box by 10% to prevent colinearity\r\n    \/\/ or coplanarity of the origin with the mesh\r\n    bbox.min.multiplyScalar( 1.1 );\r\n    bbox.max.multiplyScalar( 1.1 );\r\n\r\n    \/\/computes the box' size to compute random points\r\n    var size = bbox.max.sub( bbox.min );\r\n\r\n    \/\/to perform raycast\r\n    raycaster = raycaster || new THREE.Raycaster();\r\n    o = o || new THREE.Vector3();\r\n    d = d || new THREE.Vector3();\r\n\r\n    for( var i = 0; i < count; i++ ){\r\n\r\n        \/\/ randomize the rays origin\r\n        o.x = bbox.min.x + Math.random() * size.x;\r\n        o.y = bbox.min.y + Math.random() * size.y;\r\n        o.z = bbox.min.z + Math.random() * size.z;\r\n\r\n        \/\/randomize the ray's direction\r\n        d.x = ( Math.random() - .5 );\r\n        d.y = ( Math.random() - .5 );\r\n        d.z = ( Math.random() - .5 );\r\n        d.normalize();\r\n\r\n        \/\/sets the raycaster\r\n        raycaster.set( o, d );\r\n\r\n        \/\/shoots the ray\r\n        intersections = raycaster.intersectObject( mesh, false );\r\n\r\n        \/\/no result\r\n        if( intersections.length == 0 ){\r\n\r\n            \/\/bail out & continue\r\n            i--;\r\n\r\n        }else{\r\n\r\n            \/\/checks if we meet the conditions:\r\n            \/\/the origin must be outside\r\n            var valid = intersections.length >= 2 && (intersections.length % 2==0);\r\n            if (valid) {\r\n\r\n                \/\/tests all the intersection pairs\r\n                var additions = -1;\r\n                for( var j = 0; j < intersections.length; j+= 2 ){\r\n\r\n                    \/\/ make sure that the origin -> direction vector have the same\r\n                    \/\/ direction as the normal of the face they hit\r\n\r\n                    \/\/test the direction against the outwards' face's normal\r\n                    var dp0 = d.dot(intersections[ j + 1 ].face.normal) <= 0;\r\n\r\n                    \/\/flips the direction to make it 'look at' the origin\r\n                    d.negate();\r\n\r\n                    \/\/test the direction against the inwards' face's normal\r\n                    var dp1 = d.dot(intersections[ j ].face.normal) <= 0;\r\n\r\n                    \/\/flips the direction again for the next test\r\n                    d.negate();\r\n\r\n                    \/\/ if both vectors pairs head in the same direction\r\n                    \/\/ the point is guarranteed to be inside\r\n                    if( dp0 || dp1){\r\n                        continue;\r\n                    }\r\n\r\n                    \/\/adds the points\r\n                    if( coords.length < count * 3 ){\r\n                        console.log(\"ok\")\r\n                        p0 = intersections[j].point;\r\n                        coords.push( p0.x, p0.y, p0.z);\r\n                        p1 = intersections[j+1].point;\r\n                        dests.push( p1.x, p1.y, p1.z);\r\n                        additions++;\r\n                    }\r\n                }\r\n                \/\/increments the counter by the number of additions\r\n                i += additions;\r\n\r\n            }else{\r\n                \/\/invalid intersection, try again...\r\n                i--;\r\n            }\r\n        }\r\n    }\r\n    \/\/resets the material side\r\n    mesh.material.side = side;\r\n    return {\r\n        pos:coords,\r\n        dst:dests\r\n    };\r\n};<\/pre>\n
   this is rather self-explanatory (hopefully)\u00a0;\u00a0we get the bounding box of the mesh, ‘inflate’ it a bit to avoid some colinearity \/ coplanarity issues, then randomize the ray’s origin\/direction. performa ray casting onto the mesh then classify the result.<\/p>\n
   let’s focus on the ‘classify’\u00a0bit a minute:<\/p>\n
   \/\/the origin must be outside\r\nvar valid = intersections.length >= 2 && ( intersections.length % 2 == 0 );\r\nif (valid) {\r\n[...]<\/pre>\n
   we’re in a valid state if we have: at least 2 intersections and an even number of intersections which means that we hit the mesh at least once and our origin is outside the mesh ( as seen above with that glorious octopus illustration ). we have something like this when valid is true:
   \n<\/p>\n
   the next bit takes all pairs of points and retrieves the associated normals like so:<\/p>\n
   <\/p>\n
   and computes the dot product<\/em> between the 2 vectors of the same color.\u00a0if the dot product of 2 vectors is positive, they’re heading in the same direction, if the dot product is negative, they are heading in opposite directions and if it’s 0, they are perpendicular. this dreadful 4 liners will do this for all intersections pairs.<\/p>\n
   \/\/test the direction against the outwards' face's normal\r\nvar dp0 = d.dot(intersections[ j + 1 ].face.normal) <= 0;\r\n\r\n\/\/flips the direction to make it 'look at' the origin\r\nd.negate();\r\n\r\n\/\/test the direction against the inwards' face's normal\r\nvar dp1 = d.dot(intersections[ j ].face.normal) <= 0;\r\n\r\n\/\/flips the direction again for the next test\r\nd.negate();\r\n\r\n\/\/ if both vectors pairs head in the same direction\r\n\/\/ the point is guarranteed to be inside\r\nif( dp0 || dp1){\r\n    continue;\r\n}<\/pre>\n
   this ensures that the “broken polyhedra” work too ; if the 2 faces’ normals head in the same direction, the object is broken ; it has no inside or outside. the code above\u00a0checks this\u00a0case and bails out if need be. it\u00a0can also collect more than 2 points per ray which is nice :)<\/p>\n
   you would call it like:<\/p>\n
   var model = CHTHULU;\/\/a THREE.Mesh\r\nvar count = Math.pow( 2, 12 );\/\/ -> 4096 point pairs\r\n\r\n\/\/call the method and strore the result in a prticles object\r\nvar inside = distribute( model, count );<\/pre>\n
   the result of the distribute function is a pair of float32Arrays<\/em> containing XYZ triplets for the in\u00a0& \u00a0out positions\u00a0respectively. to place an object ‘inside’ the polyhedron, you’d do something like:<\/p>\n
   \/\/midpoint of the 2 intersection points\r\nvar p = new THREE.Vector3(\r\n\t( inside.pos[ id ].x + inside.dst[ id ].x ) * .5,\r\n\t( inside.pos[ id ].y + inside.dst[ id ].y ) * .5,\r\n\t( inside.pos[ id ].z + inside.dst[ id ].z ) * .5\r\n);<\/pre>\n
   or more likely, pass inside.dst<\/em> as an attribute and ask the shader to mix<\/em>\u00a0the two:<\/p>\n
   float t = abs( sin( time ) );\r\nvec3 pos = mix( position, dest, t );<\/pre>\n
   with a value\u00a0t<\/em>\u00a0between 0 & 1 which guarantees that the position will remain inside the\u00a0mesh.<\/p>\n
   of course we can change the above to ‘carve’ the mesh inside a cloud of points and keep only the “outside”. :)<\/p>\n
   HAMMER TIME!
   \nthis is a model with 65K particles floating around (click)<\/p>\n
   <\/a><\/p>\n
   if you notice some particles floating around, it’s because the distribution mesh is the mother of all non-manifold polyhedra\u00a0^^
   \n
   \nthis is again 65K particles distributed inside a mesh. notice how it retained the fine details (on the legs for instance)<\/p>\n
   <\/a><\/p>\n
    <\/p>\n
   still 65K particles, this time rendered as line segments<\/p>\n
   <\/a><\/p>\n
   finally a splendid rendition of 2K particles as line sets, using the Spite’s MeshLines<\/a>. my code is ugly as fuck but hey…<\/p>\n
   <\/a><\/p>\n
   and that’s it! well, I gues you get the idea ^^<\/p>\n
   there’s even a github repo for that<\/a><\/p>\n
   enjoy :)<\/p>\n","protected":false},"excerpt":{"rendered":"
   I was doing some R&D for a project with my BROS Frank & David when I came across a problem I had thought\u00a0of for a while but never tackled for real. the\u00a0idea is to distribute (scatter) a set of random 3D points inside a volume, preferably an\u00a0arbitrary mesh. distributing \u00a0random points in geometric volumes is … [Read more…]<\/a><\/span><\/p>\n","protected":false},"author":1,"featured_media":1093,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"sharing_disabled":false,"spay_email":"","jetpack_publicize_message":""},"categories":[3],"tags":[7,2],"jetpack_featured_media_url":"http:\/\/barradeau.com\/blog\/wp-content\/uploads\/2017\/04\/2017-04-03-11.png","jetpack_publicize_connections":[],"jetpack_shortlink":"https:\/\/wp.me\/p4oXhx-h4","_links":{"self":[{"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1058"}],"collection":[{"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1058"}],"version-history":[{"count":31,"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1058\/revisions"}],"predecessor-version":[{"id":1060,"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1058\/revisions\/1060"}],"wp:featuredmedia":[{"embeddable":true,"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=\/wp\/v2\/media\/1093"}],"wp:attachment":[{"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1058"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1058"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1058"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}