[vJASS] Bezier

[Almia]

I saw BPower wrote an idea before, a struct for Curves

library Bezier/* 1.0
**************************************************************************************
*
*   Used for creating/building N-degree Bezier curves
*
*   Bezier is a list of 3d vector points.
*
*   Take note that the vectors are not destroyed by a Bezier instance if it is
*   destroyed
*
**************************************************************************************
*
*   */ requires /*
*
*   */ Vector /*
*   [url]www.wc3c.net/showthread.php?t=87027[/url]
*
**************************************************************************************
*
*   API
*
*   struct Bezier
*       readonly vector head
*       readonly vector tail
*           - both ends of the Bezier curve
*
*       static method create takes vector a, vector b returns thistype
*           - create a 1-degree bezier
*
*       method has takes vector v returns boolean
*           - check if v is a node of this
*
*       method pushTail takes vector v returns nothing
*       method pushHead takes vector v returns nothing
*       method insert takes vector v, vector p, vector n returns nothing
*           - insert methods
*           - used to insert points on the Bezier's point list
*
*       method popTail takes nothing returns nothing
*       method popHead takes nothing returns nothing
*       method remove takes vector v returns nothing
*           - remove the nodes
*
*       method get takes real t returns vector
*           - get the point on the Bezier at factor t
*
*       method destroy takes nothing returns nothing
*
**************************************************************************************
*
*   Credits
*
*   Anitarf
*
**************************************************************************************/
    struct Bezier
        readonly vector head
        readonly vector tail
        
        private static integer array next
        private static integer array prev
        
        static method create takes vector a, vector b returns thistype
            local thistype this = allocate()
            set head = a
            set tail = b
            set next[b] = 0
            set prev[b] = a
            set next[a] = b
            set prev[a] = 0
            return this
        endmethod
        
        method has takes vector v returns boolean
            local vector p 
            if v != 0 then
                set p = head
                loop
                    exitwhen p == 0
                    if v == p then
                        return true
                    endif
                    exitwhen p == tail
                    set p = next
                endloop
            endif
            return false
        endmethod
        
        method pushTail takes vector v returns nothing
            /*
            *   Check if v is not empty and list has not yet owned v
            */
            if v != 0 and not has(v) then
                set next[tail] = v
                set prev[v] = tail
                set next[v] = 0
                set tail = v
            endif
        endmethod
        
        method pushHead takes vector v returns nothing
            /*
            *   Check if v is not empty and list has not yet owned v
            */
            if v != 0 and not has(v) then
                set prev[head] = v
                set next[v] = head
                set prev[v] = 0
                set head = v
            endif
        endmethod
        
        method insert takes vector v, vector p, vector n returns nothing
            /*
            *   Check if:
            *   - v is not yet contained
            *   - v is not equal to it's prev and next pointers
            *     (which is vectors n and p)
            */
            if not(has(v)  or v == p or p == n or n == v) then
                /*
                *   Determine if p is the head node
                */
                if p != 0 then
                    set next = v
                else
                    set head = v
                endif
                set next[v] = n
                set prev[v] = p
                /*
                *   Determien if n is the tail node
                */
                if n != 0 then
                    set prev[n] = v
                else
                    set tail = v
                endif
            endif
        endmethod
        
        method popTail takes nothing returns nothing
            local vector node
            /*
            *   if the list only contains two points
            *   abort popping
            */
            if next[head] == tail then
                return 
            endif
            set node = prev[tail]
            set prev[tail] = 0
            set tail = node
        endmethod
        
        method popHead takes nothing returns nothing
            local vector node
            /*
            *   if the list only contains two points
            *   abort popping
            */
            if next[head] == tail then
                return
            endif
            set node = next[head]
            set next[head] = 0
            set head = node
        endmethod
        
        method remove takes vector v returns nothing
            /*
            *   Check if list has v and list has greater than
            *   2 nodes.
            */
            if has(v) and not (next[head] == tail) then
                set next[prev[v]] = next[v]
                set prev[next[v]] = prev[v]
                if v == head then
                    set head = next[v]
                endif
                if v == tail then
                    set tail = prev[v]
                endif
            endif
        endmethod
        /*
        *   Perform iterative de Casteljau method
        */
        method get takes real t returns vector
            local real array x
            local real array y
            local real array z
            local integer points
            
            local integer i
            local integer k
            
            if t > 1 and t < 0 then
                return 0
            endif
            set points = 0
            set i = head
            loop
                set points = points + 1
                set x[points] = vector(i).x
                set y[points] = vector(i).y
                set z[points] = vector(i).z
                exitwhen i == tail
                set i = next[i]
            endloop
            /*
            *   This is the method where it minimizes the list
            *   from N-degree to 1-degree Bezier by factor t
            */
            set k = 1
            loop
                exitwhen k > points
                set i = 1
                loop
                    exitwhen i > points - k
                    set x[i] = (1 - t)*x[i] + t*x[i + 1]
                    set y[i] = (1 - t)*y[i] + t*y[i + 1]
                    set z[i] = (1 - t)*z[i] + t*z[i + 1]
                    set i = i + 1
                endloop
                set k = k + 1
            endloop
            return vector.create(x[1], y[1], z[1])
        endmethod
        
        method destroy takes nothing returns nothing
            call deallocate()
            /*
            *   clear list
            */
            loop
                exitwhen next[head] == tail
                call popHead()
            endloop
            set next[head] = 0
            set prev[tail] = 0
        endmethod
    endstruct
endlibrary

Test code:

struct Tester extends array
    /*
    *   The degree of curve
    *   the actual degree is "degree" - 1
    */
    private static constant integer degree = 3 /* replace this with any value greater than 2 */
    /*
    *   The precision of drawing the special effect
    *   "t" is where the unit is moved(the peasant)
    */
    private static constant real t = 0.5
    private static constant real precision = 0.01
    
    private static constant real sfxPeriod = 0.25
    private static real sfxT = 0
    
    private static constant timer T = CreateTimer()
    
    private static Bezier b
    
    private static unit mover
    private static unit array units
    private static vector array vectors
    
    private static method P takes nothing returns nothing
        local vector v = b.get(t)
        local integer i
        local real u
        call SetUnitX(mover, v.x)
        call SetUnitY(mover, v.y)
        //call SetUnitFlyHeight(mover, v.z, 0)
        call v.destroy()
        set i = 1 
        loop
            exitwhen i > degree
            set vectors[i].x = GetUnitX(units[i])
            set vectors[i].y = GetUnitY(units[i])
            set i = i + 1
        endloop
        
        set sfxT = sfxT - 0.03125
        if sfxT <= 0 then
            set sfxT = sfxPeriod
            set u = 0
            loop
                exitwhen u > 1
                set v = b.get(u)
                call DestroyEffect(AddSpecialEffect("Abilities\\Weapons\\SpiritOfVengeanceMissile\\SpiritOfVengeanceMissile.mdl", v.x, v.y))
                call v.destroy()
                set u = u + precision
            endloop
        endif
    endmethod

    private static method onInit takes nothing returns nothing
        local integer i = 1
        loop
            exitwhen i > degree
            set vectors[i] = vector.create(I2R(i)*128, I2R(i)*128, 0)
            set units[i] = CreateUnit(Player(0), 'hfoo', I2R(i)*128, I2R(i)*128, 0)
            
            if i == 2 then
                set b = Bezier.create(vectors[1], vectors[2])
            elseif i > 2 then
                call b.pushTail(vectors[i])
            endif
            set i = i + 1
        endloop
        
        set mover = CreateUnit(Player(0), 'hpea', 0, 0, 0)
        
        call TimerStart(T, 0.03125, true, function thistype.P)
    endmethod
endstruct

Screenshots:

2nd Degree

3rd Degree

4th Degree

[edit]
The right term was "order" not "degree" >.< that's why I feel so uncomfortable

 

[IcemanBo]

Replace all "degree" with "order" , it is "of first order", "of second order" etc. instead of "of first degree", "of second degree".

/*
    *   The degree of curve
    *   the actual degree is "degree" - 1
    */
    private static constant integer degree = 2 /* replace this with any value greater than 2 */

Why this confusion with " - 1" ? And btw, making a bezier of first order (with 2 control points) must be valid, also, so the value must not be greater than "2".

Not detaily read the code, but demo seems to work good.

Instead of not (a == b) one could write (a != b) ^^

 

[IcemanBo]

I am not sure if Vector is required. From maths side it only needs x/y/z Point struct, and a vector's primary goal is not to simply read the x/y/z from a representer point.
A very simple custom struct might also fulfil this task and would drop the requirement.

edit: author is not active, so graveyarded for now

 

[Almia]

perhaps a PointData?