LDraw.org Discussion Forums

Full Version: Idea for an LDCad script
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
A simple idea, perhaps (and for all I know someone's already done this), but what about a "place on ground" script that would calculate the lowest point of a model and place that at Y=0?

Better still, calculate the two lowest points—such as two wheels that are not quite in the same plane—and rotate the whole model so that they both rest at Y=0?
That would be a useful one !
(2021-12-31, 21:13)N. W. Perry Wrote: [ -> ]Better still, calculate the two lowest points—such as two wheels that are not quite in the same plane—and rotate the whole model so that they both rest at Y=0?

You could even do that for three points!
But depending on the geometry of the model it's possible that after such rotation, none of those three points will be the lowest, which might not be what you want.
(2022-01-03, 0:18)Owen Dive Wrote: [ -> ]You could even do that for three points!
But depending on the geometry of the model it's possible that after such rotation, none of those three points will be the lowest, which might not be what you want.

True. I haven't yet found a case where I'd need three points to put a model on the ground. But, I'd love to be able to do that when, say, dumping apples into a crate, or pebbles into a flowerbed, when building a modular building or bonsai tree!
(2021-12-31, 21:13)N. W. Perry Wrote: [ -> ]A simple idea, perhaps (and for all I know someone's already done this), but what about a "place on ground" script that would calculate the lowest point of a model and place that at Y=0?

Better still, calculate the two lowest points—such as two wheels that are not quite in the same plane—and rotate the whole model so that they both rest at Y=0?

You would need access to vertex data for this, or manually process the type 3 lines in the current api.
(2022-01-06, 18:40)Roland Melkert Wrote: [ -> ]You would need access to vertex data for this, or manually process the type 3 lines in the current api.

Which I bet would also be the first step for any potential collision detection tool, no? I wonder if the same math could be used for a collision-aware rotation tool—now that would be powerful! Big Grin
(2022-01-06, 19:57)N. W. Perry Wrote: [ -> ]Which I bet would also be the first step for any potential collision detection tool, no? I wonder if the same math could be used for a collision-aware rotation tool—now that would be powerful! Big Grin

I have implemented a collision detection in LDInspector which is working "in most cases".  Wink
I already thought of integrating this into LDCad - but never started. Blush
(2022-01-07, 14:43)Stefan Frenz Wrote: [ -> ]I have implemented a collision detection in LDInspector which is working "in most cases".  Wink
I already thought of integrating this into LDCad - but never started. Blush

I will try to add access to the vertex data (position, normal and color).

I'm wondering if it would be fast enough to do real time calculations though.
(2022-01-08, 20:57)Roland Melkert Wrote: [ -> ]I will try to add access to the vertex data (position, normal and color).
I'm wondering if it would be fast enough to do real time calculations though.

Thank you, Roland. Please don't spend too much time in this for me - in fact, at the moment the checks are very sensitive to tolerances, i.e. trade-of between false-positives and false-negatives.  Sad Some cases are just not detected correctly even though clearly colliding, which is a known problem of the triangle-comparison approach I have chosen. The currently implemented checks help me in many cases, but they are far from deserving blind trust. I would love to implement this as LDCad extension, but I'm very uncertain about the result.

If the basic idea of my current collision detection will sometimes make it into a LDCad script, it would need the triangle (not only vertex) information to check triangle intersection... I agree that it most probably will not be fast enough for real time use: at the moment, I check every triangle of a part against all triangles of all other parts, just after building some helping and very time saving bounding boxes.
(2022-01-08, 22:11)Stefan Frenz Wrote: [ -> ]at the moment the checks are very sensitive to tolerances, i.e. trade-of between false-positives and false-negatives

Two examples of the LDInspector collision detection result:

Everything ok with the 603 model:
[attachment=7360]

For the 1972 model, each tire and its rim are reported to intersect (they don't), there is no special treatment of paths (they don't intersect with theirselves), but the intersection of the Technic Connector with the bottom Plate is mathematically correct (but not relevant in reality):
[attachment=7361]
(2022-01-09, 7:59)Stefan Frenz Wrote: [ -> ]Two examples of the LDInspector collision detection result:

Very cool.

Maybe 'fake seam shrinking' the parts before testing resolves some of those false positives?
(2022-01-09, 20:05)Roland Melkert Wrote: [ -> ]Maybe 'fake seam shrinking' the parts before testing resolves some of those false positives?

Thank you for this hint!  Smile  I was not aware of this thread and have to work through its background.

I tried so many approaches to shrink parts because in LDInspector version 0.5 collisions of coplanar triangles are all filtered out. Example:

[attachment=7366]

If the parts are not perfectly aligned or moved by small steps, the current algorithm will detect the collision. But perfectly aligned in a static model (which should be some normal case in my understanding) they collide in reality, but they don't have (non-coplanar) triangle intersection, so the current implementation will not detect the collision. Shrinking would be a solution in some cases, but I could not find a general solution to the problem illustrated here: two non-colliding parts (green) do collide after shrinking (red, in this example both parts are shrinked by 5% at an unlucky part origin):

[attachment=7365]

Hmmmmm. Another thing on my ToDo-list. Smile
(2022-01-09, 21:36)Stefan Frenz Wrote: [ -> ]Hmmmmm. Another thing on my ToDo-list. Smile

You need to shrink them using their absolute center, as done in the povray snippet at the bottom of the thread you referenced.
(2022-01-08, 22:11)Stefan Frenz Wrote: [ -> ]Thank you, Roland. Please don't spend too much time in this for me - in fact, at the moment the checks are very sensitive to tolerances, i.e. trade-of between false-positives and false-negatives.  Sad Some cases are just not detected correctly even though clearly colliding, which is a known problem of the triangle-comparison approach I have chosen. The currently implemented checks help me in many cases, but they are far from deserving blind trust. I would love to implement this as LDCad extension, but I'm very uncertain about the result.

I have this working at the moment:
[attachment=7367]

The triangle is actually the first 3 positions of a quad I think as I need to add aa internal mapping for direct triangle/quad access (LDCad renders in groups by color/texture).

Main question is this something that would be usable (seeing you''re the main end user at the moment Smile )
(2022-01-09, 22:38)Roland Melkert Wrote: [ -> ]Main question is this something that would be usable (seeing you''re the main end user at the moment Smile )

For myself, I'm not as interested in detecting unintended collisions as in detecting intended ones. Basically as another form of snapping, so that you can move or rotate one part towards another, and it will stop exactly where the two parts touch. This is why I thought of it like an extension of the "put on ground" shortcut, because that's essentially moving a part (or model) downwards until it "collides" with the y=0 plane.

So for this idea of "collision snapping", or maybe better called "proximity snapping", you'd basically find the colliding surface of a nearby part and calculate from that a new "ground" plane. Then it would be the same mathematically as putting something on the ground—except that you might be moving the object on global axes while looking for the collision point on some non-normal plane.

At least, I think it would. Rolleyes
(2022-01-10, 1:46)N. W. Perry Wrote: [ -> ]At least, I think it would. Rolleyes

I could think of the collision detection as an indicator to end a directed move or directed rotation. This would allow something like "move/rotate in this direction until the first collision occurs, remember the colliding triangles and try to get (approximate? calculate?) the one-directional move/rotate value" as in the following examples: move green block to the right along the red line until it reaches the black block (becomes blue) or rotate the green block around the bottom left edge clockwise until it reaches the black block (becomes cyan).
[attachment=7368]
Doing one move and two rotations like this, I would guess a model could be set to ground (or aligned to any other part) automatically.

The following would be much harder: move until there is no collision. Most of the time there will be at least a small overlap, so the target position will not be found (with my algorithm):
[attachment=7369]

Maybe the last one could be solvable by something that does volume intersection by trying to minimize the volume that intersects. As far as I understand LDraw, a volume model is not (directly) available as invisible boundaries are not included (like the bottom of a stud or the upper end of the two inner 3002 tubes). And so far my collision detection has only very little knowledge of volumes. Wink
(2022-01-09, 22:38)Roland Melkert Wrote: [ -> ]I have this working at the moment:
Thank you so much. Smile  If the vertices order is the same as it would be for rendering (i.e. after handling all part-subpart-whatever-invertions), this should allow a port of my collision detection. Smile  For the quads I use two triangles like "addTri(t1, t2, t3);addTri(t3, t4, t1);" (not inverted) or "addTri(t1, t3, t2);addTri(t3, t1, t4);" (inverted), so if your engine already splits the quad into two triangles, this would also match perfectly.
(2022-01-10, 8:47)Stefan Frenz Wrote: [ -> ]Thank you so much. Smile  If the vertices order is the same as it would be for rendering (i.e. after handling all part-subpart-whatever-invertions), this should allow a port of my collision detection. Smile  For the quads I use two triangles like "addTri(t1, t2, t3);addTri(t3, t4, t1);" (not inverted) or "addTri(t1, t3, t2);addTri(t3, t1, t4);" (inverted), so if your engine already splits the quad into two triangles, this would also match perfectly.

Render data inside LDCad is at the part level (flattened), and uses both triangles and quads.

This stems from the age of the base code, the planned (but paused) 2.0 engine was going to be triangle exclusive so I thought it wouldn't hurt in the near future.

OpenGL will convert it to triangles somewhere in the middle anyway though.

All data has the same winding (think it's CW but have to check to be sure), unless the source .dat tree has no (complete) bfc information.
(2022-01-10, 9:26)Roland Melkert Wrote: [ -> ]Render data inside LDCad is at the part level (flattened), and uses both triangles and quads.
All data has the same winding (think it's CW but have to check to be sure), unless the source .dat tree has no (complete) bfc information.

That will fit and I will try. Smile  Thanks again! Smile
(2022-01-09, 21:36)Stefan Frenz Wrote: [ -> ]in LDInspector version 0.5 collisions of coplanar triangles are all filtered out

Motivated by this thread, I added some coplanar checks that seem to work in some Wink  cases. The given "1x1 with stud in 1x1 brick" example will be reported as collision, but now also the arm-in-body combination is reported as collision:
[attachment=7370]

Checking in LDCad, the collision report seems to be correct:
[attachment=7371]

Maybe this also can be fixed with shrinking...
(2022-01-10, 10:23)Stefan Frenz Wrote: [ -> ]Maybe this also can be fixed with shrinking...

Hm, shrinking at the appropriate absolute center seems to even make this undesired collision very robust (upper picture shows original valid lines, bottom picture is shrinked, last picture is zoomed with collision marker):
[attachment=7372]
[attachment=7373]
(2022-01-10, 10:37)Stefan Frenz Wrote: [ -> ]Hm, shrinking at the appropriate absolute center seems to even make this undesired collision very robust (upper picture shows original valid lines, bottom picture is shrinked, last picture is zoomed with collision marker):
Yeah, shrinking works only for convex shapes!
(2022-01-10, 8:39)Stefan Frenz Wrote: [ -> ]I could think of the collision detection as an indicator to end a directed move or directed rotation. This would allow something like "move/rotate in this direction until the first collision occurs, remember the colliding triangles and try to get (approximate? calculate?) the one-directional move/rotate value" as in the following examples: move green block to the right along the red line until it reaches the black block (becomes blue) or rotate the green block around the bottom left edge clockwise until it reaches the black block (becomes cyan).

Yes, that's exactly how I'd picture it working. And at least for the rotation example, the math already exists in this script. For the move example, if the movement vector is normal to the colliding plane then it's simple; otherwise I guess it's just some similar trigonometry.

And if it's user-directed, it shouldn't consume any amount of processing power (unlike e.g. scanning a whole big model for collisions). The user could simply drag or rotate a part as normal until a collision occurs, and if the "proximity snapping" option is enabled, the program would automatically snap the movement back to the collision point.

Best of all, if collisions can be detected between triangles and vertices, they can also be detected between snap objects, which could also allow for the long-desired "rotation snapping" feature! (Some tolerance would be required here, as not all real-world rotations give exact pythagorean ratios and rely somewhat on plasticity.)
(2022-01-10, 15:19)Philippe Hurbain Wrote: [ -> ]Yeah, shrinking works only for convex shapes!

Yes, that's it. So I stopped the shrinking-approach and released LDInspector 0.6 with the current implementation of coplanar triangle checks (non-coplanar collisions are not changed and should be detected as before).
Thank you Roland for your help and LDCad 1.7-alpha-2. The discussed "place on ground" seems to work in a first version. Also porting the collision detection from Java to LUA will take more time...

At the moment the script can:
1: collect all parts recursively and print their filename/description together with its bounding box
2: move all parts/submodel-references so that the lowest point has y==0
3: tbd: check collision of parts by comparing pairs of triangles of pairs of parts

The current implementation collects all parts at first which would not be necessary for case 1 (just print instead of collect+print) and case 2 (just collect maxY instead of all bounding boxes of all parts), so this implementation is far from being optimal in regards to timing or memory usage. But it helps me porting my collision detection Wink and maybe it is useful for others doing similar stuff.

Code:
Part={triangles={}, orig={}, level=0, pMinX=math.huge,pMinY=math.huge,pMinZ=math.huge, pMaxX=-math.huge,pMaxY=-math.huge,pMaxZ=-math.huge}
function Part:new(orig, level)
  o={}
  setmetatable(o, self)
  self.__index=self
  self.orig=orig or {}
  self.level=level or 0
  self.pMinX=math.huge
  self.pMinY=math.huge
  self.pMinZ=math.huge
  self.pMaxX=-math.huge
  self.pMaxY=-math.huge
  self.pMaxZ=-math.huge
  return o
end
function Part:add(tri)
  table.insert(self.triangles, tri)
  if tri.pMinX<self.pMinX then
    self.pMinX=tri.pMinX
  end
  if tri.pMinY<self.pMinY then
    self.pMinY=tri.pMinY
  end
  if tri.pMinZ<self.pMinZ then
    self.pMinZ=tri.pMinZ
  end
  if tri.pMaxX>self.pMaxX then
    self.pMaxX=tri.pMaxX
  end
  if tri.pMaxY>self.pMaxY then
    self.pMaxY=tri.pMaxY
  end
  if tri.pMaxZ>self.pMaxZ then
    self.pMaxZ=tri.pMaxZ
  end
end
function Part:info()
  return self.orig:getFileName()..' ('..self.orig:getDescription()..'): '..self.pMinX..' '..self.pMinY..' '..self.pMinZ..' to '..self.pMaxX..' '..self.pMaxY..' '..self.pMaxZ
end

Triangle={p1={}, p2={}, p3={}, pMinX=math.huge,pMinY=math.huge,pMinZ=math.huge, pMaxX=-math.huge,pMaxY=-math.huge,pMaxZ=-math.huge}
function Triangle:new(p1, p2, p3)
  o={}
  setmetatable(o, self)
  self.__index=self
  self.p1=p1
  self.p2=p2
  self.p3=p3
  self.pMinX=math.huge
  self.pMinY=math.huge
  self.pMinZ=math.huge
  self.pMaxX=-math.huge
  self.pMaxY=-math.huge
  self.pMaxZ=-math.huge
  self:check(p1)
  self:check(p2)
  self:check(p3)
--  print('vec: ', p1,' / ',p2,' / ',p3)
--  print('min/max: ', self.pMinX,' ',self.pMinY,' ',self.pMinZ, ' to ', self.pMaxX,' ',self.pMaxY,' ',self.pMaxZ)
  return o
end
function Triangle:check(p)
  local pX,pY,pZ=p:get()
  if pX<self.pMinX then
    self.pMinX=pX
  end
  if pY<self.pMinY then
    self.pMinY=pY
  end
  if pZ<self.pMinZ then
    self.pMinZ=pZ
  end
  if pX>self.pMaxX then
    self.pMaxX=pX
  end
  if pY>self.pMaxY then
    self.pMaxY=pY
  end
  if pZ>self.pMaxZ then
    self.pMaxZ=pZ
  end
end

function colldet_walk(sf, ppos, level, parts)
  local partCnt=sf:getRefCount()
  for i=1,partCnt do
    local part=sf:getRef(i):getSubfile()
--    print('-- part ', part:getDescription())
    local pos=sf:getRef(i):getPosOri()
    pos:mulBA(ppos)
--    print('-- pos ', pos)
    local data=part:getRenderData()
    if data:isLinked() then
      local mpart=Part:new(part, level)
      table.insert(parts, mpart)
      for g=1,data:getGroupCount() do
        local grp=data:getGroup(g)
        if grp:isTriangle() then
          local cnt=grp:getCount()
--          print('triangle strip contains ', cnt, ' entries')
          for j=1,cnt do
            local a,b,c=grp:getPositionIndices(j)
--            print('triPosRel: ', data:getPosition(a), '; ', data:getPosition(b), '; ', data:getPosition(c))
--            print('triPosAbs: ', data:getPosition(a):getTransformed(pos), '; ', data:getPosition(b):getTransformed(pos), '; ', data:getPosition(c):getTransformed(pos))
            mpart:add(Triangle:new(data:getPosition(a):getTransformed(pos), data:getPosition(b):getTransformed(pos), data:getPosition(c):getTransformed(pos)))
          end
        elseif grp:isQuad() then
          local cnt=grp:getCount()
--          print('quad strip contains ', cnt, ' entries')
          for j=1,cnt do
            local a,b,c,d=grp:getPositionIndices(j)
--            print('quadPosRel: ', data:getPosition(a), '; ', data:getPosition(b), '; ', data:getPosition(c), '; ', data:getPosition(d))
--            print('quadPosAbs: ', data:getPosition(a):getTransformed(pos), '; ', data:getPosition(b):getTransformed(pos), '; ', data:getPosition(c):getTransformed(pos), '; ', data:getPosition(d):getTransformed(pos))
            mpart:add(Triangle:new(data:getPosition(a):getTransformed(pos), data:getPosition(b):getTransformed(pos), data:getPosition(c):getTransformed(pos)))
            mpart:add(Triangle:new(data:getPosition(c):getTransformed(pos), data:getPosition(d):getTransformed(pos), data:getPosition(a):getTransformed(pos)))
          end
        end
      end
    else
      colldet_walk(part, pos, level+1, parts)
    end
  end
end

function colldet_collect()
  local sf=ldc.subfile()
  local pos=ldc.matrix()
  --identity is set by default: pos:setIdentity()
  local parts={}
  colldet_walk(sf, pos, 0, parts)
  print('found ',#parts,' parts:')
  for i=1,#parts do
    print(i, ': ', parts[i]:info())
  end
end

function colldet_floor()
  local sf=ldc.subfile()
  local pos=ldc.matrix()
  pos:setIdentity()
  local parts={}
  colldet_walk(sf, pos, 0, parts)
  if #parts==0 then
    print('no part found')
  else
    local max=parts[1].pMaxY
    for i=2,#parts do
      if max<parts[i].pMaxY then
        max=parts[i].pMaxY
      end
    end
    local partCnt=sf:getRefCount()
    for i=1,partCnt do
      local ref=sf:getRef(i)
      local x,y,z=ref:getPos():get()
      ref:setPos(ldc.vector(x,y-max,z))
    end
  end
end

function colldet_check()
  print('not implemented yet!')
  local sf=ldc.subfile()
  local pos=ldc.matrix()
  pos:setIdentity()
  local parts={}
  colldet_walk(sf, pos, 0, parts)
  for i=2,#parts do
    for j=1,i-1 do
      local p1=parts[i]
      local p2=parts[j]
      print('todo: checking ', i, ' (', p1:info(), ') against ', j, ' (', p2:info(), ')')
      -- todo
    end
  end
end

function register()
  local macro=ldc.macro('CD: 1 collect parts')
  macro:setHint('Collision Detection: collect parts')
  macro:setEvent('run', 'colldet_collect')
  local macro=ldc.macro('CD: 2 move to floor')
  macro:setHint('Collision Detection: move bottom point down/up to 0')
  macro:setEvent('run', 'colldet_floor')
  local macro=ldc.macro('CD: 3 check collision')
  macro:setHint('Collision Detection: check part collision')
  macro:setEvent('run', 'colldet_check')
end

register()
Thank you so much for your help, Roland. I created a new thread for discussing the collision detection macro.