I was trying to implement a quad-tree data structure, and I got:

Segmentation fault (core dumped)

When I added 4 points, everything was fine, when I added the 5th - which
triggers a subdivision, and it then crashed.
There should probably be something that checks if a mixed-type array is trying
to be added to a uniform-type array.



So I partially debugged that by adding 'mixed' to the creation of the parent
array (duh), but now I get:

Parse Error: Expected 'undeclared identifier', UTF-8 signature BOM found instead
at File: QuadTree.pov Line: 114 Col: 9

That line reads:   #local _Q [7] = yes;


Once again, I am thwarted by arrays.   :(

--------------------------------------------------------------------------------

#version 3.8;
global_settings {assumed_gamma 1.0}

// /usr/share/qtpovray-3.8/include/

#include "rand.inc"
//#include "transforms.inc"

#declare Red = pigment {rgb <1, 0, 0>};
#declare Green = pigment {rgb <0, 1, 0>};
#declare Blue = pigment {rgb <0, 0, 1>};

#declare RX = 0;
#declare RY = 0;


camera {
 location <0, 0, -2>
 right x*image_width/image_height
 up y
 look_at <0, 0, 0>
 rotate x*RX
 rotate y*RY

}

light_source {<500, 1000, -4000>/100 rgb 1
 rotate x*RX
 rotate y*RY
}

sky_sphere {pigment {rgb 0.2}}




#declare Grid = pigment {rgb 0}
#declare Points = pigment {rgb <0, 1, 0>}
#declare Line = 0.01;

//---------------------------------------------------------------------------------------
#macro Show (Quad)
  sphere {<Quad[1], Quad[2], 0> Line pigment {Grid}}
  cylinder {<Quad[1], Quad[2], 0> <Quad[1], Quad[4], 0> Line pigment {Grid}}
  sphere {<Quad[1], Quad[4], 0> Line pigment {Grid}}
  cylinder {<Quad[1], Quad[4], 0> <Quad[3], Quad[4], 0> Line pigment {Grid}}
  sphere {<Quad[3], Quad[4], 0> Line pigment {Grid}}
  cylinder {<Quad[3], Quad[4], 0> <Quad[3], Quad[2], 0> Line pigment {Grid}}
  sphere {<Quad[3], Quad[2], 0> Line pigment {Grid}}
  cylinder {<Quad[3], Quad[2], 0> <Quad[1], Quad[2], 0> Line pigment {Grid}}
  #local _size = dimension_size (Quad[5], 1)-1;
  #for (P, 0, _size)
   sphere {Quad[5][P] Line pigment {Points}}
  #end
#end
//---------------------------------------------------------------------------------------
#macro Contains (_p, _r)
 #if (
  _p.x > _r.x - _rw &&
  _p.x < _r.x + _rw &&
  _p.y > _r.x - _rh &&
  _p.y > _r.x + _rh &&
 )
  #local result = true;
 #else
  #local result = false;
 #end

 result

#end
//---------------------------------------------------------------------------------------

#macro Rectangle (V1, V2)
 // take 2 corner vectors and sort to get min and max
 #local _minx = min (V1.x, V2.x);
 #local _miny = min (V1.y, V2.y);
 #local _maxx = max (V1.x, V2.x);
 #local _maxy = max (V1.y, V2.y);
 array [4] {_minx, _miny, _maxx, _maxy}
#end

//---------------------------------------------------------------------------------------
#macro newQuadtree (_r, _cap)
 #local _pointArray = array;
 #local _childArray = array;
 #local newQT = array mixed [9] {ID, _r[0], _r[1], _r[2], _r[3], _pointArray,
_cap, no, _childArray}
 #declare Quadtree [ID] = newQT;
 #declare ID = ID + 1; // increment the global ID counter
#end // end macro Quadtree
//---------------------------------------------------------------------------------------

#macro Subdivide (_Q, cap)
 #local _CX = (_Q[3] + _Q[1])/2; // center x
 #local _CY = (_Q[4] + _Q[2])/2; // center y
 #local _HW = (_Q[3] - _Q[1])/2; // half width
 #local _HH = (_Q[4] - _Q[2])/2; // half height

 // makes 4 new rectangles and creates quadtrees from them
 #local CP = <_CX, _CY>;     // Center of parent
 #local NWC = <_CX - _HW, _CY + _HH>;  // Northwest Corner of parent
 #local NEC = <_CX + _HW, _CY + _HH>;  // Northeast Corner of parent
 #local SWC = <_CX - _HW, _CY - _HH>;  // Southwest Corner of parent
 #local SEC = <_CX + _HW, _CY - _HH>;  // Southeast Corner of parent

 #local NWR = Rectangle (CP, NWC)   // Northwest Rectangle
 #local NWQ = newQuadtree (NWR, cap)   // Northwest Quadtree
 #local NER = Rectangle (CP, NEC)
 #local NEQ = newQuadtree (NER, cap)
 #local SWR = Rectangle (CP, SWC)
 #local SWQ = newQuadtree (SWR, cap)
 #local SER = Rectangle (CP, SEC)
 #local SEQ = newQuadtree (SER, cap)
 #local _Q [7] = yes;
#end// end macro Subdivide
//---------------------------------------------------------------------------------------


#macro Insert (_p, _Q)
 #local _size = dimension_size (_Q[5], 1);
 #local _capacity = _Q[6];
 #local _subdivided = _Q[7];

 #if (_size < _capacity)
  #local _Q[5][_size] = _p;
 #else
  #if (!_subdivided)
   Subdivide (_Q, _capacity)
  #end
 #end
#end
//---------------------------------------------------------------------------------------

#declare Quadtree = array mixed;
#declare ID = 0;
// make the initial quadtree
#declare Root = Rectangle (<-1, -1>, <1, 1>);
newQuadtree (Root, 4)

// add points to quadtree
#declare Seed = seed (123);
#for (P, 1, 5)
 #local _X = SRand (Seed);
 #local _Y = SRand (Seed);
 Insert (<_X, _Y, 0>, Quadtree[0])
#end

// show Quadtree
#declare treeSize = dimension_size (Quadtree, 1)-1;
#for (Bound, 0, treeSize)
 Show (Quadtree[Bound])
#end

Post a reply to this message

On 28/05/2020 02:24, Bald Eagle wrote:
> 
> I was trying to implement a quad-tree data structure, and I got:
> 
> Segmentation fault (core dumped)
> 
> When I added 4 points, everything was fine, when I added the 5th - which
> triggers a subdivision, and it then crashed.
> There should probably be something that checks if a mixed-type array is trying
> to be added to a uniform-type array.
> 
> 
> 
> So I partially debugged that by adding 'mixed' to the creation of the parent
> array (duh), but now I get:
> 
> Parse Error: Expected 'undeclared identifier', UTF-8 signature BOM found instead
> at File: QuadTree.pov Line: 114 Col: 9
> 
> That line reads:   #local _Q [7] = yes;
> 
> 
> Once again, I am thwarted by arrays.   :(
> 
> --------------------------------------------------------------------------------
> 
> #version 3.8;
> global_settings {assumed_gamma 1.0}
> 
> // /usr/share/qtpovray-3.8/include/
> 
> #include "rand.inc"
> //#include "transforms.inc"
> 
> #declare Red = pigment {rgb <1, 0, 0>};
> #declare Green = pigment {rgb <0, 1, 0>};
> #declare Blue = pigment {rgb <0, 0, 1>};
> 
> #declare RX = 0;
> #declare RY = 0;
> 
> 
> camera {
>   location <0, 0, -2>
>   right x*image_width/image_height
>   up y
>   look_at <0, 0, 0>
>   rotate x*RX
>   rotate y*RY
> 
> }
> 
> light_source {<500, 1000, -4000>/100 rgb 1
>   rotate x*RX
>   rotate y*RY
> }
> 
> sky_sphere {pigment {rgb 0.2}}
> 
> 
> 
> 
> #declare Grid = pigment {rgb 0}
> #declare Points = pigment {rgb <0, 1, 0>}
> #declare Line = 0.01;
> 
>
//---------------------------------------------------------------------------------------
> #macro Show (Quad)
>    sphere {<Quad[1], Quad[2], 0> Line pigment {Grid}}
>    cylinder {<Quad[1], Quad[2], 0> <Quad[1], Quad[4], 0> Line pigment {Grid}}
>    sphere {<Quad[1], Quad[4], 0> Line pigment {Grid}}
>    cylinder {<Quad[1], Quad[4], 0> <Quad[3], Quad[4], 0> Line pigment {Grid}}
>    sphere {<Quad[3], Quad[4], 0> Line pigment {Grid}}
>    cylinder {<Quad[3], Quad[4], 0> <Quad[3], Quad[2], 0> Line pigment {Grid}}
>    sphere {<Quad[3], Quad[2], 0> Line pigment {Grid}}
>    cylinder {<Quad[3], Quad[2], 0> <Quad[1], Quad[2], 0> Line pigment {Grid}}
>    #local _size = dimension_size (Quad[5], 1)-1;
>    #for (P, 0, _size)
>     sphere {Quad[5][P] Line pigment {Points}}
>    #end
> #end
>
//---------------------------------------------------------------------------------------
> #macro Contains (_p, _r)
>   #if (
>    _p.x > _r.x - _rw &&
>    _p.x < _r.x + _rw &&
>    _p.y > _r.x - _rh &&
>    _p.y > _r.x + _rh &&
>   )
>    #local result = true;
>   #else
>    #local result = false;
>   #end
> 
>   result
> 
> #end
>
//---------------------------------------------------------------------------------------
> 
> #macro Rectangle (V1, V2)
>   // take 2 corner vectors and sort to get min and max
>   #local _minx = min (V1.x, V2.x);
>   #local _miny = min (V1.y, V2.y);
>   #local _maxx = max (V1.x, V2.x);
>   #local _maxy = max (V1.y, V2.y);
>   array [4] {_minx, _miny, _maxx, _maxy}
> #end
> 
>
//---------------------------------------------------------------------------------------
> #macro newQuadtree (_r, _cap)
>   #local _pointArray = array;
>   #local _childArray = array;
>   #local newQT = array mixed [9] {ID, _r[0], _r[1], _r[2], _r[3], _pointArray,
> _cap, no, _childArray}
>   #declare Quadtree [ID] = newQT;
>   #declare ID = ID + 1; // increment the global ID counter
> #end // end macro Quadtree
>
//---------------------------------------------------------------------------------------
> 
> #macro Subdivide (_Q, cap)
>   #local _CX = (_Q[3] + _Q[1])/2; // center x
>   #local _CY = (_Q[4] + _Q[2])/2; // center y
>   #local _HW = (_Q[3] - _Q[1])/2; // half width
>   #local _HH = (_Q[4] - _Q[2])/2; // half height
> 
>   // makes 4 new rectangles and creates quadtrees from them
>   #local CP = <_CX, _CY>;     // Center of parent
>   #local NWC = <_CX - _HW, _CY + _HH>;  // Northwest Corner of parent
>   #local NEC = <_CX + _HW, _CY + _HH>;  // Northeast Corner of parent
>   #local SWC = <_CX - _HW, _CY - _HH>;  // Southwest Corner of parent
>   #local SEC = <_CX + _HW, _CY - _HH>;  // Southeast Corner of parent
> 
>   #local NWR = Rectangle (CP, NWC)   // Northwest Rectangle
>   #local NWQ = newQuadtree (NWR, cap)   // Northwest Quadtree
>   #local NER = Rectangle (CP, NEC)
>   #local NEQ = newQuadtree (NER, cap)
>   #local SWR = Rectangle (CP, SWC)
>   #local SWQ = newQuadtree (SWR, cap)
>   #local SER = Rectangle (CP, SEC)
>   #local SEQ = newQuadtree (SER, cap)
>   #local _Q [7] = yes;
> #end// end macro Subdivide
>
//---------------------------------------------------------------------------------------
> 
> 
> #macro Insert (_p, _Q)
>   #local _size = dimension_size (_Q[5], 1);
>   #local _capacity = _Q[6];
>   #local _subdivided = _Q[7];
> 
>   #if (_size < _capacity)
>    #local _Q[5][_size] = _p;
>   #else
>    #if (!_subdivided)
>     Subdivide (_Q, _capacity)
>    #end
>   #end
> #end
>
//---------------------------------------------------------------------------------------
> 
> #declare Quadtree = array mixed;
> #declare ID = 0;
> // make the initial quadtree
> #declare Root = Rectangle (<-1, -1>, <1, 1>);
> newQuadtree (Root, 4)
> 
> // add points to quadtree
> #declare Seed = seed (123);
> #for (P, 1, 5)
>   #local _X = SRand (Seed);
>   #local _Y = SRand (Seed);
>   Insert (<_X, _Y, 0>, Quadtree[0])
> #end
> 
> // show Quadtree
> #declare treeSize = dimension_size (Quadtree, 1)-1;
> #for (Bound, 0, treeSize)
>   Show (Quadtree[Bound])
> #end
> 
> 

I think that :

the macro "newQuadtree()" retrun nothing...
so #local SEQ = newQuadtree (SER, cap) is not valid.
and the parser freaks out :)





-- 
Kurtz le pirate
Compagnie de la Banquise

Post a reply to this message

kurtz le pirate <kur### [at] gmailcom> wrote:

> I think that :
>
> the macro "newQuadtree()" retrun nothing...
> so #local SEQ = newQuadtree (SER, cap) is not valid.
> and the parser freaks out :)

I already caught that and fixed those declarations - good eye, catching those
though.  :)

I still get the same weird error.

I have a few other ideas in mind that I will test out, but it's one of the
strangest errors I've gotten...

Post a reply to this message

> "Bald Eagle" <cre### [at] netscapenet> wrote:

I'm still intrigued.

> #macro newQuadtree (_r, _cap)
> #local _pointArray = array;
> #local _childArray = array;
> #local newQT = array mixed [9] {ID, _r[0], _r[1], _r[2], _r[3], _pointArray,
>_cap, no, _childArray}

Can an array be invoked from another array?


>#if (
>  _p.x > _r.x - _rw &&
>  _p.x < _r.x + _rw &&
>  _p.y > _r.x - _rh &&
>  _p.y > _r.x + _rh &&
> )

And pov-ray reads "&&" the same as "&"?
http://wiki.povray.org/content/Reference:Numeric_Expressions

B. Gimeno

Post a reply to this message

"B. Gimeno" <nomail@nomail> wrote:

> Can an array be invoked from another array?

Arrays can be child elements of other parent arrays.

http://news.povray.org/povray.text.tutorials/thread/%3C3f13449b$1@news.povray.org%3E/

> >#if (
> >  _p.x > _r.x - _rw &&
> >  _p.x < _r.x + _rw &&
> >  _p.y > _r.x - _rh &&
> >  _p.y > _r.x + _rh &&
> > )
>
> And pov-ray reads "&&" the same as "&"?

No, probably not.   That was a macro I was copy/pasting from a javascript
function that I have yet to invoke, get errors, and edit for proper syntax.  ;)

A dozen segmentation faults kinda derailed all of that.


At the moment, I have tracked the problem down to something I ran into before
(somewhere), but had forgotten about - creating an array of arrays, and then
trying to access an uninitialized element of that data structure.   POV-Ray's
source code doesn't have any safeguards against that sort of shenanigans by the
user, freaks out when the element of a parent array is another array, and the
desired element of _that_ array doesn't exist --- and it crashes.

I'm not sure if an ifdef() will protect against this kind of thing, but I will
likely try it out and see - perhaps later on today.

I still need to get the "big picture" straigtened out in my head - even if it's
just a flowchart or pseudo-code, so any advice, help, nuggest of wisdom, or
other breadcrumbs are most appreciated.

Post a reply to this message