View Full Version : How to create a surface starting from a cloud of points ?
prettyPixel 10172005, 09:56 AM Is it possible to create a surface starting from a cloud of points ?
Lets us say that I have a set of vertices. The points form a surface but there are still no faces.
How to create the faces ?
Are there methods for that?
Are there already scripts for that?
Thanks for any information you can give


salmonmoose
10172005, 10:05 AM
other than using vertex snap, and making the polygons yourself, I don't think you have much chance of a 'clean' result.
You could use metaparticles  I don't think this is what you're after, it's rather hard to build faces from vertexes unless you know what order they go in.
soshiant
10172005, 02:55 PM
Is it possible to create a surface starting from a cloud of points ?
Lets us say that I have a set of vertices. The points form a surface but there are still no faces.
How to create the faces ?
Are there methods for that?
Are there already scripts for that?
Thanks for any information you can give
U can approximate all kind of surfaces with squares & circles and all kind of volumes with cubes spheres(may be other ogjs can be used but these are the most common).This is the base of diffrential in math.There exists an approximation here depending on the accuracy u want.
May be u want to create a tea pot and u dont want to approximate it with squares,
then u can detach each face( into the element or another obj) then use pflow.I dont really guess that u can use verts as ur base coz they dont have any surface at all but instead u can use faces or put faces on each vert, u can fill the faces with very small faces too.
i guess there exists a limit in the word "cloud" coz soooo many faces are required if u want to have it cloudy!!
Any how i remember a plug in called sandblaster from digimation and also i think i pFlow tools there exists some tools to.All can be done using pFlow.
prettyPixel,
in this thread: Delauney triangulation (http://forums.cgsociety.org/showthread.php?t=268981)
is a link to a 'plain text' explanation: http://astronomy.swin.edu.au/~pbourke/
search for 'delauney'.
maybe it helps.
Georg
prettyPixel
10172005, 04:46 PM
hey thanks guys !
I read only now your 3 answers.
I don't think you have much chance of a 'clean' result.
That is the problem which I encounter.
My method does not always generate correct surfaces.
U can approximate all kind of surfaces with squares & circles and all kind of volumes with cubes spheres(may be other ogjs can be used but these are the most common).This is the base of diffrential in math.There exists an approximation here depending on the accuracy u want. (...)
Thanks for this useful informations. At this time my method is not based on an approximation. I really want to use each vertex (because each point is really essential for me). Nevertheless this approach is interesting.
in this thread: Delauney triangulation
is a link to a 'plain text' explanation: http://astronomy.swin.edu.au/~pbourke/
search for 'delauney'.
maybe it helps.
Thanks Georg. I am going to read this method now...
Here is my version to calculate a surface.
Of course, I did not yet use your ideas.
It is not an estimatition, but it sometimes that generates errors.
Certain points can be ignored.
struct flagObj
(
obj,
flagVerts=#{1..obj.numVerts},
flagEdges=#{},
flagFaces=#{}
)
fn createVertexCloud csize csegs =
(
obj=geoSphere radius:csize baseType:1 segs:csegs
cscale=csize/2.2 ; cstr=csize/4.0
addmodifier obj (noiseModifier scale:cscale strength:[cstr,cstr,cstr] )
convertToPoly obj
polyOp.deleteFaces obj #{1..obj.numFaces} delIsoVerts:false
return
obj
)
fn createFirstFace theObj =
(
obj=theObj.obj
 vertex 1
v1=1
v1Pos=polyOp.getVert obj v1
theObj.flagVerts[v1]=false
 vertex 2
objNumVerts=obj.numVerts
theCenter=obj.center
theVector=v1PostheCenter
theMax=1.0 ; theMaxIdx=0
for v=1 to objNumVerts where theObj.flagVerts[v] do
(
currentPos=polyOp.getVert obj v
currentVector=currentPostheCenter
currentDot=(dot (normalize theVector) (normalize currentVector))+1.0
if currentDot>theMax do ( theMax=currentDot ; theMaxIdx=v )
)
v2=theMaxIdx
v2Pos=polyOp.getVert obj v2
theObj.flagVerts[v2]=false
 vertex 3
midEdge=(v1Pos+v2Pos)/2.0
edgeVector=v2Posv1Pos
theVector=midEdgetheCenter
theMax=1.0 ; theMaxIdx=0
for v=1 to objNumVerts where theObj.flagVerts[v] do
(
currentPos=polyOp.getVert obj v
currentVector=currentPostheCenter
currentVectorP=currentPosmidEdge
currentDot=(dot (normalize theVector) (normalize currentVector))+1.0
currentDotPerp=1.0(abs( dot (normalize edgeVector) (normalize currentVectorP) ))
currentDot*=currentDotPerp
if currentDot>theMax do ( theMax=currentDot ; theMaxIdx=v )
)
v3=theMaxIdx
v3Pos=polyOp.getVert obj v3
theObj.flagVerts[v3]=false
 face 1
faceNormal=normalize ( cross (v2Posv1Pos) (v3Posv1Pos) )
pseudoFaceNormal=normalize ( ((v1Pos+v2Pos+v3Pos)/3.0)theCenter )
if (dot faceNormal pseudoFaceNormal)>0.0 then newFace=polyOp.createPolygon obj #(v1,v2,v3) else newFace=polyOp.createPolygon obj #(v1,v3,v2)
theObj.flagFaces=#{1}
theObj.flagEdges=#{1..3}
return
OK
)
fn getFirstItem theBitArray = ( for i in theBitArray do return i )
fn getProxyVert theObj theCenter v1 v2 v3 face =
(
obj=theObj.obj
st1=theObj.flagVerts[v1]; theObj.flagVerts[v1]=false
st2=theObj.flagVerts[v2]; theObj.flagVerts[v2]=false
st3=theObj.flagVerts[v3]; theObj.flagVerts[v3]=false
 initialisation
faceNormal=polyOp.getFaceNormal obj face
v1Pos=polyOp.getVert obj v1
v2Pos=polyOp.getVert obj v2
theVector=v2Posv1Pos
midEdge=(v1Pos+v2Pos)/2.0
midEdgePerpVector=normalize ( cross theVector faceNormal )
firstActiveVert=getFirstItem theObj.flagVerts
currentPos=polyOp.getVert obj firstActiveVert
vector2MidEdge=midEdgetheCenter
currentVector=currentPostheCenter
dAngle=acos (dot (normalize vector2MidEdge) (normalize currentVector))
currentMidEdgeVector=currentPosmidEdge
dotP=dot (normalize midEdgePerpVector) (normalize currentMidEdgeVector)
dFactor=1.0((dotP+1.0)/2.0)
dirInfluence=2.0
dAngle=dAngle+(dAngle*dFactor*dirInfluence)
dmin=dAngle
dminIdx=firstActiveVert
 find the nearest
theObjFlagVerts=theObj.flagVerts
for v in theObjFlagVerts do
(
currentPos=polyOp.getVert obj v
currentVector=currentPostheCenter
dAngle=acos (dot (normalize vector2MidEdge) (normalize currentVector) )
currentMidEdgeVector=currentPosmidEdge
dotP=dot (normalize midEdgePerpVector) (normalize currentMidEdgeVector)
dFactor=1.0((dotP+1.0)/2.0)
dAngle=dAngle+(dAngle*dFactor*dirInfluence)
if dAngle<dmin do ( dmin=dAngle ; dminIdx=v )
)
theObj.flagVerts[v1]=st1
theObj.flagVerts[v2]=st2
theObj.flagVerts[v3]=st3
 return
dminIdx
)
fn notInArray theArray theValues = ( for v in theValues where (findItem theArray v)==0 collect v )
fn getFirstEdge theObj face =
(
obj=theObj.obj
edgesOfFace=polyOp.getFaceEdges obj face
filterEdgesOfFace=for e in edgesOfFace where theObj.flagEdges[e] collect e
if filterEdgesOfFace.count!=0
then ( for e in filterEdgesOfFace do return e )
else (
theObj.flagFaces[face]=false
0
)
)
fn getFirstFace theObj =
(
theObjFlagFaces=theObj.flagFaces
if theObjFlagFaces.numberSet!=0
then ( for f in theObjFlagFaces do return f )
else 0
)
fn createSurface obj =
(
theObj=flagObj obj
createFirstFace theObj
errorLevel=0
securityCountF=0
maxCountF=20
maxCountE=6
while (thisFace=getFirstFace theObj )!=0 do
(
securityCountF+=1 ; if securityCountF>maxCountF do (format "+++ securityCountF\n" ; exit)
securityCountE=0
theFaceVerts=polyOp.getFaceVerts theObj.obj thisFace
while (thisEdge=getFirstEdge theObj thisFace)!=0 do
(
securityCountE+=1 ; if securityCountE>maxCountE do (format "+++ securityCountE\n" ; exit)
theFaceVerts=polyOp.getFaceVerts theObj.obj thisFace
theEdgeVerts=polyOp.getEdgeVerts theObj.obj thisEdge
difArray=notInArray theEdgeVerts theFaceVerts
newVert=getProxyVert theObj theObj.obj.center theEdgeVerts[1] theEdgeVerts[2] difArray[1] thisFace
if newVert!=0
then (
newFace=polyOp.createPolygon theObj.obj #(theEdgeVerts[2],theEdgeVerts[1],newVert)
if newFace!=undefined then
(
securityCountF=0
theObj.flagFaces[newFace]=true
theObj.flagEdges[thisEdge]=false
edgesOfNewFace=polyOp.getFaceEdges theObj.obj newFace
for e in edgesOfNewFace do (
facesOfEdge=polyOp.getEdgeFaces theObj.obj e
if facesOfEdge.count==2 then theObj.flagEdges[e]=false else theObj.flagEdges[e]=true
)
)
else (
errorLevel+=1
theObj.flagEdges[thisEdge]=false
)
)if
else (
errorLevel+=1
if theObj.flagEdges.numberSet==3 then (
the3Verts=#()
for e in theObj.flagEdges do
(
vertsOfEdge=polyOp.getEdgeVerts theObj.obj e
if findItem the3Verts vertsOfEdge[1]==0 do append the3Verts vertsOfEdge[1]
if findItem the3Verts vertsOfEdge[2]==0 do append the3Verts vertsOfEdge[2]
)
if the3Verts.count==3 do
(
newFace=polyOp.createPolygon theObj.obj #(the3Verts[3],the3Verts[2],the3Verts[1])
for e in theObj.flagEdges do theObj.flagEdges[e]=false
)
)
else ( theObj.flagEdges[thisEdge]=false )
)
)while
)while
return
errorLevel
)fn
clearListener()
max modify mode
cloudObj=createVertexCloud 100.0 5
cloudObj.vertexTicks=true
max views redraw
messageBox ("ready for surface creation\nclick Ok to continue")
errorLevel=createSurface cloudObj
if errorLevel!=0 then messageBox ("errorLevel = "+errorLevel as string)
cloudObj.vertexTicks=false
max views redraw
Are the points equal distances from each other? like a geosphere.
prettyPixel
10172005, 06:19 PM
Are the points equal distances from each other? like a geosphere.
Not exactly, but the points are all on a sphere. They are at the same distance that the center of the sphere.
Maybe you see where I go ;)
Wahooney
10182005, 05:56 AM
Convex Hulls, I think that's your ticket. A short summation of the brute force method:
Select 3 verts.
Make a plane (not a plane object) out of them.
Test each vert and see on which side of the plane they lie.
If each vertex falls behind the plane it is convex, build the face.
Otherwise it is probably concave so don't build the face, choose the next 3 verts repeat until there are no more open edges (don't test the same combination of verts again).
There is a bit of maths involved here (plane from 3 points, point infront of/behind plane, etc.), but it will give you a neat, convex shape out of any point cloud. It is not, however, guaranteed that every vert will have attached faces, as some may lie inside the convex volume.
Google Convex Hulls and/or Paul Bourke.
Hope this helps.
salmonmoose
10182005, 07:51 AM
Ouch :)
We should add that to the weekly scripting challenge thread ;)
prettyPixel
10182005, 04:33 PM
I work at present on the method of Delauney. For the moment I encounter problems during the reconstruction of long concave faces.
If each vertex falls behind the plane it is convex, build the face.
Hope this helps.
Thank you for explanations :)
Could you explain in detail how to know if a selection of faces is concave or convex ?
stuh505
10182005, 06:43 PM
Pixel,
the convex hull method will check every combination of 3 vertices. In other words, it will check every possible face that you could possibly make. For each potential face, it checks to see if ALL of the other vertices not used by that face fall on one side of the face. If all the verts fall on one side, then the face you're looking at is definitely on the outside of the object, thus it is a convex face. If some of the verts are on one side of the faceplane and some are on the other side, then this isn't necessarily an outside face of the object, so it is not made into a face.
Therefore, this method would work perfectly well if your points were to form a sphere. However, since you are adding noise to the sphere, the convex hull method will NOT work...because probably most of the "outside" faces will not satisfy the planetest desrcribed above, and therefore they wouldn't be built into faces.
However, the convex hull method will PARTIALLY build what you want...and you can be guarnateed that the parts it builds will be correct. You will just have to do a lot more work to complete it.
CGTalk Moderation
10182005, 06:43 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.